4.4.3 Is Logic Programming Mathematical Logic?

Permalink copied!

The means of combination used in the query language may at first seem identical to the operations and, or, and not of mathematical logic, and the application of query-language rules is in fact accomplished through a legitimate method of inference.[1] This identification of the query language with mathematical logic is not really valid, though, because the query language provides a control structure that interprets the logical statements procedurally. We can often take advantage of this control structure. For example, to find all of the supervisors of programmers we could formulate a query in either of two logically equivalent forms:

and(job($x, list("computer", "programmer")),
    supervisor($x, $y))

and(supervisor($x, $y),
    job($x, list("computer", "programmer")))

If a company has many more supervisors than programmers, it is better to use the first form rather than the second, because the data base must be scanned for each intermediate result (frame) produced by the first clause of the and.

The aim of logic programming is to provide the programmer with techniques for decomposing a computational problem into two separate problems: what is to be computed, and how this should be computed. This is accomplished by selecting a subset of the statements of mathematical logic that is powerful enough to be able to describe anything one might want to compute, yet weak enough to have a controllable procedural interpretation. The intention here is that, on the one hand, a program specified in a logic programming language should be an effective program that can be carried out by a computer. Control (how to compute) is effected by using the order of evaluation of the language. We should be able to arrange the order of clauses and the order of subgoals within each clause so that the computation is done in an order deemed to be effective and efficient. At the same time, we should be able to view the result of the computation (what to compute) as a simple consequence of the laws of logic.

Our query language can be regarded as just such a procedurally interpretable subset of mathematical logic. An assertion represents a simple fact (an atomic proposition). A rule represents the implication that the rule conclusion holds for those cases where the rule body holds. A rule has a natural procedural interpretation: To establish the conclusion of the rule, establish the body of the rule. Rules, therefore, specify computations. However, because rules can also be regarded as statements of mathematical logic, we can justify any inference accomplished by a logic program by asserting that the same result could be obtained by working entirely within mathematical logic.[2]

Infinite loops

A consequence of the procedural interpretation of logic programs is that it is possible to construct hopelessly inefficient programs for solving certain problems. An extreme case of inefficiency occurs when the system falls into infinite loops in making deductions. As a simple example, suppose we are setting up a data base of famous marriages, including

assert(married("Minnie", "Mickey"))

If we now ask

married("Mickey", $who)

we will get no response, because the system doesn't know that if $A$ is married to $B$, then $B$ is married to $A$. So we assert the rule

assert(rule(married($x, $y), 
            married($y, $x)))

and again query

married("Mickey", $who)

Unfortunately, this will drive the system into an infinite loop, as follows:

The system finds that the married rule is applicable; that is, the rule conclusion married($x, $y) unifies with the query pattern married("Mickey", $who) to produce a frame in which $x is bound to "Mickey" and $y is bound to $who. So the interpreter proceeds to evaluate the rule body married($y, $x) in this frame—in effect, to process the query married($who, "Mickey").
One answer, married("Minnie", "Mickey"), appears directly as an assertion in the data base.
The married rule is also applicable, so the interpreter again evaluates the rule body, which this time is equivalent to married("Mickey", $who).

The system is now in an infinite loop. Indeed, whether the system will find the simple answer married("Minnie", "Mickey") before it goes into the loop depends on implementation details concerning the order in which the system checks the items in the data base. This is a very simple example of the kinds of loops that can occur. Collections of interrelated rules can lead to loops that are much harder to anticipate, and the appearance of a loop can depend on the order of clauses in an and (see exercise 4.62) or on low-level details concerning the order in which the system processes queries.[3]

Problems with not

Another quirk in the query system concerns not. Given the data base of section 4.4.1, consider the following two queries:

and(supervisor($x, $y),
    not(job($x, list("computer", "programmer"))))

and(not(job($x, list("computer", "programmer"))),
    supervisor($x, $y))

These two queries do not produce the same result. The first query begins by finding all entries in the data base that match supervisor($x, $y), and then filters the resulting frames by removing the ones in which the value of $x satisfies job($x,list("computer", "programmer")). The second query begins by filtering the incoming frames to remove those that can satisfy job($x, list("computer","programmer")). Since the only incoming frame is empty, it checks the data base for patterns that satisfy job($x, list("computer", "programmer")). Since there generally are entries of this form, the not clause filters out the empty frame and returns an empty stream of frames. Consequently, the entire compound query returns an empty stream.

The trouble is that our implementation of not really is meant to serve as a filter on values for the variables. If a not clause is processed with a frame in which some of the variables remain unbound (as does $x in the example above), the system will produce unexpected results. Similar problems occur with the use of javascript_predicate—the JavaScript predicate can't work if some of its variables are unbound. See exercise 4.74.

There is also a much more serious way in which the not of the query language differs from the not of mathematical logic. In logic, we interpret the statement not $P$ to mean that $P$ is not true. In the query system, however, not $P$ means that $P$ is not deducible from the knowledge in the data base. For example, given the personnel data base of section 4.4.1, the system would happily deduce all sorts of not statements, such as that Ben Bitdiddle is not a baseball fan, that it is not raining outside, and that $2 + 2$ is not 4.[4] In other words, the not of logic programming languages reflects the so-called closed world assumption that all relevant information has been included in the data base.[5]

Exercise 4.62 Louis Reasoner mistakenly deletes the outranked_by rule (section 4.4.1) from the data base. When he realizes this, he quickly reinstalls it. Unfortunately, he makes a slight change in the rule, and types it in as

rule(outranked_by($staff_person, $boss),      
     or(supervisor($staff_person, $boss),
        and(outranked_by($middle_manager, $boss),
            supervisor($staff_person, $middle_manager))))

Just after Louis types this information into the system, DeWitt Aull comes by to find out who outranks Ben Bitdiddle. He issues the query

outanked_by(list("Bitdiddle", "Ben"), $who)

After answering, the system goes into an infinite loop. Explain why.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.63 Cy D. Fect, looking forward to the day when he will rise in the organization, gives a query to find all the wheels (using the wheel rule of section 4.4.1):

wheel($who)

To his surprise, the system responds

Query results:
wheel(list("Warbucks", "Oliver"))
wheel(list("Bitdiddle", "Ben"))
wheel(list("Warbucks", "Oliver"))
wheel(list("Warbucks", "Oliver"))
wheel(list("Warbucks", "Oliver"))

Why is Oliver Warbucks listed four times?

Exercise 4.64 Ben has been generalizing the query system to provide statistics about the company. For example, to find the total salaries of all the computer programmers one will be able to say

sum($amount,      
    and(job($x, list("computer", "programmer")),
        salary($x, $amount)))

In general, Ben's new system allows expressions of the form accumulation_function($variable$, $query$-$pattern$) where accumulation_function can be things like sum, average, or maximum. Ben reasons that it should be a cinch to implement this. He will simply feed the query pattern to evaluate_query. This will produce a stream of frames. He will then pass this stream through a mapping function that extracts the value of the designated variable from each frame in the stream and feed the resulting stream of values to the accumulation function. Just as Ben completes the implementation and is about to try it out, Cy walks by, still puzzling over the wheel query result in exercise 4.63. When Cy shows Ben the system's response, Ben groans, Oh, no, my simple accumulation scheme won't work!

What has Ben just realized? Outline a method he can use to salvage the situation.

Exercise 4.65 Devise a way to install a loop detector in the query system so as to avoid the kinds of simple loops illustrated in the text and in exercise 4.62. The general idea is that the system should maintain some sort of history of its current chain of deductions and should not begin processing a query that it is already working on. Describe what kind of information (patterns and frames) is included in this history, and how the check should be made. (After you study the details of the query-system implementation in section 4.4.4, you may want to modify the system to include your loop detector.)

Exercise 4.66 Define rules to implement the reverse operation of exercise 2.18, which returns a list containing the same elements as a given list in reverse order. (Hint: Use append_to_form.) Can your rules answer both the query reverse(list(1, 2, 3), $x) and the query reverse($x, list(1, 2, 3))?

Exercise 4.67 Let us modify the data base and the rules of exercise 4.61 to add great to a grandson relationship. This should enable the system to deduce that Irad is the great-grandson of Adam, or that Jabal and Jubal are the great-great-great-great-great-grandsons of Adam.

Change the assertions in the data base such that there is only one kind of relationship information, namely related. The first item then describes the relationship. Thus, instead of son("Adam", "Cain"), you would write related("son", "Adam", "Cain"). Represent the fact about Irad, for example, as
```
related(list("great", "grandson"), "Adam", "Irad")
```
Write rules that determine if a list ends in the word "grandson".
Use this to express a rule that allows one to derive the relationship
```
list(pair("great", $rel), $x, $y)
```
where $rel is a list ending in "grandson".
Check your rules on the queries related(list("great", "grandson"), $g, $ggs) and related($relationship, "Adam", "Irad").

[1] That a particular method of inference is legitimate is not a trivial assertion. One must prove that if one starts with true premises, only true conclusions can be derived. The method of inference represented by rule applications is modus ponens, the familiar method of inference that says that if A is true and A implies B is true, then we may conclude that B is true.

[2] We must qualify this statement by agreeing that, in speaking of the inference accomplished by a logic program, we assume that the computation terminates. Unfortunately, even this qualified statement is false for our implementation of the query language (and also false for programs in Prolog and most other current logic programming languages) because of our use of not and javascript_predicate. As we will describe below, the not implemented in the query language is not always consistent with the not of mathematical logic, and javascript_predicate introduces additional complications. We could implement a language consistent with mathematical logic by simply removing not and javascript_predicate from the language and agreeing to write programs using only simple queries, and, and or. However, this would greatly restrict the expressive power of the language. One of the major concerns of research in logic programming was to find ways to achieve more consistency with mathematical logic without unduly sacrificing expressive power.

[3] This is not a problem of the logic but one of the procedural interpretation of the logic provided by our interpreter. We could write an interpreter that would not fall into a loop here. For example, we could enumerate all the proofs derivable from our assertions and our rules in a breadth-first rather than a depth-first order. However, such a system makes it more difficult to take advantage of the order of deductions in our programs. One attempt to build sophisticated control into such a program is described in de Kleer et al. 1977. Another technique, which does not lead to such serious control problems, is to put in special knowledge, such as detectors for particular kinds of loops (exercise 4.65). However, there can be no general scheme for reliably preventing a system from going down infinite paths in performing deductions. Imagine a diabolical rule of the form To show $P(x)$ is true, show that $P(f(x))$ is true, for some suitably chosen function $f$.

[4] Consider the query not(baseball_fan(list("Bitdiddle", "Ben"))). The system finds that baseball_fan(list("Bitdiddle", "Ben")) is not in the data base, so the empty frame does not satisfy the pattern and is not filtered out of the initial stream of frames. The result of the query is thus the empty frame, which is used to instantiate the input query to produce not(baseball_fan(list("Bitdiddle", "Ben"))).

[5] A discussion and justification of this treatment of not can be found in the article Negation as Failure by Clark (1978).

< Previous

Next >

4.4.3 Is Logic Programming Mathematical Logic?