コインとサイコロで非決定性プログラミングをお手軽に実験してみるよ

だいぶ前に書いた「プログラムの算術的計算法」と「プログラムの算術的計算法 (続き＆完結）」において、非決定性の選択と非決定性の繰り返しについて述べました。これらを非決定性述語により実現してみましょう。

コイン・トスとサイコロ博打で非決定性を実現

構文 choose A or B end は、「AかBのどちらかが実行されるが、どっちが実行されるかはわからない」という意味です。これは、次のようにコードでシミュレートできるでしょう。

if (coin()) {
 A;
} else {
 B;
}

ここで、coin()が非決定性の述語で、コインを投げて表ならtrue、裏ならfalseを返す関数です。

構文 repeat A end は、「Aを何回か繰り返すが、何回繰り返すかはわからない」という意味です。こちらは次のように書けるでしょう。

var n = dice();
for (var i = 0; i < n; i++) {
 A;
}

dice()は、サイコロをふって適当な整数を返す関数です。ほんとのサイコロは1から6までの整数ですが、dice()が返すのは、0以上のまったく任意の整数です。100とか1億とかが値となる可能性も否定できません。しかし、実用上はあまり大きな数が返るのも困るので上限値MAXを決めて、0≦n＜MAX と範囲を限定します。

coin()とdice()は例えばJavaScriptで次のように書けます。

function coin() {
  return (Math.random()*2 >= 1.0);
}

function dice() {
  return Math.floor(Math.random()*dice.MAX);
}
dice.MAX = 10;

制御構造の構文であるchooseとrepeatも高階関数として書けます。

function choose(func1, func2) {
 if (coin()) {
  func1();
 } else {
  func2()
 }
}

function repeat(func) {
 var n = dice();
 for (var i = 0; i < n; i++) {
  func()
 }
}

JavaScript インタプリタ Rhinoで実行してみると：

js> choose(function(){print("a")}, function(){print("b")})
a
js> choose(function(){print("a")}, function(){print("b")})
a
js> choose(function(){print("a")}, function(){print("b")})
b
js> repeat(function(){print("a")})
a
a
a
a
a
a
a
a
js> repeat(function(){print("a")})
a
js> repeat(function(){print("a")})
js>

正規表現は非決定性プログラムに対応する

a (b | c)* d d* という正規表現を考えましょう。空白は単なる区切りとして無視することにします。「|」は非決定性の選択、「*」は非決定性の繰り返しですね。この正規表現に対応する非決定性のプログラムは：

a
repeat
  choose
     b
  or
     c
  end
end
d
repeat
  d
end

JavaScriptなら：

function a() {print("a");}
function b() {print("b");}
function c() {print("c");}
function d() {print("d");}

function expr() {
 a(); // a
 repeat(function(){choose(b, c)}); // (b | c)*
 d(); // d
 repeat(d); // d*
}

実行してみます。

js> expr()
a
c
b
b
b
d
d
d
js> expr()
a
b
d
d
d
d
js> expr()
a
d
d
d
d
d
d
d
d
js>

関数expr()の出力は、正規表現 a (b | c)* d d* にマッチする文字列です。実際には、dice()が0から9までの値に制限されているので、a (b | c){0-9} d d{0-9} のパターンしか出てこないのですが、この制約を外した理論的／理想的な状況では、

関数expr()を無限回実行すれば、正規表現 a (b | c)* d d* にマッチするすべての文字列が得られる

はずです。

どうでしょう、非決定性のプログラミング／実行の感じがつかめたでしょうか。