Logic programming
Encyclopedia
Logic 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.
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:
treats the implications as goal-reduction procedures:
For example, it treats the implication:
as the procedure:
Note that this is consistent with the BHK interpretation
of constructive logic, where implication would be interpreted as a solution of problem H given solutions of B1 … Bn. However, the defining feature of logic programming is that sets of formulas can be regarded as programs and proof search can be given a computational meaning. This is achieved by restricting the underlying logic to a "well-behaved" fragment such as Horn clause
s or Hereditary Harrop formulas. See D. Miller et al., 1991.
As in the purely declarative case, the programmer is responsible for ensuring the truth of programs. But since automated proof search is generally infeasible, logic programming as commonly understood also relies on the programmer to ensure that inferences are generated efficiently (see →problem solving). In many cases, to achieve efficiency, one needs to be aware of and to exploit the problem-solving behavior of the theorem-prover. In this respect, logic programming is comparable to conventional imperative programming
; using programs to control the behaviour of a program executor. However, unlike conventional 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 executors, being theorem-provers, operate at a higher conceptual level than conventional compiler
s and interpreters
.
(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 Robert Kowalski
. Advocates of procedural representations were mainly centered at MIT, under the leadership of Marvin Minsky
and Seymour Papert
.
Although it was based on logic, Planner, developed at MIT, was the first language to emerge within this proceduralist paradigm [Hewitt, 1969]. Planner featured pattern directed invocation of procedural plans from goals (i.e. forward chaining
) and from assertions (i.e. backward chaining
). 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. 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.
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
.
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. The individuals receiving this honor were: Maurice Bruynooghe (Belgium), Jacques Cohen
(US), Alain Colmerauer
(France), Keith Clark
(UK), Veronica Dahl (Canada/Argentina), Maarten van Emden (Canada), Herve Gallaire (France), Robert Kowalski
(UK), Jack Minker
(US), Fernando Pereira (US), Luis Moniz Pereira
(Portugal), Ray Reiter (Canada), Alan Robinson
(US), Peter Szeredi (Hungary), and David H.D. Warren (UK).
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.
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
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 clause
s, where H, B1, …, Bn 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.
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.
's implementations and has been called "negation as failure". It is normally written as not(p), where p is an atom whose variables normally have 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(Bi) in the body of program clauses.
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
as a definition of the predicate
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
.
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(Bi) means literally that Bi 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.
, 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".
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.
. The inclusion of negation as failure means that logic programming is a kind of non-monotonic 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 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
.
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.
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 object-level clause of the form A :- B.
Metalogic programming allows object-level 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.
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
.
, 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)
. However, the Prolog-like concurrent systems were based on message passing and consequently were subject to the same indeterminacy as other concurrent message-passing systems, such as Actors
(see Indeterminacy in concurrent computation). Consequently, the ICOT languages were not based on logic in the sense that computational steps could not be logically deduced [Hewitt and Agha, 1988].
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.
and probabilistic inductive logic programming.
, such as predicate variables. Such languages include the Prolog extensions HiLog and λProlog.
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-directed interpretation of all of linear logic.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
for computer programming
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
. In this view of logic programming, which can be traced at least as far back as John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
's [1958] advice-taker
Advice taker
The advice taker was a hypothetical computer program, proposed by John McCarthy in his 1958 paper "Programs with Common Sense" . 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. It may also have been the...
proposal, logic is used as a purely declarative representation language, and a theorem-prover
Automated theorem proving
Automated theorem proving or automated deduction, currently the most well-developed subfield of automated reasoning , is the proving of mathematical theorems by a computer program.- Decidability of the problem :...
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.
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:
-
-
-
- If B1 and … and Bn then H
-
-
treats the implications as goal-reduction procedures:
-
-
-
- to show/solve H, show/solve B1 and … and Bn.
-
-
For example, it treats the implication:
-
-
-
- If you press the alarm signal button,
- then you alert the driver of the train of a possible emergency
-
-
as the procedure:
-
-
-
- To alert the driver of the train of a possible emergency,
- press the alarm signal button.
-
-
Note that this is consistent with the BHK interpretation
BHK interpretation
In mathematical logic, the Brouwer–Heyting–Kolmogorov interpretation, or BHK interpretation, of intuitionistic logic was proposed by L. E. J. Brouwer, Arend Heyting and independently by Andrey Kolmogorov...
of constructive logic, where implication would be interpreted as a solution of problem H given solutions of B1 … Bn. However, the defining feature of logic programming is that sets of formulas can be regarded as programs and proof search can be given a computational meaning. This is achieved by restricting the underlying logic to a "well-behaved" fragment such as Horn clause
Horn clause
In mathematical logic, a Horn clause is a clause with at most one positive literal. They are named after the logician Alfred Horn, who first pointed out the significance of such clauses in 1951...
s or Hereditary Harrop formulas. See D. Miller et al., 1991.
As in the purely declarative case, the programmer is responsible for ensuring the truth of programs. But since automated proof search is generally infeasible, logic programming as commonly understood also relies on the programmer to ensure that inferences are generated efficiently (see →problem solving). In many cases, to achieve efficiency, one needs to be aware of and to exploit the problem-solving behavior of the theorem-prover. In this respect, logic programming is comparable to conventional imperative programming
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
; using programs to control the behaviour of a program executor. However, unlike conventional 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 executors, being theorem-provers, operate at a higher conceptual level than conventional compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
s and interpreters
Interpreter (computing)
In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language...
.
History
Logic programming in the first and wider sense gave rise to a number of implementations, such as those by Fischer BlackFischer Black
Fischer Sheffey Black was an American economist, best known as one of the authors of the famous Black–Scholes equation.-Background:...
(1964), James Slagle (1965) and Cordell Green (1969), which were question-answering systems in the spirit of McCarthy's Advice taker
Advice taker
The advice taker was a hypothetical computer program, proposed by John McCarthy in his 1958 paper "Programs with Common Sense" . 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. It may also have been the...
. Foster and Elcock's Absys
ABSYS
ABSYS was an early declarative programming language from the University of Aberdeen which anticipated a number of features of Prolog.-References:...
(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
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
, associated with John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
, Bertram Raphael and Cordell Green, and in Edinburgh
University of Edinburgh
The University of Edinburgh, founded in 1583, is a public research university located in Edinburgh, the capital of Scotland, and a UNESCO World Heritage Site. The university is deeply embedded in the fabric of the city, with many of the buildings in the historic Old Town belonging to the university...
, with J. Alan Robinson
J. Alan Robinson
John Alan Robinson is a philosopher , mathematician and computer scientist. He is University Professor Emeritus at Syracuse University, United States....
(an academic visitor from Syracuse University
Syracuse University
Syracuse University is a private research university located in Syracuse, New York, United States. Its roots can be traced back to Genesee Wesleyan Seminary, founded by the Methodist Episcopal Church in 1832, which also later founded Genesee College...
), Pat Hayes
Patrick J. Hayes
Patrick John Hayes or Pat Hayes is a British computer scientist who lives and works in the United States. , he is a Senior Research Scientist at the Institute for Human and Machine Cognition in Pensacola, Florida. He received a B.A. in Mathematics from University of Cambridge and a Ph.D...
, and Robert Kowalski
Robert Kowalski
Robert "Bob" Anthony Kowalski is a British logician and computer scientist, who has spent most of his career in the United Kingdom....
. Advocates of procedural representations were mainly centered at MIT, under the leadership of Marvin Minsky
Marvin Minsky
Marvin Lee Minsky is an American cognitive scientist in the field of artificial intelligence , co-founder of Massachusetts Institute of Technology's AI laboratory, and author of several texts on AI and philosophy.-Biography:...
and Seymour Papert
Seymour Papert
Seymour Papert is an MIT mathematician, computer scientist, and educator. He is one of the pioneers of artificial intelligence, as well as an inventor of the Logo programming language....
.
Although it was based on logic, Planner, developed at MIT, was the first language to emerge within this proceduralist paradigm [Hewitt, 1969]. Planner featured pattern directed invocation of procedural plans from goals (i.e. forward chaining
Forward chaining
Forward chaining is one of the two main methods of reasoning when using inference rules and can be described logically as repeated application of modus ponens. Forward chaining is a popular implementation strategy for expert systems, business and production rule systems...
) and from assertions (i.e. backward chaining
Backward chaining
Backward chaining is an inference method that can be described as working backward from the goal...
). The most influential implementation of Planner was the subset of Planner, called Micro-Planner, implemented by Gerry Sussman
Gerald Jay Sussman
Gerald Jay Sussman is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology . He received his S.B. and Ph.D. degrees in mathematics from MIT in 1968 and 1973 respectively. He has been involved in artificial intelligence research at MIT since 1964...
, Eugene Charniak
Eugene Charniak
Eugene Charniak is a Computer Science and Cognitive Science professor at Brown University. He has an A.B. in Physics from The University of Chicago and a Ph.D. from M.I.T. in Computer Science. His research has always been in the area of language understanding or technologies which relate to it,...
and Terry Winograd
Terry Winograd
Terry Allen Winograd is an American professor of computer science at Stanford University, and co-director of the Stanford Human-Computer Interaction Group...
. It was used to implement Winograd's natural-language understanding program SHRDLU
SHRDLU
SHRDLU was an early natural language understanding computer program, developed by Terry Winograd at MIT from 1968-1970. In it, the user carries on a conversation with the computer, moving objects, naming collections and querying the state of a simplified "blocks world", essentially a virtual box...
, which was a landmark at that time. 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.
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
Algebraic Logic Functional programming language
Algebraic Logic Functional programming language also known as ALF is a programming language which combines functional and logic programming techniques...
, Fril
Fril
Fril is a programming language for first-order predicate calculus. It includes the semantics of Prolog as a subset, but takes its syntax from the micro-Prolog of Logic Programming Associates and adds support for fuzzy sets, support logic, and metaprogramming....
, Gödel, Mercury
Mercury programming language
Mercury is a functional logic programming language geared towards real-world applications. It is developed at the University Of Melbourne Computer Science department under the supervision of Zoltan Somogyi. The first version was developed by Fergus Henderson, Thomas Conway and Zoltan Somogyi and...
, Oz
Oz (programming language)
Oz is a multiparadigm programming language, developed in the Programming Systems Lab at Université catholique de Louvain, for programming language education. It has a canonical textbook: Concepts, Techniques, and Models of Computer Programming....
, Ciao, Visual Prolog
Visual Prolog
Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog, is a strongly typed object-oriented extension of Prolog. As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm Prolog Development Center that originally developed it...
, XSB
XSB
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....
, and λProlog, as well as a variety of concurrent logic programming languages, (see Shapiro (1989) for a survey), constraint logic programming languages and datalog
Datalog
Datalog is a query and rule language for deductive databases that syntactically is a subset of Prolog. Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker organized a workshop on logic and databases...
.
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. The individuals receiving this honor were: Maurice Bruynooghe (Belgium), Jacques Cohen
Jacques Cohen
Jacques Cohen is a Dutch embryologist living in New York, in the U.S. He is currently Director at Reprogenetics, LLC, Laboratory Director at ART Institute of Washington at Walter Reed National Military Medical Center , and Scientific Director of R & D at IVF-online...
(US), Alain Colmerauer
Alain Colmerauer
Alain Colmerauer is a French computer scientist.After completing his Ph.D. at the University of Grenoble, he spent 1967–1970 as Assistant Professor at the University of Montreal, where he created Q-Systems, one of the earliest linguistic formalisms used in the development of the TAUM-METEO machine...
(France), Keith Clark
Keith Clark
Keith L. Clark is a Professor of Computer Science at Imperial College London, England. He has lectured in both mathematics and computer science. Since 1979 he has had a tenured position in the Department of Computing, Imperial College London, where he has been Professor of Computational Logic...
(UK), Veronica Dahl (Canada/Argentina), Maarten van Emden (Canada), Herve Gallaire (France), Robert Kowalski
Robert Kowalski
Robert "Bob" Anthony Kowalski is a British logician and computer scientist, who has spent most of his career in the United Kingdom....
(UK), Jack Minker
Jack Minker
Jack Minker is a leading authority in artificial intelligence, deductive databases, logic programming and non-monotonic reasoning. He is also an internationally recognized leader in the field of human rights of computer scientists.-Career:...
(US), Fernando Pereira (US), Luis Moniz Pereira
Luis Moniz Pereira
Luís Moniz Pereira was born in 1947 in Lisbon, Portugal and is currently Professor of Computer Science and Director of the AI centre at Universidade Nova de Lisboa...
(Portugal), Ray Reiter (Canada), Alan Robinson
J. Alan Robinson
John Alan Robinson is a philosopher , mathematician and computer scientist. He is University Professor Emeritus at Syracuse University, United States....
(US), Peter Szeredi (Hungary), and David H.D. Warren (UK).
Prolog
The programming language PrologProlog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
was developed in 1972 by Alain Colmerauer
Alain Colmerauer
Alain Colmerauer is a French computer scientist.After completing his Ph.D. at the University of Grenoble, he spent 1967–1970 as Assistant Professor at the University of Montreal, where he created Q-Systems, one of the earliest linguistic formalisms used in the development of the TAUM-METEO machine...
. It emerged from a collaboration between Colmerauer in Marseille
Marseille
Marseille , known in antiquity as Massalia , is the second largest city in France, after Paris, with a population of 852,395 within its administrative limits on a land area of . The urban area of Marseille extends beyond the city limits with a population of over 1,420,000 on an area of...
and Robert Kowalski
Robert Kowalski
Robert "Bob" Anthony Kowalski is a British logician and computer scientist, who has spent most of his career in the United Kingdom....
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
SLD resolution
SLD resolution is the basic inference rule used in logic programming. It is a refinement of resolution, which is both sound and refutation complete for Horn clauses.-The SLD inference rule:...
(1971), behave as top-down 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 :- B1, …, Bn.
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 clause
Horn clause
In mathematical logic, a Horn clause is a clause with at most one positive literal. They are named after the logician Alfred Horn, who first pointed out the significance of such clauses in 1951...
s, where H, B1, …, Bn are all atomic predicate logic formulae, and that SL-resolution could be restricted (and generalised) to LUSH or SLD-resolution
SLD resolution
SLD resolution is the basic inference rule used in logic programming. It is a refinement of resolution, which is both sound and refutation complete for Horn clauses.-The SLD inference rule:...
. 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 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
International Organization for Standardization
The International Organization for Standardization , widely known as ISO, is an international standard-setting body composed of representatives from various national standards organizations. Founded on February 23, 1947, the organization promulgates worldwide proprietary, industrial and commercial...
standard Prolog.
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 PrologProlog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
's implementations and has been called "negation as failure". It is normally written as not(p), where p is an atom whose variables normally have 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(Bi) in the body of program clauses.
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 :- Body1.
- …
- H :- Bodyk.
as a definition of the predicate
- H iff (Body1 or … or Bodyk)
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
Closed world assumption
The closed world assumption is the presumption that what is not currently known to be true, is false. The same name also refers to a logical formalization of this assumption by Raymond Reiter. The opposite of the closed world assumption is the open world assumption , stating that lack of knowledge...
.
As an alternative to the completion semantics, negation as failure can also be interpreted epistemically, as in the stable model semantics
Stable model semantics
The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program completion and the well-founded semantics...
of answer set programming
Answer set programming
Answer set programming is a form of declarative programming oriented towards difficult search problems. It is based on the stable model semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers -- programs for generating stable...
. In this interpretation not(Bi) means literally that Bi 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 top-level atomic goal contain no variables, backward reasoning determines an and-or treeAnd-or tree
An and–or tree is a graphical representation of the reduction of problems to conjunctions and disjunctions of subproblems .-Example:The 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".
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 knowledgeKnowledge representation
Knowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
. The inclusion of negation as failure means that logic programming is a kind of non-monotonic logic
Non-monotonic logic
A non-monotonic logic is a formal logic whose consequence relation is not monotonic. Most studied formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences. Intuitively, monotonicity indicates that learning a...
.
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
Situation calculus
The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based on that introduced by Ray Reiter in 1991...
and event calculus
Event calculus
The event calculus is a logical language for representing and reasoning about actions and their effects first presented by Robert Kowalski and Marek Sergot in 1986.It was extended by Murray Shanahan and Rob Miller in the 1990s....
.
Abductive logic programming
Abductive Logic ProgrammingAbductive logic programming
Abductive logic programming is a high level knowledge-representation framework that can be used to solve problems declaratively based on abductive reasoning. It extends normal logic programming by allowing some predicates to be incompletely defined, declared as abducible predicates...
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
Abductive reasoning
Abduction is a kind of logical inference described by Charles Sanders Peirce as "guessing". The term refers to the process of arriving at an explanatory hypothesis. Peirce said that to abduce a hypothetical explanation a from an observed surprising circumstance b is to surmise that a may be true...
) 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 progam is the so-called "vanilla" meta-interpreter: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 object-level clause of the form A :- B.
Metalogic programming allows object-level 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 goal-reduction using program clauses, but are added to a store of constraints, which is required to be consistent with some built-in 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
Civil engineering
Civil engineering is a professional engineering discipline that deals with the design, construction, and maintenance of the physical and naturally built environment, including works like roads, bridges, canals, dams, and buildings...
, mechanical engineering
Mechanical engineering
Mechanical engineering is a discipline of engineering that applies the principles of physics and materials science for analysis, design, manufacturing, and maintenance of mechanical systems. It is the branch of engineering that involves the production and usage of heat and mechanical power for the...
, digital circuit
Digital circuit
Digital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...
verification, automated timetabling, air traffic control
Air traffic control
Air traffic control is a service provided by ground-based controllers who direct aircraft on the ground and in the air. The primary purpose of ATC systems worldwide is to separate aircraft to prevent collisions, to organize and expedite the flow of traffic, and to provide information and other...
, and finance. It is closely related to abductive logic programming
Abductive logic programming
Abductive logic programming is a high level knowledge-representation framework that can be used to solve problems declaratively based on abductive reasoning. It extends normal logic programming by allowing some predicates to be incompletely defined, declared as abducible predicates...
.
Concurrent logic programming
Keith ClarkKeith Clark
Keith L. Clark is a Professor of Computer Science at Imperial College London, England. He has lectured in both mathematics and computer science. Since 1979 he has had a tenured position in the Department of Computing, Imperial College London, where he has been Professor of Computational Logic...
, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
-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)
Fifth generation computer
The Fifth Generation Computer Systems project was an initiative by Japan'sMinistry of International Trade and Industry, begun in 1982, to create a "fifth generation computer" which was supposed to perform much calculation using massive parallel processing...
. However, the Prolog-like concurrent systems were based on message passing and consequently were subject to the same indeterminacy as other concurrent message-passing systems, such as Actors
Actor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
(see Indeterminacy in concurrent computation). Consequently, the ICOT languages were not based on logic in the sense that computational steps could not be logically deduced [Hewitt and Agha, 1988].
Concurrent constraint logic programming
Concurrent constraint logic programming
Concurrent constraint logic programming is a version of constraint logic programming aimed primarily at programming concurrent processes rather than solving constraint satisfaction problems...
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. Generalizations, as well as the examples and background knowledge, are expressed in logic programming syntax. Recent work in this area, combining logic programming, learning and probability, has given rise to the new field of statistical relational learningStatistical relational learning
Statistical relational learning is a subdiscipline of artificial intelligence and machine learning that is concerned with models of domains that exhibit both uncertainty and complex, relational structure...
and probabilistic inductive logic programming.
Higher-order logic programming
Several researchers have extended logic programming with higher-order programming features derived from higher-order logicHigher-order logic
In mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and a stronger semantics...
, such as predicate variables. Such languages include the Prolog extensions HiLog and λProlog.
Linear logic programming
Basing logic programming within linear logicLinear logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter...
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-directed interpretation of all of linear logic.
See also
- Boolean satisfiability problemBoolean satisfiability problemIn computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
- Constraint logic programming
- DatalogDatalogDatalog is a query and rule language for deductive databases that syntactically is a subset of Prolog. Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker organized a workshop on logic and databases...
- Functional programmingFunctional programmingIn computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
- Inductive logic programmingInductive logic programmingInductive logic programming is a subfield of machine learning which uses logic programming as a uniform representation for examples, background knowledge and hypotheses...
- Fuzzy logicFuzzy logicFuzzy logic is a form of many-valued logic; it deals with reasoning that is approximate rather than fixed and exact. In contrast with traditional logic theory, where binary sets have two-valued logic: true or false, fuzzy logic variables may have a truth value that ranges in degree between 0 and 1...
- Logic in computer science (includes Formal methodsFormal methodsIn computer science and software engineering, formal methods are a particular kind of mathematically-based techniques for the specification, development and verification of software and hardware systems...
) - Logic programming languages
- Programming paradigmProgramming paradigmA programming paradigm is a fundamental style of computer programming. Paradigms differ in the concepts and abstractions used to represent the elements of a program and the steps that compose a computation A programming paradigm is a fundamental style of computer programming. (Compare with a...
- R++R++R++ is a rule-based programming language based on C++. The United States patent describes R++ as follows:The R++ extension permits rules to be defined as members of C++ classes...
- Satisfiability
General introductions
- Chitta Baral and Michael Gelfond. Logic programming and knowledge representation Journal of Logic Programming. 1994, Vol. 19, 73-148.
- Robert Kowalski. The Early Years of Logic Programming CACM. January 1988.
- J. W. Lloyd. Foundations of Logic Programming (2nd edition). Springer-Verlag 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), 327-365.
- Naoki Kobayashi and Akinori YonezawaAkinori Yonezawais a Japanese computer scientist specializing in object-oriented programming, distributed computing and information security. Being a graduate of the University of Tokyo, Yonezawa has a Ph.D in computer science from MIT in the Actor group at the MIT AI Lab. He currently teaches at the University of...
. Asynchronous communication model based on linear logic, Formal Aspects of Computing, 1994, 279-294. - 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 senseCommon senseCommon sense is defined by Merriam-Webster as, "sound and prudent judgment based on a simple perception of the situation or facts." Thus, "common sense" equates to the knowledge and experience which most people already have, or which the person using the term believes that they do or should have...
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 Question-Answering 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 SS-06-08. AAAI Press. March 2006.
- Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov: Complexity and expressive power of logic programming. ACM Comput. Surv. 33(3): 374-425 (2001)
- Ulf Nilsson and Jan Maluszynski, Logic, Programming and Prolog