Пролог двоичного сложения - PullRequest
Новая
       28

Пролог двоичного сложения

2 голосов
/ 25 января 2020

Мне нужно реализовать двоичное сложение в прологе, где двоичные числа представлены следующим образом: 

0:  bot
1 : o(bot)
2 -> 10:  z(o(bot))
3 -> 11:  o(o(bot))
10 -> 1010:  z(o(z(o(bot))))

Я написал это: 

add(X,bot,X):-!.
add(bot,X,X):-!.

add(z(X),z(Y),Res):- add(X,Y,D), Res = z(D).
add(z(X),o(Y),Res):- add(X,Y,D), Res = o(D).
add(o(X),z(Y),Res):- add(X,Y,D), Res = o(D).
add(o(X),o(Y),Res):-addc(X,Y,D), Res = z(D).

addc(X,bot,Res):-add(X,o(bot),Res),!.
addc(bot,X,Res):-add(X,o(bot),Res),!.
addc(z(X),z(Y),Res):- add(X,Y,D),Res = o(D).
addc(z(X),o(Y),Res):-addc(X,Y,D),Res = z(D).
addc(o(X),z(Y),Res):-addc(X,Y,D),Res = z(D).
addc(o(X),o(Y),Res):-addc(X,Y,D),Res = o(D).

Это работает, когда первые 2 Аргументы являются конкретными: 

?-add(o(o(bot)),z(o(o(bot))),D).
D = o(z(z(o(bot))))

Когда один из первых 2 аргументов является переменной, он переходит в бесконечную рекурсию: 

?-add(o(o(bot)),X,z(o(o(bot)))).
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.1Gb, global: 34.9Mb, trail: 11.6Mb
  Stack depth: 1,524,958, last-call: 50%, Choice points: 762,476
  Possible non-terminating recursion:
    [1,524,958] add(bot, <compound s/1>, _1496)
    [1,524,957] add(bot, <compound s/1>, <compound z/1>)

Как я могу сделать эту работу для любого не -конкретный аргумент?

1 Ответ

2 голосов
/ 25 января 2020

(Использование bot для того, что в противном случае считается zero, null или 0, немного странно. Решетки здесь не являются нашей главной задачей.)

Во-первых, мы пытаемся понять, почему программа не заканчивается. Это может быть довольно сложно, особенно в присутствии !, который является одним из нечистых элементов Пролога. Они нужны в определенной степени, но здесь, в данном случае, они вредны только потому, что мешают нашим рассуждениям. Таким образом, вместо первых двух разделенных предложений напишите 1 

add(bot, X, X).
add(X, bot, X) :- dif(X, bot).

и аналогично для следующих двух сокращений. Обратите внимание, что эти два предложения теперь не пересекаются. После этого у нас есть чисто монотонная программа c, и поэтому мы можем применять различные методы рассуждения. В этом случае - это как раз то, что нам нужно. Чтобы лучше понять причину отсутствия завершения, я добавлю в программу цели false, поскольку есть замечательное свойство, которое мы можем использовать: если новая программа не завершает свою работу, то также и старая не прекратит Таким образом, мы можем сузить проблему до меньшей части исходной программы. После нескольких попыток я придумал следующий срез ошибки: 

<s>add(bot,X,X) :- <b>false</b>.</s>
<s>add(X,bot,X) :- <b>false</b>, dif(X,bot).</s>
<s>add(z(X),z(Y),Res) :- <b>false</b>, add(X,Y,D), Res = z(D).</s>
<s>add(z(X),o(Y),Res) :- <b>false</b>, add(X,Y,D), Res = o(D).</s>
<s>add(o(X),z(Y),Res) :- <b>false</b>, add(X,Y,D), Res = o(D).</s>
add(o(X),o(Y),Res) :- addc(X,Y,D), <b>false</b>, <s>Res = z(D)</s>.

addc(bot,X,Res) :- add(X,o(bot),Res), <b>false</b>.
addc(X,bot,Res) :- dif(X, bot), add(X,o(bot),Res), <b>false</b>.
<s>addc(z(X),z(Y),Res) :- <b>false</b>, add(X,Y,D), Res = o(D).</s>
<s>addc(z(X),o(Y),Res) :- <b>false</b>, addc(X,Y,D), Res = z(D).</s>
<s>addc(o(X),z(Y),Res) :- <b>false</b>, addc(X,Y,D), Res = z(D).</s>
addc(o(X),o(Y),Res) :- addc(X,Y,D), <b>false</b>, <s>Res = o(D).</s>

?- add(o(o(bot)),X,z(o(o(bot)))).

Из ~ 2 ^ 23 возможных сбоев среза это кажется минимальным. То есть дальнейшие действия false приводят к завершению программы.

Давайте посмотрим на это: Everywhere Res либо игнорируется, либо просто передается дальше. Следовательно, третий аргумент никак не влияет на завершение. Но вы можете поместить все эти Res = уравнения сразу после :-. Это самое раннее возможное место. 

add(bot,X,X).
add(X,bot,X):- dif(X,bot).
add(z(X),z(Y), z(D)) :- add(X,Y,D).
add(z(X),o(Y), o(D)) :- add(X,Y,D).
add(o(X),z(Y), o(D)) :- add(X,Y,D).
add(o(X),o(Y), z(D)) :- addc(X,Y,D).

addc(bot,X,Res):- add(X,o(bot),Res).
addc(X,bot,Res):- dif(X, bot), add(X,o(bot),Res).
addc(z(X),z(Y),o(D)):- add(X,Y,D).
addc(z(X),o(Y),z(D)):- addc(X,Y,D).
addc(o(X),z(Y),z(D)):- addc(X,Y,D).
addc(o(X),o(Y),o(D)):- addc(X,Y,D).

Также cTI дает благоприятные условия завершения: 

% NTI summary:  Complete result is optimal.
add(A,B,C)terminates_if b(A),b(B);b(C).
    % optimal. loops found: [add(z(_),z(_),z(_)),add(o(bot),o(o(_)),z(z(_))),add(o(o(_)),o(bot),z(z(_)))]. NTI took    8ms,72i,30i
addc(A,B,C)terminates_if b(A),b(B);b(C).
    % optimal. loops found: [addc(z(z(_)),z(z(_)),o(z(_))),addc(bot,o(_),z(_)),addc(o(_),bot,z(_))]. NTI took    4ms,96i,96i

Так что add/3 завершается, если первые два или последний аргумент дан. Так что вам не нужен первый аргумент. Вместо этого даже более общий запрос завершается: 

?- add(X,Y,z(o(o(bot)))).
     X = bot, Y = z(o(o(bot)))
   ; X = z(o(o(bot))), Y = bot
   ; X = z(bot), Y = z(o(o(bot)))
   ; X = z(o(o(bot))), Y = z(bot)
   ; X = z(z(bot)), Y = z(o(o(bot)))
   ; X = z(z(o(bot))), Y = z(o(bot))
   ; X = z(z(z(bot))), Y = z(o(o(bot)))
   ; X = z(z(o(bot))), Y = z(o(z(bot)))
   ; X = z(o(bot)), Y = z(z(o(bot)))
   ; X = z(o(o(bot))), Y = z(z(bot))
   ; X = z(o(z(bot))), Y = z(z(o(bot)))
   ; X = z(o(o(bot))), Y = z(z(z(bot)))
   ; X = o(bot), Y = o(z(o(bot)))
   ; X = o(z(o(bot))), Y = o(bot)
   ; X = o(z(bot)), Y = o(z(o(bot)))
   ; X = o(z(o(bot))), Y = o(z(bot))
   ; X = o(z(z(bot))), Y = o(z(o(bot)))
   ; X = o(z(o(bot))), Y = o(z(z(bot)))
   ; X = Y, Y = o(o(bot))
   ; X = o(o(bot)), Y = o(o(z(bot)))
   ; X = o(o(z(bot))), Y = o(o(bot))
   ; X = Y, Y = o(o(z(bot)))
   ; false.

1 И даже лучше, используйте if_/3 библиотеки reif для SICStus и SWI чтобы эти пункты были как можно более детерминированными. 

add(A, B, C) :- if_(A = bot, B = C, ( B = bot, A = C ) ).
...