Logic programming
This article may require cleanup to meet Wikipedia's quality standards. (June 2010) 
Logic programming is a programming paradigm based on formal logic. Programs written in a logical programming language are sets of logical sentences, expressing facts and rules about some problem domain. Together with an inference algorithm, they form a program. Major logic programming languages include Prolog and Datalog.
A form of logical sentences commonly found in logic programming, but not exclusively, is the Horn clause. An example is:

 p(X, Y) if q(X) and r(Y)
Logical sentences can be understood purely declaratively. They can also be understood procedurally as goalreduction procedures: to solve p(X, Y), first solve q(X), then solve r(Y).
The programmer can use the declarative reading of logic programs to verify their correctness. In addition, the programmer can use the known behaviour of the program executor to develop a procedural understanding of his program. This may be helpful when seeking better execution speed. However, many logicbased program transformation techniques have been developed to transform logic programs automatically and make them efficient.
Contents
 1 History
 2 Prolog
 3 Negation as failure
 4 Problem solving
 5 Knowledge representation
 6 Abductive logic programming
 7 Metalogic programming
 8 Constraint logic programming
 9 Concurrent logic programming
 10 Concurrent constraint logic programming
 11 Inductive logic programming
 12 Higherorder logic programming
 13 Linear logic programming
 14 Objectoriented logic programming
 15 Transaction logic programming
 16 See also
 17 References
 18 Further reading
 19 External links
History
The use of mathematical logic to represent and execute computer programs is also a feature of the lambda calculus, developed by Alonzo Church in the 1930s. However, the first proposal to use the clausal form of logic for representing computer programs was made by Cordell Green (1969). This used an axiomatization of a subset of LISP, together with a representation of an inputoutput relation, to compute the relation by simulating the execution of the program in LISP. Foster and Elcock's Absys (1969), on the other hand, employed a combination of equations and lambda calculus in an assertional programming language which places no constraints on the order in which operations are performed.^{citation needed}
Logic programming in its present form 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 John Alan Robinson (an academic visitor from Syracuse University), Pat Hayes, and Robert Kowalski. Advocates of procedural representations were mainly centered at MIT, under the leadership of Marvin Minsky and Seymour Papert.^{citation needed}
Although it was based on the proof methods of logic, Planner, developed at MIT, was the first language to emerge within this proceduralist paradigm [Hewitt, 1969]. Planner featured patterndirected invocation of procedural plans from goals (i.e. goalreduction or backward chaining) and from assertions (i.e. forward chaining). The most influential implementation of Planner was the subset of Planner, called MicroPlanner, implemented by Gerry Sussman, Eugene Charniak and Terry Winograd. It was used to implement Winograd's naturallanguage understanding program SHRDLU, which was a landmark at that time. To cope with the very limited memory systems at the time, Planner used a backtracking control structure so that only one possible computation path had to be stored at a time. Planner gave rise to the programming languages QA4, Popler, Conniver, QLISP, and the concurrent language Ether.^{citation needed}
Hayes and Kowalski in Edinburgh tried to reconcile the logicbased 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 SLresolution treats implications as goalreduction procedures. Kowalski collaborated with Colmerauer in Marseille, who developed these ideas in the design and implementation of the programming language Prolog. Prolog gave rise to 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.^{citation needed}
In 1997, the Association of Logic Programming bestowed to fifteen recognized researchers in logic programming the title Founders of Logic Programming to recognize them as pioneers in the field:^{1}
 Maurice Bruynooghe (Belgium)
 Jacques Cohen (US)
 Alain Colmerauer (France)
 Keith Clark (UK)
 Veronica Dahl (Canada/Argentina)
 Maarten van Emden (Canada)
 Hervé Gallaire (France)
 Robert Kowalski (UK)
 Jack Minker (US)
 Fernando Pereira (US)
 Luis Moniz Pereira (Portugal)
 Ray Reiter (Canada)
 J. Alan Robinson (US)
 Peter Szeredi (Hungary)
 David H. D. Warren (UK)
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 questionanswering. 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 hyperresolution, behave as bottomup parsers and others, like SLresolution (1971), behave as topdown parsers.
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_{1}, …, 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_{1}, …, B_{n} are all atomic predicate logic formulae, and that SLresolution could be restricted (and generalised) to LUSH or SLDresolution. Kowalski's procedural interpretation and LUSH were described in a 1973 memo, published in 1974.
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 questionanswering 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.
Negation as failure
MicroPlanner 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 builtin in modern Prolog's implementations and has been called "negation as failure". It is normally written as not(Goal)
or \+ Goal
, where Goal
is some goal (proposition) to be proved by the program. This operator differs from negation in firstorder logic: a negation such as \+ X == 1
fails when the variable X
has been bound to the atom 1
, but it succeeds in all other cases, including when X
is unbound. This makes Prolog's reasoning nonmonotonic: X = 1, \+ X == 1
always fails, while \+ X == 1, X = 1
can succeed, binding X
to 1
, depending on whether X
was initially bound (note that standard Prolog executes goals in lefttoright order).
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_{1}.
 …
 H : Body_{k}.
as a definition of the predicate
 H iff (Body_{1} 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 ifhalves 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.
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.
Problem solving
In the simplified, propositional case in which a logic program and a toplevel atomic goal contain no variables, backward reasoning determines an andor tree, which constitutes the search space for solving the goal. The toplevel 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 subgoals 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".
Any search strategy can be used to search this space. Prolog uses a sequential, lastinfirstout, backtracking strategy, in which only one alternative and one subgoal is considered at a time. Other search strategies, such as parallel search, intelligent backtracking, or bestfirst search to find an optimal solution, are also possible.
In the more general case, where subgoals 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 theoremproving strategies.^{2}
Knowledge representation
The fact that Horn clauses can be given a procedural interpretation and, vice versa, that goalreduction 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 nonmonotonic logic.
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 semiformal language of legislation. It is also a natural language for expressing commonsense laws of cause and effect, as in the situation calculus and event calculus.
Abductive logic programming
Abductive Logic Programming is an extension of normal Logic Programming that allows some predicates, declared as abducible predicates, to be incompletely defined. Problem solving is achieved by deriving hypotheses expressed in terms of the abducible predicates as solutions of problems to be solved. These problems can be either observations that need to be explained (as in classical abductive reasoning) or goals to be achieved (as in normal logic programming). It has been used to solve problems in Diagnosis, Planning, Natural Language and Machine Learning. It has also been used to interpret Negation as Failure as a form of abductive reasoning.
Metalogic programming
Because mathematical logic has a long tradition of distinguishing between object language and metalanguage, logic programming also allows metalevel programming. The simplest metalogic program is the socalled "vanilla" metainterpreter:
solve(true). solve((A,B)): solve(A),solve(B). solve(A): clause(A,B),solve(B).
where true represents an empty conjunction, and clause(A,B) means there is an objectlevel clause of the form A : B.
Metalogic programming allows objectlevel and metalevel representations to be combined, as in natural language. It can also be used to implement any logic that is specified by means of inference rules.
Constraint logic programming
Constraint logic programming is an extension of normal Logic Programming that allows some predicates, declared as constraint predicates, to occur as literals in the body of clauses. These literals are not solved by goalreduction using program clauses, but are added to a store of constraints, which is required to be consistent with some builtin semantics of the constraint predicates.
Problem solving is achieved by reducing the initial problem to a satisfiable set of constraints. Constraint logic programming has been used to solve problems in such fields as civil engineering, mechanical engineering, digital circuit verification, automated timetabling, air traffic control, and finance. It is closely related to abductive logic programming.
Concurrent logic programming
Keith Clark, Steve Gregory, Ehud Shapiro, Kazunori Ueda, Vijay Saraswat, etc. developed a family of concurrent logic programming languages, which integrated concepts of logic programming and concurrent programming. Much of this development was inspired by the Japanese Fifth Generation Project (FGCS). The Fifth Generation Computer Systems project (FGCS) was a $400M initiative by Japan's Ministry of International Trade and Industry, begun in 1982, to create an "epochmaking computer" withsupercomputerlike performance using massively parallel computing/processing. The aim was to build parallel computers for artificial intelligence applications using logic programming as the “missing link” between the two. The rapid development of concurrent logic programming encouraged the FGS project to choose it as its software foundation. The FGCS project and its findings contributed greatly to the development of the concurrent logic programming field.
In 1982 the government decided to go ahead with the project, and established the Institute for New Generation Computer Technology (ICOT). In his 1982 visit to the ICOT, Ehud Shapiro invented Concurrent Prolog, a novel concurrent programming language that integrated logic programming and concurrent programming. Concurrent Prolog is a logic programming language designed for concurrent programming and parallel execution. It is a process oriented language, which embodies dataflow synchronization and guardedcommand indeterminacy as its basic control mechanisms.
The language was described in a Report marked as ICOT Technical Report 003,^{3} which presented a Concurrent Prolog interpreter written in Prolog. The concurrent logic programming presented in this work inspired the concurrent logic programming language Guarded Horn Clauses (GHC) by Ueda, which was the basis of KL1, the programming language that was finally designed and implemented by FGCS and served as “machine language” of the FGCS project — the basic operating system and application programming language of the planned parallel machines. Shapiro and his team at the Weizmann Institute in Israel proceeded in developing the parallel and distributed implementation of Concurrent Prolog, also contributing to the burst of research into concurrent logic programming, a new discipline of highlevel concurrent programming.^{4}
Concurrent constraint logic programming
However, the Prologlike concurrent systems were based on message passing and consequently were subject to the same indeterminacy as other concurrent messagepassing systems, such as Actors (see Indeterminacy in concurrent computation). Although it was argued that, the ICOT languages were not based on logic in the sense that computational steps could not be logically deduced [Hewitt and Agha, 1988], this statement is not quite true.^{citation needed} In concurrent logic programming, any result of a terminating computation is a logical consequence of the program, and any partial result of a partial computation is a logical consequence of the program and the residual goal (process network). However, the indeterminacy of computations implies that not all logical consequences of the program can be deduced.
Concurrent constraint logic programming combines concurrent logic programming and constraint logic programming, using constraints to control concurrency. A clause can contain a guard, which is a set of constraints that may block the applicability of the clause. When the guards of several clauses are satisfied, concurrent constraint logic programming makes a committed choice to the use of only one.
Inductive logic programming
Inductive logic programming is concerned with generalizing positive and negative examples in the context of background knowledge: machine learning of logic programs. Recent work in this area, combining logic programming, learning and probability, has given rise to the new field of statistical relational learning and probabilistic inductive logic programming.
Higherorder logic programming
Several researchers have extended logic programming with higherorder programming features derived from higherorder logic, such as predicate variables. Such languages include the Prolog extensions HiLog and λProlog.
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 goaldirected interpretation of all of linear logic.
Objectoriented logic programming
Flogic extends logic programming with objects and the frame syntax. A number of systems are based on Flogic, including Flora2, FLORID, and a highly scalable commercial system Ontobroker.
Transaction logic programming
Transaction logic is an extension of logic programming with a logical theory of statemodifying updates. It has both a modeltheoretic semantics and a procedural one. An implementation of a subset of Transaction logic is available in the Flora2 system. Other prototypes are also available.
See also
 Boolean satisfiability problem
 Constraint logic programming
 Datalog
 Functional programming
 Inductive logic programming
 Fuzzy logic
 Logic in computer science (includes Formal methods)
 Logic programming languages
 Programming paradigm
 R++
 Reasoning system
 Satisfiability
References
This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (February 2012) 
 ^ "ALP Awards". Retrieved 12 May 2013.
 ^ R.A.Kowalski (July 1979). "Algorithm=Logic + Control". Communications of the ACM 22 (7): 424–436.
 ^ Shapiro E. A subset of Concurrent Prolog and its interpreter, ICOT Technical Report TR003, Institute for New Generation Computer Technology, Tokyo, 1983. Also in Concurrent Prolog: Collected Papers, E. Shapiro (ed.), MIT Press, 1987, Chapter 2.
 ^ Shapiro E. A subset of Concurrent Prolog and its interpreter, ICOT Technical Report TR003, Institute for New Generation Computer Technology, Tokyo, 1983. Also in Concurrent Prolog: Collected Papers, E. Shapiro (ed.), MIT Press, 1987, Chapter 2.
General introductions
 Chitta Baral and Michael Gelfond. Logic programming and knowledge representation Journal of Logic Programming. 1994, Vol. 19, 73148.
 Robert Kowalski. The Early Years of Logic Programming CACM. January 1988.
 J. W. Lloyd. Foundations of Logic Programming (2nd edition). SpringerVerlag 1987.
Other sources
 Fisher Black. A deductive question answering system Harvard University. Thesis. 1964.
 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
 Cordell Green. Application of Theorem Proving to Problem Solving IJCAI 1969.
 Pat Hayes. Computation and Deduction. In Proceedings of the 2nd MFCS Symposium. Czechoslovak Academy of Sciences, 1973, pp. 105–118.
 Carl Hewitt. Planner: A Language for Proving Theorems in Robots IJCAI 1969.
 Joshua Hodas and Dale Miller. Logic Programming in a Fragment of Intuitionistic Linear Logic, Information and Computation, 1994, 110(2), 327365.
 Naoki Kobayashi and Akinori Yonezawa. Asynchronous communication model based on linear logic, Formal Aspects of Computing, 1994, 279294.
 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.
 John McCarthy. Programs with common sense Symposium on Mechanization of Thought Processes. National Physical Laboratory. Teddington, England. 1958.
 D. Miller, G. Nadathur, F. Pfenning, A. Scedrov. Uniform proofs as a foundation for logic programming, Annals of Pure and Applied Logic, vol. 51, pp 125–157, 1991.
 Ehud Shapiro (Editor). Concurrent Prolog MIT Press. 1987.
 Ehud Shapiro. The family of concurrent logic programming languages ACM Computing Surveys. September 1989.
 James Slagle. Experiments with a Deductive QuestionAnswering Program CACM. December 1965.
 Shunichi Uchida and Kazuhiro Fuchi Proceedings of the FGCS Project Evaluation Workshop Institute for New Generation Computer Technology (ICOT). 1992.
Further reading
 Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
 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 SS0608. AAAI Press. March 2006.
 Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov: Complexity and expressive power of logic programming. ACM Comput. Surv. 33(3): 374425 (2001)
 Ulf Nilsson and Jan Maluszynski, Logic, Programming and Prolog
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 C++ with Castor
 Logic programming in Oz
 Prolog Development Center
 Racklog: Logic Programming in Racket

HPTS  Area Progetti  EduSoft  JavaEdu  N.Saperi  Ass.Scuola..  TS BCTV  TS VideoRes  TSODP  TRTWE  