2026-10-19
de_bruijn.rs
enum T { Var(&'static str), Lam(&'static str, Vec<T>) }
use T::*;
fn db<'a>(t: &'a T, env: &mut Vec<&'a str>) -> String {
match t {
Var(x) => env.iter().rev().position(|y| y == x).unwrap().to_string(),
Lam(x, body) => {
env.push(x);
let s: Vec<_> = body.iter().map(|t| db(t, env)).collect();
env.pop();
format!("(λ {})", s.join(" "))
}
}
}
fn main() {
let t = Lam("x", vec![Lam("y", vec![Var("x"), Lam("x", vec![Var("x"), Var("y")])])]);
println!("{}", db(&t, &mut Vec::new()));
}
これは何を出力するでしょうか?
Answer
(λ (λ 1 (λ 0 1))) の1行です。
t は λ計算(lambda calculus)の項 λx. λy. x (λx. x y) を表しています。Lam(x, body) は変数 x を束縛する λ で、body に並べた項を左から順に適用したものがその本体です。db は各変数を、自分を囲む λ を内側から数えたとき、その変数を束縛している λ が何番目か(いちばん内側を0とする)という番号に置き換えます。この番号を De Bruijn インデックス(de Bruijn index)といいます。
env には、いま見ている位置を囲む λ の変数名が外側から順に積まれています。Lam に入るときに名前を積み、本体を変換し終えたら取り除きます。Var では env.iter().rev() が内側から順に名前をたどり、position は最初に一致した位置を、逆順にした列の先頭から数えて返します。逆順の先頭はいちばん内側の λ なので、この位置がそのまま内側から数えた番号です。
最初の Var("x") の時点で env は ["x", "y"] です。内側から y、x の順に見るので、x は1になります。次の Lam("x", ...) に入ると env は ["x", "y", "x"] になり、その中の x は内側の "x" に最初に一致して0になります。同じ名前の外側の λx は、内側の λx に隠されて見えません。y は内側から x、y と見て1です。
同じ名前には同じ番号が付くと読むと、2つの x を同じ番号にしてしまいます。逆に名前が違う x と y が、どちらも1になっています。番号が表すのは名前ではなく、使われている位置から束縛している λ までの距離だからです。