The Expression Problem and a Solution Using Type Classes

February 19, 2008

Pablo Nogueira


The Expression Problem and a Solution Using Type Classes

Time:   11:00am
Location:   Meeting room 302 (Mountain View), level 3

Wadler coined the name Expression Problem for the problem of extending data and functions on that data in modular and type-safe fashion. I have coined the term “Twisted” Expression Problem to the problem of adding to the Expression Problem (sic) the possibility of typing data at the meta-level (by the compiler’s type-checker, not a programmer-defined type checker program). I’ll explain what the previous convoluted and circuitous phrase means. Just want to sound professional here.

Mainstream object-oriented languages unsuccessfully tackle the Expression Problem using inheritance. Bah, mostly rubbish (op. cit. Emilio), so won’t go there much.

Type classes are a nice language mechanism for principled overloading. Surprise: they can be used to represent data in a Church-encoding-like fashion. Surprise: they are modularly and safely extensible, and can be used to solve the Twisted Expression Problem. Surprise: the visitor pattern is the functional homecoming for OO programmers, and guess what, there is a connection to the type class solution. Which? You’ll have to find out yourself.

WARNING: I will make use of inappropriate and impolite language such as “type”, “static type-checking”, “safety”, “extensibility”, and (I know, despicable), functional programming. Apologies for any inconvenience.

PS: To add insult to injury, if time permits I will argue that the best solution would be provided by extensible dependent types, which currently do not exist. Anyone interested?