Expressiveness of the operation set of a data abstraction

Abstract
In 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, we characterize the expressive power of the operation set by defining two properties for data abstractions - expressive completeness and expressive richness. The operation set of an expressively complete data abstraction is adequate enough to implement all computable functions on its values. An expressively rich data abstraction is expressively complete with an operation set that is rich enough to conveniently extract from a value, all relevant information required to reconstruct the value from scratch. Practical applications of the properties of expressiveness introduced are also discussed.