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

• when defining or calling a predicate, you should not put a space between the name of the predicate and the opening bracket - "(" - which follows it.

Comments

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

• nl which moves to a new line on screen
• write(X) which writes X on screen

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).\footnoteThere 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.

• The predicate "N is E" will succeed whenever N is an unbound variable, and E is some arithmetic expression (like 2+3). After it succeeds, N will be assigned the computed value of E.

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.

Some queries:

• N is 1+1.
• N is 1+1, P is N*2, Q is P+Q.
• N is X+1.
• I is I+1.
• I is 6, I is I+1.
• I is 6, J is I+1.

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, we might write a function of the form:

  int min(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:

• In general, a function that takes k arguments will be represented in Prolog as a relation that takes k+1 arguments (the last one being used to hold the result)

Thus in prolog we write:

  % min(X,Y,Z) is true if Z is the minimum of X and Y
  min(X,Y,X) :- X<Y.
  min(X,Y,Y) :- X>=Y.

We should read a statement of the form "min(X,Y,X) :- ..." as saying"the minimum of X and Y is X if ..."

It's a bit like if we insisted that all our functions in C were to be of type void, and return their result by reference; thus we might write:

  void min(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 we might write something like "(min(x,y) > 0)" to test if the minimum of two numbers is positive, since we know that min(x,y) represents a value. You should be very careful not to do this in Prolog, since applying the predicate min to something will not give a value. The corresponding Prolog expression is: min(X,Y,Z), Z>0.

Exercises

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 recursive functions:
   1. Factorial

      fact(0)	=	1
      fact(n)	=	n*fact(n-1),	when n>0

   2. The Fibonacci function

      fib(0)	=	1
      fib(1)	=	1
      fib(n)	=	fib(n-1)+fib(n-2),	when n>1

   3. 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
Revised: 7^th October 1998
Contact: James.Power@may.ie