How to fix this recursive multiplication?

Question

I am new to logic programming and Prolog. The following Prolog program defines a predicate mul/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 + y = z:

mul(0, _, 0).
mul(X, Y, Z) :-
  ground(X),
  succ(U, X),
  add(V, Y, Z),
  mul(U, Y, V).
mul(X, Y, Z) :-
  var(X),
  add(V, Y, Z),
  mul(U, Y, V),
  succ(U, X).

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).

But it exhausts resources with queries in this argument mode:

?- mul(X, Y, 2).
   X = 1, Y = 2
;  X = 2, Y = 1
;
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 20.8Mb, trail: 10.4Mb
  Stack depth: 452,739, last-call: 0%, Choice points: 452,716
  In:
    [452,739] add(_1326, 0, 0)
    [452,738] add(_1354, 0, 1)
    [452,737] add(_1382, 0, 2)
    [452,736] mul(_1410, 0, 2)
    [452,735] mul(_1438, 0, 2)

How to fix this recursive multiplication?

Of interest: [PRESS: PRolog Equation Solving System](https://github.com/maths/PRESS) — Guy Coder, Aug 02 '21 at 00:10
@GuyCoder Thanks for the reference. But it is too advanced for me at the moment. — Géry Ogam, Aug 02 '21 at 05:43
You are unnecessarily mixing so many things here together. Note that `ground/1` is not the opposite of `var/1`. See [this](https://stackoverflow.com/q/10139640/772868) for pure solutions using successor arithmetics. — false, Aug 02 '21 at 13:29
@false Thanks for the link, it is very informative. So successor arithmetics is about using the function `succ/1`, while non successor arithmetics is about not using it (but using the predicate `succ/2` is allowed)? — Géry Ogam, Aug 02 '21 at 16:33
More commonly, it's `s/1`. Note that with this notation you can express things like `X = s(s(_))` meaning all numbers ≥ 2. Otherwise you would need constraints like [tag:clpfd]. The built-in `succ/2` is restricted to cases where one of its arguments is a given integer. — false, Aug 02 '21 at 19:32
@false Do you agree with [vukung’s answer](https://stackoverflow.com/a/68617655/2326961)? — Géry Ogam, Aug 03 '21 at 10:26
@false Thanks, so what correction do you suggest (in this context, i.e. not in successor arithmetics)? Feel free to write an answer. — Géry Ogam, Aug 03 '21 at 15:42
Writing programs with meta-logical tests like `var/1` and `ground/1` isn't a good start. Prior to that work with [tag:successor-arithmetics] and [tag:clpfd]. That will help you to clarify a lot of notions like non-termination, and the like. Then, (much later) consider to use the more procedural built-ins that are *safe* by using instantiation errors for too general queries. `succ/2` but also `(is)/2` come to mind. After all that, you might consider such examples as this one. But I see almost no merit to do so. It's extremely complex, and very prone to errors as you have seen. — false, Aug 03 '21 at 18:45
@false Okay, I did not expect that writing basic operations was that difficult in logic programming. But if you know the right answer, it might be interesting to post it, for the community (unless it is ten pages long). — Géry Ogam, Aug 03 '21 at 22:24
See my first comment about a pure Prolog solution. But as it [turned out](https://stackoverflow.com/questions/10139640/prolog-successor-notation-yields-incomplete-result-and-infinite-loop/10141181#comment121312330_10141181), your assignment was not about Prolog but some course specific logic programming language. — false, Aug 04 '21 at 09:45

score 2 · Accepted Answer · edited Aug 25 '21 at 09:51

The program works okay in the sense that it gives the two solutions, X = 1, Y = 2 and X = 2, Y = 1. It then goes into an infinite search for other solutions.

The problem is with this rule:

mul(X, Y, Z) :-
  var(X),
  add(V, Y, Z),
  mul(U, Y, V),
  succ(U, X).

Here mul(U, Y, V) recurses in a way that the first argument is not ground, but the previous rules assume that it is (when V is not zero). Simply swapping the first two arguments solves the problem.

It is still not perfect though, consider

?- mul(2, 3, X).
   false.

Here the problem is in the previous rule:

mul(X, Y, Z) :-
  ground(X),
  succ(U, X),
  add(V, Y, Z),
  mul(U, Y, V).

The call to add(V, Y, Z) becomes add(V, 3, Z), which is under-defined. Swapping it with the next mul solves this:

mul(X, Y, Z) :-
  ground(X),
  succ(U, X),
  mul(U, Y, V),
  add(V, Y, Z).

So is it okay now? Not really, e.g.

?- mul(X, 3, 6).
   false.

Try to go through it with

?- trace, mul(X,3,6).

and find where the problem lies.

--- EDIT ---

Okay, so let's try this from scratch.

To simplify things, first look at the case when the first two arguments are not variables:

% add1(+X, +Y, ?Z) [semidet]
add1(0, Y, Y) :-
  !.
add1(X, Y, Z) :-
  succ(X1, X),
  add1(X1, Y, Z1),
  succ(Z1, Z).

% mul1(+X, +Y, ?Z) [semidet]
mul1(0, _, 0) :-
  !.
mul1(X, Y, Z) :-
  succ(X1, X),
  mul1(X1, Y, Z1),
  add1(Z1, Y, Z).

Then the other case, when the sum/product is known:

% add2(?X, ?Y, +Z) [nondet]
add2(0, Y, Y).
add2(X, Y, Z) :-
  succ(Z1, Z),
  add2(X1, Y, Z1),
  succ(X1, X).

% mul2(?X, ?Y, +Z) [nondet]
mul2(X, Y, 0) :-
  !,
  (X = 0; Y = 0).
mul2(X, Y, Z) :-
  nonvar(Y),
  !,
  succ(Y1, Y),
  add2(Z1, X, Z),
  mul2(X, Y1, Z1).
mul2(X, Y, Z) :-
  add2(Z1, Y, Z),
  mul2(X1, Y, Z1),
  succ(X1, X).

Note that when the third rule in mul2 recurses, its second argument will be known, and that is used by the second rule. This is very similar to what you have written originally.

Finally, you can create a rule to choose the one you need:

add(X, Y, Z) :-
  nonvar(Z) -> add2(X, Y, Z); add1(X, Y, Z).

mul(X, Y, Z) :-
  nonvar(Z) -> mul2(X, Y, Z); mul1(X, Y, Z).

(Of course, you can unite these rules using var(X) etc., but I think it is much clearer this way.)

Thanks! I am still struggling to find where the problem lies. Could you provide the answer? — Géry Ogam, Aug 02 '21 at 16:37
Thanks for the edit. @false pointed out that the query `add(X,1,Z), X=1.` does not work with your program. — Géry Ogam, Aug 03 '21 at 15:38
Yes, you would need constraints like clpfd for that. The above works in the two cases where either (`X` and `Y` ) or `Z` are given at the time of the call. — vukung, Aug 03 '21 at 16:56

How to fix this recursive multiplication?

1 Answers1

Linked