Logic programming (which might better be called logical programming by analogy with mathematical programming and linear programming) is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a theorem-prover or model-generator is used as the problem-solver. The problem-solving task is split between the programmer, who is responsible only for ensuring the truth of programs expressed in logical form, and the theorem-prover or model-generator, which is responsible for solving problems efficiently. In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... John McCarthy (born September 4, 1927, in Boston, Massachusetts, sometimes known affectionately as Uncle John McCarthy), is a prominent computer scientist who received the Turing Award in 1971 for his major contributions to the field of Artificial Intelligence. ... John McCarthy proposed the Advice Taker in his 1958 paper Programs with Common Sense [1]. It was probably the first proposal to use logic to represent information in a computer and not just as the subject matter of another program. ...

However, logic programming, in the narrower sense in which it is more commonly understood, is the use of logic as both a declarative and procedural representation language. It is based upon the fact that a backwards reasoning theorem-prover applied to declarative sentences in the form of implications

B₁ and … and B_n implies H

treats the implications as goal-reduction procedures

to show/solve H, show/solve B₁ and … and B_n.

The programmer is responsible, not only for ensuring the truth of programs, but also for ensuring their efficiency. In many cases, to achieve efficiency, the programmer needs to be aware of and to exploit the problem-solving behavior of the theorem-prover. In this respect, logic programming is like conventional imperative programming, using programs to control the behaviour of a program executor. However, unlike imperative programs, which have only a procedural interpretation, logic programs also have a declarative, logical interpretation, which helps to ensure their correctness. Moreover, such programs, being declarative, are at a higher conceptual level than purely imperative programs; and their program executers, being theorem-provers, operate at a higher conceptual level than conventional compilers and interpreters.

History

Logic programming in the first and wider sense gave rise to a number of implementations, such as those by Fisher Black (1964), James Slagle (1965) and Cordell Green (1969), which were question-answering systems in the spirit of McCarthy's advice-taker. Foster and Elcock's Absys (1969), on the other hand, was probably the first language to be explicitly developed as an assertional programming language.

Logic programming in the narrower sense can be traced back to debates in the late 1960s and early 1970s about declarative versus procedural representations of knowledge in Artificial Intelligence. Advocates of declarative representations were notably working at Stanford, associated with John McCarthy, Bertram Raphael and Cordell Green, and in Edinburgh, with J. Alan Robinson (an academic visitor from Syracuse University), Pat Hayes, and Bob Kowalski. Advocates of procedural representations were mainly centered at MIT, under the leadership of Marvin Minsky and Seymour Papert. The Leland Stanford Junior University, commonly known as Stanford University (or simply Stanford), is a private university located approximately 37 miles (60 kilometers) southeast of San Francisco and approximately 20 miles northwest of San José in an unincorporated area of Santa Clara County. ... John McCarthy (born September 4, 1927, in Boston, Massachusetts, sometimes known affectionately as Uncle John McCarthy), is a prominent computer scientist who received the Turing Award in 1971 for his major contributions to the field of Artificial Intelligence. ... The University of Edinburgh, founded in 1582,[4] is a renowned centre for teaching and research in Edinburgh, Scotland. ... J. Alan Robinson is a philosopher (by training), mathematician and computer scientist. ... Syracuse University (SU) is a private research university located in Syracuse, New York. ... Patrick John Hayes or Pat Hayes (21 August 1944) is a British computer scientist who lives and works in the United States. ... Robert Anthony Kowalski (Bob Kowalski, born May 15, 1941 in Bridgeport, Connecticut, USA) is an American logician and computer scientist, who has spent much of his career in the UK. He was educated at the University of Chicago, University of Bridgeport (BA in mathematics, 1963), Stanford University (MSc in mathematics... Mapúa Institute of Technology (MIT, MapúaTech or simply Mapúa) is a private, non-sectarian, Filipino tertiary institute located in Intramuros, Manila. ... Marvin Lee Minsky (born August 9, 1927), sometimes affectionately known as Old Man Minsky, is an American cognitive scientist in the field of artificial intelligence (AI), co-founder of MITs AI laboratory, and author of several texts on AI and philosophy. ... Seymour Papert Seymour Papert (born March 1, 1928 Pretoria, South Africa) is an MIT mathematician, computer scientist, and prominent educator. ...

Although it was based on logic, Planner, developed at MIT, was the first language to emerge within this proceduralist paradigm [Hewitt, 1969]. The most influential implementation of Planner was the subset of Planner, called Micro-Planner, implemented by Gerry Sussman, Eugene Charniak and Terry Winograd. It was used to implement Winograd's natural-language understanding program SHRDLU, which was a landmark at that time. Planner featured pattern-directed invocation of procedural plans from both assertions and goals. In order to cope with the very limited memory systems that were available when it was developed, Planner used backtracking control structure so that only one possible computation path had to be stored at a time. From Planner there developed the programming languages QA-4, Popler, Conniver, QLISP, and the concurrent language Ether. Planner (often seen in publications as PLANNER) is a programming language designed by Carl Hewitt at MIT, and first published in 1969. ... // Gerald Jay Sussman is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT). ... Eugene Charniak is a Computer Science and Cognitive Science professor at Brown University. ... Terry A. Winograd Terry Allen Winograd (born February 24, 1946) is a professor of computer science at Stanford University. ... SHRDLU [1] was an early natural language understanding computer program, developed by Terry Winograd at MIT from 1968-1970. ...

Hayes and Kowalski in Edinburgh tried to reconcile the logic-based declarative approach to knowledge representation with Planner's procedural approach. Hayes (1973) developed an equational language, Golux, in which different procedures could be obtained by altering the behavior of the theorem prover. Kowalski, on the other hand, showed how SL-resolution treats implications as goal-reduction procedures. Kowalski collaborated with Colmerauer in Marseille, who developed these ideas in the design and implementation of the programming language Prolog. From Prolog there developed, among others, the programming languages ALF, Fril, Gödel, Mercury, Oz, Ciao, Visual Prolog, XSB, and λProlog, as well as a variety of concurrent logic programming languages, (see Shapiro (1989) for a survey), constraint logic programming languages and datalog. ALF is a programming language which combines functional and logic programming techniques. ... Fril is a programming language for first-order predicate calculus. ... Gödel is a declarative, general-purpose programming language that adheres to the logic programming paradigm. ... Mercury is a functional logic programming language based on Prolog, but more geared towards practical applications. ... Oz is a multiparadigm programming language, developed in the Programming Systems Lab at Saarland University. ... Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog. ... The XSB (Xtreme Student Body) is a fantasy football league founded in 2002 at the University of Mississippi by then-student Will Bardwell. ... λProlog, also written lambda Prolog, is a strongly-typed functional logic programming language. ... Bold textConstraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. ... Datalog is a query and rule language for deductive databases that syntactically is a subset of Prolog. ...

Prolog

Main article: Prolog

The programming language Prolog was developed in 1972 by Alain Colmerauer. It emerged from a collaboration between Colmerauer in Marseille and Robert Kowalski in Edinburgh. Colmerauer was working on natural language understanding, using logic to represent semantics and using resolution for question-answering. During the summer of 1971, Colmerauer and Kowalski discovered that the clausal form of logic could be used to represent formal grammars and that resolution theorem provers could be used for parsing. They observed that some theorem provers, like hyper-resolution, behave as bottom-up parsers and others, like SL-resolution (1971), behave as top-down parsers. Prolog is a logic programming language. ... Prolog is a logic programming language. ... Professor Alain Colmerauer is the creator of the logic programming language Prolog for computers. ... City flag Coat of arms Motto: By her great deeds, the city of Massilia shines Location Coordinates Time Zone CET (GMT +1) Administration Country France Region Provence-Alpes-Côte dAzur Department Bouches-du-Rhône (13) Subdivisions 16 arrondissements (in 8 secteurs) Intercommunality Urban Community of Marseille Provence... Robert Anthony Kowalski (Bob Kowalski, born May 15, 1941 in Bridgeport, Connecticut, USA) is an American logician and computer scientist, who has spent much of his career in the UK. He was educated at the University of Chicago, University of Bridgeport (BA in mathematics, 1963), Stanford University (MSc in mathematics...

It was in the following summer of 1972, that Kowalski, again working with Colmerauer, developed the procedural interpretation of implications. This dual declarative/procedural interpretation later became formalised in the Prolog notation

H :- B₁, …, B_n.

which can be read (and used) both declaratively and procedurally. It also became clear that such clauses could be restricted to definite clauses or Horn clauses, where H, B₁, …, B_n are all atomic predicate logic formulae, and that SL-resolution could be restricted (and generalised) to LUSH or SLD-resolution. Kowalski's procedural interpretation and LUSH were described in a 1973 memo, published in 1974. In logic, and in particular in propositional calculus, a Horn clause is a proposition of the general type (p and q and . ...

Colmerauer, with Philippe Roussel, used this dual interpretation of clauses as the basis of Prolog, which was implemented in the summer and autumn of 1972. The first Prolog program, also written in 1972 and implemented in Marseille, was a French question-answering system. The use of Prolog as a practical programming language was given great momentum by the development of a compiler by David Warren in Edinburgh in 1977. Experiments demonstrated that Edinburgh Prolog could compete with the processing speed of other symbolic programming languages such as Lisp. Edinburgh Prolog became the de facto standard and strongly influenced the definition of ISO standard Prolog. Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ... The International Organization for Standardization (ISO) is an international standard-setting body composed of representatives from national standards bodies. ...

Negation as failure

Micro-Planner had a construct, called "thnot", which when applied to an expression returns the value true if (and only if) the evaluation of the expression fails. An equivalent operator is normally built-in in modern Prolog's implementations and has been called "negation as failure". It is normally written as not(p), where p is an atom whose variables normally has been instantiated by the time not(p) is invoked. A more cryptic (but standard) syntax is + p . Negation as failure literals can occur as conditions not(B_i) in the body of program clauses. Prolog is a logic programming language. ... A common default assumption is that what is not known to be true is believed to be false. ...

The logical status of negation as failure was unresolved until Keith Clark [1978] showed that, under certain natural conditions, it is a correct (and sometimes complete) implementation of classical negation with respect to the completion of the program. Completion amounts roughly to regarding the set of all the program clauses with the same predicate on the left hand side, say

H :- Body₁.

…

H :- Body_k.

as a definition of the predicate

H iff (Body₁ or … or Body_k)

where "iff" means "if and only if". Writing the completion also requires explicit use of the equality predicate and the inclusion of a set of appropriate axioms for equality. However, the implementation of negation by failure needs only the if-halves of the definitions without the axioms of equality.

The notion of completion is closely related to McCarthy's circumscription semantics for default reasoning, and to the closed world assumption. Circumscription is a non-monotonic logic created by John McCarthy to formalize the common sense assumption that things are as expected unless otherwise specified. ... The closed world assumption is the presumption that what is not currently known to be true is false. ...

As an alternative to the completion semantics, negation as failure can also be interpreted epistemically, as in the stable model semantics of answer set programming. In this interpretation not(B_i) means literally that B_i is not known or not believed. The epistemic interpretation has the advantage that it can be combined very simply with classical negation, as in "extended logic programming", to formalise such phrases as "the contrary can not be shown", where "contrary" is classical negation and "can not be shown" is the epistemic interpretation of negation as failure. There are very few or no other articles that link to this one. ... Answer set programming is a form of declarative programming that is similar in syntax to traditional logic programming and close in semantics to non-monotonic logic. ...

Problem Solving

In the simplified, propositional case in which a logic program and a top-level atomic goal contain no variables, backward reasoning determines an and-or tree, which constitutes the search space for solving the goal. The top-level goal is the root of the tree. Given any node in the tree and any clause whose head matches the node, there exists a set of child nodes corresponding to the sub-goals in the body of the clause. These child nodes are grouped together by an "and". The alternative sets of children corresponding to alternative ways of solving the node are grouped together by an "or". This article or section does not adequately cite its references or sources. ...

Any search strategy can be used to search this space. Prolog uses a sequential, last-in-first-out, backtracking strategy, in which only one alternative and one sub-goal is considered at a time. Other search strategies, such as parallel search, intelligent backtracking, or best-first search to find an optimal solution, are also possible.

In the more general case, where sub-goals share variables, other strategies can be used, such as choosing the subgoal that is most highly instantiated or that is sufficiently instantiated so that only one procedure applies. Such strategies are used, for example, in concurrent logic programming.

The fact that there are alternative ways of executing a logic program has been characterised by the equation:

Algorithm = Logic + Control

where "Logic" represents a logic program and "Control" represents different theorem-proving strategies.

Knowledge Representation

The fact that Horn clauses can be given a procedural interpretation and, vice versa, that goal-reduction procedures can be understood as Horn clauses + backward reasoning means that logic programs combine declarative and procedural representations of knowledge. The inclusion of negation as failure means that logic programming is a kind of non-monotonic logic. Knowledge representation is an issue that arises in both cognitive science and artificial intelligence. ... A common default assumption is that what is not known to be true is believed to be false. ... A non-monotonic logic is a formal logic whose consequence relation is not monotonic. ...

Despite its simplicity compared with classical logic, this combination of Horn clauses and negation as failure has proved to be surprisingly expressive. For example, it has been shown to correspond, with some further extensions, quite naturally to the semi-formal language of legislation. It is also a natural language for expressing common-sense laws of cause and effect, as in the situation calculus and event calculus. The situation calculus is a first order logic formalism designed for representing and reasoning about dynamically changing worlds. ... The event calculus is a logic language for representing and reasoning about actions and their effects. ...

Concurrent logic programming

Keith Clark, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog-like concurrent message passing systems using unification of shared variables and data structure streams for messages. Efforts were made to base these systems on mathematical logic, and they were used as the basis of the Japanese Fifth Generation Project (ICOT). The Prolog-like concurrent systems were based on message passing and consequently were subject to the same indeterminacy [Hewitt and Agha, 1988]. Keith Clark is a Professor of Computer Science at Imperial College London. ... Prolog is a logic programming language. ... The PIM/m-1 machine. ...

Higher-order logic programming

Several researchers have extended logic programming with higher-order programming features derived from higher-order logic, such as predicate variables. Such languages include the Prolog extensions HiLog and λProlog. Higher-order programming is programming that exploits the ability to use functions as values; it is usually borrowed from models of computation like the lambda calculus which make heavy use of higher-order functions. ... In mathematics, higher-order logic is distinguished from first-order logic in a number of ways. ... λProlog, also written lambda Prolog, is a strongly-typed functional logic programming language. ...

Linear logic programming

Basing logic programming within linear logic has resulted in the design of logic programming languages that are considerably more expressive than those based on classical logic. Horn clause programs can only represent state change by the change in arguments to predicates. In linear logic programming, one can use the ambient linear logic to support state change. Some early designs of logic programming languages based on linear logic include LO [Andreoli & Pareschi, 1991], Lolli [Hodas & Miller, 1994], ACL [Kobayashi & Yonezawa, 1994], and Forum [Miller, 1996]. Forum provides a goal-direct interpretation of all of linear logic.

See also

• Constraint logic programming
• Formal methods
• Functional programming
• Programming paradigm
• Inductive logic programming

Bold textConstraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. ... In computer science and software engineering, formal methods are mathematically-based techniques for the specification, development and verification of software and hardware systems. ... Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ... A programming paradigm is a paradigmatic style of programming (compare with a methodology, which is a paradigmatic style of doing software engineering). ... Inductive logic programming (ILP) is a machine learning approach, which uses techniques of logic programming. ...

References

• John McCarthy. Programs with common sense Symposium on Mechanization of Thought Processes. National Physical Laboratory. Teddington, England. 1958.
• Fisher Black. A deductive question answering system Harvard University. Thesis. 1964.
• James Slagle. Experiments with a Deductive Question-Answering Program CACM. December, 1965.
• Cordell Green. Application of Theorem Proving to Problem Solving IJCAI 1969.
• Carl Hewitt. Planner: A Language for Proving Theorems in Robots IJCAI 1969.
• Gerry Sussman and Terry Winograd. Micro-planner Reference Manual AI Memo No, 203, MIT Project MAC, July 1970.
• Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
• Terry Winograd. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language MIT AI TR-235. January 1971.
• Bruce Anderson. Documentation for LIB PICO-PLANNER School of Artificial Intelligence, Edinburgh University. 1972
• Bruce Baumgart. Micro-Planner Alternate Reference Manual Stanford AI Lab Operating Note No. 67, April 1972.
• Julian Davies. Popler 1.6 Reference Manual University of Edinburgh, TPU Report No. 1, May 1973.
• Jeff Rulifson, Jan Derksen, and Richard Waldinger. QA4, A Procedural Calculus for Intuitive Reasoning SRI AI Center Technical Note 73, November 1973.
• Robert Kowalski and Donald and Kuehner, Linear Resolution with Selection Function Artificial Intelligence, Vol. 2, 1971, pp. 227-60.
• Robert Kowalski Predicate Logic as a Programming Language Memo 70, Department of Artificial Intelligence, Edinburgh University. 1973. Also in Proceedings IFIP Congress, Stockholm, North Holland Publishing Co., 1974, pp. 569-574.
• Drew McDermott and Gerry Sussman. The Conniver Reference Manual MIT AI Memo 259A. January 1974.
• Earl Sacerdoti, et al. QLISP: A Language for the Interactive Development of Complex Systems AFIPS National Computer Conference. 1976.
• Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
• Bill Kornfeld. The Use of Parallelism to Implement a Heuristic Search IJCAI 1981.
• Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981.
• Bill Kornfeld. Combinatorially Implosive Algorithms CACM. 1982
• Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985.
• Robert Kowalski. The Limitations of Logic Proceedings of the 1986 ACM fourteenth annual conference on Computer science.
• Ehud Shapiro (Editor). Concurrent Prolog MIT Press. 1987.
• Robert Kowalski. The Early Years of Logic Programming CACM. January 1988.
• Ehud Shapiro. The family of concurrent logic programming languages ACM Computing Surveys. September 1989.
• Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
• Shunichi Uchida and Kazuhiro Fuchi Proceedings of the FGCS Project Evaluation Workshop Institute for New Generation Computer Technology (ICOT). 1992.
• Carl Hewitt. The repeated demise of logic programming and why it will be reincarnated What Went Wrong and Why: Lessons from AI Research and Applications. Technical Report SS-06-08. AAAI Press. March 2006.
• J. W. Lloyd. Foundations of Logic Programming (2nd edition). Springer-Verlag 1987.
• Jean-Marc Andreoli and Remo Pareschi. Linear Objects: Logical Processes with Built-In Inheritance, Proceeding of the Seventh International Conference on Logic Programming, Jerusalem, May 1990.
• Joshua Hodas and Dale Miller. Logic Programming in a Fragment of Intuitionistic Linear Logic, Information and Computation, 1994, 110(2), 327-365.
• Naoki Kobayashi and Akinori Yonezawa. Asynchronous communication model based on linear logic, Formal Aspects of Computing, 1994, 279-294.
• Dale Miller. Forum: A Multiple-Conclusion Specification Language, Theoretical Computer Science, 1996, 165 (1), 201--232.
• Dale Miller. Overview of linear logic programming, in Linear Logic in Computer Science, edited by Thomas Ehrhard, Jean-Yves Girard, Paul Ruet, and Phil Scott. Cambridge University Press. London Mathematical Society Lecture Note, Volume 316.
• J.M. Foster and E.W. Elcock. ABSYS 1: An Incremental Compiler for Assertions: an Introduction, , Machine Intelligence 4, Edinburgh U Press, 1969, pp. 423-429
• Pat Hayes. Computation and Deduction. In Proceedings of the 2nd MFCS Symposium. Czechoslovak Academy of Sciences, 1973, pp. 105-118.

This article or section does not cite its references or sources. ...

External links

• Logic Programming Virtual Library entry
• Bibliographies on Logic Programming
• Association for Logic Programming (ALP)
• Theory and Practice of Logic Programming journal
• Logic programming in Oz
• Prolog Development Center