Video Talk: Haskell Type Constraints Unleashed

Unfortunately, due to the air travel disruption in Europe in April I was unable to fly to Japan to attend FLOPS 2010 to present my paper on extensions to Haskell's type constraints system. Fortunately my inability to attend provided motivation to record a video talk. See below for links to the video and to the paper.

• High quality (470.3MB MPEG4)


• Medium quality (277.6MB MPEG4)
  (If you have any problems playing the video files, I recommend VLC a great, cross-platform media player that plays almost everything.)


• Presentation Slides


• Streaming version @ Vimeo
  

  Haskell Type Constraints Unleashed from Dominic Orchard on Vimeo

  
  


• Paper


• Technical Report


• Prototype Implementation

Dictionaries: lazy or eager type class witnesses

I gave a talk at the Cambridge computer lab on May 15, 2009:

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?

You can get the slides here.