2011/06/19

いかにして私は思い悩むのを止めてcall/ccを便利に使うようになったか

call/ccは神秘的です。(call/cc call/cc) とか、いまだにくらくらします。まあ、ゆっくり考えれば難しいことではないのですが、回答に至るプロセスを即答する自信はありません。しかも、そんな込み入った話なのに、(call/cc call/cc) なんていう式には実用性のかけらもない。ゼロです。採用面接の問題にはいいかも。Schemerを募集するような会社があるかどうか知りませんが。

そんなcall/ccの使い道としてよく引き合いに出されるのは大域脱出です。でも、たとえばケント・ディヴィグの教科書の例を見てピンとくる人はいるのでしょうか。引数にゼロがあったら掛け算をやめてジャンプする。ありがたみがまったく感じられない話です。かと思うと、その次の例でいきなり登場するのは「プリエンプティブ・マルチタスクを実装したエンジン」なるもの。わけがわかりません。

そこで、自分が「call/ccうれしい」と感じられそうな例を考えてみることにしました。大域脱出を強いられる状況を作るので、下準備が少し必要です。



いま、こんなプロシージャー「>i>」が欲しいとしましょう。
(>i> 1 10)
=> (1 2 3 4 5 6 7 8 9 10)
ようするに、整数を2つ与えると間を補完してくれるようなプロシージャーです。

>i> そのものを定義するのは簡単です。でも、一歩進んで、こんな具合にメタ定義できるようにすることを考えてみましょう。
(define-range-maker >i> int++)
ここで、
(define (int++ n)
(+ n 1))
です。

define-range-maker のほうはマクロとして定義できます。
(define-macro (define-range-maker sym next)
`(define (,sym from to)
(let R ((i from) (result '()))
(if (equal? i to)
(reverse (cons i result))
(R (,next i) (cons i result))))))

define-range-maker を使ったので、似たような補完プロシージャーをもりもり作れるようになりました。たとえば、 int++ の文字バージョン char++ を用意すれば、2つの文字の間を補完するプロシージャー >c> ができます。
(define (char++ c) 
(integer->char (+ (char->integer c) 1)))

(define-range-maker >c> char++)

(>c> #\a #\k)
=> (#\a #\b #\c #\d #\e #\f #\g #\h #\i #\j #\k)
pizzaもどうぞ。
(define (kakko++ x)
(cons x '()))

(define-range-maker >p> kakko++)

(>p> '(pizza) '((((pizza)))))
=> ((pizza) ((pizza)) (((pizza))) ((((pizza)))))

さて、よく考えたら >i>>c>>p> も同じ定義の繰り替えしです。やはりこんな具合にマクロ when を作ってまとめられないでしょうか?
(define-range-maker >++>
(when integer? int++
char? char++
list? kakko++))

ぱっと思いつくのは次のような定義でしょう。 define-range-maker に渡すプロシージャー int++char++ がとることになる引数の種類に応じて、当のプロシージャーを返そうという戦法です。
(define-syntax when
(syntax-rules ()
((_ pred proc)
(lambda (x)
(if (pred x)
proc
(error "unsupported arguments"))))
((_ pred1 proc1 pred2 proc2 ...)
(lambda (x)
(if (pred1 x)
proc1
(when pred2 proc2 ...))))))
しかし、これではうまくいきません。 define-range-maker には「自分への引数を調べてプロシージャーを返そうとするプロシージャー」が渡されることになるのですが、 define-range-maker はそんなものを求めていないからです。 define-range-maker が求めているのは、あくまでも、そのプロシージャーが返そうとしているプロシージャーのほうです。

こんなとき call/cc が使えます。「自分への引数を調べてプロシージャーを返そうとするプロシージャー」のことは忘れて、当のプロシージャーを返すようにしましょう。
(define-syntax when
(syntax-rules ()
((_ pred proc)
(call/cc
(lambda (k)
(lambda (x)
(if (pred x)
(k proc)
(error "unsupported arguments"))))))
((_ pred1 proc1 pred2 proc2 ...)
(call/cc
(lambda (k)
(lambda (x)
(if (pred1 x)
(k proc1)
(k (when pred2 proc2 ...)))))))))
これでうまくいきます。
(define-range-maker >++>
(when integer? int++
char? char++
list? kakko++))

(>++> '(coffee) '(((((coffee))))))
=> ((coffee) ((coffee)) (((coffee))) ((((coffee)))) (((((coffee))))))

DSLを作るようなときはマクロなどでメタな階層を積み重ねていくことが多々あると思うのですが、そんなとき、下層に潜らないと見えない条件に基づいて上層の機能をスイッチするのに call/cc はなかなか便利です。 call/cc なんて使わずに済ませることもできるのでしょうが、こんなふうに便利に使えることもあるので、ぜひみんな『Scheme修行』を読んで「なあんだ」と実感しておきましょう。



『Scheme修行』

ちなみに、この『Scheme修行』の制作にも使っているxml2tex.scm(名前とは裏腹に、変換のためのスクリプトというよりは変換を定義するためのスクリプト)でも、ここで紹介したのとまったく同じ方法でcall/ccを利用しています。というか、それを説明用の例として書き直したのがこの記事の when マクロでした。