F 論理 -2 1 はじめに 前回 : RDB 主キーと外部キーを区別 OODB OIDのみ F 論理 OIDを1 階の項で表記. OID 間の有向グラフ構造 : F 分子式エッジは ( パラメータ付き ) メソッドでラベリング継承規則などのシステム公理一般のF 論理は, A 1,,A n : B 1,..., B m の形式のルール, OID 間の等号 (mary = mother(tom)), 型推論. 今回は Prolog の拡張として実行できるべく, 制限を加えて話す : DDBの拡張 : A : B 1,..., B m. 等号なし, 型推論なし. F 論理の推論規則 ( の一部 ): DDBの導出法の拡張クラスもメソッドも共にオブジェクト : パラメータ化し, 多態性クラス階層を用いる多態性との比較も 1
Contents 1. はじめに 1.1. Contents 2. F-clause と推論 2.1. F-clause 例 2.2. 分子式の導出 2.3. Inference Rules 2.4. 推論例 ( 述語も含む ) 3. 多態性 1: インタフェースとの比較 3.1. 関数オブジェクト 3.2. Java インタフェース 3.3. メソッドの多態性 3.4. 念のため, 計算過程を例示 3.5. A note on 実装と継承 4. 多態性 2: クラス変数を用いる場合 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
2 F-clause と推論 2.1 F-clause 例 階層 : bob: mnger. bob: facultymember. mnger::employee. EDB:bob [ name Bob ; age 40; worksfor cs [ name CS ; mngr bob; assistants {mary, john ]] IDB: 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 集合値メソッド : X[M B j ] X[M {B 1,..., B k ] j=1 略記法 (*): 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 かを明示的に区別するため, 頭部では略記法を用いないとする 3
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]. 4
2.3 Inference Rules resolution (goal reduction): :- A, As A 0 : Es with Aσ = A 0 σ :- Asσ,Esσ 代入 σ もF 分子式の内部構造に伴い 拡張定義. : 複数の可能性 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 X::Z :- X::Y, Y::Z. も同様 :- 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 5
2.4 推論例 ( 述語も含む ) DDB 同様に, 述語も許す オブジェクト間の関係, オブジェクトの性質 引数はOIDを表す項推論規則もDDBと全く同じ 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 多態性 1: インタフェースとの比較 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.... 関数オブジェクトと考えると, 関数を変数化し, 様々な関数に対する処理を統一的 抽象的に記述できる (*) オブジェクトがメソッドを持つ : オブジェクト指向の言い方 ( 考え方 ) 実際は, オブジェクトがどのようなメソッドを持つかは, クラスの定義逆に言えば, 所有するメソッドが異なれば, それは別のクラスのオブジェクト 7
3.2 Java インタフェース interface MyFunc { int apply(int x);// メソッド型制約 class Func1 implements MyFunc { public int apply(int x) 関数オブジェクト f ~ 実装クラスオブジェクトそのパラメータ化 F ~ インタフェース参照変数メソッド apply の挙動は {...;...; // メソッド実装 ホストオブジェクトによって変化 多態性 (polymorphism) メソッドの様々な振る舞い... 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) ); 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 *** ). */ 9
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. BTP :- 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 BTP) BTP :- 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: クラス階層メソッド定義の継承単一継承 : 定義衝突回避同一パス上でオーバーライドインタフェース : メソッド型制約と定数のみ抽象性 ( インスタンス化不可 ) 実体オブジェクトは実装側で生成実装クラス : 型制約を継承し実装抽象クラス : 抽象性を持つクラスで, インタフェース組込可 F 論理 with 型制約 多重継承はOK( 多重解 ) インタフェースは, メソッド型制約 X:hasIncome[income int] を実装クラス fulltime に継承させる形で, 書式を決めれば OK インタフェースはクラスではない と書いてあるが. 言語仕様上は, 確かにクラスとは異なる. つまり, インタフェースは言語的規制を受けたクラスであり, コンパイル時に規制 ( 抽象性, 実装クラスでの実装義務, などを守っているかをチェックしかし, 実行時は一つのクラス. 何ら区別はない インタフェースは, 多態性の実現のためだけでなく, クラス間の文字通りの インタフェース 11
4 多態性 2: クラス変数を用いる場合 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 ]] 演習問題 2.2. 関数オブジェクトのリスト [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). instanceof(john,st). instanceof(mary,emp). instanceof(kenji,emp). attr(tom,name,"tom"). attr(john,name,"john"). attr(mary,income,100). 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) にすべき? 演習問題 2 上記で,tom と mary に対して,no となることを確かめよ. さらに,X=list(any) とするために, どのようなルールを追加すれば良いかを考え, それを与えよ 13
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,... 14
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].?- qsort([mary,tom],x). no これは,mary と tom のクラスが異なるため?- qsort([tom,jim],x). no これは,jim が name attr を持たないため */ 15
5 new object 生成 :join で例示 R at1 a c at2 b d S at1 c b at2 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 関係 Rの OID r, そのタプルの OID t t は rのインスタンス ~ t:r. 直積 : 新たな OID 項を導入 new(tr,ts):join(r,s,[]) :- Tr:R, Ts:S. t1:r. s1:s. がEDBに登録 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 の第 3 引数 : 結合条件のリスト 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). 16
5.1 参考 : Prolog code for Join in Flogic /* タプルを表す OID としてリスト [tokyo,sapporo] 等を用いる直積のインスタンスは,OID 構成子 new を使わず,2 個のタプルIDからなるリスト [[kagoshima,hukuoka],[hukuoka,tokyo]] 等で表記. query によっては infinite loop なので, 事実を先に書く. ( 停止性の検証は引数条件を設定した上, 帰納的に. この例の場合は,instanceof の第 2 引数に基底項を束縛させたときの停止性を検証できればDBとしては十分 ) */ 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,[])) :- instanceof(ptuple,p), instanceof(qtuple,q). instanceof([ptuple,qtuple], join(p,q, [c(pattr,qattr) Cs])) :- instanceof(ptuple,p), attr(ptuple,pattr,v), instanceof(qtuple,q), attr(qtuple,qattr,v), instanceof([ptuple,qtuple], join(p,q, Cs)). 17
6 演習問題 2 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 を定めよ. P2.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)) が成功するために必用なルールを追加しなさい. 18