第八回
「FelleisenのCオペレータ」

前々回はインタプリタをCPS変換し、継続を捨てる命令 exit を実装してもらいましたが、
今回は継続に関して、捨てるだけではなく「使う」こともできるように命令を加えましょう。

というわけで、Felleisen の C オペレータというものを追加します。
プログラムの中では control (fun k -> ...) という書き方をします。
これで、この命令が実行されるときの継続を切り取って来て、それを k に渡し、
その上で ... を実行します。

例を挙げて見ていきましょう。最初の例は exit 文です。

3 + control (fun k -> 5)

とします。control (fun k -> 5)を実行するときの継続は 3 + [] です。
この継続は、答えをもらったら 3 を加えるもの、つまり fun x -> 3 + x だと見なせます。
この継続(関数)が k に渡され、そのもとで 5 が実行されるわけです。
Felleisen の C オペレータでは、control(fun k -> ... ) の ... を実行するときの
継続は初期継続、つまり空の継続 (fun x -> x) になるので、上の式は 5 となります。

つまり、control (fun k -> ...) で、... の中で k を使っていなければ
exit と同じ働きになるのです。

ちなみに、control(fun k -> ...) の ... を実行するときの継続は、
Felleisen の C オペレータでは空の継続になりますが、Lisp 系の言語である Scheme に
存在する call/cc オペレータでは、空の継続ではなくもとの継続がそのまま使われます。
なので、その場合は上の実行は 3 + 5 になり、結果として 8 が返ります。これは、C の変種です。

次の例では、取って来た継続 k を実際に使ってみましょう。

3 + control (fun k -> 4 + k 5)

ここで、k 5 のように継続を呼び出しています。このように継続を呼び出すと、
「そのときの継続は捨てて、現在の継続が k になり、」そこに 5 が渡されます。
つまり、上の式は 3 + 5 となり、結果として 8 が返ります。
4 + [] という継続が捨てられている事に気をつけてください。
このように、継続を上手く使うとジャンプを実現できます。
上の例では 5 の実行のところから 3 + [] まで(4 + [] という途中の計算を飛ばして)
ジャンプしています。

同様に、リストの要素を掛ける関数において、0 が見つかったら(全体を掛けた結果は
必ず 0 なので)即刻 0 を返すようなプログラムも書く事が出来ます。

control (fun k ->
            let rec times lst = match lst with
              [] -> 1
            | 0 :: rest -> k 0
            | a :: rest -> a * times rest
            in times [1; 2; 0; 3; 4])

実際、これを実行してみると

    times [1; 2; 0; 3; 4]
-> 1 * times [2; 0; 3; 4]
-> 1 * 2 * times [0; 3; 4]

のように計算が進みますが、この時点で 0 が見つかり、その後のリストを再帰することなく
継続 k に 0 が渡されて、全体の結果が 0 になります。

===============================================================
問題(質問、相談可)
control を実装せよ。いろいろな例で動いていることを確認せよ。
===============================================================

control を実装するには、継続を値(ここでは value_t 型)として扱う必要がでてきます。
(上の例の)変数 k の値が継続、というかたちになるからです。
なので、まず最初に value_t 型を拡張し、継続を値として扱えるようにします。
これまで値は VNumber、VBool、VFun、VRecFun でしたが、これに VCont として継続を加えます。
VCont にはインタプリタ中に出てくる cont そのものを格納したいので、
VCont の型は cont そのものの型になります。

次に、control の処理です。control は関数を受け取ったら、それに現在の継続を渡します。
つまり、control 自身は「関数を受け取り、それに現在の継続を渡す」という関数と見なせます。
なので、control が来たら、(fun f -> f <現在の継続>) に相当する関数、具体的には

VFun("f", App(Variable "f", Variable "k"), env')

のようなもの(あくまでイメージです)を返せばOKです。
ここで、env' は現在の継続に「"k"がVCont(cont)である」という情報を加えた環境です。
(cont は現在の環境。)こうしておけば、この返された VFun は (fun f -> <現在の継続>)と
同じ働きをします。

最後に、App のところで apply されるものが継続 VCont(cont') だった場合を書きます。