Term Description: A Simple Powerful Extension to Prolog Data Structures
Proceedings of the Ninth International Joint Conference on Artificial Intelligence. Logic Programming. Pages 708-709.
© 1985 International Joint Conferences on Artificial Intelligence
Abstract
Term desc::riptial is a sinple,extensicn of tenns. For 9Xallple, functicnal. ootaticn and lazy executicn of a prograu is i.nt:roclJoed in a very natural mamer withcut changing the basic mec:hanism of the oarp.ltaticn, such 88 unificaticn and bacJctrack1ng. Especially, the readability of functicnal. 11s introduoed withcut actually int:rccb::ing functicnal. cxn:epts.
- Takashi Chi.kayama.: ESP --Exten1ed Self- conta1ned PROUJG --as a Prelimi.nazy Kernel Languages of Fifth Generation Q:uplters New Generaticn Ctllp.rting, Vol. 1, ti:>. 1, ~.11- 24 (1983)
- Keith L. Clark, . Steve Gregory: PARUJG: Parallel Prograrrmiiq in "Wgic, Research Report, Dept. of Carp..iting, Ilq;lerial College (1984)
- Kemeth M. Kahn: Uniform --A LangtJage Based up::ll'l Unif:1catian which Unifies (H.Jch of) LISP, Prolog am Act 1, IJCAI-VII, ~• 933-939, (1981)
- William A. Kom.feld: Et2Uality :for Prolog, Proc. of IJCAI-VIII, ~• 514-519 (1983)
- Hideyuki Nakashima: Prolog/KR -Language Features, Proc. of 1:he First Intematicna.l Logic PrograrrminJ Cl:nference, ~• 65-70 (1982)
- Fhld Shapiro: A &lbset of Concurrent PROilJG am Its Interpreter, ICDI' TR-()()3 (1983)
- Etsuya Shibayama.: perscnal OCIRlUlicaticn (1984)
- Hisao Tamaki: Semant:1cs of a "Wgic Progr<D- m:!Iq Laa}uage with a Reducibility Predi- cate, Proc. of 1:he 1984 Internaticna.l Sym- poeiun cn Logic Programning, pp. 259-264 (1984)
- D. A. 'l'ul:ner: The Semant:1c Elegarx::e of Applicative Languages, Proc. Q:nf. cn Func- ticna.l PrograrrminJ Languages and Cl:rlprl::ar Architecture, ~-85-96 (1981)
- David H. D. Warren: Higber-Drder Extens:l.ans to Prolog -Are t:hey Needsd?, D.A.I. Research Paper t-«:>.154, university of Edin- b.Jrgh (1981)
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.
1. Equali ty and Reducibili ty
Tenn descripticns introduce equali ty for tenns in a very efficient Wcr.f CJCilP8r9d with other approaches [Kahn 81, Kol:nfeld 83]. Olecking the equali ty is nothing m::>re than executin;J a pro gram.
Let us cx:nsider definin;J m::>re than two tenns equal. To assert that norning_ star and evenin]_ star in fact refer to the same object "Verrus", we may say:
norning star( venus).
eveninJ-star( venus).
Then the - three tenns: "!norning-star", "!evenin]-star" and "venus" beccme unifiable. A tenn descripticn ! p may be trought of as an intenticn of p ( thus ! may be regarded as an intentional operator).
Let us cx:nsider aDJther example. What is expressed by a program such as:
animal(X): -bird(X).
animal ( X) : -fi1SI'IIlal ( X) ·
bird( X) : -penguin( X) ·
bird(X): -canacy(X).
penguin(p001).
is rot equal.ity OOt ra:Juc:il:>ility [Tamaki 84, Shibayama 84] · A tenn, ! animal is reducible to !bird, which is further reducible to !penguin, which is finally reducible to p001. A set of reducible tenns ( intenticns) of ! animal is a super set of the set of reducible tenns of !bird.
In the case of "norning star" and "evening star 11 , two different te:l:nS are unified through a uniqua individual 11 VE!I'1US 11 · This can be d:rle very efficiently. In the case of 11 birds 11 cn the other hand, the nunbers of individual is lllJCh. larger than the original tenns. 'Iherefore unify in;J !animal and !bird usually requires lots of backt::racJdni1. Further research is required here.
2. Equatioos
In I<RC [Turner 81], equaticns in which the sane tenn appear cn both sides such as
integers = 1: ( addl integers)
are allowed*. 'Ihe tenn descripticn also c::overs this kind of equaticns. Since 11 integers 11 is a functicn with rx> argunent, it is translated into Prolog predicate with cne argument to return its value:
integers( [1: !map(addl, !integers)]).
"Map 11 is used to apply "addl 11 to all the elements of a list, and defined as:
map(Pred,[~Y],[!Pred(X): !map(Pred,Y)]).
'Ihe ocrrp..ltaticn is infinite and hence we need II lazy executicn. II
D. Lazy Executicn and Infinite Data Stxucture
A demand driven lazy executicn is realized naturally as 11 lazy unificaticn 11 of tenn descrip ticns. Sirlee a variable is unifiable to &rri tenn, it is also unifiable to 8fri tenn descrip ticns. 'Iherefore, there is rx> need to execute the cx:nstraint when a tenn descripticn is unified with an uninstantiated variable. The descripticn is executed cnly when the result is actually necessary.
As the direct ocnsequence of the lazy execu ticn, indefinite data structure is mani.Illlatable. 'Ihe followin;J exanple depicts the use of the
infinite list in 11 Sieve of Eratosthenes 11 ·
'Ihe predicate 11 integers 11 produces an infin
i te list of integers beginning N · .
integers(N, [N !integers( !addl(N) )]) · llbte the recursive call of 11 integers 11 itself as the tenn descripticn in the seoct'ld argument. If this call is noved to the body, a call for "integers 11 runs infinitely and never returns. When the tenn descripticn is used, cnly the min:l.nun part required is ocrrp..1ted ( demand driven ocrrp..ltaticn).
* 11
: 11 is the oc:n:::atenaticn q;lerator.
'lhe predicate 11 sift 11 filters a list of integers using 11 sieve". cnl.y th::lSe which are oot prcxiJcts of 1:he previc:us elements rema.in in 1:he secend argunent.
sift( [PI Rest], [PI !sift( !sieve(P,Rest))]).
- "Sieve 11 rem:JVeS th::lse which are products of P. sieve(P, [X:remainder(X,P,O): Y], !sieve(P, Y) ). sieve(P, [X: Y], [X: !sieve(P, Y)]).
Now a call integers(2,I),sift(I,P). ratums P an infinite list of prime nunbers.
'lhere are other, special pu:pose, primitives to deal with infinite data structures: Prolog-li [Col..merauer 1982] has 'geler' (freeze) to manipu late infinite data structures; Parlog [Clark and Gregary 1984] and Ccrlcul:Tent Prolog [Shapiro 1983] have read ooly anootatioos for variables which provides syrx:hralizaticn ~ processes.
rv Iuplementation
A subset of 1:he tenn desc:ripticn is :inple mented cn Uranus, a successor of Prolog/I<R [Nakashima 82]. cnl.y th::lse which is written in functicna.l ootatioos are surp:xrted.. A tenn desc:ripticn !p(X) is written in Uranus as [p *x].
'lhis ootaticn is extended to 1:he tcp-level of Uranus. A user can type in a predicate call just as if it is a functicn. For exatple,
[+ 1 3] eclxJes back 4. If we define primitive lisP furx: ticns as predicates, then 1:he user can use 1:he system just as if it were Lisp, just by using 11 [" and II] II instead Of II ( II and II) II o Here are scme exanples:
[ClCXlS 1 2] --> (1 · 2)
[car [ClCXlS 1 2]] --> 1
[car (OCI"lS 1 2)] --> ClCXlS
[append (1 2) (3 4)] --> (1 2 3 4) Note that we oo oot need 11 ' 11 · we can s:inply use 11 ( II and II ) 11 to den;)te 8 quoted list.
In usual, 1:he desc:ripticn is replaoed by 1:he result cnoe it is exec::uted. '1bJs 1:he nultiple exec:uticn of 1:he sane desc:ripticn is avoided. However, in scme cases, i t is .i.lq;loesible to optim:l.ze 1:he executicn autcmatically. User sl:nlld be careful and respcrlSible for 1:he effi ciency.
As 1:he final oc:mnent cn :inplanentaticn, it is worth oot1ng that 1:he :inplanentaticn of lazy unificaticn cn Prolog wi th structure aharing is efficient. Sinc:e 1:he form is shared, delayirg 1:he unificaticn d:>es oot require extra storage. 'lhe s lma.:JE! required for sav1ng 1:he envircnnent is just as large as is required for backtrack1ng.
v. Ocncl~
Prolog with texm deacripticn may oot be PJre Prolog f'DI rrore. Howewr, 1:he basic mechanian of 1:he oc:.rrpJta.ticn such as unificaticn and bac:k tracJd.ng are 1:he sane.
If Prolog ever needs arr.f extensicn such as introducing functials, it stxluld be kept as snal.l as poesib1e and that 1:he tenn desc:ripticn is cne
of 1:he snallest solutials.
'lhe auttxir gives many thanks to Sataru Tall.lra and Kdd.chi Futatsugi at ~, Koichi 1'\rrukawa. at ICDI', Taku Takeshima at Fujitsu, Ka.zurxlri Ueda at NEX::, and Jlll!lliJers of ICDI' \IC2, especially Etsuya Shibayama, for their detailed discuss:lcns.
- (1] Takashi Chi.kayama.: ESP -- Exten1ed Self conta1ned PROUJG -- as a Prelimi.nazy Kernel Languages of Fifth Generation Q:uplters New Generaticn Ctllp.rting, Vol. 1, ti:>. 1, ~.1124 (1983)
- (2] Keith L. Clark, . Steve Gregory: PARUJG: Parallel Prograrrmiiq in "Wgic, Research Report, Dept. of Carp..iting, Ilq;lerial College (1984)
- Kemeth M. Kahn: Uniform -- A LangtJage Based up::ll'l Unif:1catian which Unifies (H.Jch of) LISP, Prolog am Act 1, IJCAI-VII, ~· 933-939, (1981)
- [4) William A. Kom.feld: Et2Uality :for Prolog, Proc. of IJCAI-VIII, ~· 514-519 (1983)
- Hideyuki Nakashima: Prolog/KR - Language Features, Proc. of 1:he First Intematicna.l Logic PrograrrminJ Cl:nference, ~· 65-70 (1982)
- Fhld Shapiro: A &lbset of Concurrent PROilJG am Its Interpreter, ICDI' TR-()()3 (1983)
- Etsuya Shibayama.: perscnal OCIRlUlicaticn (1984)
- [8) Hisao Tamaki: Semant:1cs of a "Wgic Progr<D m:!Iq Laa}uage with a Reducibility Predi cate, Proc. of 1:he 1984 Internaticna.l Sym poeiun cn Logic Programning, pp. 259-264 (1984)
- D. A. 'l'ul:ner: The Semant:1c Elegarx::e of Applicative Languages, Proc. Q:nf. cn Func ticna.l PrograrrminJ Languages and Cl:rlprl::ar Architecture, ~- 85-96 (1981)
- David H. D. Warren: Higber-Drder Extens:l.ans to Prolog - Are t:hey Needsd?, D.A.I. Research Paper t-«:>.154, university of Edin b.Jrgh (1981)
@inproceedings{ijcai1985p138,
title = {Term Description: A Simple Powerful Extension to Prolog Data Structures},
author = {Nakashima, Hideyuki},
booktitle = {Proceedings of the Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-85}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Aravind Joshi},
pages = {708--709},
year = {1985},
note = {Logic Programming},
url = {https://ijcai.org/proceedings/1985/138},
}
TY - CPAPER TI - Term Description: A Simple Powerful Extension to Prolog Data Structures AU - Nakashima, Hideyuki T2 - Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85 PB - International Joint Conferences on Artificial Intelligence PY - 1985 SP - 708 EP - 709 UR - https://ijcai.org/proceedings/1985/138 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: