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"のオレ解釈なわけで。