「未定義な遷移の解釈 -- 3つの立場」にはブックマークも星も付いてませんが、クワタさんやsumimさんが反応してくださったので、続きを書いてみます。前のエントリーで、「未定義」概念に対する3つの考え方を紹介しました（他の考え方もあるかも知れません）。まだ分析が甘いのでもう少し詰めてみましょう。
内容：
- 言葉の使い方
- 実例
- 実例の分析
- 未定域をさらに分類する
- 三値論理と計算の停止性など
- 三値を二値に還元できるのは誰なのか
●言葉の使い方
部分関数に関する記法や用語が整備されてないので、今回ここで使う言葉を決めておきます。f:X→Y が部分関数ということは、D⊆Xである部分集合Dと普通の関数（全域関数）D→Yがあることでした。
- 部分関数と、対応する全域関数を同じ記号（例えばf）で表す。混乱の危険が若干あるが、文脈から区別できるでしょう。
- 圏論の標準的用語法に従い、集合Xを部分関数fの域（domain）、集合Yを余域（codomain）と呼ぶ。
- Dを部分関数fの確定域、XからDを除いた残り（Dの補集合）をfの未定域と呼ぶ。
例えば、「未定義な遷移の解釈 -- 3つの立場」で例にした部分関数downに関しては、
- {0, 1, 2, 3, ...} が域、
- {0, 1, 2, 3, ...} が余域（域と同じ集合）、
- {1, 2, 3, 4, ...} が確定域、
- {0} が未定域。
確定域もハッキリと示したいときは、f:X⊇D→Y のように書くことにします。
●実例
JavaScript風に：
function exam(n:Integer) {
if (n == -1) throw "error";
if (n == 0) return 1;
return n * exam(n - 1);
}
この例の記述構文は基本的にJavaScriptですが、引数の型宣言ができて、静的型チェック（コンパイル時に型エラーを検出）を行うと仮定してます。よって、関数examの引数nは整数に限定されます。
●実例の分析
関数examは、域が整数全体（Integer）、確定域が{0, 1, 2, 3, ...}である部分関数とみなしてよいでしょう*1。実際、n ≧ 0 では、exam(n)は「nの階乗」になっています。
- n ≧ 0 なら、exam(n) = n! （n!は「nの階乗」のこと）
D = {n∈Integer | n ≧ 0}として、exam:Integer⊇D → Integer と書けますね。
nがDに入らないとき、つまり負の値のときが問題です。nが負なら、exam(n)は未定義ですが、未定義具合がマダラですよね。n = -1 のときの未定義はエラーを発生させていますが、n ≦ -2 ではエラーが発生しません -- が、再帰が止まらないので、いずれスタック*2を使い果たします。
実際の処理系では、スタックの使い果たしもエラー（例外）として通知されるかも知れませんが、もしスタックが無限にあるなら、exam(-2)は無限走行し、結果を返しません。「未定義具合がマダラ」といったのは、n = -1 の未定義具合と n = -2 の未定義具合がどうも異なる感じがするからです。
●未定域をさらに分類する
前節の「分析」から、未定域（実例では負の整数）の引数に対して、関数が自覚的・自発的にエラーを発生させているケースと、関数は何も知らないままに無限に走るケースがあることがわかります。
この2つのケースは区別すべきでしょうか？ 区別したほうが精密な記述ができそうですから区別しましょう。まず、関数が無限に走って値を返さないことを、便宜上「⊥という値を返した」とみなします。ここで、記号⊥は一種のフィクション、トリックと思ってください*3。「exam(-2) = ⊥」と書いてあったら、「exam(-2) は無限に走って値を返さない」と読み直してください。
架空の値⊥を含めると、値の範囲は、Integer∪{error, ⊥} となります。戻り値は次の意味を持ちます。
- Integerに属する値を返した ⇒ 計算が正常に終了した。
- errorを返した ⇒ 関数が、なんらかの異常事態を自分で認識した。
- ⊥を返した ⇒ 関数は、自分では異常とは認識できず、無限に走り、計算は終了しない。
この戻り値の分類から、引数の領域も次の3つのパートに分類されます。
- exam(n) がIntegerに属する値を返す ⇒ nは確定域に属する。
- exam(n) がerrorを返す ⇒ nは未定域に属する。nが未定域に入ることをexamは認識可能。
- exam(n) が⊥を返す ⇒ nは未定域に属する。nが未定域に入ることをexamは認識不可能。
これで、未定域は、認識可能なパートと認識不可能なパートに細分されました。
●三値論理と計算の停止性など
さてここで、関数examに対して次のような関数を考えましょう。
function isDefined(n:Integer) {
try {
exam(n);
return true;
} catch (e) {
return false;
}
}
isDefinedは、整数引数nに対して、nがexamの確定域に入るならtrueを、そうでなければfalseを返します。true, falseの真偽値（Boolean）を返す関数を論理学では述語と呼びます。ですから、isDefinedは述語です。
たぶんもうお気づきでしょうが、述語isDefinedは、examが無限走行すると真偽値を返せません。正確に言えば次のようになります。
- exam(n)の計算が正常に停止するとき ⇒ isDefined(n) ＝ true
- exam(n)の計算の途中で異常事態を認識したとき ⇒ isDefined(n) ＝ false
- exam(n)の計算が無限走行するとき ⇒ isDefined(n) ＝ ⊥
つまり、isDefinedの値は{true, false, ⊥}の三値となります。isDefinedの3つの値はちょうど、確定域、認識可能未定域、認識不可能未定域の分類に対応します。もちろん、⊥は架空の値ですが、それでも、and, or, notなどの論理演算を三値に拡張することもできます*4。
認識可能な未定義と認識不可能な未定義の区別があるときの推論には、三値論理のほうが便利かも知れません。このような状況は、「ゲーデルの不完全性定理」や計算の停止性問題とも関係します（「プログラマのための『ゲーデルの不完全性定理』(2)：速攻速習編」を参照）。
●三値を二値に還元できるのは誰なのか
スタックの長さが有限なら、スタックがなくなった時点で例外を発生させることができます。通常は言語処理系やOSがスタックを監視するでしょうが、関数自体が監視することも（やれば）できそうです。
function exam(n:Integer) {
if (n == -1) throw "error";
if (n == 0) return 1;
if (noMoreStackFrames()) throw "error";
return n * exam(n - 1);
}
無限のスタックに対しても、noMoreStackFrames()のような監視関数を作れないでしょうか？ 無理ですよね、人間には。でも、神様ならどうでしょうか？ 無限スタックのお尻に番兵をしかけて、番兵を踏んだら例外を発生させればいいでしょ。… でも、「無限のお尻」って？ 感じとしては、0, 1, 2, 3, ...., ω（お尻！）です。ω番目にダミーのスタックフレームを置いて番兵にするのです。
そんなバカな!? いやっ、神様＝超越者ならできるんですよ。少なくとも、「できるはず」と信じている人はたくさんいます。この超越者の立場からは、認識可能なerrorと認識不可能な⊥を区別する必要はありません。だって、超越者の辞書には認識不可能なんてないのですから。
超越者の世界におけるexamは、
- 有限時間走行して整数を返す。
- 有限時間走行してerrorを返す。
- 無限時間走行してerrorを返す。
のいずれかです。超越者にとって有限と無限の差はどうでもいいので、述語isDefinedは、必ずtrueかfalseのどちらかを返します。つまり、二値述語です。
三値論理とかカッタルイ(?)ことを持ち出すのは、我々人間が無限時間走行とその結果を瞬時に把握することができないせいなのでしょう。超越者の世界では、真偽は常に定まり、有限と無限にさしたる差はなく、数学的関数と走行するプログラムで実装された関数の区別も不要なのです。でも僕たち人間はそうもいかないので、例外と無限走行を区別して、「未定義とはなんぞ」とかツマラン詮索をすることになるわけね。
