Structure and Interpretation of Computer Programs (85 page)

(and (supervisor ?x ?y)
     (not (job ?x (computer programmer))))

the first clause will generate frames with bindings for
?x
and
?y
. The
not
clause will then filter
these by removing all frames in which the binding for
?x
satisfies the restriction that
?x
is a computer
programmer.
⁷⁰

The
lisp-value
special form is implemented as a similar filter
on frame streams. We use each frame in the stream to instantiate any
variables in the pattern, then apply the Lisp predicate. We remove
from the input stream all frames for which the predicate fails.

In order to handle rules in the query language, we must be able to
find the rules whose conclusions match a given query pattern. Rule
conclusions are like assertions except that they can contain
variables, so we will need a generalization of pattern
matching – called
unification
– in which both the “pattern”
and the “datum” may contain variables.

A unifier takes two patterns, each containing constants and variables,
and determines whether it is possible to assign values to the
variables that will make the two patterns equal. If so, it returns a
frame containing these bindings. For example, unifying
(?x a
?y)
and
(?y ?z a)
will specify a frame in which
?x
,
?y
, and
?z
must all be bound to
a
. On the other
hand, unifying
(?x ?y a)
and
(?x b ?y)
will fail, because
there is no value for
?y
that can make the two patterns equal.
(For the second elements of the patterns to be equal,
?y
would
have to be
b
; however, for the third elements to be equal,
?y
would have to be
a
.) The unifier used in the query system,
like the pattern matcher, takes a frame as input and performs
unifications that are consistent with this frame.

The unification algorithm is the most technically difficult part of
the query system. With complex patterns, performing unification may
seem to require deduction. To unify
(?x ?x)
and
((a ?y c)
(a b ?z))
, for example, the algorithm must infer that
?x
should
be
(a b c)
,
?y
should be
b
, and
?z
should
be
c
. We may think of this process as solving a set of
equations among the pattern components. In general, these are
simultaneous equations, which may require substantial manipulation to
solve.
⁷¹
For example, unifying
(?x
?x)
and
((a ?y c) (a b ?z))
may be thought of as specifying the
simultaneous equations

?x  =  (a ?y c)
?x  =  (a b ?z)

These equations imply that

(a ?y c)  =  (a b ?z)

which in turn implies that

a  =  a, ?y  =  b, c  =  ?z,

and hence that

?x  =  (a b c)

In a successful pattern match, all pattern variables become bound, and
the values to which they are bound contain only constants. This is
also true of all the examples of unification we have seen so far. In
general, however, a successful unification may not completely
determine the variable values; some variables may remain unbound and
others may be bound to values that contain variables.

Consider the unification of
(?x a)
and
((b ?y) ?z)
. We
can deduce that
?x = (b ?y)
and
a = ?z
, but we cannot
further solve for
?x
or 
?y
. The unification doesn't fail,
since it is certainly possible to make the two patterns equal by
assigning values to
?x
and
?y
. Since this match in no way
restricts the values
?y
can take on, no binding for
?y
is
put into the result frame. The match does, however, restrict the
value of 
?x
. Whatever value
?y
has,
?x
must be
(b ?y)
. A binding of
?x
to the pattern
(b ?y)
is thus
put into the frame. If a value for
?y
is later determined and
added to the frame (by a pattern match or unification that is required
to be consistent with this frame), the previously bound
?x
will
refer to this value.
⁷²

Unification is the key to the component of the query system that makes
inferences from rules. To see how this is accomplished, consider
processing a query that involves applying a rule, such as

(lives-near ?x (Hacker Alyssa P))

To process this query, we first use the ordinary pattern-match
procedure described above to see if there are any assertions in the
data base that match this pattern. (There will not be any in this
case, since our data base includes no direct assertions about who
lives near whom.) The next step is to attempt to unify the query
pattern with the conclusion of each rule. We find that the pattern
unifies with the conclusion of the rule

(rule (lives-near ?person-1 ?person-2)
      (and (address ?person-1 (?town . ?rest-1))
           (address ?person-2 (?town . ?rest-2))
           (not (same ?person-1 ?person-2))))

resulting in a frame specifying that
?person-2
is bound
to
(Hacker Alyssa P)
and that
?x
should be bound to (have
the same value as)
?person-1
. Now, relative to this frame, we
evaluate the compound query given by the body of the rule. Successful
matches will extend this frame by providing a binding for
?person-1
, and consequently a value for
?x
, which we can use to
instantiate the original query pattern.

In general, the query evaluator uses the following method to apply a
rule when trying to establish a query pattern in a frame that
specifies bindings for some of the pattern variables:

• Unify the query with the conclusion of the rule to form, if
  successful, an extension of the original frame.
  
• Relative to the extended frame, evaluate the query formed by
  the body of the rule.
  

Notice how similar this is to the method for applying a procedure in
the
eval
/
apply
evaluator for Lisp:

• Bind the procedure's parameters to its arguments to form a
  frame that extends the original procedure environment.
  
• Relative to the extended environment, evaluate the expression
  formed by the body of the procedure.
  

The similarity between the two evaluators should come as no surprise.
Just as procedure definitions are the means of abstraction in Lisp,
rule definitions are the means of abstraction in the query language.
In each case, we unwind the abstraction by creating appropriate
bindings and evaluating the rule or procedure body relative to these.

We saw earlier in this section how to evaluate simple queries in the
absence of rules. Now that we have seen how to apply rules, we can
describe how to evaluate simple queries by using both rules and
assertions.

Given the query pattern and a stream of frames, we produce, for each
frame in the input stream, two streams:

• a stream of extended frames obtained by matching the pattern
  against all assertions in the data base (using the pattern matcher),
  and
  
• a stream of extended frames obtained by applying all
  possible rules (using the unifier).
  ⁷³
  

Appending these two streams produces a stream that consists of all the
ways that the given pattern can be satisfied consistent with the
original frame. These streams (one for each frame in the input
stream) are now all combined to form one large stream, which therefore
consists of all the ways that any of the frames in the original input
stream can be extended to produce a match with the given pattern.

Despite the complexity of the underlying matching operations, the
system is organized much like an evaluator for any language. The
procedure that coordinates the matching operations is called
qeval
, and it plays a role analogous to that of the
eval
procedure for Lisp.
Qeval
takes as inputs a query and a stream
of frames. Its output is a stream of frames, corresponding to
successful matches to the query pattern, that extend some frame in the
input stream, as indicated in figure 
4.4
. Like
eval
,
qeval
classifies the different types of expressions
(queries) and dispatches to an appropriate procedure for each. There
is a procedure for each special form (
and
,
or
,
not
,
and
lisp-value
) and one for simple queries.

The driver loop, which is analogous to the
driver-loop
procedure
for the other evaluators in this chapter, reads queries from the
terminal. For each query, it calls
qeval
with the query and a
stream that consists of a single empty frame. This will produce the
stream of all possible matches (all possible extensions to the empty
frame). For each frame in the resulting stream, it instantiates the
original query using the values of the variables found in the frame.
This stream of instantiated queries is then printed.
⁷⁴

The driver also checks for the special command
assert!
, which
signals that the input is not a query but rather an assertion or rule
to be added to the data base. For instance,

(assert! (job (Bitdiddle Ben) (computer wizard)))
(assert! (rule (wheel ?person)
               (and (supervisor ?middle-manager ?person)
                    (supervisor ?x ?middle-manager))))

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.
⁷⁵
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 (computer programmer))
     (supervisor ?x ?y))

or

(and (supervisor ?x ?y)
     (job ?x (computer programmer)))

If a company has many more supervisors than programmers (the usual
case), 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.
⁷⁶

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)))