命題論理から考えるデバッグ手法
はじめに
デバッグはプログラミングの技術として非常に重要であるにもかかわらず、体系的に教える手法がほとんどないことで知られています。そこでこの記事ではプログラムのデバッグを数学的なアプローチを用いて説明することを試みました。数学の諸概念を扱うのでそれらの前提知識があると読みやすいですが、もしそれらの概念に詳しくなかったとしても、前提知識についてはなるべく説明するように心掛けています。
命題論理とは
命題論理をデバッグに応用する前に、命題論理そのものの復習をしておきます。既に理解しているという方は プログラミングに応用する まで読み飛ばしてもらって構いません。
命題とは
命題の定義は場所によって様々ありますが、一般的な定義として 「真か偽かが明確に定まる文」 のことを命題と呼ぶことにします。例えば次は命題の例です。
-
5 < 3 - 東京は首都である (真)
- (
x = 2 x > 3
逆に次のような文は命題ではありません。
-
x > 3 x - 京都は首都ですか？ (真偽を与えられない)
論理記号の導入
先ほど考えた例は全て原子命題と呼ばれる 「これ以上分解できない命題」 でしたが、命題同士を組み合わせて別の命題を作るということが考えられます。よく使われる論理記号として次の5つがあります。
-
A∧B -
A∨B -
￢A -
A→B -
A↔B
一般的に次の言い換えが行えます。
-
A→B ￢A∨B -
A↔B (A→B)∧(B→A) - すなわち
(￢A∨B)∧(￢B∨A) - すなわち
(A∧B)∨(￢A∧￢B)
- すなわち
つまり
それぞれの論理記号の意味はそれぞれのプログラミングの世界での意味とほぼ同じですが、真理値表 によってその意味を確認しておきましょう。真理値表とは、例えば
それぞれの論理記号について真理値を考えてみると、次のようになります。(読みやすさのために真を1、偽を0として表現しています)
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 |
| 0 | 1 |
必要条件・十分条件
命題
-
Q P -
Q P
-
-
P Q -
P Q
-
直感的には
集合との対応
実は命題は集合と対応付けることができます。例えば
※ここで
これは単に同じことを複雑に言い換えているだけに感じるかもしれません。しかし論理記号を考えると集合を考えることの面白さが出てきます。
この例だと単純に
同様に
ここで
-
P→Q x∈(\bar{A}∪B) -
P↔Q x∈((A∩B)∪(\bar{A}∩\bar{B}))
これだけだと単に複雑な結果に思えるかもしれませんが、これらが常に成り立つような
-
P→Q A⊂B ∵(\bar{A}∪B) = U ⇔ B⊃\overline{\bar{A}} ⇔ A⊂B
-
P↔Q A=B ∵((A∩B)∪(\bar{A}∩\bar{B})) = U ⇔ A∩B⊃\overline{\bar{A}∩\bar{B}} ⇔ A∩B⊃A∪B ⇔ A = B
※ここで
これは非常に面白い結果で、論理的に (真理値表的に) 見れば複雑だった含意・同値が集合関係では非常にシンプルに表現できることが分かりました。この関係はのちの議論で非常に重要になります。
プログラミングに応用する
長い長い下準備が終わったところで、実際にプログラミングの世界で命題論理をどう役立てていくか考えてみましょう。
プログラミングの世界と命題の世界を繋げる
例として次のプログラムを題材にします。main() 関数が一定間隔で呼ばれている状況で、rightKey() や leftKey() はそれぞれ右矢印キーと左矢印キーが押されているかどうかを検知する関数だとします。
let x = 0;
function main() {
console.log('Hello, main!');
if (rightKey()) {
console.log('Hello, rightKey!');
x += 1;
}
if (leftKey()) {
console.log('Hello, leftKey!');
x -= 1;
}
ctx.clearRect(0, 0, WIDTH, HEIGHT);
ctx.fillRect(x, 10, 30, 30);
}
ここで「このプログラムの内部状態」全体の集合を考えることができます。これを便宜上
さらに内部状態の全体集合
-
console.log('Hello, main!');が実行されてHello, main!がコンソールに表示される -
x += 1;が実行されてxが1足される - if文の時点で
rightKey()がtrueを返す
さらにこれらの要素、すなわちこのプログラムにおいて起きうることは適切な前提条件を与えれば命題とみなすことができます。これはそのプログラムがある行を実行するかしないか、ある時点での変数の値が○○かどうか、など真偽を一意に定めることができるためです。
命題論理を活用してデバッグする
命題とみなすことができるということは、論理関係を考えることもできれば、対応する集合を考えることもできます。これらの考え方を用いてデバッグを考えていきましょう。
デバッグのサイクル
このプログラムは右矢印キーが押されている間は右に動くことが期待されているわけですが、何らかの原因で 右矢印キーを押しても右に動かない という状況が生まれたとします。これは開発者の意図と反した挙動であり、いわゆるバグです。このバグの根本的な原因を追究していきましょう。
右矢印キーを押しても右に動かない、という状況はプログラムにおいて発生している事象であり、起きうる事象の全体集合
ここで原因を追究するという行為は常に
-
Q Q Q Q Q -
Q P∧￢Q P∧￢Q
つまりバグという事象が起きた時、そのバグが起きる原因となる可能性のある現象 (=仮説) を考え、それが正しいかを検証することでより狭い範囲に原因を絞る、というプロセスを繰り返していくことになります。最終的に自明に直せる事象 (例えばtypoしていた、引数の順序を間違えていた、など) まで辿り着けば無事バグを直せたということになります。
集合で考える
また、このプロセスは集合で考えると分かりやすくなります。はじめにバグの事象として
しかし仮説
逆に
つまりどちらの場合にしろ、考えるべき内部状態が減っていることが分かります。これは本質的な原因に迫っていることを表しています。この考え方を用いると、良いデバッグの道筋とは何かが自ずと見えてきます。つまり、なるべく考えられる内部状態を減らす方向に向かうデバッグこそが、良いデバッグであると言えます。
具体例で考える
抽象的な議論では分かりづらいと思うので、具体的な例を考えてみましょう。先の議論においての
- 仮説
Q x += 1;が実行されていない
右に動かないという事象をより具体的なプログラミング的な言葉で言い換えたような形です。プログラム全体から鑑みるに
x += 1; が実行されたらどうかを直接確認することは難しいですが、x += 1; の実行と同値な条件[1]である console.log('Hello, rightKey!'); を確認することは容易です。実際のデバッグでは、検証のプロセスでこのような同値の条件を確認するテクニックを使うことが多いです。
ここでは実行されていないことが確認された、すなわち仮説 x += 1; が実行されないのかという原因を追究していくことになります。これに対しての仮説
- 仮説
R rightKey()の返り値がfalse(falsy な値) になっている
これも
let x = 0;
function main() {
console.log('Hello, main!');
+ const target = rightKey();
+ console.log('target = ', target);
+ if (target) {
- if (rightKey()) {
console.log('Hello, rightKey!');
x += 1;
}
if (leftKey()) {
console.log('Hello, leftKey!');
x -= 1;
}
ctx.clearRect(0, 0, WIDTH, HEIGHT);
ctx.fillRect(x, 10, 30, 30);
}
このように書き換えても通常プログラムの動作は変わらず、追加でif文に渡される rightKey() の値を知ることができます。ここでは rightKey() で undefined が返ってきていた、すなわち仮説 rightKey() が undefined を返すのかを内部実装やドキュメントなどを参照して探っていくことになるでしょう。
これ以上の説明しませんが、命題論理を活用したデバッグの手法は分かって頂けたのではないかと思います。特段変なことをしているわけではなく、単に仮説の検証を繰り返して原因を絞っていくという一般的なプロセスを、より形式的に記述したような形です。
これまでの命題論理が一切分からなかったとしても、このプロセス自体はデバッグの一般的な手法として有用なのではないかと思います。ぜひ役立ててみてください。
おわりに
この考え方が実際のデバッグに役立つかは正直分かっていませんが、1つの考え方として理解しておくと面白いのかなと思います。加えて、実は数学的なアプローチはこういう場面でも活用できるということが示せたら、それも一つ良かったのかなと思っています。
もし間違いとかがあれば優しくコメントとかで教えてもらえると嬉しいです。お願いします。
-
少なくともJavaScriptにおいては、例外が起きない限り隣接する2つの処理のどちらかだけが実行されないということは基本的に起きないので、任意の前提条件において
x += 1;が実行されることとconsole.log('Hello, rightKey!');が実行されることは同値な命題であることが分かります。 ↩︎
Discussion