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