Tabled logic programming: Difference between revisions

Revision as of 10:21, 28 October 2023

Latest revision as of 21:30, 26 May 2025

(27 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Technique in natural language processing}}
{{redirect|Tabling|the parliamentary procedure|Table (parliamentary procedure)}}
'''Tabling''' is a technique first developed for natural language processing, where it was called [[Earley parsing]]. It consists of storing in a table (a.k.a. chart in the context of parsing) partial successful analyses that might come in handy for future reuse.

Tabling consists of maintaining a table of goals that are called during execution, along with their answers, and then using the answers directly when the same goal is subsequently called. Tabling gives a guarantee of total correctness for any (pure) Prolog program without function symbols.<ref>{{Cite journal |lastlast1=Körner |firstfirst1=PjilippPhilipp |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|doi-access=free |hdl=10174/33387 |hdl-access=free }}</ref>

Tabling can be extended in various directions. It can support recursive predicates through '''SLG resolution''' or linear tabling. In a multi-threaded Prolog system tabling results could be kept private to a thread or shared among all threads. And in incremental tabling, tabling might react to changes.<ref>{{Cite journal |last1=Swift |first1=T. |journal=Annals of Mathematics and Artificial Intelligence |volume=25 |issue=3/4 |pages=201–240|title=Tabling for non‐monotonicnon-monotonic programming |year=1999 |doi=10.1023/A:1018990308362 |s2cid=16695800}}</ref><ref>{{cite journal|last1=Zhou|first1=Neng-Fa|last2=Sato|first2=Taisuke|title=Efficient Fixpoint Computation in Linear Tabling|journal=Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming|date=2003|pages=275–283|url=http://www.sci.brooklyn.cuny.edu/~zhou/papers/ppdp03.pdf}}</ref>

== 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 H.D. Warren]].<ref>{{Cite book |lastlast1=Pereira |firstfirst1=Fernando C. N. |title=Prolog and Natural Language Analysis |last2=Shieber |first2=Stuart M. |publisher=[[Center for the Study of Language and Information]] |year=1987 |___location=Stanford |pages=185--210185–210}}</ref> An interpretation method based on tabling was later developed by Tamaki and Sato, modelled as a refinement of SLD-resolution.<ref>{{Citation |lastlast1=Tamaki |firstfirst1=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|doi=10.1007/3-540-16492-8_66 |url-access=subscription }}</ref>

David S. Warren 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 |lastlast1=Sagonas |firstfirst1=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|doi-access=free }}</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 |lastlast1=Rao |firstfirst1=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|doi=10.1007/3-540-63255-7_33 |url-access=subscription }}</ref>

== SLG resolution ==

{{expand section}}

== Termination properties ==

{{expand section}}

== References ==

{{reflist}}

* {{DualCC-notice|cc=by4|from this source=Fifty Years of Prolog and Beyond|sourcepathurl=https://www.cambridge.org/core/journals/theory-and-practice-of-logic-programming/article/fifty-years-of-prolog-and-beyond/3A5329B6E3639879301A6D44346FD1DD|date=2717 OctMay 20232022|author(s)=PHILIPP KÖRNER, MICHAEL LEUSCHEL, JOÃO BARBOSA, VÍTOR SANTOS COSTA, VERÓNICA DAHL, MANUEL V. HERMENEGILDO, JOSE F. MORALES, JAN WIELEMAKER, DANIEL DIAZ, SALVADOR ABREU and GIOVANNI CIATTO}}

Philipp Körner,

[[Category:Logic programming]]

Michael Leuschel,

[[Category:Dynamic programming]]

Joao Barbosa,

Vitor Santos Costa,

Veronica Dahl,

{{prog-lang-stub}}

Manuel V. Hermenegildo,

Jose F. Morales,

Jan Wielemaker,

Daniel Diaz,

Salvador Abreu,

Giovanni Ciatto

}}

{{Draft categories|[[Category:Logic programming]][[Category:Dynamic programming]]

}}