# Why doesn't < evaluate the arguments?

I’m working my way through a book, and have been reading about the way Prolog does arithmetic. He explained how `=` doesn’t cause evaluation, so `1+2=2+1` will be false, whereas `1+2=:=2+1` would be true.

Along the way, he said that `<` would evaluate its arguments.

One of the samples that followed involved writing a predicate to work out the greatest common divisor of two integers. The formula is simple enough…

1. if X and Y are equal, then D is X
2. if X < Y then D is the GCD of X and Y-X
3. if Y < X, do as in 2) but with X and Y reversed

This led me to the following code…

``````gcd(X, X, X).
gcd(X, Y, D) :-
X < Y,
gcd(X, Y-X, D).
gcd(X, Y, D) :-
Y < X,
gcd(Y, X-Y, D).
``````

However, this always failed.

Using `trace/0` (which I’m now beginning to understand), I could see that when it got to the lines with `<`, it didn’t evaluate the subtraction…

``````[trace] 19 ?- gcd(2, 4, D).
Call: (10) gcd(2, 4, _214) ? creep
Call: (11) 2<4 ? creep
Exit: (11) 2<4 ? creep
Call: (11) gcd(2, 4-2, _214) ? creep
Call: (12) 2<4-2 ? creep
Fail: (12) 2<4-2 ? creep
Redo: (11) gcd(2, 4-2, _214) ? creep
Call: (12) 4-2<2 ? creep
Fail: (12) 4-2<2 ? creep
Fail: (11) gcd(2, 4-2, _214) ? creep
Redo: (10) gcd(2, 4, _214) ? creep
Call: (11) 4<2 ? creep
Fail: (11) 4<2 ? creep
Fail: (10) gcd(2, 4, _214) ? creep
false.
``````

If I understand this correctly, then on the 6th line (the first `fail`), it’s comparing `2` with `4-2`, which are not the same thing (when not evaluated) and so the comparison fails.

Why doesn’t `<` evaluate `4-2`?

P.S. Rewriting the code solved the problem…

``````gcd(X, X, X).
gcd(X, Y, D) :-
X < Y,
Z is Y-X,
gcd(X, Z, D).
gcd(X, Y, D) :-
Y < X,
Z is X-Y,
gcd(Y, Z, D).
``````

…but I would like to understand why the evaluation wasn’t done, when my book says it should be.

Thanks

The evaluation for (<)/2 was being done, but unification doesn’t evaluate:

``````gcd(X, X, X). % does not evaluate X
``````

Instead, you need to do something like this for the first clause:

``````gcd(X, Y, D) :-
X =:= Y  % evaluate
D is X.  % also evaluate
``````

So, as a general rule, it’s best to use is/2 to evaluate an expression rather than passing unevaluated expressions around.

BTW, this is how I’d write it (using if-then-else) without using is/2:

``````gcd(X, Y, Gcd) :-
(   X =:= Y
->  Gcd is X
;   X < Y
->  gcd(X, Y-X, Gcd)
;   % Y < X
gcd(Y, X-Y, Gcd)
).
``````

and using if-then-else and is/2:

``````gcd(X, Y, D) :-
(   X = Y
->  D = X
;   X < Y
->  Z is Y-X,
gcd(X, Z, D)
;   % Y < X,
Z is X-Y,
gcd(Y, Z, D)
).
``````

The if-then-else avoids creating choicepoints.

1 Like

2-5 is just a format - Prolog treats it as a structure, a term:

``````?- X = 2-5, X == -(2, 5).
X = 2-5.
``````

Edit: Whoops, (<)/2 does work with arithmetic expressions

If it didn’t, then could use e.g.:

``````less_than_eval(Less, More) :-
LessEval is Less,
MoreEval is More,
LessEval < MoreEval.
``````

Results:

``````?- less_than_eval(2-5, 4+6).
true.

?- less_than_eval(200-5, 4+6).
false.
``````
1 Like

FYI I get the same with plain `<`/2, as in:

``````?- 2 - 5 < 4 + 6.
true.

?- 200 - 5 < 4 + 6.
false.
``````

Whoops, I dived straight into a solution without checking that the problem really exists

If you don’t want to evaluate the arguments to “less than”, use (@<)/2 and (@>)/2:

``````?- (-) @> (+).
true.

?- 1-2 @< 1-a.
true.

?- 1-2 < 1-a.
ERROR: Arithmetic: `a/0' is not a function
ERROR: In:
ERROR:   [10] 1-2<1-a
ERROR:    [9] toplevel_call(user:user: ...) at /home/peter/.local/lib/swipl/boot/toplevel.pl:1173
``````

Exercise for the reader: create a term where (@<)/2 returns true and (<)/2 returns false (or vice versa), using the standard order of terms.

BTW, because (<)/2 and (>)/2 evaluate their arguments, you can avoid the use of (=:=)/2 by re-ordering the if-then-else:

``````gcd(X, Y, Gcd) :-
(   X < Y
->  gcd(X, Y-X, Gcd)
;   X > Y
->  gcd(Y, X-Y, Gcd)
;   Gcd is X
).
``````

However, this is less efficient than using is/2 because it re-evaluates the term at each iteration:

``````?- wrap_predicate(gcd(A,B,Gcd), gcd_wrap, W, ( writeln(gcd(A,B)), call(W) )).
W = call(<closure>(gcd/3)(A,B,Gcd)).

?- gcd(12,8, G).
gcd(12,8)
gcd(8,12-8)
gcd(12-8,8-(12-8))
G = 4.

?- gcd(12,7, G).
gcd(12,7)
gcd(7,12-7)
gcd(12-7,7-(12-7))
gcd(7-(12-7),12-7-(7-(12-7)))
gcd(7-(12-7),12-7-(7-(12-7))-(7-(12-7)))
gcd(12-7-(7-(12-7))-(7-(12-7)),7-(12-7)-(12-7-(7-(12-7))-(7-(12-7))))
G = 1.
``````

@peter.ludemann As always, an excellent answer! Not only did you explain what I asked, you even managed to anticipate the question I was about to ask!

Having seen that my code generated a choicepoint if the first number were greater than or equal to the second, I decided to try and rewrite if using `if`, but got very confused with the syntax I was about to post a question about it, and saw that you had already supplied the answer

I’m about to start the next set of exercises in the book I’m reading. To save time, perhaps you could answer the questions I’m going to ask on those before I start reading!

Thanks again.

SWI-Prolog has an extension (SSU), that allows a simpler syntax:

``````gcd(X, Y, Gcd), X < Y => gcd(X, Y-X, Gcd).
gcd(X, Y, Gcd), X > Y => gcd(Y, X-Y, Gcd).
gcd(X, _, Gcd) => Gcd is X.
``````

or, using is/2:

``````gcd(X, Y, Gcd), X < Y => Y_X is Y-X, gcd(X, Y_X, Gcd).
gcd(X, Y, Gcd), X > Y => X_Y is X-Y, gcd(Y, X_Y, Gcd).
gcd(X, _, Gcd) => Gcd = X.  % or: gcd(X, X, Gcd) => Gcd = X.
``````

(note that the last clause has `Gcd=X` on the right hand side of the `=>`; if that clause had been written `gcd(X,_,X) => true.` it would get a runtime error because SSU doesn’t do full unification on the left side of the `=>`.)

1 Like

@peter.ludemann Thanks, that’s a very neat way to write it!

Another way of getting the “façade” is by using wrap_predicate/4:

``````:- wrap_predicate(gcd(A,B,Gcd), gcd_wrap, W, gcd_wrap(W, A, B, Gcd)).

gcd(X, Y, Gcd), X < Y => gcd(X, Y-X, Gcd).
gcd(X, Y, Gcd), X > Y => gcd(Y, X-Y, Gcd).
gcd(X, _, Gcd) => Gcd = X.

gcd_wrap(call(Closure), X, Y, Gcd) :-
functor(Closure, ClosureBlob, 3),
X_eval is X,
Y_eval is Y,
call(ClosureBlob, X_eval, Y_eval, Gcd).
``````

EDIT: I originally wrote the following, but the final `Gcd is G` isn’t necessary. `Gcd is G` could be used instead of `X_eval is X, Y_eval is Y`, but would be less efficient:

``````gcd_wrap(call(Closure), X, Y, Gcd) :-
functor(Closure, ClosureBlob, 3),
X_eval is X,
Y_eval is Y,
call(ClosureBlob, X_eval, Y_eval, G),
Gcd is G.
``````
1 Like

I was trying a few things out with wrap_predicate/4 … the is/2 could be done either on the arguments or on the result and I left in both. My mistake (I’ll edit my response).

What happens if you use (#=)/2 from CLP(FD) instead (is)/2 ?

(#=)/2 works the same as is/2 in this situation. I suppose with sufficient work, we could make a version of `gcd/3` that would solve queries such as `gcd(X,10,2)`.