Previous Up Next

3.5��ML3 — 関数の導入

ここまでのところ，この言語には，いくつかのプリミティブ関数(二項演算子) しか提供されておらず，MLプログラマが(プリミティブを組み合わ せて)新しい関数を定義することはできなかった．ML3 では，fun式 による関数抽象と，関数適用を提供する．

3.5.1��関数式と適用式

まずは，ML3 の式の文法を示す．

<式>::=…�
 |fun�<識別子>�→�<式>�
 |<式1>�<式2>

構文に関するインタプリタ・プログラムは，図8に示す． 適用式は左結合で，他の全ての演算子よりも結合が強いとする．

syntax.ml:

type exp = 
   ...
  | FunExp of id * exp
  | AppExp of exp * exp

parser.mly:

%token RARROW FUN

Expr :
   ...
   | FunExpr { $1 }

MExpr :
    MExpr MULT AppExpr { BinOp (Mult, $1, $3) }
  | AppExpr { $1 }

AppExpr :
    AppExpr AExpr { AppExp ($1, $2) }
  | AExpr { $1 }

lexer.mll:

let reservedWords = [
   ...
  ("fun", Parser.FUN);
   ...
]
...
| "=" { Parser.EQ }
| "->" { Parser.RARROW }

Figure 8: 関数と適用(1)

3.5.2��関数閉包と適用式の評価

さて，Objective Camlと同様，ML3 においても，関数は式を評価した結果とな るだけでなく，変数の束縛対象にもなる第一級の値(first-class value)として扱う．そのため，expressed value, denoted value ともに 関数値を加えて拡張する．

Expressed Value=整数�(…,�−2,�−1,�0,�1,�2,�3,�…)�+�真偽値�+ 関数値�
Denoted Value=Expressed Value

さて，関数値をどのように表現するかを考える．fun 式が適用された時には，パラメータを実引数(の値)に束縛し，関数本体を評価 するので，少なくともパラメータの名前と，本体の式の情報が必要である．しかし， 一般的には，以下の例のように，関数本体の式にパラメータ以外の変数(つま り自由変数)が出現することも可能である． 


let x = 2 in
let addx = fun y → x + y in
addx 4

x の静的束縛を実現するためには，この addx の適用を行う際には 本体中の x が 2 であることを記録しておかなければならない． というわけで，一般的に関数が適用される時には，

  1. パラメータ名
  2. 関数本体の式，に加え
  3. 本体中のパラメータで束縛されていない変数(自由変数)の束縛情報 (名前と値)

が必要になる．この3つを組にしたデータを関数閉包・クロージャ(function closure) と呼び，これを関数値として用いる．ここで作成するインタプリ タでは，本体中の自由変数の束縛情報として，fun式が評価された時点 での環境全体を使用する．これは，本体中に現れない変数に関する余計な束縛 情報を含んでいるが，もっとも単純な関数閉包の実現方法である．

以上を踏まえた eval.ml への主な変更点は図9のようになる． 式の値には，環境を含むデータである関数閉包が含まれるため，exval と dnval の定義が(相互)再帰的になる．関数 値は ProcV コンストラクタで表され，上で述べたように，パラメータ名の リスト，本体の式と環境の組を保持する．eval_exp で FunExp を処理す る時には，その時点での環境，つまりenv を使って関数閉包を作っている． 適用式の処理は，適用される関数の評価，実引数の評価を行った後，本当に適 用されている式が関数かどうかのチェックをして，本体の評価を行っている． 本体の評価を行う際の環境 newenv は，関数閉包に格納されている環境を，パ ラメータ・実引数で拡張して得ている．

eval.ml:

type exval =
    IntV of int
  | BoolV of bool
  | ProcV of id * exp * dnval Environment.t
and dnval = exval

let rec eval_exp env = function
   ...
  | FunExp (id, exp) -> ProcV (id, exp, env)
  | AppExp (exp1, exp2) ->
      let funval = eval_exp env exp1 in
      let arg = eval_exp env exp2 in
       (match funval with
            ProcV (id, body, env') ->
              let newenv = Environment.extend id arg env' in
                eval_exp newenv body
          | _ -> err ("Non-function value is applied"))

Figure 9: 関数と適用(3)

Exercise�8��[必修課題] ML3 インタプリタを作成し，高階関数が正しく動作するかなどを含めて テストせよ．
Exercise�9��[難易度 2] Objective Caml での「(中置演算子) 」記法をサポートし，プリミティブ演算 を通常の関数と同様に扱えるようにせよ．例えば 

let threetimes = fun f → fun x → f (f x x) (f x x) in
  threetimes (+) 5
は，20を出力する．
Exercise�10��[難易度 1] Objective Caml の 
fun x1 ... xn → ...
let f x1 ... xn = ...
といった簡略記法をサポートせよ．
Exercise�11��[難易度 1] 以下は，加算を繰り返して 4 による掛け算を実現している ML3 プログラムである．これを改造して，階乗を計算するプログラムを 書け． 

let makemult = fun maker → fun x →
                 if x < 1 then 0 else 4 + maker maker (x + -1) in
let times4 = fun x → makemult makemult x in
  times4 3
Exercise�12��[難易度 1] 静的束縛とは対照的な概念として動的束縛(dynamic binding)があ る．動的束縛の下では，関数本体は，fun式を評価した時点ではなく， 関数呼び出しがあった時点での環境をパラメータ・実引数で拡張した環境下 で評価される．例えば， 

let a = 3 in
let p = fun x → x + a in
let a = 5 in
  a * p 2
というプログラムで，関数p本体中の a は 3 ではなく 5 に束縛される．インタプリタを改造し，動的束縛を 実現せよ．
Exercise�13��[難易度 1] 動的束縛の下では，ML4 で導入するような再帰定義を実現するための特別な仕組みや，Exercise�11のようなトリックを使うことなく， 再帰関数を定義できる．以下のプログラムを静的束縛・動的束縛の下で 実行し，結果について説明せよ． 

let fact = fun n → n + 1 in
let fact = fun n → if n < 1 then 1 else n * fact (n + -1) in
  fact 5
Previous Up Next