第十回
「Prompt の導入」

前々回に作った Felleisen の control オペレータは、
現在の継続をすべて残らず取って来てしまいます。
control を使って exit を定義する場合や、簡単な例外処理をしたい場合、これは便利です。

ですが、今のままの control だと次第に不便になってきます。
例えば以下のような場合です。

let rec append lst = match lst with
    [] -> exit 0
  | a :: rest -> a :: append rest
in append [1; 2; 3]

これを実行した時の exit 0 の部分での継続は
  1 :: 2 :: 3 :: []
です。
これは、fun x -> 1 :: 2 :: 3 :: x という関数、
つまり [1; 2; 3] を x にくっつける関数になっています。
従って、 exit 0 を control (fun k -> k) に書き換えると、

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

control (fun k -> k) のところで、 k が fun x -> 1 :: 2 :: 3 :: x という
関数になります。
fun k -> でこの継続を受け取って来たら、それをそのまま返しているからです。
結果として append[1; 2; 3] とすると、「受け取ったリストに [1; 2; 3] をくっつける関数」が
返ってきます。(なので append という名前にしています)

ところが、この返ってくる関数を次のように使いたいとしましょう。

let rec append lst = match lst with
    [] -> control (fun k -> k)
  | a :: rest -> a :: append rest
in let append123 = append [1; 2; 3]
in append123 [4; 5; 6]

append [1; 2; 3] とすることで、[1; 2; 3]をくっつける関数 append123 を作り、
それを引数 [4; 5; 6] で呼び出すので、結果として [1; 2; 3; 4; 5; 6] が返ってくることを
期待しています。
ところが、実際にはそうはなりません。
何故かというと、control (fun k -> k) のところで取って来られる継続が、このプログラムだと
fun x -> 1 :: 2 :: 3 :: x にはならず、

let append123 = 1 :: 2 :: 3 :: []
in append123 [4; 5; 6]

になるのからです。つまり、取って来られる継続は、1 :: ... のところまでではなく、
その後の let append123 = ... in append123 [4; 5; 6] も含まれてしまうのです。

そこで、control で取ってくる継続を継続全てではなく、
決められた範囲の継続のみに限定するようにしましょう。
それには prompt という命令を追加します。prompt は

prompt 式

という形で使い、「式」の中に現れる control で取ってくる継続をここまでに限定します。
例えば

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

では k には 2 + [] のみが入ります。
1 + は prompt の外なので control では取って来られず、
prompt の中は 2 + 4 が実行されて 6 が返って来ます。
これは prompt 項全体の値となり、最終結果としてはそれに 6 が加わって 7 が返って来ます。

prompt というのは、インタプリタで入力を促すマークのことです。
OCaml なら OCamlインタプリタを立ち上げたときに出てくる # マークです。
上のように、prompt はその中を独立したプログラムとして扱うようにする命令です。
インタプリタのプロンプトも、毎回、入れるプログラムを独立して扱うようにしているので、
それを似ているから prompt という名前がついています。

このように継続の中でも範囲が限られている継続のことを限定継続 (delimited continuation)と
呼びます。(部分継続という言葉を使う事もある。)

さて、prompt を使って先の append の例を書き換えてみましょう。

let rec append lst = match lst with
    [] -> control (fun k -> k)
  | a :: rest -> a :: append rest
in let append123 = prompt (append [1; 2; 3])
in append123 [4; 5; 6]

append [1; 2; 3] のところを prompt でくくってやると、
control で取ってくる継続がここまでの継続に限定されます。
その結果、得られた継続を append123 に入れています。
このようにすると、ちゃんと [1; 2; 3; 4; 5; 6] が返ってきます。

=====================================================================
問題(質問、相談可)

prompt を実装せよ。いろいろな例で動いていることを確認せよ。
=====================================================================