De Bruijn Indices

Definition

De Bruijn indices provide a notation for the syntax of the $\lambda$-calculus where variable names are replaced by natural numbers. Each index represents the number of binders ($\lambda$) between the variable occurrence and its corresponding binder.

Structure

In this formalization, a $\lambda$-term is defined by the following grammar:

$M,N::=n\mid MN\mid \lambda M$

where $n\in \mathbb{N}$ is an index. An index $0$ refers to the innermost enclosing $\lambda$, while an index $n+1$ refers to the binder that binds the index $n$ in the enclosing scope.

Examples

The following table shows the translation from named terms to De Bruijn terms:

Named Term	De Bruijn Term
$\lambda x.x$	$\lambda 0$
$\lambda x.\lambda y.x$	$\lambda \lambda 1$
$\lambda x.\lambda y.y$	$\lambda \lambda 0$
$\lambda x.\lambda y.\lambda z.(xz)(yz)$	$\lambda \lambda \lambda (20)(10)$

Properties

1. Canonical Representation: Terms that are $\alpha$-equivalent in named notation have identical De Bruijn representations. This eliminates the need for $\alpha$-conversion during computation.
2. Substitution: Implementing $\beta$-reduction requires a shifting operation. When a term is moved under a binder or a binder is removed, free indices within that term must be incremented or decremented to maintain their original references.
3. Implementation: They are widely used in proof assistants like Coq or Agda and in compiler backends to simplify scope management and equality checking.

References

• De Bruijn, N. G. (1972). Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagationes Mathematicae.
• Pierce, B. C. (2002). Types and Programming Languages. MIT Press.

Would you like me to provide the Agda implementation for the lifting and substitution operations on these indices?