Почему эта команда вызывает переполнение стека в прологе?

Question

У меня есть следующий фрагмент кода пролога:

num(0).
num(X) :- num(X1), X is X1 + 1.

fact(0,1) :-!.
fact(X,Y) :- X1 is X-1, fact(X1,Y1), !, Y is Y1 * X.

fact(X) :- num(Y), fact(Y,X).

Может кто-нибудь объяснить, почему следующая команда вызывает переполнение стека? Заранее спасибо.

fact(6).

Answer 1

Причина, по которой fact(6) не завершается, может быть найдена в следующем fault-slice :

?- fact(6).

<s>num(0) :- <b>false</b></s>.
num(X) :-
   num(X1), <b>false</b>,
   <s>X is X1 + 1</s>.

fact(X) :-
   num(Y), <b>false</b>,
   <s>fact(Y,X)</s>.

Поскольку этот фрагмент не заканчивается,также ваша оригинальная программа не заканчивается.Обратите внимание, что отсутствие завершения не зависит от определения fact/2!В лучшем случае ваша программа может быть успешной, но она никогда (конечно) не завершится неудачей.

Рассмотрите возможность использования другого определения fact/2, которое заканчивается также для fact(N, 6).

Answer 2

Сначала посмотрим на правила

  num(0).
  num(X) :- num(X1), X is X1 + 1.

предикат num(Y) будет немедленно действителен для Y = 0.

Таким образом, правило

  fact(X) :- num(Y), fact(Y,X).

можно упростить до

  fact(X) :- fact(0,X).

, который найдет совпадение для fact(0,1). Для X = 6 вместо этого происходит следующее: поскольку ни одно из правил не определяет предикат для fact(0,6), поиск начинается с fact(-1,V1), затем с fact(-2,V2) и т. Д. ... пока не будет найдено совпадение для fact(-value, Var), где локальным результатом будет найденная переменная.

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