継続:コルーチン(1) - さかもとのブログ

SICPと平行して，プログラミングGaucheに取り組む．
今回は19.8のコルーチン．SICP前にこれに取り組んだときは手も足も出なかった...
今回は理解できた気がする．

コルーチン機構を作り出すマクロは以下のもの．

(use util.queue)

(define *task* (make-queue))

(define-syntax define-coroutine
  (syntax-rules ()
    [(_ (routine yield) body ...)
     (define (routine)                                        ;(1)
       (call/cc (lambda (return)                          ;(2)
                  (define (yield)                               ;(3)
                    (call/cc (lambda (cont)                ;(4)
                               (enqueue! *task* cont)
                               (return))))
                  body ...))
       ((dequeue! *task*)))]))

(define (coroutine-init! . rs)
  (set! *task* (make-queue))
  (for-each (lambda (r)
              (enqueue! *task* r))
            rs))

coroutine-init!はとりあえず置いておいて, define-coroutineのすごーく簡単な解説

"routine"に相当する名前の関数を定義する(1)
"routine"関数内で,"yield"に相当する名前の関数を定義する(3)
"yield"を定義し終えると,bodyの評価に入る
bodyの評価を終えると(これは実際には起こらないが),　(dequeue! *task*)を評価する

例題1

プログラム例は

(define-coroutine (three yield)
  (let lp ()
    (print 'one)
    (yield)
    (print 'two)
    (yield)
    (print 'three)
    (yield)
    (lp)))
(three)

であって, 実行すると,

one
two
three
・
・

となり無限ループになる．
なぜこうなるのかを説明する．
プログラム例の(let lp () ...)がdefine-coroutineのbody...になる．
重要なのは, (let lp ()...)が(yield)を呼び出すこと．このyieldは,当然(3)の関数を指している．
これを実行するとどうなるかというと,　

(yield)を呼び出したところを"cont"とする
"cont"を*task*に入れ，(return)を呼び出す
"return"が呼び出されると, "return"の継続地点に戻る
(dequeue!...)によって，*task*に入っているもの取り出し，評価する
- ここでは，1の"cont"が評価される
評価された結果，"cont"は継続なので，継続地点の先が評価される
再び(yield)が呼び出され，1〜4が行われる

今回のサンプルプログラムでは，(yield)を実行することで，自分への継続地点(cont)を*task*に入れるんだけど，(return)によって，dequeueされ，すぐに継続地点に戻ってしまう．
簡単に言えば，yieldでenqueueして，(return)でdequeueをする．

例題2

つぎのプログラム例は

(define-coroutine (Go next)
  (let loop ()
    (print 'ichi1)
    (next)
    (print 'ni2)
    (next)
    (print 'san3)
    (next)
    (print 'yon4)
    (next)
    (print 'Go!5)
    (next)
    (loop)))
(coroutine-init! Go)

ここで初めて，coroutine-init!が使われる．
coroutine-init!は何をする関数かというと，引数で渡された関数を*task*にあらかじめ関数を入れておくものである．
あらかじめ関数を入れておいて(three)を実行するとどうなるか...以下がこのプログラムの実行

gosh>(three)
gosh> one
ichi1
two
ni2
three
san3
one
yon4
two
Go!5
three
ichi1
 :
 :

無限ループとなる．さきほどはone，two，threeだけだったが，coroutine-init!をしたおかげで，結果はこうなる．
なぜこうなるかの説明をする．基本的には例題1と変わらないが，今回はすでに*task*にある関数が入っていることと*task*がキュー(先入れ先だし)であることが重要

"three"において，(yield)を呼び出したところを"cont"とする
"cont"を*task*に入れ，(return)を呼び出す
"return"が呼び出されると, "return"の継続地点に戻る
(dequeue!...)によって，*task*に入っているもの取り出し，評価する
- 1回目は，*task*に入っているGoが評価される
"Go"の評価に入る
(next)を呼び出したところを"cont"とする
"cont"を*task*に入れ，(return)を呼び出す
"return"が呼び出されると, "return"の継続地点に戻る
(dequeue!...)によって，*task*に入っているもの取り出し，評価する
- ここでは，*task*の先頭に入っている, "three"での(yield)による継続が評価される
再び(yield)が呼び出され，"cont"が*task*に追加され，*task*の先頭に入っている"cont"が呼び出される
- ここでは，*task*の先頭に入っている, "Go"での(next)による継続が評価される

こんな感じ．わかりにくい説明になってしまった....
つまり，(yield) -> "Go"の評価 -> (next) -> {*task*の先頭にある"three"の継続 -> (yield) -> *task*の先頭にある"Go"の継続 -> (next) -> …}
{}の中が無限ループになる．(もちろんletのなかで(lp)を呼び出しているからだけど)

継続ってすごいなぁ...