Denotational semantics and domain theory

Abstract

This tutorial is an introduction to denotational semantics and domain theory. For this reason the presentation is not entirely rigorous, with some proofs being omitted and certain simplifying assumptions being made. Instead, the emphasis here has been on satisfying the computational intuition of the reader - dwelling too long on the mathematical aspects of semantic domains is not always satisfying to somebody attempting to ascertain why these structures are relevant to computer science in the first place. Thus, we have started right at the beginning by discussing the concepts of syntax and semantics, and we have attempted to build the mathematical theory of domains upon this computational foundation in a fluid, intuitive and informal manner. In Section 1 and Section 2 we begin with brief descriptions of the syntax and semantics of computer languages, the roles these notions play in computer science, and how they interact in the quest for a formal methodology for computer programming. Section 3 provides an introduction to denotational semantics in particular - this being illustrated by a very simple example. In Section 4 we get down to the business of defining a language which can be recognised as something approximating a real computer language. Here we also endow this language (which can be found in [8]) with a denotational description. We have attempted to explain why the semantics presented for our toy language should seem natural to the reader. In Sections 5-7 we begin to explore the mathematical complexities of domain theory. Our motivation for introducing all this new theory is the search for a denotational description of the 'while'-loop in our example programming language. We conclude in Section 8 with a discussion of parallelism, non-determinism, and the new demands which these complications make of the theory developed up to then. For more advanced presentations of denotational semantics and domain theory, we recommend [3, 4, 6, 7, 10].