Как понять рекурсивный поиск в Прологе?

Question

Вот часть кода Пролога, определяющего цифру рекурсивным способом:

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

При получении запроса numeral(X). Пролог вернет:

X  =  0  ; 

X  =  succ(0)  ; 

X  =  succ(succ(0))  ; 

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

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

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

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

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

X  =  succ(succ(succ(succ(succ(succ(succ(succ(0)))))))) 
yes

На основании того, что у меня естьузнал, что при выполнении запроса пролог сначала создает X в переменную, подобную (_G42), а затем ищет факты и правила, чтобы найти совпадение.

В этом случае он найдет 0 (факт) как правильный матч.Затем он также попытается соответствовать правилу.Это означает, что _G42 - это не 0, а _G42 - это помощь другого числа.Таким образом, генерируется другая переменная (например, _G44), _G44 будет соответствовать 0, а также будет идти дальше, как _G42.Так как _G44 соответствует 0, то оно вернется к _G42, получив _G42 = succ(_G44) = succ(0).

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

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

Answer 1

Мое личное мнение: Особенно как новичок, у вас есть ноль шанс "понять рекурсивный поиск в Прологе".Бесчисленные новички пытаются понять Пролог таким образом, и они очень последовательно терпят неудачу.

Печально то, что это поражает самых тяжёлых работников: ты всегда думаешь, что можешь как-то понять это,но, в конце концов, вы не можете , потому что существует слишком много способов вызвать даже самые простые предикаты, с неинстанцированными и (частично) инстанцированными аргументами и даже с псевдонимами переменных.

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

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

1. 0 - это число
2. Если X - это число (что бы X не было!), , тогда succ(X) из X будет также цифрой.

Обратите внимание, что :- даже означает ←то есть, следствиесправа налево.

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

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