Tabled logic programming

Tabling is a technique first developed for natural language processing, where it was called Earley parsing.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.[1]

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.[2][3]

History

edit edit source

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.[4] An interpretation method based on tabling was later developed by Tamaki and Sato, modelled as a refinement of SLD-resolution.[5]

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.[6] This resulted in a complete implementation of the well-founded semantics, a three-valued semantics that represents values for true, false and unknown.[7]

References

edit edit source
  1. ^ Körner, Philipp; Leuschel, Michael; Barbosa, Joao; Costa, Vitor Santos; Dahl, Veronica; Hermengildo, Manuel V.; Morales, Jose F.; Wielemaker, Jan; Diaz, Daniel; Abreu, Salvador; Ciatto, Giovanni (2022-05-17). "Fifty Years of Prolog and Beyond". Theory and Practice of Logic Programming. 22 (6): 776–858. doi:10.1017/s1471068422000102. hdl:10174/33387. ISSN 1471-0684. Wikipedia revision 1365857929, retrieved 2026-11-18
  2. ^ Swift, T. (1999). "Tabling for non-monotonic programming". Annals of Mathematics and Artificial Intelligence. 25 (3/4): 201–240. doi:10.1023/A:1018990308362. S2CID 16695800. Wikipedia revision 1365857929, retrieved 2026-11-18
  3. ^ Zhou, Neng-Fa; Sato, Taisuke (2003). "Efficient Fixpoint Computation in Linear Tabling" (PDF). Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming: 275–283. Wikipedia revision 1365857929, retrieved 2026-11-18
  4. ^ Pereira, Fernando C. N.; Shieber, Stuart M. (1987). Prolog and Natural Language Analysis. Stanford: Center for the Study of Language and Information. pp. 185–210. Wikipedia revision 1365857929, retrieved 2026-11-18
  5. ^ Tamaki, Hisao; Sato, Taisuke (1986), "OLD resolution with tabulation", Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 84–98, doi:10.1007/3-540-16492-8_66, ISBN 978-3-540-16492-0, retrieved 2023-10-27 Wikipedia revision 1365857929, retrieved 2026-11-18
  6. ^ Sagonas, Konstantinos; Swift, Terrance; Warren, David S. (1994-05-24). "XSB as an efficient deductive database engine". ACM SIGMOD Record. 23 (2): 442–453. doi:10.1145/191843.191927. ISSN 0163-5808. Wikipedia revision 1365857929, retrieved 2026-11-18
  7. ^ Rao, Prasad; Sagonas, Konstantinos; Swift, Terrance; Warren, David S.; Freire, Juliana (1997), "XSB: A system for efficiently computing well-founded semantics", Logic Programming And Nonmonotonic Reasoning, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 430–440, doi:10.1007/3-540-63255-7_33, ISBN 978-3-540-63255-9, retrieved 2023-10-27 Wikipedia revision 1365857929, retrieved 2026-11-18
  •  This article incorporates text from this source, which is by 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 available under the CC BY 4.0 license.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1365857929 under CC BY-SA 4.0; modifications have been made.