Programming Language Theory

Maintained by Steven Shaw and contributors

Module Systems


Modular Type Classes

Modular Type Classes - the original paper
by Derek Dreyer, Robert Harper, and Manuel M.T. Chakravarty.

I found the paper kind of tough going but I recall that presentation gives a really good intuition about it. View via Google Docs

Extract of the SML code from the presentation/paper

The authors note that to make these “type classes” convenient in SML, you’d need to add implicit parameters (ala Scala - this is after Odersky’s “poor man’s type classes” but I’m not sure if they were inspired by it here).

A related paper with Stefan Wehr: Stefan further developed theses ideas in his thesis with a Java extension.

Scott Kilpatrick (working on “modules” for Haskell — a better package system AFAIK). This is Backpack for Haskell/GHC.

Scott’s revelation when he finds the “modular type classes” work

MixML — ML module system inspired by Scala/Odersky. Really like the look of this compared to OO-style mixin composition in Scala.

My understanding is the ML-style modules (i.e. modules from SML and OCaml) use a limited form of dependent typing. i.e. they are like records/structs with type members (in addition to fun/val members). They are not first-class like they are in Scala but special functions which operate on modules called functors (not to be confused with fmap-Functors or Applicative Functors). These module functors are parameterised modules.

Bruno C. d. S. Oliveira

Type classes as objects and implicits

Bruno Oliveira went on to write a paper about “implicits” with some other folks.

The Implicit Calculus: A New Foundation for Generic Programming

The idea is to study the “implicits” as a separate language feature that should be considered by language designers, or in their words “This calculus isolates and formalizes the key ideas of Scala implicits and provides a simple model for language designers interested in developing similar mechanisms for their own languages.”.

Martin Odersky

Odersky introduced implicit parameters to Scala in version 2.0. He explained how that gets you to “type classes” at this talk:

and again (more formally) in 2010:

    Type classes as objects and implicits

George Kuan

Modular type classes show-stopper? “In contrast, since the type of x is universally quantified, the canonical instance of Num a must be determined dynamically (i.e. passed in as an argument).”

Modular type classes and deriving

Orphan instances

It seems that Haskell’s Type Classes do find instances by linking only. i.e. instances are automatically exported/imported from the defining module (+ any recursively imported modules when importing).

“Partial Revelation feature of Modula-3 which causes similar problems like Haskell’s type class instances” Link to partial Revelation is broken. This might be a good substitute

IMO this is much better solved with “normal” scoping rules (including implicit definitions).