Previous Up Next
3.6 mini Scheme4 --- 関数の導入

ここまでのところ，この言語には，いくつかのプリミティブ操作しか提供され ておらず，mini Schemeプログラマが(プリミティブを組み合わせて)新しい操作 を定義することはできなかった．mini Scheme4 では，関数を定義する機能と，定 義された関数を適用する機能を提供する．

3.6.1 関数式と適用式

まずは，mini Scheme4 の文法を示す．
<式> ::= …
  | (lambda (<識別子1> … <識別子n>) <式>)
  | (<式0> … <式n>)
構文的な部分に関するインタプリタ・プログラムは，図10に示す．
syntax.ml:

type exp = 
   ...
  | Lambda of id list * exp
  | App of exp * exp list


parser.mly:

%token LAMBDA

Exp :
   ...
  | LPAREN LAMBDA LPAREN IDlist RPAREN Exp RPAREN { Lambda ($4, $6) }
  | LPAREN Exp Explist RPAREN { App ($2, $3) }

...
IDlist :
 /* empty */ { [] }
  | ID IDlist { $1 :: $2 }

Explist :
 /* empty */ { [] }
  | Exp Explist { $1 :: $2 }


lexer.mll:

let reservedWords = [
   ...
  ("lambda", Parser.LAMBDA);
]

Figure 10: 関数と適用(1)

lambda 式は，<識別子1>，...，<識別子 n> をパラメータとして，<式> を評価する関数を表す．パ ラメータとして宣言される，<識別子1>，...，<識別子n> の有効範囲は関数本体の<式>全体である．関数の 適用はプリミティブ適用と似た構文を持ち，<式1>, ..., <式n>の値を実引数として関数<式0>を呼び出す．

例えば， 

(let ((f (lambda (x y) (* (+ x y) 3))))
   (f i x))
のようなプログラムが書ける．また，lambda 式は，式が必要な場所のど こにでも書くことができるので，上のプログラムを 

((lambda (x y) (* (+ x y) 3)) i x)
などと書くこともできる．また，関数は他の関数への引数として渡すこともできる． 

(let ((twice (lambda (f x) (f (f x))))
      (square (lambda (x) (* x x))))
   (twice square 5))
は，5 の自乗の自乗を計算する．

3.6.2 値の定義の拡張

さて，上の例のように，mini Scheme4 においては，関数は式を評価した結果とな るだけでなく，変数の束縛対象にもなる第一級の値(first-class value)として扱う．そのため，Expressed Value, Denoted Value ともに 関数値を加えて拡張する．
Expressed Value = 整数 (…, -2, -1, 0, 1, 2, 3, …) + 関数値
Denoted Value = 整数 + 関数値
上の式で + は「または」を示している．関数値が具体的にどのように表 現されるかは，ひとまず置いておいて，これをObjective Camlプログラムとして表現 すると，以下のような定義になる． 
type exval = 
    IntV of int
  | ProcV of (* discussed later *)
and dnval = exval
値の種類が増えるため，インタプリタ内で値を直接扱う部分，つまりプリミティ ブの処理，if 式の処理では，プリミティブの引数やif 式のテス ト部分を評価した値が整数であるかをチェックする必要がでてくる．これに関 する主な変更点を図11に示す．
core.ml:

let apply_prim p args =
  match p, args with
  | (Plus, [IntV i; IntV j]) -> IntV (i + j)
  | (Plus, [_; _]) ->
     failwith "One of the arguments is not an integer: +"
  | (Plus, _) -> failwith "Arity mismatch: +"
   ...

let rec eval_exp env = function
   ...
  | If (e1, e2, e3) ->
      (match eval_exp env e1 with
        IntV test ->
          if test <> 0 then eval_exp env e2
          else eval_exp env e3
      | _ -> failwith "test expression is not an integer")
   ...

Figure 11: 関数と適用(2)

apply_prim では，各々のプリミティブについて，引数の数は正しいが， 引数(のいくつか)が整数で無い場合の処理を追加する． 図 11では Plus の場合のみを記述したが，その他のプリミ ティブも同様に書かれる．また，eval_exp では，コンストラクタ If の処理で， e1 の評価結果が整数であるかを明示的にチェックするコードになっている．

3.6.3 関数閉包と適用式の評価

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

(let ((x 2))
  (let ((addx (lambda (y) (+ x y))))
    (addx 4))
この addx の適用を行う際には，x の静的束縛を実現するために， 本体中の x が 2 であることを記録しておかなければならない． つまり，一般的に関数が適用される時には，
  1. パラメータ名

  2. 関数本体の式，に加え

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

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

type exval = 
    IntV of int
  | ProcV of id list * exp * env
and dnval = ...
and env = ...

let rec eval_exp env = function
   ...
  | Lambda (ids, body) -> ProcV (ids, body, env)
      (* closed in the current env *)
  | App (rator, rands) ->
      let proc = eval_exp env rator in
      let args = eval_rands env rands in
      (match proc with
        (* check the operator is a procedure value *)
        ProcV (ids, body, env) ->
        if List.length ids = List.length args then
            (* extend the env in the closure *)
            let newenv = extend_env ids args env in
            eval_exp newenv body
          else failwith "# of parameters and arguments don't agree"
      | _ -> failwith "Applying a non-procedure value")

Figure 12: 関数と適用(3)


Exercise 8  [必修課題] mini Scheme4 インタプリタを作成し，テストせよ．

Exercise 9  [難易度 2] このインタプリタは，プリミティブと宣言された関数を区別しているので， 


(let ((twice (lambda (f x) (f (f x)))))
   (twice add1 3))
のように，プリミティブを関数への引数として渡したりすることができない． (そもそもこれは構文的に mini Schemeプログラムではない．) プリミティブも第一級の値として扱えるようにイン タプリタを改造・テストせよ．(ヒント: プリミティブはキーワードとして扱 わずただの識別子として導入する．また，Expressed Value に含め，大域環境 に束縛する．)

Exercise 10  [難易度 2] 以下は，加算を繰り返して 4 による掛け算を実現している mini Scheme4 プログラムである．これを改造して，階乗を計算するプログラムを 書け． 


(let 
  ((makemult
    (lambda (maker x)
      (if (= x 0) 0 (+ 4 (maker maker (sub1 x)))))))
  (let ((times4 (lambda (x) (makemult makemult x))))
    (times4 3)))

Exercise 11  [難易度 2] mini Scheme3 を導入した際に，静的束縛と動的束縛について述べた．動的束縛 の下では，関数本体は，lambda式を評価した時点ではなく， 関数呼び出しがあった時点での環境をパラメータ・ 実引数で拡張した環境下で評価される．例えば， 


(let ((a 3))
  (let ((p (lambda (x) (+ x a)))
        (a 5))
    (* a (p 2))))
というプログラムで，関数本体中の a は 3 ではなく 5 に束縛される． インタプリタを改造し，動的束縛(dynamic binding)を実現せよ．

Exercise 12  [難易度 1] 動的束縛の下では，mini Scheme5 で導入するような再帰のための特別な仕組みや， Exercise 10のようなトリックを使うことなく， 再帰関数を定義できる．以下のプログラムを静的束縛・動的束縛の下で 実行し，結果について説明せよ． 


(let ((fact (lambda (n) (add1 n))))
  (let ((fact (lambda (n)
           (if (= n 0) 1
               (* n (fact (sub1 n)))))))
    (fact 5)))

Previous Up Next