matarillo.com

The best days are ahead of us.

継続渡しスタイル(CPS)再訪、パート2: 制御フローは大雑把に

2018-06-30 09:37:18

原文

前回の『素晴らしい冒険』はこの文章で終わった。 「複数の継続を記録しておいて、どれが次に実行されるかを決めることによって、任意の複雑な制御フローをライブラリメソッドとして作ることができるようになる。」

条件文より複雑な何かを例にとろう。try - catch の単純化されたバージョンを考えてみる。それは、throw 文に式がないものだ。 throw は、その文を囲んでいる catch のうち最も近くのところに移動する、非局所的な goto でしかなくなる。以下の

void Q()
{
    try
    {
        B(A());
    }
    catch
    {
        C();
    }
    D();
}

int A()
{
    throw;
    return 0; // unreachable, but let's ignore that
}
void B(int x) { whatever }
void C() { whatever }
void D() { whatever }

についての従来的な解釈は、「この近くのどこかに catch ブロックがあるのを覚えておく。自分が何をしていたかについて覚えておく。 A() を呼び出す。呼び出しが正常に復帰したなら、自分が何をしていたかについて覚えておいた上で、 A() からの結果を渡しながら B() を呼び出す。 B() の呼び出しが正常に復帰したなら、 D() を呼び出す。 A() または B() の呼び出しが正常に復帰しなかったなら、以前に覚えていた catch ブロックを探す。 C() を呼び出した後で D() を呼び出す。」となる。

本物のCLRでは、throw を実行するコードは発狂するほど難しくなる; フィルタやハンドラーなどを探して呼び出しスタックの中を走り回らなければならないからだ。もし言語に try - catch が組み込まれていなかったらどうなるだろう? そんな複雑極まりないことを ライブラリメソッド として実装する方法は、たとえそれを望んだとしても、まったくない。いや、実はあるのだろうか? CPSをサポートする言語だったら Try()Throw() メソッドを自作できるのだろうか?

スローするかもしれないあらゆる関数に 2つ の継続を引き渡すことから始めてみてはどうだろうか。1つの「正常時の」継続と1つの「エラー時の」継続を。 Q も例外をスローするかもしれないとしよう。そしてすべてを「継続が2つ」のCPSに変換してみよう。すると、こうなる。

void A(Action<int> normal, Action error)
{
    Throw(()=>normal(0), error);
}

これにはちゃんと意味があるはずだ。A() は何をするものだろう? それは Throw を呼び出し、正常時の継続にゼロを渡すという形でゼロを返す。したがって、 Throw の正常時の継続は、 A() の正常時の継続にゼロを渡すものになっている。(すぐにわかることだが、これは無意味だ。Throw は定義上、正常に完了しないからだ。しかし、これも単なる一つの関数呼び出しでしかないから、このまま一つの関数呼び出しとして扱い続けることにしよう。)

void B(int x, Action normal, Action error) { whatever }
void C(Action normal, Action error) { whatever }
void D(Action normal, Action error) { whatever }

Throw の実装はどういうものになるだろう? 簡単だ! Throw はエラー時の継続を呼び出して正常時の継続は破棄する。

void Throw(Action normal, Action error)
{
    error();
}

Try の実装はどうなるだろう? こっちは少し難しい。try - catch って、そもそもどういうものだろうか? それは try 本体用にはエラー時継続を新しく作るけれど、catch 本体のためにはしない。それをどう書けばいいのだろう? 申し訳ないけど天下り的にコードを登場させるので、それがちゃんと動くかどうかだけ確認してほしい。

void Try(Action<Action, Action> tryBody,
         Action<Action, Action> catchBody,
         Action outerNormal,
         Action outerError)
{
    tryBody(outerNormal, ()=>catchBody(outerNormal, outerError));
}

void Q(Action qNormal, Action qError)
{
    Try (
       /* tryBody      */ (bodyNormal, bodyError)=>A(
       /* normal for A */   x=>B(x, bodyNormal, bodyError),
       /* error for A  */   bodyError),
       /* catchBody    */ C,
       /* outerNormal  */ ()=>D(qNormal, qError),
       /* outerError   */ qError );
}

OK。まず最初に、これはCPSになってる? イエス。あらゆるメソッドは void を返しているし、あらゆるdelegateは void を返している。そして、あらゆるmethodまたはラムダは、その最後の処理で、他のメソッドを呼び出している。

では、この実装は正しい? ウォークスルーで動作を調べてみよう。最初に Try を呼び出すときに、トライ本体、キャッチ本体、正常時の継続、そしてエラー時の継続を渡している。

Try はトライ本体を呼び出す。そしてそれは2つの継続を受け取っている。Try には outerNormal が渡されているけれど、その実体は ()=>D(qNormal, qError) で、つまりそれがトライ本体の正常時の継続になる。

トライ本体には、エラー時の継続として、()=>catchBody(outerNormal, outerError) が渡されている。それが何をするかが分かるように展開しよう。キャッチ本体は、C だったわけなので、トライ本体のエラー継続は、()=>C(()=>D(qNormal, qError), qError) と評価される。(このステップはきちんと確認して理解しよう。)

トライ本体は何だっただろうか? それは、(bodyNormal, bodyError)=>A(x=>B(x, bodyNormal, bodyError), bodyError) だった。 bodyNormalbodyError が何なのかはもうわかっているので、それらも展開しよう。全部を展開すると、トライ本体は以下のことをしている。

A(
  x=>B(               // Aの正常時の継続
    x,                // Bの実引数
    ()=>D(            // Bの正常時の継続
      qNormal,        // Dの正常時の継続
      qError),        // Dのエラー時の継続
    ()=>C(            // Bのエラー時の継続
      ()=>D(          // Cの正常時の継続
        qNormal,      // Dの正常時の継続
        qError),      // Dのエラー時の継続
      qError)),       // Cのエラー時の継続
  ()=>C(              // Aのエラー時の継続
    ()=>D(            // Cの正常時の継続
      qNormal,        // Dの正常時の継続
      qError),        // Dのエラー時の継続
    qError))          // Cのエラー時の継続

つまり、トライ本体は A を呼び出す。 A は即座に Throw を呼び出す。その時、正常時の継続としてちょっと複雑なものを渡し、エラー時の継続として ()=>C(()=>D(qNormal, qError), qError) を渡す。

Throw は、その通常時の継続を無視して捨てて、()=>C(()=>D(qNormal, qError), qError) を呼び出す。

C(もしくはそこから呼び出される何か)がスローするならどうなるだろうか? C がスローしたなら、制御はすぐに qError に移る。 Q を呼び出すにあたってどんなエラーハンドラーが置かれていても、である。 C が正常に完了するならどうなるだろうか? C の正常時の継続は ()=>D(qNormal, qError) なので、 C が正常に完了するなら D が呼び出される。

それでは D がスローするならどうなるだろうか?その場合は、DqError を呼ぶ。 D がスローしないなら、D は最後に qNormal を呼ぶ(ことが期待される!)

ちょっと戻ってみよう。 A から Throw を取り除いて、A がスローしないようにしたならどうなるだろうか? A がその正常時の継続にゼロを渡すだけなら? さて、上記の A の正常時の継続は B の呼び出しなので、結局 B にゼロが渡される。そして、想像通り、B がスローするならば制御が C へと移り、B がスローしないならば制御が D へと移る。

さあ、これで全部だ。 私たちは、 try - catchthrow を単なるメソッドとして実装できた。 しかも、私たちは両方とも 1行メソッド として実装できた。ということは、 try - catch - throw は、全然まったく難しくないってことだ!

制御フローを具現化したものであるCPSについて、私が何を言いたかったか分かるかな? 継続は、次に起こることを意味するオブジェクトだ。そしてそれこそが、制御フローにほかならない。制御フローとは次に何をするか決定するものだからだ。 考えられるどんな制御フローでも、CPSで表現することができる。

考えられる全部の制御フローというのは相当たくさんある。なのにそれら全部がうまくいくのは、すべての可能な制御フローは、条件つきの goto に対するいい感じのラッパーでしかないからだ。if 文は goto だし、ループも goto だし、サブルーチン呼び出しも goto だし、returngoto だし、例外も goto だし、それらは全部 goto だ。継続にとっては、どんな種類の goto が非局所的に分岐する性質を持っていようが、何も関係ない。とても風変わりな制御フローだろうがCPSで実装することができる。復旧可能な例外とか、両方の分岐を同時並行で評価する条件文とか、yield-return とか、コルーチンとか。いやいや。本当に必要なら、普通に前へ前へと進んだ後で、後へ後ろへと戻っていくプログラムだって書くことができる。制御フローの一種でさえあれば、どんなものでもCPSで実現できるんだ。

次回: コルーチンは大雑把に。


インデックスへ戻る