2021/6/24 IoPLMaterials | Materials for the class “Implementation of Programming Languages” in Kyoto University.
https://kuis-isle3sw.github.io/IoPLMaterials/textbook/chap03-6.html 1/3
IoPLMaterials
Edit this page Report an issue
MiniML4: 再帰的関数定義の導入
多くのプログラミング言語では，変数を宣言するときに，その定義にその変数自身を参照する
という，再帰的定義 (recursive definition) が許されている．MiniML4 では，このような再帰的定
義の機能を導入する．ただし，単純化のため再帰的定義の対象を関数に限定する．
まず，再帰的定義のための構文 let rec 式・宣言を，MiniML3 の文法を拡張する形で以下のよ
うに導入する．
P ::= …
| let rec <識別子> = fun <識別子> -> e ;;
e ::= …
| let rec <識別子> = fun <識別子> -> e in e
この構文の基本的なセマンティクスは let 式・宣言と似ていて，環境を宣言にしたがって拡張
したもとで本体式を評価するものである．ただし，環境を拡張する際に，再帰的な定義を処理
する工夫が必要になる．例で説明しよう．
let rec fact = fun n -> if n = 0 then 1 else n * (fact (n + (-1))) in
fact 5
おなじみの階乗関数である．この式がどう評価されるかを説明しよう．
まず関数 fact を関数閉包に束縛する．この関数閉包は， n を受け取って if n = 0 then 1
else n * (fact (n + (-1))) の評価結果を返す関数である．この関数閉包内には，以前説明
したとおり，関数閉包を作る時点での環境が保存されており， fact が束縛される先の関数
閉包内の環境は，これが作成されたときの環境，すなわちデフォルトの大域環境
initial_env である．
この関数閉包を fact 5 で使用している．関数適用を行う際には，関数閉包内に保存されて
いる環境を取り出し，その環境を仮引数に対する束縛で拡張した上で関数本体の評価を行
う．したがって，この例では， initial_env を n=5 で拡張した環境で if n = 0 then 1 else
n * (fact (n + (-1))) の部分を評価することになる．数ステップ後，インタプリタは fact
(n + (-1)) をこの環境で評価することになるのだが，環境内には fact に対する束縛が含ま
れていないので，エラーとなる．
https://kuis-isle3sw.github.io/IoPLMaterials/
https://github.com/kuis-isle3sw/IoPLMaterials/blob/master/textbook/chap03-6.md
https://github.com/kuis-isle3sw/IoPLMaterials/issues
https://kuis-isle3sw.github.io/IoPLMaterials/textbook/chap03-5.html#closure
2021/6/24 IoPLMaterials | Materials for the class “Implementation of Programming Languages” in Kyoto University.
https://kuis-isle3sw.github.io/IoPLMaterials/textbook/chap03-6.html 2/3
何が問題だったのだろうか？ let rec fact = fun n -> if n = 0 then 1 else n * (fact (n +
(-1))) で再帰関数を定義する際に， fact に対する束縛が関数閉包内に保存される環境に入って
いなかったことである．再帰関数におい ては， 今これから作ろうとしている関数である fact
を関数本体 if n = 0 then 1 else n * (fact (n + (-1))) 内で使う可能性がある ので， fact に
対する束縛も閉包内の環境に含まれていてほしい．このような circular な構造をいかにして実現
するかが今回の再帰関数を扱うための拡張のキモである．
これを実現するための方法はいくつかあるが，今回はいわゆる バックパッチ (backpatching) と
呼ばれる手法を用いる．バックパッチは，最初，ダミーの環境を用意して，ともかく関数閉包
を作成し，環境を拡張してしまう．そののちダミーの環境を，たった今作った関数閉包で拡張
した環境に 更新 する，という手法である．
以下では OCaml における破壊的代入をサポートする「参照」の機能がわかっていないときつ
い．もし， let x = ref 3 in x := 4; !x というプログラムが何をするかわからない場合は，
「プログラミング言語」のOCaml爆速入門（特に「ref 型」の節）を復習しよう．
以下にバックパッチを用いて再帰関数定義をサポートするために MiniML3 に加えるべき変更を
示す．
syntax.ml
BNF の拡張に従って exp 型と program 型に新しいコンストラクタを追加する．
type exp =
…
| LetRecExp of id * id * exp * exp
type program =
…
| RecDecl of id * id * exp
eval.ml
type exval =
…
(* Changed! 関数閉包内の環境を参照型で保持するように変更 *)
| 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
(* 関数閉包を作り，idをこの関数閉包に写像するように現在の環境envを拡張 *)
let newenv = Environment.extend id (ProcV (para, exp1, dummyenv)) env in
(* ダミーの環境への参照に，拡張された環境を破壊的代入してバックパッチ *)
https://www.fos.kuis.kyoto-u.ac.jp/~igarashi/class/pl/03-ocaml.html
2021/6/24 IoPLMaterials | Materials for the class “Implementation of Programming Languages” in Kyoto University.
https://kuis-isle3sw.github.io/IoPLMaterials/textbook/chap03-6.html 3/3
dummyenv := newenv;
eval_exp newenv exp2
再帰関数を定義する際に，一旦ダミーの環境を作成し，関数閉包を作成した後に，その環境を
更新する必要があるが，これを OCaml の参照を用いて実現している． eval.ml の exval 型の定
義において， ProcV が保持するデータが環境 dnval Environment.t ではなく，環境への参照
dnval Environment.t ref になっていることに注意されたい．（したがって，ここに明示されて
いない関数適用のケースにおいては，格納されている環境を使用するために，参照から環境を
取り出す操作が必要になる．） eval_exp の LetRecExp を処理する部分は，まずダミーの型環
境への参照 dummyenv を作った上で，この dummyenv を含む関数閉包を作成し，現在の環境 env
を id からこの関数閉包への写像で拡張した環境 newenv を作り，参照 dummyenv の指す先を
newenv に変更している．
Exercise 3.5.1 [必修]
図に示した syntax.ml にしたがって， parser.mly と lexer.mll を完成させ，MiniML4 インタ
プリタを作成し，テストせよ．( let rec 式だけでなく let rec 宣言も実装すること．)
Exercise 3.5.2 [**]
and を使って変数を同時にふたつ以上宣言できるように let rec 式・宣言を拡張し，相互再帰
的関数をテストせよ．