Одна аналогия, которую я нахожу полезной при демистификации Пролога, состоит в том, что Возврат похож на Вложенные циклы , и когда все внутренние значения переменных l oop все найдены, цикл приостанавливается, переменные 'значения сообщаются, и затем цикл возобновляется.
В качестве примера, давайте запишем простую программу генерации и проверки, чтобы найти все пары натуральных чисел выше 0, которые суммируют до простого числа. Давайте предположим, что is_prime/1 нам уже дано.
Мы пишем это в Прологе как
above(0, N), between(1, N, M), Sum is M+N, is_prime(Sum).
Мы пишем это в императивном псевдокоде как
for N from 1 step 1:
for M from 1 step 1 until N:
Sum := M+N
if is_prime(Sum):
report_to_user_and_ask(Sum)
Сейчас когда вызывается report_to_user_and_ask, он печатает Sum и спрашивает пользователя, следует ли прервать или продолжить. Петли не выходят, наоборот, они просто подвешены. Таким образом, все значения переменных l oop, которые продвинули нас так далеко - и может быть больше тестов в цепочке циклов, которые иногда успешны, а иногда - неудачны - сохраняются, то есть сохраняется состояние вычислений, и вычисление готово к возобновить с этого момента, если пользователь нажимает ;.
Впервые я увидел это в реализации книги Пролога в Common Lisp в книге AI Питера Норвига. Однако он использовал отображение (Common Lisp's mapcan, который concatMap в Haskell или flatMap во многих других языках) в качестве циклической конструкции, и мне потребовались годы, чтобы увидеть, что вложенные циклы являются что это такое на самом деле.
Цели соединение выражается как вложенность петель; цели дизъюнкция выражается в виде альтернатив к l oop через.
Дальнейший поворот заключается в том, что структура вложенных циклов не фиксирована с самого начала. Это жидкость , вложенные циклы данного l oop могут быть созданы в зависимости от текущего состояния этого l oop, то есть в зависимости от текущей альтернативы, исследуемой там; циклы записываются как мы go. В (большинстве) языков, где такое динамическое создание вложенных циклов c невозможно, его можно закодировать с помощью вложенной рекурсии / вызова функции / внутри циклов. (Вот один пример , с некоторым псевдокодом.)
Если мы сохраним все такие циклы (созданные для каждой из альтернатив) в памяти даже после того, как они закончатся, мы получим Таким образом, создается дерево И-ИЛИ (упомянутое в другом ответе), пока исследуется пространство поиска и найдены решения.
(не случайно эта текучесть также является сущностью "монады" ; недетерминизм моделируется списком ; и существенным Операция списка монады - это операция flatMap, которую мы видели выше. С структурой жидкости петель это "Монада" ; с фиксированным структура это «Аппликативный функтор» ; простые циклы с без структуры (без вложенности вообще): просто «Функтор» (понятия, используемые в Haskell и т. П.). Также помогает демистифицировать их.)
Таким образом, правильный слоган может быть Возвратный путь похож на вложенные циклы, либо фиксированные, известные с самого начала, либо динамически создаваемые как мы go. Это немного дольше, хотя. :)
Вот также пример Пролога, который "как будто создает код для запуска вначале (N вложенных циклов для данного значения N), а затем запускает его. " (в SO тоже есть целый выделенный тег для него, оказывается, recursive-backtracking .)
И вот один в схеме ( "создает вложенные циклы с решением, доступным в самом внутреннем теле l oop" ), и пример C ++ ( "создает n вложенных циклов во время выполнения, фактически перечисляя двоичное кодирование 2 n , и печатая суммы из самого внутреннего l oop" ).