How to fix this recursive addition?

Question

I am new to logic programming and Prolog. The following Prolog program defines a predicate add/3 for multiplying the first argument to the second argument, which results in the third argument, based on the equation x + y = z which is equivalent to (x − 1) + y = (z − 1):

add(0, Y, Y) :-
  number(Y).
add(X, Y, Z) :-
  number(X),
  number(Z),
  succ(U, X),
  succ(V, Z),
  add(U, Y, V).

But it this query, supposed to solve the equation 1 + 0 = z, does not return the expected result (1):

?- add(1, 0, Z).
   false.

How to fix this recursive addition?

The call to `number(Z)` will fail if Z is currently uninstantiated. — gusbro, Jul 30 '21 at 16:52
@gusbro I thought that `number(Z)` did actually instantiate `Z`. Because removing that literal yields an error: `Arguments are not sufficiently instantiated`. — Géry Ogam, Jul 30 '21 at 16:54
`number(Z)` checks whether Z is a number. The error you are getting when you remove that call is from `succ(V, Z)` because both `V` and `Z` are uninstantiated in your sample call. You have to change your algorithm or use _CLP(fd)_ — gusbro, Jul 30 '21 at 17:04
@gusbro And how would you change the algorithm (I don’t want to use CLP)? — Géry Ogam, Jul 30 '21 at 17:07
You may swap the goals: first call `add(U, Y, V)`, then `succ(V, Z)`. That should work for queries where "X"and "Y" are instantiated. — gusbro, Jul 30 '21 at 17:26
you have to remove the number(Z) as stated in my first comment — gusbro, Jul 30 '21 at 17:32
@gusbro Many thanks, that works! Could you write an answer so that I can accept it? — Géry Ogam, Jul 30 '21 at 17:37

score 1 · Accepted Answer · edited Aug 25 '21 at 09:42

1

The reason you get false is because the second clause of add/3 calls number(Z) which only succeeds for ground number variables, but you are calling it with Z uninstantiated. number/1 cannot be used as a generator.

Removing that goal will in turn give you another error, now in succ(V, Z) as you end up calling it with both variables uninstantiated and that predicate requires that at least one of its arguments be instantiated.

You can swap the goal with the recursive call to add/3 so that V gets instantiated prior to calling succ/2. As succ/2 already checks its arguments I will just remove the check for X being a number.

add(0, Y, Y) :-
  number(Y).
add(X, Y, Z) :- 
  succ(U, X),
  add(U, Y, V),
  succ(V, Z).

This procedure now should work for mode +,+,?. It will not work right for other modes. You may want to check CLP(fd).

To make it work with at most 1 unbound variable within the three parameters you may split the recursive step on two different paths so as to ensure the first call to succ/2 has 1 bound variable and the second call to succ/2 has at least 1 bound variable.

add(0, Y, Y) :-
  number(Y).
add(X, Y, Z) :-
  (var(Z) -> L1-R1/L2-R2 = U-X/V-Z; L2-R2/L1-R1 = U-X/V-Z),
  succ(L1, R1),
  add(U, Y, V),
  succ(L2, R2).

which essentially selects an equation which can be evaluated with Prolog arithmetics.

edited Aug 25 '21 at 09:42

Géry Ogam

6,336
4
38
67

answered Jul 30 '21 at 18:34

gusbro

22,357
35
46

Thanks! Is there a way to make it work for any modes (without CLP)? – Géry Ogam Jul 30 '21 at 18:37
You can easily make it work with queries that have 2 ground arguments. You just have to use the proper equation for the unbound argument. I get you want to do this as an exercise so you may try it yourself. – gusbro Jul 30 '21 at 18:47
Also the usual recursive solution for this problem uses peano representation of successors and not actual integers. You may look for peano and addition on this site for similar questions. – gusbro Jul 30 '21 at 18:49
So `add(X, Y, Z) :- succ(V, Z), add(U, Y, V), succ(U, X).` works for a single variable in the first position (e.g. `add(X, 2, 2)`), `add(X, Y, Z) :- succ(U, X), succ(V, Z), add(U, Y, V).` works for a single variable in the second position (e.g. `add(2, Y, 2).`), and `add(X, Y, Z) :- succ(U, X), add(U, Y, V), succ(V, Z).` works for a single variable in the third position (e.g. `add(2, 2, Z).`). How can I combine these clauses into a single rule to handle these three kinds of query? – Géry Ogam Jul 30 '21 at 22:35
1

@Maggyero: Edited the answer to show how you may combine those clauses onto a single rule that handles any case with at most 1 free variable – gusbro Jul 31 '21 at 04:14
Thanks, I have learnt a lot. The key was the predicate `var/1` which tests whether its argument is a free variable. I think that an equivalent rule definition (but simpler for me to understand) is: `add(0, Y, Y). add(X, Y, Z) :- var(X) -> succ(V, Z), add(U, Y, V), succ(U, X); var(Y) -> succ(U, X), succ(V, Z), add(U, Y, V); succ(U, X), add(U, Y, V), succ(V, Z).` – Géry Ogam Jul 31 '21 at 12:27
Note that I also removed the predicate `number/1` in the first clause because it makes the results non symmetric (it returns `false` only for calls that bind the *second* parameter to a non-number ground argument) and it is useless (the last predicate `succ/2` already checks it since `V` is `Y` when `U` is `1`). – – Géry Ogam Jul 31 '21 at 12:27
By the way, your rule definition and my equivalent one work also for queries with *two* free variables, as long as the third parameter variable is bound, e.g. `add(X, Y, 3)`. – Géry Ogam Jul 31 '21 at 12:28
I have just found another equivalent rule definition that does not use the `->/2` predicate: `add(0, Y, Y). add(X, Y, Z) :- ground(X), ground(Z), succ(U, X), succ(V, Z), add(U, Y, V). add(X, Y, Z) :- ground(X), var(Z), succ(U, X), add(U, Y, V), succ(V, Z). add(X, Y, Z) :- ground(Z), var(X), succ(V, Z), add(U, Y, V), succ(U, X).` – Géry Ogam Aug 01 '21 at 18:26
@Maggyero you can usually "split" a clause that uses `->/2` by onto 2 separate clauses guarding each clause with the prerequisites needed to "enter" each clause. In your last comment, one clause guards for `X` and `Y` being ground, the second with `X` being ground and `Z` free, and the last one with `Z` being ground and `X` free. Note that if you "enter" any of those clauses then the other ones will not go through. – gusbro Aug 01 '21 at 18:33
Thanks for the information. I have just opened a new question [here](https://stackoverflow.com/q/68614837/2326961) about recursive multiplication. This time I have a stack overflow issue when the query has *two* free variables in the first and second position. May I require your expertise again? – Géry Ogam Aug 01 '21 at 22:34

How to fix this recursive addition?

1 Answers1