続 Prolog で FizzBuzz
コメントでご指摘いただいたとおり,前に書いた Prlog 版 FizzBuzz は最初の (っていうか唯一の) 解を見つけた後,別の解を探しに行くと無限ループというかスタックオーバーフローになります.
心より恥じる.
全解探索するつもりが毛頭なかったのですっかり油断してました.
そんなわけで (どんなわけで?),修正版.
fizzbuzz(N, L) :- fizzbuzz(N, L, []). fizzbuzz(0, L, L) :- !. fizzbuzz(N, L, D) :- M3 is N mod 3, M5 is N mod 5, fizzbuzz(N, M3, M5, V), N1 is N - 1, fizzbuzz(N1, L, [V | D]). fizzbuzz(_, 0, 0, 'FizzBuzz') :- !. fizzbuzz(_, 0, M5, 'Fizz') :- !. fizzbuzz(_, M3, 0, 'Buzz') :- !. fizzbuzz(N, M3, M5, N).
微妙にやり方変えてますが気にしない気にしない.
ご指摘頂いたように最初の節にカットを付けても実用上問題はないというか,むしろ一番効率的なのですが,本来必要なのは下請けの (節が複数ある) 述語なんですよね.
例えば
fizzbuzz(0, L, L) :- !.
ここのカットがないと,停止条件が停止条件として機能せず,第 1 引数が 0 の場合でもバックトラックによって 2 番目の節が呼び出されてしまいます.
んで,その第 1 引数が 0 から始まって -1,-2,-3... という具合に再帰呼び出しされてしまった次第.
Prolog で複数の節を並べた場合って,Java なんかでいうところの
if (a) { ... } else if (b) { ... } else if (c) { ... }
のように見えちゃいますが,バックトラックを含めて考えると
if (a) { ... } if (b) { ... } if (c) { ... }
なんですよね.
そこで必要ならカットを付けて else if
相当にしなきゃいけない,と.
でもでも,明示的に条件を付けてやれば,つまり
if (a) { ... } if (!a && b) { ... } if (!a && !b && c) { ... }
のようにしてあげればカットは必要ないはず (効率の問題は置いておくテスト).
そんなわけで (どんなわけで?),こうなりました.
fizzbuzz(N, L) :- fizzbuzz(N, L, []). fizzbuzz(0, L, L). fizzbuzz(N, L, D) :- N > 0, M3 is N mod 3, M5 is N mod 5, fizzbuzz(N, M3, M5, V), N1 is N - 1, fizzbuzz(N1, L, [V | D]). fizzbuzz(_, 0, 0, 'FizzBuzz'). fizzbuzz(_, 0, M5, 'Fizz') :- M5 =\= 0. fizzbuzz(_, M3, 0, 'Buzz') :- M3 =\= 0. fizzbuzz(N, M3, M5, N) :- M3 =\= 0, M5 =\= 0.
で,ですね.
カットを排除するのって,何気に GHC/KL1 にする (つまり並列化する) のとほとんど同じなんですねぇ.
なので,カット排除版を GHC/KL1 にするのは超簡単.
fizzbuzz(N, L) :- true | fizzbuzz(N, L, []). fizzbuzz(0, L, D) :- true | D = L. fizzbuzz(N, L, D) :- N > 0 | M3 is N mod 3, M5 is N mod 5, fizzbuzz(N, M3, M5, V), N1 is N - 1, fizzbuzz(N1, L, [V | D]). fizzbuzz(_, 0, 0, V) :- true | V = 'FizzBuzz'. fizzbuzz(_, 0, M5, V) :- M5 =\= 0 | V = 'Fizz'. fizzbuzz(_, M3, 0, V) :- M3 =\= 0 | V = 'Buzz'. fizzbuzz(N, M3, M5, V) :- M3 =\= 0, M5 =\= 0 | V = N.
前回以上に Prolog 版とそっくり (動かしてないからアレだけどたぶんこんなもん).
ちなみに '|' を ',' に置換すれば Prolog として実行できます.
前回書いたように剰余を求めるのに 10 秒かかる環境を仮定すると,今回のコードは Prolog (逐次) 版では約 2000 秒ほどかかるはずですが,GHC/KL1 (並行) 版だと 200 CPU というか 200 SMT (Simultaneous Multi-Threading) では約 10 秒ほどになる可能性あり.
まぁ,現実は剰余を求めるコストより並列に実行するコストの方が遥かに高くついたりして意味のない話なんですが.
ともあれ (JW),GHC/KL1 で書いたプログラムをバリバリ並列に実行できる環境が欲しい今日この頃なのであります.