4.10 · Recursive rule search

A recursive rule needs a visible search boundary.

A finite ancestor query can repeatedly expand parent facts through a recursive clause, but the evaluator must report whether its explicit work budget completed the search or stopped it early.

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. It does not silently present the repeated prefix as the complete ancestor relation. This narrow breadth-first model does not implement general unification, variable renaming, duplicate removal, negation, fairness, or a complete logic-programming engine.

Lispex · SICP sourceScheme-compatible SICP syntax executed by the Lispex SICP profile.

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

Lispex learning runtimeLispex SICP profile 1.0.0

Loading Lispex SICP runtime

Lispex · SICP source1,284 / 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))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Visible execution0 / 0 trace events

This browser result is not a Lispex Vouch record or authority.wasm —

Expected observation

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 before you read the hint.

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

Show one hint

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