De Bruijn index

• Buddy Allocator
  • de Bruijn列でBSR32をO(1)で実装できる理由

名前を使わずに引数を参照する記法
相対的に何階層外側にあるかを自然数で表記

ex.

• λz. (λy. y (λx. x)) (λx. z x) -> λ (λ 1 (λ 1)) (λ 2 1)
• λx. x -> λ.0

参考文献

• De Bruijn index - Wikipedia