このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

プログラムの算術的計算法

あー、やっぱりな -- 連休で調子がくるって、まだ何かおかしいよ。

で、少し頭のトレーニングになる話でもしましょうか。

pが論理式で、Aが文とか文の並びだとして、if (p) {A;} else {A;}って書く人はあまりいませんよね、これは単にA;と書いても“同じ”だから。次の3つの表現も事実上“同じ”なのはわかるでしょう。

// その1
if (p) {
 ;
} else {
 if (q) {
  A;
 }
}

// その2
if (!p) {
 if (q) {
  A;
 }
}

// その3
if (!p && q) {A;}

次の「その2」はなんだか無意味みたいですが、「その1」と“同じ”です。

// その1
while (p) {A;}

// その2
if (p) {
 A;
 while (p) {A;}
}

さて、一般に2つのプログラムコードが“同じ”であることを判定するのは難しいことです。が、算術的計算でプログラムの同値性を示せることもあります。その計算法(の一例)を紹介しましょう。

※印刷の時はサイドバー消えます。
内容:

記号と言葉のお約束

論理式の表現と計算には、標準的な論理記号を使いましょう。以前、「プログラマのための述語論理」でも登場したやつです。

記号 意味 プログラミング言語での記号
かつ(連言) &&
または(選言) ||
¬ ではない(否定) !

論理計算については今特に説明しませんが、二重否定の除去「¬¬p = p」とか、ド・モルガンの法則「¬(p∧q) = (¬p)∨(¬q)」とかは使います。

論理式とプログラムの実行文を区別したいので、次の約束をします。

  • A, Bなどの大文字 -- 文や文の並びなどを表す
  • p, qなどの小文字 -- 条件、論理式を表す

以下、「文」と言ったら、単純な文だけではなく、文の並び(複文)や複数の文を組み合わせた複雑な表現も意味します。

ちょっと変わった制御構造

プログラムの制御構造には、順次実行、非決定性の選択、条件(ガード)付き実行の3種を基本に採用します。順次実行はお馴染みのものですが、非決定性の選択、条件付き実行は、普通の言語ではあまりお目にかかりません。

順次実行、非決定性の選択、条件付き実行を、それぞれ次のような記号で書くことにします。括弧内はキーワードを使った補助的な代替記法です。

  • A;B
  • A | B (choose A or B end)
  • p・A (when (p) do A end)

非決定性の選択 A | Bは、AかBのどちらかが実行されます。が、どっちが実行されるかは前もってわかりません。その場その場でサイコロをふって決めると思ってください。

条件付き実行 p・Aif (p) then A endと似てます。が、同じではありません。条件(ガードとも呼ばれます)pが成立しないときは、そこで、プログラムは無限に待ち続けます。もし、何らかの外的要因でpが真になれば、プログラムが続行されることもあります。

非決定性の選択はバクチ打ちで、条件付き実行はイクジなし(ガードを強行突破はできない)ってわけです。こんなトンデモナイ制御構造でまともにプログラムが記述できるとは信じがたいのですが、バクチ打ちとイクジなしでもうまく使えば通常の制御構造を実現できます。

if-then-elseの実現

まず、非決定性の選択と条件付き実行により if (p) then A else B を実現しましょう。答えを先に言ってしまうと、p・A | (¬p)・Bです。これは次のようにも書けます。

choose
 when (p) do A end
 or
 when (!p) do B end
end

割と簡単できれいな形です。が、どうも変な気もします。今、pがtrueだとして考えてみましょう。choose(選択)はサイコロをふるので、二番目の選択肢が選ばれるかもしれません。すると、条件(!p)はfalseとなり、“待ち”に入ってプログラムはつっかえてしまうはずです。そうなると、明らかにif文とは違う振る舞いになります。

いやっ、実は非決定性の選択の解釈は、「プログラムは通れる実行経路を通ろうとするが、どこを通るかはわからない」ということです。選択肢の片一方が通れない(実行を続行できない)なら、そこで“待ち”に入るのではなくて、もう一方を選んで進みます。

簡単な計算例

記号「;」「|」「・」は、文と論理式に対する二項演算記号と思えます。「;」と「・」は積(掛け算)のように、「|」は和(足し算)のように振る舞います。そして、普通に期待される計算法則はだいたい成立します(って、ひどくイイカゲンな言い方ではあるが)。計算法則を並べる前に、具体例を出してしまいましょう。if (p) then A else Aの計算です。

// if (p) then A else A 
  p・A | (¬p)・A  // ・と|に関して分配法則
= (p∨¬p)・A      // p∨¬p はtrue
= true・A          // trueをガードにしても影響はない
= A
// よって、if (p) then A else A は A と同じ

「・」は省略して、「|」と「∨」をどちらも「+」と書いて、「¬p」を「p'」、「true」を「1」と書くと、簡潔だし親しみも持てるでしょう。

  pA + p'A   // 分配法則
= (p + p')A  // p + p' = 1
= 1A         // 1A = A
= A

文Aに、論理定数1(ture)をガードとして前置しても何の変化もないので、1・A = A です。よって、どんな文もガード付き文だと考えてもかまいません。

さて、n個の文 A1, A2, ..., An とn個の論理式 p1, p2, ..., pn から、p1・A2 | p2・A2 | ... | pnAn (簡潔な表現なら p1A1 + p2A2 + ... + pnAn)を作れますが、これは、非決定性の多方向分岐です。プログラム実行のある時点で、各piは1(true)か0(false)の値をとります。nで割り算すると、事象Aiが確率(pi/n)で生起するときの和事象と似た形式です。確率計算と同じではないのですが、かなり似てます。A + A = A、pp = p など(ベキ等性という)に気を付ければ線形代数*1の計算とも似てます。

そんなわけで、プログラムを計算の対象にできるらしいことがわかったわけですが、今日は疲れたのでココマデ。続きは次回

*1:形<かたち>ではなくて型<かた>を使うべき、という話もあるが僕はあまり気にしてない