Prolog binary addition without cuts(!)

I am trying to figure out how to add two binary numbers together which are represented as lists. For example: addNumbers([1,0,1], [1,1,0,0], X). should return X = [1,0,0,0,1].

We are not allowed to use cuts(!) to solve this problem. So I know I have to implement an adder of sorts. Right now I have adding Digits implemented with its needed predicates:

addDigits(A,B,X,Y) :- myXor(A,B,X), myAnd(A,B,Y).

myAnd(A,B,R) :- A == 1, B == 1, R is 1.
myAnd(A,B,R) :- A == 0, B == 0, R is 0.
myAnd(A,B,R) :- A == 1, B == 0, R is 0.
myAnd(A,B,R) :- A == 0, B == 1, R is 0.
myOr(A,B,R) :- A == 0, B == 0, R is 0.
myOr(A,B,R) :- A == 0, B == 1, R is 1.
myOr(A,B,R) :- A == 1, B == 0, R is 1.
myor(A,B,R) :- A == 1, B == 1, R is 1.

This correctly returns X as the sum of the 2 binary digits and Y as the carry. Now I know I need this for my adder. Now to actually implement addDigits is where I am stuck. This is currently what I have but does not work. NOTE: The hint was the start the the LSB's but I currently don't do that.

addNumbers([HA|TA],[HB|TB],X) :- adder(HA,HB,Cin,Sum,Cout,X),
    append(Sum, X, X),
    addNumbers(TA,TB,X).

adder(X,Y,Cin,Sum,Cout) :- addDigits(X,Y,Sum1,Carry1),
    addDigits(Sum1, Cin, Sum, Carry2),
    myOr(Carry1, Carry2, Cout).

Any help/suggestions would be appreciated.

Cheers

Solution

You are on a good track. Your major problem is to understand typical Prolog recursion.

But first, your binary functions: They are correct, but it's easier and more readable like this (you are missing this one anyway):

myXor(1,0,1).
myXor(0,1,1).
myXor(1,1,0).
myXor(0,0,0).

There is a typo in your myOr in the fourth case: you spelled it with a lower case "o". With this defined, your adder does indeed work correctly!

Now, about the recursion: You really need to start with the LSB, otherwise you can't even know which bits to add, because the numbers are not necessarily the same length. Fortunately, you can do this easily by wrapping the call in reverses:

addNumbers(N1, N2, Sum) :- 
    reverse(N1, N12), 
    reverse(N2, N22),
    addNumbers(N12, N22, 0, [], Sum0),
    reverse(Sum0, Sum).

This is quite a common pattern in Prolog: addNumbers/3 calling addNumbers/5 with more parameters needed for the recursion. The "0" is the initial carry, the [] is the accumulator for the result. Here is addNumbers/5, with some changes from your version:

addNumbers([HA|TA],[HB|TB],Cin,X0,X) :- 
    adder(HA,HB,Cin,Sum,Cout),
    append(X0, [Sum], X1),
    addNumbers(TA,TB,Cout,X1,X).

First, note that you need to receive Cin as an input parameter here! Also, we have X0 as an "accumulator" variable, that is, it grows longer with each recursive call. The final call will have the result, so it can make it into the output variable. For that, you also need the base cases:

addNumbers([],B,Cin,X0,X) :- % TODO: Respect Cin
    append(X0,B,X).
addNumbers(A,[],Cin,X0,X) :- % TODO: Respect Cin
    append(X0,A,X).

See how the result of append is not X1 (another intermediate variable) as above, but X? This is because its the final result, and it will be unified with the same X all the way down the call stack, and this way it becomes the output of the whole addNumbers/5 call!

I left it unfinished though, so that there is some (little) work for you left: Also the base cases need to take Cin into account...