最初からすべてを実装するのは大変なので, 3つのversionを作ります.Schemeの処理系はGaucheを想定しています.
- interp1 : 普通のSchemeで作成した（Schemeのsubsetを解釈する）メタ循環インタプリタ
- interp2 : カリー化されたSchemeのメタ循環インタプリタ
- interp3 : Abstrcting Control(論文)のSemanticsに基づいたインタプリタ
shift/resetの評価器
次の一連の式は, shift/resetを実行可能な評価関数の定義です. 論文(Abstracting Control)のセクション1, Extended Continuation-Passing Styleの後半部分に登場する評価器(evaluator)です.一番先頭の行は, 評価器(インタプリタ)の型で, 式と環境, 継続とメタ継続(限定継続)を引数にとり, 計算結果を返すものです. 上から順に変数, 組み込み関数(オペレータ)の適用, 関数適用, ラムダ抽象, if(条件分岐), call/cc, shift, resetを表します.
基本的に, ラムダ計算にcall/cc, shift/reset, ifと定数/プリミティブ関数を拡張したプログラムになります.
Eval :: Exp -> Env -> Cont -> MCont -> Ans
Eval[x]ρκγ = κ (ρ[x]) γ
Eval[π E]ρκγ = Eval[E] ρ (λνγ'. κ (π ν) γ') γ
Eval[E1 E2]ρκγ = Eval[E1] ρ (λfγ'. Eval[E2] ρ (λaγ". f a κ γ") γ') γ
Eval[λx. E]ρκγ = κ (λνκ'γ'. Eval[E] ρ[x := ν] κ' γ') γ
Eval[E1 → E2 | E3]ρκγ
= Eval[E1] ρ (λbγ'. b → Eval[E2]ρκγ' | Eval[E3]ρκγ') γ
Eval[εk. E]ρκγ = Eval[E] ρ[k := (λνκ'γ'. κ ν γ')] κ γ
Eval[ξk. E]ρκγ = Eval[E] ρ[k := (λνκ'γ'. κ ν (λw. κ' w γ'))] (λxγ". γ" x) γ
Eval[{E}]ρκγ = Eval[E] ρ (λxγ'. γ' x) (λν.κνγ)
ρ[x] は, 環境ρから変数xに相当する値を返す処理を意味しています.E1→E2|E3は, Schemeにおける (if E1 E2 E3)を表します.
ρ[x:=ν]は, 環境ρ中のxをνに置き換えることの表現です.
Eval[x]ρκγ = ...は例えば, 評価関数が式x(変数)と, 環境ρ, 継続κ, メタ継続γを引数として受け取った時, 右側の式を返すという風に読みます.
全体的に限定継続付きの継続渡しスタイルになっていて, ある評価ステップで計算しきれなかった計算(=残りの計算)は, 次以降のステップで継続として記述されます. 定数/変数項やラムダ抽象のステップでは, これ以上計算できないので, 継続にその式(定数やラムダ抽象など)を関数適用します. それ以外のステップは, 基本的に残りの計算を継続で表現して, 式(プログラム)の解釈を進めます.
最終的な目標
次のような実装を実現することです.gosh> (interp3 '(reset (+ 1 (shift (c) (c 10))))) 11 gosh> (interp3 '(reset (+ 1 (shift (c) (c (c 10)))))) 12 gosh> (interp3 '(reset (+ 1 (shift (c) 10)))) 10一番目の実行では, 限定継続が1回実行されて11を返しますが, 二回目は, 2回実行されて12を返します. 最後の実行では, 残りの計算が切り捨てられて10を返しています.
interp1(メタ循環インタプリタの実装)
interp1では, 簡単なラムダ抽象とその関数適用, ifによる分岐, プリミティブの演算の実行が可能な処理系を作成します.文法は以下のようなものを受け付けます.
exp := const | var | (exp exp ...) | (lambda (var ...) exp) | (if exp exp exp)
interp1の実装は次のようになります.
環境(変数を表すシンボルとその値のペアからなるリスト)から変数名を探し, それに該当する値を返すのがlookup関数, extend*は, 環境を拡張する関数でインタプリタでは共に定番の補助関数となっています. initial-envは, プリミティブの演算(関数)が含まれている環境. eval1がインタプリタ. interp1は例外の機構を付け加えたインタプリタです(interp2以降では, もう少し複雑な使われ方をします).
サンプルプログラムとして, 階乗を計算するプログラムとフィボナッチ数を計算するプログラムを作成しました. ループは不動点コンビネータで記述します.
評価関数は, schemeのmatchマクロの都合上, 最初に(lambda, ifなどの)スペシャルフォームを持ってきて, 次に関数適用, 定数/変数といった順に並べる必要がありました.
ラムダ抽象を評価した結果の値は, レキシカルクロージャ(ラムダ抽象と環境のペア)です.
エラーが発生するポイントとしては, 探している変数が見つからないlookup関数(8行目), 間違った関数適用の形式(46行目), 想定されていないプログラムのフォーマット(54行目)などがあります. このようなケースでは, continuationを使って, 脱出します.
実行結果は, こんな感じです.
gosh> (interp1 factorial-p) 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 gosh> (interp1 fib-p) 144 gosh> (interp1 '((lambda (x y) (+ x (* y y))) 7 12)) 151
interp2(カリー化)
基本的に動作(計算結果, 機能など)については, interp1とほぼ同じですが, 内部的に式をカリー化したインタプリタを作成します. interp2では, プログラムとなる式を受け取ると, 内部的にカリー化して, カリー化された式を受け付けるインタプリタによりプログラムを計算します.
また, これに伴い, プリミティブの関数もカリー化します.
カリー化が必要なのは, 冒頭の説明にあるshift/resetの評価器がカリー化されたλ式をターゲットプログラムとしているからです.
カリー化が必要なのは, 冒頭の説明にあるshift/resetの評価器がカリー化されたλ式をターゲットプログラムとしているからです.
interp2の動作とinterp1の動作の違いは, 例えば, 次のプログラムを解釈できるか否かだと言えます.
gosh> (interp2 '((lambda (x) (x 2)) (+ 4))) 6 gosh> (interp1 '((lambda (x) (x 2)) (+ 4))) 4"# error :: malformed lambda"
interp1では, +関数のカリー化に失敗しています(ラムダ抽象で包み込む必要があります)が, interp2では, その必要がありません (Haskell likeなスタイルになっているようにも見えます).
実行結果は,前述のケース以外では, interp1と同じです.
プリミティブ関数をカリー化するcurryマクロとそれに関連するcurry*, curry-primitives-2などのマクロが登場しています. これは, プリミティブの関数fを, (lambda (x) (lambda (y) (f x y)))と書き直すことで, カリー化するマクロです. カリー化されたことで, eval2インタプリタでは, 関数適用が必ず関数と引数のペアになりました(今までは, 関数と引数の割合は一対多でした).
curry-s-expは, 普通のS式を引数にとって, カリー化されたS式を返します.
interp3(素朴なshift/resetの実装)
interp2まで完成すると, いよいよ, shift/resetが実装できるようになります. shift/resetの評価器は, 継続渡しスタイルで記述されます.
この素朴な実装のメリットは, 上記の評価器をそのまま書けば, shift/resetの実装として正しく動いてくれるところです. ただし, matchマクロにあうように, スペシャルフォームから順に実装する必要があります.
ターゲット言語の文法は, 機能を追加したので, 次のようになります.
exp := const | var | (exp exp ...) | (lambda (var ...) exp) | (if exp exp exp)
| (call/cc (var) exp) | (shift (var) exp) | (reset exp)
interp3の実装はこのようになります.この素朴な実装のメリットは, 上記の評価器をそのまま書けば, shift/resetの実装として正しく動いてくれるところです. ただし, matchマクロにあうように, スペシャルフォームから順に実装する必要があります.
ターゲット言語の文法は, 機能を追加したので, 次のようになります.
exp := const | var | (exp exp ...) | (lambda (var ...) exp) | (if exp exp exp)
| (call/cc (var) exp) | (shift (var) exp) | (reset exp)
normal2->cps2は, 2引数をとるプリミティブの関数を限定継続付きの継続渡しスタイルへ変換するマクロです. add-transform-cps-2で, その処理をすべてのプリミティブ関数に実行します.
eval3では, インタプリタ上の例外処理をきれいに扱うため, factory関数を作り, eval3をその関数が生成するクロージャとすることで, 評価器の定義をそのまま記述できるようにしました. 基本的に書き方は, 冒頭で書いた定義と(順番が違う以外は, )ほぼ同じです.
カリー化するプログラム(curry-s-exp)も, 文法の拡張部分について, 修正をほどこします.
eval3へ最初に渡す継続は, (λx m. x)で, xに式全体の計算結果が渡されるので, それを返すようにします.
サンプルプログラムとして, factorial-pでcall/ccとshift/resetを使ったものを作成しました.
interp3の実行結果は次のようになるはずです.
gosh> (interp3 normal-p) 3628801 gosh> (interp3 shift-exception-p) 101 gosh> (interp3 call/cc-exception-p) "call/cc exception"normal-pでは, 例外を返さない範囲内の引数が与えられたので, 普通にfactorialを計算します. shift-exception-pでは, factorial関数に50より上の値が渡されたので限定継続を使って, resetの外側へ脱出しています. 負の値を渡した場合は, 継続によってcall/ccの外へジャンプします.
紛らわしいのですが, call/ccは, 継続を束縛した変数cを呼び出すことで例外のように式の外側へジャンプしますが, shift/resetは, 限定継続を束縛した変数cを呼び出さないことで式(reset)の外側へ脱出します.
以上で, メタ循環インタプリタに限定継続(と継続)の機能を実装することができるようになりました.
この投稿では, 素朴な(お試しの)実装について書きましたが, 本格的な言語に実用的な実装するには, Stackなどによる実装にする必要があります(遅いです).