Structure and Interpretation of Computer Programs (86 page)

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)
  successfully
  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 appears directly as an assertion in the data
  base:
  (married Minnie Mickey)
  .
  
• 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.64
)
or on low-level details concerning the order in which the system
processes queries.
⁷⁷

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 (computer programmer))))
(and (not (job ?x (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
(computer programmer))
. The second query begins by filtering the
incoming frames to remove those that can satisfy
(job ?x
(computer programmer))
. Since the only incoming frame is empty, it
checks the data base to see if there are any patterns that satisfy
(job ?x (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
lisp-value
– the Lisp predicate can't work if some of its
arguments are unbound. See exercise 
4.77
.

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.
⁷⁸
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.
⁷⁹

Exercise 4.64.
  
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

(outranked-by (Bitdiddle Ben) ?who)

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

Exercise 4.65.
  
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 (Warbucks Oliver))
(wheel (Bitdiddle Ben))
(wheel (Warbucks Oliver))
(wheel (Warbucks Oliver))
(wheel (Warbucks Oliver))

Why is Oliver Warbucks listed four times?

Exercise 4.66.
  
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 (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
qeval
. 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.65
. 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.67.
  
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.64
. 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.68.
  
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
(reverse (1 2 3) ?x)
and
(reverse ?x (1 2 3))
?

Exercise 4.69.
  Beginning with the data base and the rules you formulated in
exercise 
4.63
, 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)
.

Section 
4.4.2
described how the query system
works. Now we fill in the details by presenting a complete
implementation of the system.

The driver loop for the query system repeatedly reads input
expressions. If the expression is a rule or assertion to be added to
the data base, then the information is added. Otherwise the
expression is assumed to be a query. The driver passes this query to
the evaluator
qeval
together with an initial frame stream
consisting of a single empty frame. The result of the evaluation is a
stream of frames generated by satisfying the query with variable
values found in the data base. These frames are used to form a new
stream consisting of copies of the original query in which the
variables are instantiated with values supplied by the stream of
frames, and this final stream is printed at the terminal:

(define input-prompt ";;; Query input:")
(define output-prompt ";;; Query results:")
(define (query-driver-loop)
  (prompt-for-input input-prompt)
  (let ((q (query-syntax-process (read))))
    (cond ((assertion-to-be-added? q)
           (add-rule-or-assertion! (add-assertion-body q))
           (newline)
           (display "Assertion added to data base.")
           (query-driver-loop))
          (else
           (newline)
           (display output-prompt)
           (display-stream
            (stream-map
             (lambda (frame)
               (instantiate q
                            frame
                            (lambda (v f)
                              (contract-question-mark v))))
             (qeval q (singleton-stream '()))))
           (query-driver-loop)))))

Here, as in the other evaluators in this chapter, we use an abstract
syntax for the expressions of the query language.
The implementation of the expression syntax, including the predicate
assertion-to-be-added?
and the selector
add-assertion-body
,
is given in section 
4.4.4.7
.
Add-rule-or-assertion!
is defined in section 
4.4.4.5
.

Before doing any processing on an input expression, the driver loop
transforms it syntactically into a form that makes the processing more
efficient. This involves changing the
representation of pattern
variables. When the query is instantiated, any variables that remain
unbound are transformed back to the input representation before being
printed. These transformations are performed by the two procedures
query-syntax-process
and
contract-question-mark
(section  
4.4.4.7
).

To instantiate an expression, we copy it, replacing any variables in
the expression by their values in a given frame. The values are
themselves instantiated, since they could contain variables (for
example, if
?x
in
exp
is bound to
?y
as the result
of unification and
?y
is in turn bound to 5). The action to
take if a variable cannot be instantiated is given by a procedural
argument to
instantiate
.

(define (instantiate exp frame unbound-var-handler)
  (define (copy exp)
    (cond ((var? exp)
           (let ((binding (binding-in-frame exp frame)))
             (if binding
                 (copy (binding-value binding))
                 (unbound-var-handler exp frame))))
          ((pair? exp)
           (cons (copy (car exp)) (copy (cdr exp))))
          (else exp)))
  (copy exp))

The procedures that manipulate bindings are defined in
section 
4.4.4.8
.

The
qeval
procedure, called by the
query-driver-loop
, is
the basic evaluator of the query system. It takes as inputs a query
and a stream of frames, and it returns a stream of extended frames.
It identifies special forms by a
data-directed dispatch using
get
and
put
, just as we did in implementing generic operations
in chapter 2. Any query that is not identified as a special form is
assumed to be a simple query, to be processed by
simple-query
.

(define (qeval query frame-stream)
  (let ((qproc (get (type query) 'qeval)))
    (if qproc
        (qproc (contents query) frame-stream)
        (simple-query query frame-stream))))

Type
and
contents
, defined in section 
4.4.4.7
,
implement the abstract syntax of the special forms.

The
simple-query
procedure handles simple queries. It takes as
arguments a simple query (a pattern) together with a stream of frames,
and it returns the stream formed by extending each frame by all
data-base matches of the query.

(define (simple-query query-pattern frame-stream)
  (stream-flatmap
   (lambda (frame)
     (stream-append-delayed
      (find-assertions query-pattern frame)
      (delay (apply-rules query-pattern frame))))
   frame-stream))