Pointers as a data type

Abstract

The distinction between an abstract data type and an implementation of a data type is not as clear as is commonly thought. A hash table can be used to implement the type bag but few of our colleagues think of a hash table as itself being a data type. Similarly, pointers can be used to give a linked implementation of the data type list, but few of us seem to think of pointers as themselves forming a data type. However we shall give an algebraic specification of a pointer data type which is an abstraction of the representation of pointers in Pascal. The usual linked structures can then be specified abstractly via mutually recursive type specifications. In addition we shall describe a uniform method of constructing implementations of data type specifications via operations on strings.