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.