Relational Semantics of Functional Programs

The natural meaning of a program written in a functional language like Lisp or ML is a (possibly partial) function. Functions are relations, and this chapter is a gentle introduction to the idea of regarding functional programs as elements of a relational algebra. Using relations rather than functions we avoid the complexity introduced by artificial bottom elements denoting undefinedness. Relations are also natural candidates for modelling non-determinate or set-valued functions. However, the main reason for using relations is that they can be calculated with so well. Using equational reasoning for functional programs, we can construct proofs that are intuitive, memorable and machine-checkable. One basic ingredient of functional programs — composition of functions — is a built-in operator of the relational calculus. Other control constructs as well as concrete data must be translated into the language of relations. We shall attempt to do this in a modular fashion, treating one construct at a time.