Typeclasses  

Typeclasses are really neat

  • They are a major win for separation of concerns. Cross cutting stuff like comparison, equality, pretty-printing, and serialization can be cleanly added retroactively and/or out of band.
  • The dynamic scoping characteristics of typeclasses allow complex parameterized code to be invoked simply so long as it is invoked in an environment that satisfies all constraints.

but...

  • They have a terrible name. The word "class" was already taken, and in many contexts is synonymous with type already, so typeclass sounds meaningless to a portion of the population.
  • It's really hard to translate them into a vObj context without ending up where scala did.
  • In Haskell, typeclasses only specify values. In a language with Scala/Beta style nesting, we'd want to posit types, too.
  • The most successful implementation of typeclasses (Haskell) does not permit named instances.
  • The second most successful implementation of typeclasses (Scala) creates an awkward duality between objects and typeclasses that obscures programmer intent. More below.
  • Haskell's workaround for the lack of named instances (newtype) is clumsy, poorly named, and non-obvious to beginners.

The problem with implicits as typeclasses

  • An implicit parameter only introduces one identifier, which is used to scope all access to members of the implicit.
  • Implicits attack the problem of typeclasses at too low a level--method dictionaries are only one way to implement type classes. Scala has allowed the method-dictionary implementation technique to creep into the language.
  • Implicit objects are values in scala. They must have types, support reflection, etc, so they cannot be erased. This makes typeclasses heavier than need to be.

Dynamic scoping

Dynamic scoping is very powerful and a lot of work has gone into making it safe and reasonable.

Implicit parameters as expressed in scala represent the state of the art in non-research languages, and are also a cornerstone of its implementation of typeclasses.

Unfortunately, typeclasses don't seem to allow for elegant implementation of dynamic scoping.

Separation of typeclasses and objects

I'm relatively convinced at this point that the typeclass system and the object system should be separate in order to conserve programmer intent information. Lets see if that sticks.

A sketch

class BinaryWriter (stream:Stream)
    inherit StreamWrapper stream
    def write (a:A) with BinaryWriteable A
        write stream a
      
typeclass BinaryWriteable A
    def write (a:A) (stream:Stream) : unit
  
instance BinaryWriteable Int
    def write (a:Int) (stream:Stream) : unit
        ((a >> 24) & 0xff) |> byte |> stream.write_byte
        ((a >> 16) & 0xff) |> byte |> stream.write_byte
        ((a >>  8) & 0xff) |> byte |> stream.write_byte
        ((a >>  0) & 0xff) |> byte |> stream.write_byte
        
    def write (a:Int16) (stream:Stream) : unit
        ((a >>  8) & 0xff) |> byte |> stream.write_byte
        ((a >>  0) & 0xff) |> byte |> stream.write_byte
        
    def write (a:Int8) (stream:Stream) : unit
        a |> byte |> stream.write_byte 
        
    def write (a:String) (stream:Stream) : unit
        let bs = UTF8.get_bytes a
        write stream bs.Length
        write bs
        
    def write (b:Array Byte) : unit
        iterate stream.write_byte b

I like this, but it has no named instances and no obvious way to get them.

There is a lot of good stuff here:

  • Typeclasses are different from subtypes and unrelated to objects
  • Programmer intent is very clear
  • All binding is static and can be resolved at compile time, even inlined

A more mature sketch

abstract concept Eq a
    def (x:a) == (y:a) : Bool

concept Eq_Int : Eq int 
    def x == y = builtin.int_equals x y

concept Eq_Inverted_Int : Eq int
    def x == y = builtin.int_equals x y |> not

variant ComparisonResult = LessThan
                         | EqualTo
                         | GreaterThan

concept Comparison a
    def cmp (x:a) (y:a) : Comparison

concept Comparison_Int : Comparison Int
    def cmp (x:Int) (y:Int) = match x - y with
                                  | x st x < 0 -> LessThan
                                  | x st x > 0 -> GreaterThan
                                  | _          -> EqualTo

def my_equals (x:a) (y:a) : Bool
    requires Eq a
    x == y

concept Eq_Pair (a,b) : Eq (a,b)
    requires Eq a, Eq b
    def (x1,y1) == (x2,y2) = x1 == x2 && y1 == y2

my_equals 1 2
(my_equals with Eq_Inverted_Int) 1 2

// requires means that call sites of my_equals must search their dynamic scope
// and discover an implicit module that conforms to 'Eq a'
//
// if multiple modules conform, the most specific one is chosen. if this choice is ambiguous then an error is
// signaled during compilation.

This solves the named instances problem, doesn't turn typeclass instances into values like scala's approach, and is crystal clear as to programmer intent.

Additionally, Eq_Pair is suitably elegant and this scheme seems to support a clean encoding of haskell-style numeric and collections hierarchies.

I don't love my_equals with Eq_Inverted_Int, though. I wonder if dynamic scoping re-introduction would be better. Something like:

prefer Eq_Inverted_Int
    my_equals 1 2

Or alternately, without the scoping behavior

prefer Eq_Inverted_Int
my_equals 1 2

I suppose it could also be a low-priority left associating operator like:

my_equals 1 2 with Eq_Inverted_Int

or

my_equals 1 2 preferring Eq_Inverted_Int
Comments powered by Disqus