2006/12/24

call/ccについておまえの知っていることを晒せと脅された。

まずこんな式を考える。
(begin 
(print "hello")
(print "goodbye")
(print "hello again")
(print "goodbye again"))
この式を評価すると、beginの中の環境で(print ...)という式が上からじゅんばんに評価される。結果的にこう出力される。
=>
hello
goodbye
hello again
goodbye again
Schemeでは、式の1つめの要素をオペレータとみなし、残りをオペランドとみなす。Schemeで式を評価するっていうのは、各オペランドを評価したものを引数として、それらをオペレータに適用することを意味している。

上記の例の(begin ...)という式を評価する場合、beginプロシージャに対してオペランドである(print ...)たちを評価したものが適用される。beginは引数として与えられた式を順番に評価していくプロシージャなので、まずどんな動作をするかというと、「(print "hello")を評価した。これから残りの(print ...)たちをbeginに適用する」。

で、この動作を記録にとっておくことにしよう。具体的にはスタックにつむことにする。
(print "hello")を評価した。これから残りの引数を評価する
同様に次の動作もスタックにつむ。
top    : (print "hello")と(print "goodbye")を評価した。これから残りの引数を評価する
bottom : (print "hello")を評価した。これから残りの引数を評価する
これを繰り返すと、beginの評価が終ったときのスタックの状態はこうなる。
top    : (print "hello")と(print "goodbye")と(print "hello again")と(print "goodbye again")を評価した。最後の式の値を返すよ
(print "hello")と(print "goodbye")と(print "hello again")を評価した。これから残りの引数を評価する
(print "hello")と(print "goodbye")を評価した。これから残りの引数を評価する
bottom : (print "hello")を評価した。これから残りの引数を評価する
じつはこの活動記録が「継続」を表している。で、スタックなので通常はいちばん上しか見えないけれど(つまり最後の式の値が返るだけ)、Schemeには途中を捕まえる方法がある。それがcall/cc。
(define c '())
(begin
(print "hello")
(print "goodbye")
(call/cc
(lambda (k) (set! c k)))
(print "hello again")
(print "goodbye again"))
こうすると、call/ccを仕掛けた場所の継続、つまり、くだんのスタックの下から2番目を捕まえて、あらかじめ適当な値で定義しておいたcに代入できる。けっきょくcには、「(print "hello")と(print "goodbye")を評価した。これから残りの引数を評価する」という継続が代入される。そこでcを評価すれば、cは「これから残りの引数を評価する」つもりでまんまんなので、こうなる。
gosh> (c)
hello again
goodbye again
これを応用すれば、たとえば「(a b a c a d)というリストから、最後のaで始まる部分リスト(a d)を取ってくる」とか、「木構造を探索するのに、途中で分岐した場所から別の枝を探索し直す」とかできる。これらは「途中を忘れて覚えておいた場所からやり直す」という人生やりなおし機型の応用といえる。一方、「とにかくcall/ccを仕掛けた場所に戻れる」という性質を利用すれば、いわゆる局所脱出ができるようになる。具体的な例はディヴィグの本とか"Seasoned Schemer"とかを参照。そもそもこの記事は"Seasoned Schemer"のオレ解釈なわけで。

No comments :