Logic Programming

Logic programming is the use of LOGIC to represent programs and of deduction to execute programs in LOGICAL FORM. To this end, many different forms of logic and many varieties of deduction have been investigated. The simplest form of logic, which is the basis of most logic programming, is the Horn clause subset of logic, where programs consist of sets of implications: A₀ if A₁ and A ₂ and ... and A_n. Here each A_i is a simple (i.e., atomic) sentence.

Because deduction by backward reasoning interprets such implications as procedures, it is usual to write them backward: to solve the goal A₀, solve the subgoals A₁ and A₂ and . . . and A_n. The number of conditions, n, can be 0, in which case the implication is simply a fact, which behaves as a procedure which solves goals directly without introducing subgoals.

The procedural interpretation of implications can be used for declarative programming, where the programmer describes information in logical form and the deduction mechanism uses backward reasoning to achieve problem solving behavior. Consider, for example, the implication

X is a citizen of the United States
  if X was born in the United States.

Backward reasoning treats the sentence as a procedure:

To show X is a citizen of the United States,
show that X was born in the United States.

In fact, backward reasoning can be used, not only to show a particular person is a citizen, but also to find people who are citizens by virtue of having been born in the United States.

Logic programs are nondeterministic in the sense that many different procedures might apply to the same goal. For example, naturalization and being the child of a citizen provide alternative procedures for obtaining citizenship. The nondeterministic exploration of alternative procedures, to find one or more which solve a given goal, can be performed by many different search strategies. In the logic programming language Prolog, search is performed depth-first, trying procedures one at a time, in the order in which they are written, backtracking in case of failure.

Declarative programming is an ideal. The programmer specifies what the problem is and what knowledge should be used in solving problems, and the computer determines how the knowledge should be used. The declarative programming ideal works in some cases where the knowledge has a particularly simple form. But it fails in many others, where nondeterminism leads to an excessively inefficient search. This failure has led many programmers to reject logic programming in favor of conventional, imperative programming languages.

The following example shows the kind of problem that can arise with declarative programming:

There is a path from X to Y if there is a step from X to Y.

There is a path from X to Y if there is a path from X to Z and there is a path from Z to Y.

Given no other information and the goal of showing whether there is a path from a node a to a node b, Prolog fails to find a step from a to b using the first procedure. It therefore tries to find a path from a to some Z using the second procedure. There is no step from a to any Z using the first procedure. So Prolog tries to find a path from a to some Z' using the second procedure. Continuing in this way, it goes into an infinite loop, looking for paths from a to Z, to Z' to Z'', . . . .

The alternative to rejecting logic programming because of such problems or of restricting it to niche applications, is for the programmer to take responsibility for both the declarative correctness and the procedural efficiency of programs. The following is such a correct and efficient logic program for the path-finding problem. It incrementally constructs a path of nodes already visited and ensures that no step is taken that revisits a node already in the path. The goal of showing there is a path from X to Y is reformulated as the goal of extending the path consisting of the single node X to a path ending at Y. For simplicity, a path is regarded as a trivial extension of itself .

The path P can be extended to a path ending at Y
  if P ends at Y.
The path P can be extended to a path ending at Y
   if P ends at X
and there is a step from X to Z
and Z is not in P
and P' extends P by adding Z to the end of P
and the path P' can be extended to a path ending at Y.

It is usual to interpret the negation in a condition, such as "Z is not in P" above, as negation by failure. A subgoal of the form "not A" is deemed to hold if and only if the positive subgoal "A" cannot be shown to hold. Programs containing such negative conditions, extending the Horn clause subset of logic programming, are called "normal logic programs."

The use of negation as failure renders logic programming a NONMONOTONIC LOGIC, where addition of new information may cause a previously justified conclusion to be withdrawn. A simple example is the sentence

The condition "not X is guilty" is interpreted as "it cannot be shown that X is guilty."

Many extensions of normal logic programming have been investigated. Among the most important of these is the extension that includes METAREASONING. For example, the following implication is a fragment of a metalevel logic program that can be used to reason about the interval of time for which a conclusion holds:

"R" holds for interval I
   if "R if S" holds for interval I₁
and "S" holds for interval I₂
and I is the intersection of I₁ and I₂.

Similar metalevel programs are used to construct explanations and to implement resource-bounded reasoning and reasoning with UNCERTAINTY.

Among the other extensions of logic programming being investigated are extensions to incorporate constraint processing, a second "strong" form of negation, disjunctive conclusions, and abductive reasoning. Methods are being developed both to execute programs efficiently and to transform inefficient programs into more efficient ones. Applications range from natural language processing and legal reasoning to commercial knowledge management systems and parts of the Windows NT operating system.

See also

• BOUNDED RATIONALITY
• CONSTRAINT SATISFACTION
• DEDUCTIVE REASONING
• INDUCTIVE LOGIC PROGRAMMING
• LOGICAL REASONING SYSTEMS
• SITUATION CALCULUS

Additional links

• DIGITAL
• PC AI - Logic Programming
• The World Wide Web Virtual Library: Logic Programming

-- Robert Kowalski

Further Readings

Apt, K., and F. Turini, Eds. (1995). Meta-Logics and Logic Programming. Cambridge, MA: MIT Press.

Bratko, I. (1988). Prolog Programming for Artificial Intelligence. Reading, MA: Addison-Wesley.

Clark, K. L. (1978). Negation by failure. In H. Gallaire and J. Minker, Eds., Logic and Databases. New York: Plenum Press, pp. 293-322.

Colmerauer, A., H. Kanoui, R. Pasero, and P. Roussel. (1973). Un système de communication homme-machine en français. Research report, Groupe d'Intelligence Artificielle. Université d'Aix-Marseilles II, Luminy, France.

Flach, P. (1994). Simply Logical: Intelligent Reasoning by Example. New York: Wiley.

Gabbay, D., C. Hogger, and J. A. Robinson. (1993). Handbook of Logic in Artificial Intelligence and Logic Programming. Vol. 1, Logic Foundations. Oxford: Clarendon Press.

Gabbay, D., C. Hogger, and J. A. Robinson. (1997). Handbook of Logic in Artificial Intelligence and Logic Programming. Vol. 5, Logic Programming. Oxford: Clarendon Press.

Gillies, D. (1996). Artificial Intelligence and Scientific Method. New York: Oxford University Press.

Kowalski, R. (1974). Predicate logic as programming language. In Proceedings IFIP Congress, Stockholm. Amsterdam: Elsevier, pp. 569-574.

Kowalski, R. (1979). Logic for Problem Solving. Amsterdam: Elsevier.

Kowalski, R. (1992). Legislation as logic programs. In G. Comyn, N. E. Fuchs, and M. J. Ratcliffe, Eds., Logic Programming in Action. New York: Springer, pp. 203-230.

Lloyd J. W. (1987). Foundations of Logic Programming. 2nd ed. New York: Springer .

Copyright © 1999 Massachusetts Institute of Technology