Logic programming

From Free net 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

[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 an existing theory. Logic provides a way to prove 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. Logical programming systems automate this process. Artificial Intelligence was an important influence on the development of logic programming.

[edit]

Prolog

Prolog was an early programming language that was billed by its designers as being based on mathematical logic. The basis for the claim that Prolog was that it used backward chaining from goal to subgoal (as in Planner).

Schematically, the process is: 

   goal :-  subgoal1, ..., subgoaln.

which states that in order to prove goal, it is sufficient to prove subgoal1 through subgoaln.

[edit]

Limitations of Prolog as logic programming

However, Prolog did not include the negation or disjunction of mathematical logic because both individually and together they cause a lot of trouble for the Prolog interpreter. For example if negation were included, the following Prolog program 

       not Q.
       Q :- P.

would be unable to prove not P even though it follows by the rules of mathematical logic. This is an illustration of the fact that Prolog is unable to prove many of the logical consequences that follow from a declarative reading of its programs. However, certain dialects do implement negation as failure typically using the characters \+ or ~.

[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 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, Herve 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

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

External links

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:邏輯編程

Retrieved from "http://www.netipedia.com/index.php/Logic_programming"