Dictionaries: lazy or strict type class witnesses?

Add to your list(s) Download to your calendar using vCal

• Tom Schrijvers (K.U. Leuven)
• Friday 15 May 2009, 15:15-15:45
• GS15, Computer Laboratory.

If you have a question about this talk, please contact Dominic Orchard.

Type classes are Haskell’s acclaimed solution to ad-hoc overloading. This talk gives an introductory overview of type classes and their runtime witnesses, dictionaries. It asks the questions whether dictionaries should abide by Haskell’s default lazy evaluation strategy.

Conceptually, a type class is a type-level predicate: a type is an instance of a type class iff it type provides an implementation for overloaded functions. For instance, `Eq a’ declares that type `a’ implements a function `(==) :: a → a → Bool’ for checking equality.

Type classes are used as constraints on type variables, in so-called constrained polymorphic functions. E.g. `sort :: Ord a => [a] → [a]’ sorts a list with any type of elements `a’ that are an instance of the Ord type class, i.e. provide implementations for comparison.

Witnesses for type class constraints are necessary to select the appropriate implementation for the overloaded functions at runtime. For instance, if `sort’ is called with Int elements, the Int comparison must be used, versus say Float comparison for Float elements.

Two forms of witnesses have been considered in the literature, runtime type representations and so-called dictionaries, of which the latter are the most most commonly implementation, e.g. in GHC . Haskell implementations treat dictionaries just like all other data, as lazy values that may potentially consists of non-terminating computations. This way part of the type checker’s work, who has made sure that the dictionaries do exist, is simply forgotten. Is this really necessary? Can performance be gained by exploiting the strict nature of dictionaries?

This talk is part of the Computer Laboratory Programming Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Programming Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• GS15, Computer Laboratory
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.