コルーチンと継続の簡単なまとめ

はじめに

非同期プログラミングを勉強していると、コルーチンや継続といった概念に遭遇します。なので、頭を整理するために、継続とコルーチンの簡単なまとめを書いてみました。ちなみに継続はコルーチンの上位互換で、継続を使ってコルーチンを実装できます。継続とコルーチンを詳しく知りたい方は月刊ラムダノートのVol.1,No.1¹とVol.3,No.1²を読むと良いと思います。この記事は、嘘が多分に混じっていると思います。。

継続

継続とは？

ある計算の残りの計算のことです。どこの地点からの残り？という話ですが、Schemeではcall/cc関数からリターンした後、Rubyならcallcc関数からリターンした後からです。どこまでかというと、インタプリタが終了するまで、またはプログラムが終了するまでです。継続はcall/cc(callcc)の引数として渡されます。継続を実行するためには、継続を評価します。また継続は変数に保存しておいて、callccの外で評価することもできます。さまざまなコード例を知りたい場合は参考文献²を読むと良いでしょう。おもしろい例がたくさん載っています。

継続のイメージをRubyの擬似コード？で示します。

継続は、必ずしもコードのcallccが書かれている箇所より下のコード片ではないことに注意してください。継続はcallccからリターンした地点からインタプリタ終了までの計算です。例えば、関数の中にcallcc関数が入っている場合、継続は視覚的にcallccが書いてある箇所より下のコード片ではありません。継続はそのcallccが入っている関数内でcallccがリターンする箇所から、関数の残りを実行し、その関数の呼び出し元に返ってきて、インタプリタが終了するまでの計算です。上の例は、たまたまコードの実行順序とコードの視覚的な位置が一致しているので、オレンジで囲っている箇所が継続になります。

コード例

イメージを持ってもらうために、いくつかコード例とその出力を示します。require "continuation"が文頭に必要ですが、省略します。

callcc内部で継続を評価する。

puts "1"
callcc do |ctn|
    ctn.call
    puts "2"
end
puts "3"

出力

1
3

継続は「puts "3"を実行」して、「インタプリタを終了する」です。継続が評価されると、callccから直ちにリターンするので、puts "2"は実行されません。

callcc外部で継続を評価する。１

puts "1"
callcc do |ctn|
    $ctn = ctn
    puts "2"
end
puts "3" 
$ctn.call

出力

1
2
3
3
3
…無限ループ

この場合、継続は「puts "3"を実行」して、「$ctl.callを実行」するです。継続の実行の最後に$ctl.callが再び呼び出されるので、無限ループします。

callcc外部で継続を評価する。２

puts "1"
callcc do |ctn|
    $ctn = ctn
    puts "2"
end
$ctn.call
puts "3" 

出力

1
2
…終わらない

継続は「$ctl.callを実行」して、「puts "3"を実行する」です。$ctn.call呼出→$ctn.call呼出→$ctn.call呼出と無限ループします。

大域脱出

$baz = -> do
    puts "baz start"
    $ctn.call # 脱出や！
    puts "baz end"
end

$bar = -> do
    puts "bar start"
    $baz.call
    puts "bar end"
end

$foo = -> do
    puts "foo start"
    callcc do |ctn|
        $ctn = ctn # 継続を変数に保存
        $bar.call
    end
    puts "bar end"
end

$foo.call

出力

foo start
bar start
baz start
bar end

bar endとbaz endが実行されないことがわかります。継続を評価すると直ちにcallccがリターンするからです。

ジェネレータっぽいもの

$bar = -> do
    5.times do
        n = callcc do |ctn|
            $bar = ctn
            $foo.call
        end
        puts n
    end
end

$foo = -> do
    i = 0
    while  true
        callcc do |ctn|
            $foo = ctn
            $bar.call(i)
        end
        i+=1
    end
end

$bar.call

出力

0
1
2
3
4

継続を使って、ジェネレータっぽいものを書いてみましたが、多分違います。。

継続の機能の制限

継続を実行できる場所

継続は変数に保存しておけば、どこでもその継続は実行できるのですが、callcc関数の外からは呼べないという制限をもった継続もあります。

継続を実行できる回数

また、継続を実行(callの呼び出し)ができる関数が一回に制限されている継続もあります。

継続の分類

機能による分類

完全継続

どこからでも、何回でも呼び出せる継続です。最強なやつです。

マルチショット継続(再呼出可能継続)

何回でも呼び出せる継続のことです。

ワンショット継続

一回しか呼び出せない継続です。

エスケープ継続

callcc関数内でしか呼び出せない継続です。callcc内で継続を実行すると、callccがリターンされた地点、つまり、callcc関数外に出てしまうので、必然的に一回しか呼べません。callcc関数のなかに、深くネストした関数呼出があった場合、その最下層で継続を評価するとcallccの外に移動するので、大域脱出に使うことができます。

適用範囲による分類

ここまで、残りの計算とは、callccがリターンした後から、インタプリタが終了するまでといっていましたが、もっと小さい範囲に制限した継続もあります。

限定継続

インタプリタが終了するまでやプログラムが終了するまでより、小さな範囲に制限した継続です。例えば、スレッドや関数など。

非限定継続？

限定されてない継続です。こんな用語は多分ないです。。というか普通の継続のことです。

コルーチン

コルーチンとは？

正直良くわからないですが、制御を他の誰かに移譲できる関数のことと考えます。

コルーチンの分類

対称コルーチン

対称コルーチンとは制御を対等に移譲し合える、コルーチンです。transferで制御を移譲します。対等な関係なので、transferした後に制御が戻ってくるかどうかは、他のコルーチンの動作次第です。

非対称コルーチン

親子関係にあるコルーチンです。親側に絶対に制御が戻ってきます。親側がresumeを呼ぶことで、コルーチンが再開し、子側でyieldを呼ぶと、親側に制御が戻ります。

yieldを呼べる場所による分類

コルーチンが中断している間にスタックを必要とするかどうかで、スタックレスコルーチンとスタックフルコルーチンという分類ができます。

スタックレスコルーチン

コルーチンのボディでのみ中断できるコルーチンのこと。つまり、コルーチン内で呼ばれている関数内でコルーチンを中断するといった芸当はできません。中断時にコルーチン内の関数呼び出しのコールスタックを保持する必要がないという意味でスタックレスということなんでしょうか。。ここははっきり分かっていません。。

スタックフルコルーチン

いつでも中断できるコルーチンのこと。

参考文献

1. 月刊ラムダノート Vol.1, No.1, ラムダノート, 2019
2. 月刊ラムダノート Vol.3, No.1, ラムダノート, 2021
3. お気楽Schemeプログラミング, http://www.nct9.ne.jp/m_hiroi/func/abcscm20.html
4. 20分くらいでわかった気分になれるC++20コルーチン, https://www.slideshare.net/yohhoy/20c20
5. Stackless vs. Stackful Coroutines, https://blog.varunramesh.net/posts/stackless-vs-stackful-coroutines/
6. Continuation, https://en.wikipedia.org/wiki/Continuation

1. 月刊ラムダノート Vol.1, No.1, ラムダノート, 2019 ↩

2. 月刊ラムダノート Vol.3, No.1, ラムダノート, 2021 ↩ ↩²