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:
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
Original
JavaScript
(assert! (married Minnie Mickey))
assert(married("Minnie", "Mickey"))
If we now ask
Original
JavaScript
(married Mickey ?who)
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
Original
JavaScript
(assert! (rule (married ?x ?y)
(married ?y ?x)))
assert(rule(married($x, $y),
married($y, $x)))
and again query
Original
JavaScript
(married Mickey ?who)
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)
successfully unifies with the query pattern
(married Mickey ?who)
to produce a frame in which
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$x
is bound to
Mickey"Mickey"
and
?y$y
is bound to
?who.$who.
So the interpreter proceeds to evaluate the rule body
(married ?y ?x)married($y, $x)
in this frame—in effect, to process the query
(married ?who Mickey).married($who, "Mickey").
One answer appears directly as an assertion in the data
base:
(married Minnie 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).married("Mickey", $who).
The system is now in an infinite loop. Indeed, whether the system
will find the simple answer
(married Minnie Mickey)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.74) 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:
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),supervisor($x, $y),
and then filters the resulting frames by removing the ones in which the
value of
?x$x
satisfies
(job ?x (computer programmer)).
job($x,list("computer", "programmer")).
The second query begins by filtering the
incoming frames to remove those that can satisfy
(job ?x (computer programmer)).
job($x, list("computer","programmer")).
Since the only incoming frame is empty, it checks the data base
to see if there are any
for
patterns that satisfy
(job ?x (computer programmer)).
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$x
in the example above), the system will produce unexpected results. Similar
problems occur with the use of
lisp-value—thejavascript_predicate—the
Lisp
predicate can't work if some of its arguments are unbound.
JavaScript
predicate can't work if some of its variables are unbound.
See exercise 4.88.
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.74
Louis Reasoner mistakenly deletes the
outranked-byoutranked_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
Just after Louis types this information into the system, DeWitt
Aull comes by to find out who outranks Ben Bitdiddle. He issues
the query
Original
JavaScript
(outranked-by (Bitdiddle Ben) ?who)
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.75
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):
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.76
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
where
accumulation-functionaccumulation_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
qeval.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.75. 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.
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.77
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.74. 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.)
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.78
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.)
append_to_form.)
Can your rules answer both
(reverse (1 2 3) ?x)the query
reverse(list(1, 2, 3), $x)
and
(reverse ?x (1 2 3))?the query reverse($x, list(1, 2, 3))?
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.
Original
JavaScript
Exercise 4.79
Beginning with the data base and the rules you formulated in
exercise 4.73, devise a rule for adding
greats 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.
(Hint: Represent the fact about Irad, for example, as
((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
((great . ?rel) ?x ?y),
where ?rel is a list ending in
grandson.) Check your rules on queries such
as ((great grandson) ?g ?ggs) and
(?relationship Adam Irad).
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.80
Let us modify the data base and the rules of
exercise 4.73 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").
This exercise is a bit more verbose than the original, because of the
choice of using explicit predicate symbols rather than general lists,
see comment in the beginning of section 4.4.1. So the hint here is
to revert to a list representation that makes the relationship
explicit, and therefore programmable. This trick is used in the
implementation of HiLog, a logic programming language with first-class
predicates, see
Chen, Weidong; Kifer, Michael; Warren, David S.
(February 1993). HiLog: A foundation for higher-order logic
programming. Journal of Logic Programming. 15 (3): 187–230.
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.
[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
lisp-value.
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
lisp-valuejavascript_predicate
introduces additional complications. We could implement a language
consistent with mathematical logic by simply removing
not and
lisp-valuejavascript_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.77). 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 (Bitdiddle Ben))).
not(baseball_fan(list("Bitdiddle", "Ben"))).
The system finds that
(baseball-fan (Bitdiddle Ben))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 (Bitdiddle Ben)))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).