[Haskell-cafe] Disadvantages of de Bruijn indicies?

[Stefan Holdermans]

Neil,

> 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.

De Bruijn indices are used within Epigram, or at least they used to  
be. Maybe the Epigram people can inform you about their experiences.  
Anyway, Conor and James' Haskell Workshop paper on manipulating  
syntax that involves both free and bound variables [1] is really nice  
and could perhaps be of interest to you.

Cheers,

   Stefan

[1] Conor McBride and James McKinna. Functional pearl: I am not a  
number—I am a free
variable. In Proceedings of the 2004 ACM SIGPLAN Haskell Workshop,  
Snowbird, Utah,
USA, September 22, 2004, pages 1–-9. ACM Press, 2004.
http://portal.acm.org/citation.cfm?id=1017472.1017477