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]
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]
As of 27 Oct 2023, this article is derived in whole or in part from Fifty Years of Prolog and Beyond, authored by 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. The copyright holder has licensed the content in a manner that permits reuse under CC BY-SA 3.0 and GFDL. All relevant terms must be followed.
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]
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]
As of 27 Oct 2023, this article is derived in whole or in part from Fifty Years of Prolog and Beyond, authored by 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. The copyright holder has licensed the content in a manner that permits reuse under CC BY-SA 3.0 and GFDL. All relevant terms must be followed.