Непонимание Разумного Схемера Глава 5 кадр 62

Question

В настоящее время я изучаю miniKanren, изучая Разумный Схемер.

И я застрял в упражнении в главе 5 кадра 62: (run* (x) (flatten_o (a) x))почему в выводе три списка?

Заранее большое спасибо.

Answer 1

Хороший вопрос! Откуда эти дополнительные списки?

Проблема в else пункт определения flatteno, else пункт обрабатывает случай, в котором s это символ (символ a, Вот). Тем не менее, пункт также позволяет s быть пустым списком или парой! Вот почему мы видим три списка вместо одного - два дополнительных списка создаются рекурсивными вызовами, которые успешно выполняются из-за else предложение, принимающее не символьные значения для s,

В более поздних версиях miniKanren мы добавили специальные ограничения, такие как symbolo а также =/= предотвратить такое поведение. Например, вот такой же запрос, и flattenoнаписано в быстрее-miniKanren ( https://github.com/webyrd/faster-miniKanren):

(define flatteno
  (lambda (s out)
    (conde
      ((== '() s) (== '() out))
      ((fresh (a d res-a res-d)
         (== (cons a d) s)
         (flatteno a res-a)
         (flatteno d res-d)
         (appendo res-a res-d out)))
      ((symbolo s) (== (cons s '()) out)))))

(run* (x)
  (flatteno '(a) x))
=>
((a))

Обратите внимание на использование symbolo ограничение в flatteno для обеспечения s это символ

Вы можете найти объяснение этих ограничений не в "Маленькой книге" в этой статье:

http://webyrd.net/quines/quines.pdf

Мы пытаемся выяснить, как включить описание этих ограничений в формат Little Book. Реализация ограничений немного сложна, что затрудняет вписывание в Маленькую Книгу!

Надеюсь это поможет!

Ура,

--Будет