Menu


継続渡しスタイル(CPS)再訪、パート1

原文

素晴らしい読者のみなさん、おはよう。最初に言っておきたいんだけど、この連載はすごく長くてすごく込み入った話になる。でも、きっと最後には報われるから。それと、今回はいつもよりハイペースで投稿するつもりだ。いつものペースだと週に2つだけれど、それ以上で。(私がなぜこんなことをしているか、いずれ明らかになるだろう、と彼は謎めかして言った。覚えておいて。緊張感は高級なブログのしるしなんだよ。)

今回たくさん話そうと思っているトピックは、数年前に少しだけ論じたのが最初だった。すなわち、継続渡しスタイル(Continuation Passing Style。これからはCPSと略す)だ。このトピックは分かりにくいけれど魅力的だと、多くの人々が思っている(註:私もその一人だ)。

この連載の残りを読み続ける前に、手短かに記憶をリフレッシュしたい人もいるだろう。私はJScriptを使って、CPSについての短い紹介をした。

http://blogs.msdn.com/b/ericlippert/archive/tags/continuation+passing+style/

おかえりなさい。理解してもらえたなら何より。入れ子にされた匿名関数のためのJScriptの構文は、かなり直接的だし、C#の匿名メソッドのそれと類似している。できれば、JScriptを通常読まない人にとっても明快だったといいのだけど。全部読み通しても理解できなかったなら困るので、要約させてほしい。

従来のサブルーチンによるプログラミングのスタイルが提供するプログラミングモデルは、こんな感じだ。

  • 今何をしていたか、および、局所変数がどんな値を持っていたかを、とある一時的な格納庫(別名「スタック」)に書きとめる。
  • リターンするまで、制御をサブルーチンへ移す。
  • さっきのメモを調べて、さっき中断した場所からまた始めるが、今ではサブルーチンの戻り値がわかっている。もし戻り値が存在するならばだが。

CPSは、「サブルーチン」と「復帰」自体がないプログラミングのスタイルである。 その代わりに、現在の関数が最後にすることは、次の関数を呼ぶことである。その際に、現在の関数の結果を次の関数に引数として渡す。関数は決して「リターン」しないし、次の関数を呼んだあとで動作することもないので、どこにいたかについて記録しておく必要はない。どこにいたか重要でないのは、 そこには決して戻って来ないからだ。ものごとが望ましい順序で起こることを保証するためには、新しい関数を呼ぶときに「継続」を渡すのが一般的だ。継続自体はただの関数なのだが、それによって「次に起こるすべて」を実行するのである。

私は、それをJScriptで組み立てるひとつの方法を示した。あらゆる関数が継続を受けとるようにする。新しい継続は、入れ子にされた匿名関数によって必要に応じて作ることができる。いつもならサブルーチンを呼び出していたような状況では常に、そうする代わりに、これからやるべき仕事を表現する継続を作り、ロジック上でサブルーチンに渡して、それをサブルーチンに実行してもらう。JScriptでは、スタックを消費せずにこのようなことをするためには、ある種の「オーケストレーション」コードに継続を渡す必要がある。オーケストレーションコードは、次に起こるべきことを記録している。オーケストレーターはループの中に居座って、最後に計算された結果を現在の継続に送り届けるだけである。CPSを組み込みでサポートしていない言語では、スタックを消費せずに徹底したCPSプログラミングをしたいならば、これ以上に良い方法はほぼない。

CPSが面白くて役に立つのは、多くの素晴らしい特性があるからなのだが、最初の連載記事ではそれらをあまり説明しなかった。私は単に、深い再帰に関する問題点を処理する方法としてCPSを示しただけだった。つまり、サブルーチン呼び出しから戻ることがないため、呼び出しスタックを消費する必要がない、と。しかし、CPSの真価はそれだけにとどまらない。たとえば、CPSでできることの1つに、制御フローをメソッドとして実装して、新しい制御フローのプリミティブを言語に組み入れることがある。非現実的に聞こえたかもしれないが、非常に単純な例から見てみよう。継続から制御フローが作れるかもしれない方法の例を。

たとえば条件演算子 ?: を考えてみよう。これは次に起こることについての判断をするものだから、制御フローの一種である。さて、string M(int x)bool B()int C()int D()というメソッドがあったと仮定しよう。そのとき、プログラムのどこかにこんなコード片があるかもしれない:

ここで、C#言語が ?: 演算子を持っておらず、あなたがライブラリメソッド呼び出しとしてそれを実行したかったと仮定しよう。単にこうするだけではだめだ:

なぜなら、これではconsequencealternativeが遅延評価ではなく先行評価されてしまうからである。ただし、こうすることは可能だ:

そうなっていれば、こういう風に呼び出す。

条件演算子をライブラリメソッドとして実装できた。

さてここで、我々が条件演算子をCPSにしたかったと仮定しよう。なぜなら……なぜなら、我々はどんな苦難にも耐えられると思うからだ。CPSでは継続があり、Mを呼び出した後で何かが実行される。それを「現在の継続」と呼ぼう。中身は問わない。それを得る手段は重要ではないから、すでに持っているものとしておこう。

Bを書き直して、boolを受け入れる継続を受け取るようにしなければならない。「boolを受け入れる継続」といえば、それってかなりAction<bool>のように思える。なので、bool B()void B(Action<bool>)に書き直すことができるものと仮定しよう。

Bの継続って何だろう?Bの「後で起きること」とは?一歩ずつ進んでいこう。

BはCPSになったが、Bに渡されるラムダはCPSではない。Conditionalを呼び、Mを呼ぶという2つのことをしているからだ。CPSであるためには、何かを呼びだすのは最後でなければならない。ついさっきBでやった分析を繰り返そう。Mは、intAction<string>を受ける必要がある。CとDは、Action<int>を受ける必要がある。Conditionalはどうだろうか?これも同様に引数を遅延評価する必要があるが、引数のラムダを呼びだしたとしても、どちらも値を返すことができない;むしろ、それらも継続を受けとらなければならない:

さて、Conditionalはこうなった:

まとめ。Bは実行され、その結果のbool値ををラムダに渡す。そのラムダは、bと3種類のラムダをConditionalに渡す。Conditionalは、最初の2つのDelegateのどちらに第3のDelegate(継続)を渡すするべきかについて決める。alternativeを選んだとしよう。そうすると、alternative、すなわちDが実行され、その結果が継続に渡される。その継続とはt=>M(t, currentContinuation)である。それからMは整数tを使って自分自身の処理をした後で、最初の呼び出しにおける"現在の継続"を呼び出す。それが何であったとしても。そして、すべてが完了する。

もはやどこにもreturnがない。あらゆるメソッドはvoidである。あらゆるdelegateはActionである。どんなメソッドも、最後にすることは別のメソッドを呼び出すことだけだ。戻って来る必要がなくなったので、呼び出しスタックはもはや必要ではない。もしも新しいC#コンパイラを作って、このスタイルでプログラミングされたコードを最適化できたとすれば、これらのメソッドはどれも、局所変数や一時的な変数を保存するという即時の要求を越えて呼び出しスタックを消費することはないだろう。

そして、ああなんてことだ、我々はあの単純だった処理をなんという混乱に変えてしまったのだろうか。しかし、ここで成し遂げたことは何なのか、分かるだろうか?私は、?:演算子のCPSバージョンをライブラリメソッドとして定義したのだ; consequencealternativeは遅延評価されるという事実は、それらをラムダとして書き直すことによって達成されている。そして、制御フローは、正しいメソッドに正しい継続を渡すことによって達成されている。

しかしそれがどうした?今回やったことは別に、継続でなければ簡単にできないようなことではなかったのに。ここが一番興味深いところだ:継続とは、制御フローの具象化なのである。ここまで話題にしてきたのは、1つの継続だけが引き渡されているシステムについてだった。継続は事実上ただのDelegateなので、複数の継続を引き渡すことができない理由も、後で使うためにしまっておくことができない理由もない。そういったことをすれば、任意の複雑な制御フローをライブラリメソッドとして作ることができるようになる。複数の継続を記録しておいて、どれが次に実行されるかを決めることによって。

次回:より複雑な制御フローに関してちょっと考えてみた。


インデックスへ戻る


Last Update: 2014-02-12 16:20:49