Records

Most modern programming languages provide some form of record constructor, and most implementations of abstract data types make very heavy use of records. More recently, record-based type extensions have been used to integrate object-oriented programming ideas into a language of the Algol family[8].

The reader may therefore have been surprised by the omission from this proposal of a type constructor for records. The reason for this is that such constructors are very difficult to model as operators resulting in sets of values.

Consider the following (Ada-like) type definition:

type Stack is
record
Top : range 0..100;
Elems : array 1..100 of Integer;
end record;

and the following interpretation of Stack as a set of values:

Stack = {$f$ $|$ $f$ : {Top, Elems} $\to$ R $$ E}
R = {0, ..., 100}
E = {$g$ $|$ $g$ : {1, ..., 100} $\to$ Integer}

Provided that one views a reference to S.Top, where S is a variable of type Stack, as syntactic sugar for $(s())$(Top), and an assignment to S.Top as a partial redefinition of the function returned by $s$, this interpretation of Stack makes it possible to model S as a function and Stack as a set of values.

Note, however, that the constraint that the function returned by $s$ may only return a value between 0 and 100 when applied to Top, is not captured by the model. Another problem is that there is no explicit connection between type Stack and the names Top and Elems.

The latter becomes a significant problem when deciding whether or not type Stack1, below, represents the same set of values as type Stack.

type Stack1 is
record
Top : range 0..100;
Elems : array 1..100 of Integer;
end record;

If the intention is to use Stack as an abstract data type, then the irrelevant detail that Stack values are records must be hidden from the client code. Specifically, the client code must not be able to do something like this:

S : Stack;
...
put(S.Elems[S.Top$-$1]);
put(S.Elems[S.Top]);
S.Top := S.Top $-$ 2;

In conventional languages like Ada this is achieved by hiding the component selector operators, .Top and .Elems, from the client code. Correspondingly, a language based on the functional data model could provide a means of exporting the name, Stack, without also exporting the names Top and Elems.

However, what happens if a client module includes a definition of type Stack1? If type Stack and Stack1 represent the same set of values, the names Top and Elems are not hidden from the client, since they have to be available for use with variables of type Stack1.

Thus to support both records and information hiding in a language based on the functional data model, it is necessary to specify that different applications of the same record constructor yield different sets of values. This is much like saying that 5+6 should yield a different value every time it is evaluated.