| Data Refinement and Algebraic Structure (2000) | |||||||||||||||||
Abstract | |||||||||||||||||
| We recall Hoare's formulation of data refinement in terms of upward, downward and total simulations between locally ordered functors from the structured locally ordered category generated by a programming language with an abstract data type to a semantic locally ordered category: we use a simple imperative language with a data type for stacks as leading example. We give a unified category theoretic account of the sort of structures on a category that allow upward simulation to extend from ground types and ground programs to all types and programs of the language. This answers a question of Hoare about the category theory underlying his constructions. It involves a careful study of algebraic structure on the category of small locally ordered categories, and a new definition of sketch of such structure. This is accompanied by a range of detailed examples. We extend that analysis to total simulations for modelling constructors of mixed variance such as higher order types. 1 Introduction ... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||