# Arithmetic expressions

# 3.5. Arithmetic expressions#

In Logic Programming, recursion is the only looping control structure. Consequently, recursive datatypes such as lists can be expressed very naturally. Natural numbers also have a recursive nature: ‘\(0\) is a natural number, and if \(X\) is a natural number, then the successor of \(X\) is also a natural number’. In Prolog, this is expressed as

```
nat(0).
nat(s(X)):-nat(X).
```

Addition of natural numbers is defined in terms of successors:

```
add(0,X,X).
add(s(X),Y,s(Z)):-add(X,Y,Z).
```

The following query asks for the sum of two and three:

```
?-add(s(s(0)),s(s(s(0))),Z).
Z = s(s(s(s(s(0)))))
```

We can also find an \(X\) such that the sum of \(X\) and \(Y\) is \(Z\) (i.e., subtract \(Y\) from \(Z\)):

```
?-add(X,s(s(s(0))),s(s(s(s(s(0)))))).
X = s(s(0))
```

We can even find all \(X\) and \(Y\) which add up to a given sum. Thus, this program is fully declarative. Similarly, multiplication is repeated addition:

```
mul(0,_X,0).
mul(s(X),Y,Z):-mul(X,Y,Z1),add(Y,Z1,Z).
```

There are two problems with this approach to representing and manipulating natural numbers. First, naming natural numbers by means of the constant symbol `0`

and the functor `s`

is very clumsy, especially for large numbers. Of course, it would be possible to write a translator from decimal notation to successor notation, and back. However, the second problem is more fundamental: multiplication as repeated addition is extremely inefficient compared to the algorithm for multiplication of numbers in decimal notation. Therefore, Prolog has built-in arithmetic facilities, which we will discuss now.

Consider the arithmetic expression `5+7-3`

. Prolog will view this expression as the term `+(5,-(7,3))`

, with the functors `+`

and `-`

written as infix operators. We want to *evaluate* this expression, i.e. we want a single numerical value which represents somehow the same number as the expression. A program for doing this would look something like

```
is(V,E1+E2):-
is(V1,E1),is(V2,E2),
fast_add(V1,V2,V).
is(V,E1-E2):-
is(V1,E1,),is(V2,E2),
fast_sub(V1,V2,V).
is(E,E):-
number(E).
```

Here, `fast_add`

and `fast_sub`

represent the fast, built-in procedures for addition and subtraction, which are not directly available to the user. These procedures are **not** reversible: its first two arguments must be instantiated. Therefore, the predicate `is`

will include a test for groundness of its second argument (the arithmetic expression), and will quit with an error-message if this test fails.

Operators#

In Prolog, functors and predicates are collectively called *operators*. An operator is declared by the query `?-op(Priority,Type,Name)`

, where `Priority`

is a number between 0 and 1200 (lower priority binds stronger), and `Type`

is `fx`

or `fy`

for prefix, `xfx`

, `xfy`

or `yfx`

for infix, and `xf`

or `yf`

for postfix. The `x`

and `y`

determine associativity: for instance, `xfx`

means not associative (you cannot write `X op Y op Z`

, but must either write `(X op Y) op Z`

or `X op (Y op Z)`

), `xfy`

means right-associative (`X op Y op Z`

means `op(X,op(Y,Z))`

), and `yfx`

means left-associative (`X op Y op Z`

means `op(op(X,Y),Z)`

). Every special symbol of Prolog, such as ‘`:-`

’ and ‘`,`

’ (conjunction in the body of a clause), is a predefined operator. The interpretation of operators can be visualised by means of the predicate `display`

, which writes a term without operators. For instance, the query `?-display((p:-q,r,s))`

writes `:-(p,','(q,','(r,s)))`

. The extra parentheses are needed because `:-`

binds very weakly.

The `is`

predicate is a built-in feature of Prolog, and is declared as an infix operator. Its behaviour is illustrated by the following queries:

```
?-X is 5+7-3.
X = 9
?-9 is 5+7-3.
Yes
?-9 is X+7-3.
Error in arithmetic expression
?-X is 5*3+7/2.
X = 18.5
```

Tip

Try these queries here in SWISH.

```
% Try these queries here.
```

The last example shows, that arithmetic expressions obey the usual precedence rules (which can be overruled using parentheses). Also, note that the `is`

predicate can handle real numbers.

Prolog also provides a built-in predicate `=`

, but this predicate behaves quite differently from `is`

, since it performs *unification* rather than arithmetic evaluation (see also Section 2.3). The following queries illustrate the operation of `=`

:

```
?-X = 5+7-3.
X = 5+7-3
?-9 = 5+7-3.
No
?-9 = X+7-3.
No
?-X = Y+7-3.
X = _947+7-3
Y = _947
?-X = f(X).
X = f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f
(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(
Error: term being written is too deep
```

The first query just unifies `X`

with the term `5+7-3`

(i.e. `+(5,-(7,3))`

), which of course succeeds. In the second and third query, we try to unify a constant with a complex term, which fails. The fourth query succeeds, leaving `Y`

unbound (`_947`

is an internal variable name, generated by Prolog).

Tip

Try these queries here in SWISH. Is the answer to the last query really as described above?

```
% Try these queries here.
```

The fifth query illustrates that Prolog indeed omits the occur check (Section 2.3) in unification: the query should have failed, but instead it succeeds, resulting in the circular binding { `X`

→ `f(X)`

}. The problem only becomes apparent when Prolog tries to write the resulting term, which is infinite. Just to stress that Prolog quite happily constructs circular bindings, take a look at the following strange program:

```
strange:-X=f(X).
```

The query `?-strange`

succeeds, and since there is no answer substitution, it is not apparent that there is a circular binding involved.

Write a predicate `zero(A,B,C,X)`

which, given the coefficients \(a\), \(b\) and \(c\), calculates both values of \(x\) for which \(ax^2 + bx + c = 0\).

Finally, we mention that Prolog provides a number of other useful arithmetic predicates, including the inequality tests `<`

and `>`

, and their reflexive counterparts `=<`

and `>=`

. For these tests, both arguments should be instantiated to numbers.