Проблемы с пониманием конкретного рекурсивного предиката Пролога

Question

Я нахожусь в процессе изучения Пролога.
У меня есть этот рекурсивный предикат:

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

Хорошо, опытные программисты на Прологе, вероятно, поймут, что делает этот предикат.На первый взгляд это не так сложно понять;если в качестве первого и второго аргумента указаны две цифры, он вернет результат сложения их в качестве третьего аргумента.Звучит просто?Действительно.

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

Запрашивая это:
add(succ(succ(succ(0))), succ(succ(0)), R).
Пролог создаст экземпляр и, таким образом, вернет R как succ(succ(succ(succ(succ(0))))).Хорошо.Это должно быть правильно.Однако я понятия не имею, почему это так.

Что у меня есть проблемы с пониманием, так это как и почему Пролог удаляет самый внешний функтор succ из исходного запроса,Опять же, поскольку он рекурсивный, он передает результаты в качестве аргументов самому себе и, таким образом, удаляет самый внешний функтор succ, пока цель не будет объединена.Я понимаю, как работает succ(Z) и аргумент R, но, по-видимому, я не могу понять, как он на самом деле удаляет самый внешний функтор succ, как уже упоминалось.Мне кажется, что добавляет succ вместо удаления, из-за succ(X) в определении предиката.

Любая помощь очень ценится ,Заранее спасибо!

Answer 1

Пролог видит строку add(succ(X),Y,succ(Z)) ... и думает "о, это может быть сопоставлено с запросом add(succ(succ(succ(0))), succ(succ(0)), R)., потому что я могу установить (объединить) X = succ (succ (0)), Y = succ (succ (0)), succ (Z) = R! "Важное условие для Пролога, которое определяет это , может сделать это - это то, что succ(succ(succ(0))) может быть сопоставлено с succ(X), остальное просто, потому что Y и R могут быть в этом первом наборе шаговпроизвольно (они еще не унифицированы).И succ(succ(succ(0))) можно сопоставить с succ(X) только потому, что succ (A) можно сопоставить с succ (B) в любое время, когда A можно сопоставить с B - вы видите, что компьютеру это не очень сложно решить.

Следующий шаг - Пролог просматривает оставшуюся часть строки (: - add(X,Y,Z)) и генерирует запрос add(succ(succ(0)), succ(succ(0)), Z).Помните, что succ (Z) = R, и он не изменится, пока (если) путь вычисления не будет отклонен.Следующий запрос будет add(succ(0), succ(succ(0)), Z'), где succ (Z ') = Z.Тогда add(0, succ(succ(0)), Z''), где succ (Z '') = Z '.

Тогда Пролог может использовать первое правило и определить, что Z''=Y=succ(succ(0)).Тогда больше нечего делать, поэтому просто напишите в вывод, что R=succ(Z)=succ(succ(Z'))=succ(succ(succ(Y)))=succ(succ(succ(succ(succ(0))))).