(sec: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
```{swish} swish:3.5.0
```
Addition of natural numbers is defined in terms of successors:
```{swish} swish:3.5.1
---
query-id: swishq:3.5.1-1 swishq:3.5.1-2
query-text: ?-add(s(s(0)),Y,s(s(s(0)))).
---
```
The following query asks for the sum of two and three:
```{swish-query} swishq:3.5.1-1
?-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$):
```{swish-query} swishq:3.5.1-2
?-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:
```{swish} swish:3.5.2
---
inherit-id: swish:3.5.1
---
```
+++
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
```Prolog
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.
```{infobox}
---
title: 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:
```Prolog
?-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.
```{swish} swish:3.5.added
```
````
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 {numref}`sec:2.3`). The following queries illustrate the operation of `=`:
```Prolog
?-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?
```{swish} swish:3.5.added2
```
````
+++
The fifth query illustrates that Prolog indeed omits the occur check ({numref}`sec: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:
```pProlog
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.
```{exercise} ex:3.9
```
+++
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.