# LaVOZs

The World’s Largest Online Community for Developers

'; recursion - Prolog binary addition - LavOzs.Com

I need to implement binary addition in prolog, where binary numbers are represented as follows:

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

I've written this:

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

``````

It works when the first 2 arguments are concrete:

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

When one of the first 2 arguments is a variable, it goes into an infinite recursion:

``````?-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,957] add(bot, <compound s/1>, <compound z/1>)
``````

How can i make this work for any one non-concrete argument?

(Using `bot` for what is otherwise considered `zero`, `null` or `0` is a bit odd. Lattices are not our major concern here.)

First, we try to understand why the program does not terminate. This can be quite tricky, in particular in presence of the `!` which is one of Prolog's impure elements. They are needed to a certain degree, but here in this case, they are harmful only, as they are hindering our reasoning. So instead of the first two cutful clauses, write1

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

and similarly for the next two cuts. Note that those two clauses are now disjoint. After this we have a pure monotonic program and thus we can apply various reasoning techniques. In this case, a is just what we need. To better understand the reason for non-termination, I will add goals `false` into the program, for there is a nice property we can exploit: If the new program does not terminate, then also the old one will not terminate. In this manner we can narrow down the problem to a smaller part of the original program. After a couple of tries, I came up with the following failure-slice:

```add(bot,X,X) :- false.

```

Out of the ~2^23 possible failure slices, this appears to be a minimal one. That is, any further `false` makes the program terminate.

Let's look at it: Everywhere `Res` is either ignored or just passed further on. Therefore the third argument has no influence on termination whatsoever. But you can put all those `Res =` equations just after the `:-`. That's the earliest possible place.

``````add(bot,X,X).

``````

Also cTI gives favorable termination conditions:

``````% NTI summary:  Complete result is optimal.
``````

So `add/3` terminates either if the first two, or the last argument are given. So you do not need the first argument. In stead, even the more general query terminates:

``````?- 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 And even better, use `if_/3` of library `reif` for SICStus and SWI to keep those clauses as determinate as possible.

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