1.1 Introduction

Programming languages can be classified in a variety of ways. One major division is between procedural languages and declarative languages. Procedural languages require the programmer to specify in some detail the steps the program must execute in order to accomplish its intended task. In declarative languages, on the other hand, the programmer provides in the program a definition of the task to be accomplished, but is not concerned with the details of how the computer will use the definition.

Most conventional programming languages (Basic, C, Fortran, Pascal etc.) are procedural. Prolog belongs to the class of declarative programming languages. It gets its name (PROgramming in LOGic) because it is modelled on first order logic and (in principle) requires the programmer to give a logical model of the task to be undertaken. This makes programming in Prolog a rather different experience to programming in a procedural language.

In introducing Prolog, I have followed Pereira and Shieber (1987) in breaking it down into three stages. The first, Database Prolog, is a restricted subset which allows us to exemplify some of the basic ideas. The second, Pure Prolog, is an extension of the first which maintains a purely logical semantics but introduces arithmetic, recursion and lists. The final extension, to Full Prolog, takes us into the range of extra-logical constructs, such as input and output, negation and flow of control.