Menu


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

原文

前回の『素晴らしい冒険』は:「しかし、我々は複数の継続の経過を追って、どちらが次に行くようになるかについて決めることによって、任意の複雑な制御フローを造ることができる。」

条件文より複雑な何かの例を見よう。「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)であった。我々は現在、bodyNormalとbodyErrorが何であるかについてわかっているので、それらも外へ展開しよう。我々がこれを外へ展開するとき、本体は以下のことをする:

A(
  x=>B(               // A's normal continuation
    x,                // B's argument
    ()=>D(            // B's normal continuation
      qNormal,        // D's normal continuation
      qError),        // D's error continuation
    ()=>C(            // B's error continuation
      ()=>D(          // C's normal continuation
        qNormal,      // D's normal continuation
        qError),      // D's error continuation
      qError)),       // C's error continuation
  ()=>C(              // A's error continuation
    ()=>D(            // C's normal continuation
      qNormal,        // D's normal continuation
      qError),        // D's error continuation
    qError))          // C's error continuation

それで、本体はAを呼び出す。それは即座にThrowを呼び出す。そして、通常の継続として若干複雑なものを渡し、エラー継続として()=>C(()=>D(qNormal, qError), qError)を渡す。

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

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

それではDがスローするならどうだろうか?その場合は、それはqErrorを呼ぶ。Dがスローしないならば、結局それはqNormalを呼ぶ。(と我々は期待する!)

後ろに戻ろう。Aがスローしないように我々がThrowを取り除くならどうだろうか?それがその正常時の継続にゼロを渡すだけならどうだろうか?さて、上記のAの正常時の継続はBへの呼び出しであるので、これはBにゼロを渡す。そして、あなたがそれからわかることができるように、Bがスローするならばそれは制御をCへ移し、Bがスローしないならばそれは制御をDへ移す。

さあ、この通りだ。我々は、単なるメソッドとしてtry-catchとthrowを実装した。さらに、我々はそれら両方を1行メソッドとしてインプリメントした。明らかに、try-catch-throwは、全然まったく難しくない!

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

考えられるどんな制御フローでも、かなりたくさんである。これはうまくいくのは、すべての可能な制御フローが単に条件つきの「goto」に対する装飾的なラッパーだからだ。if文はgotoであり、ループはgotoであり、サブルーチン呼び出しはgotoであり、returnはgotoであり、例外はgotoであり、それらはすべてgotoである。継続では、どんな特定の種類のgotoの非局所的に分岐している性質でも、完全に無関係である。あなたは、若干の全くエキゾチックな制御フローをCPSでインプリメントすることができる。復旧可能な例外、両方の枝を平行に評価する条件文、yield-return、コルーチン。いったい、あなたが本当に必要とするならば、あなたは前方へ動作して、それから、再び後方に自分を走らせるプログラムを書くことができる。それが一種の制御フローであるならば、あなたはCPSでそれをすることができる。

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


インデックスへ戻る


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