ボンジュール・マドモアゼル

本サイトの情報は自己責任にてご利用下さい。

[Prologの技芸] Prologの技芸 読解メモ

 
第5章
論理プログラミングの理論

109ページ
第3章で紹介したように、型は項の集合である。その集合が代入例関係のもとで閉じていれば、その型は完備(complete)であるという。

ここでいう代入例関係とは、108ページでいう領域(domain)のことだと考えられる。
領域(domain)は、代入例という関係について閉じた、必ずしも基底的ではないゴールの集合である。すなわち、ゴール A が領域 D に含まれ、かつ A' が A の代入例であるならば、 A' も D に含まれる。


不完備な型 IT とは、 T に含まれる代入例と T に含まれない代入例を共に持つ項の集合のことである。
言い換えると、型 T に対して、ある項 A の、代入例 Aθ1 が T に含まれ、代入例 Aθ2 が T に含まれない場合、項 A は不完備である。

不完備自然数は、変数 X, あるいは、 sn(X)という形をした項である。
変数 X は、自然数 s(0) と、非自然数 a を代入例として持つ。同じように sn(X) は、自然数 s(0) と、非自然数 s(a) を代入例として持つ。

あるリストが完備であるためには、そのすべての代入例がプログラム3.11を満足すればよい。プログラム3.11を満足する代入例と共に、満足しない代入例があるならば、そのリストは不完備である。[...] これに対して、 [a,b|Xs] は不完備である。

[a,b|Xs] は、[a,b|[]] というプログラム3.11を満足する代入例を持つが、一方で、プログラム3.11 を満足しない [a,b|c] = .(a,.(b, c))という代入例を持つ。 [a,b|c] は、空リストで終わらない為、プログラム3.11 を満足しない。


第9章
構造探査

173ページ
図9.1 の型述語は、それぞれ、あたかも次のような無限にある事実の表で定義されているかのように動作する。すなわち、整数の表: integer(0), integer(1), integer(-1), …; プログラムの中のアトムの表: atom(foo), atom(bar), …;変数引数を持つプログラムの中の関数記号の表: compound(father(X,Y)), compound(son(X,Y)),…である。

178ページ
関数子述語も、型述語と同じように、引数の数が N の関数子 f の1つ1つについて、 functor(f(X1,…XN),f,N)という形をした事実からなる表として定義される。functor(father(X,Y),father,2), functor(son(X,Y),son,2),…がその例である。

179ページ
述語argも、また、無限の事実の表が存在するかのように定義される。その表の一部を次に示す。
    arg(1,father(X,Y),X).    arg(2,father(X,Y),Y).

arg(1,son(X,Y),X). …

これらは、つまり、述語 integer(X), atom(X), constant(X), compound(X), functor(Term,F,Arity), arg(N,Term,Arg) が一階論理の述語だと言っている。


第10章
メタ論理述語

196ページ
not_occurs_in の定義は、基底項だけに制約されていない。プログラム9.2の subterm の制約を取り除くのは、これほど簡単ではない。

(中略)

プログラム9.2で定義した subterm が正しく動作するのは、基底項についてだけである。しかしながら、プログラム10.6の not_occurs_in の定義のように、メタ論理テストを付け加えることにより、この問題点は容易に改善される。
どっちやねん。
ちなみに原文は、
10.2 Comparing Nonground Terms
P.181
Note that the definition of not_occurs_in is not restricted to ground terms. Lifting the restriction on Program 9.2 for subterm is not as easy. Consider the query subterm(X,Y)?. This would succeed using Program 9.2 instantiating X to Y.
[...]
P.182
As Defined, subterm works properly only for ground terms. However, by adding meta-logical type tests, as in the definition of not_occurs_in in Program 10.6, this problem is easily rectified.

The Art of Prolog 2nd

[Prologの技芸] Prologの技芸 水差し問題

 
Solutions to the jug problem can be found by filling one of the jugs whenever possible, emptying the other whenever possible, and otherwise transferring the contents of the jug being filled to the jug being emptied. Thus instead of six moves only three need be specified,
The Art of Prolog Second Edition

水差し問題の解は、一方の水差しを満たすことができればそれを満たし、もう一方の水差しを空にすることができればそれを空にし、そうでなければ、満たされた水差しの水を空にした水差しに移すことによって求められる。したがって、6つの指手に代わって3つの指手を記述するだけでよく、
Prologの技芸 初版3刷

水差し問題については、
Puzzle DE Programming
水差し問題
http://www.geocities.jp/m_hiroi/puzzle/water_jug.html
がとても参考になる。

『Prologの技芸』で言われる3つ指手の版を書いてみた。
% ?- test_dfs(jugs,Solution).
solve_dfs(State,History,[]):-
    final_state(State).
solve_dfs(State,History,[Move|Moves]):-
    move(State,Move),
    update(State,Move,State1),
    legal(State1),
    \+member(State1,History),
    solve_dfs(State1,[State1|History],Moves).
test_dfs(Problem,Moves):-
     initial_state(Problem,State),solve_dfs(State,[State],Moves),!.

initial_state(jugs,jugs(0,0)).
final_state(jugs(4,V2)).
final_state(jugs(V1,4)).

move(jugs(0,V2),fill(1)).
move(jugs(V1,V2),empty(2)):- V1 = 0, capacity(2,V2).
move(jugs(V1,V2),transfer(1,2)):- V1 = 0, capacity(2,C2),V2 < C2.

update(jugs(V1,V2),fill(1),jugs(C1,V2)):-capacity(1,C1).
update(jugs(V1,V2),empty(2),jugs(V1,0)).
update(jugs(V1,V2),transfer(1,2),jugs(W1,W2)):-
    capacity(2,C2),
    Liquid is V1 + V2,
    Excess is Liquid - C2,
    adjust(Liquid,Excess,W2,W1).

adjust(Liquid,Excess,Liquid,0):- Excess =< 0.
adjust(Liquid,Excess,V,Excess):-
    Excess > 0, V is Liquid - Excess.

legal(jugs(V1,V2)).

capacity(1,8).
capacity(2,5).

高度な指手 fill_and_transfer バージョン
% ?- test_dfs(jugs,Solution).
solve_dfs(State,History,[]):-
    final_state(State).
solve_dfs(State,History,[Move|Moves]):-
    move(State,Move),
    update(State,Move,State1),
    legal(State1),
    \+member(State1,History),
    solve_dfs(State1,[State1|History],Moves).
test_dfs(Problem,Moves):-
     initial_state(Problem,State),solve_dfs(State,[State],Moves),!.

initial_state(jugs,jugs(0,0)).
final_state(jugs(4,V2)).
final_state(jugs(V1,4)).

move(jugs(V1,V2),fill_and_transfer(1)).

update(jugs(V1,V2),fill_and_transfer(1),jugs(0,V)):-
    capacity(1,C1),
    capacity(2,C2),
    C1 > C2,
    V is (C1 + V2) mod C2.

legal(jugs(V1,V2)).

capacity(1,8).
capacity(2,5).

どちらも最適解は出ません。あしからず。

[Prologの技芸] Prologの技芸 正誤表

 
Prologの技芸 初版3刷 の誤植,誤記につき。
原著(初版)の誤記かもしれない。
なお、Prologの技芸は、The Art of Prolog の初版を訳しているが、
以下、英語版として参照しているのは、The Art of Prolog 2nd.

65ページ
図3.5: リスト反転の証明木
reverse([a,b,c,d],[d,c,b,a])

|
reverse([a,b,c,d],[],[b,c,d,a d,c,b,a])
|
reverse([b,c,d],[a],[d,c,b,a])
|
reverse([c,d],[b,a],[d,c,b,a])
|
reverse([d],[c,b,a],[d,c,b,a])
|
reverse([],[d,c,b,a],[d,c,b,a])


90ページ
S が変数で、 T が S を含まない項である場合には、次のような処理が行われる。スタック中に現れる S をすべて捜し出し、それを T で置き換える。同様に θ 中のすべての S をT に置き換える。そして代入 S = T を θ に付け加える。

If S is a variable, and T is a term not containing S, the following happens. The stack is searched for all occurrences of S, which are replaced by T. Similarly, all occurrences of S in θ are replaced by T. Then the substitution S = T is added to θ.

105ページ
ハーブランド空間(Herbrand universe) → エルブラン領域
ハーブランド基底(Herbrand base) → エルブラン基底

185ページ
プログラム9.5a: 項に対応するリストの構築
Term =.. List:-

List は、Term の関数子と、その後ろに Term の引数を連ねたも
のからなるリストである。
Term =..[F|Args]):-
functor(Term,F,N), args(0,N,Term,Args).
args(I,N,Term,Arg,Args[Arg|Args]):-
I<N,I1:=I+1,arg(I1,Term,Arg),args(I1,N,Term,Args).
args(N,N,Term,[]).


219ページ
プログラム11.6 11.5の交換ソートについて考えてみよう。

372ページ
move(jugs(V1,V2),fill_and_transfer(1)).


update(jugs(V1,V2),fill_and_transfer(1),jugs(0,V)):-
capacity(1,C1),
capacity(2,C2),
C1 > C2,
V is (C1 + C2 V2) mod C2.

384ページ
プログラム18.10: ミニマックス・アルゴリズムによる最良な指手の選択
evaluate_and_choose([Move|Moves],Position,D,MaxMin,Record,Best) :-

move(Move,Position,Position1),
minimax(D,Position1,MaxMin,MoveX,Value),
update(Move,Value,Record,Record1),
evaluate_and_choose(Moves,Position,D,MaxMin,Record1,Best).
evaluate_and_choose([],Position,D,MaxMin,(Move,Value),Value (Move,Value)).


456ページ
銀行のデータ:担保の分類
     collateral(local_currency_deposits,first_class).

collateral(foreign_currency_deposits,first_class).
collateral(negotiate_instruments,second_class).
collateral(mortgage,unliquid illiquid).


おまけ(誤植ではないが)
444ページ
プログラム20.3:(続き)

extend_move(Stones,M,Board,[]) :-
Stones == ( 7-M ) mod 13, !.
extend_move(Stones,M,Board,Ms) :-
Stones =:= ( 7-M ) mod 13, !,
distribute_stones(Stones,M,Board,Board1),
move(Board1,Ms).



以下補足

1.4 存在限量質問
次に導入する演繹規則は、汎化(generalization)である。これは、存在限量質問 P? が任意の代入 θ について、その代入例 Pθ の論理的帰結であるという規則である。

An existential query P is a logical consequence of an instance of it, Pθ ,for any substitution θ.

もっと、簡潔に訳すと、
汎化とは、存在限量質問 P? は、任意の代入例 Pθ の論理的帰結であるという規則である。
言い換えれば、任意の代入例 Pθ から、存在限量質問 P? を帰結することを汎化という。