Citizendia
Your Ad Here

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. John McCarthy (born September 4, 1927, in Boston, Massachusetts) is an American Computer scientist and Cognitive The advice taker was a hypothetical Computer program, proposed by John McCarthy in his 1958 paper "Programs with Common Sense". 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.

The programmer is responsible, not only for ensuring the truth of programs, but also for ensuring their efficiency. In many cases, to achieve efficiency, the programmer needs to be aware of and to exploit the problem-solving behavior of the theorem-prover. In this respect, logic programming is like conventional imperative programming, using programs to control the behaviour of a program executor. In Computer science, imperative programming is a Programming paradigm that describes computation in terms of statements that change a program state However, unlike imperative programs, which have only a procedural interpretation, logic programs also have a declarative, logical interpretation, which helps to ensure their correctness. Moreover, such programs, being declarative, are at a higher conceptual level than purely imperative programs; and their program executors, being theorem-provers, operate at a higher conceptual level than conventional compilers and interpreters. A compiler is a Computer program (or set of programs that translates text written in a computer language (the source language) into another In Computer science, an interpreter normally means a Computer program that executes, i

Contents

History

Logic programming in the first and wider sense gave rise to a number of implementations, such as those by Fischer Black (1964), James Slagle (1965) and Cordell Green (1969), which were question-answering systems in the spirit of McCarthy's advice-taker. Fischer Sheffey Black ( January 11, 1938 - August 30, 1995) was an American Economist, best known as one of the authors Foster and Elcock's Absys (1969), on the other hand, was probably the first language to be explicitly developed as an assertional programming language.

Logic programming in the narrower sense can be traced back to debates in the late 1960s and early 1970s about declarative versus procedural representations of knowledge in Artificial Intelligence. Advocates of declarative representations were notably working at Stanford, associated with John McCarthy, Bertram Raphael and Cordell Green, and in Edinburgh, with J. Alan Robinson (an academic visitor from Syracuse University), Pat Hayes, and Bob Kowalski. Leland Stanford Junior University, commonly known as Stanford University or simply Stanford, is a private Research university located in John McCarthy (born September 4, 1927, in Boston, Massachusetts) is an American Computer scientist and Cognitive The University of Edinburgh (Oilthigh Dhùn Èideann founded in 1582 is a renowned centre for teaching and research in Edinburgh, Scotland, UK. Syracuse University (SU is a private research university located in Syracuse, New York. Patrick John Hayes or Pat Hayes ( 21 August 1944) is a British Computer scientist who lives and works in the United States Robert "Bob" Anthony Kowalski (born May 15, 1941, in Bridgeport, Connecticut, U Advocates of procedural representations were mainly centered at MIT, under the leadership of Marvin Minsky and Seymour Papert. Marvin Lee Minsky (born August 9, 1927) is an American cognitive scientist in the field of Artificial intelligence (AI co-founder Seymour Papert (born February 29, 1928 in Pretoria South Africa) is an MIT Mathematician, computer scientist, and

Although it was based on logic, Planner, developed at MIT, was the first language to emerge within this proceduralist paradigm [Hewitt, 1969]. Planner (often seen in publications as "PLANNER" although it is not an acronym is a Programming language designed by Carl Hewitt at MIT, and Planner featured pattern directed invocation of procedural plans from goals (i. e. forward chaining) and from assertions (i. Forward chaining is one of the two main methods of reasoning when using Inference rules (in Artificial intelligence) e. backward chaining). Backward chaining (or backward reasoning) is an inference method used in Artificial intelligence. The most influential implementation of Planner was the subset of Planner, called Micro-Planner, implemented by Gerry Sussman, Eugene Charniak and Terry Winograd. Gerald Jay Sussman is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT Eugene Charniak is a Computer Science and Cognitive Science professor at Brown University. Terry Allen Winograd (born February 24, 1946) is an American Professor of Computer science at Stanford University, and It was used to implement Winograd's natural-language understanding program SHRDLU, which was a landmark at that time. SHRDLU was an early Natural language understanding Computer program, developed by Terry Winograd at MIT from 1968-1970 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. Algebraic Logic Functional programming language also known as ALF is a Programming language which combines functional and Logic programming techniques Fril is a Programming language for First-order predicate calculus. Gödel is a declarative, general-purpose Programming language that adheres to the logic Programming paradigm. Mercury is a functional logic Programming language geared towards real-world applications Oz is a Multiparadigm programming language, developed in the Programming Systems Lab at Saarland University. Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog is a strongly typed object-oriented extension of Prolog. XSB is the name of a dialect of the Prolog Programming language and its implementation developed at Stony Brook University in collaboration with the Constraint logic programming is a form of Constraint programming, in which Logic programming is extended to include concepts from Constraint satisfaction Datalog is a query and rule language for Deductive databases that syntactically is a subset of Prolog.

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 (USA), Alain Colmerauer (France), Keith Clark (UK), Veronica Dahl (Canada/Argentina), Maarten van Emden (Canada), Herve Gallaire (France), Robert Kowalski (UK), Jack Minker (USA), Fernando Pereira (USA), Luis Moniz Pereira (Portugal), Ray Reiter (Canada), Alan Robinson (USA), Peter Szeredi (Hungary), and David H.D. Warren (UK). Alain Colmerauer (born 24 January 1941) is a French Computer scientist. Keith L Clark is a Professor of Computer Science at Imperial College London. Robert "Bob" Anthony Kowalski (born May 15, 1941, in Bridgeport, Connecticut, U Jack Minker is a leading authority in Artificial intelligence, Deductive databases Logic programming and Non-monotonic reasoning. See Fernando "Cobo" Pereira for the officer of São Tomé and Príncipe. 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 Raymond Reiter ( June 12, 1939 &ndash September 16, 2002) was a Canadian Computer scientist and Logician. David H D Warren is a Computer scientist ( PhD Artificial intelligence, University of Edinburgh 1977)

Prolog

Main article: Prolog

The programming language Prolog was developed in 1972 by Alain Colmerauer. Prolog is a Logic programming language It is a general purpose language often associated with Artificial intelligence and Computational linguistics Prolog is a Logic programming language It is a general purpose language often associated with Artificial intelligence and Computational linguistics Alain Colmerauer (born 24 January 1941) is a French Computer scientist. It emerged from a collaboration between Colmerauer in Marseille and Robert Kowalski in Edinburgh. Marseille, ( English alt Marseilles mɑrˈseɪ — French: maʁsɛj locally — Provençal Occitan: Marselha maʀˈsijɔ Robert "Bob" Anthony Kowalski (born May 15, 1941, in Bridgeport, Connecticut, U 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. SLD resolution ( Selective Linear Definite clause resolution is the basic inference rule used in Logic programming.

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 clauses, where H, B1, …, Bn are all atomic predicate logic formulae, and that SL-resolution could be restricted (and generalised) to LUSH or SLD-resolution. In Mathematical logic, a Horn clause is a clause (a Disjunction of literals with at most one positive literal SLD resolution ( Selective Linear Definite clause resolution is the basic inference rule used in Logic programming. 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. Lisp (or LISP) is a family of Computer Programming languages with a long history and a distinctive fully parenthesized syntax Edinburgh Prolog became the de facto standard and strongly influenced the definition of ISO standard Prolog.

Negation as failure

Main article: 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. Negation as failure ( NAF, for short is a non-monotonic inference rule in Logic programming, used to derive not~p from failure to derive p An equivalent operator is normally built-in in modern Prolog's implementations and has been called "negation as failure". Prolog is a Logic programming language It is a general purpose language often associated with Artificial intelligence and Computational linguistics Negation as failure ( NAF, for short is a non-monotonic inference rule in Logic programming, used to derive not~p from failure to derive p 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. The closed world assumption is the presumption that what is not currently known to be true is false

As an alternative to the completion semantics, negation as failure can also be interpreted epistemically, as in the stable model semantics of answer set programming. The concept of a stable model, or answer set is used to define a declarative semantics for logic programs with Negation as failure. Answer set programming (ASP is a form of Declarative programming oriented towards difficult (primarily NP-hard) search problems. 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 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 knowledge. Knowledge representation is an area in Artificial intelligence that is concerned with how to formally "think" that is how to use a symbol system to represent The inclusion of negation as failure means that logic programming is a kind of non-monotonic logic. Negation as failure ( NAF, for short is a non-monotonic inference rule in Logic programming, used to derive not~p from failure to derive p A non-monotonic logic is a Formal logic whose consequence relation is not monotonic.

Despite its simplicity compared with classical logic, this combination of Horn clauses and negation as failure has proved to be surprisingly expressive. For example, it has been shown to correspond, with some further extensions, quite naturally to the semi-formal language of legislation. It is also a natural language for expressing common-sense laws of cause and effect, as in the situation calculus and event calculus. The situation calculus is a Logic formalism designed for representing and reasoning about dynamical domains 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

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. Abductive Logic Programming is a high level knowledge-representation framework that can be used to solve problems declaratively based on Abductive reasoning. 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). Abduction, or inference to the best explanation, is a method of Reasoning in which one chooses the hypothesis that would if true best explain the relevant evidence 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.

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. Constraint logic programming is a form of Constraint programming, in which Logic programming is extended to include concepts from Constraint satisfaction 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, mechanical engineering, digital circuit verification, automated timetabling, air traffic control, and finance. Civil engineering is a professional engineering discipline that deals with the design construction and maintenance of the physical and naturally built Mechanical Engineering is an Engineering discipline that involves the application of principles of physics for analysis Design, Manufacturing Digital electronics are Electronics systems that use Digital signals Digital electronics are representations of Boolean algebra also see Air traffic control ( ATC) is a service provided by ground-based controllers who direct Aircraft on the ground and in the air It is closely related to 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.

Concurrent logic programming

Keith Clark, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. Keith L Clark is a Professor of Computer Science at Imperial College London. developed a family of Prolog-like concurrent message passing systems using unification of shared variables and data structure streams for messages. Prolog is a Logic programming language It is a general purpose language often associated with Artificial intelligence and Computational linguistics Efforts were made to base these systems on mathematical logic, and they were used as the basis of the Japanese Fifth Generation Project (ICOT). For the Fifth Generation of Chinese filmmakers see Cinema of China-The rise of the Fifth Generation. 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). In Computer science, the Actor model is a mathematical model of Concurrent computation that treats "actors" as the universal primitives of concurrent Indeterminacy in concurrent computation is concerned with the effects of Indeterminacy in Concurrent computation. Consequently, the ICOT languages were not based on 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. Concurrent constraint logic programming is a version of Constraint logic programming aimed primarily at programming Concurrent processes rather than (or in addition Constraint logic programming is a form of Constraint programming, in which Logic programming is extended to include concepts from Constraint satisfaction 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. Inductive logic programming ( ILP) is a subfield of Machine learning which uses Logic programming as a uniform representation for examples 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 learning and probabilistic inductive logic programming.

Higher-order logic programming

Several researchers have extended logic programming with higher-order programming features derived from higher-order logic, such as predicate variables. Higher-order programming is a style of programming that exploits the theoretical ability to use functions as values it is usually instantiated with or borrowed from models In Mathematics, higher-order logic is distinguished from First-order logic in a number of ways 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. In Mathematical logic, linear logic is a type of Substructural logic that denies the Structural rules of weakening and contraction. Horn clause programs can only represent state change by the change in arguments to predicates. In linear logic programming, one can use the ambient linear logic to support state change. Some early designs of logic programming languages based on linear logic include LO [Andreoli & Pareschi, 1991], Lolli [Hodas & Miller, 1994], ACL [Kobayashi & Yonezawa, 1994], and Forum [Miller, 1996]. Forum provides a goal-direct interpretation of all of linear logic.

See also

References

External links

Oz is a Multiparadigm programming language, developed in the Programming Systems Lab at Saarland University.
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic