ド・ブラン・インデックス

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ド・ブラン・インデックス(英:De Bruijn Index)とは、ラムダ計算において、名前を使わずに引数束縛変数)を参照するための記法である。オランダ人数学者ニコラース・ホーバート・ド・ブランによって発明された。

解説[編集]

この記法では、それぞれのλでは引数の名前を書かない。引数は、通常の記法でその引数を宣言するλが、何階層外側にあるかを表す自然数の番号で表記する。

例えば、λz. (λy. y (λx. x)) (λx. z x) は λ (λ 1 (λ 1)) (λ 2 1) となる。

ド・ブラン・レベルは絶対的な位置を表すが、ド・ブラン・インデックスは相対的な位置を表す。

参考文献[編集]

De Bruijn, Nicolaas Govert (1972). “Lambda Calculus Notation with Nameless Dummies: A Tool for Automatic Formula Manipulation, with Application to the Church-Rosser Theorem”. Indagationes Mathematicae (Elsevier) 34: 381–392. ISSN 0019-3577. http://alexandria.tue.nl/repository/freearticles/597619.pdf. 

関連項目[編集]