shiroさんに、何度も「違ってるよ」と言われてしまいました。件<くだん>のコードは、いつものように、ナプキンペーパーに絵を描いて、それをJava風の逐次コードに書き下ろしたのですが、いかんですねー。うまくないですねー。間違ってますねー。
「Java風の逐次コード」にするのが間違いのモトだということで(オイッ)、もっと絵を直接的に書き下ろせる擬似言語を考えましょう。
順次、選択、例外分岐
実行コードを、A, B, Cとかにして、順次(逐次)実行を A; B とセミコロンで書きます。選択的実行を [A | B] と書きます。縦棒記号はパイプじゃなくて、排他的ORの意味。並列同時実行じゃなくて、AかBのどちらか一方だけが実行されます。さらに、{A | b:B} とブレイス(波括弧)で囲んだ場合は、直前で例外が起きてなければAが実行され、例外ならば、Bが実行されるとします。b: は例外フィルターです。つまり、bという種類の例外のときはBですね。b以外の例外は、そのまま捕捉されずに時間方向に飛んでいきます。
{A | b:B | c:C} と書くと、「例外が起きてないならA、種類bの例外ならB、種類がcの例外ならC」を実行します、それ以外の例外なら、ここではなにも実行されずにプログラム全体は次のステップに進みます。捕捉できなかった例外は、次のステップで捕捉されるかもしれません。捕捉されないかもしれません。未来のことはわかりません。
角括弧(ブラケット)と波括弧(ブレイス)は上記のような特殊な意味を持ちますが、丸括弧(パーレン)はまとまりを付けるために使えます。括弧の種類によって全然違う意味になるので十分に注意してください。
では次のコードを考えてみます。
A;
[B | (C ; {D | e:E | f:F})];
{G | h:H}
このコードの可能な実行経路(execution paths)を列挙します。↓は実行成功(正常)、↑は例外発生(異常)を示すとします。↓は地に足が着いている、↑はアッチの世界にイッチャッテイルということですね。最後の実行は成功/失敗が未知、またはどうでもいいとします。
Aが成功する場合:
- A↓, B↓, G
- A↓, B↑, h:H
- A↓, B↑
- A↓, (C↓, D↓), G
- A↓, (C↓, D↑), h:H
- A↓, (C↓, D↑)
- A↓, (C↑, e:E↓), G
- A↓, (C↑, f:F↓), G
- A↓, (C↑, e:E↑), h:H
- A↓, (C↑, e:E↑)
- A↓, (C↑, f:F↑), h:H
- A↓, (C↑, f:F↑)
- A↓, C↑, h:H
- A↓, C↑
Aが失敗する場合:
- A↑, e:E↓, G
- A↑, f:F↓, G
- A↑, e:E↑, h:H
- A↑, f:F↑, h:H
- A↑, e:E↑
- A↑, f:F↑
- A↑, h:H
- A↑
思ったより場合分けが多いでしょう(抜けがないか心配だ)。分岐を組み合わせると、組み合わせが膨れあがるんですよね。
プログラムの振る舞いを比べてみる
なにもしないことを表すために、空文を使ってもいいのですが、ここではnop(no operation)を使うことにします。{A | e:E} で、A がnopの場合を考えることにします。次が例題です。
A;
{nop | e:E};
B;
{nop | f:F};
C
やっぱり、すべての実行経路を列挙します(抜けがないか心配だ)。
Aが成功する場合:
- A↓, B↓, C
- A↓, B↑, f:F↓, C
- A↓, B↑, f:F↑
- A↓, B↑
Aが失敗する場合:
- A↑, e:E↓, B↓, C
- A↑, e:E↓, B↑, f:F↓, C
- A↑, e:E↓, B↑, f:F↑
- A↑, e:E↓, B↑
- A↑, e:E↑, f:F↓, C
- A↑, e:E↑, f:F↑
- A↑, e:E↑
- A↑, f:F↓, C
- A↑, f:F↑
- A↑
次のコードは、ブレイスのなかにブレイスが入れ子で入ってます。これはどんな実行経路を持つでしょう。
A;
{nop | e:E};
{(B; {nop | f:F}) | f:F};
C
シラミツブシにやってみれば分かりますが、実行経路は前のコードと変わりません。つまり、ここに挙げた2つのコードは字面は違っても、同じ振る舞いをします。
と、ここまでは僕がナプキンペーパーに絵を描いて確認したことです。
try-catch構文への翻訳
次の形のプログラム(というか実行記述式)は、まずXを実行し、例外が出なければ何もせず(nop)、種類がzの例外発生のときはZをすることです。
X;
{nop | z:Z}
その動作を考えれば、次のtry-catch構文と同じです。
try {
X
} catch(z) {
Z
}
nopのところに任意の文Yを置いた形を考えましょう。
X;
{Y | z:Z}
次のtry-catchでいいでしょうか?
try {
X
} catch(z) {
Z
}
Y
X↓, z:X↓, Y という実行経路があるかないか考えてみると違いがあります。この翻訳ではダメです。
どうも、問題の擬似コードをスマートにtry-catchで書くのは難しいようです。zの例外ハンドラZが実行されると自動的に z_handled というフラグが立つと仮定して、次のように書きましょう。
try {
X
} catch(z) {
Z
}
if (!z_handled) {
Y
}
以上の書き換え規則を使って、前節で出てきた2つの式をtry-catch構文に翻訳してみます。
A;
{nop | e:E};
B;
{nop | f:F};
C
try {
try {
A
} catch(e) {
E
}
B
} catch(f) {
F
}
C
A;
{nop | e:E};
{(B; {nop | f:F}) | f:F};
C
try {
try {
A
} catch(e) {
E
}
} catch(f) {
F
}
if (!f_handled) {
try {
B
} catch(f) {
F
}
}
C
もとの2つの擬似コードが同値なので、try-catchに書き換えた2つのコードも同じ振る舞いのはずです。僕は、前の記事で次のように間違っていました。
try {
A
} catch(e) {
try {
E
} catch(f) {
F
}
}
if (!f_handled) {
try {
B
} catch(f) {
F
}
}
C
A↑, f:F↓, C という実行経路を考えると、僕が間違っていたことがハッキリします。これがshiroさんの2番目のご指摘でした。
プログラムの書き換えといえば…
条件分岐や例外処理を含むプログラムコードを、振る舞いを変えずに書き換えることはけっこう難しい作業です。ボヤッとした勘に頼ると、僕のように間違えます(振る舞いが変わってしまう)。すべての実行経路について振る舞いを調べるのは良い方法ですが、実行経路を完全に列挙するのが困難です。経路の数が多くなると、事実上不可能でしょう。
正しいことが保証された書き換え規則、一種のリファクタリング・パターンに基づき書き換えれば振る舞いを保存できます。制御構造をグラフ(フローチャート!)で表して、グラフ書き換えアルゴリズムを適用すればいいんです。書き換えシステム(rewriting system)は、論理の演繹系と似たようなもので、基本書き換え規則は推論規則に対応します。
グラフとその同値変形といえば、アルゴリズム的結び目理論(例えばライデマイスター移動)が使えそうでしょ。結び目理論の定式化のひとつにトレース付きモノイド圏(traced monoidal category)があって … … 今日はこのへんでやめます。