mini Scheme4 --- 関数の導入

mini Scheme⁴ --- 関数の導入

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

3.6.1

関数式と適用式

まずは，mini Scheme⁴ の文法を示す．

<式>	::=	…
	\|	(lambda (<識別子₁> … <識別子_n>) <式>)
	\|	(<式₀> … <式_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 式は，<識別子₁>，...，<識別子 _n> をパラメータとして，<式> を評価する関数を表す．パラメータとして宣言される，<識別子₁>，...，<識別子_n> の有効範囲は関数本体の<式>全体である．関数の適用はプリミティブ適用と似た構文を持ち，<式₁>, ..., <式_n>の値を実引数として関数<式₀>を呼び出す．

例えば，


(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 Scheme⁴ においては，関数は式を評価した結果となるだけでなく，変数の束縛対象にもなる第一級の値(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 であることを記録しておかなければならない．つまり，一般的に関数が適用される時には，

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

が必要になる．この３つを組にしたデータを関数閉包・クロージャ(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 10 [必修課題] mini Scheme⁴ インタプリタを作成し，テストせよ．

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



(let ((twice (lambda (f x) (f (f x)))))
   (twice add1 3))

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

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



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

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



(let ((a 3))
  (let ((p (lambda (x) (+ x a)))
        (a 5))
    (* a (p 2))))

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

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



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