Integrating Logic Programs and Schemata
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 340-341.
© 1983 International Joint Conferences on Artificial Intelligence
Abstract
Willi . (l lorn cl :tusc'/Sd le rrl a ll.• · pr< 'SI' IILat.i on l .a n p; u ap;e ) is l.l1< ' res11ll. ol' an l'llo r t. l.o I'OIIIhin•· t.he llll'Liwd s or lo p; ic: pro f\ r:tflln: il q; an d s• ·lll' lll:t-basPd knowledge n·pr<·s<·nl.al.ion int.o a s ingle hy brid sys l.l' lll . l11 IISII.L, knowl• · d t~ ' ! •·x pr essed in sc hem :tl. :t <":til hP ar•'< ''" l'd durin p; t.be ex••cul.ion or lo t~ie programs, and t.he rel.ri<•v:d .. r I h< • va lu< 's or a slot. in a Sl'lll' lll a ra11 involv<! !.he exee ul.ioll or lo gic: prop;ra iiiS !.bat. at.t.e 111pl. l.o d ed 11 1:e Lh< ! va lu< !S prior t.o r!' so rtin ); t.o inhNiLan<'<', s honld Lh<• s lol. IH' !'Il l pLy. IISI/.L supports t il e illq>II ' III PIIL aL ion or prOf';I";J.JliS LhaL Lake :u l va i!L ar~e or the bl'sL l'< ·a Lur!'s or Ll1< · lo giral and obje~:L - orie11Led approachi!S t.o k11 ow ledg <! represe nl .al.ion.
- Attardi , G., and Simi, M. Semantics of inh eritance a nd at- tribution s in the descrip tion system Ornega. AI rnerno 612, A rt.ificial lntdli ge n<:c Laboratory , MIT, I 98 I.
- llrachrnan, ILl., and Levesque, li . .J. Competence in knowl- edge represe ntation. !'roe. AAAI -82, I 982, pp.l89 -192.
- ChesLer, D. IICI'RVH. : an interpreter for logic programs. !'roc. AAAI-80, I 980, pp. 93 95.
- Fox, M.S. On inheritance in knowledge re presentatio n. !'roc.! J.JCAI-79, UJ79, pp. 282 281.
- Fri sc h, A.M., an d Allen, .J.l•'. Knowledge retrieval as limited infen,ncc. !'roc. !ilh Conference on Automated Deduction, I 982, pp. 271 •29 I.
- llayes, l'.J. The Logic or Jlrames. In Frame Conceptions and Text Understanding, Metzing, D., c,I., de Gruytcr, 1979, pp. 16 Gt.
- Kowalski, l~. A . Logic for Problem Solving. Norlh-llolland, I 979.
- Moore, ILC. D-SCJtiPT: a computational theory of descrip- tions. !'roe. IJCAT-73, I 97:l, pp. 223-229.
- ltich, C. Knowled ge rcprcsen LaLio n languages a nd predicate calculus: how Lo have your cake and caL it too. l'roc. AAAI- 82, 1982, pp. 193 -196.
- Seott., D. Existence and description in formal• logic. In Bertrand Russell: Philosopher of the Century, Schoernan, R. , ed., Allen and Unwin, 1967, ch. 16, pp. 181 -200.
- Warren, D.H. Prolog on the DECsyslern-10. In Expert Sys- tems in the Mirro -l\'lccl ronic Age, Michie, D., ed., l•:dirr- bnrgh University l'reso<, 1!)7!J .
- Warr<~n, D.ll. l•: lli ,:ienl. pro!".l'ssi II !\ of intNadivc relational datab:rs<' qrrPri<'S ('XJlr''ss<'d in Iogie. T edr. ll.q>t. lfJfi, De- part m e nt ol' Art.ilieial lnL e lli ~.>;c rH '<', University of l•:dinburg h , I !J8 I.
- Wright, .I.M., a nd Fox , M.S. Sll.l. / l.fJ lJst'r Manual. T ce h . H.Ppt.., ltoboties ln sl.it utt', Ca'rnt'gi('-Mellon University, 1!)8:\.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
Integrating Logic Programs and Schemata·
Bradley P . Allen J.M. Wright
Intelligent Systems Laboratory The Robotics lnstitutc Camcp;ic-!Vlcllon University
Pittsburgh, Pennsy lvania U.S.A. 15213
the us<·r to exploit. 1.11<! sl.rc·n;·;l.h ,; ol' <'il.h<·r kind ol' r<·prcs<,nl.al.ion as h<' rhoosPs, it h:>s !.111' di s:ulvanl.:>j\<' l.li:tl l.he sl. rl'n!!;l.hs ol' one rPpr··sent.al.ion are no I. brought. Lo bPar on I. he w<·ak ness<'s or t.hc ol.her.
Ano t her proposal is t.o impl err1ent. inlll'ril.:uH:<'-Iike inl'<'r<"l<!C in a lot\i t:a l rep resPntal.ion. This approach st.ems l'rom l.he pcr <'<'pi.ion t.hat sehen1ata ar<' simply a synl.act.ie variant. ol' Iogie [fl]. A sysi.PIIl ol' t.his sorl. has bel'll described by l'riseh and Allen [f>]. This approach provides an it nswer l.o i.he imprP<: ist! seman tics ol' ad-hot: iniH:ril.ance rrll:<·.hani sms, bul. leaves llli:llldressed i.h<· prohl<'lll or i.he usability ol' l:tr!!;e hut unst. ruet.ured logical k IH>wl<:dge bases.
Thi s J>:IJH:r desnibl's a system <·ailed IISH.L, which atll'll!Jli.S t.o uniry t.he schelna-bas<·d and logical approa<:hes Lhrough t.he inl.<:grat.ioll ol' all ill l.<!rprder l'or Iogie pro!!; r:liiiS wil.h a schema b:~ sl'd knowl ed!!;l' r<'pr<>Sc lll.al.ion. We lirsl. describe i.he compo nent. sysl.<,rrls or IISil.l, and show how i.ltey are modifi ed a 11d i.h<!n cn111hincd Lo ereal.e t.h<· un ifi<:d syst.em. Thc11 W<' di sc uss t.h e llH:ril.s ol' IISil.L as a Iogie programmi11 g la11guage and as a se hema- based knowl edge rl'presenl.al.ion , indic :tLing whl're II SRL addresses i.hc probll'ms rai sed above. W<! dos<' by indie:tl.ing di reelions l'or ful.ure researeh.
II THE COMPONENT SYSTEMS
A. The SRL knowledge representation
SW, (Seh ema l~cprese11lalio11 Language) [I :1] is a schcma hasrd knowledge rcprescul.at.ion wrillcn in Fran~ Lisp. SI{L is used l'or l'adory and organizati onal 1110deling i11 proj ec ts in the illl.<!lligciiL Systems La.boralory ol' Lhe l{obot.i<:s fn st.it.ut.c. A sc hema in SI{L is composed of a name (print.ed i11 bold l'ont.) whieh dcnolcs t.hc object. represented by Lhe schema and a scl ol' slols (printed in ,,/a nl.cd l'onl). Slots arc used Lo de11ote lhe a lt.ribules of l.hc schema as wdl as relations along whi<:h inhcri l.anee may Lake place. l~ach slot may have a ny number of values, and can have a schema, eallcd a ml'ta-seherna, associated with il. The slols ol' Lhe mcl.a-sehema (printed in italic fo11t) a rc used Lo sl.or<' met:t-inf'orm:tl.ion about. i.hc slot.. i\11 example of' an SI{L sc hema is t.he chameleon schema shown in Figure l.
{ { chameleon is-a: lizard habHaL: tropical co/or: green description: chameleon-color /oc.1Lion: } }
ABSTRACT
Willi . (l lorn cl :tusc'/Sdlerrl a ll.· ·pr<'SI'IILat.i on l.anp;uap;e) is l.l1<' res11ll. ol' an l'llor t. l.o I'OIIIhin·· t.he llll'Liwds or lop; ic: prof\ r:tfll n: ilq; and s··lll'lll:t-basPd knowledge n·pr<·s<·nl.al.ion int.o a single hybrid sys l.l'lll . l11 IISII.L, knowl· · d t~ ' ! ··xpressed in schem:tl.:t <":til hP ar·'<''"l'd durin p; t.be ex··cul.ion or lot~ie programs, and t.he re l.ri<·v:d .. r I h<· valu<'s or a slot. in a Sl'lll'lll a ra11 involv<! !.he exeeu l.ioll or logic: prop;raiiiS !.bat. at.t.e 111pl. l.o ded 11 1:e Lh<! valu<!S prior t.o r!'so rtin ); t.o inhNiLan<'<', shonld Lh<· slol. IH' !'Ill pLy. IISI/.L sup ports t il e illq>II'III PIILaLion or prOf';I";J.JliS LhaL Lake :u l vai!Lar~e or the bl'sL l'<·aLur!'s or Ll1< · logiral and obje~:L- orie11Led approachi!S t.o k11owledg<! represenl.al.ion.
I INTRODUCTION
The dirh ol.omy b!'l.ween dec la ral.i v·· knowkdge n·presenl.a t.ions which use S<'ll l.<!nc:es ol' lot;ie ;·s t.heir basic: unit.s and t.hose which use sc hemata (a.k.a. rrames, unil.s, snipt.s) has h<!en a prohl<'lll l'or Ar:.ifkial lnt.ell ip;encl! si ne" t.he early IU70's. Aside l'ro111 Lhe dille rent. philosophical l:lllllllliLnlelll.s i111pliciL in dLhN kind ol' approaeh, using one or t.he other has ce rtain pragmatic: eo ns<·qne n et~s.
I< nowl<'d[~<! b:tses ~:o n sLr uct.ed usin t; sehcm:tl.a :tre g<·ncrally easy l'or JH'ople t.o comprehend hceau sc ol' Lhei r objed-o ri cnt.ed, l.axonomi<: st. ru<·.l.ure. l Jnl'orLunat.ely, most. sehcma- b:ts<!d rep rcsent.at.ions have no g<!ner:tl inl'crence mech a nisms ot.her Lhan inlll·rilancc. FurLhermor<', t.be S<'lllant.ies ol' sueh represcnlat.ions is usu:tl ly unel r:ar, and l'r<"JIIent.l y their only ri go rou s deseriplion is t.he inlpl<·rrfl!nLat.ion code ilsclf.
On t.he oi.hl'r hand, knowkdg<' basi's <:o nsisl.ing ol' s<,nl.cnces ol' lo}!;it: have a dearly defi111!d scmanl.ic:s and almost. always have a gen<·ral ini'Nence meeh:tnisn1 (i.e. , a theorem prove r) wit.h well llfHkrsl.ood properties. I fowcver, LhP lal'k ol' sl. ruct.urc in logic knowiPdge bases makes it. hard t.o l'or jH'!ople l.o grasp what. Lhcy eo nl:tin when t.hey are ol' suflieienl. sir-e Lo be useful in pracli<:al applical.ions. Suc h repn·senl.al.ions a lso laek the del'ault. reason inf~ al>ilil.y whieh is avai lable in sch<"ll:l-based represenlalions through the use ol' inheritance.
Tl1e problem that. prPsc nl.s it.sell' is how l.o build a knowl edge r<'pr<'scnLal.ion whieh has t.he advantages ol' both approaches and avoids their di sadvanl.:lf;cs . llraelunan and Levesque [2] anti l{i ch [\J ] have proposed systems in whir.h knowledge is stored in Lwo parallel represenlat.ions, one logical and Lhe olher schcrna- . based. An cxplieit. int.erl'aec between Lhe two rPpresenlalions a l lows ehangcs Lo knowledge in onP Lo be incrementally translated inlo Lh<· olher. While Lhis app roach has Lhc merit of allowing ValuPs l'or l.he slots in a sch<·rna n1ay IH· obtained l'rorn slols 111 ol.lll·r sch<'nJal.a through inlll'ril.aJll'" rdalions . l'or exampl<·, 1.1"· value lropiral ean be inhnii.J·d in Llll' lr :IIJil.:tl, slot. ol' the srll!·nJa Claude (s l1own in Fit·;ure :!) t.hrout\h LlH· inlwrit.anl'e re laLion i11sf.:uwc l'rom t.he hahif.:tl, slot. in Llll' chameleon sdtema.
· Thi s paper dcseribcs work done in Lhc Intelligent Systems Laboratory ol' Lhe 11.obot.il's lnstit.ute a t. Carnegie-Mel lon Uni versity. This work was. supported by t.he Air l"orcc Ofnce of Scientific Hcsearch under conlracl F·1\Jfi:l0-82-J<OOL7.
- - ---- ------
{ { Claude illsbllcc: chatneleon h:t!Jiiai: color: /oc:tiio11: rock-59}}
Inheritance relations in SII.L are l.hcrnsclvcs reprPscnLcd by srlH·rrt a l.a . This allows Lhe dce\aralivc spceifi<:al.ion ol' idiosyn naLie inhcrilanec relalions by Lire user [1].
D. The HCPRVR Horn clause theorem prover
IICI'\~V\1. is a logic program inLe rprei.N wriU.en in Lisp. Us int\ IICI'I~VI~ is mrH:h like using i.he lop;ic programming language I'I~OLOC [II ], wil.h t.he cxeeplion !.haL Lhc synlax is somewhat simpler. A deseripl.ion of' Lhe operation of' IICI'RVR a nd of Ute syntax of logic programs in IICI'I~VI~ is given in [3] .
III INTEGRATING SH.L AND HCPRVR
A. Using knowledge in schemata in the interpretation of logic programs
The first. s lcp in inlegraling SI~L a11d IICI'RVI~ inlo IISRL is lo modify Lhe fundion l'ltoVt-: in IICI'RVI~, which conlrols Lhe problem rcdur:l.ion process used Lo inl.erprcl logic programs. The ddinilion of l'ltOVE is a\Lered so Lhat. if' Lhe formula for which an inst.ant.ial.ion is sought. slart.s wilh Lhe name of' a schema followed by Lhe name of a slot. in the schema, then Lhe axioms matched against. l.hc formula arc pbLa ined by int.crprl'Ling l.he slot. in the following way: A slot. s/ wilh n values in a schema sch can be considered as a set of' infix alomic formulae of Lhe form
(sch s/ valuet), (sch s/ value2), ... , (sch sl valuen)·
Under Litis interpretation, retrieving; the values of sl in sch is the same as finding all instantiations of the atomic formula
where x is a free variable. For example, the formula
(Claude habitatx)
(Claude !JaiJii:tL t.ropical),
sin ce t.ltc l!:tiJii.:Ji of' Claude is Lropi<:a\ by inheritance !'rom the l~:~lJii: ti slot. of chameleon.
B. Using logic programs to retrieve slot values in a schen1a
The second st.<'P in Lite int.e~rat.ion is to modify Lhe slot value access l'uncl.ion VAL\Jt ·:C in SltL. In Sll.L, Lhc values of the slot s/ in seltcrna sch arc rdrieved wilh a l'undion call of' t.he form
(VALUt ·:G sch s /) . VALlJt ·: C uses inhnit.:utee i\' v:tlues are not rlir<'ct.ly stored in s/. 1\owcver, in I ISH\ , WI' want. Lo be able to lirsL usc dcduet.ion Lo lind Lhe values o\' a slot. whenever appliea bk axioms arc in Lite knowled(!;e base, and then usc inheritance lo find reasonable default. value~ when dcduct.ion !'ails. Furlher more, we want. t.o place Lhc in\'onna t.ion \'or dcdueiJJ(!; the values of' slots Loget.lter wil.h Lhc slols in Lhe selremala.
We aehi cve this by ch :rn (!; ing Lit e definition of' V,\LI Jto:G so UraL il. aLLcmpl.s Lo dcduee slot. values bcl'on' inh e riting t.hcm. The knowledge UraL VALUI-:C uses t.o deduec values is expressed in the form o\' description schemata. The rol e of' deseriplion sehemala in a IISI~L knowledge base is roughly analogous to tha t. of ddinile and indclinile descriptions in a Llteory of first order Iogie [10]. Dcseriptions have been used in several knowi Prlgc rcpresenlat.ions as a melltod \'or Lhe dcelarat.ive specili<:a Lion of dedudivc proeedures, mos t. notably in D-SCJ~II'T [8] and Omq>;a [1]. An example of a dcseriplion in \ISI~L is Lhc schema chameleon-color, shown in Figure :1. chameleon-color ex presses Lite axiom Lhat Lhe color of' a chameleon is Lhat of Lhe object. on whieh Lhe chamel eon happens to be loca ted.
{ { chameleon-color iusi:wcc: description sc!Jcrrw: ch filler: clr variah/es: obj clauses: (ch /ocaUon obj) (obj color clr)}}
To illustrate the new procedure wiLh which IISilL obtains slot values, we show how the call (VALUEG Claude color) is evaluated.
First, the color slot of Claude is examined for a value. When none is found, the description slot in the meta-schema of the color slot is examined for a value. No value is found and no meta-schema exisls for the description slot but lhe value chameleon-color can be inherited \'ront the description slot. of' the rnda-s<·herna o\' the co/or slot. o\' chameleon. chameleon color is then int.erprel.cd by I ICI'I~Vl~ as Lhe axiom
(Claude eo/or r.l·r) < (Claude loc:tiiou obj)( obj color clr ).
The antecedent. of' this axiom is <:onslruded !'rom chameleon color by suhs t.iLuLin (!; Lite na nH' Claude !'or eaeh oeeurrenee of' the value of t.ltc sehcma slot. in Ute values of' Ute r:/a us"s slot. The eonscquent. is lhe at.omie formula whose l'ree variable is the value of' t.he filler slot. and whid1 repr"senLs a query \'or Lhe values of eo/or in Claude. The axiom is Lhen used to find all inst.artl.ialions of' (Claude color r:lr). VAI.Ut ·:C Lhen rclurns Lhe value obtained, which is the value in the co/or slot. of' Lhe sehema rock-59. lienee Claude as represented in t.he knowledge base will always have Lhe same color as Lhe object. on which he hapj>ens to be loealed. II' the rdricval of Lhe c:o/or of' rock-59 had failed, Lhe value green would have been inherited from chameleon.
IV TWO VIEWS OF HSRL
A. HSRL as a logic programming language
I!SRL permits the usc of IICPRVR in the way described in [:!], so Lite user is allowed to wrile standard logic programs. Pure I ICI'IlVR axioms can he also he combined wilh axioms referring Lo schcmala in a knowledge base and with axioms in the form of desc:riptions :bsoc:iated with slots in thP- schemata. l·:rn bcdding Iogie programs in descriptions provides a natural way to index axioms in the knowl<'dge base that people as well as programs can use. lleeause inheritance is used only when an allernpt to deduce the values ol" a slot using deseripLions has !"ailed, IISitL perl"orms del"ault reasoning in cxacl.ly those cases where it is needed.
B. HSRL as a schema-bnsed knowledge representation
An I ISIU, knowledge base that docs not contain descriptions behaves in exadly th<' same w;ty as a n Slt L knowledge base. I lowevcr, including dcscri ptions in a knowledge base allows the user to ex ploit IICI'ItVIt so that modus ponens inferenec, as well as inheritance, can lH' used in ;wswering queries in an incomplete knowledge base. One shorteorni ng of I !Sil.L is that it sidesteps the issue of clarity in the sernanLies of inheritanee by relying on the inherit.a ru:e a lgo rithm ol" sm,. llowcver, the idea or using Iogie programs in desnipLions to deduee the values of a slot ean be extended t.o include the use of descriptions Lo ded uce the default values of a slot. We will explore this technique in a future paper.
V SUMMARY AND FUTURE RESEARCH
IISILL is a hybrid logic/schernala knowledge representation which unifies t.he methodologies of schema-based knowledge rep resentation and logic programming. IL docs so in a way that \lSI '" LIH·, str .. rq.>;t hs or on<~ repr('Scntation to c:orrrpensatc for the wcakncss,~s ol" Lire other. lssu, ::; that w'' plan to deal with in l"u Lnre ext.(·nsions to IISitL arc the dynarnic ordering or elaUSI'S in ,lc,seriptions l"or inereasl'd dli eienc:y in n'Lricval [12], the usc of d"srri pl.ions Lo repr<~senl. d:d.a dept'ndenei('S in a knowl<'dge base, ext.c,nding 'ksrripl.i(il!s with arbitrary el;rus!'s '[7], and speei l"yin~ default. reasoning with dt'seript.ion s [f> ]. IISil.L is implemented in Franz Lisp runrring under lkrkdey UNIX on a Digita ll·:quiprnenL Corporation VA X II / 780.
ACKNOWLEDGEMENTS
Th" authors would like to thank Mark Fox, llill Sdrerlis, .laimc Carboru·ll, l'aul ll alcy, and .Jirrr Dri seoll for their helpful <:onrrnents on earlier drarts of this paper. Special Llnurks go Lo our !"olkagues in the Intelli gent. Systems Laboratory of the ltoboties lr: stit.ut.· ~ , whose eolleet.ive blood a nd brains went into the su perb res!':crch cnvironrnent Llrat mad e this work possible.
@inproceedings{ijcai1983p79,
title = {Integrating Logic Programs and Schemata},
author = {Allen, Bradley P. and Wright, J. Mark},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {340--341},
year = {1983},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1983/79},
}
TY - CPAPER TI - Integrating Logic Programs and Schemata AU - Allen, Bradley P. AU - Wright, J. Mark T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 340 EP - 341 UR - https://ijcai.org/proceedings/1983/79 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards