Mathematical formalism
ラムダ 計算は 、ラムダ項の構築とそれらに対する簡約演算からなる正式な数学体系です。ラムダ項の定義は、単に変数、ラムダ抽象、または 関数適用 ですが、正式な説明はやや長くなることがあります。この記事の焦点は、ラムダ計算、特に拡張のない純粋な型なしラムダ計算の完全な定義を提示することです。ただし、説明のために数値と算術演算で拡張されたラムダ計算も使用します。
ラムダ項 ラムダ計算は、特定の形式構文によって定義されるラムダ項 の言語で構成されています 。ラムダ計算の構文は、一部の式を有効なラムダ計算式として定義し、一部の式を無効と定義します。これは、一部の文字列が有効なコンピュータプログラムであり、一部の文字列が無効であるのと同じです。有効なラムダ計算式は「ラムダ項」と呼ばれます。最も単純なラムダ計算では、項は以下の3つの規則のみを使用して構築されます。これらの規則は、すべての構文的に有効なラムダ項を構築するために適用できる 帰納的な定義 を与え、次のような式を生成します。 [1]
(
λ
x
.
λ
y
.
(
λ
z
.
(
λ
x
.
z
x
)
(
λ
y
.
z
y
)
)
(
x
y
)
)
.
{\displaystyle (\lambda x.\lambda y.(\lambda z.(\lambda x.z\ x)\ (\lambda y.z\ y))(x\ y)).}
変数 は パラメータを表す文字または文字列であり、それ自体が有効なラムダ項です。
x
{\textstyle x}
ラムダ 抽象化 は、束縛変数 （λと点/ドット . の間）を入力として受け取り、本体 を返す関数定義です 。抽象化を含む関数の定義は、関数を単に「設定」するだけで、関数を呼び出すことはありません。抽象化は、 単一の入力 xを受け取り、 M を返す 匿名関数 を表します。構文は、 変数 x を 項 M に束縛します。例えば、 は匿名関数 を表す抽象化です 。より具体的には、この関数に という名前を付け 、 と記述することができます が、ラムダ計算を使用する場合、この名前 は不要です。
(
λ
x
.
M
)
{\textstyle (\lambda x.M)}
x
{\displaystyle x}
M
{\textstyle M}
(
λ
x
.
M
)
{\displaystyle (\lambda x.M)}
λ
x
.
(
x
2
+
2
)
{\displaystyle \lambda x.(x^{2}+2)}
x
↦
x
2
+
2
{\displaystyle x\mapsto x^{2}+2}
f
{\displaystyle f}
f
(
x
)
=
x
2
+
2
,
{\displaystyle f(x)=x^{2}+2,}
f
{\displaystyle f}
関数の 適用は 、引数への 関数の適用を表します 。 と はどちら もラムダ項です。関数の適用は、入力 N に対して関数 M を 呼び出してを生成する 動作を表します 。
(
M
N
)
{\textstyle (M\ N)}
M
{\textstyle M}
N
{\textstyle N}
M
{\textstyle M}
N
{\textstyle N}
M
(
N
)
{\displaystyle M(N)}
拡張バッカス・ナウア記法 では 、これは と要約できます 。ここで、変数は 無限集合 から与えられ 、その他の記号はラムダ「 」、ドット「.」、括弧「(」と「)」で構成されます。この文法をより形式的かつ寛容に表現すると、次のようになります。
e
::=
v
∣
(
λ
v
.
e
)
∣
(
e
e
)
{\displaystyle e::=v\mid (\lambda v.e)\mid (e\,e)}
v
{\displaystyle v}
v
1
,
v
2
,
v
3
,
…
{\displaystyle v_{1},v_{2},v_{3},\ldots }
λ
{\displaystyle \lambda }
名前 BNF 説明
表現 < 式 > ::= < 抽象 > | < 適用 > | < 変数 > | < 括弧 > ラムダ項は、抽象化、アプリケーション、変数、または括弧で囲まれた式のいずれかです。
抽象化 匿名関数の定義。
変数リスト < 変数リスト > ::= < 変数 > , < 変数リスト > | < 変数 > カンマで区切られた変数のリスト。
応用 アプリケーション (関数呼び出し) は、2 つ以上の式を連続して実行します。
変数 < 変数 > ::= < アルファ > ( < アルファ > | < 数字 > | '_')*
変数名 (例: x、y、fact、sum、...)
グループ化 括弧で囲まれた式。
ラムダ式の集合は、例えば集合 Λとして帰納的に定義されます。この場合、規則1～3を適用した結果は Λ の要素のみとなります 。最も厳密な意味では、それ以外のものはラムダ項ではありません。つまり、ラムダ項は、これら3つの規則を繰り返し適用することで得られる場合にのみ有効です。正式には、
x が変数の 場合、 x ∈ Λ となります。 x が変数で M ∈ Λ の場合 、 (λ x . M ) ∈ Λ となります。 M 、 N∈Λ ならば 、 ( MN )∈Λです 。 ルール2のインスタンスは抽象化 と呼ばれ、ルール3のインスタンスは アプリケーション と呼ばれます 。 [2]
ここで示した構文に追加の演算を加えることで拡張することもよくあります。例えば、数学定数や演算を表す用語を導入することで、次のような用語の意味を理解できるようになります。 型なしラムダ計算は、異なる種類のデータを区別しないという点で柔軟性があります。例えば、数値を操作する関数があるとします。しかし、型なしラムダ計算では、関数が 真理値 、文字列、その他の数値以外のオブジェクトに適用されることを防ぐ方法はありません。データのエンコーディングによっては、意味をなさない結果になる場合もあれば、意図したとおりに機能する場合もあります。
λ
x
.
x
2
.
{\displaystyle \lambda x.x^{2}.}
自由変数と束縛変数 自由変数と束縛変数 という数学的概念に倣い 、抽象化演算子 は 、抽象化の本体のどこに現れても、その変数を束縛すると言われます。抽象化のスコープに含まれる変数は 束縛されていると言われ、λ x の 部分はしばしば x の 結合子 と呼ばれます 。束縛されていない変数は 自由変数 と呼ばれます。例えば、関数定義は、2つの変数 x と y を含む ラムダ項 として表すことができます 。変数 x はラムダ抽象化によって束縛され、 y は自由です。自由変数 y は まだ定義されていないため、未知数とみなされます。抽象化は構文的に有効な項であり、入力をまだ未知である y に追加する関数を表します 。また、変数は「最も近い」抽象化によって束縛されることにも注意してください。次の例では、 式内の の唯一の出現は、2番目のラムダによって束縛されています。 変数は項の中で自由と束縛の両方で現れることがあります。例えば などです 。
λ
{\displaystyle \lambda }
f
(
x
)
=
x
+
y
{\displaystyle f(x)=x+y}
λ
x
.
(
x
+
y
)
{\displaystyle \lambda x.(x+y)}
λ
x
.
(
x
+
y
)
{\displaystyle \lambda x.(x+y)}
x
{\displaystyle x}
λ
x
.
y
(
λ
x
.
z
x
)
{\displaystyle \lambda x.y(\lambda x.z\ x)}
y
{\displaystyle y}
y
(
λ
y
.
y
)
{\displaystyle y(\lambda y.y)}
より正式には、ラムダ式の 自由変数 と 束縛変数 の集合は、 と 表され、 項の構造の再帰によって次のように定義できます。 [3] [4]
M
{\displaystyle M}
FV
(
M
)
{\displaystyle \operatorname {FV} (M)}
BV
(
M
)
{\displaystyle \operatorname {BV} (M)}
FV
(
M
)
{\displaystyle \operatorname {FV} (M)}
- 自由変数セット
コメント
BV
(
M
)
{\displaystyle \operatorname {BV} (M)}
- バインドされた変数セット
コメント
FV
(
x
)
=
{
x
}
{\displaystyle \operatorname {FV} (x)=\{x\}}
ここでxは変数です。つまり、 の自由変数 は です 。
x
{\displaystyle x}
x
{\displaystyle x}
BV
(
x
)
=
∅
{\displaystyle \operatorname {BV} (x)=\emptyset }
ここでxは変数である
FV
(
λ
x
.
M
)
=
FV
(
M
)
∖
{
x
}
{\displaystyle \operatorname {FV} (\lambda x.M)=\operatorname {FV} (M)\setminus \{x\}}
Mの自由変数だが、 削除された
x
{\displaystyle x}
BV
(
λ
x
.
M
)
=
BV
(
M
)
∪
{
x
}
{\displaystyle \operatorname {BV} (\lambda x.M)=\operatorname {BV} (M)\cup \{x\}}
M の境界変数に x を加えたもの。
FV
(
M
N
)
=
FV
(
M
)
∪
FV
(
N
)
{\displaystyle \operatorname {FV} (M\ N)=\operatorname {FV} (M)\cup \operatorname {FV} (N)}
関数とパラメータからの自由変数の結合
BV
(
M
N
)
=
BV
(
M
)
∪
BV
(
N
)
{\displaystyle \operatorname {BV} (M\ N)=\operatorname {BV} (M)\cup \operatorname {BV} (N)}
関数とパラメータの束縛変数の結合
自由変数を含まない式は 閉じ ていると呼ばれます。閉じたラムダ式はコンビネータとも呼ばれ、 組み合わせ論理 における項と同等です。議論を閉じた項のみに限定することが一般的であり、ラムダ計算のいくつかの表現では閉じた項のみを考慮します。例えば、恒等式を表すラムダ項は 自由変数を持たず、閉じています。
λ
x
.
x
{\displaystyle \lambda x.x}
表記 式が明確な場合は、便宜上、括弧を省略することができます。例えば、最も外側の括弧は常に省略できます— の代わりに です 。ただし、すべての括弧を省略できるわけではありません。例えば、
M
N
{\displaystyle M\ N}
(
M
N
)
{\displaystyle (M\ N)}
λ
x
.
(
(
λ
x
.
x
)
x
)
{\displaystyle \lambda x.((\lambda x.x)x)}
は形式的であり 、したがって抽象的であるが、
λ
x
.
B
{\displaystyle \lambda x.B}
(
λ
x
.
(
λ
x
.
x
)
)
x
{\displaystyle (\lambda x.(\lambda x.x))x}
形式である ため、アプリケーションです。
M
N
{\displaystyle MN}
例1と例2は異なる用語を表しており、括弧の位置のみが異なります。これらはそれぞれ異なる意味を持ちます。例1は関数定義ですが、例2は関数適用です。ラムダ変数 x はどちらの例でもプレースホルダーです。
ここで、例1は 関数 （ は 入力 を持つ 無名関数） を定義しています 。一方、例2は、 （ は N に適用される M です。 は 入力 に適用される ラムダ項です。 ）です。例1と例2はどちらも 恒等関数 （ ） として評価されます 。
λ
x
.
B
{\displaystyle \lambda x.B}
B
{\displaystyle B}
(
λ
x
.
x
)
x
{\displaystyle (\lambda x.x)x}
(
λ
x
.
x
)
{\displaystyle (\lambda x.x)}
x
{\displaystyle x}
M
{\displaystyle M}
N
{\displaystyle N}
M
{\displaystyle M}
(
λ
x
.
(
λ
x
.
x
)
)
{\displaystyle (\lambda x.(\lambda x.x))}
N
{\displaystyle N}
x
{\displaystyle x}
λ
x
.
x
{\displaystyle \lambda x.x}
このような状況でさらに 簡潔 にするために、通常は次の規則が適用されます。
アプリケーションは左結合であると仮定される。代わりに [5] と書くこともできる。
M
N
P
{\displaystyle M\ N\ P}
(
(
M
N
)
P
)
{\displaystyle ((M\ N)\ P)}
抽象化の本体は 可能な限り右に 拡張されます。 つまり、 は であり 、 ではないということです 。言い換えれば、ラムダ抽象化は適用よりも優先順位が低いということです。
λ
x
.
M
N
{\displaystyle \lambda x.M\ N}
λ
x
.
(
M
N
)
{\displaystyle \lambda x.(M\ N)}
(
λ
x
.
M
)
N
{\displaystyle (\lambda x.M)\ N}
抽象化のシーケンスは縮約される： [6] [7] [5] と略される
λ
x
.
λ
y
.
λ
z
.
N
{\displaystyle \lambda x.\lambda y.\lambda z.N}
λ
x
y
z
.
N
{\displaystyle \lambda xyz.N}
すべての変数が1文字の場合、応用部分のスペースは省略できます。MNP の代わりに MNPを 使用 し ます 。 [8]
ラムダ式の意味は、式がどのように変換され、簡約されるかによって定義されます。 [9]
変換には 3 種類あります。
α変換 ：束縛変数（ アルファ ）の変更 β-削減 : 関数をその引数 ( ベータ ) に適用し、関数を呼び出す; η-還元: 外延性 ( イータ )の概念を捉えます 。 また、結果として得られる同値性についても言及します。2 つの式を β 変換して同じ式にできる場合、それらの
式は β 同等であり、α/η 同等性も同様に定義されます。
還元式 （redex）とは、還元可能 な表現（reducible expression） の略で 、いずれかの還元規則によって還元できる部分項を指します。例えば、 における の 置換を表す はβ-還元式です 。 が において自由でない場合 、 はη-還元式です。還元式が還元される式は、その還元式と呼ばれます。前の例を用いると、これらの式の還元式はそれぞれ と となり ます 。
(
λ
x
.
M
)
N
{\displaystyle (\lambda x.M)\ N}
N
{\displaystyle N}
x
{\displaystyle x}
M
{\displaystyle M}
x
{\displaystyle x}
M
{\displaystyle M}
λ
x
.
M
x
{\displaystyle \lambda x.M\ x}
M
[
x
:=
N
]
{\displaystyle M[x:=N]}
M
{\displaystyle M}
α変換 α変換 （ アルファ 変換）は、αリネーミングとも呼ばれ、 [10] により、束縛変数の名前を変更できます。例えば、 のアルファ変換により が 生成されます 。項 と は、 抽象化において束縛されていないため、それ自体ではアルファ同値ではありません。アルファ変換によってのみ異なる項は α同値 と呼ばれ、抽象化において束縛変数の特定の選択は（通常は）重要ではないという直感を捉えています。ラムダ計算では、α同値な項はしばしば同値であるとみなされます。
λ
x
.
x
{\displaystyle \lambda x.x}
λ
y
.
y
{\displaystyle \lambda y.y}
x
{\displaystyle x}
y
{\displaystyle y}
アルファ変換の正確なルールは、必ずしも自明ではありません。まず、抽象化をアルファ変換する場合、名前が変更される変数は、同じ抽象化に束縛されているものだけです。例えば、 のアルファ変換は になる可能性があります が、 になることは ありません 。後者は元の値とは異なる意味を持ちます。これは、プログラミングにおける 変数のシャドウイング の概念に似ています。
λ
x
.
λ
x
.
x
{\displaystyle \lambda x.\lambda x.x}
λ
y
.
λ
x
.
x
{\displaystyle \lambda y.\lambda x.x}
λ
y
.
λ
x
.
y
{\displaystyle \lambda y.\lambda x.y}
第二に、アルファ変換は、変数が異なる抽象化によって捕捉される結果となる場合、不可能です。例えば、 において を に置き換えると となり 、 これは全く同じではありません。De Bruijn 指数 記法では、任意の2つの α 等価項は構文的に同一であり、このような混乱は発生しません。
x
{\displaystyle x}
y
{\displaystyle y}
λ
x
.
λ
y
.
x
{\displaystyle \lambda x.\lambda y.x}
λ
y
.
λ
y
.
y
{\displaystyle \lambda y.\lambda y.y}
例を参照してください:
α変換
λ式
デ・ブルージン表記
コメント
λ
z
.
λ
y
.
(
z
y
)
{\displaystyle \lambda z.\lambda y.(z\ y)}
λ
.
λ
.
(
21
)
{\displaystyle \lambda .\lambda .(21)}
オリジナルの表現。
y を k に正しく名前変更します (k は本文では使用されていないため)
λ
z
.
λ
k
.
(
z
k
)
{\displaystyle \lambda z.\lambda k.(z\ k)}
λ
.
λ
.
(
21
)
{\displaystyle \lambda .\lambda .(21)}
de Brujinの表現には変化なし。
単純にyをzに名前変更します（zは で解放されているので間違いです ）
λ
y
.
(
z
y
)
{\displaystyle \lambda y.(z\ y)}
λ
z
.
λ
z
.
(
z
z
)
{\displaystyle \lambda z.\lambda z.(z\ z)}
λ
.
λ
.
(
1
1
)
{\displaystyle \lambda .\lambda .({\color {Red}1}1)}
z
{\displaystyle z}
捕らえられます。
代替 置換（と 表記）とは、 式中 の変数 の自由な出現箇所をすべて式 に置き換える処理です 。ラムダ計算における項の置換は、項の構造の再帰によって以下のように定義されます（注： x と y は変数、 M と N は任意のλ式です）。
E
[
V
:=
R
]
{\displaystyle E[V:=R]}
V
{\displaystyle V}
E
{\displaystyle E}
R
{\displaystyle R}
x
[
x
:=
N
]
=
N
{\displaystyle x[x:=N]=N}
;を に 置き換える と 、
N
{\displaystyle N}
x
{\displaystyle x}
x
{\displaystyle x}
N
{\displaystyle N}
y
[
x
:=
N
]
=
y
{\displaystyle y[x:=N]=y}
; を に 置き換えた 場合 、 （ ではない ）は残る
x
≠
y
{\displaystyle x\neq y}
N
{\displaystyle N}
x
{\displaystyle x}
y
{\displaystyle y}
x
{\displaystyle x}
y
{\displaystyle y}
(
M
1
M
2
)
[
x
:=
N
]
=
(
M
1
[
x
:=
N
]
)
(
M
2
[
x
:=
N
]
)
{\displaystyle (M_{1}\ M_{2})[x:=N]=(M_{1}[x:=N])(M_{2}[x:=N])}
; 置換はアプリケーションの両側に分配されます
(
λ
x
.
M
)
[
x
:=
N
]
=
λ
x
.
M
{\displaystyle (\lambda x.M)[x:=N]=\lambda x.M}
; 抽象化によって束縛された変数は置換の対象とならない。そのような変数を置換しても抽象化は変更されない。
(
λ
y
.
M
)
[
x
:=
N
]
=
λ
y
.
(
M
[
x
:=
N
]
)
{\displaystyle (\lambda y.M)[x:=N]=\lambda y.(M[x:=N])}
およびの 場合 、抽象化によって束縛されていない変数の置換は、抽象化された変数が 置換項に対して 「 新鮮 」である、つまり、自由変数の中に現れない限り、抽象化の本体で実行されます。
x
≠
y
{\displaystyle x\neq y}
y
∉
F
V
(
N
)
{\displaystyle y\notin FV(N)}
y
{\displaystyle y}
N
{\displaystyle N}
N
.
{\displaystyle N.}
たとえば、 、 などです 。
(
λ
x
.
x
)
[
y
:=
y
]
=
λ
x
.
(
x
[
y
:=
y
]
)
=
λ
x
.
x
{\displaystyle (\lambda x.x)[y:=y]=\lambda x.(x[y:=y])=\lambda x.x}
(
(
λ
x
.
y
)
x
)
[
x
:=
y
]
=
(
(
λ
x
.
y
)
[
x
:=
y
]
)
(
x
[
x
:=
y
]
)
=
(
λ
x
.
y
)
y
{\displaystyle ((\lambda x.y)x)[x:=y]=((\lambda x.y)[x:=y])(x[x:=y])=(\lambda x.y)y}
鮮度条件（ が の自由変数に含まれていないことを要求する ）は、置換によって関数の意味が変わらないようにするために重要です。置換された が 自由であるはずなのに束縛されてしまう状況は、 を捕捉する（capture） と呼ばれます。ラムダ抽象に置換するには、式をα変換する必要がある場合があります。例えば、この置換は 定数関数を 恒等関数 に変換するため誤りです 。正しい置換は、α同値性を用いて束縛変数の名前を変更することです（この場合は ） 。
y
{\displaystyle y}
N
{\displaystyle N}
x
{\displaystyle x}
x
{\displaystyle x}
(
λ
x
.
y
)
[
y
:=
x
]
≠
λ
x
.
(
y
[
y
:=
x
]
)
=
λ
x
.
x
{\displaystyle (\lambda x.y)[y:=x]\neq \lambda x.(y[y:=x])=\lambda x.x}
λ
x
.
y
{\displaystyle \lambda x.y}
λ
x
.
x
{\displaystyle \lambda x.x}
(
λ
x
.
y
)
[
y
:=
x
]
=
(
λ
z
.
y
)
[
y
:=
x
]
=
λ
z
.
(
y
[
y
:=
x
]
)
=
λ
z
.
x
{\displaystyle (\lambda x.y)[y:=x]=(\lambda z.y)[y:=x]=\lambda z.(y[y:=x])=\lambda z.x}
一般に、新鮮さの条件を満たさない場合は、最初に適切な新しい変数を使用してアルファ名前変更を行うことで改善できます。置換は、α同値性まで一意に定義されます。置換の実装のほとんどは、置換中にキャプチャを回避するためにアルファ変換を自動的に使用します。この操作は、 キャプチャ回避置換 と呼ばれます。静的スコープを持つプログラミング言語では、キャプチャ回避置換を使用して、 包含 スコープで 変数のシャドウイングを 注意深く処理することにより、 名前解決 を実装できます。 名前解決を簡単にする ために、ソースプログラムでアルファ名前変更を要求する別の戦略もあります。De Bruijn インデックスを 使用すると、名前の衝突がなくなるため、α変換は不要になります。同様に、 Iota や Jot などのユニバーサル ラムダ関数を使用する場合、変数名は必要ありません。これらの関数は、さまざまな組み合わせで関数を呼び出すことで、任意の関数の動作を作成できます。
β還元 β-縮約 （ ベータ 縮約）は、関数適用の考え方をとらえています。β-縮約は置換によって定義されます。つまり、 のβ-縮約 は です 。β-縮約規則は、形式 の適用が という 項に縮約されることを定めています 。 という表記法は、 β-縮約がに縮約されること を示すために使用されます 。β-縮約は、関数適用（関数呼び出しとも呼ばれる）の考え方をとらえ、仮パラメータ変数を実パラメータ式に置換することを実装します。β-縮約は、 カリー・ハワード同型 を介して、 自然演繹 における 局所縮約性 の概念と同じであると見なすことができます。
(
(
λ
V
.
E
)
E
′
)
{\displaystyle ((\lambda V.E)\ E')}
E
[
V
:=
E
′
]
{\displaystyle E[V:=E']}
(
λ
x
.
t
)
s
{\displaystyle (\lambda x.t)s}
t
[
x
:=
s
]
{\displaystyle t[x:=s]}
(
λ
x
.
t
)
s
→
t
[
x
:=
s
]
{\displaystyle (\lambda x.t)s\to t[x:=s]}
(
λ
x
.
t
)
s
{\displaystyle (\lambda x.t)s}
t
[
x
:=
s
]
{\displaystyle t[x:=s]}
例えば、 任意の に対して が成り立ちます。これは、 が恒等関数であることを示しています。同様に、 は 、 が 定数関数であることを示しています。 の何らかの符号化を仮定すると 、次のβ-縮約が得られます 。
s
{\displaystyle s}
(
λ
x
.
x
)
s
→
x
[
x
:=
s
]
=
s
{\displaystyle (\lambda x.x)s\to x[x:=s]=s}
λ
x
.
x
{\displaystyle \lambda x.x}
(
λ
x
.
y
)
s
→
y
[
x
:=
s
]
=
y
{\displaystyle (\lambda x.y)s\to y[x:=s]=y}
λ
x
.
y
{\displaystyle \lambda x.y}
2
,
7
,
×
{\displaystyle 2,7,\times }
(
(
λ
n
.
n
×
2
)
7
)
→
7
×
2
{\displaystyle ((\lambda n.\ n\times 2)\ 7)\rightarrow 7\times 2}
より正式には、実パラメータに変数名が自由でなく、本体に束縛されている場合にのみ、アルファリネームなしでラムダ抽象化に対してβリダクションを実行できる。 [a]
F
V
(
y
)
∩
B
V
(
b
)
=
{
}
→
(
λ
x
.
b
)
y
=
b
[
x
:=
y
]
{\displaystyle FV(y)\cap BV(b)=\{\}\to (\lambda x.b)\ y=b[x:=y]}
アルファリネームは、 では自由だ が では束縛されている名前を 、この変換の前提条件を満たすように で
リネームするため に使用できます。例を参照してください。
b
{\displaystyle b}
y
{\displaystyle y}
b
{\displaystyle b}
β還元
λ式
デ・ブルージン表記
コメント
(
λ
x
.
λ
y
.
(
λ
z
.
(
λ
x
.
z
x
)
(
λ
y
.
z
y
)
)
(
x
y
)
)
{\displaystyle (\lambda x.\lambda y.(\lambda z.(\lambda x.z\ x)(\lambda y.z\ y))(x\ y))}
(
λ
.
λ
.
(
λ
.
(
λ
.21
)
(
λ
.21
)
)
(
21
)
)
{\displaystyle (\lambda .\lambda .(\lambda .(\lambda .21)(\lambda .21))(21))}
オリジナルの表現。
ナイーブベータ1、
(
λ
x
.
λ
y
.
(
(
λ
x
.
(
x
y
)
x
)
(
λ
y
.
(
x
y
)
y
)
)
)
{\displaystyle (\lambda x.\lambda y.((\lambda x.(x\ y)x)(\lambda y.(x\ y)y)))}
正しい
(
λ
.
λ
.
(
(
λ
.
(
3
2
)
1
)
(
λ
.
(
3
2
)
1
)
)
)
{\displaystyle (\lambda .\lambda .((\lambda .({\color {Blue}3}2)1)(\lambda .(3{\color {Blue}2})1)))}
正しくない
(
λ
.
λ
.
(
(
λ
.
(
1
2
)
1
)
(
λ
.
(
3
1
)
1
)
)
)
{\displaystyle (\lambda .\lambda .((\lambda .({\color {Red}1}2)1)(\lambda .(3{\color {Red}1)}1)))}
x と y は置換でキャプチャされています。
アルファの名前変更内部、x → a、y → b
(
λ
x
.
λ
y
.
(
λ
z
.
(
λ
a
.
z
a
)
(
λ
b
.
z
b
)
)
(
x
y
)
)
{\displaystyle (\lambda x.\lambda y.(\lambda z.(\lambda a.z\ a)(\lambda b.z\ b))(x\ y))}
(
λ
.
λ
.
(
λ
.
(
λ
.21
)
(
λ
.21
)
)
(
21
)
)
{\displaystyle (\lambda .\lambda .(\lambda .(\lambda .21)(\lambda .21))(21))}
ベータ2、
(
λ
x
.
λ
y
.
(
(
λ
a
.
(
x
y
)
a
)
(
λ
b
.
(
x
y
)
b
)
)
)
{\displaystyle (\lambda x.\lambda y.((\lambda a.(x\ y)a)(\lambda b.(x\ y)b)))}
(
λ
.
λ
.
(
(
λ
.
(
32
)
1
)
(
λ
.
(
32
)
1
)
)
)
{\displaystyle (\lambda .\lambda .((\lambda .(32)1)(\lambda .(32)1)))}
x と y がキャプチャされていません。
詳しく見てみると、重要な置換は次のようになります
(
(
λ
x
.
z
x
)
(
λ
y
.
z
y
)
)
[
z
:=
(
x
y
)
]
(blocked - will capture)
(
(
λ
a
.
z
a
)
(
λ
b
.
z
b
)
)
[
z
:=
(
x
y
)
]
(allowed - no capture)
{\displaystyle {\begin{array}{r}((\lambda x.z\ x)(\lambda y.z\ y))[z:=(x\ y)]{\text{(blocked - will capture)}}\\((\lambda a.z\ a)(\lambda b.z\ b))[z:=(x\ y)]{\text{(allowed - no capture)}}\end{array}}}
この例では、
β-リデックスでは、
自由変数は、
FV
(
x
y
)
=
{
x
,
y
}
{\displaystyle \operatorname {FV} (x\ y)=\{x,y\}}
バインドされた変数は、
BV
(
(
λ
x
.
z
x
)
(
λ
y
.
z
y
)
)
=
{
x
,
y
}
{\displaystyle \operatorname {BV} ((\lambda x.z\ x)(\lambda y.z\ y))=\{x,y\}}
単純な β-redex では、式が内部抽象化に置き換えられたときに実際のパラメータの x と y がキャプチャされたため、式の意味が変わりました。 アルファの名前変更により、内部抽象化内の x と y の名前が実際のパラメータ内の x と y の名前と区別されるように変更され、問題が解消されました。
自由変数は、
FV
(
x
y
)
=
{
x
,
y
}
{\displaystyle \operatorname {FV} (x\ y)=\{x,y\}}
バインドされた変数は、
BV
(
(
λ
a
.
z
a
)
(
λ
b
.
z
b
)
)
=
{
a
,
b
}
{\displaystyle \operatorname {BV} ((\lambda a.z\ a)(\lambda b.z\ b))=\{a,b\}}
その後、β-redex は意図した意味に進みます。
η-還元 η-還元（ イータ 還元）は、 が に自由変数として現れない 場合、 を に変換します 。 f が自由変数を持つ場合に η-還元を使用する際の問題は、次の例で示されます。
λ
x
.
(
f
x
)
{\displaystyle \lambda x.(fx)}
f
{\displaystyle f}
x
{\displaystyle x}
f
{\displaystyle f}
削減 ラムダ式 β還元
(
λ
x
.
(
λ
y
.
y
x
)
x
)
a
{\displaystyle (\lambda x.(\lambda y.y\,x)\,x)\,a}
λ
a
.
a
a
{\displaystyle \lambda a.a\,a}
ナイーブη-還元
(
λ
y
.
y
x
)
a
{\displaystyle (\lambda y.y\,x)\,a}
λ
a
.
a
x
{\displaystyle \lambda a.a\,x}
この η 縮小の不適切な使用は、 x を 置換せずに 残すことによって意味を変えます 。
λ
y
.
y
x
{\displaystyle \lambda y.y\,x}
η-縮小は、しばしばその逆関数である η-展開と対になって考えられます 。 η-展開は、 が において 自由に現れない ことを前提として、 から に変換します。この 2 つの処理は合わせて η-変換と呼ばれます。 η-変換は 外延性 [ 12] の概念を表現します。 これは、この文脈では、2 つの関数がすべての引数に対して同じ結果を返す 場合のみ、それらの関数は同じである、というものです。 η-変換は 、カリー・ハワード同型性 を介して、 自然演繹 における 局所完全性 の概念と同じであると見なすことができます 。
f
{\displaystyle f}
λ
x
.
(
f
x
)
{\displaystyle \lambda x.(fx)}
x
{\displaystyle x}
f
{\displaystyle f}
評価と正規化 ラムダ計算は、 Haskell や Standard MLのような 関数型プログラミング 言語の理想化されたバージョンと見なすことができます 。この見方によれば、 β-還元は計算ステップに対応します。このステップは、還元する適用がなくなるまで、追加の β-還元によって繰り返すことができます。評価が終了した場合、結果は β-還元ではそれ以上還元できないラムダ式になります。これは、式の 正規形 と呼ばれます。β-還元ではそれ以上還元できないラムダ式は ベータ正規形 であり、同様に、η-還元でも還元できない場合は ベータ-イータ正規形 です。α-変換によって互いに変換できるすべての正規形は、等しいと定義されます。チャーチ ・ロッサーの定理 により、正規形は、存在する場合、還元が実行される順序（還元 戦略 ）に関係なく、一意です。
しかし、すべてのラムダ式が正規形を持つわけではありません。例えば、項 を考えてみましょう 。ここでは です 。つまり、項 は単一のβ-還元で自身に還元されるため、還元プロセスは決して終了しません。 単純型ラムダ計算 などの 型付き ラムダ計算では、 のような項の構築は許可されない ため、これらのシステムにおける型付けされた項はすべて正規形を持ちます。
Ω
=
(
λ
x
.
x
x
)
(
λ
x
.
x
x
)
{\displaystyle \Omega =(\lambda x.xx)(\lambda x.xx)}
(
λ
x
.
x
x
)
(
λ
x
.
x
x
)
→
(
x
x
)
[
x
:=
λ
x
.
x
x
]
=
(
x
[
x
:=
λ
x
.
x
x
]
)
(
x
[
x
:=
λ
x
.
x
x
]
)
=
(
λ
x
.
x
x
)
(
λ
x
.
x
x
)
{\displaystyle (\lambda x.xx)(\lambda x.xx)\to (xx)[x:=\lambda x.xx]=(x[x:=\lambda x.xx])(x[x:=\lambda x.xx])=(\lambda x.xx)(\lambda x.xx)}
Ω
{\displaystyle \Omega }
注記
^ Barendregt、Barendsen (2000) この形式を呼び出します
公理β : (λx.M[x]) N = M[N]、書き直しは(λx.M) N = M[x := N]、「ここでM[x := N]はMにおけるxの出現ごとにNを代入することを意味する」。 [3] : 7 またM[N/x]とも表記され、「MにおけるxのNの代入」を意味する。 [11]
参考文献
^ Barendregt, Hendrik Pieter (1984), The Lambda Calculus: Its Syntax and Semantics, Studies in Logic and the Foundations of Mathematics, vol. 103 (Revised ed.), North Holland, Amsterdam., ISBN 978-0-444-87508-2 、2004年8月23日にオリジナルからアーカイブ
— 訂正 ^ Barendregt, Hendrik Pieter (1984). ラムダ計算：その構文と意味論. 論理学と数学の基礎研究. 第103巻（改訂版）. 北ホラント. ISBN 0-444-87508-5 。 （訂正） ^ ab Barendregt、ヘンク ; Erik Barendsen (2000 年 3 月)、ラムダ計算入門 (PDF) ^ Barendregt, Henk (1985). 『ラムダ計算 ― その構文と意味論 』 論理学と数学の基礎研究 第103巻. アムステルダム: 北ホラント. ISBN 0444867481 。 ここでは：定義2.1.6、p.24 ^ ab 「結合則の例」Lambda-bound.com . 2012年6月18日 閲覧 。 ^ Selinger, Peter (2008), Lecture Notes on the Lambda Calculus (PDF) , vol. 0804, Department of Mathematics and Statistics, University of Ottawa, p. 9, arXiv : 0804.3434 , Bibcode :2008arXiv0804.3434S
^ 「結合法則の例」Lambda-bound.com . 2012年6月18日 閲覧 。 ^ 「ラムダ式の基本文法」 SoftOption 。 他のシステムでは、並置を適用の意味で用いるため、「ab」は「a@b」を意味します。これは変数の長さが1である必要があることを除けば問題ありません。つまり、「ab」は長さ2の変数1つではなく、2つの変数が並置されていることを意味します。しかし、「firstVariable」のようなラベルは単一の変数を意味するようにしたいため、この並置規則は使用できません。 ^ de Queiroz, Ruy JGB (1988). 「プログラミングの証明理論的説明と縮約規則の役割」. Dialectica . 42 (4): 265– 282. doi :10.1111/j.1746-8361.1988.tb00919.x. ^ Turbak, Franklyn; Gifford, David (2008), プログラミング言語における設計概念 、MIT press、p. 251、 ISBN 978-0-262-20175-9 ^ n ラボ での明示的な置換 ^ Luke Palmer (2010 年 12 月 29 日) Haskell-cafe: η ルールの目的は何ですか? 
![{\displaystyle M[x:=N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2903f0b1ec544a7beb9cdca4dd72aed0e81e3494)
![{\displaystyle E[V:=R]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e80fdc3aba2d511d9bd56c4b92e53ef3360cdda0)
![{\displaystyle x[x:=N]=N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80dbd456f3dfe65b3ba7aed025d3c7252e3e87ec)
![{\displaystyle y[x:=N]=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cba4435cf3a816f4f504e213e25c032f20d8c32d)
![{\displaystyle (M_{1}\ M_{2})[x:=N]=(M_{1}[x:=N])(M_{2}[x:=N])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ab45e60a5e424292620a2f6b3106ebbb107c234)
![{\displaystyle (\lambda xM)[x:=N]=\lambda xM}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ec8379452b69b2813ac4bd4062702f687d80fd1)
![{\displaystyle (\lambda yM)[x:=N]=\lambda y.(M[x:=N])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89dd24135f5382cb8d0bf1a9c570d0b19e420646)
![{\displaystyle (\lambda xx)[y:=y]=\lambda x.(x[y:=y])=\lambda xx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/592caa8aa08c98d5217f7dfec3edcb5cb3521fac)
![{\displaystyle ((\lambda xy)x)[x:=y]=((\lambda xy)[x:=y])(x[x:=y])=(\lambda xy)y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b294b29a663f2b54d066505b5ddafdaab77d635)
![{\displaystyle (\lambda xy)[y:=x]\neq \lambda x.(y[y:=x])=\lambda xx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/500e04490df6994d874bab36740944f8416c7834)
![{\displaystyle (\lambda xy)[y:=x]=(\lambda zy)[y:=x]=\lambda z.(y[y:=x])=\lambda zx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eedaecd736095dabc581cf3f10cbbfa2f2d4ea5d)
![{\displaystyle E[V:=E']}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd4dcacf675aaf9fb5fdb735676b593529e58655)
![{\displaystyle t[x:=s]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c69396d99d4f60dbe54641cf62b9864b0a2251e1)
![{\displaystyle (\lambda xt)s\to t[x:=s]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b3ec6af9a3a97d2362dd9473b3b00f414b5323e)
![{\displaystyle (\lambda xx)s\to x[x:=s]=s}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02262c02953e5da0468ebf98f4b38327229bd4c9)
![{\displaystyle (\lambda xy)s\to y[x:=s]=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de42f8231c1e95fb1556e6aee11c40d0000ea008)
![{\displaystyle FV(y)\cap BV(b)=\{\}\to (\lambda xb)\ y=b[x:=y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3b6460bc4cd65e05ec8334394eced8ccb54ae34)
![{\displaystyle {\begin{array}{r}((\lambda xz\ x)(\lambda yz\ y))[z:=(x\ y)]{\text{(ブロック - キャプチャされます)}}\\((\lambda az\ a)(\lambda bz\ b))[z:=(x\ y)]{\text{(許可 - キャプチャされません)}}\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85f2fbda2ff3882790e0b63491c2491c6e3cda61)
![{\displaystyle (\lambda x.xx)(\lambda x.xx)\to (xx)[x:=\lambda x.xx]=(x[x:=\lambda x.xx])(x[x:=\lambda x.xx])=(\lambda x.xx)(\lambda x.xx)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba84bd0baf6c5c33e59226aa42474b36e3046231)
