Изучите Prolog сейчас - проблемы с возвратом в упражнении по рекурсии

У меня проблемы с пониманием того, что происходит в этом примере
Изучите Пролог сейчас - Глава 3 - Пример 3: Преемник

numeral(0).
numeral(succ(X)) :- numeral(X).

Когда задается вопрос о числе (X), он сначала даст 0 для X, затем продолжит с succ (0), увеличивая часть succ (0) на единицу таким образом, пока не закончится место:

X = 0 ?     
X = succ(0) ? ;
X = succ(succ(0)) ? ;
X = succ(succ(succ(0))) ? ;
X = succ(succ(succ(succ(0)))) ?

Я изо всех сил пытаюсь понять, почему он увеличивает succ (0)?

Я знаю, что пролог сначала найдет факт и сопоставит его, следовательно, первый 0. Затем он вернется назад, чтобы увидеть, есть ли другие решения, и «увидит» правило. В правиле он будет использовать созданный экземпляр X в 0. Где я терплю неудачу, это чтобы понять, почему он продолжает увеличивать succ (0). Становится ли X succ (0) вместо 0?

Мои извинения за глупый мозг.


prolog successor-arithmetics
person qwerty    schedule 03.01.2017    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Я изо всех сил пытаюсь понять, почему он увеличивается succ(0)?

Если вы снова прочитаете этот раздел, в нем говорится:

Вот еще один способ записи чисел, который иногда используется в математической логике. В нем используется всего четыре символа: 0, succ, а также левая и правая круглые скобки, ( ). Этот стиль цифр определяется следующим индуктивным определением:

0 - числительное.
Если X - числительное, то succ (X) - тоже.

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

В этом примере вы должны мыслить символически, например Символьное вычисление или, что более важно, Абстрактная система перезаписи.

В этом примере они используют не арабские цифры, а функциональный способ описания чисел. Другими словами, для описания числа у вас есть только начальный символ 0 и функция succ(x). Обратите внимание: я говорю символ, а не число, потому что символ 0 имеет значение только в контексте, в данном случае natural числа

So 

 0 is 0
 1 is succ(0)        - The successor of 0 is 1.
 2 is succ(succ(0))  - The successor of the successor of 0 is 2 or
                       The successor of 1, e.g. succ(0), is 2.

и так далее. Если вы читали о лямбда-исчислении, вы часто увидите это.

Другой способ подумать об этом - ключевое слово индуктивный. При индукции вам нужен исходный факт и правило, которое приведет вас к следующему факту. Итак, 0 - это факт, а правило, которое приведет вас к следующему факту, - succ(X).

person Guy Coder    schedule 03.01.2017
comment
Ах я вижу! Отличное объяснение и спасибо за предложение книги - я думаю, что это будет большим подспорьем. Очень признателен. - person qwerty; 03.01.2017
comment
Интересно: Аксиома бесконечности - person Guy Coder; 04.01.2017

arrow_upward
5
arrow_downward

Я думаю, что Гай Кодер дал хорошее подробное объяснение того, что происходит. Я дам небольшой вариант его индуктивного объяснения, чтобы, надеюсь, внести больше ясности.

Подумайте, что говорят ваши правила Пролога:

numeral(0).

Это означает, что 0 - это число.

numeral(succ(X)) :- numeral(X).

Это говорит о том, что succ(X) является числом, если X является числом.

Итак, по первому правилу 0 - это числительное. То есть numeral(0) верно (успешно). По второму правилу, поскольку 0 является числом, тогда succ(0) должно быть числом (numeral(succ(0)) истинно). Поскольку succ(0) является числом, то согласно второму правилу снова succ(succ(0)) должно быть числом (numeral(succ(succ(0)) истинно). И так далее...

person lurker    schedule 03.01.2017
comment
Спасибо, что нашли время изучить мой вопрос, ваш ответ действительно помог мне прояснить ситуацию в моей голове! Действительно ценю это! :) - person qwerty; 03.01.2017