Prolog での乱数

そんなわけで (どんなわけで?),さっそく乱数の話題.
先のまとめで書いたように,写経していて一番激しく落胆したのが乱数を生成する次の述語です.

random(Min, Max, Num) :-
	integer(Min),
	integer(Max),
	Min =< Max,
	retract(seed(S)),
	Num is S mod (Max - Min + 1) + Min,
	NewSeed is (125 * S +1) mod 4096,
	asserta(seed(NewSeed)), !.
seed(7).

これがひどいのは,乱数の元になる種を述語として Prolog データベースに登録していることです.
要するに,Prolog データベースをグローバル変数として使っているというわけ.
をいをい,Prolog って副作用のある,破壊的代入はできないんじゃなかったのかい!?
ましてやグローバル変数とは.
本当に本当に,許し難いくらいひどいコードだと思いましたよ.

オブジェクト指向っぽく

そんなわけで (どんなわけで?),もうちょっとマシに乱数を扱えないか考えてみました.
まず,乱数の何が課題かというと,これはいわゆる関数のように決まった値を返すわけではない,というところですね.
Prolog の場合は関数じゃないので言い換えると,一つの事実に定まらない,というべきか.
そこで Prolog データベースに次々と変わる種を憶えているわけです.


これが Java なんかだと,種をインスタンスの状態として保持することができるので,全く問題ないわけです.
まぁ,これは副作用を普通に使えるからですが.
んで,まずはこれを Prolog でまねできないか考えてみます.
基本的に副作用のない Prolog なので,値が次々に変化するインスタンス変数というのは使えませんが,代わりに,新しいインスタンスを返すことならできます.
これは「オブジェクト指向入門 (isbn:4756100503)」でスタックを抽象データ型として扱う際に使われていた手法です.
身近なところだと,JavaBigDecimal なんかがそうですね.
BigDecimal は他のインスタンスと加算したり減算したりすることができますが,その際には新しいインスタンスが返されます.

BigDecimal result = foo.add(bar).

こういうやり方であれば,Prolog でも十分表現できるはず.
んで,こうなりました.

random_create(Seed, Min, Max, Value, Next) :-
	random_next(rand(Seed, Min, Max), Value, Next).

random_next(rand(Seed, Min, Max), Value, Next) :-
	Value is Seed mod (Max - Min + 1) + Min,
	NewSeed is (125 * Seed + 1) mod 4096,
	Next = rand(NewSeed, Min, Max).

種と上限・下限をインスタンス変数のように rand/3 に保持します.
そのコンストラクタに相当するのが random_create/4.第 4 引数で作成したインスタンス (rand/3) を返します.
そして random_next/3 は第 1 引数で与えたインスタンスから新たな乱数を生成して第 2 引数に,そして次の乱数を生成するためのインスタンスを第 3 引数に返します.
写経本では 1〜100 までの乱数を生成して,77 が出てくるまで繰り返すのが使用例でしたが,同じことをこれでやるとこんな感じ.

random_test(Seed) :-
	random_create(Seed, 1, 100, Value, Next),
	random_print(Value, Next).

random_print(77, _) :- !,
	write(77), nl.
random_print(Value, Rand) :-
	write(Value), nl,
	random_next(Rand, Value1, Next),
	random_print(Value1, Next).

無限リストで

他に手はないかなということで,同じく副作用のない Haskell ではどうするのかぐぐってみたりしたら (本は積みっぱなし),どうやら遅延評価で無限の長さを持つリストを生み出すらしい.なるほど...
そういえば,並列論理型言語である KL1 や GHC (Guarded Horn Clauses,Haskellコンパイラじゃないよ) でも無限長のリストを活用するみたい.
つまり,遅延評価か並列のどちらかがあれば無限長のリストが使えるようなのですが,Prolog は少なくとも並列言語ではないはず.
そこで遅延評価を探したら,ありましたよ.「Prolog 入門 (isbn:4274073084)」に説明があって,freeze/2 という述語があるとのこと.
それを SWI-Prolog でも使えるか探してみたら,さらにそれを一般化した when/2 という述語がありました.
これを使うと,ある変数が具体化されたときに実行される述語を登録することができるようです.
どこに登録されるかというと,その変数自身.結局副作用? (^^;
まぁいいや,とりあえず使ってみました.こうなりました.

random_create(Seed, Min, Max, [Value | Rest]) :-
	Value is Seed mod (Max - Min + 1) + Min,
	NewSeed is (125 * Seed + 1) mod 4096,
	when(nonvar(Rest), random_create(NewSeed, Min, Max, Rest)).

random_next(List) :-
	List = [_ | _].

random_create/4 に種の初期値と上限・下限を与えると,リストを返します.
このリストの car (Value) は乱数に具体化されていますが,cdr (Rest) は具体化されていない変数です.
その具体化されていない変数 Value には when/2 を使ってこの述語自身を遅延評価するようにしています.
つまり,リストの cdr が具体化されると,その car が新たな乱数になると同時に cdr が具体化された際にまたまたこの述語が遅延評価されるように設定されます.
ちょっと面白いのは,最初に random_create/4 を呼び出したときの第 1〜3 引数が,その呼び出しが終わった後もずっと使われ続けること.一種のクロージャ? これもじっくり考えてみると面白いかも〜.
んで,リストの cdr を具体化するのが random_next/1.これが必要なのがちょっと残念.
この程度なら述語を用意しなくてもいいかとも思ったのですが,それもどうかということで.
本当は,変数が具体化された時じゃなくて,参照されたときに述語が呼び出されると最高なんですけどね.残念!!
ともあれ,無限リスト版の使用例.

random_test(Seed) :-
	random_create(Seed, 1, 100, L),
	random_print(L).

random_print([77 | _]) :- !,
	write(77), nl.
random_print([Value | Rest]) :-
	write(Value), nl,
	random_next(Rest),
	random_print(Rest).

ちょっとすっきり♪

データ駆動だ

さらに,GHC や KL1 を調べていたら,並列に実行する戦略として「データ駆動」と「要求駆動」というのが出てきました.
これらはデータを生成するプロセスと消費するプロセスをどのように同期させるかに関するものです.
「データ駆動」では,データを生成するプロセスが消費するプロセスを駆動します.
「要求駆動」では,データを消費するプロセスが生成するプロセスを駆動します.
ふむ.
上で試した二つの方法は,いずれも「要求駆動」と言えそうです.乱数を消費する側が生成する側を呼び出しているので.
そんなわけで (どんなわけで?),「データ駆動」っぽいやり方も試してみましょう.
つまり,乱数を生成する述語が乱数を消費する述語をコールバックすればいいわけですね.
こうなりました.

random_create(Seed, Min, Max, F) :-
	random_next(Seed, Min, Max, F, _).

random_next(_, _, _, _, End) :-
	nonvar(End), !.
random_next(Seed, Min, Max, F, _) :-
	Value is Seed mod (Max - Min + 1) + Min,
	P =.. [F, Value, End],
	P,
	NewSeed is (125 * Seed + 1) mod 4096,
	random_next(NewSeed, Min, Max, F, End).

random_create/4 は,種の初期値に上限・下限,そして乱数を消費する 2 引数の述語の名前を受け取ります.
乱数を消費する述語の引数は乱数と終了フラグ.終了フラグを具体化して返すと乱数の生成は終了します.
そんなわけで (どんなわけで?),使用例.

random_test(Seed) :-
	random_create(Seed, 1, 100, random_print).

random_print(77, End) :- !,
	write(77), nl,
	End = true.
random_print(Value, _) :-
	write(Value), nl.

かなりすっきり♪


いろいろなやり方がありますね.