Types are not sets

ABSTRACT

The title is not a statement of fact, of course, but an opinion about how language designers should think about types. There has been a natural tendency to look to mathematics for a consistent, precise notion of what types are. The point of view there is extensional: a type is a subset of the universe of values. While this approach may have served its purpose quite adequately in mathematics, defining programming language types in this way ignores some vital ideas. Some interesting developments following the extensional approach are the ALGOL-68 type system [vW], Scott's theory [S], and Reynolds' system [R]. While each of these lend valuable insight to programming languages, I feel they miss an important aspect of types.Rather than worry about what types are I shall focus on the role of type checking. Type checking seems to serve two distinct purposes: authentication and secrecy. Both are useful when a programmer undertakes to implement a class of abstract objects to be used by many other programmers. He usually proceeds by choosing a representation for the objects in terms of other objects and then writes the required operations to manipulate them.

REFERENCES

• 1: A. van Wijngaarden, Report on the algorithmic language ALGOL 68, Printing by the Mathematisch Centrum, 1969
• 2: {S} Scott, D., "Outline of a Mathematical Theory of Computation," PRG-2, Oxford University.
• 3: {R} Reynolds, J. C., "A Set-Theoretic Approach to the Concept of Type," Argonne National Laboratories, 1969.
• 4: {D} Dahl, O. J., and Hoare, C. A. R., "Hierarchical Program Structure," Structural Programming, Academic Press, 1972.
• 5: James H. Morris, Jr., Protection in programming languages, Communications of the ACM, v.16 n.1, p.15-21, Jan. 1973 [doi>10.1145/361932.361937]
• 6: {W} Wulf, W. A., et. al., "Hydra: the Kernal of a Multiprocessor Operating System," Department of Computer Science, Carnegie Mellon University, June 1973.