call/cc 入門 (Coroutine with call/cc)

call/cc を使って簡単な Coroutine を作ります。call/cc 入門だと思ってもらえれば幸いです。

coroutine とは

ここでは coroutine を「実行の途中でリターンでき、さらにそこ(実行の途中)から再開することが出来る何か」の意味で使用します。適当な疑似言語で書くと次の通り。関数の途中でのリターンを suspend(), 途中からの再開を resume() で表すことにします。

void f(co) { // co は coroutine object の意味
    int i = 0;
    while (true) {
        printf("=> %d\n", ++i);
        co.suspend();
    }
}

co = coroutine.create(f);
co.start(); // f(co) を呼び出す
=> 1
co.resume(); // suspend() の後から再開される。
=> 2
co.resume();
=> 3
...

ここでは、これを scheme の call/cc を用いて表すことを目指します。

call/cc とは

call/cc とは、call-with-current-continuation という scheme の関数で、「現在の継続(current continuation)を生成し、それを関数に渡してその関数を実行する」ものです。読者の殆どは「継続」についてよく知っているかもしれませんが、基本的な概念を以下に説明します。

継続とは何か

「継続」とは、「式の評価の途中のある時点で、現在までの値を使ってそのあとしなければならないこと」を意味します。例を挙げましょう。((lambda (x) (+ 5 (* x x))) 10) を考えます。これは、次の様に評価されます。

((lambda (x) (+ 5 (* x x))) 10)
=> (+ 5 (* 10 10))
=> (+ 5 100)        ; (a)
=> 105

さて、(a) の時点でその後に評価しなければならないことはなんでしょう。おわかりかと思いますが、得られた値 100 を使って、(+ 5 100) を実行すること i.e. 得られた値に 5 を足すことです。

ここで、得られた値を x とし、これを関数に渡すことにすれば、5 を足すことは (lambda (x) (+ 5 x))と表現できます。上の関数を全てこの形に、即ち得られた値を引数として関数を呼び出す形にすると、次のように書けます。わかりやすいように分解して書きましょう。

(define x1 ((lambda (x) (* x x)) 10)) ; 得られた値を x1 として
((lambda (x) (+ x 5)) x1)            ; それを関数に渡す

もう少し簡単な例を考えると;

(a (b (c d)))
; これを書き直すと;
(define c1 ((lambda (x) (c x)) d))
(define c2 ((lambda (x) (b x)) c1))
(define c3 ((lambda (x) (a x)) c2))
c3

さて、この式が (b (c d)) を評価した後の継続は何ですか? あとしなければならないこと「継続」は、その値 x を使って、(a x) を実行すること、すなわち、(lambda (x) (a x)) だと言えるでしょう。

call/cc

以上の概念が分かれば、scheme の call/cc を理解することもそう難しくは無いでしょう。

(call/cc func) は、現在の継続 cont を生成し、これを引数として (func cont) を実行します。例えば、次の通り。

(+ 5 (call/cc (lambda (cont) (* 10 10))))
; 分けて書くと、
(define (f cont) (* 10 10))
(+ 5 (call/cc f))

さて、ここで f に渡される継続 cont は、「あとしなければならないこと」なので、「5を足すこと」です。f ではcont を使っていないので、(call/cc f) の返り値は、f の内部をそのまま実行した値、すなわち 100 となります。

fcont を使うことを考えましょう。f の中で cont が使われると、f は実行を直ちに終了し、「cont への引数」を 「call/cc の返り値」として、実行を継続します。例えば、

(define (f cont) (* 10 10 (cont 20)))
(+ 5 (call/cc f))

とすると、(call/cc f) の返り値は、cont の引数なので 20 です。従って、(+ 5 20) の値 25 が全体の値として返ります。

以下、いくつかの call/cc の例を挙げます。

(+ 20 30 (call/cc (lambda (cont) (+ 5 10))))
; cont を使っていないので式の値が call/cc 呼び出しの値。全体は 65
(define cont #f) ; とりあえず適当に cont を宣言
(+ 5 (call/cc (lambda (c) (begin (set! cont c) 10))))
; 全体は 15
; cont に現在の「あとしなければならないこと」即ち、継続「値に5を足す」を代入している。
; このように、継続は scheme ではファーストオブジェクトである。
(cont 10) ; cont に束縛されているのは「あと5を足す」。5を足せば全体は 15
(cont 20) ; 全体は 25

継続は、大域脱出にも使えます。これが重要。

(define (f)
    (call/cc (lambda (escape)
        (begin (display 1) (newline)
               (display 2) (newline)
               (escape 10) ; call/cc の外に大域脱出!
               (display 3) (newline)))))
(f) ; 1, 2 の順に出力され、f の値として 10 が返る、3 は出力されない。

call/cc の引数が束縛されたときの挙動がわかりにくかったかも知れませんが、次のように考えると少しはわかりが良いかも知れません。

(... ... ... (call/cc cont) ... ... ...)
; このような文脈で call/cc が呼ばれたとすると
; (call/cc cont) の部分を x に変えて、全体をλ抽象とする。(評価し終わったものは値に落ちているとする)
(lambda (x) (... ... ... x ... ... ...))
; このλ抽象を、継続を束縛したものだと思うことにする。
; 次の例だと……
(define (f cont) (* 10 10 (cont 20)))
(+ 5 (call/cc f))
; (call/cc f) の部分を x にかえてλ抽象にした、
(lambda (x) (+ 5 x))
; を、call/cc から抜けて束縛した後は cont だと思う。

もっと continuation

ところで、この説明では call/cc の中の continuation の振る舞いと、一旦束縛したときの continuation の振る舞いが違うように見えてしまいます(見えるハズです。見える様に説明しました)。つまり、call/cc の中の cont は、「即 return して、引数が call/cc の値」だったのに対し、束縛したものは、「call/cc の値を x にしてλ抽象」。

これは自分の説明が下手なのでわざとわけて説明した(そして、わざとわけて説明してから次の一文を言う方がわかりやすいと考えた)だけなのですが……。実は、continuation は「continuation が呼ばれると、continuation が作られた call/cc の外に、引数を call/cc の返り値としてジャンプする」というのが正しい振る舞いです。(この振る舞いだと、分けて説明したものと大体同じ動作をします。)

つまり、次の例だと……

(+ 5 (call/cc (lambda (c) (begin (set! cont c) 10))))
;    -----------------------------------------------
;  「この全体の式で、--- の部分を cont の引数に変更した式」に、現在の文脈が変更される

この式の外でも、この式の call/cc の外にジャンプして、cont の引数を call/cc の返り値として計算します。今までの例を、この視点で振り返ってみてください。

次の例も試してください。

(define cont #f)
(and (call/cc (lambda (c) (begin (set! cont c) 10)))
   (begin (display 'a) 10))

(cont 10) とすると a は表示されますか?

(and (begin (display 'a) 10)
   (call/cc (lambda (c) (begin (set! cont c) 10))))

この場合では? さらに (begin (cont 10) (display ‘c)) とすると c は表示されますか?

(begin (display 'a)
       (call/cc (lambda (c) (set! cont c) (display 'b))))
       (display 'c))

(cont #f) とすると、a, b は表示されますか?

coroutine with call/cc

ここまで理解できれば coroutine の生成は容易かと思いますが、さて。

(define call/cc call-with-current-continuation)

; coroutine は pair であらわす。car が継続、cdr が条件
(define coroutine '(#t . #t))
; 継続の再開
(define (resume)
    (begin (set-cdr! coroutine #t)
           ((car coroutine) 'dummy)
           (newline)))

; 条件を #f にして、大域脱出
(define (suspend escape)
    (set-car! coroutine (begin (set-cdr! coroutine #f) (call/cc (lambda (x) x))))
    (if (cdr coroutine) #f (escape #f)))

(define (f dummy)
    (call/cc (lambda (escape)
        (letrec ((iter (lambda (i) (begin (display i) (suspend escape) (iter (+ i 1))))))
        (iter 0)))))

(set-car! coroutine f)

; (resume) (resume) (resume) ... resume を何度も実行してみてください

無限リストの様相も呈して来ましたね。そのあたりは別の機会があれば。

参考文献

2004-01-01