Binary Arithmetic with non-standard representation in Prolog

I'm trying to do binary operations in Prolog for a homework assignment. I'm not looking for copy-paste answers but I'm really stuck and any pointers would be greatly appreciated. The numbers are defined with f0 = 0 and f1 = 1, from least to most significant digit, i.e.:

f0(f0(f1(null))) = 100 = 4
f1(f1(null)) = 11 = 3
f0(f1(f0(null)) = 010 = 2 (this is considered an "illegal" number because of the trailing zeroes)

The requirements are:

Define predicate incr(P1,P2) such that P2 is the successor to P1
Define predicate legal(P) true exactly of legal Pterms (excluding null and anything with leading zeroes)
Using legal/2, revise incr to incrR such that incrR(X,Y) lists all numbers in order.
Define predicate add(P1,P2,P3) such that P3 = P1+P2

I have working predicates for 1-3, and my add/3 works to verify values true or false, but it is failing to find P3 when given P1 and P2 (i.e. add(something,something,X) is non-terminating). I'm not sure if my add is wrong, or if there are problems in my previous predicates not allowing me

We are not allowed to use lists or in-built arithmetic for this as we haven't covered them yet. My current knowledge base is as follows:

% Question 1

incr(f1(null),f0(f1(null))).
incr(f1(X),f0(Ans)) :- incr(X,Ans).
incr(f0(X),f1(X)).

% Question 2

legal(f0(null)).
legal(X) :- legal(A), incr(A,X).

% Question 3

incrR(X,Y) :- legal(X), incr(X,Y).

% Question 4

add(f0(null),X,X).
add(P1,P2,P3) :- incrR(A,P1), incrR(B,P3), add(A,P2,B).

I've been struggling with this for a few days and haven't found anything to help me online, so I thought I'd ask here as a hail mary. Any help much appreciated.

Solution

You just need to do the addition in the same manner in which you'd do decimal arithmetic long hand. Beginning with the least significant digit (the "one's place"):

Add each digit together. The resulting value is the sum modulo the base of the numbering system in use (10 for decimal, 2 for binary). The carry is the result of integer division by the base.
Move to the next most significant digit, include the carry as a value to be summed.
Repeat until you run out of digits.

Your nested data structure has the least significant digit first, so that actually simplifies things a bit.

A common pattern in Prolog is the use of helper predicates, that have some additional arguments that carry the state neccessary for the computation. Here, that additional state would be the carry.

That leads us to this:

You'll notice that the the result is built up as we go, as an open data structure, where its content is unbound, and is finally closed only once the digits of both numbers have been exhausted.

%----------------------------------------------------------------
% add/3: add two binary numbers, X and Y, yielding the sum as Z
%----------------------------------------------------------------
add( X, Y, Z ) :- add(f0,X,Y,Z) . % invoke the helper with an initial carry of zero

%---------------------------------------------------------------------
% add/4: compute the sum of two binary numbers, X and Y, digit-by-digit with a carry,
% yielding Z as the result.
%
% add( Carry , X , Y , Sum  ) .
%---------------------------------------------------------------------

% these clauses are the terminating cases
add( f0 , null  , null  ,    null  ) . % both numbers exhausted with a 0 carry: close the result.
add( f1 , null  , null  , f1(null) ) . % both numbers exhausted with a 1 carry: close the result.

% these clauses are the non-terminating special cases where we've
% exhausted the digits of one number, but not the other
add( f0 , null  , f0(Y) , f0(Z)    ) :- add(f0,null,Y,Z) . % 0+0   --> 0 carry 0
add( f0 , null  , f1(Y) , f1(Z)    ) :- add(f0,null,Y,Z) . % 0+1   --> 1 carry 0
add( f0 , f0(X) , null  , f0(Z)    ) :- add(f0,X,null,Z) . % 0+0   --> 0 carry 0
add( f0 , f1(X) , null  , f1(Z)    ) :- add(f0,X,null,Z) . % 0+1   --> 1 carry 0
add( f1 , null  , f0(Y) , f1(Z)    ) :- add(f0,null,Y,Z) . % 1+0   --> 1 carry 0
add( f1 , null  , f1(Y) , f0(Z)    ) :- add(f1,null,Y,Z) . % 1+1   --> 0 carry 1
add( f1 , f0(X) , null  , f1(Z)    ) :- add(f0,X,null,Z) . % 1+0   --> 1 carry 0
add( f1 , f1(X) , null  , f0(Z)    ) :- add(f0,X,null,Z) . % 1+1   --> 0 carry 1

% And these clauses are the general case, where we have digits from both numbers.
add( f0 , f0(X) , f0(Y) , f0(Z)    ) :- add(f0,X,Y,Z)    . % 0+0+0 --> 0 carry 0
add( f0 , f0(X) , f1(Y) , f1(Z)    ) :- add(f0,X,Y,Z)    . % 0+0+1 --> 1 carry 0
add( f0 , f1(X) , f0(Y) , f1(Z)    ) :- add(f0,X,Y,Z)    . % 0+1+0 --> 1 carry 0
add( f0 , f1(X) , f1(Y) , f0(Z)    ) :- add(f1,X,Y,Z)    . % 0+1+1 --> 0 carry 1
add( f1 , f0(X) , f0(Y) , f1(Z)    ) :- add(f0,X,Y,Z)    . % 1+0+0 --> 1 carry 0
add( f1 , f0(X) , f1(Y) , f0(Z)    ) :- add(f1,X,Y,Z)    . % 1+0+1 --> 0 carry 1
add( f1 , f1(X) , f0(Y) , f0(Z)    ) :- add(f0,X,Y,Z)    . % 1+1+0 --> 0 carry 1
add( f1 , f1(X) , f1(Y) , f1(Z)    ) :- add(f1,X,Y,Z)    . % 1+1+1 --> 1 carry 1