Prolog Tutorial 2: Operators and Arithmetic

James Power, 1997.


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.


Some Prolog Details

In this section we want to emphasise a few points, some of which you might have come up against in last week's tutorial.

Arity

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!

Spaces

While we're on the subject, another common source of error in defining a predicate is putting spaces in the wrong place. Basically, Prolog doesn't really mind how you lay out your code (you can add extra spaces and carriage-returns almost anywhere) with one main exception:

Comments

As you write more knowledge bases, you may want to comment them for your own reference; two forms of comment are allowed in Prolog:
  1. The character "%" followed by any sequence of characters up to end of line.
  2. The symbols "/*" followed by any sequence of characters (including new lines) up to "*/"

Simple I/O in Prolog

We'll be looking at I/O in a little more detail in later tutorials, but for the moment you should know about the following predicates:


Arithmetic in Prolog

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.

Built-In Predicates

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.

Arithmetic Operators

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

Some queries:

Each of the following can be entered as a query to Prolog. Try entering them, and make sure you understand Prolog's response in each case: Only two of these are actually valid queries - make sure you understand why.

Defining your own relations

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.


* Note: In the C version of the min function, we'd use pointers rather than reference parameters, so we might phrase the signature as void minimum(int x, int y, int* z). Thanks to Boris Glawe for pointing this out.


Exercises

Define predicates to calculate the following:
  1. the result of adding 1 to a number
  2. the function signum(x) which is x-1 if x>0, and 0 otherwise.
  3. the maximum of two numbers
  4. the maximum of three numbers
  5. the absolute value of a number
  6. The following well-known recursive functions:
    (a) Factorial:
    fact(0) =1
    fact(n) =n*fact(n-1), when n>0
    (b) The Fibonacci function:
    fib(0) =1
    fib(1) =1
    fib(n) =fib(n-1)+fib(n-2), when n>1
    (c) Ackermann's function:
    Ack(0,y) = y+1
    Ack(x,0) = Ack(x-1,1) when x >0
    Ack(x,y) = Ack(x-1,Ack(x,y-1)) when x,y>0


Written by James Power
Released under the GNU Free Documentation License
Last revised: 2 March 2007.