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

2018-06-30 09:37:18

原文

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

まずは、とあるトピックについてしばらく話させてほしい。それを最初に論じたのは数年前だったけど、その時はすごく短かったので。その話題とはすなわち、継続渡しスタイル（Continuation Passing Style。これからはCPSと略す）だ。このトピックは分かりにくいけれど魅力的だと、多くの人々¹が思っている。

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

https://learn.microsoft.com/en-us/archive/blogs/ericlippert/recursion-part-four-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()というメソッドがあったと仮定しよう。そのとき、プログラムのどこかにこんなコード片があるかもしれない：

M(B() ? C() : D())

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

T Conditional<T>(bool b, T consequence, T alternative)
{
  if (b) return consequence; else return alternative;
}

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

T Conditional<T>(bool b, Func<T> consequence, Func<T> alternative)
{
  if (b) return consequence(); else return alternative();
}

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

M(Conditional(B(), () => C(), () => D()))

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

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

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

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

B(b => M(Conditional(b, () => C(), () => D))) 

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

B(b => Conditional(b, c => C(c), c => D(c), t => M(t, currentContinuation)))

さて、 Conditional はこうなった：

void Conditional<T> (bool condition,
                     Action<Action<T>> consequence,
                     Action<Action<T>> alternative,
                     Action<T> continuation)
{
  if (condition)
    consequence(continuation);
  else
    alternative(continuation);
}

まとめ。 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バージョンをライブラリメソッドとして定義したんだ; consequence と alternative は遅延評価されるという事実は、それらをラムダとして書き直すことによって達成されている。そして、制御フローは、正しいメソッドに正しい継続を渡すことによって達成されている。

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

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

インデックスへ戻る