TY - JOUR
T1 - Open and closed scopes for constrained genericity
AU - Duggan, Dominic
AU - Ophel, John
PY - 2002/3/28
Y1 - 2002/3/28
N2 - Constrained 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.
AB - Constrained 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.
KW - Constrained genericity
KW - Dynamic type dispatch
KW - Refinement kinds
KW - Type classes
UR - http://www.scopus.com/inward/record.url?scp=0037187384&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037187384&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(01)00129-3
DO - 10.1016/S0304-3975(01)00129-3
M3 - Article
AN - SCOPUS:0037187384
SN - 0304-3975
VL - 275
SP - 215
EP - 258
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -