継続渡しに対する誤解
継続渡しについてひとつ誤解していたことがあって、それが理解を妨げていた。
それが何かというと、
(define (k+ a b k) (k (+ a b))) (define (k* a b k) (k (* a b)))
Scheme 入門 16. 継続
からの引用だけど、誤解というのはこのk+やk*といった関数が+や*と同じものだと思っていたことである。
「+」は当然、2つの数字を*1足し合わせる関数である。
(+ 1 2)
たいして「k+」は、2つの数字を足し合わせて、さらにその結果を「関数k」に渡す関数だ。
(k+ 1 2 display)
これは、1足す2を計算して、その結果を関数displayに渡す、という式になる。
そもそも引数の数からして違うんだからこの2つを同一視するのはどうかしているが、そう思い込んでいたからしょうがない。
(display (* 3 (+ 1 2)))
と
(k+ 1 2 (lambda (x) (k* 3 x display)))
は全体としては等価（1と2を足して、その結果に3を掛けて、その結果を表示する）になるけど、個々のk+やk*が+や*と等価なわけではないのである。
これが階乗を計算する
(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))
と
(define (kfact n k) (if (= n 0) (k 1) (kfact (- n 1) (lambda (x) (k (* n x))))))
になっても同じで、factは階乗を計算するだけなのに対して、kfactは階乗を計算して、その先を実行する。
そんなわけで、継続渡しスタイルは個々の関数だけ見ても理解できなくて、ある程度のかたまり（特に、関数と「その先」）を見ないと分からないのかもしれない。
以下まとまらない雑文
関数の連鎖
継続渡しが少しだけ分かったきっかけは、関数の返り値を次の関数の入力にしてプログラムを作れないか、と考えたこと。F#のパイプライン演算子とか見てるとそんな風にできそうな気がする。
open System.IO
let rec allFiles dir =
Directory.GetDirectories(dir)
|> Array.map allFiles
|> Array.concat
|> Array.append (Directory.GetFiles(dir))返り値を渡していくだけで、あるフォルダ以下のすべてのファイルを取得する関数ができた！
（追記）
Array.collectを使うと短くなる。
open System.IO
let rec allFiles dir =
Directory.GetDirectories dir
|> Array.collect allFiles
|> Array.append (Directory.GetFiles dir)
継続渡しでフィボナッチ数列
Schemeといったらフィボナッチ数列ですよね！っということで、継続渡しで書いてみる。
(define (cps-fib n con) (if (< n 2) (con 1) (cps-fib (- n 1) (lambda (k1) (cps-fib (- n 2) (lambda (k2) (con (+ k1 k2))))))))
実際にどう動くのかを確かめてみる。引数は3くらいが適当かな。実行後にdisplayで表示してみる。
(cps-fib 3 display)
n=3なのでelse節が実行される。
(cps-fib (- 3 1) func1)
ただし
func1=(lambda (k1)
(cps-fib (- 3 2) (lambda (k2)
(display (+ k1 k2)))))なんだか無名関数で引数を包んで遅延評価もどきをするのに似ているような（404 Blog Not Found:λ Calculus - まずは遅延評価から）。
(- 3 1)を計算して(cps-fib 2 func1)。
n=2なのでまたelse節が実行される。
(cps-fib (- 2 1) func2)
ただし
func2=(lambda (k1)
(cps-fib (- 2 2) (lambda (k2)
(func1 (+ k1 k2)))))「後にする計算」がfunc1になった。
次、(cps-fib 1 func2)を実行する。
n=1なのでthen節が実行される。
(func2 1)
これはこうなる。
(cps-fib 0 func3) ただし func3=(lambda (k2) (func1 (+ 1 k2)))
(cps-fib 0 func3)。うん、n=0でthen節だ。
(func3 1)
これはつまり、
(func1 (+ 1 1))
になって、func1は(lambda (k1) (cps-fib 1 (lambda (k2) (display (+ k1 k2)))))だから、k1に2を代入して、
(cps-fib 1 func4) ただし func4=(lambda (k2) (display (+ 2 k2)))
ここまできたらあと一息。n=1だから、
(func4 1)
で、
((lambda (k2) (display (+ 2 k1))) 1)
で、
(display (+ 2 1))
3が表示される。
うーん、なんかだまされた気分だ。
コールバック関数も継続渡しの一種なら
実は気づかないうちに継続渡しを使っていた。
ポップアップメニューを手軽に扱う - MeryWiki
（MeryWikiのマクロライブラリに投稿しました。 - komorebikoboshiのブログ）
ESCキーを押したときの動作を引数で指定するようにしているけど、これって継続渡しじゃない？ESCキーを押した「後の動作」を渡している。（話が外れるけど、今ではさすがにスクリプト自体を落とすデフォルトの挙動はやりすぎたなーと思っています。書き直すかなあ）突っ込みどころの多い関数ですが、使われているのでしょうか。
