Why doesn't < evaluate the arguments?

[Yossu]

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?

Thanks for any help you can give.

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

[peter.ludemann]

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.

[brebs]

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.

[oskardrums]

@brebs

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.

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

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

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

[brebs]

@oskardrums

FYI I get the same with plain </2

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

[peter.ludemann]

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.

[Yossu]

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

[peter.ludemann]

@Yossu

rewrite it using if, but got very confused with the syntax

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

[Yossu]

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

[peter.ludemann]

@j4n_bur53

build a façade

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.

[peter.ludemann]

@j4n_bur53

So I don’t know where the Gcd is G comes from?

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

[j4n_bur53]

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

[peter.ludemann]

@j4n_bur53

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