Tabled logic programming: Difference between revisions

Revision as of 14:55, 27 October 2023

Latest revision as of 21:30, 26 May 2025

(34 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Technique in natural language processing}}

Tabling is a technique first developed for natural language processing, where it was called [[Earley parsing]] (Kay Reference Kay1967; Earley Reference Earley1970). 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.

{{redirect|Tabling|the parliamentary procedure|Table (parliamentary procedure)}}

'''Tabling''' is a technique first developed for natural language processing, where it was called [[Earley parsing]] (Kay Reference Kay1967; Earley Reference Earley1970). 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=VÍTORVitor SANTOSSantos |last5=DAHLDahl |first5=VERÓNICAVeronica |last6=HERMENEGILDOHermengildo |first6=MANUELManuel V. |last7=MORALESMorales |first7=JOSEJose F. |last8=WIELEMAKERWielemaker |first8=JANJan |last9=DIAZDiaz |first9=DANIELDaniel |last10=ABREUAbreu |first10=SALVADORSalvador |last11=CIATTOCiatto |first11=GIOVANNIGiovanni |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>

Its adaptation into a logic programming proof procedure, under the name of Earley deduction, dates from an unpublished note from 1975 by David H.D. Warren, as documented by Pereira and Shieber (Reference Pereira and Shieber1987). An interpretation method based on tabling was later developed by Tamaki and Sato (Reference Tamaki and Sato1986), modeled as a refinement of SLD-resolution.

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>

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.

== History ==

Indeed, the completion semantics cannot faithfully capture important concepts such as the transitive closure of a graph or relation. The minimal model semantics is able to capture such concepts. Moreover, tabled execution terminates for corresponding programs such as for the transitive closure of a cyclic graph. This makes Prolog more declarative.

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 |last1=Pereira |first1=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–210}}</ref> An interpretation method based on tabling was later developed by Tamaki and Sato, 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.

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, which was one of the goals of that work.

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>

== References ==

''XSB Prolog (1994)'' The concept of tabled Prolog was introduced in 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.

{{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=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]]

== References ==

{{Cite journal |last=Körner |first=Pjilipp |last2=Leuschel |first2=Michael |last3=Barbosa |first3=Joao |last4=Costa |first4=VÍTOR SANTOS |last5=DAHL |first5=VERÓNICA |last6=HERMENEGILDO |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}}

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

}}