Tabled logic programming: Difference between revisions

Revision as of 21:35, 27 October 2023

Revision as of 21:50, 27 October 2023

Line 4:

== History ==

The adaptation of tabling into a logic programming proof procedure, under the name of Earley deduction, dates from an unpublished note from 1975 by [[David H. D. Warren,|David asH.D. documentedWarren]].<ref>{{Cite bybook |last=Pereira |first=Fernando C. N. |title=Prolog and Natural Language Analysis |last2=Shieber (Reference|first2=Stuart PereiraM. |publisher=[[Center for the Study of Language and Shieber1987).Information]] |year=1987 |___location=Stanford |pages=185--210}}</ref> An interpretation method based on tabling was later developed by Tamaki and Sato (Reference Tamaki and Sato1986), modelled as a refinement of SLD-resolution.<ref>{{Citation |last=Tamaki |first=Hisao |title=OLD resolution with tabulation |date=1986 |url=http://dx.doi.org/10.1007/3-540-16492-8_66 |work=Lecture Notes in Computer Science |pages=84–98 |access-date=2023-10-27 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |isbn=978-3-540-16492-0 |last2=Sato |first2=Taisuke}}</ref>

David S. Warren ^Footnote5 and his students adopted this technique with the motivation of changing Prolog’s semantics from the completion semantics to the minimal model semantics.

Tabled [[Prolog]] was first introduced in [[XSB]].<ref>{{Cite journal |last=Sagonas |first=Konstantinos |last2=Swift |first2=Terrance |last3=Warren |first3=David S. |date=1994-05-24 |title=XSB as an efficient deductive database engine |url=http://dx.doi.org/10.1145/191843.191927 |journal=ACM SIGMOD Record |volume=23 |issue=2 |pages=442–453 |doi=10.1145/191843.191927 |issn=0163-5808}}</ref> This resulted in a complete implementation of the [[well-founded semantics]], a three-valued semantics that represents values for true, false and unknown.<ref>{{Citation |last=Rao |first=Prasad |title=XSB: A system for efficiently computing well-founded semantics |date=1997 |url=http://dx.doi.org/10.1007/3-540-63255-7_33 |work=Logic Programming And Nonmonotonic Reasoning |pages=430–440 |access-date=2023-10-27 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |isbn=978-3-540-63255-9 |last2=Sagonas |first2=Konstantinos |last3=Swift |first3=Terrance |last4=Warren |first4=David S. |last5=Freire |first5=Juliana}}</ref>

The concept of tabled Prolog was introduced in [[XSB|XSB Prolog]] (Sagonas ''et al.'' Reference Sagonas, Swift and Warren1994). This resulted in a complete implementation (Rao ''et al.'' Reference Rao, Sagonas, Swift, Warren, Freire and Notes1997) of the [[well-founded semantics]] (Van Gelder ''et al.'' Reference Van Gelder, Ross and Schlipf1991), a three-valued semantics that represents values for true, false and unknown.

== References ==

{{reflist}}

=== General References ===

* {{Cite journal |last=Körner |first=Pjilipp |last2=Leuschel |first2=Michael |last3=Barbosa |first3=Joao |last4=Costa |first4=Vitor Santos |last5=Dahl |first5=Veronica |last6=Hermengildo |first6=Manuel V. |last7=Morales |first7=Jose F. |last8=Wielemaker |first8=Jan |last9=Diaz |first9=Daniel |last10=Abreu |first10=Salvador |last11=Ciatto |first11=Giovanni |date=2022-05-17 |title=Fifty Years of Prolog and Beyond |url=http://dx.doi.org/10.1017/s1471068422000102 |journal=Theory and Practice of Logic Programming |volume=22 |issue=6 |pages=776–858 |doi=10.1017/s1471068422000102 |issn=1471-0684}}

{{Dual|source=Fifty Years of Prolog and Beyond|sourcepath=https://www.cambridge.org/core/journals/theory-and-practice-of-logic-programming/article/fifty-years-of-prolog-and-beyond/3A5329B6E3639879301A6D44346FD1DD|date=1727 MayOct 20222023|author=

Philipp Körner,

Michael Leuschel,