LHC history

[csabahruska]

Hi,

What was the reason no to use GHC as a Haskell frontend?

Regards,
Csaba

[lemmih]

A previous incarnation of LHC did just that. However, by the time the code has been compiled to Core, GHC has already made a bunch of implementation decisions (eg regarding type-classes). I wanted a clean slate.

[csabahruska]

Can you give some details about GHC design decisions which interfere with GRIN?

[lemmih]

They don't interfere with GRIN, I just don't like that GHC gets to make the decisions. The biggest decision is probably about how type-classes are implemented. GHC uses dictionary passing. LHC, on the other hand, maintains type information at runtime and uses it to do type-based dispatch.

[csabahruska]

I believe that the dictionary approach is not an issue at all if the optimizer framework implements interprocedural Dead Data Elimination. That will eliminate the unused class methods.

[lemmih]

Type-classes by dictionary passing and type-classes by type inspection are fundamentally incompatible. For example, dictionary passing only allows compile-time specialization where type inspection allows run-time specialization. That is, you can look at the types at runtime and dispatch the correct specialized function. Type inspection has a bunch of other benefits as well.

[csabahruska]

The run-time specialization can be done in GRIN level also.

[lemmih]

Yes, LHC does that. But you can't if you let GHC do your desugaring for you. :)

[csabahruska]

I don't see, what's the obstacle?

[lemmih]

How would you recover the needed information from dictionaries? That is, if I give you a function that takes a dictionary, how would you do runtime specialization?

[csabahruska]

Do you mean a dispatch function to select between specialized and generic functions?
Heap Points-To will reveal the overloaded routes. Then an optimization pass would select a subset of heavily overloaded functions to specialize.

[lemmih]

Let's say you have this code:

square :: Num a => a -> a
square a = a+a
{-# SPECIALIZE square :: Int -> Int #-}

For the sake of the argument, assume that 'square' is so large that it won't be inlined anywhere. How would you implement 'square' in GRIN using both dictionary passing and specialization?

My argument is that it's exceedingly difficult (and downright impossible in some cases) to do runtime specialization using dictionaries. Whole-program optimizations are great but they're not magic and cannot un-erase information. Once GHC has erased types, you literally have less information to use in your optimizations.

[csabahruska]

In GRIN square would be compiled naively to a function which uses dictionary. However the HPT would tell that various dictionaries are passed to it at lots of call sites. With function cloning the GRIN optimizer would specialize square to use a specific dictionary, then probably the optimizer would inline the cloned things together and the dead data elimination would specialize the dictionaries.
This is what I expect, but I have to prove it of course. :)
I'm close to reach a working version of GHC frontend for our GRIN implementation. We are planning to do measurements on the effect of dead data elimination + inter-procedural dead code elimination + Boquist GRIN optimizations. We also plan to write a paper on the results.

Maybe I misunderstood your initial assumption about the inliner. If the inliner/cloner does not select the highly overloaded functions, then of course they will not be specialized.
But I believe that it's not the case. If I'm wrong then I'd like to see counter examples, that would enhance my intuition on the topic.

[lemmih]

So you would ignore the SPECIALIZE pragma and trust that the optimizer handles the case? What if the user wrote their own specialized function? And what if there are newtypes involved (which may have the same dictionaries but are specialized in different ways)? What if the functions are too big to be cloned? What if the optimizer isn't smart enough to merge the cloned functions together in a sensible manner? My point is that there are a dozen ways for it to go wrong. In LHC, however, we can guarantee that the specialization /will/ happens (and that it happens efficiently), regardless of code layout, optimization parameters, custom specialized functions, or newtypes.

[csabahruska]

These are real concerns. But I want to analyze/compile real world programs so GHC is the only option for that. (IMHO)
If it turns out that the optimizer need user hints then I'll export the necessary information from GHC.

Currently my modified GHC with the GRIN backend can compile any stack based project. e.g. I compiled Idris compiler and lambdacube-quake3 with it.

[lemmih]

Maybe I misunderstood your initial assumption about the inliner. If the inliner/cloner does not select the highly overloaded functions, then of course they will not be specialized.
But I believe that it's not the case. If I'm wrong then I'd like to see counter examples, that would enhance my intuition on the topic.

Aha! This may be the crux of the argument. This is exactly the behavior in GHC. If a function is not directly used with a specific type, the function will not be specialized. I believe this to be a misfeature. I think a runtime type inspection should guarantee that the function is /always/ specialized when executed over the specific type.