Как объяснить прогон 5 (x) g0 g1 в The Reasoned Schemer

Question

Я не понимаю, как запустить n (x) g0 g1 ... для запуска через лист

список определен так

(define listo
  (lambda (l)
    (conde
      [(nullo l) #s)]
      [(pairo l)
       (fresh (d)
         (cdro l d)
         (listo d))]
      [else #u])))

Разумный Планировщик на странице 29 в сегменте 14 говорит код

(run 5 (x)
  (listo (a b c . x)))

дает результат

(()
 (_.0)
 (_.0 _.1)
 (_.0 _.1 _.2)
 (_.0 _.1 _.2 _.3))

Не могли бы вы объяснить, как это произошло? Заранее спасибо.

Answer 1

Запрос

(run 5 (x)
  (listo `(a b c . ,x)))

(я добавил квазицитатуру и кавычку, книга использует жирный и не жирный текст)

в любом случае, как работает листо, он пытается проверить (nullo (a b c . ,x)) and this fails, so it tries to check (pairo (a b c., X)), и это успешно. Таким образом, следует, что ветвь конде и работает

(fresh (d)
     (cdro `(a b c . ,x) d)
     (listo d))

cdro производит d = `(b c., X), поэтому мы имеем

(fresh (d)
     ;(cdro `(a b c . ,x) `(b c . ,x)) ;; this disappears since it has been solved
     (listo `(b c . ,x)))

Итак, теперь весь процесс повторяется для (листо (b c . ,x)) and then (listo (с., Х)) и затем (листо х)

Это также единственно возможная ветвь, которая может быть взята, поэтому (listo `(a b c., X)) логически эквивалентен (listo x). Оба запроса будут давать одинаковые результаты.