Abstract
This paper presents an elementary model of relational programming as a generalisation of functional programming. We present well-known models of features of functional programming and show one way that they generalise to the relational case. This is achieved by giving a uniform construction of a category of types and relations from a category of types and functions.
Our construction of a relational from a functional calculus is used to discuss data-types and polymorphism in relational languages, and to show how they can be modeled by extensions of functional techniques. We also discuss the class of causal relations that can be implemented particularly efficiently and characterise them.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Bibliography
A. Asperti and G. Longo, Applied category theory: an introduction to categories, types and structures for the working computer scientist, M.I.T. Press, 1991, To appear.
R. Backhouse, An exploration of the Bird-Meertens formalism, Technical Report CS 8810, Department of Computing Science, Groningen University, 1988.
R. Backhouse, P. de Bruin, E. Voermans, and J. van der Woude, A relational theory of datatypes, Proceedings of the Workshop on Constructive Algorithmics, Ameland, The Netherlands, 1990.
J. de Bakker, Semantics and termination of nondeterministic recursive programs, in Automata, Languages and Programming (S. Michaelson and R. Milner, Eds. ), (1976), Edinburgh University Press.
M. Barr, Relational algebra, in the Reports of the Midwest Category Seminar IV, (1970), Springer-Verlag LNM 137.
R. Bird and P. Wadler, Introduction to functional programming, Prentice Hall, 1988.
V. Breazu-Tannen and T. Coquand, Extensional models for polymorphism, Theoretical Computer Science, Volume 59 (1988), Pp. 85–144.
J. Cockett, List-arithmetic distributive categories: locoi, Journal of Pure and Applied Algebra, Volume 66 (1990), Pp. 1–29.
O. de Moor, Categories, relations and dynamic programming, Technical Report PRG-TR-18-90, Programming Research Group, Oxford University, 1990.
P. Freyd and A. Scedrov, Categories, allegories, North Holland, 1990.
C. Hoare and J. He, The weakest prespecification, Technical Report PRG-44, Programming Research Group, Oxford University, 1985.
C. Hoare, J. He, and C. Martin, Pre-adjunctions in order enriched categories, Manuscript, Programming Research Group, Oxford University, 1990.
G. Hutton, A simple guide to the Ruby simulator, Department of Computing Science, University of Glasgow.
G. Hutton, Functional programming with relations, in Functional Programming (G. Hutton, C. Hoist, and S. Peyton-Jones, Eds. ), (1990), Springer-Verlag Workshops in Computer Science.
C. Jay, Extending properties to categories of partial maps, Technical Report ECS-LFCS-90-107, Laboratory for Foundations of Computer Science, 1990.
C. Jay, Tail recursion from universal invariants, in Category Theory and Computer Science, (1991), Springer-Verlag LNCS 530.
G. Jones and M. Sheeran, The study of butterflies, Technical Report PRG-TR- 14–90, Oxford University Computing Laboratory, 1990, to appear, proceedings of the IVth Banff Higher Order workshop.
J. Lambek and P. Scott, Introduction to higher order categorical logic, CUP, 1986.
E. Moggi, Categories of partial morphism and the partial λ calculus, in Category Theory and Computer Science (D. Pitt et al., Ed.), (1985), Springer-Verlag LNCS 240.
E. Moggi, Computational λ-calculus and monads, in Proceedings of Logic in Computer Science, (1989).
D. Murphy, Formal Design of Regular Architectures, in Algorithms and Parallel VLSI Architectures II (P. Quinton et al., Eds. ), (1991), North Holland.
D. Murphy, Type refinement in ruby, in Functional Programming (G. Hutton, C. Hoist, and S. Peyton-Jones, Eds. ), (1990), Springer-Verlag Workshops in Computer Science.
W. Phoa, Two results on set-theoretic polymorphism, in Category Theory and Computer Science, (1991), Springer-Verlag LNCS 530.
R. Seely, Categorical semantics for higher order polymorphic lambda calculus, Journal of Symbolic Logic, Volume 52 (1987), Number 4, Pp. 969–989.
M. Sheeran, Describing and reasoning about circuits using relations, in Proceedings of the workshop on theoretical aspects of VLSI design (J. Tucker et al., Ed. ), (1990), CUP.
D. Spenser, A survey of categorical computation: Fixed points, partiality, combinators… control?, Bulletin of the EATCS, Volume 43 (1991), Pp. 285–312.
E. Stark, Compositional relational semantics for indeterminate dataflow networks, in Category Theory and Computer Science (D. Pitt et al., Ed.), (1989), Springer;Verlag LNCS 398.
A. Tarski, On the calculus of relations, Journal of Symbolic Logic, Volume 6 (1941), Pp. 73–89.
N. Verwer, Categorical semantics as a basis for program transformation, Technical Report RUU-CS-90-38, Department of Computer Science, Utrecht University, 1990.
P. Wadler, Theorems for free!, in Functional Programming and Computer Architecture, (1989), Springer-Verlag LNCS.
G. Wraith, A critique of Hagino’s thesis, Manuscript, Department of Mathematics, University of Sussex, 1988.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1992 British Computer Society
About this paper
Cite this paper
Murphy, D. (1992). A Semantics for Relational Programming. In: Heldal, R., Holst, C.K., Wadler, P. (eds) Functional Programming, Glasgow 1991. Workshops in Computing. Springer, London. https://doi.org/10.1007/978-1-4471-3196-0_19
Download citation
DOI: https://doi.org/10.1007/978-1-4471-3196-0_19
Publisher Name: Springer, London
Print ISBN: 978-3-540-19760-7
Online ISBN: 978-1-4471-3196-0
eBook Packages: Springer Book Archive