[Haskell-cafe] Disadvantages of de Bruijn indicies?

[Stefan O'Rear]

On Fri, May 11, 2007 at 03:10:42PM +0100, Neil Mitchell wrote:
> Hi,
> 
> de Bruijn indicies look quite nice, and seem to eliminate a lot of
> complexity when dealing with free variables:
> http://en.wikipedia.org/wiki/De_Bruijn_index
> 
> So I was wondering, are they suitable for use in a compiler? If so,
> what are their disadvantages/advantages? Is there any particular
> reason that GHC (as an example) doesn't use them in its Core?
> 
> I'm trying to decide if I should use them in my compilers data type -
> and would like some recommendations before I start.

>From what I've heard, the main disadvantage is that they make Core
nigh-impossible to read - which is important because you will spend
much much more time debugging your compiler than writing it.

There is a brief discussion of the tradeoffs in section 2.5 of the
paper "Secrets of the Glasgow Haskell Compiler inliner":

http://research.microsoft.com/~simonpj/Papers/inlining/index.htm

Stefan