Previous Up Next

3.6��ML4 — 再帰的関数定義の導入

多くのプログラミング言語では，変数を宣言するときに，その定義にその変数 自身を参照するという，再帰的定義(recursive definition)が許され ている．ML4 では，このような再帰的定義の機能を導入する．ただし， 単純化のため再帰的定義の対象を関数に限定する．

まず，再帰的定義のための構文 let rec 式・宣言を，以下の文法で導入する．

�<プログラム>::=…�| let�rec �<識別子1>�=�fun�<識別子2> →�<式>�;;
��<式>::=…�
 |let�rec �<変数1>�=�fun�<変数2> →�<式1>��in�<式2>

この構文の基本的なセマンティクスは let 式・宣言と似ていて，環境 を宣言にしたがって拡張したもとで本体式を評価するものである．ただし，環 境を拡張する際に，再帰的な定義を処理する工夫が必要になる． 再帰的定義 の場合，定義される関数の閉包内の環境を，今これから作ろうと している束縛関係まで含んでいるものにしたい．これを実現するために，い わゆるパックパッチ(backpatching)と呼ばれる手法を用いる．バック パッチは，最初，ダミーの環境を用意して，ともかく関数閉包を作成し，環境 を拡張してしまう．そののちダミーの環境を，たった今拡張した環境に 更新する，という手法である．Objective Caml で実装する際には，関数閉 包の環境を更新できるように，(例えば)参照を用いる．

syntax.ml:

type exp = 
   ...
  | LetRecExp of id * id * exp * exp

type program = 
   ...
  | RecDecl of id * id * exp

eval.ml:

type exval =
   ...
  | ProcV of id * exp * dnval Environment.t ref

let rec eval_exp env = function
   ...
  | LetRecExp (id, para, exp1, exp2) ->
      let dummyenv = ref Environment.empty in
      let newenv =
          Environment.extend id (ProcV (para, exp1, dummyenv)) env in
       dummyenv := newenv;
       eval_exp newenv exp2

Figure 10: 再帰的関数定義

図10が，主なプログラムの変更点である． eval_exp の LetRecExp を処理する部分は，上で述べたバックパッチを まさに実現している．

Exercise�14��[必修課題] 図に示した syntax.ml にしたがって，parser.mly と lexer.mll を 完成させ，ML4 インタプリタを作成し，テストせよ．(let rec宣言 も実装すること．)
Exercise�15��[難易度 2] andを使って変数を同時にふたつ以上宣言できるように let rec 式・宣言を拡張し，相互再帰的関数をテストせよ．
Previous Up Next