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.