9 - A Prolog semantics

Summary

Ashcroft and Wadge [4] have criticized effort spent on describing existing programming languages and have suggested a more active, prescriptive role for denotational semantics in designing languages of the future. Accepting some truth in this, this chapter contains a semantics for Prolog. While there are existing Prologs, plural, logic programming is still a research area and a denotational semantics is one way to investigate variations in it.

Prolog [9] is a programming language based on first-order predicate logic. A Prolog program can be thought of in two ways. It can be taken to be a set of logical assertions or facts about a world or some part of a world. This is the declarative semantics of the program. It can also be taken as a set of procedure definitions which gives its procedural semantics.

The declarative semantics are very elegant in that the program stands for some basic facts and certain other facts that logically follow from them. No side-effects or considerations of the order of evaluation are involved. Unfortunately, to make Prolog run and to make it run efficiently, some programs require side-effects such as input–output and the order of evaluation to be taken into account. This can only be understood procedurally.

Here a denotational semantics of a subset of Prolog is given. This defines the backtracking search and unification processes of Prolog. Later the definition is translated into Algol-68 to form an interpreter. Prolog is still a research language and giving a denotational semantics enables it to be compared with other languages in a uniform framework.