Francais | English | Espanõl

From Wikipedia, the free encyclopedia

Logic programming (sometimes called logical programming) is programming that makes use of pattern-directed invocation of procedures from assertions and goals. John McCarthy [1958] was the first to publish a proposal that mathematical logic be used for programming. The first logic programming language was Planner which 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. Subsequently, Prolog was developed as a simplification of Planner that had pattern-directed invocation only from goals (also based on backtracking). From Planner there developed the programming languages QA-4, Popler, Conniver, and QLISP. The programming languages Mercury, Visual Prolog, Oz and Fril developed from Prolog. There are also concurrent logic programming languages (not based on backtracking) derived from Planner (e.g., Ether) and derived from Prolog (see Shapiro [1989] for a survey).

Contents 1 Basis in mathematical logic 2 Prolog 2.1 Negation in logic programming 2.2 Prolog Implementation 3 Limitations of using mathematical logic for programming 4 Concurrent logic programming 5 Higher-order logic programming 6 Application domains 7 History 8 See also 9 References 10 External links

[edit] Basis in mathematical logic

The point of logic programming is to bring the style of mathematical logic to computer programming. Mathematicians and philosophers find logic a successful tool for developing bodies of theory. Many problems are naturally expressed as a theory. To say a problem needs solving is often equivalent to asking if a new hypothesis is consistent with, or is a consequence of an existing theory. Logic provides a way of proving whether the question is true or false. The process of constructing a proof is well-known, so logic is thought to be a reliable way to answer questions. Logic programming systems automate this process. Artificial Intelligence was an important influence on the development of logic programming.

[edit] Prolog

Prolog was a programming language introduced in 1972 by Colmerauer in Marseille and more formally by Kowalski in 1974, and was explicitly presented as being based on mathematical logic. The basis for this claim was that a Prolog program could be read literally as a set of formulas in a subset of first order logic, and hence inherited the model theory and proof theory of first order logic. A program clause

   H :-  B1, ..., Bn.

can be read either as a logical implication (its declarative reading)

   B1 and ... and Bn implies H

where all variables in the clause were universally quantified, or as a backward chaining rule (its procedural reading) which states that in order to prove H, it is sufficient to prove B₁ through B_n. The procedural semantics was also formulated as the construction of a refutation proof using linear resolution (LUSH or SLD resolution). The close relationship between the declarative and the procedural semantics remains a distinctive feature of logic programming languages, though the relationship becomes more complex when negation, disjunction and other quantifiers are allowed in programs.

[edit] Negation in logic programming

If a logic program consists of clauses H :- B₁, ..., B_n where H, B₁, ..., B_n are all atomic predicate logic formulae then the program is called a definite or Horn clause program. The declarative and procedural semantics of definite logic programs is straightforwardly adopted from predicate logic. With the inclusion of negation, the relationship with classical logic becomes less straightforward. The so-called negation-as-failure inference rule states that, if a goal Q cannot be proven from a program then its negation not(Q) is regarded as proven. This is clearly not the case in general in classical logic; it is quite possible that neither Q nor not(Q) is a consequence of a set of axioms. As a result, this rule leads to some logical anomalies and practical difficulties. A backward chaining proof rule augmented with negation-as-failure is incomplete, meaning that it is unable to prove all of the logical consequences that follow from a declarative reading of its programs. However, most Prolog dialects do implement negation as failure typically using the characters \+.

Though not complete, the negation-as-failure rule is a sound inference rule (under certain restrictions) with respect to the completion of a program. Completion of a logic program was first defined by Keith Clark and 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 the single equivalence formula

     H iff (Body1 or ... or Bodyk)

where iff means equivalence (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. The notion of completion is closely related to McCarthy's circumscription technique for handling non-monotonic reasoning, and the assumption of a closed world.

[edit] Prolog Implementation

The first Prolog implementation was Marseille Prolog, developed in 1972. 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.

[edit] Limitations of using mathematical logic for programming

John McCarthy proposed that mathematical logic be used as the foundation for the epistemology of computer systems. Under the leadership of Marvin Minsky and Seymour Papert a different approach based on procedural approaches was developed at MIT. When Planner was developed, the question arose about the relationship between the two approaches. Robert Kowalski developed the thesis that “computation could be subsumed by deduction” and quoted with approval “Computation is controlled deduction.” which he attributed to Pat Hayes in his 1988 paper on the early history of Prolog. Contrary to Kowalski and Hayes, Carl Hewitt developed the thesis that logical deduction was incapable of carrying out concurrent computation in open systems. (See Indeterminacy in computation.)

The answer to the question about the relationship between the logical and procedural approaches is that the procedural approach has a different mathematical semantics (see Denotational semantics) from the semantics of mathematical logic (see Model theory).

[edit] Concurrent logic programming

Keith Clark, Hervé Gallaire, 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).

Like the Actor model, the Prolog-like concurrent systems were based on message passing and consequently were subject to the same indeterminacy. This was the basis of an argument by Carl Hewitt and Gul Agha [1988] claiming that the Prolog-like concurrent systems were neither deductive nor logical.

[edit] 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.

[edit] Application domains

• Expert systems, where the program generates a recommendation or answer from a large model of the application domain.
• Automated theorem proving, where the program generates novel theorems to extend some existing body of theory.

[edit] History

Logic Programming is an idea that has been investigated in the context of artificial intelligence since at least the time of John McCarthy [1958] which proposed

"programs to manipulate in a suitable formal language (most likely a part of the predicate calculus) common instrumental statements. The basic program will draw immediate conclusions from a list of premises. These conclusions will be either declarative or imperative sentences. When an imperative sentence is deduced the program takes a corresponding action.”

McCarthy justified his proposal as follows

"'The main advantages we expect the advice taker to have is that its behavior will be improvable merely by making statements to it, telling it about its symbolic environment and what is wanted from it. To make these statements will require little if any knowledge of the program or the previous knowledge of the advice taker. One will be able to assume that the advice taker will have available to it a fairly wide class of immediate logical consequences of anything it is told and its previous knowledge. This property is expected to have much in common with what makes us describe certain humans as having common sense. We shall therefore say that a program has common sense if it automatically deduces for itself a sufficiently wide class of immediate consequences of anything it is told and what it already knows."

[edit] See also

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

[edit] 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 Predicate Logic as a Programming Language Memo 70, Department of Artificial Intelligence, Edinburgh University. 1973.
• 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 limitation 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.

[edit] 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 Ozbs:Logičko programiranje

de:Logische Programmierung es:Programación lógica fr:Programmation logique io:Logika programeso nl:Logisch programmeren pl:Programowanie logiczne ru:Логическое программирование fi:Logiikkapohjainen ohjelmointikieli th:การเขียนโปรแกรมเชิงตรรกะ zh:邏輯編程