Summary

The consequences of completely abandoning the view that every value belongs to one and only one type are profound. One can achieve no more than a partial abandonment, however, unless one also holds that a type is simply a set of values and allow any set of values to serve in the role of a type.

The interpretation of a type as no more than a set of values forces one to conclude that type constructors are simply set operators. This in turn simplifies the resolution of questions about type equivalence and suggests that structural equivalence is appropriate.

Structural equivalence leads to problems when applied to record constructors. Records have also proved troublesome to database designers[6] and have been successfully done away with in DAPLEX[10]. This suggests that records are not ``nice'' constructs and that ``post-Hoare'' programming languages might better off without them.

Another consequence of regarding types as nothing more than sets of values, is that operators take on an independent existence and that the notion of operator inheritance by subtypes thus becomes simple. Also, types can be made into first-class values by treating sets as first class values. This is more intuitive than other approaches[7], but requires implementers to tackle lazy evaluation. Finally, polymorphism and the ability to do type membership tests are automatic consequences of making types equivalent to sets.

In classical Algol-style languages the prevalence of disjoint types and highly restricted mechanisms for introducing subtypes make ``nearly'' static type checking possible. When any set of values can serve as a type, however, it must be accepted that non-trivial run-time type checks will have to be performed in some situations -- typically those situations where the application programmer would have to provide them if the language does not.

Acceptance of non-trivial run-time type checking makes it reasonable to accept furthermore that, in some cases, even the values making up a type will not be known at compile-time. This leads to the very useful concept of a dynamic type that makes it possible to support abstract types in a non-traditional, more natural way, and to integrate concepts from database languages and object-oriented languages into Algol-style languages.

The author has recently designed an Algol-style language that supports and exploits unrestricted type intersection. A prototype version has been in use since early 1989 and our experiences with its expressivity are very positive. The design of the type system of the language is reported in more detail in [12] and the language itself is defined (in under 20 pages) in [11].

The author has little doubt that the active exploration of the design space of languages that allow and exploit unrestricted type intersection will result in some very exiting and powerful new programming languages appearing on the scene.