Open and closed scopes for constrained genericity

Dominic Duggan, John Ophel

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)215-258
Number of pages44
JournalTheoretical Computer Science
Volume275
Issue number1-2
DOIs
StatePublished - 28 Mar 2002

Keywords

  • Constrained genericity
  • Dynamic type dispatch
  • Refinement kinds
  • Type classes

Fingerprint

Dive into the research topics of 'Open and closed scopes for constrained genericity'. Together they form a unique fingerprint.

Cite this