Tabled logic programming: Difference between revisions

Revision as of 21:35, 27 October 2023

Latest revision as of 21:30, 26 May 2025

(32 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 whichjournal was|last1=Körner one|first1=Philipp |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 theProlog goalsand Beyond |journal=Theory and Practice of thatLogic workProgramming |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-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 asH.D. documentedWarren]].<ref>{{Cite bybook |last1=Pereira |first1=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 |last1=Tamaki |first1=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 ^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 |last1=Sagonas |first1=Konstantinos |last2=Swift |first2=Terrance |last3=Warren |first3=David S. |date=1994-05-24 |title=XSB as an efficient deductive database engine |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 |last1=Rao |first1=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>

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}}

* {{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}}

* {{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=17 May 2022|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}}

[[Category:Logic programming]]

[[Category:Dynamic programming]]

{{prog-lang-stub}}

{{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=17 May 2022|author=

Philipp Körner,

Michael Leuschel,

Joao Barbosa,

Vitor Santos Costa,

Veronica Dahl,

Manuel V. Hermenegildo,

Jose F. Morales,

Jan Wielemaker,

Daniel Diaz,

Salvador Abreu,

Giovanni Ciatto

}}