DCPDCP DCP
8.3 変換例
例として、N-Queen問題を解くプログラムを以下に示す．
% メインモジュール (オリジナル)
:- module main.
main :- N = 8,
klicio:klicio([stdout(normal(Out))]),
util:times(UserTime), go(N,UserTime,Out).
go(N,UserTime,Out)
:-count(Result,0,UserTime,Out),
queen(N,Result) @ lower_priority.
queen(N,Result) :- queen:queen(N,Result) @ fault_tolerant.
count([A|X],K,UT,Out) :- count(X,~(K+1),UT,Out).
count([] ,K,UT,Out)
:-util:times(UT1), Out = [putt([~(UT1-UT),K]),nl].
メインモジュールでは、util:times(UserTime)で開始時間を計り、
N-Queenプログラムutil:queen:queen(N,Result)をフォールトトレラント実行するよう に指定している．得られた結果は、count(Result,0,UserTime)で個数だけ調べ、調べ終っ たところで終了時間を測定している．klicioは、入出力ストリームを獲得する述語である．
上の例では標準出力ストリームOutをとり、出力メッセージを送って画面出力させている．
~(K+1)はマクロ表記であり、演算結果と置き換わる．
N-Queen問題を解くモジュールは、以下のようになる．
% N-Queenモジュール (オリジナル)
:- module queen.
queen(4,X) :- queen([1,2,3,4],[],[],X).
...
queen(8,X) :- queen([1,2,3,4,5,6,7,8],[],[],X).
queen([P|U],C, L,I):- % clause 1
merge(I1,I2,I), append(U,C,N),
c1(P,1,N,L,L,I1) @ node, % goal 1
queen(U,[P|C],L,I2). % goal 2
queen([],[_|_],_,I):- I=[]. % clause 2
queen([],[], L,I):- I=[L]. % clause 3
c1(T,D,N,[P|R],B,I):- T=\= P+D, T=\=P-D, D1:=D+1|
c1(T,D1,N,R,B,I).
c1(T,D,N,[P|_],B,I):- T=:=P+D | I=[].
c1(T,D,N,[P|_],B,I):- T=:=P-D | I=[].
c1(T,D,N,[], B,I):- queen(N,[],[T|B],I).
append([A|X],Y,Z):- Z=[A|Z1], append(X,Y,Z1).
append([], Y,Z):- Z=Y.
merge([X|I1],I2,I) :- I = [X|IT], merge(I1,I2,IT).
merge(I1,[X|I2],I) :- I = [X|IT], merge(I1,I2,IT).
merge([],I2, I) :- I = I2.
merge(I1,[], I) :- I = I1.
上のプログラムは、リスト位置とその数値でqueenを置いたチェス盤面の位置を表す．リ ストの位置を盤面の行とすれば、初期値として与えたリストが[1,2,3,4,5,6,7,8]のよう に値が重複しない数値とされているのは、同じ列にqueenは2つ置けないことを反映する．
clause 1に始まる述語定義では、第三引数にこれまで置いたqueen を逆順に置き、この
盤面に対して次の行に置けなかった列の位置を第二引数に記録する．第一引数には、次の 行での候補の列位置がある．clause 3 は、次の行の候補列位置が無くなり、かつ置けな かった行位置もないなら、これまで置いたqueenの盤情報を一つの解として第四引数に返 させることを示す．clause 2は逆に、queenが置ききれず解が見つからなかったことを示 す． は、これまで を置いてきた盤面 に対して、次の行の列 に置いた場
合goal 1と、次の行についてP以外の残りの候補で試すゴールgoal 2 の二つの部分問題 に分割している． 各部分問題の解は、マージされて一つにされる．clause 1では、Pに 置いた場合について、別ノードで実行するように指定している．
このプログラムを耐故障変換すると、以下のようになる．
% N-Queenモジュール (FTS)
:- module queen.
queen(N,X)
:-watchdog:fork(Primary,Backup),
queen_1({N,X},Primary,Backup) @ lower_priority(10).
フォールトトレラント実行の始めに、監視プロセスを各ノードに生成する．監視プロセ スは、PSG、BSGそれぞれのノードでリングネットワークを構成し、代表する監視プロセ スへのストリームがそれぞれ返される．
監視プロセスをノード内で最高優先度で動作させるために、その他のプロセスは低い優 先度に指定する．
queen_1(Args,Primary,Backup)
:-copy:replicate(Args,Args1,Args2,ToAbt),
ToAbt = {Abt1,Abt2}, Log = ack(Log1),
Primary = {primary,queen,queen,Args1,Log,ToBackup,Abt1},
Backup = {backup ,queen,queen,Args2,Log1,ToBackup,Abt2}.
オリジナルゴールの引数の複製を作り、PSGと BSGにそれぞれ送る．
次のように、Record Version、Replay Versionそれぞれの述語定義を展開する．それぞ れの述語には、ログ用の変数の他に、監視プロセスとのコミュニケーション用に2 変数
(Sig,Raise)が、終了判定のショートサーキット用に2変数(引数対SC)が追加される．
ゴールを別ノードへ送る部分は、ゴールを監視用プロセスへ送るユニフィケーションに 置き変わる．
また、FTRepVでは、監視用プロセスからのコマンドrebirthによって、FTRecVに置 き換わるためのクローズが追加される．このクローズは、すでにPSG で生成されたログ 情報を消費し終る必要があるので、alternativelyを用いて優先度を低くしてある．
queen_record([1,2,3,4],[],[],X,Log,Sig,Raise)-SC.
...
% FT Record Version
queen_record([P|U],C, L,I,ack(Log),Sig,Raise)-SC
:-Log = c1(L1,L2,L3),
Raise = {Raise1,Raise2},
merge_record(I1,I2,I,L1,Sig)-SC,
append(U,C,N)-SC,
Raise1 = [goal(primary,queen,c1,{P,1,N,L,L,I1},L2)],
queen_record(U,[P|C],L,I2,L3,Sig,Raise2)-SC.
queen_record([],[_|_],_,I,ack(Log),Sig,Raise)-SC
:-Log=c2(Ack), output(Ack,[I|Raise],[[]])-SC.
output(Ack,X,Y)-SC :- wait(Ack) | X = Y.
...
% FT Replay Version
queen_replay(A, B, Log,Sig,Raise)-SC
:-(wait(Log) -> queen_replay_1(A, B, Log,Sig,Raise)-SC ;
alternatively;
Sig = [rebirth|Sig1] -> queen_record(A, B, _,Sig1,Raise)-SC).
queen_replay_1(4,B,Log,Sig,Raise)-SC
:-queen_replay([1,2,3,4],[],[],B,Log,Sig,Raise)-SC.
...
queen_replay(A,B,C,D,Log,Sig,Raise)-SC
:-(wait(Log) -> queen_replay_1(A,B,C,D,Log,Sig,Raise)-SC ;
alternatively;
Sig = [rebirth|Sig1] -> queen_record(A,B,C,D,_,Sig1,Raise)-SC).
queen_replay_1([P|U],C, L,I,Log,Sig,Raise)-SC
:-Log = c1(L1,L2,L3) |
L1 = ack(Log1), L2 = ack(Log2), L3 = ack(Log3),
Raise = {Raise1,Raise2},
merge_replay(I1,I2,I,L1,Sig)-SC,
append(U,C,N)-SC,
Raise1 = [goal(backup,queen,c1,{P,1,N,L,L,I1},L2)],
queen_replay(U,[P|C],L,I2,L3,Sig,Raise2)-SC.
...
外部呼出し述語は以下のモジュールで定義される．これらは、監視プロセスが別ノード から投げられたユーザゴールを実行させるのに必要とされる．
% 外部呼出しモジュール (FTS)
:- module exgoal.
call_goal(Site,Module,Predicate,Args,Log,GSig,Raise)-SC
:-call_goal_0(Site,Module,Predicate,Args,Log,
GSig,Raise)-SC @ lower_priority.
call_goal_0(primary,queen,c1,{A,B,C,D,E,F},Log,GSig,Raise)-SC
:-queen:c1_record(A,B,C,D,E,F,Log,GSig,Raise)-SC.
call_goal_0(backup, queen,c1,{A,B,C,D,E,F},Log,GSig,Raise)-SC
:-queen:c1_replay(A,B,C,D,E,F,Log,GSig,Raise)-SC.
...