Added to Favorites

Popular Searches

Nearby Words

In mathematical logic, the de Bruijn notation is a syntax for terms in the λ calculus invented by the Dutch mathematician Nicolaas Govert de Bruijn (). It can be seen as a reversal of the usual syntax for the λ calculus where the argument in an application is placed next to its corresponding binder in the function instead of after the latter's body.
## Formal definition

## Advantages of the de Bruijn notation

## References

Terms ($M,\; N,\; ldots$) in the de Bruijn notation are either variables ($v$), or have one of two wagon prefixes. The abstractor wagon, written $[v]$, corresponds to the usual λ-binder of the λ calculus, and the applicator wagon, written $(M)$, corresponds to the argument in an application in the λ calculus.

- $M,N,...\; ::=\; v\; |\; [v];M\; |\; (M);N$

Terms in the traditional syntax can be converted to the de Bruijn notation by defining an inductive function $mathcal\{I\}$ for which:

$begin\{align\}\; mathcal\{I\}(v)\; \&=\; v\; mathcal\{I\}(lambda\; v.\; M)\; \&=\; [v];mathcal\{I\}(M)\; mathcal\{I\}(M;N)\; \&=\; (mathcal\{I\}(N))mathcal\{I\}(M)\; end\{align\}$

All operations on λ-terms commute with respect to the $mathcal\{I\}$ translation. For example, the usual β-reduction,

- $(lambda\; v.\; M);N\; longrightarrow\_beta\; M[v\; :=\; N]$

- $(N);[v];M\; longrightarrow\_beta\; M[v\; :=\; N]$.

A feature of this notation is that abstractor and applicator wagons of β-redexes are paired like parentheses. For example, consider the stages in the β-reduction of the term $(M);(N);[u];(P);[v];[w];(Q);z$, where the redexes are underlined:

$begin\{align\}\; (M);underline\{(N);[u]\};(P);[v];[w];(Q);z\; \&\{\; longrightarrow\_beta\; \}\; (M);underline\{(P[u:=N]);[v]\};[w];(Q[u:=N]);z\; \&\{\; longrightarrow\_beta\; \}\; underline\{(M);[w]\};(Q[u:=N,v:=P[u:=N]]);z\; \&\{\; longrightarrow\_beta\; \}$(Q[u:=N,v:=P[u:=N],w:=M]);zend{align}

Thus, if one views the applicator as an open paren ('`(`

') and the abstractor as a close paren ('`)`

'), then the pattern in the above term is '`(()())`

'. De Bruijn called an applicator and its corresponding abstractor in this interpretation partners, and wagons without partners bachelors. A sequence of wagons, which he called a segment, is well balanced if all its wagons are partnered.

In a well balanced segment, the partnered wagons may be moved around arbitrarily and, as long as parity is not destroyed, the meaning of the term stays the same. For example, in the above example, the applicator $(M)$ can be brought to its abstractor $[w]$, or the abstractor to the applicator. In fact, all commutatives and permutative conversions on lambda terms may be described simply in terms of parity-preserving reorderings of partnered wagons. One thus obtains a generalised conversion primitive for λ-terms in the de Bruijn notation.

Several properties of λ-terms that are difficult to state and prove using the traditional notation are easily expressed in the de Bruijn notation. For example, in a type-theoretic setting, one can easily compute the canonical class of types for a term in a typing context, and restate the type checking problem to one of verifying that the checked type is a member of this class. De Bruijn notation has also been shown to be useful in calculi for explicit substitution in pure type systems.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday July 09, 2008 at 02:26:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday July 09, 2008 at 02:26:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.