2010/03/23

よくわかるcall/cc

「打ち消し線」すごくわかりやすい!
内容に直接関係しないのですが、「スタックのコールバック」。@aharisuさんが言っていたのはたぶん「コールスタックの破棄」的なことだったかと。コールスタックごと吹き飛ばす的な。違ったかな。

継続あれこれ

眺めてたら途中で力尽きた。
「ある時点での状態」を変数に束縛して、後からそこへ戻るといったことも可能になる。Schemeの継続は関数の形をとっており、これは「その関数を呼ぶことにより、そこに渡された引数をcall/ccで囲まれている式全体の値として継続に“注入”できる」と定義されている。
プログラムの実行順序を制御する概念
既に終了したスタックフレームを黄泉の国か ら引きずり出してスタックにぶちこめるわけである。
普通の人間が「おっ、ここはCall/CCを使えば カッコ良く実装できるね!」などと思いついたりすることはまずありえない
継続を用いれば大域脱出、コルーチン、疑似マルチタスク、バックトラックといった特殊な制御を必要とするプログラムを効率的に記述することができる
「分かれば分かる」
継続は現在の計算を続行するための情報 
どんなコードでも継続渡し形式として「見る」ことができる 
現在の継続を手続き (継続手続き) にパッケージ化して、それを引数として procを呼び出します。procが戻ったら、その返り値がcall/ccの 値となります。
言語によっては、呼び出し元の関数が分からず呼び出したらもう戻ってこ ないものもあります。呼び出し元の関数に値が返ってくるのは、どこから自分を呼び出したのかという情報をどこかで管理し、呼び出された側はその 情報を元に値を返すという決まりがあるからです。 
保存した継続を動かしてみましょう。
(* 2 (fact 10))という計算は、fact/cpsを使えば次の式と等価です。(fact/cps 10 (lambda (a) (* 2 a)))
継続渡し形式で書けば、現在実装中の関数が、 どういう形で結果を返すのが良いかの設計を遅らせることが出来ます。
継続は保存してから呼び出されるまでの間、完全に休眠しており、 その間にいかなる式の評価でもはさむことが出来ます。 
(call/cc (lambda (return) ...)) は説明すると長くなるけど、まあ、 returnってラベルを定義してるもんだと思ってくれればいい。

0 件のコメント:

コメントを投稿