4.4.1 · Rule-based queries

A rule turns one query into a sequence of smaller goals.

A finite query evaluator can scan assertions directly, then expand a rule and carry each resulting frame from one body goal into the next.

Guiding question

How does a rule preserve the middle binding needed by its next goal?

Represent facts, queries, variables, and a rule as quoted data
Return one binding frame for each matching assertion
Expand a rule head into an ordered sequence of body goals
Carry every successful frame into the following goal

The first program compares the parent predicate and fixed ada position with each assertion. Every match returns a frame containing one child binding. scan-assertions reaches the end of the finite facts list, so both matching frames remain in assertion order.

The second program binds grand from the rule head, then solve-goals processes the two parent goals in order. The first goal produces middle values ben and dia. Each frame becomes input to the second goal, which finds cy and eli. The lesson evaluator processes direct parent facts and one ordered parent-rule body while preserving every intermediate frame.

SICP code679 of 1,048,576 UTF-8 bytes

(begin
  (define facts
    '((parent ada ben)
      (parent ben cy)
      (parent ada dia)
      (parent dia eli)))
  (define query '(parent ada (var child)))
  (define (match-assertion query assertion)
    (if (and (eq? (car query) (car assertion))
             (eq? (cadr query) (cadr assertion)))
        (list (cons (cadr (caddr query)) (caddr assertion)))
        #f))
  (define (scan-assertions remaining answers)
    (if (null? remaining)
        (reverse answers)
        (let ((frame (match-assertion query (car remaining))))
          (scan-assertions (cdr remaining)
                           (if frame (cons frame answers) answers)))))
  (scan-assertions facts '()))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The assertion scan returns (((child . ben)) ((child . dia))). The rule expansion returns (cy eli).

Trace focus

In the first run, follow each assertion comparison and the two child-frame extensions. In the second run, follow the grand binding into the first goal, then confirm that the ben and dia middle frames are each passed into the second goal before child becomes cy or eli. The execution traces record the exact database scan and ordered rule-body evaluation.

Try it yourself

Change the program and compare the result.

Add (parent cy fox), then change the second query to (grandparent ben (var who)). Predict the returned answer.

Show hint

The first goal binds middle to cy, and the new fact lets the second goal bind child to fox.

Complete this lesson

0 of 23 lessons complete in this chapter0%