継続渡しスタイル(CPS)再訪、パート3: コルーチンは慎重に

2018-06-30 09:37:18

原文

前回は、try-catchのような面白い制御フローを継続を使ってどう実装するかを簡単に説明した; そこで分かったと思うけれど、TryとThrowの実際の実装はCPSさえあればなんてことはない。あれを拡張してtry-catch-finallyを実装することもすぐできると思う。それでもいいけど、CPSについて学ぶときの基本的な課題は他にもあって、それは、コルーチンを実装することだ。

コルーチンって何？ いい質問だね！

Windows 3の協調的マルチタスクの頃を思い出してほしい。協調的マルチタスクの考え方は、プロセスの開始を許可するのはOSだけれど、そのプロセスを一時停止して別のプロセスを動かすかどうかはプロセス自身が判断するというものだ。あるプロセスが無限ループするなら、プロセッサー時間を他のすべてのプロセスから無期限に奪ってしまう。プロセスが制御をOSに戻すことで、OSが次に実行するプロセスを選択できるようになるので、それまでにCPUサイクルをあまり取ってしまわないように、プログラムは注意深く設計されていなければならなかった。

もちろん今日では、プロセスとスレッドの両方のレベルでOSに組みこまれている非協調的マルチタスクがある。特定のプロセスの特定のスレッドがいつ一時停止する必要があるかは、プロセスではなくOSが決める。これは、プログラムが他のプログラムに親切であるように気を付けて書かれる必要がないという意味だ。他のプロセスのCPU時間が飢餓状態になることを心配せずに、単純な書き方でプログラムを書いていい。でも、OSにしてみれば、CPU内の状態のうち特定のスレッドに関連するものをすべて把握して後で使うために保存したり、それを復元して、スレッド自身が賢くなくてもスレッドが中断地点から再開できるようにしたり、ということがすばやくできなければならなくなる。（実際、OSは基本的にスレッドの 継続 を保存している！）

コルーチンは、OSレベルの協調的マルチタスクにとても良く似たプログラミング言語概念だ。コルーチンは、しばらくの間動作して、それから、親切にも自分自身で一時停止し、他のコルーチンが動作できるようにするメソッドのことだ。複数のコルーチンが制御を戻したときは、先頭のものが自分のちょうど中断した地点から再開する。このテクニックを活用できるシステムはいくつでも思い浮かぶ。

Stack<Pancakes> pancakes = new Stack<Pancakes>();
coroutine MakePancakes(Chef chef)
{
    while(true)
    {
        while (chef.IsAwake)
            pancakes.Push(chef.MakePancake());
        yield;
    }
}

coroutine EatPancakes(Child child)
{
    while(true)
    {
        while (child.IsHungry && pancakes.Count != 0)
            child.Eat(pancakes.Pop());
        yield;
    }
}

これは、相互再帰よりずっとよい。 MakePancakes() と EatPancakes() を相互再帰で呼び出したくないのは明らかだ。なぜなら、(1)無限再帰になるから。それに、(2)複数のシェフと複数の子供がいて、順序を変えたいかもしれないから。それよりは、こんな風に書きたいはずだ。「この作業は今のところ終わったので、他の人が働いてもいいけど、また私の番が来たらちょうどここから再開しないといけない。」これは協調的なシングルスレッドマルチタスクなので、2つのコルーチンが同時に実行されたり、あるコルーチンが処理の途中で中断されたりすることはない。2つのルーチンが同じグローバルなパンケーキスタックを共有していても、「スレッド安全性」の問題はない。

ややこしい部分はもちろん、「また私の番が来たらちょうどここから再開する」をどう実現するかだ。Windowsなら、コルーチンを実装するためにファイバーを使うことができる。ファイバーというのは要するに、別のファイバーに制御を渡すタイミングを（OSに決めさせるのではなく）自分自身が決める「軽量」スレッドのことだからだ。でも、それは忘れよう。ファイバーはない¹けれど、その代わりに継続がある、と仮定しよう。

継続についてのこれまでの知識があれば明らかだけど、CPSをサポートするプログラミング言語ならコルーチンを簡単に実装できる。次の継続の呼び出しを指揮する何かしらのコードを利用できるのならさらに簡単になるけど、厳密にはそれも必要ではない。制御を譲る時間になったら、こんな風に指揮者に伝えるだけでいい。「私は今制御を譲ろうとしているコルーチンです。私の現在の継続はこれなので、キューの最後に入れておいてください。キューの先頭にある継続を、それが何のコルーチンのものでもかまわないので、実行してください。」全員が協力すれば、保留中の仕事を抱えた複数のコルーチンが、それぞれすこしずつ動いては次の人に順番を渡す。（もちろん、コルーチンが完了したなら、キューに継続を置かずに消えるだけだ。）「次に必要となるすべてのもの」というのは、継続の定義そのものなので、どうやって中断地点から再開すればいいか見つけるという問題はもう解決済みだ。

これまで知らなかったとしても 今まさに完全に理解しただろうけど、 C#の yield return 文はコルーチンの弱い形だ。 概念的には、イテレーターは yield return にたどり着いたときに、継続、つまりどこで中断したかを知るのに十分な情報を保存する。それからイテレーターは呼び出し元に制御を戻し、呼び出し元はいつMoveNext()をまた呼び出すかを決め、イテレーターブロックの中断地点から再開する。イテレーターブロックと呼び出し元は協力しなければならない。イテレーターブロックは、次の要素をタイムリーに返すことを約束するし、呼び出し側は、イテレーターが次の作業を実行するために MoveNext() を呼び出すか、またはイテレーター自身のクリーンアップのために Dispose() を呼び出すかすることを約束する。

もちろん、昨年も指摘したけれど、実際のイテレーターブロックはこれまでに提示したような「純粋な」継続渡しスタイルで実装されているわけじゃない。メソッド全体とその中のすべての関数呼び出しを実際にCPSに変換して「次に来るもの」のラムダを構築したりはしない。あくまで IEnumeratorの実装を構築するだけのために コルーチンのようなデータフローを実装しているのだから、CPSという巨大ハンマーを道具箱から引っ張り出してくるまでもない。もっとずっとシンプルなシステムを作ればすむ。どこまで進んだかを追跡できるステートマシンと、すべてのローカル変数の値を追跡するクロージャーだけ。とはいえ理論的には、イテレーターブロックをコルーチンとして書くこともできたし、継続をもとにしてコルーチンを書くこともできた。yield return 文はかなり複雑な制御フローを持つとはいえ、どんな複雑な制御フローも継続があれば作ることができる。

さてそろそろ、イテレーターが実際にはどのようにC# で実装されているかを書いたRaymondの記事や、それから余裕があれば、そのような設計判断をした結果についての私の記事の残りも読むことをお勧めする。そういうテーマに精通していることがもうすぐ必要になると思うので。（思い出そう。予告は質の高いブログのしるしだよ。）

次回予告： 継続渡しスタイルがそんなにすごいなら、なぜ、誰でも毎日このテクニックを使ったりしていないのだろう？

インデックスへ戻る