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.
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. This deliberately narrow evaluator supports parent goals in one finite rule body. It does not implement variable renaming, negation, recursive rules, duplicate removal, or general unification.
(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 '()))- Output
- —
- Value
- —
- Diagnostic
- —
The assertion scan returns (((child . ben)) ((child . dia))). The rule expansion returns (cy eli).
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. These bounded traces cover only this finite database and narrow rule evaluator.
Change the program before you read the hint.
Add (parent cy fox), then change the second query to (grandparent ben (var who)). Predict the returned answer.
Show one hint
The first goal binds middle to cy, and the new fact lets the second goal bind child to fox.