Why is Prolog's sum function struggling with non-zero first variables?

[gnome]

This is supposed to recursively define a function sum(X,Y,Z) meaning X + Y = Z. how could anything be simpler, right?

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

It's very good at telling that 0+1=1 or 0+2=2, etc. But give it anything other than 0 for the first variable and it's lost. What's wrong?

 

[dodo]

I don't have a Prolog interpreter at hand to check this, but I can make a few suggestions that you can try yourself; at least they will give some clues.

0) I hope a successor predicate is implemented in your interpreter!

1) Prolog works by unifying your query to the head (left-side) of clauses; and unifying is NOT evaluating. So the most probable reason is that compound terms like s(X) or s(Z) in the head of the second clause won't unify with atomic entities such as numbers, in a query like sum(1,2,3).

Try this alternate to your second clause:

sum(X1,Y,Z1) :- X1 is s(X), Z1 is s(Z), sum(X,Y,Z).

(Syntax might vary for the evaluation operator "is"; it might be implemented as "=".)

Hope this helps.

---
Edit:
I fail to recall if s(X) will be at all evaluable. But something that will work in most interpreters is

sum(X1,Y,Z1) :- X1 is X+1, Z1 is Z+1, sum(X,Y,Z).

As for the behavior of the s() predicate, I'm not sure. You can try... and tell us.

---
Edit 2:
Of course, having the ability to evaluate expression you can write a single-clause sum() as

sum(X,Y,Z) :- X is Y+Z.

But I suppose the former has an exercising value. Sorry for the multiple edits, to me it's "long time no see" for Prolog.

 

[gnome]

Thanks for the suggestions, but I still don't have the answer.

0) yes, there is a successor function. For example this program:

int2s(0,0).
int2s(N,s(S)) :- N>0, N1 is N-1, int2s(N1,S).

works this way:
| ?- int2s(5,T)
T = s(s(s(s(s(0)))))?
yes

1) sum(X1,Y,Z1) :- X1 is s(X), Z1 is s(Z), sum(X,Y,Z).
doesn't compile; gives
error: wrong arithmetic expression : s(_570b34)
error: wrong arithmetic expression : s(_570ba8)

2) sum(X1,Y,Z1) :- X1 is X+1, Z1 is Z+1, sum(X,Y,Z).
sort of defeats the purpose, which was to understand how the successor function works, but I tried it anyway in the interest of science.
It compiles, and responds reasonably to queries involving addition of 0 to a number, but other queries result in errors I don't understand. For example, this series of queries and responses:

| ?- compile(math)
Compiling...math.pl
compiled in 0 milliseconds

yes
| ?- load(math)
loading...math.out

yes
| ?- sum(0,1,1)

yes
| ?- sum(X,1,1)
X = 0?
yes
| ?- sum(X,1,2)
** Error ** number_expected:_570828+1
| ?- sum(1,1,2)
** Error ** number_expected:_570828+1
| ?-

 

[gnome]

Hmmm...

It turns out that the original program

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

does work. I just wasn't forming the queries correctly. Here's an example of what it gives:

| ?- sum(s(s(0)),s(s(s(s(s(0))))),T)
T = s(s(s(s(s(s(s(0)))))))?
yes

Guess it'll take a while to figure out how to do something useful with that.

 

[dodo]

Hmmm... and note that this DOESN'T mean that s() is something built-in into your Prolog interpreter. The s() is interpreted symbolically; the whole thing would've equally worked if representing 2 as after(after(0)), where of course after() is nothing special. (And substituting after() for s() accordingly in your clauses, of course.)

As for the failure in " sum(X1,Y,Z1) :- X1 is X+1, Z1 is Z+1, sum(X,Y,Z). ",
1) I assume you did include the initial clause too, "sum(0,Y,Y)."
2) _<number> is the construct the interpreter is using to refer to an unbound variable; the error is saying, "I can't add 1, in X+1 (or Z+1), if X (or Z) has no value". A possible test is to change the order of the second clause (again, experimenting) as
sum(X1,Y,Z1) :- sum(X,Y,Z), X1 is X+1, Z1 is Z+1.
so it'll recurse before the evaluation. (Strange, though.)

Another interesting test is to combine your original problem with the given predicates for int2s() (which "translate" an integer into a symbolic form made of s's). Something like

... int2s as above...

sum(0,Y,Y).
sum(X,Y,Z) :- int2s(X,Xs), int2s(Z,Zs), Xs is s(X0), Zs is s(Z0), sum(X0,Y,Z0).

or, alternatively,

sum(0,Y,Y).
sum(X,Y,Z) :- int2s(X,s(X0)), int2s(Z,s(Z0)), sum(X0,Y,Z0).

and check if it accepts integers now.

 

[gnome]

>>.. and note that this DOESN'T mean that s() is something built-in into your Prolog interpreter.
Thanks for pointing that out. Now it makes more sense that it doesn't produce a numerical result.


>>1) I assume you did include the initial clause too, "sum(0,Y,Y)."
Of course.

>>A possible test is to change the order of the second clause (again, experimenting) as
>>sum(X1,Y,Z1) :- sum(X,Y,Z), X1 is X+1, Z1 is Z+1.
Interestingly, that almost works. It seems to be a case of yes/maybe. Here are some sample queries to that:

| ?- sum(0,1,T)
T = 1?
yes
| ?- sum(1,1,T)...(
T = 2?
yes
| ?- sum(4,6,T)
T = 10?
yes
| ?- sum(5,2,7)...(here I supplied all 3 literals & it responded correctly)

yes
| ?- sum(1,2,3)...(same here)

yes
| ?- sum(T,2,5)...(here I supply a variable for the first term; response is appropriate)
T = 3?
yes
| ?- sum(2,T,5)...(but it can't deal with the variable as the 2nd term)
** Error ** number_expected:_570828+1
| ?- sum(4,2,7)...(and if I supply 3 literals that don't add correctly, instead of saying "no" it hangs
| ?-......(I had to use ctrl-c to get out of that loop)

Your last two suggestions are interesting, but they didn't work. The first one

sum(0,Y,Y).
sum(X,Y,Z) :- int2s(X,Xs), int2s(Z,Zs), Xs is s(X0), Zs is s(Z0), sum(X0,Y,Z0).

doesn't compile, giving two "wrong arithmetic expression" errors on the s(X0) and s(Z0) expressions.
The last one

sum(0,Y,Y).
sum(X,Y,Z) :- int2s(X,s(X0)), int2s(Z,s(Z0)), sum(X0,Y,Z0).

compiles but doesn't do what we wanted. It gives good responses to queries in the form (T,4,4) or (0,4,4) for example, but any other format gives "error : number expected".

Still, there should be some way to combine the predicates. I'll work on it some more as time permits.

PS: If you want to play around with small prolog programs, here's a link to a cute online prolog implementation. It's not what I've been using (I'm using B-prolog) but it seems to work the same for these little programs.
http://kti.ms.mff.cuni.cz/~bartak/prolog/testing.html

 

[dodo]

"Don't give a man a fish, but a fishing rod." Thanks for the link!

Edit: After some sleep :), I can see I forgot, in the second variant of the last example, to convert the s's back to numbers, before recursing...