Предикат Пролог - бесконечный цикл - PullRequest
Новая
       47

Предикат Пролог - бесконечный цикл

5 голосов
/ 16 марта 2012

Мне нужно создать предикат Пролога для степени 2 с натуральными числами. Натуральные числа: 0, s (0), s (s (0)) и т. Д.

Например: 

?- pow2(s(0),P).
P = s(s(0));
false.
?- pow2(P,s(s(0))).
P = s(0);
false.

Это мой код: 

times2(X,Y) :-
  add(X,X,Y).

pow2(0,s(0)).
pow2(s(N),Y) :-
  pow2(N,Z),
  times2(Z,Y).

И он отлично работает с первым примером, но во втором бесконечном цикле ..
Как я могу это исправить?

Ответы [ 2 ]

8 голосов
/ 16 марта 2012

Вот версия, которая заканчивается для первого или второго связываемого аргумента: 

pow2(E,X) :-
  pow2(E,X,X).

pow2(0,s(0),s(_)).
pow2(s(N),Y,s(B)) :-
   pow2(N,Z,B),
   add(Z,Z,Y).

Вы можете определить условия его завершения с помощью cTI.

Итак,как я придумал это решение?Идея состояла в том, чтобы найти способ, как второй аргумент может определить размер первого аргумента.Основная идея заключается в том, что для всех i ∈ N : 2 i > i .

Поэтому я добавил еще один аргумент, чтобы выразить это отношение.Может быть, вы можете усилить это немного дальше?

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

?- pow2(P,s(s(0))), <b>false</b>.

<s>pow2(0,s(0)) :- <b>false</b></s>.
pow2(s(N),Y) :-
  pow2(N,Z), <b>false</b>,
  <s>times2(Z,Y)</s>.

Именно этот крошечный фрагмент является источником для прекращения!Посмотрите на Z, которая является новой новой переменной!Чтобы решить проблему, этот фрагмент должен быть изменен каким-то образом .

И вот причина, по которой решение @ Keeper не прекращается для pow2(s(0),s(N)). 

?- pow2(s(0),s(N)), <b>false</b>.

<s>add(0,Z,Z) :- <b>false</b></s>.
add(s(X),Y,s(Z)) :-
  add(X,Y,Z), <b>false</b>.

times2(X,Y) :-
  add(X,X,Y), <b>false</b>.

<s>pow2(0,s(0)) :- <b>false</b></s>.
<s>pow2(s(N),Y) :- <b>false</b></s>,
  <s>var(Y)</s>,
  <s>pow2(N,Z)</s>,
  <s>times2(Z,Y)</s>.
pow2(s(N),Y) :-
  nonvar(Y),
  times2(Z,Y), <b>false</b>,
  <s>pow2(N,Z)</s>.
4 голосов
/ 16 марта 2012

Это происходит из-за порядка вычисления pow2. Если вы переключите порядок pow2, у вас будет первый пример, застрявший в бесконечном цикле .. Таким образом, вы можете сначала проверить, является ли Y var или nonvar.

Вот так: 

times2(X,Y) :-
  add(X,X,Y).

pow2(0,s(0)).
pow2(s(N),Y) :-
  var(Y),
  pow2(N,Z),
  times2(Z,Y).
pow2(s(N),Y) :-
  nonvar(Y),
  times2(Z,Y),
  pow2(N,Z).
...