DVIOUT-flogic-kb-new

”

Ｆ論理－２

”

1

はじめに

前回：

ＲＤＢ

主キーと外部キーを区別

ＯＯＤＢ ＯＩＤのみ

Ｆ論理

ＯＩＤを１階の項で表記．

ＯＩＤ 間の有向グラフ構造： Ｆ分子式

エッジは（パラメータ付き）メソッドでラベリング

継承規則などのシステム公理

一般のＦ論理は，

A

1

,

· · · , A

n

:

−B

1

, ..., B

m

の形式のルール，

OID

間の等号（

mary = mother(tom)

），型推論．

今回は

Prolog

の拡張として実行できるべく，制限を加えて話す：

ＤＤＢの拡張：

A :

_−B

1

, ..., B

m

.

等号なし，型推論なし．

Ｆ論理の推論規則（の一部）

： ＤＤＢの導出法の拡張

クラスもメソッドも共にオブジェクト

:

パラメータ化し，多態性

Contents

1. はじめに 1.1. Contents 2. F-clause と推論 2.1. F-clause 例 2.2. 分子式の導出 2.3. Inference Rules 2.4. 推論例（述語も含む） 3. 多態性１： インタフェースとの比較 3.1. 関数オブジェクト 3.2. Java インタフェース 3.3. メソッドの多態性 3.4. 念のため，計算過程を例示 3.5. A note on 実装と継承 4. 多態性２：クラス変数を用いる場合 4.1. parameterized data type 4.2. instanceof

4.3. クラス変数を用いたプログラム 4.4. 参考： 汎用 qsort の Prolog 版 5. new object 生成 : join で例示

5.1. 参考： Prolog code for Join in Flogic 6. 演習問題

2

F-clause

と推論

2.1

F-clause

例

階層：

bob: mnger.

bob: facultyMember. mnger::employee.

ＥＤＢ：

bob [ name

→

”Bob”; age

→

40;

worksFor

→

cs [ name

→

”CS”; mngr

→

bob;

assistants

_{→→ {mary, john} ]]}

ＩＤＢ：

E [ boss

→

M ] :- E:employee, D:dept, M:employee,

E [ worksFor

_{→ D [mnger → M ] ]}

システム公理

ISA

継承

: X : Z :

_{−X : Y, Y :: Z}

X :: Z :

_{−X :: Y, Y :: Z}

集合値メソッド

:

à k

∧

j=1

X[M

→→ B

j

]

!

↔ X[M →→ {B

1

, ..., B

k

}]

略記法

(*)

：

X[M1

→

V] :- X:T, Y:D, Y[M2

→

V]

X[M1

→

V] :- X:T, Y:D[M2

→

V]

(*) X:c :- Bodyか，X[M→V] :- X:c, Bodyかを明示的に区別するため，頭部では略記法を用 いないとする

2.2

分子式の導出

ルールの適用例：

bob[name

→

"Bob";age

→

40;worksFor

→

cs].

cs:dept[dsName

→

"CS";mngr

→

bob]].

E[boss

→

M] :- E[worksFor

→

D:dept[mnger

→

M].

X:employee :- X[worksFor

→

Z:dept].

mh[worksFor

→

cs]

---mh:employee. mh[boss

→

bob].

（

mh:employee[boss

→

bob]

）

継承の例：

jim:workingSt[wagePerHour

→

1000;monthlyWHour

→

40]

workingSt::partTime

X[income

→

V]

:- X:partTime, X[wagePerHour

→

W; monthlyWHour

→

H], V is W*H.

---jim:partTime [income

→

40000].

2.3

Inference Rules

resolution (goal reduction):

:- A, As

A

0

:

_{−Es with Aσ = A}

0

σ

:- Asσ, Esσ

代入

σ

もＦ分子式の内部構造に伴

い、拡張定義．

_→→:

複数の可能性

ISA

階層

X::Z :- X::Y, Y::Z.

も右記と同様

:- t1 : c

X : Z :

_{−X : Y, Y :: Z with (t1 : c)σ = (X : Z)σ}

:- (X : Y, Y :: Z)σ

:- bob : Class

bob : fullTime

Class = fullTime

□

:- bob : Class

X:Z :- X:Y, Y::Z with X=bob, Z=Class

:- bob : Y, Y::Class

bob:fullTime with Y=fullTime

:- fullTime::Class

fullTime::hasIncome with Class = hasIncome

□

2.4

推論例（述語も含む）

ＤＤＢ同様に，述語も許す

⎧ ⎪ ⎨ ⎪ ⎩

オブジェクト間の関係，

オブジェクトの性質

引数はＯＩＤを表す項

推論規則もＤＤＢと全く同じ

highIncome(P)

:- P[income

→

V],

V > 500000.

:- highIncome(jim).

the above rule with

P=jim

:- jim[income

→

V],

V > 50000.

:- jim[income

→

V], V>500000.

X[income

→

S]

:-X:partTime[ wagePerHour

→

W;

montlyWHour

→

H],

S is W*H.

V = S, X = jim

:- jim:partTime[wagePerHour

→

W;

monthlyWHour

→

H], V is W*H, V>500000

jim:workingSt, workingSt::partTime

:- jim[wagePerHour

→

W;monthlyWHour

→

H],

V is W*H, V>500000

jim[ wagePerHour

→

1000;

monthlyWHour

→

40],

W = 1000, H = 40

:- V is 1000*40, V>500000

V = 40000

:- 40000 > 500000

失敗！

6

3

多態性１： インタフェースとの比較

3.1

関数オブジェクト

apply(f,x) = f(x)

関数

f

を引数化（「もの」としてみる）

apply

メソッド『関数

f

に

x

を渡して実行せよ』

f[apply@x

→

Z]

_{↔ x[f}

→

Z].

(

オブジェクトが関数を持つ

(*))

func1:myfunc.

func1[apply@X

→

V] :- ..., V is ...

func2:myfunc.

func2[apply@X

→

V] :- ..., V is ...

process(F,X,Y) :- F:myfunc[apply@X

→

V], ..., Y is ...

:- process(func1,10, X)

:- func1:myfunc,

func1[apply@10

→

V],...Y is...

:- func1[apply@10

→

V],...,Y is ...

:- ..., V is ,...,Y is ...

...

□

関数オブジェクトと考える

と，関数を変数化し，様々な

関数に対する処理を統一的・

抽象的に記述できる

(*)「オブジェクトがメソッドを持つ」：オブジェクト指向の言い方（考え方） 実際は，オブジェクトがどのようなメソッドを持つかは，クラスの定義 逆に言えば，所有するメソッドが異なれば，それは別のクラスのオブジェクト

3.2

Java

インタフェース

interface MyFunc {

int apply(int x);//

メソッド型制約

}

class Func1 implements MyFunc {

public int apply(int x)

{...;...;}

//

メソッド実装

}

class A {

//

インタフェース参照変数を用いた応用手続き

static int process(MyFunc fc, int x)

{int v = fc.apply(x); ... ; return y;}

public static void main(String[] args) {

Func1 func1 = new Func1();//

実装クラスオブジェクト

System.out.println( process(func1, 101) );

}

}

関数オブジェクト

f

～ 実装クラスオブジェクト

そのパラメータ化

_F

～ インタフェース参照変数

メソッド

apply

の挙動は

ホストオブジェクトによって変化

多態性

(polymorphism)

メソッドの様々な振る舞い

...

8

3.3

メソッドの多態性

interface HasIncome {

// income メソッドを持つもの int income();

}

class FullTime implements HasIncome{ // フルタイムワーカの場合はこうです

private int salary;

public int income() {return salary;} }

class PartTime implements HasIncome{ // パートタイムワーカの場合はこうです

private int hourPerMonth, hourWage; public int income() {

return hourPerMonth*hourWage; }

}

class Company {

private hasIncome[] employees; //「income メソッドを持つもの」の配列

int payment() { int payment = 0;

for (int i=0;i<employees.length;i++) payment += employees[i].income(); return payment; } } /* 場合分け（実装） 下記ではクラス階層なし ～ 陰に： fullTime::any. partTime::any. */ X[income → V] :-X:fullTime[salary → V]. X[income → V] :- X:partTime, X[hourPerMonth → H;hourWage → W], V is H*W. /* -- データ分子式（事実）*/ bob:partTime [hourPerMonth → 30; hourWage → 1000]. john:fullTime[salary → 20000]. /* -- income 総計算 */ payment([],0). payment([E|Es],P) :- /* 陰に E:any */ E[income → V], payment(Es, EP), P is V + EP. /* full or partTime 以外の要素があれば単に失敗. 動的型検査を行いたい場合は */ fullTime::hasIncome. partTime::hasIncome. payment([],0). payment([E|Es],P)

:-E:hasIncome[income → V], payment(Es, EP), P is V + EP.

payment([E|_],null) :- \+ E:hasIncome, print(’*** type error ***’).

3.4

念のため，計算過程を例示

:- payment([tom,jim],P)

payment([E|Es],P) :- E:hasIncome[income

→

V], payment(Es, EP),

P is V+EP

:- tom:hasIncome, tom[income

→

V], payment([jim],P1), P is V+P1.

tom:fullTime. fullTime::hasIncome.

ＢＴＰ

:- tom[income

→

V], payment([jim],P1), P is V+P1.

X[income

→

V] :- X:partTime,

X[hourPerMonth

→

H;hourWage

→

W], V is H*W.

:- tom:partTime, ...

（失敗，バックトラック

to

ＢＴＰ）

ＢＴＰ

_{:- tom[income}

→

_{V], payment([jim],P1), P is V+P1.}

X[income

→

V] :- X:fullTime[salary

→

V]

:- tom:fullTime[salary

→

V],payment([jim],P1), P is V+P1.

tom:fullTime[salary

→

300000]

:- payment([jim],P1), P is 300000+P1.

...

:- ...

10

3.5

A note on

実装と継承

Jave:

クラス階層

メソッド定義の継承

単一継承：定義衝突回避

同一パス上でオーバーライド

インタフェース：メソッド型制約 と定数のみ

抽象性（インスタンス化不可）

実体オブジェクトは実装側で生成

実装クラス：型制約を継承 し実装

抽象クラス： 抽象性を持つクラスで，インタフェース組込可

Ｆ論理

with

型制約

多重継承はＯＫ（多重解）

インタフェースは，メソッド型制約

_{X:hasIncome[income}

⇒

_int]

を実装クラス

fullTime

に継承させる形で，書式を決めればＯＫ

『インタフェースはクラスではない』と書いてあるが ．．． 言語仕様上は，確かにクラスとは異なる．つまり，インタフェースは言語的規制を受けた クラスであり，コンパイル時に規制（抽象性，実装クラスでの実装義務，などを守っ ているかをチェック しかし，実行時は一つのクラス．何ら区別はない インタフェースは，多態性の実現のためだけでなく，クラス間の文字通りの「インタフェース」

4

多態性２：クラス変数を用いる場合

4.1

parameterized data type

クラスオブジェクトの変数化

just as

関数オブジェクトの変数化

X:T

T

はクラスを表す変数とみる

その値は「クラスオブジェクト」

[]:list(T).

[X|Y]:list(T)

:- X:T, Y:list(T).

:- [mh,bob]:list(empl).

[mh,bob] = [mh|[bob|[]]]

:- mh:empl, [bob]:list(empl).

:- [bob]:list(empl).

[bob] = [bob|[]]

:- bob:empl, []:list(empl).

:- []:list(empl).

□

[a] = [a|[]]

[b,a] = [b|[a]]

[c,b,a] = [c|[b,a]]

...

[a

1

, a

2

,

· · · , a

k

] = [a

1

|[a

2

, . . . , a

k

]]

演習問題 ２．２．

関数オブジェクトのリスト

[f1,...,fk]:list(myfunc)

と，

オブジェクト

a

を与え，

?- rapply(a, [f1,...,fk], X).

X = [b1,...,bk]

ただし，

bj

は

a

に

fj

を適用して得られる値

となるような

rapply

を定めよ

.

12

4.2

instanceof

Flogic

[]:list(T).

[X|Y]:list(T)

:- X:T, Y:list(T).

Prolog

instanceof([],list(T)).

instanceof([X|Xs],list(T)):-instanceof(X,T), instanceof(Xs,list(T)).

instanceof(tom,st).

attr(tom,name,"Tom").

instanceof(john,st).

attr(john,name,"John").

instanceof(mary,emp).

attr(mary,income,100).

instanceof(kenji,emp).

attr(kenji,income,1000).

?- instanceof([tom,john], X).

X=list(st).

質問：

[tom,john]

の型は何ですか？

答え： それは，

st

のリスト型です．

?- instanceof([tom,mary], X).

no

tom

と

mary

を統一するクラスは陽には存在しないから

no

となった

st::any.

emp::any

を追加して，

X = list(any)

にすべき？

演習問題２ 上記で，

tom

と

mary

に対して，

no

となることを確かめよ．さ

らに，

X=list(any)

とするために，どのようなルールを追加すれば良い

かを考え，それを与えよ

4.3

クラス変数を用いたプログラム

qsort(X:list(T),

Y:list(T))

分割（

divide

）のとき，クラスに

応じた処理を行う多態性（クラス

変数

_T

）

:- divide(jim,[bob],L1,L2,T). jim:emp, bob:emp, L1 = [bob|L11] :- lessThan(bob,jim,emp), divide(jim,[],L11,L2,st). :- jim[income → XV], bob[income → YV], YV < XV, divide(jim,[],L11,L2,st). ... /* クラス変数 T を用いた program */ qsort([],[]). qsort([X|Xs],Zs) :- divide(X,Xs,Ls,Gs), qsort(Ls,RLs), qsort(Gs,RGs), append(RLs,[X|RGs],Zs). divide(X,[],[],[]). divide(X,[Y|Ys],[Y|Ls],Gs) :- X:T, Y:T, lessThan(Y,X,T), divide(X,Ys,Ls,Gs). divide(X,[Y|Ys],Ls,[Y|Gs]) :- X:T, Y:T, \+ lessThan(Y,X,T), divide(X,Ys,Ls,Gs). /* st での実装 */ lessThan(Y,X,st)

:-Y[name → YN], X[name → XN], dicOrder(YN, XN).

/* emp での実装 */ lessThan(Y,X,emp)

:-X[income → XV], Y[income → YV], YV < XV.

給与計算の例と同じスタイルでも書ける

st::comparable. emp::comparable.

divide(X,[Y|Ys],[Y|Ls],Gs) :- X:comparable, Y:comparable, ...

4.4

参考： 汎用

qsort

の

Prolog

版

qsort([],[]).

qsort([X|Xs],Zs) :- divide(X,Xs,Ls,Gs),

qsort(Ls,RLs), qsort(Gs,RGs), append(RLs,[X|RGs],Zs). append([],X,X). append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs). divide(X,[],[],[]). divide(X,[Y|Ys],[Y|Ls],Gs) :-instanceof(X,T), instanceof(Y,T), lessThan(Y,X,T), divide(X,Ys,Ls,Gs). divide(X,[Y|Ys],Ls,[Y|Gs]) :-instanceof(X,T), instanceof(Y,T), \+ lessThan(Y,X,T), divide(X,Ys,Ls,Gs). /* emp での実装 */

lessThan(X,Y,emp) :- attr(X,income,XS), attr(Y,income,YS), XS < YS. /* st での実装 */

lessThan(X,Y,st) :- attr(X,name,XN), attr(Y,name,YN), lexicogOrder(XN,YN). lexicogOrder([],[_|_]). /* 文字列は内部的には character code のリスト */ lexicogOrder([X|Xs],[Y|Ys]):- X < Y. lexicogOrder([X|Xs],[Y|Ys]):- X = Y, lexicogOrder(Xs,Ys). /* st データ */ instanceof(tom,st). attr(tom,name,"Tom"). instanceof(john,st). attr(john,name,"John"). instanceof(jim,st). /* emp データ */ instanceof(mary,emp). attr(mary,income,100). instanceof(kenji,emp). attr(kenji,income,1000). /* ?- qsort([kenji,mary],X). X=[mary,kenji]. ?- qsort([john,tom],X). X=[john,tom].

5

new object

生成

: join

で例示

R at1 at2 a b c d S at1 at2 c b b x R × S

R.at1 R.at2 S.at1 S.at2

a b c b

a b b x

c d c b

c d b x

等結合 σR.at2=S.at1(R× S)

R.at1 R.at2=S.at1 S.at2

a b x

関係Ｒの

OID r

，そのタプルの

OID t

「ｔ は ｒのインスタンス」 ～

t:r.

直積

:

新たな

OID

項を導入

new(Tr,Ts):join(R,S,[]) :- Tr:R, Ts:S.

t1:r. s1:s.

がＥＤＢに登録

⇒

new(t1,s1):joint(r,s,[])

が導出

属性の定義（

n:

属性名の衝突を回避）

new(T,S)[Attr

→

Z]:-T[Attr

→

Z].

new(T,S)[n(Attr)

→

Z]:-S[Attr

→

Z].

join

の第３引数： 結合条件のリスト

c(at2,at1) : r

の

at2

属性値と

s

の

at1

属性値の等価性を要求

new(Ptuple,Qtuple)

が全ての要素条件を満たすことを反復検証

new(Ptuple, Qtuple):join(P,Q,[]) :- Ptuple:P, Qtuple:Q.

new(Ptuple, Qtuple):join(P,Q, [c(PAttr,QAttr)|Cs])

:- Ptuple:P[PAttr

→

V], Qtuple:Q[QAttr

→

V], /*

等価性

*/

new(Ptuple, Qtuple):join(P,Q, Cs).

5.1

参考：

Prolog code for Join in Flogic

/* タプルを表す OID として リスト [tokyo,sapporo] 等を用いる

直積のインスタンスは，OID 構成子 new を使わず，２個のタプルＩＤから なるリスト [[kagoshima,hukuoka],[hukuoka,tokyo]] 等で表記.

query によっては infinite loop なので，事実を先に書く.

（停止性の検証は引数条件を設定した上，帰納的に．この例の場合は，instanceof の 第２引数に基底項を束縛させたときの停止性を検証できればＤＢとしては十分） */ instanceof([kagoshima,hukuoka],edge). instanceof([hukuoka,tokyo],edge). instanceof([tokyo,sapporo],edge). instanceof([sapporo,kagoshima],edge). /*

?- instanceof(X, join(edge,edge,[]) ). 直積 edge × edge

X = [[kagoshima,hukuoka],[kagoshima,hukuoka]] ? ; 別解のプロンプト X = [[kagoshima,hukuoka],[hukuoka,tokyo]] ? ; 改行：強制終了 yes ?- instanceof(X, join(edge,edge,[c(target,source)]) ). X = [[kagoshima,hukuoka],[hukuoka,tokyo]] ? ; X = [[hukuoka,tokyo],[tokyo,sapporo]] ? ; X = [[tokyo,sapporo],[sapporo,kagoshima]] ? ; X = [[sapporo,kagoshima],[kagoshima,hukuoka]] ? ; 最後の解（別解を要求し no ） no */ attr(T,source,V) :- instanceof(T,edge), T=[V,_]. /* 関係スキーマに相当 */ attr(T,target,V) :- instanceof(T,edge), T=[_,V].

attr([T,S],Attr,V) :- \+ Attr=n(_), attr(T,Attr,V). attr([T,S],n(Attr),V) :- attr(S,Attr,V).

instanceof([Ptuple,Qtuple], join(P,Q,[]))

6

演習問題２

P 2.1. (sheet 3.1) あなたが普段使っているプログラミング言語を用い，「関数オブジェクト」と 同様なことができるか否かを論じなさい．ただし，Java については述べたの で，Java 以外で解答すること． P 2.2. (sheet 4.1) 関数オブジェクトのリスト [f1,...,fk]:list(myfunc) と，オブジェクト a を与え， ?- rapply(a, [f1,...,fk], X). X = [b1,...,bk] ただし，bj は a に fj を適用して得られる値 となるような rapply を定めよ. P 2.3．(sheet 4.2) []:list(T). [X|Xs]:list(T) :- X:T, Xs:list(T). st::any. emp::any. tom:st. mary:emp.

に対し， [tom,mary]:list(any) の証明過程を説明しなさい．さらに，Prolog において，instanceof を用い

instanceof([tom,mary], list(any)) が成功するために必用なルールを追加しなさい．