Topological sorting is a classical example in the study of data structures and is often included within introductory programming courses in Computer Science at tertiary level. We shall use the problem to illustrate how a well-defined (and hence mathematical but not necessarily numerical) problem can yield a specification which, after appropriate transformation, gives rise to non-recursive PDL code and subsequently to a procedural program in a high-level language.

Although programs in procedural language are in effect algorithms, recall that the aim of this text is not the development of algorithms per se; and hence the algorithm which emerges at the end of the chapter is a consequence of the way in which we transform the problem specification. Other transformations would imply different algorithms. No value judgements are offered as to the quality of the resultant algorithm but it must be said that many years of programming experience will have had some effect on the way that the specification has been interpreted and subsequently transformed.

Problem formulation

In mathematical terminology the problem may be stated as: To find a linear ordering which is consistent with a given (necessarily acyclic) binary relation on a finite set'. Now whilst this may be fine for a (modern) Mathematician and should also be intelligible to any Computer Scientist who has attended a discrete mathematics course as part of his studies, it does not immediately suggest how we might formulate a proper specification of the process in terms of the fundamental entities at our disposal.

This is an introductory textbook on denotational semantics intended for interested computer scientists, for undergraduates towards the end of their course and for postgraduates beginning theirs. The material has been used in a final-year undergraduate course at the University of Western Australia for some years. The objective is to introduce readers to the range of material, both mathematical and practical, in the subject so that they may carry out simple applications and understand more advanced material.

The mathematical foundations of denotational semantics are covered in sufficient detail to illustrate the fundamental problems in semantic theory that were solved by Scott. The section is self-contained but a background including a computer-science or mathematics course on discrete structures or algebra would be helpful. It can be skipped on a first reading or omitted by a reader prepared to take the foundations on trust.

The remainder of the book covers the use of denotational semantics to describe sequential programming languages. Knowledge of at least one high-level programming language, such as Ada, Algol, C, Modula, Pascal or PL 1, is essential. It is an advantage to be aware of the general features of several languages so as to realize the variety available. Familiarity with compilation, interpretation and functional programming is also a help.

A great deal of emphasis is placed on practical work. The usual notation of denotational semantics is akin to a powerful functional programming language.

Denotational semantics is a formal method for defining the semantics of programming languages. It is of interest to the language designer, compiler writer and programmer. These individuals have different criteria for judging such a method – it should be concise, unambiguous, open to mathematical analysis, mechanically checkable, executable and readable depending on your point of view. Denotational semantics cannot be all things to all people but it is one attempt to satisfy these various aims. It is a formal method because it is based on well-understood mathematical foundations and uses a rigorously defined notation or meta-language.

The complete definition of a programming language is divided into syntax, semantics and sometimes also pragmatics. Syntax defines the structure of legal sentences in the language. Semantics gives the meaning of these sentences. Pragmatics covers the use of an implementation of a language and will not be mentioned further.

In the case of syntax, context-free grammars expressed in Backus–Naur form (BNF) or in syntax diagrams have been of great benefit to computer scientists since Backus and Naur [44] formally specified the syntax of Algol-60. Now all programming languages have their syntax given in this way. The result has been ‘cleaner’ syntax, improved parsing methods, parser-generators and better language manuals. As yet no semantic formalism has achieved such popularity and the semantics of a new language is almost invariably given in natural language.

The typical problem facing a programmer is to write a program which will transform data satisfying some properties or assertions ‘P’ into results satisfying ‘Q’.

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.

There is great variety amongst programming languages in the area of data structures and type checking. It is only possible to deal with some of the more straightforward issues in this chapter.

Some languages, such as BCPL [52], are typeless, or have only one type. All BCPL variables have the type ‘word’. This enables BCPL to rival assembly code in application while being much more readable and concise. There are dangers, however; the compiler cannot detect type errors because there are none.

Languages that do provide types are characterized by the kind of data structures, the time at which types are checked and how much the programmer can define. Simple types, such as integer, stand for basic domains like Int. Structured types – arrays and records – stand for derived domains. There are hard problems, however, in deciding what a programmer-defined type, particularly one defined by possibly recursive equations, stands for – see recent conference proceedings [1, 2, 31]. This is obviously connected with recursive domains (§4.3).

APL [27] is a dynamically typed language. Each constant has a particular type – integer, character or vector or array of one of these. The value currently assigned to a variable therefore has some type, but both the value and the type may change as the program runs. Each APL operator is only applicable to certain types, so it is possible to add 1 to an integer or to a vector of integers but not to a character.