This week we just want to get some more practice with writing and querying knowledge bases, and look a little closer at how Prolog works. In particular, we want to emphasise that Prolog deals with relations and not functions, and demonstrate this by looking at how Prolog deals with arithmetic.
In this section we want to emphasise a few points, some of which you might have come up against in last week's tutorial.
You have probably noticed that Prolog's error messages always refer to
a predicate name along with a number; for example likes/2 in
last week's example. The number given with each predicate is called its
arity.
The arity of a predicate is simply the number of arguments it
takes.
The reason Prolog always refers to the arity is that Prolog allows you to have different predicates with the same name, but different arity. Thus you could define two totally different predicates with the same name but a different number of "parameters"; when you called one of them, Prolog would count the number of arguments, and reference the appropriate definition. It's not really a good idea to do this (as it can be confusing), but it might help explain some seemingly strange errors in your input!
In this section we want to look at how Prolog deals with numbers; an important point here is the difference between functions (as in C) and Prolog's relations.
To date we have been defining our own predicates as we needed them.
As you might expect, many commonly-used predicates are built in to
Prolog, and we can use these in our programs. Because these are part
of the language we can use them like a normal relation (i.e. write
them between their arguments), instead of having to write them before
their arguments. (for the record, the former is called infix,
the latter is called prefix). There are ways of making
your own infix predicates, but we won't worry about this for the moment.
The built-in arithmetical predicates are the obvious ones: <, >, >=, =<, = etc. A simple example of their use would be the following two predicates:
positive(N) :- N>0. non_zero(N) :- N<0 ; N>0.
Note that Prolog's "=" relation is equality (not assignment); it
is the same as the "==" relation in C.
Prolog also has arithmetic operators like +, -, *, / and
also the usual collection of functions like sqrt, exp, cos.
However these do not work exactly as expected!
The important point here is to realise that writing "2+3" in Prolog is not an instruction to carry out the addition (remember, Prolog is not an imperative language). Rather it represents "the addition of 2 and 3". It is thus a completely different term to "1+4", or "3+2", and certainly different from "5*1" etc.
Thus if we have the knowledge base:
prime(2). prime(3). prime(5). ...
The queries "prime(1+1)" or "prime(5*1)" will both fail,
because the terms they contain cannot be unified with any of those in
the knowledge base.
The value of an arithmetic expression is only actually computed when we ask Prolog to compute it - the standard way of doing is to use Prolog's assignment predicate is.
Thus, in the above example, the query "X is 1+1, prime(X)." would succeed, since the is will cause the term 1+1 to be evaluated to 2.
It's worth emphasising this point: in general, the variable used before the is should be unbound; any variables occurring in the arithmetical expression should have a value.
So, to use one of the built-in arithmetic functions, you'd need something like:
| ?- X is sqrt(9), Y is 2 ** 4, Z is floor(3.14). X = 3.0 Y = 16.0 Z = 3
The relations positive and non_zero that
we defined above
represent things which would be regarded as relations in most
languages. However, it's important to remember that in Prolog all
"operations" must be represented as relations - this can seem
a little strange at first.
Suppose we wanted to define a predicate to calculate the minimum value of two numbers. In C/C++, we might write a function of the form:
int minimum(int x, int y) { if (x < y) return x; else return y; }
This function takes two arguments and returns one value. In Prolog we don't' have functions, so this has to be represented as a relation. The first two arguments to the relation will be the input values, the third argument will be the result. Thus we note that:
Thus in Prolog we write:
% minimum(X,Y,Z) is true if Z is the minimum of X and Y minimum(X,Y,X) :- X<Y. minimum(X,Y,Y) :- X>=Y.
We should read a statement of the form "minimum(X,Y,X) :- ..." as saying"the minimum of X and Y is X if ...". Note the way that the two alternatives are expressed as separate clauses in Prolog.
It's a bit like if we insisted that all our functions in C/C++ were to be of type void, and return their result by pointers or reference; thus in C++ we might write*:
void minimum(int x, int y, int& z) { if (x < y) z = x; else z = y; }
Remember also that these predicates cannot be used in expressions like functions; in C/C++ we might write something like "(minimum(x,y) > 0)" to test if the minimum of two numbers is positive, since we know that minimum(x,y) represents a value. You should be very careful not to do this in Prolog, since applying the predicate minimum to something will not give a value. The corresponding Prolog expression is: minimum(X,Y,Z), Z>0.
(a) Factorial: |
| |||||||||||
(b) The Fibonacci function: |
| |||||||||||
(c) Ackermann's function: |
|
Written by James Power