Why doesn't < evaluate the arguments?

Help!
1

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

2

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
4

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 :grinning:

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
5

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

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

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

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

7

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

@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 :smiley:

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.

9

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
10

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

12

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
15

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

16

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

17

(#=)/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).