Open and closed scopes for constrained genericity

AbstractConstrained genericity is an extension of parametric polymorphism, that allows type parameters in polymorphic procedures to be constrained to have certain operations defined over them. It is realized in the Ada and Haskell programming languages, as exemplified by type classes in Haskell. Type classes only allow a single global scope for instances of type classes. This article introduces a type system and a semantics that allows both dynamic and static scoping of such operations to be mixed in a program. Applications include overcoming scoping problems with constrained genericity, enabling program optimizations, and programming with dynamic data structures. Type classes with “open” scope obey the usual semantics for Haskell type classes, based on call-site “type dictionaries”. Type classes with “closed” scope use run-time type descriptions to dispatch to instances. The type system to support this combines operator kinds, refinement kinds and singleton kinds. The system is extended to allow overlapping specialized instance types, in order to support specialized representations for data structures (for example, arrays of integers, arrays of floats and arrays of boxed values). This extension requires the combination of both type dictionaries and run-time type information for type class dispatching