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