Computability and implementability issues in abstract data types

AbstractIn a strongly typed system supporting user-defined data abstractions, the designer of a data abstraction ought to be careful in choosing the operations for the abstraction. If the operation set chosen is not expressive enough, it might be impossible or inconvenient to implement certain useful functions on the values of the data abstraction. In this paper, two properties of the operation set of a data abstraction, expressive completeness and expressive richness, are defined to formally characterize the expressive power of the operation set.For an expressively complete data abstraction, the operation set is powerful enough to implement in principle all computable properties of the values, whereas for an expressively rich data abstraction, the operation set can be used to implement the properties in a ‘simple and natural’ fashion. It is shown that if the equality predicate on the values of a data abstraction can be implemented in terms of its operations, then the data abstraction is expressively complete.For expressive richness, we identify a finite set of functions that represent certain basic kinds of manipulations of the values, and require them to be implemented in terms of the operation set as ‘straight line’ programs. The relation between these formal properties and the intuitive notions are considered. We argue that it is important to consider both expressive completeness and expressive richness while designing the operation set of a data abstraction. Practical applications of the properties of expressiveness introduced are also discussed