Пролог: на каких условиях t завершает оценку цели p (t), а что нет?

Question

Рассмотрим следующую логическую программу:

p(b) :- p(b). 
p(X) :- r(b). 
p(a) :- p(a). 
r(Y). 

Для того, что условия т делает оценку цели р (т) обрываются, который делает это не?

Answer 1

Что вы хотите, так это определить все запросы, которые не прекращаются. И я предполагаю, что вы имеете в виду прекращение повсеместно. То есть мы не только смотрим на первый ответ, но и смотрим на все из них.

Существует очень быстрый ответ на этот вопрос, если ваша программа чиста, монотонна: просто возьмите самый общий запрос. То есть, если есть какая-либо возможность для любого термина T, чтобы сделать p(T) не завершающим, то p(X) также не будет прекращаться.

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

 
p(b) :- false, p(b). 
p(X) :- false, r(b). 
p(a) :- p(a), false. 

r(Y) :- false. 

Это один минимальный отказ. То есть p(a) не закончится. Остерегайтесь, однако, что просто запрашивая p(a) (в исходной программе) будет успешным, вы должны настаивать на том, чтобы смотреть на дальнейших ответов:

 
?- p(a). 
true ;  % there is one answer 
** LOOP ** % loops "on backtracking" 

Чтобы сэкономить труд, чтобы просить дальнейших ответов, просто используйте p(a), false вместо ,

Существует еще один минимальный провал срезами:

 
p(b) :- p(b), false. 
p(X) :- false, r(b). 
p(a) :- false, p(a). 

r(Y) :- false. 

failure-slice См больше примеров.