DVIOUT-flogic-kb-new

Size: px

Start display at page:

Download "DVIOUT-flogic-kb-new"

こうだいふじした
6 years ago
Views:

1 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

2 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

3 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

4 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

5 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

6 2.4 推論例 ( 述語も含む ) DDB 同様に, 述語も許すオブジェクト間の関係, オブジェクトの性質引数はOIDを表す項推論規則もDDBと全く同じ highincome(p) :- P[income V], V > :- highincome(jim). the above rule with P=jim :- jim[income V], V > :- jim[income V], V> 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> jim:workingst, workingst::parttime :- jim[wageperhour W;monthlyWHour H], V is W*H, V> jim[ wageperhour 1000; monthlywhour 40], W = 1000, H = 40 :- V is 1000*40, V> V = : > 失敗! 6

7 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

8 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

9 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

10 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 ] :- payment([jim],p1), P is P1.... :

11 3.5 A note on 実装と継承 Jave: クラス階層メソッド定義の継承単一継承 : 定義衝突回避同一パス上でオーバーライドインタフェース : メソッド型制約と定数のみ抽象性 ( インスタンス化不可 ) 実体オブジェクトは実装側で生成実装クラス : 型制約を継承し実装抽象クラス : 抽象性を持つクラスで, インタフェース組込可 F 論理 with 型制約多重継承はOK( 多重解 ) インタフェースは, メソッド型制約 X:hasIncome[income int] を実装クラス fulltime に継承させる形で, 書式を決めれば OK インタフェースはクラスではないと書いてあるが. 言語仕様上は, 確かにクラスとは異なる. つまり, インタフェースは言語的規制を受けたクラスであり, コンパイル時に規制 ( 抽象性, 実装クラスでの実装義務, などを守っているかをチェックしかし, 実行時は一つのクラス. 何ら区別はないインタフェースは, 多態性の実現のためだけでなく, クラス間の文字通りのインタフェース 11

12 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

13 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

14 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

15 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

16 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

17 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

18 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

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション基本 Java プログラミング演習第 13 回担当 : 植村今後の予定 7/15 第 13 回今回 7/22 第 14 回小テスト ( クラス ) 7/29 第 15 回総まとめテストレポート提出期末テストの時間割に Java のテストの欄がありますが無視してください再テストはまた別途連絡いたします 2 CHAPTER 11 はじめてのクラス前回の復習クラスクラスを構成する要素