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 paradigm based on formal logic. A logic program is a set of sentences in logical form, representing knowledge about some problem domain. Computation is performed by applying logical reasoning to that knowledge, to solve problems in the 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 that has its origins in artificial intelligence, automated theorem proving and computational linguistics.

<span class="mw-page-title-main">Inductive logic programming</span>

Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "inductive" here refers to philosophical rather than mathematical induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples.

In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form that gives it useful properties for use in logic programming, formal specification, universal algebra and model theory. Horn clauses are named for the logician Alfred Horn, who first pointed out their significance in 1951.

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, 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. 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. A comprehensive discussion of the most significant Prolog systems is presented in an article published in the 50-years of Prolog anniversary issue of the journal Theory and Practice of Logic Programming (TPLP).

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.

SICStus Prolog is a proprietary, ISO-conforming implementation of the logic programming language Prolog. It is developed by the Swedish Institute of Computer Science since 1985 and puts a strong focus on performance and scalability.

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.

The LogicBlox system is a commercial, declarative, incremental logic programming language and deductive database inspired by Datalog. The LogiQL programming language extends Datalog with several features, including stratified negation, aggregation, and a module system. LogicBlox has been used to build pointer analyses for Java.

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 . hdl: 10174/33387 . 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, doi:10.1007/3-540-16492-8_66, 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, doi:10.1007/3-540-63255-7_33, ISBN   978-3-540-63255-9 , retrieved 2023-10-27


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.