Tabled logic programming

Last updated

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]

Related Research Articles

Logic programming is a programming, database and knowledge-representation and reasoning paradigm which is based on formal logic. A program, database or knowledge base in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, Answer Set Programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

Prolog is a logic programming language associated with artificial intelligence and computational linguistics.

<span class="mw-page-title-main">Interpreter (computing)</span> Program that executes source code without a separate compilation step

In computer science, an interpreter is a computer program that directly executes instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program. An interpreter generally uses one of the following strategies for program execution:

  1. Parse the source code and perform its behavior directly;
  2. Translate source code into some efficient intermediate representation or object code and immediately execute that;
  3. Explicitly execute stored precompiled bytecode made by a compiler and matched with the interpreter Virtual Machine.

In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again. Memoization has also been used in other contexts, such as in simple mutually recursive descent parsing. It is a type of caching, distinct from other forms of caching such as buffering and page replacement. In the context of some logic programming languages, memoization is also known as tabling.

Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more.

In computer science, the occurs check is a part of algorithms for syntactic unification. It causes unification of a variable V and a structure S to fail if S contains V.

SWI-Prolog is a free implementation of the programming language Prolog, commonly used for teaching and semantic web applications. It has a rich set of features, libraries for constraint logic programming, multithreading, unit testing, GUI, interfacing to Java, ODBC and others, literate programming, a web server, SGML, RDF, RDFS, developer tools, and extensive documentation.

In computer science, future, promise, delay, and deferred refer to constructs used for synchronizing program execution in some concurrent programming languages. They describe an object that acts as a proxy for a result that is initially unknown, usually because the computation of its value is not yet complete.

In computer science, a term index is a data structure to facilitate fast lookup of terms and clauses in a logic program, deductive database, or automated theorem prover.

A definite clause grammar (DCG) is a way of expressing grammar, either for natural or formal languages, in a logic programming language such as Prolog. It is closely related to the concept of attribute grammars / affix grammars from which Prolog was originally developed. DCGs are usually associated with Prolog, but similar languages such as Mercury also include DCGs. They are called definite clause grammars because they represent a grammar as a set of definite clauses in first-order logic.

In computer science, the well-founded semantics is a three-valued semantics for logic programming, which gives a precise meaning to general logic programs.

XSB is the name of a dialect of the Prolog programming language and its implementation developed at Stony Brook University in collaboration with the Katholieke Universiteit Leuven, the New University of Lisbon, Uppsala University and software vendor XSB, Inc.

Logtalk is an object-oriented logic programming language that extends and leverages the Prolog language with a feature set suitable for programming in the large. It provides support for encapsulation and data hiding, separation of concerns and enhanced code reuse. Logtalk uses standard Prolog syntax with the addition of a few operators and directives.

The following Comparison of Prolog implementations provides a reference for the relative feature sets and performance of different implementations of the Prolog computer programming language.

HiLog is a programming logic with higher-order syntax, which allows arbitrary terms to appear in predicate and function positions. However, the model theory of HiLog is first-order. Although syntactically HiLog strictly extends first order logic, HiLog can be embedded into this logic.

Flora-2 is an open source semantic rule-based system for knowledge representation and reasoning. The language of the system is derived from F-logic, HiLog, and Transaction logic. Being based on F-logic and HiLog implies that object-oriented syntax and higher-order representation are the major features of the system. Flora-2 also supports a form of defeasible reasoning called Logic Programming with Defaults and Argumentation Theories (LPDA). Applications include intelligent agents, Semantic Web, knowledge-bases networking, ontology management, integration of information, security policy analysis, automated database normalization, and more.

Rulelog is an expressive semantic rule-based knowledge representation and reasoning (KRR) language. It underlies knowledge representation languages used in systems such as Flora-2, SILK and others. It extends well-founded declarative logic programs with features for higher-order syntax, frame syntax, defeasibility, general quantified expressions both in the bodies of the rules and their heads, user-defined functions, and restraint bounded rationality.

Quintus Prolog is a proprietary implementation of the Prolog programming language based on the Warren Abstract Machine. Originally developed by Quintus Computer Science, it is currently maintained by SICS. It was long known as the most highly-performing implementation of Prolog, and the early 1990s, it defined a de facto standard for Prolog implementations.

References

  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 . ISSN   1471-0684.
  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.
  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.
  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.
  5. ↑ 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
  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.
  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, 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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.