coroutine とは

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

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

call/cc とは

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

継続とは何か

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

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

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

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

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

call/cc

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

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

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

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

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

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

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

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

もっと continuation

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

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

つまり、次の例だと……

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

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

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

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

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

coroutine with call/cc

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

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

参考文献

• 魅力的な python
• A page about call/cc
• 継続