Menu


Microsoft Most Valuable Person

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

原文

この前、私は短く、人が継続を使用してtry-catchのような面白い制御フローを実装するかもしれない方法をスケッチした;我々が見たように、一旦あなたがCPSを持つならば、TryとThrowの実際の実装は取るに足らない。私は、あなたがその仕事をtry-catch-finallyを実装するよう拡張することができたと確信する。または、CPSについて学ぶとき、あなたがためすかもしれないもう一つの基本的な練習問題は、コルーチンを実装することである。

コルーチンとは何か?優れた質問だ!

Windows 3の協力的なマルチタスキングの頃まで心を回顧しよう。協力的なマルチタスキングの考えはオペレーティングシステムがプロセスが動作するのを許可するということである、そして、プロセスはいつそれ自体を中断するべきで、もう一つのプロセスが動作するのを許可するべきかについて決める。プロセスが無限ループを得るならば、それは全ての他のプロセスからプロセッサー時間を無期限に奪うことができる。彼らがOSへ制御を生ずる前に多くのサイクルを取らないように、プログラムは慎重に設計されなければならなかった。そして、それはそれから次のプロセスを動作するために選ぶ。

もちろん、近頃は、我々はプロセスとスレッド・レベルでオペレーティングシステムに組み入れられる非協力的なマルチタスキングを持っている。プロセスではなくオペレーティングシステムが、特定のプロセスの特定のスレッドがいつ休止する必要があるかについて決める。これは、プログラムが他のプログラムに親切であるために特別に記述される必要がないことを意味する;彼らは、ちょうど他のプロセスが飢えることを心配することなく、直接の方法を書かれることができる。しかし、それはスレッドがそれがこれまでにより賢明なものであることなく離れて去ったところを拾うように、オペレーティングシステムが速く特定のスレッドに関連するCPUですべての状態をつかんで、それ以後のためにそれを取っておいて、それを回復させることができなければならないことを意味する。(実際、オペレーティングシステムはスレッドの継続を基本的に保存している!)

コルーチンは、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をサポートするどんなプログラミング言語ででもコルーチンが全く簡単に実装されることができることは、明白でなければならない。あなたが次の継続の起動を統制しているどんなコードからでも少しの援助を得ることができるならば、それは特に簡単であるが、必ずしも必要ではない。制御を与える時間であるとき、あなたはちょうどorchestratorに話す。「私は、現在実行中のコルーチンである。私の現在の継続は、ここにある。キューの終わりにそれを置いてください。コルーチンの継続がキューの上にたとえ何であろうとも、動作しに行きなさい。」 誰でも協力するならば、保留中の仕事をもつ各々のコルーチンはわずかな間走って、それから、次の人にターンを与える。(そして、もちろん、コルーチンが完了するとき、それがそうするならば、それはキューに継続を単に決して与えない、そして、それは消える。) 「私が次にする必要があるすべて」が正確に継続が定義されるものであるので、我々はどのように我々が離れて去ったところを拾うべきかわかる問題をすでに解決した。

あなたがまだそれを知らないならば、あなたがちょうど今間違いなくわかったように、C#の「yield return」文はコルーチンの弱形である。あなたが「yield return」にぶつかったとき、概念的に、列挙子はその継続(つまり、それが離れて去ったところを拾う方法を知っているのに十分な情報)を保管する。それはそれからその呼び出し側へ制御を明け渡す。そして、それはいつもう一度MoveNextを呼ぶべきで、反復子ブロックが離れて去ったところを拾うべきかについて決める。反復子ブロックと呼び出し側は、協力しなければならない;反復子ブロックはタイムリーに後ろに次のアイテムを与える約束をして、呼び出し側は反復子がその次の一仕事を走らせるか、それ自体の後片付けをするのを許可するMoveNextかDisposeを呼ぶと約束する。

もちろん、私が昨年に注意したように、私がここまでそれを示したずっと、反復子ブロックは「純粋な」継続渡しスタイルで本当に実行されない。我々は、実はそれの中で全メソッドとすべての関数呼び出しをCPSに変えるというわけではなくて、「次に来るもの」のためにラムダを造らない。我々が単にIEnumeratorの実装を構築する目的でだけコルーチンのようなデータフローを実装することに限っているので、我々は我々のツールボックスからCPSの大きいハンマーを引っぱり出す必要はない。我々は、すべての局所変数値が何であったかについて経過を追うクロージャをプラスして、非常により単純なシステム(それがどこにあったかについて経過を追うステート機械)を構築する。しかし、理論的には、我々はコルーチンとして反復子ブロックを書くことができた、そして、我々は彼らを継続から造ることによってコルーチンを書くことができた。「yield return」文はかなり複雑な制御フローを与えるが、我々はどんな複雑な制御フローでも継続から造ることができる。

この時に、反復子がどのようにC#で実際に実装されるかというRaymondの記事と、オプションとして、それらのデザイン決定の結果のいくらかに関する残りの私の記事を読むことは、良い考えであるかもしれない。その主題の熟知は、現在必要である。(思い出しなさい。兆候を示すことは高級なブログの合図である。)

次の時間:継続渡しスタイルがとてもものすごいならば、それならなぜ、みんなは毎日、この技術を使用しないか?

(*) または我々がデフォルトで各々のファイバーのために予約されている100万バイトのスタック・スペースの価格を払いたくなかったために。ファイバーは、実は、人が好きでありえるほど軽量でない。


インデックスへ戻る


Last Update: 2012-09-26 09:38:41