Equality, Inequality, and Arithmetic in Prolog

But there still remains a question: equality or inequality of what?
—Aristotle, Politics

One of the uglier parts of Prolog is the way that it has many different ways to write equality or inequality, with subtly different shades of meaning. Here are some of them:

Operator	Meaning
`=`	The two sides can and do unify (can be made the same)
`\=`	The two sides cannot be made to unify
`==`	The two sides are already the same
`\==`	The two sides are not already the same
`is`	The left side unifies with the value of the right-hand-side
`=:=`	The value of the left is equal to the value of the right
`<`	The value of the left is less than the value of the right
`=<`	The value of the left is less-than-or-equal-to the value of the right

Unification

The = operator in Prolog attempts to unify two terms, and fails if it cannot.

The \= operator succeeds when given two terms that cannot be unified, but fails if they could unify (though Prolog does not unify them in that case, since the failure forces backtracking).

Example

Assume each of the following is a separate query (so that all variables start out unset in each case, and each query is independent of the others):

```
X = a.
```
Succeeds and defines X to a.
```
[X,a] = [b,Y].
```
Succeeds and defines X to b and Y to a.
```
X = [Y].
```
Succeeds and defines X to be the list [Y] but leaves Y undetermined).
```
X = [X].
```
Perhaps surprisingly, succeeds and defines X to be the list [X]

This is implemented by defining X to be a linked list of length 1 whose only data is a pointer to the list itself.
It’s rather questionable whether this should be allowed, but detecting such pathological cases — known as an occurs check because it checks for circular definitions where the variable we are defining occurs in the proposed definition — would be extra work every unification. Since unification is such a fundamental operation in Prolog and executes so frequently, it was decided that doing the occur check would make Prolog too slow.
```
X \= Y
```
Fails, since we could have made both sides equal by defining X to be Y or vice-versa.
```
X = 3, Y = 2, X = Y.
```
Fails, since by the time we get to X = Y, we have already decided that X must be 3 and Y must be 2, and there’s no way to make 3 unify with 2.
```
X = 3, Y = 2, X \= Y.
```
Succeeds, since by the time we get to X \= Y, we have decided that X must be 3 and Y must be 2, and it is correct to say that 3 cannot be unified with 2.

Structural Equality

The operator == succeeds if the two terms are already the same, and fails otherwise. Unlike the unification operator =, the == operator never sets any variables.

The operator \= succeeds if the two terms are not the same, and fails if they are already the same

Example

Assume each of the following is a separate query (so that all variables start out unset in each case, and each query is independent of the others):

```
X == a.
```
Fails, since X starts out unset and so is not yet the same as a.
```
[X,a] == [b,Y].
```
Fails, since the list [X,a] (containing an unset variable X) is not the same as the list [b,Y] (containing an unset variable Y).
```
X == [X].
```
Fails, since the unset variable X is not already equal to a list.
```
X = [X], X == [X].
```
Succeeds, since by the time we check X == [X] we have already use definition to make [X] the definition of X.
```
1+2 == 1+2.
```
Succeeds, since both sides are the same term.
```
1+2 == 2+1.
```
Fails, since 1+2 is literally a different term than 2+1. (Prolog does not evaluate terms like 1+2 unless we use specific operators like is to force that to happen!)
```
X = 3, Y = 3, X==Y.
```
Succeeds, since by the time we get to X==Y we have defined both X and Y to be 3.

Arithmetic

The most important operator for doing arithmetic in Prolog is the is operator; this unifies the left-hand term with the evaluated value of the right-hand term.

Comparisons like < and =< (Prolog’s way of saying less-than-or-equal-to) evaluate both sides, and then succeed or fail based on the result of the comparison.

Example

Assume each of the following is a separate query (so that all variables start out unset in each case, and each query is independent of the others):

```
X is 5+2.
```
Succeeds, and sets X = 7 .
```
X is Y*7.
```
Fails, since Y is undefined and so we cannot evaluate Y*7 to a value.
```
Y = 6, X is Y*7.
```
Succeeds, and sets Y = 6, X = 42. The difference from the previous example is that by the time we need to calculate Y*7, we have already defined Y to be 7.
```
1+2 is 2+1.
```
Fails, since is only evaluates the right-hand-side, and the term 1+2 does not unify (cannot be made identical) to the value 3.

(The operator =:= evaluates both sides and checks for equality, but it’s rarely needed.)

Doing Calculations

Newcomers to Prolog may be tempted to write

fac(0) :- 1.
fac(X) :- X * fac(X-1).

but this is totally broken.

In the first line, the right-hand-side of a rule has to be a formula that can be true or false, so we can’t have 1 as a right-hand-side.
In the second line, we also have the problem that Prolog only defines relations (that succeed or fail) and not functions, and multiplying X by the result of a relation makes no sense.

We can express this recursive computation in Prolog, but need to define the relation between the input and the output:

fac(0, 1).  % Input 0 is related to output 1
fac(N, X) :- Nminus1 is N-1,
                fac(Nminus1, Nminus1Factorial),
                X is N * Nminus1Factorial.

We have to be careful to use is in this code to force Prolog to do the arithmetic and give a name to the result; if we just passed N-1 to the recursive call Prolog would start building unevaluated terms like N-1, N-1-1, N-1-1-1, … and these terms would never unify with the number 0 in our base case.