2005/05/25

継続がらみは悩ましい。Kent Dibvigでは、call/ccの最初の例として、次のような局所的脱出が挙げられている。

(define product
(lambda (ls)
(call/cc
(lambda (break)
(let f ((ls ls))
(cond
((null? ls) 1)
((= (car ls) 0) (break 0))
(else (* (car ls) (f (cdr ls))))))))))

(product '(2 3 4) => 24

これはつまり、リストの途中に0が出てきたら、その時点の継続を0に設定して返すというものだ。そうすれば残りの掛け算をせずにfの再帰から抜けられる、というのがメリットらしい。ここまではわかる。
わからないのは、単にリストの途中に0が出てきたら抜けるという動作をさせたいだけなら、次のコードでも一緒じゃないのか? という点だ。

(define product
(lambda (ls)
(let ((ls ls))
(cond
((null? ls) 1)
((= (car ls) 0) 0)
(else (* (car ls) (product (cdr ls))))))))

もっとも、これだと末尾再帰じゃなくて気持悪いので、こうは改良したい。

(Define product/cps
(lambda (ls k)
(let ((ls ls) (k k))
(cond
((null? ls) k)
((= (car ls) 0) 0)
(else (product/cps (cdr ls) (* (car ls) k)))))))

(product/cps '(2 3 4) 1) => 24

この三つ目のバージョンでは継続引き渡しを使ってるつもりなんだけど、このように末尾再帰で書けることをもってして継続のメリットだと主張されるならとてもクリアだ。となると、この例における call/cc のありがた味っていったい……

さらに、もう一つ、Kent Dibvigの継続の解説でさらに分からなくなることがあって困る。本の中では、最初のリストの掛け算を継続引き渡しで書き直す例も説明されてるんだけど、それがどうにも妙ちきりんなんだよね。

(define product/cps
(lambda (ls k)
(let ((break k))
(let f ((ls ls) (k k))
(cond
((null? ls) (k 1))
((= (car ls) 0) (break 0))
(else (f (cdr ls) (lambda (x) (k (* (car ls) x))))))))))

(product/cps '(2 3 4) (lambda (x) x)) => 24

もしかしたら、こういう風に「自分自身を返す継続」を使うことが推奨されるのだろうか。それとも、単に僕の解釈が間違っていて、上記の3番目のバージョンでは継続引き渡しになっていないのだろうか。ああ、そもそも3番目のバージョンは「リストの途中に0があったらその時点で後続の掛け算をやめる」という仕様を満たしていないのかもしれないのか。Gauche に Chez Scheme のような trace があればなあ。どうやって作るんだろう。

No comments :