[Haskell-cafe] Disadvantages of de Bruijn indicies?

[Neil Mitchell]

Hi

Thanks for all the responses, I'm busy reading through them.

I'm still trying to decide whether I should use them or not. They
complicate things, are less intuitive than names. But on the other
hand, the language I'm working in is untyped and has only letrec.
These things make binding errors easier to occur, and harder to
detect.

Thanks for the helpful throughts,

Neil


On 5/13/07, Stefan Holdermans <stefan at cs.uu.nl> wrote:
> 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