/* ---- This is an executable Prolog file -------- MINIDATR: A minimal core DATR engine in Prolog Dafydd Gibbon U Bielefeld gibbon@spectrum.uni-bielefeld.de August 1993 Bug removed September 1996 Notice: This document contains draft information from a section of a preliminary version of a VERBMOBIL deliverable (TP 5.3-P1). It is distributed in this form to assist partners in advance planning. This document contains a simple version of the core DATR inference engine in Prolog in order to illustrate the principles of DATR inference to Prolog programmers. Note that in minor details it departs slightly from DATR conventions: - nonstandard nodenames are permitted; - the knowledge base must be pre-sorted to permit 'longest path first' inference; - queries include the theory name. Note also that this is not a directly usable implementation: there is no user interface, no DATR-Prolog interpreter, no DATR-specific trace or debugging, no attention paide to efficiency, etc. The aim is to provide a minimal 'core DATR standard inference' interpreter in logical style. 1 Illustration of a DATR theory: a 'microlexicon' MINILEX.DTR Tablecloth: <> == Compound == lemma == (for covering) == "Table:<>" == "Cloth:<>". Table: <> == Simplex == lemma == (horizontal surface to put things on) == (t a b l e). Cloth: <> == Simplex == lemma == (variety of textile) == (c l o t h). Compound: <> == Word == generalisation == compound == ("" "" "") == ("" ""). Simplex: <> == Word == generalisation == simplex. Word: == generalisation == word. Theorems: Tablecloth:=(for covering). Tablecloth:=(variety of textile for covering horizontal surface to put things on). Tablecloth:=(t a b l e c l o t h). Table:=(t a b l e). Table:=undefined. 2 A Prolog translation of MINILEX.DTR: MINILEX.PRO knowledge base. Note the 'longest path first' reordering of the theory in Prolog. Tablecloth: <> == Compound == lemma == (for covering) == "Table:<>" == "Cloth:<>". */ datr_sentence(minilex,'Tablecloth',[ilex],[lemma]). datr_sentence(minilex,'Tablecloth',[relation],[for,covering]). datr_sentence(minilex,'Tablecloth',[modifier],[[gnp,'Table',[]]]). datr_sentence(minilex,'Tablecloth',[head],[[gnp,'Cloth',[]]]). datr_sentence(minilex,'Tablecloth',[],[[ln,'Compound']]). /* Table: <> == Simplex == lemma == (horizontal surface to put things on) == (t a b l e). */ datr_sentence(minilex,'Table',[ilex],[lemma]). datr_sentence(minilex,'Table',[meaning],[horizontal,surface,to,put,things,on]). datr_sentence(minilex,'Table',[orthography],[t,a,b,l,e]). datr_sentence(minilex,'Table',[],[[ln,'Simplex']]). /* Cloth: <> == Simplex == lemma == (variety of textile) == (c l o t h). */ datr_sentence(minilex,'Cloth',[ilex],[lemma]). datr_sentence(minilex,'Cloth',[meaning],[variety,of,textile]). datr_sentence(minilex,'Cloth',[orthography],[c,l,o,t,h]). datr_sentence(minilex,'Cloth',[],[[ln,'Simplex']]). /* Compound: <> == Word == generalisation == compound == ("" "" "") == ("" ""). */ datr_sentence(minilex,'Compound',[ilex],[generalisation]). datr_sentence(minilex,'Compound',[type],[complex]). datr_sentence(minilex,'Compound',[meaning], [[gp,[head,meaning]],[gp,[relation]],[gp,[modifier,meaning]]]). datr_sentence(minilex,'Compound',[orthography], [[gp,[modifier,orthography]],[gp,[head,orthography]]]). datr_sentence(minilex,'Compound',[],[[ln,'Word']]). /* Simplex: <> == Word == generalisation == simplex. */ datr_sentence(minilex,'Simplex',[ilex],[generalisation]). datr_sentence(minilex,'Simplex',[type],[simplex]). datr_sentence(minilex,'Simplex',[],[[ln,'Word']]). /* Word: == generalisation == word. */ datr_sentence(minilex,'Word',[ilex],[generalisation]). datr_sentence(minilex,'Word',[type],[word]). minilex(Node,Path,Value) :- datr(minilex,Node,Path,Value). /* 3 A DATR test theory, MINITEST.DTR This theory illustrates the seven cases of DATR standard inference. The relevant theorems are the following: A:<> = (via node A via node B via node C undefined). A:<1> = (via node A Rule 1). A:<2> = (via node A Rule 2). A:<3> = (via node A Rule 3). A:<4> = (via node A Rule 4). A:<5> = (via node A via node C Rule 5). A:<6> = (via node A Rule 6). A:<7> = (via node A Rule 7). A:<1 2> = (path <1 2> extends path <1>). A: = (via node A nested global path with a). A: = (via node A nested global path with rubbish). The MINITEST.DTR theory: A:<> == (via node 'A' B) <1> == <2> == <3> == <4> == <5> == <6> == <7> == == 'Rule 7' <1 2> == (path '<1 2>' extends path '<1>') == alpha. B:<> == (via node 'B' C) == 'Rule 1' == C: == C == == "C:" == "C" == "" == 'Rule 4' == "> == 'nested global path with a' == 'nested global path with rubbish'. C:<> == (via node 'C' D) <6> == 'Rule 6' == 'Rule 2' == 'Rule 3' == 'Rule 5'. D:<> == undefined == "". 4 A BNF description of core DATR syntax ::= | ::= : ::= . | ::= == ::= "<" ">" ::= nullseq | ::= | ( ) ::= nullseq | ::= atom | | " " ::= : | | ::= "<" ">" ::= | ' ' ::= ::= nullseq | ::= nullseq | ::= {:, <, >, =, (, ), ", .} ::= {char(0),...,char(127)} ::= {char(33),...,char(127)} | \ ::= - ::= {A,...,Z} ::= - 5 MINITEST.DTR to MINITEST.PRO translation (outline) ::= datr_node(,,,). ::= Prolog list of atoms, perhaps empty, e.g. [], [a], [attribute,list] ::= Prolog list of expressions, perhaps empty, e.g. [], [a], [aa,bb], etc. ::= expression of one of the following types, corresponding to each of the 7 DATR inference rules as a Prolog atom or a tagged list: (1) (2) [lnp,,] for local node-path (3) [ln,] for local node (4) [lp,] for local path (5) [gnp,,] for global node-path (6) [gn,] for global node (7) [gp,] for global path ::= ::= Prolog atomic symbol ::= 6 Illustration of DATR-Prolog translation for MINITEST.DTR This line-by-line illustration includes "longest path first" pre-sorting: /* A:<1 2> == (' path <1 2> extends path <1>'). */ datr_sentence(minitest,'A',[1,2],[' path <1 2> extends path <1>']). /* A:<1> == . */ datr_sentence(minitest,'A',[1],[[lp,[one]]]). /* A:<2> == . */ datr_sentence(minitest,'A',[2],[[lp,[two]]]). /* A:<3> == . */ datr_sentence(minitest,'A',[3],[[lp,[three]]]). /* A:<4> == . */ datr_sentence(minitest,'A',[4],[[lp,[four]]]). /* A:<5> == . */ datr_sentence(minitest,'A',[5],[[lp,[five]]]). /* A:<6> == . */ datr_sentence(minitest,'A',[6],[[lp,[six]]]). /* A:<7> == . */ datr_sentence(minitest,'A',[7],[[lp,[seven]]]). /* A: == 'Rule 7'. */ datr_sentence(minitest,'A',[seventh],[' Rule 7']). /* A: == alpha. */ datr_sentence(minitest,'A',[param],[alpha]). /* A:<> == (via node 'A' B). */ datr_sentence(minitest,'A',[],[' via node A',[ln,'B']]). /* B: == 'Rule 1'. */ datr_sentence(minitest,'B',[one],[' Rule 1']). /* B: == C:. */ datr_sentence(minitest,'B',[two],[[lnp,'C',[second]]]). /* B: == C. */ datr_sentence(minitest,'B',[three],[[ln,'C']]). /* B: == . */ datr_sentence(minitest,'B',[four],[[lp,[fourth]]]). /* B: == "C:". */ datr_sentence(minitest,'B',[five],[[gnp,'C',[fifth]]]). /* B: == "C". */ datr_sentence(minitest,'B',[six],[[gn,'C']]). /* B: == "". */ datr_sentence(minitest,'B',[seven],[[gp,[seventh]]]). /* B: == 'Rule 4'. */ datr_sentence(minitest,'B',[fourth],[' Rule 4']). /* B: == ">. */ datr_sentence(minitest,'B',[nest],[[lp,[elsif,[gp,[param]]]]]). /* B: == 'nested global path with a'. */ datr_sentence(minitest,'B',[elsif,alpha,a],[' nested global path with a']). /* B: == 'nested global path with rubbish'. */ datr_sentence(minitest,'B',[elsif],[' nested global path with rubbish']). /* B:<> == (via node 'B' C). */ datr_sentence(minitest,'B',[],[' via node B',[ln,'C']]). /* C:<6> == 'Rule 6'. */ datr_sentence(minitest,'C',[6],[' Rule 6']). /* C: == 'Rule 2'. */ datr_sentence(minitest,'C',[second],[' Rule 2']). /* C: == 'Rule 3'. */ datr_sentence(minitest,'C',[three],[' Rule 3']). /* C: == 'Rule 5'. */ datr_sentence(minitest,'C',[fuenf],[' Rule 5']). /* C:<> == (via node 'C' D). */ datr_sentence(minitest,'C',[],[' via node C',[ln,'D']]). /* D: == "". */ datr_sentence(minitest,'D',[fifth],[[gp,[fuenf]]]). /* D:<> == undefined. */ datr_sentence(minitest,'D',[],[' undefined']). minitest(Node,Path,Value) :- datr(minitest,Node,Path,Value). /* Outline of the MINIDATR.PRO inference engine datr(Theory,Node,Path,Value). - defines initial DATR global and local query environments - 1 clause datr_connect(Theory,Gnode,Gpath,Lnode,Lpath,Value). - accesses DATR theory with query environments - 1 clause datr_rhs(Gnode,Gpath,Lnode,Prefix,Suffix,Rhs,Value). - evaluates RHS of DATR equations as lists - 2 clauses datr_rule(Gnode,Gpath,Lnode,Prefix,Suffix,Descriptor,Value). - 7 DATR inference rules - 7 clauses, for evaluation of atoms and of local and global node-path, node, and path descriptors. append(Prefix,Suffix,Whole). - expresses RHS sequence evaluation and path extension - 2 clauses (standard definition). The following queries illustrate standard DATR inference. Query Response minitest('A',[],X). X = [ via node A, via node B, via node C,undefined] minitest('A',[1],X). X = [ via node A, Rule 1] minitest('A',[2],X). X = [ via node A, Rule 2] minitest('A',[3],X). X = [ via node A, Rule 3] minitest('A',[4],X). X = [ via node A, Rule 4] minitest('A',[5],X). X = [ via node A, via node C, Rule 5] minitest('A',[6],X). X = [ via node A, Rule 6] minitest('A',[7],X). X = [ via node A, Rule 7] minitest('A',[1,2],X). X = [ path <1 2> extends path <1>] minitest('A',[nest,a],X). X = [ via node A, nested global path with a] minitest('A',[nest,b],X). X = [ via node A, nested global path with rubbish] 7 Code for the MINIDATR inference engine Note that this minimalistic core DATR inference engine allows nonstandard node-names, has no DATR variables, and does not include the 'longest path first' default connection condition. This means that the 'longest path first' ordering must be pre-defined in the Prolog knowledge base. */ datr(Theory,Node,Path,Value) :- atomic(Theory), atomic(Node), nonvar(Path), atompath(Path), var(Value), datr_connect(Theory,Node,Path,Node,Path,Value),!. atompath([]) :- !. atompath([First|Rest]) :- atomic(First), atompath(Rest). datr_connect(Theory,Gnode,Gpath,Lnode,Lpath,Value):- datr_sentence(Theory,Lnode,Prefix,Rhs), append(Prefix,Suffix,Lpath),!, datr_rhs(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,Rhs,Value). datr_rhs(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,[],[]). datr_rhs(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,[First|Rest],Value) :- datr_rule(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,First,First_value), append(First_value,Rest_value,Value),!, datr_rhs(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,Rest,Rest_value). /* DATR Inference Rule 1 */ datr_rule(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,Expr,[Expr]) :- atomic(Expr). /* DATR Inference Rule 2 */ datr_rule(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,[lnp,Node,Path],Value) :- datr_rhs(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,Path,Path_value), append(Path_value,Suffix,Extension), datr_connect(Theory,Gnode,Gpath,Node,Extension,Value). /* DATR Inference Rule 3 */ datr_rule(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,[ln,Node],Value) :- append(Prefix,Suffix,Extension), datr_connect(Theory,Gnode,Gpath,Node,Extension,Value). /* DATR Inference Rule 4 */ datr_rule(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,[lp,Path],Value) :- datr_rhs(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,Path,Path_value), append(Path_value,Suffix,Extension), datr_connect(Theory,Gnode,Gpath,Lnode,Extension,Value). /* DATR Inference Rule 5 */ datr_rule(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,[gnp,Node,Path],Value) :- datr_rhs(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,Path,Path_value), append(Path_value,Suffix,Extension), datr_connect(Theory,Node,Extension,Node,Extension,Value). /* DATR Inference Rule 6 */ datr_rule(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,[gn,Node],Value) :- %% Bug. Removed 11.09.96. DG %% append(Gpath,Suffix,Extension), datr_connect(Theory,Node,Extension,Node,Extension,Value). /* DATR Inference Rule 7 */ datr_rule(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,[gp,Path],Value) :- datr_rhs(Theory,Gnode,Gpath,Lnode,Prefix,Suffix,Path,Path_value), append(Path_value,Suffix,Extension), datr_connect(Theory,Gnode,Extension,Gnode,Extension,Value).