継続渡しスタイル(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)
だった。 bodyNormal
とbodyError
が何なのかはもうわかっているので、それらも展開しよう。全部を展開すると、トライ本体は以下のことをしている。
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
がスローするならどうなるだろうか?その場合は、D
は qError
を呼ぶ。 D
がスローしないなら、D
は最後に qNormal
を呼ぶ(ことが期待される!)
ちょっと戻ってみよう。 A
から Throw
を取り除いて、A
がスローしないようにしたならどうなるだろうか? A
がその正常時の継続にゼロを渡すだけなら? さて、上記の 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で実現できるんだ。
次回: コルーチンは大雑把に。