Объяснение рекурсивной процедуры Пролога

Question

Я бы хотел, чтобы кто-нибудь объяснил эту процедуру, если это возможно (из книги "Изучай пролог сейчас"). Он берет две цифры и складывает их вместе.

add(0,Y,Y).  
add(s(X),Y,s(Z)) :- add(X,Y,Z).

В принципе я понимаю, но у меня есть несколько вопросов. Допустим, я выдаю запрос

?- add(s(s(0)), s(0), R).

Что приводит к:

R = s(s(s(0))).

Шаг 1 совпадает с правилом 2. Теперь X становится s(0), а Y по-прежнему s(0). Однако Z (согласно книге) становится s(_G648) или s() с неопознанной переменной внутри. Почему это?

На последнем шаге подбирается 1-е правило, которое завершает рекурсию. Здесь содержимое Y каким-то образом оказывается в неосуществленной части того, что было Z! Очень запутанно, мне нужно простое английское объяснение.

Answer 1

Первые помещения:

• У нас есть s(X) определяется как преемник X так в основном s(X) = X+1
• Нотация _G### используется в трассировке для внутренних переменных, используемых для рекурсии

Давайте сначала посмотрим на другое определение дополнения с преемниками, которое я считаю более интуитивным:

add(0,Y,Y).
add(s(A),B,C) :- add(A,s(B),C).

это в основном то же самое, но рекурсию легче увидеть:

мы просим

add(s(s(0)),s(0),R).

Теперь на первом этапе пролог говорит, что эквивалентно

add(s(0),s(s(0)),R)

потому что у нас есть add(s(A),B,C) :- add(A,s(B),C) и если мы посмотрим на вопрос A = s (0) и B = s (0). Но это все еще не заканчивается, поэтому мы должны повторно применить эту эквивалентность с A = 0 и B = s (s (0)), чтобы она стала

add(0,s(s(s(0))),R)

который, учитывая add(0,Y,Y). это означает, что

R = s(s(s(0)))

---

Ваше определение add в основном делает то же самое, но с двумя рекурсиями:

Сначала он запускает первый аргумент до 0, поэтому сводится к добавлению (0,Y,Y):

add(s(s(0)),s(0),R)

с X=s(0), Y = s(0) и s(Z) = R и Z = _G001

add(s(0),s(0),_G001)

с X = 0, Y=s(0) и s(s(Z)) = s(G_001) = R и Z = _G002

add(0,s(0),_G002)

Итак, теперь он знает, что _G002 - это s (0) из определения add(0,Y,Y), но должен проследить его шаги назад, чтобы _G001 было s(_G002), а R - s(_G001) - s(s(_G002)) это s(s(s(0))).

Таким образом, суть в том, чтобы добраться до определения add(0,Y,Y). Пролог должен ввести внутренние переменные для первой рекурсии, из которой R затем оценивается во второй.

Answer 2

Если вы хотите понять смысл программы Prolog, вы можете сначала сосредоточиться на том, что описывает отношение. Тогда вы можете захотеть понять его свойства завершения.

Если вы углубитесь в детали конкретного исполнения, как подсказывает ваш вопрос, вы скоро потеряетесь во множестве деталей. В конце концов, Prolog имеет два различных чередующихся потока управления (AND- и OR-control), и в дополнение к этому он имеет объединение, которое включает передачу параметров, назначение, сравнение и решение уравнений.

Вкратце: хотя компьютеры выполняют конкретный запрос без усилий за миллионы умозаключений, вы устали после их скрининга. Вы не можете победить компьютеры в этом. К счастью, есть лучшие способы понять программу.

Что касается значения, сначала посмотрите на правило. Это читает:

add(s(X),Y,s(Z)) :- add(X,Y,Z).

Увидеть :- между? Он предназначен для обозначения стрелки. Немного необычно, что стрелка указывает справа налево. В неофициальном письме вы бы написали это скорее слева направо. Прочитайте это следующим образом:

Предоставлена, add(X,Y,Z) верно, то и add(s(X),Y,s(Z)) правда.

Итак, мы предполагаем, что у нас уже есть некоторые add(X,Y,Z) что означает "X+Y=Z". И учитывая это, мы можем заключить, что также "(X+1)+Y=(Z+1)".

После этого вам может быть интересно понять его свойства завершения. Позвольте мне сделать это очень кратко: чтобы понять это, достаточно взглянуть на правило: 2-й аргумент будет рассмотрен только далее. Следовательно: Второй аргумент не влияет на завершение. И первый, и третий аргументы выглядят одинаково. Следовательно: они оба влияют на завершение одинаково! Фактически, добавление /3 завершается, если 1-й или 3-й аргумент не объединится с s(_),

Узнайте больше об этом в других ответах, помеченных как срез-срез, например:

Запись преемника Пролога дает неполный результат и бесконечный цикл

---

Но теперь, чтобы ответить на ваш вопрос add(s(s(0)), s(0), R). Я только смотрю на первый аргумент: да! Это прекратится. Вот и все.

Answer 3

Давайте разделим проблему на три части: вопросы, касающиеся создания переменных и схемы накопителя, которую я использую в варианте этого примера:

add(0,Y,Y).                    
add(s(X),Y,Z):-add(X,s(Y),Z).

и комментарий о вашем примере, который использует композицию замен.

Пролог применяется для того, чтобы увидеть, какое правило (то есть предложение Хорна) соответствует (чья голова объединяется) - это алгоритм объединения, который, в частности, говорит, что если у меня есть переменная, скажем, X и funtor, то есть f(Y) эти два термина унифицируют (есть небольшая часть о проверке происходящего, чтобы... проверять, но не обращать внимания на атм), следовательно, существует подстановка, которая может позволить вам преобразовать одно в другое.

Когда вызывается ваше второе правило, действительно R объединяется с s(Z). Не пугайтесь внутреннего представления, которое Пролог дает новым, необоснованным переменным, это просто имя переменной (так как оно начинается с "_"), которое обозначает код (Пролог должен иметь способ выражения постоянно создаваемых переменных и так _G648, _G649, _G650 и т. д.). Когда вы вызываете процедуру Prolog, передаваемые вами параметры, которые являются необоснованными (в данном случае R), используются для хранения результата процедуры по завершении ее выполнения, и он будет содержать результат, так как в какой-то момент во время вызова процедуры ее будет создан для чего-то (всегда через объединение). Если в какой-то момент у вас есть что var, то есть K istantiated для s(H) (или s(_G567), если вы предпочитаете), он все еще частично создается и для получения полного вывода вам нужно рекурсивно создать экземпляр H. Чтобы увидеть для чего он будет создан, ознакомьтесь с параграфом шаблона аккумулятора и последующим способом решения проблемы.

Паттерн аккумулятора взят из функционального программирования и, вкратце, является способом получить переменную, аккумулятор (в моем случае сам Y), который должен нести частичные вычисления между некоторыми вызовами процедур. Шаблон опирается на рекурсию и имеет примерно такую ​​форму:

• Базовый шаг рекурсии (мое первое правило, т. Е.) Всегда говорит, что, поскольку вы достигли конца вычисления, вы можете скопировать частичный результат (теперь итоговый) из вашей аккумуляторной переменной в вашу выходную переменную (это шаг, на котором, через унификацию ваш выходной var создается!)
• В рекурсивном шаге рассказывается, как создать частичный результат и как сохранить его в переменной-аккумуляторе (в моем случае я "увеличиваю" Y). Обратите внимание, что на рекурсивном шаге выходная переменная никогда не изменяется.

Наконец, что касается вашего примера, он следует другому шаблону, составу замен, который, я думаю, вы можете лучше понять, подумав об аккумуляторе и создании экземпляра посредством объединения.

• Его базовый шаг совпадает с шаблоном аккумулятора, но Y никогда не изменяется на рекурсивном шаге, в то время как Z
• Он использует для объединения переменной в Z с Y путем частичного создания всех вычислений в конце каждого рекурсивного вызова после того, как вы достигли базового шага и каждый вызов процедуры заканчивается. Таким образом, в конце первого вызова внутренняя свободная переменная в Z много раз заменялась объединением значением в Y. Обратите внимание на приведенный ниже код, после того, как вы достигли нижнего вызова, стек вызовов процедур начинает всплывать, и ваша частичная vars (S1, S2, S3 для простоты) объединяются, пока R не будет полностью создан

Вот трассировка стека:

add(s(s(s(0))),s(0),S1).          ^ S1=s(S2)=s(s(s(s(0))))
add(  s(s(0)) ,s(0),S2).          | S2=s(S3)=s(s(s(0)))
add(    s(0)  ,s(0),S3).          | S3=s(S4)=s(s(0))
add(      0   ,s(0),S4).          | S4=s(0)
add(      0   ,s(0),s(0)).  ______|