Tabled logic programming: Difference between revisions

Revision as of 14:51, 27 October 2023

Revision as of 14:55, 27 October 2023

Line 1:

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.

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.

Line 9:

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.

''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.

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

Line 24:

Giovanni Ciatto

}}

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