Datatypes in Memory

Abstract. Besides functional correctness, specifications must describe other properties of permissible implementations. We want to use simple algebraic techniques to specify resource usage alongside functional behaviour. In this paper we examine the space behaviour of datatypes, which depends on the representation of values in memory. In particular, it varies according to how much values are allowed to overlap, and how much they must be kept apart to ensure correctness for destructive space-reusing operations. We introduce a mechanism for specifying datatypes represented in a memory, with operations that may be destructive to varying degrees. We start from an abstract model notion for data-in-memory and then show how to specify the observable behaviour of models. The method is demonstrated by specifications of lists-in-memory and pointers; with a suitable definition of implementation, we show that lists-in-memory may be implemented by pointers. We then present a method for proving implementations correct and show that it is sound and, under certain assumptions, complete.