Personal tools
You are here: Home Events Variations on Variants

Variations on Variants

— filed under:

  • Lab Lunch
When Mar 14, 2016
from 05:25 PM to 05:25 PM
Add event to calendar vCal

Extensible variants improve the modularity and expressiveness of
programming languages: they allow program functionality to be
decomposed into independent blocks, and allow seamless extension
of existing code with both new cases of existing data types and new
operations over those data types.

This paper considers three approaches to providing extensible
variants in Haskell. Row typing is a long understood mechanism for
typing extensible records and variants, but its adoption would require
extension of Haskell’s core type system. Alternatively, we might
hope to encode extensible variants in terms of existing mechanisms,
such as type classes. We describe an encoding of extensible variants
using instance chains, a proposed extension of the class system.
Unlike many previous encodings of extensible variants, ours does
not require the definition of a new type class for each function that
consumes variants. Finally, we translate our encoding to use closed
type families, an existing feature of GHC. Doing so demonstrates
the interpretation of instances chains and functional dependencies
in closed type families.

One concern with encodings like ours is how completely they
match the encoded system. We compare the expressiveness of our
encodings with each other and with systems based on row types. We
find that, while equivalent terms are typeable in each system, both
encodings require explicit type annotations to resolve ambiguities
in typing not present in row type systems, and the type family
implementation retains more constraints in principal types than does
the instance chain implementation. We propose a general mechanism
to guide the instantiation of ambiguous type variables, show that
it eliminates the need for type annotations in our encodings, and
discuss conditions under which it preserves coherence.

Document Actions