1997 | OriginalPaper | Chapter
Relational Semantics of Functional Programs
Authors : Rudolf Berghammer, Burghard von Karger
Published in: Relational Methods in Computer Science
Publisher: Springer Vienna
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.