Рекурсивное сложение в Прологе

База знаний

add(0,Y,Y). // clause 1
add(succ(X),Y,succ(Z)) :- add(X,Y,Z). // clause 2

Запрос

add(succ(succ(succ(0))), succ(succ(0)), R)

Трассировка

Call: (6) add(succ(succ(succ(0))), succ(succ(0)), R)
Call: (7) add(succ(succ(0)), succ(succ(0)), _G648)
Call: (8) add(succ(0), succ(succ(0)), _G650)
Call: (9) add(0, succ(succ(0)), _G652)
Exit: (9) add(0, succ(succ(0)), succ(succ(0)))
Exit: (8) add(succ(0), succ(succ(0)), succ(succ(succ(0))))
Exit: (7) add(succ(succ(0)), succ(succ(0)), succ(succ(succ(succ(0)))))
Exit: (6) add(succ(succ(succ(0))), succ(succ(0)), succ(succ(succ(succ(succ(0))))))

Мой вопрос

  • Я вижу, как рекурсивный вызов в разделе 2 удаляет внешний succ () при каждом вызове аргумента 1.
  • Я вижу, как он добавляет внешний succ () к аргументу 3 при каждом вызове.
  • Я вижу, когда 1-й аргумент в результате этих рекурсивных вызовов достигает 0. В этот момент я вижу, как 1-е предложение копирует 2-й аргумент в 3-й аргумент.

Вот где я запутался.

  1. После выполнения 1-го предложения автоматически выполняется и 2-е предложение, а затем добавляется succ () к первому аргументу?

  2. Кроме того, как программа завершается и почему она просто не продолжает бесконечно добавлять succ () к первому и третьему аргументу?

Объяснение с сайта LearnPrologNow.com (которое я не понимаю)

Давайте шаг за шагом рассмотрим, как Prolog обрабатывает этот запрос. Ниже приведено дерево трассировки и поиска по запросу.

Первый аргумент не равен 0, что означает, что можно использовать только второе предложение для add / 3. Это приводит к рекурсивному вызову add / 3. Самый внешний функтор succ удаляется из первого аргумента исходного запроса, и результат становится первым аргументом рекурсивного запроса. Второй аргумент передается рекурсивному запросу без изменений, а третий аргумент рекурсивного запроса - это переменная, внутренняя переменная _G648 в трассировке, приведенной ниже. Обратите внимание, что _G648 еще не создан. Однако он разделяет значения с R (переменная, которую мы использовали в качестве третьего аргумента в исходном запросе), потому что R был создан как succ (_G648), когда запрос был объединен с заголовком второго предложения. Но это означает, что R больше не является полностью необоснованной переменной. Теперь это сложный термин, аргументом которого является (неустановленная) переменная.

Следующие два шага по сути такие же. С каждым шагом первый аргумент становится на один слой меньше; И трассировка, и дерево поиска, приведенные ниже, хорошо это демонстрируют. В то же время succ-функтор добавляется к R на каждом шаге, но всегда оставляет самую внутреннюю переменную неустановленной. После первого рекурсивного вызова R завершается успешно (_G648). После второго рекурсивного вызова _G648 создается с помощью succ (_G650), так что R является succ (succ (_G650). После третьего рекурсивного вызова _G650 создается с помощью succ (_G652), и поэтому R становится succ (succ (succ ( _G652))). В дереве поиска показано пошаговое создание экземпляра.

На этом этапе все succ-функторы удалены с первого аргумента, и мы можем применить базовое предложение. Третий аргумент приравнивается ко второму аргументу, поэтому «дыра» (неустановленная переменная) в комплексном члене R, наконец, заполнена, и мы прошли.


recursion addition prolog successor-arithmetics
person prolog    schedule 17.03.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Давайте начнем с правильной терминологии.

Это пункты, как вы правильно указали:

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

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

  1. 0 плюс Y равно Y. Это имеет смысл.
  2. Если верно, что X плюс Y равно Z , то верно, что преемник X плюс Y является преемником Z.

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

?- add(X, Y, Z).
X = 0,
Y = Z ;
X = succ(0),
Z = succ(Y) ;
X = succ(succ(0)),
Z = succ(succ(Y)) .

В этом случае нечего «убирать», поскольку ни один из аргументов не создается. Тем не менее, Prolog по-прежнему дает очень разумные ответы, которые проясняют, для каких терминов это отношение выполняется.

В вашем случае вы рассматриваете другой запрос (не «определение предиката»!), А именно запрос:

?- add(succ(succ(succ(0))), succ(succ(0)), R).
R = succ(succ(succ(succ(succ(0))))).

Это просто частный случай более общего запроса, показанного выше, и естественное следствие вашей программы.

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

?- add(succ(succ(succ(0))), B, R).
R = succ(succ(succ(B))).

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

Если вы действительно настаиваете на процедурном чтении, сначала начните с более простого случая. Например, рассмотрим:

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

Чтобы «пройти» процедурно, мы можем действовать следующим образом:

  1. Соответствует первое предложение? (Обратите внимание, что «сопоставление» уже является ограниченным чтением: Пролог фактически применяет унификацию, и процедурное прочтение уводит нас от этой общности.)
  2. Ответ: Нет, потому что s(_) не объединяется с 0. Таким образом, применяется только второй пункт.
  3. Второе предложение содержит только если его тело, а в данном случае - если add(0, succ(0), Z). И это выполняется (с применением первого предложения) если Z равно succ(0), а R равно succ(Z).
  4. Следовательно, один ответ - R = succ(succ(0)).. Этот ответ сообщен.
  5. Есть ли другие решения? Об этом сообщается только при обратном отслеживании.
  6. Ответ: Нет, других решений нет, потому что не подходит ни один другой пункт.

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

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

Например, снова рассмотрим самый общий запрос, показанный выше: он дает ответы, но не завершается. Чтобы ответ был представлен в отчете, достаточно, чтобы была найдена подстановка ответа, которая делает запрос истинным. Так обстоит дело в вашем примере. Альтернативы, если они потенциально остаются, проверяются и сообщаются при обратном отслеживании.

Вы всегда можете попробовать следующее, чтобы проверить завершение вашего запроса: просто добавьте, например, false/0:

?- add(X, Y, Z), false.
nontermination

Это позволяет вам сосредоточиться на свойствах завершения, не заботясь о конкретных ответах.

Также обратите внимание на то, что add/3 - ужасное название для отношения: императив всегда подразумевает направление, но на самом деле это гораздо более общий, и его можно использовать также, если ни один из аргументов не является даже экземпляр! Хорошее имя предиката должно отражать эту общность.

person mat    schedule 17.03.2017
comment
Спасибо, что нашли время ответить на мой вопрос и дали лучшее объяснение, чем эта книга. - person prolog; 17.03.2017
comment
Добро пожаловать! На мой взгляд, главная привлекательность Prolog заключается в том, что нам не нужно отслеживать его таким болезненным способом для отладки наших программ. Вместо этого мы можем применять гораздо более мощные методы отладки, основанные на декларативных свойствах наших программ, и очень быстро сокращать количество ошибок в нашем коде, просто применяя логические рассуждения. Трассировка только уведет вас от истинной силы и универсальности языка, заставив читать код в определенном направлении использования. Посетите страницу моего профиля, чтобы найти ресурсы, которые, я надеюсь, помогут вам в изучении Пролога. Наслаждаться! - person mat; 17.03.2017
comment
Возможно, одна из самых больших моих проблем связана с чисто процедурным программированием. Я видел ссылки в вашем профиле, и мне интересно, почему они не занимают более высокое место в Google, чем LearnPrologNow: D - person prolog; 17.03.2017
comment
Спасибо. По большей части это совсем недавно, поэтому давайте посмотрим, как рейтинг Google будет развиваться с течением времени. - person mat; 17.03.2017