Survival of generic-classes in ghc

[Jan-Willem Maessen]

* Language philosophers who are skimming this discussion will want to
  take a look at #### below.

Simon PJ writes:

> One thing that is slowing me down is a design uncertainty: how to
> deal cleanly with constructors.  To write read, show, etc, one needs
> access to the constructor name, fixity etc.  We dance around that a
> little in the paper.  I'm thinking of this design:
...
> -- Con is part of the Generics library, like 1, :*:, :+:
> newtype Con c a = Con a
> 
> class ConCls c where
>    name :: c -> String
>    arity :: c -> Arity
>    ..etc..
> 
> data NilT	-- Phantom types
> data ConsT	-- one per constructor
> 
> instance ConCls NilT where
>    name _ = "Nil"
>    ...etc...
> 
> instance ConCls ConsT wher
>     name _ = "Cons"
>    ...etc...

But you're going to have to keep those ConCls dictionaries somewhere,
which means either:

1) The type Con should existentially quantify over c:
< data Con a = forall c. (ConCls c) => Con a
  [I haven't checked that this is even legal anywhere, but you get the
   idea]

2) Any function which needs the type "c" must carry around a
   dictionary for *each* constructor in the type.  I'm not quite sure
   how to work the typing of the code generic functions in this
   regime, though I'm sure it could somehow be managed.

As long as we're reifying everything in sight, why not simplify the
design problem and reify the constructor dictionaries?

>From my own strawman experiments (this is old code):
> data Constructor t = Constructor CI !t
> 
> data CI = CI Bool String Int [String] [Bool] deriving (Eq)
> -- Op-ness, constructor, fixity, field names, strictnesses of fields

We could do something similar for fields, of course.

There need only be one copy of this info for each data constructor
(and field); it's easy for the compiler to share these.  The type CI
is effectively a representation of the dictionary for ConCls.  The
"Constructor" type the works just like the existentially quantified
example (1).

The drawback?  We need to store the constructor info CI in every
reified constructor.  My suspicion is this will not matter much in
practice.  Compiling generics should be done with one of two sets of
assumptions:
* Generics are a mechanism of convenience.  If you want your code to
  go fast, you should write the code longhand (possibly using an
  overlapping instance for an otherwise generic function/class).  In
  this case, the extra overhead of the constructor info is likely to
  be a drop in the bucket.
* Generics should be specialized at the types at which they are used.
  This might be accomplished by careful inlining of reification
  functions into the bodies of generic methods (or vice versa).
  In this case "Constructor" should vanish.

#######################
On a broader philosophical note:

I'm disturbed by the idea of adding explicit type application and the
like to Haskell.  Haskell language extensions are rapidly becoming a
riotous array of confusing syntax and twisty semantic corners.  From
an experimenter's standpoint, this isn't so bad.  However, many of
these extensions are incredibly useful, and there's a lot of code
relying upon them.  This creates pressure (from both users and
implementors) to immortalize the existing, grubby implementations.
The result?  An incomprehensible, byzantine language.

For example, we now have multiparameter type classes (useful) with
functional dependencies (addressing a vital problem with
multiparameter constraint solving).  Now Simon is wants explicit type
application, kind annotations, and the like. 

There are some things Haskell does very well---algebraic types and
pattern matching are cleaner and more pleasant to use then in ML, and
the class system has proven to be Haskell's most brilliant
distinguishing feature.  I'd like to see solutions to some of the
current problems that build on these strengths.  

I'm not sure if it's possible to get a type language based on
functions and pattern matching in the face of type inference.  Cayenne
makes it clear that one can write type-level code very naturally when
the type language and the value language work the same way.

Similarly, I observe that:

* Views = coercion methods + implicitly-inserted coercions + deforestation

* Generics = reification methods + functions become methods +
             implicitly-inserted reification + deforestation

The two lists are pretty similar, and it might be worth trying to
unify the efforts in some fashion---possibly by breaking down the
functionality into simple pieces.  Here are some possibilities:

* Come up with a coherent story on implicitly-inserted coercions.
  Ideally fromInteger and fromRational would just be specific cases of
  this coherent story.  (The current story is nice and coherent: if
  it's a numeric constant, there's a coercion, otherwise there isn't.)

* Allow patterns to match at multiple types, if those types match
  particular constraints (such as coercability).

These two together might well be enough to give you views.

* Give the deriving mechanism a language-level reading.  Allow
  "deriving"-like clauses outside the context of type declarations.

* Give some way to declare "closure" of a class.  This should be done
  with an eye on abstraction barriers.  Perhaps "closed" classes may
  still be derived (by newtypes, or using the mechanism for generics).

* Make generic functions look like closed classes; possibly this means
  allowing the programmer to write instances as part of the class
  declaration.  

* Perhaps Haskell needs a universal class.  This class would provide
  the reification methods for all [boxed?] data types, and might be a
  place for the implementation to hide (e.g.) type-based GC methods or
  specialized versions of seq.

I'm hoping something along these lines is enough for single-parameter
generics at least.

Much of this work already exists in fragmentary form.  However, in
many cases it's part of attempts at larger mechanisms.  For example,
"views" proposals have suggested using distinguished "view types", and
adding coercions when patterns mention the constructor of a view type.
"Closed" classes were mentioned in the paper on instance resolution at
PoPL last month.  And of course there's lots of good work on generics,
the big problem being that the efforts have become scattershot and
still doesn't seem to fit the rest of the language nicely.  

It's time to reduce the useful mechanisms to their essentials.

-Jan-Willem Maessen
Eager Haskell project