Schemeと継続
目次
継続とcall/cc
継続とは
Schemeでは継続を手続きとして取り出して利用することができる。継続とはプログラムの (基本的にはトップレベルに戻るまでの) 残りの処理のことで、例えば、以下の [] の部分には、(square 2) をかけて1を足すという処理が残されている。
(+ 1 (* [] (square 2)))
call/ccは継続を取り出してくれる
call/cc (call-with-current-continuation) を使うと、この残りの処理を手続きとして取り出し、この手続きを引数として関数を呼び出してくれる。
> (+ 1 (* (call/cc (lambda (cc) (cc 3))) (square 2))) => 13
現在の継続が取り出され、これを引数として (lambda (cc) ...) が呼び出されている。ここではこのccが継続で、それは普通の手続きである。ccが呼ばれると、(call/cc ...) が呼ばれた時点のその全体がccの引数で置き換えられる。先ほどの [] の部分がccの引数で埋められるとも言える。
(lambda (cc) ...) も普通の関数で、普通に呼び出されているので、もしccが呼ばれないなら最後に評価された式の値が返される。
> (+ 1 (* (call/cc (lambda (cc) 0)) (square 2))) => 1
継続はファーストクラスのオブジェクト
継続はファーストクラスのオブジェクトなので、変数に束縛したり、関数の引数や返り値として渡すこともできる。
> (define cont #f) > (+ 1 (* (call/cc (lambda (cc) (set! cont cc) 0)) (square 2))) => 1 > (cont 3) => 13
時をさかのぼる
さて、継続が面白いのは、(その定義通り) 継続が取り出された時点のプログラムの残りの処理が保存されていることである。
(define cont #f) (define (wayback n) (let ((x (call/cc (lambda (cc) (set! cont cc) n)))) (begin (display `("wayback" ,x)) (newline) (if (> x 0) (cont (- x 1)) x))))
xへの変数束縛以降の継続がcontに保存されており、1度waybackを抜けた後も、contを使って何度でも呼び直すことができる。
> (wayback 2) (wayback 2) (wayback 1) (wayback 0) => 0 > (cont 3) (wayback 3) (wayback 2) (wayback 1) (wayback 0) => 0
まるで時間をさかのぼって、別の未来への処理をやり直しているように見える。継続の保存期間には制限がないので、束縛されている限りは何度でも呼び出せる。
どこでも取り出せる継続
あまり迷う人もいないかもしれないが、クロージャは定義された位置での環境を参照するのに対して、call/ccは呼ばれた時点での継続を取り出す。そこで、こんな手続きを使うこともできる。
(define cont #f) (define (capture x) (call/cc (lambda (cc) (set! cont cc) x))) (define (func n) (cond ((= n 0) (capture 1)) (else (* n (func (- n 1))))))
captureは呼ばれた時点での継続をcontに束縛し、xを返す。そのため、コード中の好きな式aを (capture a) に置き換えれば、結果を変えずにその位置での継続をcontに束縛できる。
> (func 4) => 24 > (cont 5) => 120
Schemeではcall/ccを使えば、どこでもその時点の継続を取り出すことができ、それを変数に束縛したり、関数に渡したり返したりして、遠く離れた場所からも利用できる。これはなんだか大変な力に思える。
継続の利用
それでは、具体的には継続は何に使えるのだろうか？ここでは簡単なサンプルコードを示して継続の使い方を紹介してみたいと思う。
大域脱出
継続のわかりやすい使用例は大域脱出だ。継続がなくても同様の処理は書くことができるが、深い位置からの脱出ではコードがより簡潔になることもあるかもしれない。
(define (escape x lst) (call/cc (lambda (return) (map (lambda (l) (if (= l 0) (return '()) (/ x l))) lst))))
returnにescape関数の最も外側の継続が保存されているので、returnが呼ばれた時点で (残りの処理を飛ばして) その引数が直ちにescape関数の返り値となる。それゆえに、returnはCのような言語のreturn文のように使うことができる。
> (escape 2 '(1 2 3)) => (2 1 2/3) > (escape 2 '(0 1 2)) => ()
処理の一時中断と再開
継続の力がより発揮される例の1つは、好きな位置で一時中断して、後で停止した位置から再開するような処理ではないだろうか。まずは以下のようなコードを考えてみる。
(define resume #f) (define (resumable n) (call/cc (lambda (return) (display `("resumable" ,n)) (newline) (call/cc (lambda (cc) (set! resume (lambda () (cc #t))) (return n))) (resumable (+ n 1)))))
resumable関数は内側のcall/ccが呼ばれた時点の継続をresumeの中に保存し、returnでnを返している。なので、resumeを呼び出せば、内側の (call/cc ...) が#tで置き換えられ、(resumable (+ n 1)) が呼ばれる。
> (resumable 0) (resumable 0) => 0 > (resume) (resumable 1) => 1 > (resume) (resumable 2) => 2 ...
ただ、このresumableはnを返して止まってしまうので、返り値を使うことはできず、例えば以下のようにリストを作ることはできない。
> (import (srfi 1)) > (fold (lambda (i l) (cons (resume) l)) '() (iota 10)) (resumable 3) => 3
それというのも、(resume) は前回の resumable 途中の継続に飛んで行ってしまって、呼び出し元の継続には帰って来ないからである。返り値を使いたい場合は、(resume) の中で取り出された継続に帰って来てくれないといけない。そこで、以下のように改良してみる。
(define yield #f) (define (generator proc) (define current proc) (define (next) (call/cc (lambda (return) (set! yield (lambda (x) (call/cc (lambda (cc) (set! current cc) (return x))))) (current)))) next) (define (endless) (let loop ((i 0)) (begin (display `("endless" ,i)) (newline) (yield i) (loop (+ i 1)))))
generator内のnext関数は、yieldの呼び出し時の継続をcurrentに保存し、yieldの引数xをreturnに返すような関数をyieldにセットし、currentを呼び出す。そのため、currentの呼び出し先でyieldが呼ばれると、currentはyieldへ戻るための継続に更新され、nextはxを返す。こうして、nextは呼ばれる度に、yieldまでの処理を実行し、xを返し、一時中断する。
> (define gen (generator endless)) > (gen) (endless 0) => 0 > (gen) (endless 1) => 1 ... > (import (srfi 1)) > (fold (lambda (i l) (cons (gen) l)) '() (iota 10)) => (11 10 9 8 7 6 5 4 3 2)
こうした技術を使うと、重い処理や無限に続く処理などを適当なところで止めておいて、必要に応じて再開することができる。また、もっと対称的に2つの処理がお互いの継続を呼び合うような方法を考えることもできる。これらは実行順や範囲を意識的に制御される平行処理のようなものを実現する。
(define (coroutine-1 cont) (let loop ((i 3)) (if (>= i 0) (begin (display `("c-1" ,i)) (newline) (set! cont (call/cc cont)) (loop (- i 1)))))) (define (coroutine-2 cont) (let loop ((i 0)) (if (< i 4) (begin (display `("c-2" ,i)) (newline) (set! cont (call/cc cont)) (loop (+ i 1))))))
それぞれの (set! cont (call/cc cont)) ではその時点での自身の継続を引数に相手の継続を呼び出し、帰ってきた相手の継続をcontに束縛している。
> (coroutine-1 coroutine-2) (c-1 3) (c-2 0) (c-1 2) (c-2 1) (c-1 1) (c-2 2) (c-1 0) (c-2 3)
まとめと参考文献
Schemeではファーストクラスの継続を簡単に取り出して利用することができる。継続を使うと、プログラムを任意の時点で中断したり、再開したりすることができる。そのため、大域脱出や例外処理、ジェネレータやコルーチン、探索時のバックトラッキングなど、複雑な制御を比較的簡単に実現することができる。
ここまで継続について学んだことをまとめてみた。あまり実用的な例を紹介することはできなかったが、もし自分のような勉強中の方の参考になったらさいわいだ。最後に、参考にしたサイトや本を紹介しておきたい。ここで紹介したコードの多くは、これらの参考文献をもとに書かれている。より進んだ内容や、より正確な内容が知りたい方は参照してほしい。
call-with-current-continuation
Scheme/継続の種類と利用例 - Wikibooks
使いたい人のための継続入門
なんでも継続
独習 Scheme 三週間 Teach Yourself Scheme in Fixnum Days (Chapter 13, 14)
もうひとつの Scheme 入門 (16, Appendix 3)
On Lisp (20-23)
R7RS 日本語訳 (報告書 P49-52)
