継続を使って末尾再帰の最適化。

call/ccを使って末尾再帰の最適化に挑んでみます。

階乗がおなじみなので、階乗にした。

まずは反復で。

traceが入ってるけど、反復バージョンの階乗。

(define (fact n)
  (define (iter m aac)
    (if (= m 0)
        aac
        (iter (- m 1) (* aac m))))
  (trace iter)
  (iter n 1))
(trace fact)
(fact 10)

SICPやり始めたときは反復で泣きそうだったけど、普通に書けるようになってるし。

trace結果

MzSchemeを使う。

|(fact 10)
|(iter 10 1)
|(iter 9 10)
|(iter 8 90)
...
|(iter 1 3628800)
|(iter 0 3628800)
|3628800
3628800

末尾再帰の最適化がされてますね。安心してSchemeが使える理由のひとつでもあります。

継続バージョン

継続を使います。

valuesを使って末尾再帰の最適化を阻止しました。基本的には何も変わってません。

(define (fact n)
  (call/cc
    (lambda (cont)
      (define (iter m aac)
        (if (= m 0)
            (cont aac)
            (values (iter (- m 1) (* aac m)))))
      (trace iter)
      (iter n 1))))
(trace fact)
(fact 10)

trace結果を見ると

おぉ。

|(fact 10)
|(iter 10 1)
| (iter 9 10)
| |(iter 8 90)
| | (iter 7 720)
| | |(iter 6 5040)
| | | (iter 5 30240)
| | | |(iter 4 151200)
| | | | (iter 3 604800)
| | | | |(iter 2 1814400)
| | | | | (iter 1 3628800)
| | | |[10](iter 0 3628800)
|3628800
3628800

末尾再帰の最適化がされてないのに、末尾再帰と同ステップで計算を終了することが出来ました。


valuesの代わりに適当に打ち込んでも、

(* 10000000 (iter (- m 1) (* aac m)))))

結果は同じ。valuesは全く評価されていない。

継続を外に出してみる。

あ、外に出せるな。と思って外に出したら、

(define (fact/cc n cont)
  (define (iter m aac)
    (if (= m 0)
        (cont aac)
        (values (iter (- m 1) (* aac m)))))
  (trace iter)
  (iter n 1))

(call/cc (lambda (cont) (fact/cc 10  cont)))

継続渡しスタイルになってしまった(汗

(valuesは評価されていないが)

追記

この時点で僕は不思議なジャンプについて解読できていなかったので追記しておく。


(* 2)を使わないでcall/ccを実行する。

(call/cc (lambda (cont)
           (* 2 (cont 10)))) ; 10

contの中には、SchemeのPRINT-AND-NEXT-REPLという継続が入っているので、

(call/cc (lambda (PRINT-AND-NEXT-REPL)
           (* 2 (PRINT-AND-NEXT-REPL 10))))

PRINTで10と表示される。そしたら、NEXTを実行して、

(* 2 (REPL 次はなんだ))

と待っている状態になる。

(* 2)よりもREPLの方が先に評価されるので、ジャンプしている「ように」見える。(* 2)は永久に評価されることが無いだけ。これがcall/ccのカラクリ。


call/ccはScheme自体の継続を取り出すことが出来るというわけだ。