第十一回
「control/prompt から shift/reset への拡張」

今回でインタプリタの拡張は最後になります。
今までお疲れさま！
しかも今回も書き換える量はとっても少ないです。
（なので最後にインタプリタ拡張以外の問題が足してあるよ！）

これまで実装した Felleisenの control オペレータで取ってきた継続を使うと、
その継続を使って来た継続は捨てられていました。
たとえば、
prompt (2 + control(fun k -> 3 * k 4))
となっていたとき、k は 2 + [] となりますが、k 4 で k が呼び出されると、
そのときの継続である 3 * [] が捨てられてしまいます。
control オペレータはそもそも「その後のすべての仕事をとってくる」という意味なので、
未来永劫分の継続をとってきます。
よって、k 4 としたところでその実行には未来永劫かかることになり、
その結果が 3 * [] に返って来なくても自然なわけです。
（この説明が分かりにくければ、「計算後に答えを出して終わる」ところも含めて継続でとってくると
　考えてください。k 4 で継続を呼び出すと、2 + [] を呼び出した後に答えを出して終わってしまい
　3 * [] の実行はされないわけです。実際、作ったインタプリタは初期継続（値を返して終わる）
　から始めているので、それっぽい動作になります。）

ところが、前回 prompt を導入し、継続を区切るようにしました。
この区切られた継続は未来永劫分にはならない（「値を返して終わる」は含まない）と思えば、
2 + [] の実行後、値が 3 * [] に渡されても不思議ではありません。
つまり、control で継続を取って来た時点での継続が「本当に」fun x -> 2 + x という関数に
一致すると見なすということです。
そうすると、上のプログラムの実行は以下のようになります。

    prompt(2 + control(fun k -> 3 * k 4))
-> 3 * k 4 {k : fun x -> 2 + x}
-> 3 * (fun x -> 2 + x) 4
-> 3 * 6
-> 18

k 4 の後の継続 3 * [] も実行されるようになっています。
この実行は見方を変えると、control オペレータによって
2 + [] と 3 * [] の実行順がひっくり返されたと考えることもできます。
もともと 2 + 3 * [4] という計算だったものを、k = 2 + [] として 3 * k 4 とすることで、
3 * (2 + [4]) としているわけです。

このように取って来た継続を完全に普通の関数であると捉えると、いろいろと面白いことが出来ます。
たとえば

prompt(1 + control (fun k -> 2 * k (k 3)))

のように k を複数回使うこともできます。（10 が返ってくる筈です。）
===============================================================
問題（質問、相談可）

継続を使ったときの挙動を、上で述べたように変更せよ。
===============================================================
おそらく一番素直にこれを実装すると、shift/reset に対応するものになります。
そこで、これまで prompt と書いていたところを reset に書き直し、
control を書いていたところを shift に書き直してください。
prompt と reset は意味的に全く同じです。
control と shift は微妙に違います。（詳しい話は先生に聞きましょう）


さて、上で述べた「計算順をひっくり返す」という考え方にもう少し突っ込んでみます。

let rec id lst = match lst with
    [] -> []
  | a :: rest -> a :: id rest

この関数 id は受け取ったリストを順に見て行きますが、何もせずにそのまま返しているので、
結局は恒等関数になっています。
ここで、a :: id rest という部分に着目してみましょう。
ここでは a を再帰呼び出しの結果に付け加えてから結果を返しています。
それを明示するため、以下のように書き換えてみましょう。

let rec id lst = match lst with
    [] -> []
  | a :: rest -> shift(fun k -> k (a :: id rest))

その後の仕事を k としましたが、id rest に a を付け加えた結果を k に返しているだけなので
これは最初の id と同じ動作をします。

ここで、「a を付け加える」という動作と「その後の仕事」をひっくり返してみましょう。

let rec f lst = match lst with
    [] -> []
  | a :: rest -> shift(fun k -> a :: k (f rest))
in let rec g lst = reset (f lst)
in g [1; 2; 3]

===============================================================
問題（質問、相談可）

これを実行した結果は何か。
===============================================================

実行をすべて書き下してみるとこのプログラムの挙動を理解するのに良いかもしれません。

また、上の問題と直接は関係ありませんが、shift/reset の挙動の理解を深めるために
以下の問題をやってみましょう。

===============================================================
問題（質問、相談可）

リストを受け取ったら、そのプリフィックスのリストを返す関数 prefix を書け。

例えば
prefix [1; 2; 3; 4; 5]
とすると
[[1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]; [1; 2; 3; 4; 5]]
が返る。

ヒント：a :: rest を処理する際、ここまでのプリフィクスを作る部分と、そ
れ以上、長いプリフィクスを作る部分（再帰）にわけ、a :: を両方で共有す
る。（継続をとってきて、それを２度使う。）
===============================================================