Tabled logic programming
This article may meet Wikipedia's criteria for speedy deletion as a copyright infringement(Copyvios report) of http://dx.doi.org/10.1017/s1471068422000102 (Copyvios report) as well as https://www.cambridge.org/core/journals/theory-and-practice-of-logic-programming/article/fifty-years-of-prolog-and-beyond/3A5329B6E3639879301A6D44346FD1DD (Copyvios report). This criterion applies only in unequivocal cases, where there is no free-content material on the page worth saving and no later edits requiring attribution – for more complicated situations, see Wikipedia:Copyright violations. See CSD G12.
If this article does not meet the criteria for speedy deletion, or you intend to fix it, please remove this notice, but do not remove this notice from pages that you have created yourself. If you created this page and you disagree with the given reason for deletion, you can click the button below and leave a message explaining why you believe it should not be deleted. You can also visit the talk page to check if you have received a response to your message. Note that this article may be deleted at any time if it unquestionably meets the speedy deletion criteria, or if an explanation posted to the talk page is found to be insufficient. Note to administrators: this article has content on its talk page which should be checked before deletion. Note to administrators: If declining the request due to not meeting the criteria please consider whether there are still copyright problems with the page and if so, see these instructions for cleanup, or list it at Wikipedia:Copyright problems. Please be sure that the source of the alleged copyright violation is not itself a Wikipedia mirror. Also, ensure the submitter of this page has been notified about our copyright policy.Administrators: check links, talk, history (last), and logs before deletion. Consider checking Google. This page was last edited by Dan arndt (contribs | logs) at 10:49, 29 October 2023 (UTC) (20 months ago) |
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
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
- ^ 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. ISSN 1471-0684.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Tamaki, Hisao; Sato, Taisuke (1986), "OLD resolution with tabulation", Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 84–98, ISBN 978-3-540-16492-0, retrieved 2023-10-27
- ^ 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.
- ^ 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, ISBN 978-3-540-63255-9, retrieved 2023-10-27
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.
 | This programming-language-related article is a stub. You can help Wikipedia by expanding it. |