ド・ブラウン・レベル

出典: フリー百科事典『ウィキペディア(Wikipedia)』

これはこのページの過去の版です。299b69a (会話 | 投稿記録) による 2021年10月12日 (火) 14:31個人設定で未設定ならUTC)時点の版であり、現在の版とは大きく異なる場合があります。

ド・ブラウン・レベル英語: de Bruijn Level)とは、ラムダ計算において、名前を使わずに引数(束縛変数)を参照するための記法である。

解説

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

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

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

参考文献

浜名誠、高階書換え系の停止性のための代数モデル[1]

関連項目