SUPPORT THE WORK

# GetWiki

### logic programming

ARTICLE SUBJECTS
news  →
unix  →
wiki  →
ARTICLE TYPES
feed  →
help  →
wiki  →
ARTICLE ORIGINS
logic programming
[ temporary import ]
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{redirect|Rule-Based|the method of machine translation|Rule-based machine translation|methods of machine learning|Rule-based machine learning}}{{Programming paradigms}}Logic programming is a type of programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, answer set programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:
H :- B1, â€¦, Bn.
and are read declaratively as logical implications:
H if B1 and â€¦ and Bn.
H is called the head of the rule and B1, â€¦, Bn is called the body. Facts are rules that have no body, and are written in the simplified form:
H.
In the simplest case in which H, B1, â€¦, Bn are all atomic formulae, these clauses are called definite clauses or Horn clauses. However, there exist many extensions of this simple case, the most important one being the case in which conditions in the body of a clause can also be negations of atomic formulae. Logic programming languages that include this extension have the knowledge representation capabilities of a non-monotonic logic.In ASP and Datalog, logic programs have only a declarative reading, and their execution is performed by means of a proof procedure or model generator whose behaviour is not meant to be under the control of the programmer. However, in the Prolog family of languages, logic programs also have a procedural interpretation as goal-reduction procedures:
to solve H, solve B1, and ... and solve Bn.
Consider, for example, the following clause:
fallible(X) :- human(X).
based on an example used by Terry WinogradJOURNAL, T. Winograd, Understanding natural language, Cognitive Psychology, 3, 1, 1972, 1â€“191, 10.1016/0010-0285(72)90002-3, to illustrate the programming language Planner. As a clause in a logic program, it can be used both as a procedure to test whether X is fallible by testing whether X is human, and as a procedure to find an X that is fallible by finding an X that is human. Even facts have a procedural interpretation. For example, the clause:
human(socrates).
can be used both as a procedure to show that socrates is human, and as a procedure to find an X that is human by "assigning" socrates to X.The declarative reading of logic programs can be used by a programmer to verify their correctness. Moreover, logic-based program transformation techniques can also be used to transform logic programs into logically equivalent programs that are more efficient. In the Prolog family of logic programming languages, the programmer can also use the known problem-solving behaviour of the execution mechanism to improve the efficiency of programs.

## Concepts

### Logic and control

Logic programming can be viewed as controlled deduction. An important concept in logic programming is the separation of programs into their logic component and their control component. With pure logic programming languages, the logic component alone determines the solutions produced. The control component can be varied to provide alternative ways of executing a logic program. This notion is captured by the slogan
Algorithm = Logic + Control
where "Logic" represents a logic program and "Control" represents different theorem-proving strategies.JOURNAL, R.A.Kowalski, Algorithm=Logic + Control, Communications of the ACM, 22, 7, July 1979, 424â€“436, 10.1145/359131.359136,

### 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.

### Negation as failure

For most practical applications, as well as for applications that require non-monotonic reasoning in artificial intelligence, Horn clause logic programs need to be extended to normal logic programs, with negative conditions. A clause in a normal logic program has the form:
H :- A1, â€¦, An, not B1, â€¦, not Bn.
and is read declaratively as a logical implication:
H if A1 and â€¦ and An and not B1 and â€¦ and not Bn.
where H and all the Ai and Bi are atomic formulas. The negation in the negative literals not Bi is commonly referred to as "negation as failure", because in most implementations, a negative condition not Bi is shown to hold by showing that the positive condition Bi fails to hold. For example:canfly(X) :- bird(X), not abnormal(X).abnormal(X) :- wounded(X).bird(john).bird(mary).wounded(john).Given the goal of finding something that can fly:
- canfly(X).
there are two candidate solutions, which solve the first subgoal bird(X), namely X = john and X = mary. The second subgoal not abnormal(john) of the first candidate solution fails, because wounded(john) succeeds and therefore abnormal(john) succeeds. However, The second subgoal not abnormal(mary) of the second candidate solution succeeds, because wounded(mary) fails and therefore abnormal(mary) fails. Therefore, X = mary is the only solution of the goal.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 Prolog's implementations. It is normally written as not(Goal) or + Goal, where Goal is some goal (proposition) to be proved by the program. This operator differs from negation in first-order logic: a negation such as + X == 1 fails when the variable X has been bound to the atom 1, but it succeeds in all other cases, including when X is unbound. This makes Prolog's reasoning non-monotonic: X = 1, + X == 1 always fails, while + X == 1, X = 1 can succeed, binding X to 1, depending on whether X was initially bound (note that standard Prolog executes goals in left-to-right order).The logical status of negation as failure was unresolved until Keith Clark [1978] showed that, under certain natural conditions, it is a correct (and sometimes complete) implementation of classical negation with respect to the completion of the program. Completion amounts roughly to regarding the set of all the program clauses with the same predicate on the left hand side, say
H :- 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.For example, the completion of the program above is:
canfly(X) iff bird(X), not abnormal(X). abnormal(X) iff wounded(X). bird(X) iff X = john or X = mary. X = X. not john = mary. not mary = john.
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.

### 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. 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 provides a natural representation for the common-sense laws of cause and effect, as formalised by both the situation calculus and event calculus. It has also been shown to correspond quite naturally to the semi-formal language of legislation. In particular, Prakken and SartorPrakken, H. and Sartor, G., 2015. Law and logic: a review from an argumentation perspective. Artificial Intelligence, 227, 214â€“245. credit the representation of the British Nationality Act as a logic programSergot, M.J., Sadri, F., Kowalski, R.A., Kriwaczek, F., Hammond, P. and Cory, H.T., 1986. The British Nationality Act as a logic program. Communications of the ACM, 29(5), 370â€“386. with being "hugely influential for the development of computational representations of legislation, showing how logic programming enables intuitively appealing representations that can be directly deployed to generate automatic inferences".

## Variants and extensions

### Prolog

The programming language Prolog was developed in 1972 by Alain Colmerauer. It emerged from a collaboration between Colmerauer in Marseille and Robert Kowalski in Edinburgh. Colmerauer was working on natural language understanding, using logic to represent semantics and using resolution for 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
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. 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.

### Abductive logic programming

Abductive logic programming is an extension of normal Logic Programming that allows some predicates, declared as abducible predicates, to be "open" or undefined. A clause in an abductive logic program has the form:
H :- B1, â€¦, Bn, A1, â€¦, An.
where H is an atomic formula that is not abducible, all the Bi are literals whose predicates are not abducible, and the Ai are atomic formulas whose predicates are abducible. The abducible predicates can be constrained by integrity constraints, which can have the form:
false :- L1, â€¦, Ln.
where the Li are arbitrary literals (defined or abducible, and atomic or negated). For example:canfly(X) :- bird(X), normal(X).false :- normal(X), wounded(X).bird(john).bird(mary).wounded(john).where the predicate normal is abducible.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 solved (as in normal logic programming). For example, the hypothesis normal(mary) explains the observation canfly(mary). Moreover, the same hypothesis entails the only solution X = mary of the goal of finding something that can fly:
- canfly(X).
Abductive logic programming has been used for fault diagnosis, planning, natural language processing and machine learning. It has also been used to interpret Negation as Failure as a form of abductive reasoning.

### Metalogic programming

Because mathematical logic has a long tradition of distinguishing between object language and metalanguage, logic programming also allows metalevel programming. The simplest metalogic program is the 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. Metalogic is used in logic programming to implement metaprograms, which manipulate other programs, databases, knowledge bases or axiomatic theories as data.

### Constraint logic programming

Constraint logic programming combines Horn clause logic programming with constraint solving. It extends Horn clauses by allowing some predicates, declared as constraint predicates, to occur as literals in the body of clauses. A constraint logic program is a set of clauses of the form:
H :- C1, â€¦, Cn â—Š B1, â€¦, Bn.
where H and all the Bi are atomic formulas, and the Ci are constraints. Declaratively, such clauses are read as ordinary logical implications:
H if C1 and â€¦ and Cn and B1 and â€¦ and Bn.
However, whereas the predicates in the heads of clauses are defined by the constraint logic program, the predicates in the constraints are predefined by some domain-specific model-theoretic structure or theory.Procedurally, subgoals whose predicates are defined by the program are solved by goal-reduction, as in ordinary logic programming, but constraints are checked for satisfiability by a domain-specific constraint-solver, which implements the semantics of the constraint predicates. An initial problem is solved by reducing it to a satisfiable conjunction of constraints.The following constraint logic program represents a toy temporal database of john's history as a teacher:teaches(john, hardware, T) :- 1990 â‰¤ T, T < 1999.teaches(john, software, T) :- 1999 â‰¤ T, T < 2005.teaches(john, logic, T) :- 2005 â‰¤ T, T â‰¤ 2012.rank(john, instructor, T) :- 1990 â‰¤ T, T < 2010.rank(john, professor, T) :- 2010 â‰¤ T, T < 2014.Here â‰¤ and
• John McCarthy. Programs with common sense Symposium on Mechanization of Thought Processes. National Physical Laboratory. Teddington, England. 1958.
• JOURNAL, Uniform proofs as a foundation for logic programming, Annals of Pure and Applied Logic, 51, 1â€“2, 125â€“157, 10.1016/0168-0072(91)90068-W, 1991, Miller, Dale, Nadathur, Gopalan, Pfenning, Frank, Scedrov, Andre,
• Ehud Shapiro (Editor). Concurrent Prolog MIT Press. 1987.
• James Slagle. Experiments with a Deductive Question-Answering Program CACM. December 1965.

{{Programming language}}{{computable knowledge}}{{Authority control}}

- content above as imported from Wikipedia
- "logic programming" does not exist on GetWiki (yet)
- time: 12:08pm EDT - Fri, Aug 23 2019
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 JUL 2019
Eastern Philosophy
History of Philosophy
GETWIKI 09 MAY 2016
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
GETWIKI 20 AUG 2014
GETWIKI 19 AUG 2014
CONNECT