재귀 규칙에는 보이는 탐색 경계가 필요하다.
유한한 ancestor 질의는 parent 사실을 재귀적으로 펼칠 수 있지만 명시적인 작업 예산이 탐색을 끝냈는지 중간에 멈췄는지 함께 보고해야 합니다.
데이터에 순환이 있어도 재귀 규칙 확장을 정직하게 끝내려면 무엇이 필요할까요?
- 직접 parent 절과 재귀 ancestor 절 구분하기
- 대기 중인 대상을 frontier로 명시하기
- frontier 항목 하나를 펼칠 때 작업 단위 하나 사용하기
- 완료된 결과와 한도에서 잘린 결과 구분하기
- 중복 제거 없는 순환 탐색에서 반복 답 관찰하기
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.
(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))- 출력
- —
- 값
- —
- 진단
- —
The acyclic search returns (complete (ben eli cy fox dia) () 4). The cyclic search returns (truncated (ben cy ada ben cy) (cy) 0).
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.
힌트를 보기 전에 프로그램을 바꿔 보세요.
Run the acyclic search with a work limit of 2. Predict the answer prefix, remaining frontier, and status before executing it.
힌트 하나 보기
The first expansion queues ben and eli. The second removes ben and queues cy behind eli.