Comparison and unification of arbitrary terms. Terms are ordered in
the so-called “standard order” . This order is defined as
follows:
- Variables < Numbers < Strings
< Atoms < Compound Terms
- Variables are sorted by address.
- Numbers are compared by value. Mixed rational/float are
compared using cmpr/2.70Up
to 9.1.4, comparison was done as float. NaN is considered
smaller than all numbers, including
-inf. If the comparison
is equal, the float is considered the smaller value. If the Prolog flag
iso is defined, all
floating point numbers precede all rationals.
- Strings are compared alphabetically.
- Atoms are compared alphabetically.
- Non-text blobs (see section
12.4.10) occupy a band of their own between Strings and Atoms.
Two blobs of the same type are compared by that type; between types the
order is the order in which the types were registered and is therefore
not guaranteed to be the same in another run.
- Compound terms are first checked on their arity, then on
their functor name (alphabetically) and finally recursively on their
arguments, leftmost argument first.
Although variables are ordered, there are some unexpected properties
one should keep in mind when relying on variable ordering. This applies
to the predicates below as to predicate such as sort/2
as well as libraries that reply on ordering such as library library(assoc)
and library
library(ordsets). Obviously, an established relation A @<
As stated above, variables are sorted by address, which implies that
they are sorted by ‘age’, where ‘older’
variables are ordered before
‘newer’ variables. If two variables are unified their ‘shared’
age is the age of oldest variable. This implies we can examine a list of
sorted variables with ‘newer’ (fresh) variables without
invalidating the order. Attaching an attribute, see section
8.1, turns an ‘old’ variable into a ‘new’
one as illustrated below. Note that the first always succeeds as the
first argument of a term is always the oldest. This only applies for the first
attribute, i.e., further manipulation of the attribute list does not
change the ‘age’.
?- T = f(A,B), A @< B.
T = f(A, B).
?- T = f(A,B), put_attr(A, name, value), A @< B.
false.
The above implies you can use e.g., an assoc (from library
library(assoc), implemented as an AVL tree) to maintain
information about a set of variables. You must be careful about what you
do with the attributes though. In many cases it is more robust to use
attributes to register information about variables.
Note that the standard order is not well defined on
rational trees, also known as cyclic terms. This
issue
was identified by Mats Carlsson, quoted below. See also
issue#1162
on GitHub.
Consider the terms A and B defined by
the equations
[1] A = s(B,0).
[2] B = s(A,1).
- Clearly, A and B are not identical, so either
A @< B or A @> B must hold.
- Assume
A @< B. But then, s(A,1) @> s(B,0)
i.e.,
B @< A. Contradiction.
- Assume
A @> B. But then, s(A,1) @< s(B,0)
i.e.,
B @< A. Contradiction.
By default, comparing such terms returns an arbitrary order, which
breaks predicates that rely on a consistent order such as sort/2,
library library(assoc) and library library(ordsets).
Setting the Prolog flag incomparable
to error raises an exception instead. The predicate partial_compare/3
reports such pairs as
incomparable(Sub1, Sub2).
- [ISO]@Term1 == @Term2
- True if Term1 is equivalent to Term2. A variable
is only identical to a sharing variable.
- [ISO]@Term1 \== @Term2
- Equivalent to
\+Term1 == Term2
- [ISO]@Term1 @< @Term2
- True if Term1 is before Term2 in the standard
order of terms.
- [ISO]@Term1 @=< @Term2
- True if both terms are equal (==/2)
or Term1 is before Term2 in the standard order of
terms.
- [ISO]@Term1 @> @Term2
- True if Term1 is after Term2 in the standard order
of terms.
- [ISO]@Term1 @>= @Term2
- True if both terms are equal (==/2)
or Term1 is after Term2 in the standard order of
terms.
- [ISO]compare(?Order,
@Term1, @Term2)
- Determine or test the Order between two terms in the standard
order of terms. Order is one of
<>=
- partial_compare(?Order,
@Term1, @Term2)
- As compare/3,
but only decides the Order if this decision is
stable, i.e., if it cannot be invalidated by binding a
variable. This predicate is the building block for comparisons that must
be sound on non-ground terms. If the order depends on a variable, Order
is unified with
undecided(Sub1, Sub2), where Sub1
and
Sub2 are the first pair of subterms of Term1 and Term2
that could not be compared. Because the standard order compares terms
lexicographically, this pair decides the entire comparison: after any
further instantiation, compare(Order, Term1, Term2) gives
the same result as compare(Order, Sub1, Sub2), unless Sub1
and
Sub2 become equal (==/2), in which case the comparison must
continue with the remaining subterms.
If the two terms are cyclic and have no order (see
section 4.6.1), Order
is unified with
incomparable(Sub1, Sub2), where Sub1 and Sub2
are a pair of subterms at which the lexicographic comparison runs into a
cycle. Unlike undecided(Sub1, Sub2), further instantiation
cannot make the terms comparable.
?- partial_compare(Order, f(a,1), f(a,2)).
Order = (<).
?- partial_compare(Order, f(a,X), f(a,b)).
Order = undecided(X, b).
?- partial_compare(Order, f(X,1), f(X,2)).
Order = (<).
?- partial_compare(Order, f(_,1), g(_,2)).
Order = (<).
?- A = s(B,0), B = s(A,1), partial_compare(Order, A, B).
A = s(s(A, 1), 0),
B = s(A, 1),
Order = incomparable(s(s(A, 1), 0), s(A, 1)).
The last two queries illustrate that a variable only makes the
comparison undecided if it is actually reached: the first of these
compares the same variable to itself and continues with the second
argument, while the second is decided by the functor name before the
arguments are examined at all.
1 
