4.4.5 · Recursive rule search

A recursive rule needs a visible search boundary.

A finite ancestor query expands parent facts through a recursive clause, and the evaluator reports whether its work budget completed the search.

Guiding question

How can recursive rule expansion terminate honestly when the data may contain a cycle?

Separate a direct parent clause from a recursive ancestor clause
Carry a visible frontier of pending subjects through the search
Spend one explicit work unit for each frontier expansion
Distinguish a complete result from a result truncated at the bound
Observe repeated answers when cyclic data is searched without duplicate removal

The first program gives ancestor two clauses in procedural form. Every child of the current person is a direct answer, and every child is also placed on a frontier so the same rule can search one generation farther. Because the facts are finite and acyclic, the frontier becomes empty before the ten-unit work budget is exhausted, and the result is marked complete.

The second program uses a three-person cycle. Expanding ada reaches ben, ben reaches cy, and cy reaches ada again. The evaluator spends exactly one work unit per removed frontier item and returns truncated with the remaining frontier when the budget reaches zero. This breadth-first lesson model covers parent expansion, an explicit frontier, repeated answers, and complete or truncated status.

SICP code1,284 of 1,048,576 UTF-8 bytes

(begin
  ; ancestor(from, to) <- parent(from, to)
  ; ancestor(from, to) <- parent(from, middle), ancestor(middle, to)
  (define facts
    '((parent ada ben)
      (parent ada eli)
      (parent ben cy)
      (parent cy dia)
      (parent eli fox)))
  (define (children-of person remaining answers)
    (if (null? remaining)
        (reverse answers)
        (let ((fact (car remaining)))
          (children-of
            person
            (cdr remaining)
            (if (and (eq? (car fact) 'parent)
                     (eq? (cadr fact) person))
                (cons (caddr fact) answers)
                answers)))))
  (define (bounded-ancestor-search start work-limit)
    (define (search frontier remaining-work answers)
      (cond ((null? frontier)
             (list 'complete answers frontier remaining-work))
            ((= remaining-work 0)
             (list 'truncated answers frontier remaining-work))
            (else
             (let* ((person (car frontier))
                    (children (children-of person facts '())))
               (search
                 (append (cdr frontier) children)
                 (- remaining-work 1)
                 (append answers children))))))
    (search (list start) work-limit '()))
  (bounded-ancestor-search 'ada 10))

(begin
  ; ancestor(from, to) <- parent(from, to)
  ; ancestor(from, to) <- parent(from, middle), ancestor(middle, to)
  (define facts
    '((parent ada ben)
      (parent ada eli)
      (parent ben cy)
      (parent cy dia)
      (parent eli fox)))
  (define (children-of person remaining answers)
    (if (null? remaining)
        (reverse answers)
        (let ((fact (car remaining)))
          (children-of
            person
            (cdr remaining)
            (if (and (eq? (car fact) 'parent)
                     (eq? (cadr fact) person))
                (cons (caddr fact) answers)
                answers)))))
  (define (bounded-ancestor-search start work-limit)
    (define (search frontier remaining-work answers)
      (cond ((null? frontier)
             (list 'complete answers frontier remaining-work))
            ((= remaining-work 0)
             (list 'truncated answers frontier remaining-work))
            (else
             (let* ((person (car frontier))
                    (children (children-of person facts '())))
               (search
                 (append (cdr frontier) children)
                 (- remaining-work 1)
                 (append answers children))))))
    (search (list start) work-limit '()))
  (bounded-ancestor-search 'ada 10))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The acyclic search returns (complete (ben eli cy fox dia) () 4). The cyclic search returns (truncated (ben cy ada ben cy) (cy) 0).

Trace focus

Follow each frontier car, the finite fact scan that produces its children, the append that queues those children, and the one-unit budget decrease. In the complete run, the frontier empties with four units left. In the cyclic run, ada reappears before the budget reaches zero and cy remains pending when the result is marked truncated.

Try it yourself

Change the program and compare the result.

Run the acyclic search with a work limit of 2. Predict the answer prefix, remaining frontier, and status before executing it.

Show hint

The first expansion queues ben and eli. The second removes ben and queues cy behind eli.

Complete this lesson

0 of 23 lessons complete in this chapter0%