A Tour Through the Programming Choices: Semantics and Applications

The discipline of programming, as Edsger Dijkstra would call it, has provided a formal basis for the study of programs where choices are not necessarily deterministic. That is, despite reservations from pioneers, like Tony Hoare, about the inclusion of nondeterministic behaviour in a program. For over 65 years, nondeterminism has played an important role in modelling and reasoning about programs. Moreover, there are at least two major flavours: angelic and demonic. Further programming choices, such as preferential and probabilistic, have been proposed to capture other important phenomena, for example, in the context of cyber-physical systems, distributed systems, and cryptography. In this chapter, we provide a critical account of these programming choices and their semantics, and discuss their applications. Our account focuses mainly on denotational semantics, and in particular relational models, as is fitting in honour of Jim Woodcock. We discuss approaches based on, or inspired by, weakest preconditions semantics and alphabetised relations, as found in the Unifying Theories of Programming (UTP). They are at the core of the semantics of notations such as Z and Circus, and extensions to deal with time and probabilities. Some of the ideas discussed here have been developed in close collaboration with Jim.