AIMAをかじる

せっかく得たPrologの理解（イロハのイだが）もたぶんすぐに消えてしまう。今はまだ、日々ごりごりプログラムを書く状態じゃないから。

そうするとこれが消えないうちに、PrologとFOLとLispとをもうすこし繋いでおきたい。どうしたもんかなぁ、FOLを数理論理学の本できっちりやるのは、それはそれで時間がかかるしなぁ、と思案してたんだけど、これAIMA(Artificial Inteligence a Modern Approach)をやればいいじゃん！ということに気付いた。AIMAにはFOLについて簡潔にまとめた部分があるのです。PAIPやってて、Prologやったところだから、Norvigつながりもあって結構よい組み合わせではないか。

AIMAのFOLは8章と9章なんで、頭から読んでいるとPrologを忘れちゃう。そこで、思い切って7章からやろうと思う。7章から論理エージェントが初まる。

本を途中から読むということに慣れていないので、うまくいかないかもしれない。うまくいくかもしれない。チャレンジしてみよう。

こつこつ。

Allegro Prolog

以前はまったくわからんかったが、今はわかる！！

Allegro Prolog

LispとPrologとを多少連携して使えるみたい。

PAIPやりながらAllegro Prologもいじってみることにする。これは楽しみ。

CL-USER(2): (require :prolog)
; Fast loading /opt/acl81.64/code/prolog.002
;;; Installing prolog patch, version 2.
T
CL-USER(3): (use-package :prolog)
T
CL-USER(4): (?- (append ?x ?y (1 2 3)))
?X = ()
?Y = (1 2 3)
?X = (1)
?Y = (2 3)
?X = (1 2)
?Y = (3)
?X = (1 2 3)
?Y = ()
No.
CL-USER(5): (<-- (likes Kim Robin))
LIKES
CL-USER(6): (<- (likes Sandy Lee))
LIKES
CL-USER(7): (<- (likes Sandy Kim))
LIKES
CL-USER(8): (<- (likes Robin cats))
LIKES
CL-USER(9): (?- (likes Sandy ?x))
?X = LEE
?X = KIM
No.
CL-USER(10): 

12 Working With Files

* 12 Working With Files
** 1 Splitting Programs over Files
 - consult
  - [FileName]. (at top-level)
  - 実体はconsultという述語らしい。
  - ファイルの中で使うときは頭に:-をつけるようだ。
 - ensure_loaded
  - ensure_loaded([FileName]).は、読み込み済みで無
   変更なものは再読み込みしないようだ。
 - module
  - そのファイルをmoduleにする。
  - :- module(ModuleName,
              List_of_Predicates_to_be_Exported).
 - use_module
  - moduleを使う。
  - :- use_module(ModuleName).
  - importする述語の指定(制限)もできる。
  - :- use_module(ModuleName,
                  List_of_Predicates_to_be_imported).
 - library
  - 処理系にてライブラリとして定義されているもの
    を指定する。use_moduleとあわせて使う。
  - 例:
    :- use_module(library(lists)).

** 2 Writing to Files
 - streamがある。使い方はこんな感じ。

open('hoge.txt',wrie,Stream),
write(Stream,'This is hoge.',nl(Stream),
close(Stream).

** 3 Reading from Files
 - read/2
  - streamからPrologのtermsを読み込む。
  - streamが読むものがないとエラーになる。
 - at_end_of_stream/1
  - streamの終端の検知。
 - get_code/2
  - streamからcharacterをひとつ読む。

** 4 Exercise
 - Exercise 12.1.

main :-
    open('hogwarts.houses',write,Stream),
    tab(Stream,10),write(Stream,'glyffindor'),nl(Stream),
    tab(Stream,3),write(Stream,'hufflepuff'),tab(Stream,4),write(Stream,'ravenclaw'),nl(Stream),
    tab(Stream,10),write(Stream,'slytherin'),nl(Stream),
    close(Stream).

 - Exercise 12.2.

:- dynamic word/2.

main :-
        open('swipl-man.txt',read,S),
        doWords(S),
        close(S).

readWord(InStream,W) :-
        get_code(InStream,Char),
        checkCharAndReadRest(Char,Chars,InStream),
        atom_codes(W,Chars).

checkCharAndReadRest(10,[],_) :- !.
checkCharAndReadRest(32,[],_) :- !.
checkCharAndReadRest(-1,[],_) :- !.
checkCharAndReadRest(end_of_file,[],_) :- !.
checkCharAndReadRest(Char,[Char|Chars],InStream) :-
        get_code(InStream,NextChar),
        checkCharAndReadRest(NextChar,Chars,InStream).

doWords(InStream) :-
        \+ at_end_of_stream(InStream),
        readWord(InStream,W),
        writeWord(W),
        doWords(InStream).

writeWord(Word) :-
        Word \== '', memoize(Word).
writeWord('').

memoize(W) :-
        word(W,N),M is N+1,asserta(word(W,M)),retract(word(W,N)),!.
memoize(W) :- asserta(word(W,1)).
   
** 5 Practical Session
 - 今まで作ってきたものをモジュール化して統合。
 - モジュール名と、ファイル名の拡張子より前は、同
   じでないといけないみたい。
 - Step 2までにしておき、後は入出力の練習なので、
   割愛する。

読了！！！！
頭がくたくただ！

【LPN】10 Cuts and Negation [落葉拾い]

いずれも寝た後なら簡単だった。疲れたときにも頑張ることは、意味がないのかなぁ。

 - Exercise 10.4.

   うーん。むずかしい。cutは宣言的かつ手続き的なの
   で、慣れれば強力かもしれないが、慣れないと中途
   半端で考えにくい。特にunificationがどう効いてく
   るかが問題になると、自分で束縛管理した方が楽じゃ
   んと思えてしまう。
   
   ここは後日、再チャレンジ。

   一晩寝たら5分でできた。。。

directTrain(saarbruecken,dudweiler).
directTrain(dudweiler,saarbruecken).
directTrain(forbach,saarbruecken).
directTrain(saarbruecken,forbach).
directTrain(freyming,forbach).
directTrain(forbach,freyming).
directTrain(stAvold,freyming).
directTrain(freyming,stAvold).
directTrain(fahlquemont,stAvold).
directTrain(stAvold,fahlquemont).
directTrain(metz,fahlquemont).
directTrain(fahlquemont,metz).
directTrain(nancy,metz).
directTrain(metz,nancy).


route(From,To,Route) :- rt(From,To,[To],Route).
rt(From,From,A,A) :- !.
rt(From,To,A,Route) :-
        directTrain(From,To),
        rt(From,From,[From|A],Route).
rt(From,To,A,Route) :-
        directTrain(ViaSt,To),
        rt(From,ViaSt,[ViaSt|A],Route).


** 5 Practical Session   
 - 1.

   \+ version.

nu(A,B) :- \+ A = B.

   \+ cut-free version

nu(A,B) :-
        A = B, fail;
        A \= B.

   cut-fail combination version

nu(A,B) :- A = B, !, fail.
nu(_,_).
   
 - 2.

  頭がまわらないので、これも後日。

  これも一晩寝たら30分くらいでできた。

unifiableUni(Term1,Term2) :-
        atomic(Term1),atomic(Term2),
        Term1 = Term2.
unifiableUni(Term1,Term2) :-
        var(Term1);
        var(Term2).
unifiableUni(Term1,Term2) :-
        complexterm(Term1),
        complexterm(Term2),
        Term1 =.. [F1|Args1],
        Term2 =.. [F2|Args2],
        F1 = F2,
        unifiableLists(Args1,Args2).  
unifiableLists([],[]).
unifiableLists([H1|T1],[H2|T2]) :-
        unifiableUni(H1,H2),
        unifiableLists(T1,T2).

unifiableAcc([],Term,A,A).
unifiableAcc([H|T],Term,A,R) :-
        unifiableUni(H,Term),
        unifiableAcc(T,Term,[H|A],R),!;
        unifiableAcc(T,Term,A,R).

unifiable(List1,Term,List2) :-
        unifiableAcc(List1,Term,[],List2).

こつこつ。

【LPN】11 Database Manipulation and Collecting Solutions

* 11 Database Manipulation and Collecting Solutions
** 1 Database Manipulation
 - assert/1。む、swi-prologはちょっと変なことを言う。

?- listing.
true.

?- assert(happy(mia)).
true.

?- listing.

:- dynamic happy/1.

happy(mia).
true.

?- 

 - ファイルから読み込んだものはstatic predicates、
   REPL?で定義したものはdynamic predicates。
 - retract : 撤回する
 - swi-prologではretractの対象がDBに複数あるとき、
   バックトラック的な操作で全て消せる。

?- retract(happy(vincent)).
true ;
true.

?- listing.

:- dynamic happy/1.

happy(butch).

:- dynamic naive/1.

naive(A) :-
 happy(A).
true.

?- 

 - assertはmemoisaitonに使える。
 - database manipulationの迂闊な利用はnightmareだか
   ら注意して。

** 2 Collecting Solutions
 - findall/3はちょっとmap的。
 - bagof/3、便利。
 - setof/3、便利。

** 3 Exercise
 - Exercise 11.1.
   - 第一段階

q(foo,blug).
q(a,b).
q(1,2).

   - 第二段階

q(foo,blug).
q(a,b).
p(X) :- h(X).

   - 第三段階

p(X) :- h(X).

 - Exercise 11.2.
   - findall(X,q(blob,X),List).
     List = [blug,blag,blig].
   - findall(X,q(X,blug),List).
     List = [blob,dang].
   - findall(X,q(X,Y),List).
     List = [blob,blob,blob,,blaf,dang,dang,flab].
   - bagof(X,q(X,Y),List).
     Y = blug,
     List = [blob,dang].
     Y = blag,
     List = [blob,blaf].
     Y = blig,
     List = [blob].
     Y = dong,
     List = [dang].
     Y = blob,
     List = [flab].
   - setof(X,Y^q(X,Y),List).
     List = [blaf,blob,dang,flab].

 - Exercise 11.3.
   - まずこう書いた。
sigma(0,0).
sigma(N,S) :-
        M is N - 1, M >= 0,
        T is S - N, T >= 0,
        sigma(M,T),!,
        asserta((:- sigma(N,S))).

   - これはpredicateとしては使えるが、構築には使え
     ない。

?- sigma(5,15).
true.

?- sigma(10,X).
ERROR: is/2: Arguments are not sufficiently instantiated
^  Exception: (9) _L143 is _G174-10 ? 

    - traceで調べる。

?- trace.
Unknown message: query(yes)
[trace]  ?- sigma(2,X).
   Call: (7) sigma(2, _G303) ? 
^  Call: (8) _L180 is 2-1 ? 
^  Exit: (8) 1 is 2-1 ? 
^  Call: (8) 1>=0 ? 
^  Exit: (8) 1>=0 ? 
^  Call: (8) _L181 is _G303-2 ? 
ERROR: is/2: Arguments are not sufficiently instantiated
^  Exception: (8) _L181 is _G303-2 ? 
   Exception: (7) sigma(2, _G303) ? 
?- 

    - なるほど。Unificationのinstantiationがいまい
      ちつかめていないのだな。accumulatorを使おう。

sigma(N,S) :- sigmaAcc(N,0,S),!,asserta((sigma(N,S))).
sigmaAcc(0,A,A) :- !.
sigmaAcc(N,A,S) :-
        M is N - 1,
        NewA is A + N,
        sigmaAcc(M,NewA,S).

      assertaが

ERROR: asserta/1: No permission to modify static_procedure `sigma/2'

      を吐く。これはまた別の問題なので割愛する。

** 4 Practical Session
 - 1.

subset([],_).
subset([H|T],[H|ST]) :-
        subset(T,ST).
subset([H|T],[SH|[H|ST]]) :-
        subset(T,[SH|ST]).

   backtrackで出力する集合に重複があるけどそれは勘
   弁。

 - 2.

powerset(L,P) :-
        findall(X,subset(X,L),P).

   先の重複の問題があるので、同じ集合だけど並びが
   違うものも含んでしまっている。

?- powerset([a,b,c],P).
P = [[], [a], [a, b], [a, b, c], [a, c], [a, c, b], [b], [b|...], [...|...]|...].

   これらの手落ちは後日時間があったらやろう。

よろよろ。

【LPN】10 Cuts and Negation

* 10 Cuts and Negation
** 1 The Cut
 - ! : predicate called cut.
 - cutは常に成功する。副作用する。副作用が大事。
 - fat-freeじゃなくてcut-free。
 - commit A to do,doing : Aに...することを義務づけ
   る。
 - cutを踏んだ時点で2つのことが義務となる。1つめは、
   現在のproof searchにおいて、そのclauseのみを探
   索の対象とすること(他のclauseは除外するというこ
   と)。次に、cutを踏む前にunify済みの変数について
   は、これ以降unificationは実施しないこと。
** 2 Using Cut
 - green cuts : cutsを入れても入れなくてもプログラ
   ムの意味(入出力の対応)に変化はないもの。green
   cutsに意味があるのは、効率があがるときである。
 - red cuts : cutsの有り無しでプログラムの意味が変
   わるcuts。
 - red cutsがある、ということはそのプログラムがあ
   まり宣言的ではない証左。なるほど。
** 3 Negation as Failure
 - fail/0 : バックトラックを強制する述語。
 - cut-fail combination : failによるバックトラック
   を抑制するイディオム。このイディオムがくると、
   そこでproof search自体がfailする(バックトラック
   しない)。
 - この章に入って、Prologの手続き的側面がどんどん
   導入されていく。。
 - negation : Monadic Boolean operations whose
   result have the Boolean value opposite to that
   of the operand.
 - cut-failじゃなくてnegation as failureを使うほう
   が安全。

neg(Goal) :- Goal,!,fail.
neg(Goal).

 - \+ : built-in negation as failure predicate.

 - cutsとnegation as failureの使い方についての完全
   なルールは存在しないケースバイケースの判断が必
   要。

 - まあ、プログラミングは、科学であるのと同じくら
   い芸術(技芸)でもあるので、自身が選択した言語と
   問題領域について理解を常に深めなければならない。
   だから面白いんだよ、プログラミングは。など。
** 4 Exercises
 - Exercise 10.1.
   p(X).
   X = 1.
   X = 2.

   p(X),p(Y).
   X = 1, Y = 1.
   X = 1, Y = 2.

   これ、間違えた。正解は、


?- p(X),p(Y).
X = 1,
Y = 1 ;
X = 1,
Y = 2 ;
X = 2,
Y = 1 ;
X = 2,
Y = 2.

?- 

   ということ。p(Y)でのcutはp(X)の探索には影響を及
   ぼさないことに注意。
   
   p(X),!,p(Y).
   X = 1, Y = 1.
   X = 1, Y = 2.
   
 - Exercise 10.2.

class(Number,positive) :- Number > 0.
class(0,zero).
class(Number,negative) :- Number < 0.

   これは数字のクラスに関する述語。正か負かゼロか
   でクラス分けしている。

   green cutsによる効率化。

class(Number,positive) :- Number > 0,!.
class(0,zero) :- !.
class(Number,negative) :- Number < 0.
   
 - Exercise 10.3.

   まず、cut-free。
   
split([],[],[]).
split([LH|LT],[LH|PT],N) :-
        LH >= 0, split(LT,PT,N).
split([LH|LT],P,[LH|NT]) :-
        LH < 0, split(LT,P,NT).

   続いてgreen cuts。

split([],[],[]) :- !.
split([LH|LT],[LH|PT],N) :-
        LH >= 0, !, split(LT,PT,N).
split([LH|LT],P,[LH|NT]) :-
        LH < 0, !, split(LT,P,NT).

 - Exercise 10.4.

   うーん。むずかしい。cutは宣言的かつ手続き的なの
   で、慣れれば強力かもしれないが、慣れないと中途
   半端で考えにくい。特にunificationがどう効いてく
   るかが問題になると、自分で束縛管理した方が楽じゃ
   んと思えてしまう。
   
   ここは後日、再チャレンジ。



** 5 Practical Session   
 - 1.

   \+ version.

nu(A,B) :- \+ A = B.

   \+ cut-free version

nu(A,B) :-
        A = B, fail;
        A \= B.

   cut-fail combination version

nu(A,B) :- A = B, !, fail.
nu(_,_).
   
 - 2.

  頭がまわらないので、これも後日。

よろよろ。

【LPN】9 A Closer Look at Terms

* 9 A Closer Look at Terms
** 1 Comparing Terms
 - ==/2はCommon Lispのeqみたいなニュアンスかな。
 
?- a == a.
true.

?- a == b.
fail.

?- a == 'a'.
true.

?- X == Y.
fail.

?- X=Y.
X = Y.

?- a = X, a == X.
X = a.

?- 

 - ふむ、eval、、、ではなくunifyされたobjectsを
   eq、、、じゃなく==は等価性チェックする。
 - ただ、==はtrue/failだけでなく、unifyされている
   ときは、unification(binding)を返しているな。な
   んか気になる。
 - \==/2の導入。

** 2 Terms with a Special Notation
 - Arithmetic terms

?- (2 =:= 3) == =:=(2,3).
true.

?- 2 =:= 3 == =:=(2,3).
ERROR: Syntax error: Operator priority clash
ERROR: 2 =:=
ERROR: ** here **
ERROR:  3 == =:=(2,3) . 
?- 

 - なるほど。

 - List as terms
   
?- .(a,[]) == [a].
true.

?- .(a,.(b,[])) == [a,b].
true.

?- 
 - おお、consだ！会いたかったよ、cons。こんなに小
   さくなっちゃって。。。

** 3 Examining Terms
 - Types of Terms
 - termsの型を調べる述語たち。
 
 - The structure of Terms

?- functor(f(a,b),F,A).
F = f,
A = 2.

?- 
 - おお、functorとarityも取れるのね。

?- functor(T,hoge,1).
T = hoge(_G240).

 - 構成もしてくれる、と。

 - complex termに対する型判定述語は自分で作る。

complexterm(X) :-
        nonvar(X),
        functor(X,_,A),
        A > 0.

 - arg : 引数に対するアクセス。
 - =.. : complex termsのfunctorとargsをリストで返
   す。univと呼ばれる。
 - atom_codes/2にてatomとstringの相互変換ができる。

** 4 Operators
 - ?-というのはprefix operatorだったのか。
 - precedenceが大きいものが主たる(:外側の)functor
   になる。+と*でいうと+の方が優先度が大きいので

   2 + 3 * 4.

   は、

   +(2,*(3,4)).

   になる。優先度が高い = 結合度が低い、かな。

 - operatorsとpredicatesが同義語なのかそうでないの
   かがわからない。先々わかるかな。
 - precedenceが同じoperatorsが存在する場合どうなる
   か。それはoperatorsのassociativityという概念/機
   構によって振る舞いがきまる。
 - 例えば、+は左結合性をもっている(left
   associative)。
 - 左結合性をは何か？
 - まずexpressionsのprecedenceの概念がある。それは
   そのexpressionの主functorのprecedenceである。さ
   て、左結合性とは、infix operatorsなのでそもそも
   引数は左右の2つなのだが、左にいれるexpressionは
   自身と同じprecedenceでもよいが、右にいれる
   expressionは自身より低くないといけない。これに
   よって、

   2 + 3 + 4.
   
   は、

   +(+(2,3),4).

   というように曖昧さなく解釈される。ためす。

?- 2 + 3 + 4 = +(+(2,3),4).
true.

?- 2 + 3 + 4 = +(2,+(3,4)).
fail.

   なお、これは内側のoperatorが+でなくても(同じで
   なくても)適用される。

 - ==, =:= は同じprecedenceを持ち、かつ
   non-associtiveである。すなわち、左右引数双方と
   も自身よりもprecedenceが低い必要がある。そのた
   め、

   2 =:= 3 == =:=(2,3).

   が、

   ==((2 =:= 3),=:=(2,3)).

   なのか、

   =:=(2,==(3,=:=(2,3))).

   なのかをPrologは自動判定できない。

 - Defining operators
 - operatorsというのは、operatorとして構文定義され
   たpredicatesのことのようだな。逆に言うと、op
   operatorが定義するのは構文だけで、それの意味と
   いうかその演算の結果がどうなるかは通常のqueryと
   同じであるということ。

?- assert(kill(marcellus,zed)).
true.

?- kill(X,zed).
X = marcellus.

?- assert((is_dead(X) :- kill(_,X))).
true.

?- is_dead(zed).
true.

?- op(500,xf,is_dead).
true.

?- zed is_dead.
true.

?- is_dead zed.
ERROR: Syntax error: Operator expected
ERROR: is_dead 
ERROR: ** here **
ERROR: zed . 

?- 

** 5 Exercise
 - Exercise 9.1.
  - 12 is 2*6.
    true.
  - 14 =\= 2*6.
    true.
  - 14 = 2*7.
    true. /* 正しくはfail。unifyは計算しない。term
    の種類が違う。*/
  - 14 == 2*7.
    fail.
  - 14 \== 2*7.
    true.
  - 14 =:= 2*7.
    true.
  - [1,2,3|[d,e]] == [1,2,3,d,e].
    true.
  - 2+3 == 3+2.
    fail.
  - 2+3 =:= 3+2.
    true.
  - 7-2 =\= 9-2.
    true.
  - p == 'p'.
    true.
  - p =\= 'p'.
    fail. /* 正しくはERROR.数字じゃないので計算で
    きない */
  - vicent == VAR.
    fail
  - vincent=VAR,VAR==vincent.
    true.

 - Exercise 9.2.
  - .(a,.(b,.(c,[]))) = [a,b,c].
    true.
  - .(a,.(b,.(c,[]))) = [a,b|c].
    fail
  - .(.(a,[]),.(b,[]),.(.(c,[]),[])) = X.
    ERROR. /* 最外の.の引数が3つ。*/
    お、ERRORにならない。そうか'.'/3が定義されるの
    か!
  - .(a,.(b,.(.(c,[]),[]))) = [a,b|[c]].
    fail. /* [a,b,[c]] */
 - Exercise 9.3.

complexterm(X) :-
        nonvar(X),
        functor(X,_,A),
        A > 0.

termtype(Term,atom) :-
        atom(Term).
termtype(Term,number) :-
        number(Term).
termtype(Term,constant) :-
        atomic(Term).
termtype(Term,variable) :-
        var(Term).
termtype(Term,simple_term) :-
        atomic(Term);
        var(Term).
termtype(Term,comprex_term) :-
        complexterm(Term).
termtype(_,term).

 - Exercise 9.4.

groundterm(X) :-
        atomic(X), nonvar(X).
groundterm(X) :-
        nonvar(X),
        X = [H|T],
        groundterm(H),
        groundterm(T).
groundterm(X) :-
        complexterm(X),
        '=..'(X,[functor|Args]),
        groundterm(Args).

 - Exercise 9.5.
 
  - うー。operatorの結合めんどくさい。S式でいいじゃん。

X is_a witch
is_a(X,witch).

harry and ron and hermione are friends
are(and(harry,and(ron,haermione)),friends)

harry is_a wizard and likes quidditch
illegal.

dubledore is_a famous wizard
is_a(dubledore,famous(wizard)).

** 6 Practical Session   
 - pretty printer

pptree(T) :- ppt(T,0).
ppt(T,I) :-
        atomic(T),tab(I),write(T).
ppt(T,I) :-
        complexterm(T),
        '=..'(T,[Functor,Single]),
        tab(I),write(Functor),write('('),write(Single),write(')').
ppt(T,I) :-
        complexterm(T),
        '=..'(T,[Functor,Left,Right]),
        tab(I),write(Functor),write('('),nl,
        NewI is I + 2,
        ppt(Left,NewI),nl,
        ppt(Right,NewI),write(')').

 - propositional logic formulas

:- op(200,fx,not).
:- op(300,xfy,implies).

さすがに体調が悪くなってきた。
仕事との両立が難しいのか、体が弱いのか。

こつこつ。