Почему я получаю бесконечный цикл (пролог)

Question

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

?- q(b).

и я не понимаю, почему это так. Было бы хорошо, если бы кто-то мог мне это объяснить.

p(a).    
p(b).
q(Y) :- r(X), r(Y).    
r(X) :- r(f(X)).    
r(a) :- p(c).    
r(a) :- p(a).    
r(b) :- p(b).

Answer 1

Как сказано в комментарии, цикл вызван r/1. Чтобы показать почему, просто наберите ?- trace, q(b). Посмотрите на трассировку (игнорируйте пока одноэлементное предупреждение):

 Call:q(b)
 Call:r(_4244)
 Call:r(f(_4162))
 Call:r(f(f(_4162)))
 Call:r(f(f(f(_4162))))
 Call:r(f(f(f(f(_4162)))))
 Call:r(f(f(f(f(f(_4162))))))
 Call:r(f(f(f(f(f(f(_4162)))))))
 Call:r(f(f(f(f(f(f(f(_4162))))))))

Теперь вы можете видеть, что он пытается r/1 войти в цикл. Вы также можете увидеть этот вопрос , чтобы получить более подробное объяснение.

Обратите внимание, что в прологе порядок пунктов имеет значение. Просто попробуйте поставить строку r(X) :- r(f(X)). внизу вашей программы. Теперь попробуйте ?- q(b). В первом ответе вы получите true, потому что пролог объединяет X с a и Y с b перед входом в цикл.

Answer 2

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

q(Y) :- r(X), <b>false</b>, <s>r(Y)</s>.

r(X) :- r(f(X)), <b>false</b>.
<s>r(a) :- <b>false</b>, p(c)</s>.
<s>r(a) :- <b>false</b>, p(a)</s>.
<s>r(b) :- <b>false</b>, p(b)</s>.

?- q(Y).
** LOOPS **

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

Если вы внимательно посмотрите на q/1, вы увидите одну из проблем:

q(Y) :- r(X), <b>false</b>, <s>r(Y)</s>.

Переменная Yвообще не используется в видимой части.X появляется только один раз.Таким образом, r(X) будет самым общим возможным запросом, и, следовательно, он будет иметь наихудшее возможное свойство завершения (которое действительно зависит от определения r/1).В любом случае, аргумент q/1 не влияет на завершение!

Есть еще одно свойство, на котором можно сделать вывод: порядок предложений не влияет на свойство завершения!Это легко увидеть: независимо от того, где появляются пункты, которые были полностью удалены с помощью false, их можно удалить.

Подробнее см. fault-slice .