Prolog addition excercise

Question

I have this very simple code as a representation of numerals. The problem is when I use the add2 function.

Example: add2(s(0)+s(s(0)), s(s(0)), Z). returns s(s(s(s(s(0))))) correctly. However add2(0, s(0)+s(s(0)), Z). always returns s(0)+s(s(0)). Can anyone see why this is happening?

numeral(0).
numeral(s(X)) :- numeral(X).
numeral(X+Y) :- numeral(X), numeral(Y).

add(0,X,X).
add(s(X),Y,s(Z)) :- add(X,Y,Z).

%%  exercise 1
add2(X,Y,R) :- add(X,Y,R).
add2(X+Y,Z,R) :- add(X,Y,A),add2(A,Z,R).
add2(X,Y+Z,R) :- add(Y,Z,A),add2(X,A,R).

Answer 1

It's happening because of the combination of the first add2 clause and the first add clause. Your add2(0, ..., ...) will trigger add(0, ..., ...) which always unifies the second and third argument.

Answer 2

When you call add2(0, s(0)+s(s(0)), Z), it will be unified with the first clause of add2/3, since this first clause only has three variables in the head, so it can be unified with any call of add2/3. This in turn will in your example lead to calling the first clause of add/3, so Z will be bound to s(0)+s(s(0)).

The problem with your code is that the more specific clauses of add2/3 are placed after the general clause. So to make your code work, place the first clause of add2/3 last, and add cuts to the other two, e.g.

add2(X+Y,Z,R) :- !,add(X,Y,A),add2(A,Z,R).

since when the head of that clause has matched the query, you're sure that you're executing the right clause and you won't have trouble on backtracking.

Answer 3

In Prolog function symbols like the infix + are not evaluated. It seems you are trying to evaluate all occurrences of +. However, some of them are still not evaluated and this can be quite tricky if you try to do this ad hoc as in add2/3. Consider add2(0+0+0,0,R) which fails with your definition.

What you call numeral/1 might better be called expression/1.

Consider to define an auxiliary predicate eval/2 to simplify expressions to s(X)-numbers. Note however, that even such a definition will still fail for goals like add2(0,0,0+0). This is an inherent problem which can only be solved using constraints or similar techniques...