はじめに
中島秀之先生のProlog/KRには多重世界機構がありました。中島先生の実装はLisp上のものでした。同様なものをエジンバラPrologの機能を使って実装するということについて再度取り組みました。再度と言いますのは、以前にも取り組んだことがあったからです。このときは理解が浅く実装も中途半端なものでした。この度、動作を正確にし自作の処理系N-Prologに多重世界機構を組み込みました。
Prolog/KRにおける多重世界機構
Prolog/KRはLispベースで作られておりS式で表現されます。withという述語が用意されています。
(with w1 (assert (bird canary))
(with w1 (assert (bird penguin))
(with w2 (assert (fly *x) (bird *x)))
(with w3 (assert (deny (fly penguin))))
質問をするときにはwithをネストさせて動的に多重世界を形成します。その状況で質問がなりたつかどうかを計算します。
(with w1 (with w2 (with w3 (fly canary)))). -> yes
(with w1 (with w2 (with w3 (fly penguin)))). -> no
一般的に鳥は飛ぶことができます。しかし例外もありペンギンは飛ぶことはできません。このような知識を表現するのに多重世界機構が優れています。
エジンバラPrologでの表現
次のように表現することとしました。
with(w1,assertz(bird(canary))).
with(w1,assertz(bird(penguin))).
with(w2,assertz((fly(X) :- bird(X))))
with(w3,assertz(deny(fly(penguin)))).
-? with(w1,with(w2,with(w3,fly(canary)))). -> yes
^? with(w1,with(w2,with(w3,fly(penguin)))). -> no
実装方法
with/2述語の機能は３つに分かれます。
（１）assertzによって節を登録すること
（２）denyによって否定を登録すること
（３）質問の述語を実行すること
登録される述語や節は次の形式とします。
（１）述語 bird(w1,canary).
（２）節 fly(w2,X) :- bird(w2,X).
（３）否定 deny(fly(w3,penguin)).
第１項をその属するワールドを表すアトムとします。
with(W,assertz(X)) :-
add_world(X,W,Y),
assertz(Y).
with(W,deny(X)) :-
add_world(X,W,Y),
assertz(deny(Y)).
with(W,with(X,Y)) :-
with1(with(X,Y),[W]).
with(W,X) :-
add_world(X,W,X1),!,
call_with(X1,[W]).
with1(with(W,X),L) :-
with1(X,[W|L]).
with1(X,[L|L1]) :-
add_world(X,L,X1),!,
call_with(X1,[L|L1]).
with/2はワールドがネストしない場合には単独で、ネストする場合にはwith1/2の補助述語を使って再帰的に処理をしていきます。
add_world/3は述語あるいは節の第１項にワールドを追加するものです。
add_world(bird(canary),w1,X). とすればXにはbird(w1,canary) がユニファイされます。
add_world((fly(X) :- bird(X)),w2,X). とすればxにはfly(w2,X) :- bird(w2,X)がユニファイされます。
これにより変換されたものをPrologの述語あるいは節として登録します。
add_world/3の詳細は下記の通りです。ユーザー定義の述語のみ、第１項にワールドを追加します。組込み述語である場合には変換せずそのままです。
% if predicate X is built_in predicate, not add world.
add_world(X,W,X) :-
predicate_property(X,built_in).
% if predicate X is user_defined predicate add world.
add_world(X,W,Y) :-
predicate_property(X,dynamic),
X =.. X1,
add_world1(X1,W,L),
Y =.. L.
% if 1st argument is clause, add world to head and body.
add_world((H :- B),W,(H1 :- B1)) :-
add_world(H,W,H1),
add_world_body(B,W,B1).
% if 1st argument is conjunction add world to each predicate.
add_world((B1,B2),W,(C1,C2)) :-
add_world1(B1,W,C1),
add_world(B2,W,C2).
% if 1st argument is disjunction add world to each predicate.
add_world((B1;B2),W,(C1;C2)) :-
add_world1(B1,W,C2),
add_world(B2,W,C2).
% base of conjunction or disjunction.
add_world(P,W,P1) :-
P =.. L,
add_world1(L,W,L1),
P1 =.. L1.
% add world to listed predicate.
add_world1([L|Ls],W,[L,W|Ls]).
% add varialbe world to conjunction body
add_world_body((B1,B2),W,(C1,C2)) :-
add_world(B1,W,C1),
add_world_body(B2,W,C2).
% add variable world to disjunction body
add_world_body((B1;B2),W,(C1;C2)) :-
add_world(B1,W,C1),
add_world_body(B2,W,C2).
% base of body
add_world_body(B,W,C) :-
add_world(B,W,C).
次に質問の述語を処理する仕組みについてです。call_with/2という述語が質問を担当します。
質問は2つの場合が考えられます。
（１）bird(canary)のように単独の述語である場合
（２）fly(X) :- bird(X)のように場合にfly(canary)を質問する場合
（１）（２）を区別するのにclause/2が使えます。clause(fly(X),Y) のようにするとYにはボディー部であるbird(X)がユニファイされます。clauseに与えられる第1項が述語の場合には第2項にはtrueがユニファイされることとなっています。これで区別をします。
与えられる述語にはワールドの情報が付加されています。これを変数に置き換えます。
bird(w1,canary)は=..述語をつかってbird(W,canary)に変換されます。これをclauseでユニファイするものを見つけます。上述の例ではbirdはw1ワールドで定義されています。W変数にはw1がユニファイされます。call_with/2は動的に構成された多重世界のリストを保持しています。もっとも内側の世界が先頭となるリスト（例えば[w3,w2,w1]）になっています。Wにユニファイされたワールドがこのリストのメンバーであることを確認できたらその述語は成功です。
fly(w2,canary)の場合にはclase/2を利用してヘッド部がユニファイするものを探しそのボディー部をさらにcall_with/2に回します。
以下同様に再帰的に処理していくことによりcall_with/2は多重世界機構において質問の真偽を調べます。なお、ボディー部に組込述語があった場合にはワールドは関係ありませんので、単純にcall/1を利用してProlog述語として実行します。
さらにボディー部は連言あるいは選言である場合がありますので、その場合についても記述しておきます。コードは下記のようになります。
%conjunction
call_with((X,Y),L) :-
call_with(X,L),
call_with(Y,L).
%disjunction
call_with((X;Y),L) :-
call_with(X,L).
call_with((X;Y),L) :-
call_with(Y,L).
% if X is built_in predicate, call X.
call_with(X,L) :-
predicate_property(X,built_in),
call(X).
% if X ls user_defined predicate and the 1st argument is member of world and deny, fail.
call_with(X,L) :-
predicate_property(X,dynamic),
X =.. [H,W|[A]],
X1 =.. [H,W1|[A]],
X2 =.. [deny,X1],
inner_world(W,L,L1),
clause(X2,true),
member(W1,L1),!,
fail.
% if X ls user_defined predicate and the 1st argument is member of world and X not has clause, call X.
call_with(X,L) :-
predicate_property(X,dynamic),
X =.. [H,W|[A]],
X1 =.. [H,W1|[A]],
inner_world(W,L,L1),
clause(X1,true),
member(W1,L1).
% if X ls user_defined predicate and the 1st argument is member of world and X is clause, call clause.
call_with(X,L) :-
predicate_property(X,dynamic),
X =.. [H,_|[A]],
X1 =.. [H,W|[A]],
clause(X1,Y),
Y \= true,
member(W,L),
call_with(Y,L).
% make inner world w.g. inner_world(w2,[w3,w2,w1],X). X is [w2,w1]
inner_world(W,[],[]).
inner_world(W,[W|Ls],[W|Ls]).
inner_world(W,[L|Ls],X) :-
inner_world(W,Ls,X).
% dummy data to avoid existance error.
deny(dummy).
なお、inner_world/3は質問実行中の述語が定義されたワールドと同じがその内側のワールドで成立していることを確認するためのものです。
終わりに
実装を作ってみたら案外とうまくできたように思えました。そこでお自作の処理系N-Prologに組込述語として組み入れています。ver1.94以後で多重世界機構が使えるようになっています。N-PrologはOSSです。1980年代のRUN\PROLOG互換なものです。N-PrologはGithubにおいてあります。
英語版のReddit/Prologに反応を確かめたくて投稿してみました。興味をもっていただけたようです。次のようなコメントをいただきました。
Nice! On first look, it appears that multiple worlds work similar to the module system in other Prologs, and this is the first time I've seen the 'DENY' predicate. I guess in systems without it, you would have to explicitly add a guard to fly/1 to test for not_fly(X) and have defined not_fly(penguin), or something similar :D.
私は以下のようにご返信しました。
Thank you for your interest. In the 1980s, Dr. Nakashima devised a multi-world mechanism to express hierarchical knowledge. He implemented it in Prolog/KR.
中島秀之先生の素晴らしいアイディアが若い人たちにも広く知られるとうれしいです。