もうひとつのScheme入門 16. 継続を写経した。
「継続」は、計算において必ず存在する。 しかし、明示的に扱われることが少ない。
例えば、
(* 3 (+ 1 2))
のような計算があるとき、(+ 1 2)
を評価した後の残りの計算は、(* 3 _)
である。
この部分を継続と呼ぶ。
継続渡しスタイル
継続は、第一級関数をもつ言語であれば、CPS(継続渡しスタイル)によってあつかうことができる。
これは、関数が値を返す部分に、計算結果をどんな関数に渡すのかを引数で指定する方法。
(define (id x) x) (define (k+ a b k) (k (+ a b))) (define (k* a b k) (k (* a b)))
この関数群を使って、先ほど示したコードを書くとこうなる。
(k+ 1 2 (lambda (x) (k* 3 x id)))
関数適用の順番が入れ替わっている。
再帰関数のCPS化
(define (fact n) (if (= n 1) 1 (* n (fact (- n 1))))) (define (kfact n k) (if (= n 1) (k 1) (kfact (- n 1) (lambda (x) (k (* n x))))))
一つ目が通常の階乗。二つ目がCPS階乗。 CPS版は末尾再帰になっている。 このように、再帰関数をCPS化することで、末尾再帰に変換できる。 Schemeは末尾再帰をループに最適化するので、とても嬉しい。
call/cc
call/ccを使うと、継続によるジャンプができる。
> (* 3 (call/cc (lambda (k) (+ 1 2)))) 9 ;継続が呼ばれていないので、普通の式と同じ > (* 3 (call/cc (lambda (k) (+ 1 (k 2))))) 6 ;継続kが呼ばれ、(* 3 2)を計算し、トップレベルに6が返る
(define cc) (* 3 (call/cc (lambda (k) (set! cc k) (+ 1 2)))) > (+ 100 (cc 3)) 9 > (+ 100 (cc 100)) 300
継続を呼ぶと、その後の式を無視してトップレベルに戻る。
具体的な使用方法は後でまとめる。