Desugaring instances

[Max Bolingbroke]

2009/3/5 Simon Peyton-Jones <simonpj at microsoft.com>:
> Guys
>
> I've been struggling with how to desugar instance declarations for some time.  It's been going round and round in my head, but without reaching a fixed point.  Ganesh's message (below) made me realise an additional problem with the current "solution".
>
> So I thought I'd take an hour to articulate the issues and invite you all to help me.
>
> Here's my writeup:
>        http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/DesugaringInstances
>
> Can you look, and see if you can think of a good way to go?

Might this be another option? Desugar the instance as:

{{{
Rec {
  dCList :: C a -> C [a]
  dCList d_a = letrec {
	         d_as = DC opfl opgl
                 opfl = opF_aux d_a
                 opgl = $dmopG d_as
               } in d_as

  opF_aux :: C a -> a -> Int
  opF_aux d_a = let { d_as = dCList d_a } in
                \xs -> case xs of
                     []     -> 0
                     (y:ys) -> opF d_a y + opF d_as ys
}
}}}

I.e. make sure the let binding the list dictionary is outside the
lambda. You still have that recursive calls via the dictionary become
direct recursion:

{{{
opF_aux d_a = let { d_as = dCList d_a } in
                \xs -> case xs of
                     []     -> 0
                     (y:ys) -> opF d_a y + opF d_as ys
=
opF_aux d_a = letrec {
	             d_as = DC opfl opgl
                 opfl = opF_aux d_a
                 opgl = $dmopG d_as
               } in \xs -> case xs of
                     []     -> 0
                     (y:ys) -> opF d_a y + opF d_as ys
=
opF_aux d_a = \xs -> case xs of
                     []     -> 0
                     (y:ys) -> opF d_a y + opF_aux d_a ys
}}}

To prevent reconstruction of the dictionary in general, I think that
CSE needs to be able to do:

f x = ... f x ...
=>
f x = letrec n = ... n ...
        in n

We've discussed this transformation before, in the context of arity
improvement. I'm not sure it's a good idea to rely on the
infrequently-run CSE transformation to get your dictionaries right,
however. This scheme also fails if the user turns on -fdicts-cheap
(but then they probably deserve it :-).

Cheers,
Max