разрешение унификации пролога

Почему это работает:

   power(_,0,1) :- !.
   power(X,Y,Z) :-
      Y1 is Y - 1,
      power(X,Y1,Z1),
      Z is X * Z1.

И это дает исключение переполнения стека?

power(_,0,1) :- !.
power(X,Y,Z) :-
  power(X,Y - 1,Z1),
  Z is X * Z1.

exponentiation resolution prolog unification
person TheOne    schedule 03.10.2009    source источник

Ответы (2)


arrow_upward
7
arrow_downward

Потому что арифметические операции над предложениями выполняются только через оператор is. В вашем первом примере Y1 привязан к результату вычисления Y - 1. В последнем система пытается доказать утверждение power(X, Y - 1, Z1), которое объединяется с power(X', Y', Z') привязка X' = X, Y' = Y - 1, Z' = Z. Затем это снова рекурсивно, поэтому Y'' = Y - 1 - 1 и т. д. до бесконечности, фактически никогда не выполняя вычисления.

Пролог - это в первую очередь просто унификация терминов - расчет в «общем» смысле должен запрашиваться явно.

person Adam Wright    schedule 03.10.2009
comment
разве Y - Y' - Y'' - Y''' ... - 1 в конце концов не равняется нулю, попадая в базовый случай и завершая рекурсию? - person TheOne; 04.10.2009
comment
Нет, в Прологе Y - 1, когда Y = 1 все еще Y - 1, пока он не связан :) - person Pierre Bourdon; 04.10.2009
comment
Действительно - это всего лишь синтаксическая форма. Инфиксная нотация — это просто нотация. Это эквивалентно -(Y, -(Y', -(Y'', Y'''))). Который будет расширяться до бесконечности, пока вы не свяжете какое-то семантическое значение с -. Вот что - делает. - person Adam Wright; 04.10.2009
comment
Глупый СОФ. Я добавил исправление, которое потерялось - это то, что делает `is' - person Adam Wright; 05.10.2009

arrow_upward
1
arrow_downward

Оба определения не работают должным образом.

Учитывать

?- pow(1, 1, 2).

который зацикливается для обоих определений, потому что второе предложение может применяться независимо от второго аргумента. Сокращение в первом предложении не может отменить это. Во втором предложении требуется цель Y > 0 перед рекурсивной целью. Использование (is)/2 по-прежнему является хорошей идеей для получения актуальных решений.

Лучше всего (для начинающих) начать с преемник -арифметика или clpfd и избегать prolog-cut.

См., например: Предикат Prolog - бесконечный цикл

person false    schedule 01.04.2013