42
functional language like ML (Milner, Tofte et al. 1990; Milner and Tofte 1991) or an algebraic
specification language (Bergstra, Heering et al. 1989). For the general level of discussion in
this chapter we shall not need a formal definition of data type, beyond the generic notion of
structured data that must satisfy some additional constraints. We shall generally ignore the
distinction between typesandtype constructors,and the types we shall consider, like se-
quence, or cell, are in fact type constructors (for types like sequence of integers, string-
containing cell, etc.). Type constructors are very general, and correspond closely to the
kinds of generic “container” objects used in many object-oriented designs. This genericity
accounts for the focus on type constructors, since they cover a very wide range of potential
application. While there are many examples of interesting type-specific operations we shall
not consider these in any detail here.
The simplest type of data object is a single cell that can hold some particular value given
some history. There are two sorts of operation that can be defined on such an object. If the
type of the contained data is ignored, only a change-value operation makes sense on a cell.
If the type of the contained data isknown, type-specific operations might apply. For exam-
ple, an integer could be subjected to arithmetic operations that update its value, e.g., incre-
ment, add 20, ordouble.A string might be subjected to operations likechange case, append
text,orstring replacement.Palimpsest does not address the question of representing such
operations, though some extension might be possible.
Once we leave the cell behind, we move into the broader realm of composite data struc-
tures in general. Think of a composite structure as a set of cells with access functions (possi-
bly augmented with extra arguments to serve as addresses within the composite). An access
function returns either another structure, or the contents of a particular cell. A structure
may constrain the relationships of cells in arbitrary ways. For instance, an array might have
a fixed number of cells, accessible only by functions that take addresses in the form of num-
bers within a fixed range.
functional language like ML (Milner, Tofte et al. 1990; Milner and Tofte 1991) or an algebraic
specification language (Bergstra, Heering et al. 1989). For the general level of discussion in
this chapter we shall not need a formal definition of data type, beyond the generic notion of
structured data that must satisfy some additional constraints. We shall generally ignore the
distinction between typesandtype constructors,and the types we shall consider, like se-
quence, or cell, are in fact type constructors (for types like sequence of integers, string-
containing cell, etc.). Type constructors are very general, and correspond closely to the
kinds of generic “container” objects used in many object-oriented designs. This genericity
accounts for the focus on type constructors, since they cover a very wide range of potential
application. While there are many examples of interesting type-specific operations we shall
not consider these in any detail here.
The simplest type of data object is a single cell that can hold some particular value given
some history. There are two sorts of operation that can be defined on such an object. If the
type of the contained data is ignored, only a change-value operation makes sense on a cell.
If the type of the contained data isknown, type-specific operations might apply. For exam-
ple, an integer could be subjected to arithmetic operations that update its value, e.g., incre-
ment, add 20, ordouble.A string might be subjected to operations likechange case, append
text,orstring replacement.Palimpsest does not address the question of representing such
operations, though some extension might be possible.
Once we leave the cell behind, we move into the broader realm of composite data struc-
tures in general. Think of a composite structure as a set of cells with access functions (possi-
bly augmented with extra arguments to serve as addresses within the composite). An access
function returns either another structure, or the contents of a particular cell. A structure
may constrain the relationships of cells in arbitrary ways. For instance, an array might have
a fixed number of cells, accessible only by functions that take addresses in the form of num-
bers within a fixed range.
