ラムダ計算

ラムダ抽象化が分解された。 $\lambda$ 関数の開始を示します。 $x$ は入力パラメータです。 $M$ ドット区切り文字で区切られた本文です。 $.$ 入力パラメータから。

{\displaystyle \lambda } — ラムダ抽象化が分解された。 $\lambda$ 関数の開始を示します。 $x$ は入力パラメータです。 $M$ ドット区切り文字で区切られた本文です。 $.$ 入力パラメータから。

数理論理学において、ラムダ計算（ λ計算とも表記される）は、変数束縛と置換を用いて関数の抽象化と適用に基づく計算を表現する形式体系である。本稿の主題である型なしラムダ計算は、汎用機械、すなわち任意のチューリングマシンをシミュレートできる（そしてその逆も可能な）計算モデルである。これは、数学者アロンゾ・チャーチが1930年代に数学の基礎に関する研究の一環として導入したものである。チャーチは1936年に論理的に一貫性のある定式化を発見し、1940年にそれを文書化した。

意味

ラムダ計算は、形式構文によって定義されるラムダ項の言語と、それらの項を操作するための変換規則のセットから構成されます。BNFでは、構文は次のようになります。 $e::=x\mid \lambda x{\text{.}}e\mid e\,e,$ 変数 $x,y,z$ 無限個の名前の範囲。用語 $M,N,t,s,e,f$ すべてのラムダ項にわたる範囲。これは次の帰納的定義に対応します。

変数 $x$ は有効なラムダ式です。
抽象化とはラムダ項のことである $(\lambda x{\text{.}}t)$ どこ $t$ はラムダ式であり、抽象化の本体と呼ばれ、 $x$ は抽象化のパラメータ変数です。
アプリケーションはラムダ項です $(t\,s)$ どこ $t$ そして $s$ ラムダ式です。

ラムダ項は、以下の3つの規則を繰り返し適用することで得られる場合に構文的に有効です。便宜上、ラムダ項を記述する際に括弧を省略できる場合が多くあります。詳細は「ラムダ計算の定義 § 表記法」を参照してください。

ラムダの用語では、何らかの囲み関数のパラメータではない変数の出現は、 $\lambda$ は無料であると言われています。 $x$ 学期中 $M$ 束縛されている $\lambda x{\text{.}}M$ . 内の他の変数の任意の自由な出現 $M$ 自由のまま $\lambda x{\text{.}}M$ 。

例えば、この用語では $x\,y$ 、両方 $x$ そして $y$ 無料で発生します。 $(\lambda x{\text{.}}x\,y)$ 、 $y$ 無料ですが、 $x$ 本体（つまりドットの後）は自由ではなく、（パラメータに）束縛されていると言われます。 $y$ 無料です $(\lambda x{\text{.}}x\,y)$ 、それは $(\lambda y{\text{.}}\lambda x{\text{.}}x\,y)$ 2 回出現します $x$ で $(\lambda y{\text{.}}(\lambda x{\text{.}}x\,y)\,x)$ ―一方は束縛され、もう一方は自由である。

$\operatorname {FV} (M)$ は自由変数の集合です $M$ つまり、自由変数として出現する変数 $M$ 少なくとも一度は。帰納的に以下のように定義できる。

$\operatorname {FV} (x)=\{x\}$
$\operatorname {FV} (M_{1}M_{2})=\operatorname {FV} (M_{1})\cup \operatorname {FV} (M_{2})$
$\operatorname {FV} (\lambda x{\text{.}}M)=\operatorname {FV} (M)\backslash \{x\}$

表記法 $M[x:=N]$ キャプチャ回避置換を表す：置換 $N$ 自由出現ごとに $x$ で $M$ 変数キャプチャを回避しながら。^{[ a ]}この操作は、以下のように帰納的に定義されます。

$x[x:=N]=N$ ; $y[x:=N]=y$ もし $y\neq x$ 。
$(M_{1}M_{2})[x:=N]=(M_{1}[x:=N])(M_{2}[x:=N])$ 。
$(\lambda y{\text{.}}M)[x:=N]$ $(\lambda y{\text{.}}M)[x:=N]$ 3つのケースがあります。
- もし $y=x$ 、 $\lambda x{\text{.}}M$ （ $x$ 拘束されている（変更なし）。
- もし $y\notin \operatorname {FV} (N)$ 、 $\displaystyle \lambda y.(M[x:=N])$ 。
- もし $y\in \operatorname {FV} (N)$ 、最初のαリネーム $\lambda y{\text{.}}M$ に $\lambda y'{\text{.}}M[y:=y']$ と $y'$ 名前の衝突を避けるために新たに作成し、その後上記の手順を続けます。 $\lambda y'{\text{.}}M[y:=y'][x:=N]$ と $y'\notin \operatorname {FV} (M)\cup \operatorname {FV} (N)$ 。

ラムダ項を同等のラムダ項に還元することを可能にする「等価性」と「還元」の概念がいくつか存在する。^{[ 3 ]}

α変換は、抽象化における束縛変数の特定の選択は（通常）重要ではないという直感を捉えています。 $y\notin \operatorname {FV} (M)$ すると、その条件は $\lambda x{\text{.}}M$ そして $\lambda y{\text{.}}M[x:=y]$ アルファ等価とみなされ、 $\lambda x{\text{.}}M\equiv _{\alpha }\lambda y{\text{.}}M[x:=y]$ 同値関係は、この規則によって生成されるラムダ項に関する最小の合同関係です。例えば、 $\lambda x{\text{.}}x$ そして $\lambda y{\text{.}}y$ これらはアルファと等価なラムダ項である。
β還元規則は、β還元、形式の適用について述べている。 $(\lambda x{\text{.}}t)s$ 、次の項に簡略化されます。 $t[x:=s]$ [ ^b^]例えば、すべて^の $s$ 、 $(\lambda x{\text{.}}x)s\to x[x:=s]=s$ これは、 $\lambda x{\text{.}}x$ まさにアイデンティティです。同様に、 $(\lambda x{\text{.}}y)s\to y[x:=s]=y$ これは、 $\lambda x{\text{.}}y$ 定数関数です。
η変換は外延性を表現し、変換を行う $\lambda x{\text{.}}fx$ そして $f$ いつでも $x$ 無料には表示されません $f$ ラムダ計算に関する多くの解説では、しばしば省略されている。

還元式(redex)とは、還元規則のいずれかによって還元できる部分項を指します。例えば、 $(\lambda x{\text{.}}M)\,N$ は置換を表現するβ-レデックスである $N$ のために $x$ で $M$ . redex が還元される式をその還元式と呼び、 $\lambda x{\text{.}}M\,N$ は $M[x:=N]$ 。

説明と応用

ラムダ計算はチューリング完全であり、つまり、あらゆるチューリングマシンをシミュレートするために使用できる普遍的な計算モデルです。^[⁴^]その名前の由来であるギリシャ文字のラムダ（λ）は、関数内の変数を束縛することを示すためにラムダ式とラムダ項で使用されます。

ラムダ計算は、型なしまたは型ありのいずれかです。型付きラムダ計算では、関数は、与えられた入力の「型」のデータを受け入れることができる場合にのみ適用できます。型付きラムダ計算は、型なしラムダ計算よりも厳密に弱いです。型なしラムダ計算は、型なしラムダ計算よりも表現できるものが少ないという意味で、この記事の主な主題です。一方、型付きラムダ計算では、より多くのことを証明できます。たとえば、単純型付きラムダ計算では、すべての評価戦略はすべての単純型付きラムダ項に対して終了するという定理があります^{[ 5 ]} 。一方、型なしラムダ項の評価は終了する必要はありません（下記参照）。型付きラムダ計算が数多く存在する理由の一つは、型なしラムダ計算でできることの多くを実現しつつ、ラムダ計算に関する強力な定理を証明できる能力を放棄したくないという願望があるからだ。

ラムダ計算は、数学、哲学^{[ 6 ]} 、言語学^{[ 7 ]}^{[ 8 ]}、コンピュータ科学^{[ 9 ]}^{[ 10 ]}など、さまざまな分野で応用されています。ラムダ計算は、プログラミング言語の理論の発展において重要な役割を果たしてきました。関数型プログラミング言語はラムダ計算を実装しています。ラムダ計算は、圏論における現在の研究テーマでもあります^[¹¹^]。

歴史

ラムダ計算は、数学の基礎に関する研究の一環として、1930年代に数学者アロンゾ・チャーチによって導入されました。^[¹²^]^[^c^]元のシステムは、1935年にスティーブン・クリーネとJB・ロッサーがクリーネ・ロッサーのパラドックスを提唱した際に、論理的に矛盾していることが示されました。^[¹³^]^[¹⁴^]

その後、1936年にチャーチは計算に関連する部分だけを分離して発表し、現在では型なしラムダ計算と呼ばれているものを発表した。^{[ 15 ]} 1940年には、計算能力は劣るものの論理的に一貫性のあるシステムも導入し、これは単純型付きラムダ計算として知られている。^{[ 16 ]}

プログラミング言語との関係が明確になった1960年代までは、ラムダ計算は単なる形式体系に過ぎませんでした。リチャード・モンタギューをはじめとする言語学者たちが自然言語の意味論に応用したおかげで、ラムダ計算は言語学^{[ 17 ]とコンピュータ科学}^[¹⁸^]の両方で確固たる地位を築き始めました。

λ記号の由来

チャーチがギリシャ文字ラムダ（ $\lambda$ ラムダ計算における関数抽象化の表記法として ) が用いられるようになったのは、おそらくチャーチ自身による説明が矛盾していたことが一因であろう。CardoneとHindley（2006）によれば、次のようになる。

ところで、チャーチはなぜ「 $\lambda$ 「？[1964年のハラルド・ディクソン宛の未発表の手紙]の中で、彼はそれが「 ${\hat {x}}$ 「ホワイトヘッドとラッセルによってクラス抽象化に使用され、最初に修正された」 ${\hat {x}}$ " に " $\land x$ 「関数抽象とクラス抽象を区別し、そして変更する」 $\land$ " に " $\lambda$ 印刷のしやすさを考慮して。
この起源は[Rosser, 1984, p.338]でも報告されている。一方、晩年、チャーチは2人の質問者に、その選択はもっと偶然だったと語った。象徴が必要で、 $\lambda$ たまたま選ばれただけだ。

ダナ・スコットも様々な公開講演でこの問題を取り上げています。^{[ 19 ]} スコットは、かつてラムダ記号の起源についてチャーチの元教え子で義理の息子であるジョン・W・アディソン・ジュニアに質問したところ、アディソンは義父に絵葉書を送ったと述べています。

チャーチ教授へ
ラッセルはイオタ演算子を、ヒルベルトはイプシロン演算子を持っていました。なぜあなたはラムダを演算子として選んだのですか？

スコットによれば、チャーチの返答は、ハガキに「イーニー、ミーニー、マイニー、モー」という注釈を添えて返送することだけだった。

モチベーション

計算可能な関数は、コンピュータ科学と数学における基本的な概念です。ラムダ計算は、計算の性質を形式的に研究するのに役立つ、計算のためのシンプルな意味論を提供します。ラムダ計算は、その意味論をシンプルにする2つの簡略化を取り入れています。最初の簡略化は、ラムダ計算では関数を「匿名」に扱い、明示的な名前を付けないということです。たとえば、関数

\operatorname {square\_sum} (x,y)=x^{2}+y^{2}

匿名形式で書き直すと次のようになります

(x,y)\mapsto x^{2}+y^{2}

（これは「タプル」と読みます） $x$ そして $y$ マッピング先 ${\textstyle x^{2}+y^{2}}$ 「) ^{[ d ]}同様に、関数

\operatorname {id} (x)=x

匿名形式で書き直すと次のようになります。

x\mapsto x

入力は単純にそれ自身にマッピングされます。^{[ d ]}

2つ目の簡略化は、ラムダ計算では単一の入力の関数のみを使用するという点です。例えば、2つの入力を必要とする通常の関数は、 ${\textstyle \operatorname {square\_sum} }$ 関数は、単一の入力を受け取り、出力として別の関数を返す同等の関数に書き換えることができ、その関数もまた単一の入力を受け取ります。たとえば、

(x,y)\mapsto x^{2}+y^{2}

再加工して

x\mapsto (y\mapsto (x^{2}+y^{2}))

この手法はカリー化と呼ばれ、複数の引数を取る関数を、それぞれが単一の引数を取る関数の連鎖に変換する。

機能の適用 ${\textstyle \operatorname {square\_sum} }$ 関数を引数 (5, 2) に渡すと、すぐに

{\textstyle ((x,y)\mapsto x^{2}+y^{2})(5,2)}

{\textstyle =5^{2}+2^{2}}

{\textstyle =29}

、

一方、カレー風味バージョンの評価にはもう1つのステップが必要となる。

{\textstyle {\Bigl (}{\bigl (}x\mapsto (y\mapsto x^{2}+y^{2}){\bigr )}(5){\Bigr )}(2)}

{\textstyle =(y\mapsto 5^{2}+y^{2})(2)}

// 定義

x

使用されてきた

5

内部表現において。これはβ還元に似ています。

{\textstyle =5^{2}+2^{2}}

// 定義

y

使用されてきた

2

これもまた、β還元と同様である。

{\textstyle =29}

同じ結果にたどり着く。

ラムダ計算では、関数は「第一級の値」とみなされるため、関数は入力として使用することも、他の関数からの出力として返すこともできます。例えば、ラムダ項 $\lambda x.x$ 恒等関数を表す。 $x\mapsto x$ 。さらに遠く、 $\lambda x.y$ 定数関数を表す $x\mapsto y$ 常に返す関数 $y$ 入力に関係なく。関数に対して作用する関数の例として、関数合成は次のように定義できます。 $\lambda f.\lambda g.\lambda x.(f(gx))$ 。

正規形と合流

β還元はα変換まで合流的であることが示せる（つまり、2つの正規形が、一方を他方にα変換できる場合に等しいとみなされる）。チャーチ・ロッサーの定理によれば、与えられたラムダ項から始まり、最終的に終了する還元ステップの任意の特定のシーケンスは、同じβ正規形を生成する。しかし、書き換え規則としてのβ還元による型なしラムダ計算は、強く正規化も弱く正規化もせず、 Ωのような正規形を持たない項が存在する。

個々の項について考えると、強正規化項と弱正規化項はいずれも一意の正規形を持つ。強正規化項については、どのような縮約戦略を用いても必ず正規形が得られるが、弱正規化項については、一部の縮約戦略では正規形を見つけられない場合がある。

データ型のエンコード

基本的なラムダ計算は、次のサブセクションi、ii、iii、および§ ivで示されているように、算術、ブール値、データ構造、および再帰をモデル化するために使用できます。

ラムダ計算における算術

ラムダ計算における自然数の定義方法はいくつかありますが、最も一般的なのはチャーチ数であり、これは次のように定義できます。

0 := λ f .λ x . x

1 := λ f .λ x . f x

2 := λ f .λ x . f ( f x )

3 := λ f .λ x . f ( f ( f x ))

などなど。あるいは、関数に複数の非カリー化引数を許可する別の構文を使用することもできます。

0 := λ fx . x

1 := λ fx . f x

2 := λ fx . f ( f x )

3 := λ fx . f ( f ( f x ))

チャーチ数とは、高階関数です。これは、引数が1つの関数fを受け取り、別の引数が1つの関数を返します。チャーチ数nは、関数f を引数として受け取り、 fのn乗合成、つまり関数f をn回自身と合成したものを返す関数です。これはf ⁽ⁿ⁾と表記され、実際にはfのn乗(演算子として考えた場合) です。f ( ⁰⁾は恒等関数として定義されます。関数の合成は結合法則を満たすため、単一の関数fのこのような繰り返し合成は、指数法則f ⁽^m⁾ ∘ f ⁽ⁿ⁾ = f ⁽^m+n⁾および( f ⁽ⁿ⁾ ) ⁽^m⁾ = f ⁽^m*n⁾の2 つの法則に従います。これが、これらの数が算術に使用できる理由です。（チャーチのオリジナルのラムダ計算では、ラムダ式の仮引数は関数本体に少なくとも一度は出現する必要があり、そのため上記の0の定義は不可能だった。）

プログラムの解析によく用いられるチャーチ数nを考える一つの方法は、「 n回繰り返す」という命令として捉えることです。例えば、以下で定義するPAIR関数とNIL関数を用いると、空のリストから始めて、「別のx要素を先頭に追加する」という命令をn回繰り返すことで、すべてxに等しいn個の要素からなる（連結）リストを構築する関数を定義できます。ラムダ項

λ n .λ x . n (PAIR x ) NIL

チャーチ数nとxが与えられたとき、 n個のアプリケーションのシーケンスを作成する

ペアx (ペアx ...(ペアx NIL)...)

繰り返す内容や、その繰り返される関数が適用される引数を変化させることで、非常に多様な効果を実現できる。

チャーチ数nを受け取り、与えられた関数fをさらに1回適用することで、そのn+1の後継数を返す後継関数を定義できます。ここで、( nfx )は「xから始まるfのn回の適用」を意味します。

SUCC := λ n .λ f .λ x . f ( n f x )

fのm番目の合成とfのn番目の合成を組み合わせると、 fのm + n番目の合成が得られるので、f ⁽^m⁾ ∘ f ⁽ⁿ⁾ = f ⁽^m+n⁾となり、加算は次のように定義できます。

プラス := λ m .λ n .λ f .λ x。m f ( n f x )

PLUSは、2つの自然数を引数として受け取り、自然数を返す関数と考えることができます。

プラス2 3

そして

5

これらはベータ同値なラムダ式です。数値にmを加えることは、後続演算をm回繰り返すことで実現できるため、別の定義は次のようになります。

プラス' := λ m .λ n。m成功n ^{[ 20 ]}

同様に、( f ⁽ⁿ⁾ ) ⁽^m⁾ = f ⁽^m*n⁾に従って、乗算は次のように定義できます。

MULT := λ m .λ n .λ f . m ( n f ) ^{[ 21 ]}

したがって、チャーチ数の乗算は、関数としてのそれらの合成に他ならない。

MULT' := λ m .λ n。m (プラスn ) 0

mとnを掛け合わせることは、nを0から始めてm回繰り返し足すことと同じだからである。

べき乗とは、ある数をそれ自身と繰り返し掛け合わせることであり、関数としては、教会数とそれ自身を繰り返し合成することに相当する。そして、教会数とはまさに繰り返し合成のことなのである。

POW := λ b .λ n . n b ^{[ 1 ]}

あるいは、ここでも、

POW' := λ b .λ n。n (マルチb ) 1

簡単に言うと、

POW'' := λ b .λ n .λ f。nbf

しかしそれは、すでに上で述べたPOWのイータ展開版にすぎません。

2 つの式PRED (SUCC n ) = nおよびPRED 0 = 0で指定される前任者関数は、かなり複雑です。

PRED := λ n .λ f .λ x。n (λ g .λ h . h ( g f )) (λ u . x ) (λ u . u )

can be validated by showing inductively that if T denotes (λg.λh.h (gf)), then T⁽ⁿ⁾(λu.x) = (λh.h(f⁽ⁿ⁻¹⁾(x))) for n > 0. Two other definitions of PRED are given below, one using conditionals and the other using pairs. With the predecessor function, subtraction is straightforward. Defining

SUB := λm.λn.n PRED m,

SUB mn yields m − n when m > n and 0 otherwise.

Logic and predicates

By convention, the following two definitions (known as Church Booleans) are used for the Boolean values TRUE and FALSE:

TRUE := λx.λy.x

FALSE := λx.λy.y

Then, with these two lambda terms, we can define some logic operators (these are just possible formulations; other expressions could be equally correct):^[22]

AND := λp.λq.pqp

OR := λp.λq.ppq

NOT := λp.p FALSE TRUE

IFTHENELSE := λp.λa.λb.pab

We are now able to compute some logic functions, for example:

AND TRUE FALSE

≡ (λp.λq.pqp) TRUE FALSE →_β TRUE FALSE TRUE

≡ (λx.λy.x) FALSE TRUE →_β FALSE

and we see that AND TRUE FALSE is equivalent to FALSE.

述語とは、ブール値を返す関数です。最も基本的な述語はISZEROで、引数が教会数0の場合はTRUE を返し、それ以外の教会数の場合はFALSE を返します。

ISZERO := λ n。n (λ x .FALSE) TRUE

次の述語は、最初の引数が2番目の引数以下であるかどうかを判定します。

LEQ := λ m .λ n .ISZERO (SUB m n )、

また、m = n はLEQ m nかつLEQ n mの場合に成り立つので、数値の等価性を表す述語を簡単に構築できます。

述語が利用可能であること、および上記のTRUEとFALSEの定義により、ラムダ計算で「if-then-else」式を簡単に記述できます。たとえば、前任関数は次のように定義できます。

PRED := λ n。n (λ g .λ k .ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0) 0

これは、n (λ g .λ k .ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0)がn > 0 のadd n − 1 関数であることを帰納的に示すことで検証できます。

ペア

ペア（2要素タプル）は2つの値をカプセル化し、2つの値を渡すハンドラを必要とする抽象化によって表現されます。FIRSTはペアの最初の要素を返し、SECONDは2番目の要素を返します。

ペア := λ x .λ y .λ f . f x y

FIRST := λ p。p (λ x .λ y . x )

SECOND := λ p。p (λ x .λ y . y )

連結リストは、空リストを表すNIL、または要素（いわゆるヘッド）とそれよりも小さいリスト（テール）のペアのいずれかになります。述語NULLは、 NILの場合はTRUEを返し、空でないリストの場合はFALSEを返します。

NIL := λ f .TRUE

NULL := λ p。p (λ x .λ y .FALSE)

あるいは、NIL := FALSEの場合、構造( l (λ h .λ t .λ z . ... h ... t ...) _on_nil_)により、明示的な NULL テストは不要になります。

NIL := λ x .λ y . y

NULL := λ l。l (λ h .λ t .λ z .FALSE) TRUE

ペアの使用例として、( m , n )を( n , n + 1)にマッピングするシフトおよびインクリメント関数は次のように定義できます。

Φ := λ p .PAIR (SECOND p ) (SUCC (SECOND p ))

Ψ := λ fp .PAIR (SECOND p ) (f (SECOND p ))

これにより、先行関数の最も分かりやすいバージョンを提供できます。

PRED := λ n .FIRST ( n (Ψ SUCC) (PAIR 0 0))

= λ nfx .FIRST ( n (Ψ f ) (PAIR xx ))

定義を代入し、結果として得られる式を簡略化すると、簡潔な定義が得られる。

= λ nfx。n (λ rab . rb ( fb )) (λ ab . a ) xx

= λ nfx。n (λ rij . j ( rjf )) (λ ij . x ) II

= λ nfx。n (λ rij . i ( rjj )) (λ ij . x ) I f

= λ nfx。n (λ ri . i ( rf )) (λ i . x ) I

（ここでI := λ x . x）明らかに元の状態に戻ります。

追加のプログラミング技術

ラムダ計算には、数多くのプログラミング慣用表現が存在します。これらの多くは、もともとラムダ計算をプログラミング言語のセマンティクスの基盤として用いるという文脈で開発されたものであり、実質的にラムダ計算を低レベルプログラミング言語として利用しています。いくつかのプログラミング言語にはラムダ計算（あるいはそれに非常によく似たもの）が断片として含まれているため、これらの手法は実際のプログラミングでも利用されていますが、その場合、難解あるいは馴染みのないものとして認識される可能性があります。

名前付き定数

ラムダ計算では、ライブラリは事前に定義された関数の集合という形をとります。これらの関数はラムダ項としては単なる特定の定数です。純粋なラムダ計算には名前付き定数の概念はありません。なぜなら、すべての原子ラムダ項は変数だからです。しかし、定数の名前として変数を分けておき、抽象化を用いてその変数を本体に束縛し、その抽象化を意図した定義に適用することで、名前付き定数を持つことをエミュレートできます。したがって、M （別のラムダ項、「メインプログラム」）でN（明示的なラムダ項）を意味するためにfを使用するには、次のように記述できます。

(λ f . M ) N

著者は、上記をより直感的な順序で記述できるようにするために、 let、^[^e^]などの構文糖衣を導入することがよくあります。

f = N をMに代入する

このような定義を連鎖させることで、ラムダ計算の「プログラム」を、0個以上の関数定義と、それらの関数を用いたプログラムの本体を構成する1つのラムダ項として記述することができる。

このletの注目すべき制約は、名前f をN内で参照できないことです。なぜなら、N は抽象化束縛fのスコープ外であり、そのスコープはMだからです。つまり、letを使用して再帰関数定義を記述することはできません。letrec ^[^f^]という構成を使用すれば、抽象化束縛fのスコープにNとMの両方が含まれる再帰関数定義を記述できます。あるいは、 Yコンビネータにつながるような自己適用を使用することもできます。

再帰と不動点

再帰とは、関数が自身を呼び出すことです。このような関数を表す値とはどのようなものでしょうか。定義が自身の中で自身を参照するように、何らかの方法で自身の中で自身を参照する必要があります。この値が値によって自身を含む場合、無限のサイズにならなければならず、それは不可能です。再帰をネイティブにサポートする他の表記法では、定義の中で関数を名前で参照することでこの問題を克服しています。ラムダ計算では、そもそも項に名前がなく、引数の名前、つまり抽象化のパラメータしかないため、これを表現することはできません。したがって、ラムダ式は引数として自身を受け取り、対応するパラメータの名前を介して自身（のコピー）を参照することができます。実際に自身を引数として呼び出した場合は、これはうまく機能します。たとえば、 (λ x . x x ) E = ( EE )は、 Eが再帰呼び出しを表現するために本体内でパラメータを自身に適用する抽象化である場合に再帰を表現します。このパラメータは値としてEを受け取るため、その自己適用は再び同じ（EE）になります。

具体的な例として、階乗関数F( n )を考えてみましょう。これは次のように再帰的に定義されます。

F( n ) = 1 (n = 0 の場合)、それ以外の場合はn × F( n − 1)。

この関数を表すラムダ式では、パラメータ（通常は最初のパラメータ）はラムダ式自体を値として受け取るものと想定されるため、最初の引数としてラムダ式自体を呼び出すと再帰呼び出しになります。したがって、再帰を実現するには、自己参照を意図した引数（ここでは「s」と呼ばれ、「self」または「self-applying」を連想させる）を、関数本体内の再帰呼び出し箇所で常に自身に渡す必要があります。

E := λ s . λ n .(1, if n = 0; else n × ( s s ( n −1)))

ssn = F n = EE n が成り立つので、 s = E となり、

F := (λ x . x x ) E = EE

そして私たちは

F = EE = λ n .(1, n = 0 の場合; それ以外の場合n × (EE ( n −1)))

ここで、ssはアプリケーション(EE)の結果内で同じ(EE)となり、呼び出しに同じ関数を使用することが再帰の定義です。自己アプリケーションはここで複製を実現し、関数のラムダ式を引数値として次の呼び出しに渡します。これにより、パラメータ名sで参照できるようになり、自己アプリケーションs sを介して必要に応じて何度も呼び出され、その都度ラムダ項F = EEが再作成されます。

アプリケーションは、名前検索と同様に、追加の手順となります。遅延効果も同様です。F全体を最初から内部に保持するのではなく、次の呼び出しまで再作成を遅延させることで、内部に 2 つの有限ラムダ項Eが存在し、必要に応じて後で動的に再作成されることが可能になります。

この自己適用アプローチは問題を解決しますが、各再帰呼び出しを自己適用として書き直す必要があります。書き直しを必要としない汎用的な解決策を求めています。

G := λ r . λ n .(1, if n = 0; else n × ( r ( n −1)))

r x = F x = G r x を保持するため、 r = G r =: FIX G および

F := FIX G ただし FIX g = ( rただしr = g r ) = g (FIX g )

したがって、 FIX G = G (FIX G) = (λ n .(1, n = 0 の場合; それ以外の場合はn × ((FIX G) ( n −1))))

再帰呼び出しを表す最初の引数を持つラムダ式（ここではG）が与えられた場合、固定小数点コンビネータFIXは、再帰関数（ここではF ）を表す自己複製ラムダ式を返します。自己複製は作成時にあらかじめ設定されており、呼び出されるたびに実行されるため、関数を明示的に自身に渡す必要はありません。したがって、呼び出し時に元のラムダ式（FIX G）が自身の中で再作成され、自己参照が実現されます。

実際、このFIX演算子には多くの定義が存在し、その中で最も単純なものは次のとおりです。

Y := λ g .(λ x . g ( x x )) (λ x . g ( x x ))

ラムダ計算において、Y gはg の不動点であり、次のように展開されます。

Y g

~> (λ h .(λ x . h ( x x )) (λ x . h ( x x ))) g

~> (λ x . g ( x x )) (λ x . g ( x x ))

~> g ((λ x . g ( x x )) (λ x . g ( x x )))

<~ g ( Y g )

さて、引数nに対して階乗関数を再帰的に呼び出すには、単に( Y G) nと呼び出せばよい。例えば、n = 4 の場合、次のようになる。

( Y G) 4

~> G ( Y G) 4

~> (λ r .λ n .(1, if n = 0; else n × ( r ( n −1)))) ( Y G) 4

~> (λ n .(1, if n = 0; else n × (( Y G) ( n −1)))) 4

~> 1、4 = 0 の場合。それ以外の場合は 4 × (( Y G) (4−1))

~> 4 × (G ( Y G) (4−1))

~> 4 × ((λ n .(1, if n = 0; else n × (( Y G) ( n −1)))) (4−1))

~> 4 × (1、3 = 0 の場合。それ以外の場合は 3 × (( Y G) (3−1)))

~> 4 × (3 × (G ( Y G) (3−1)))

~> 4 × (3 × ((λ n .(1, if n = 0; else n × (( Y G) ( n −1)))) (3−1)))

~> 4 × (3 × (1、2 = 0 の場合。それ以外の場合は 2 × (( Y G) (2−1))))

~> 4 × (3 × (2 × (G ( Y G) (2−1))))

~> 4 × (3 × (2 × ((λ n .(1, if n = 0; else n × (( Y G) ( n −1)))) (2−1))))

~> 4 × (3 × (2 × (1、1 = 0 の場合。それ以外の場合は 1 × (( Y G) (1−1)))))

~> 4 × (3 × (2 × (1 × (G ( Y G) (1−1)))))

~> 4 × (3 × (2 × (1 × ((λ n .(1, if n = 0; else n × (( Y G) ( n −1)))) (1−1)))))

~> 4 × (3 × (2 × (1 × (1, if 0 = 0; else 0 × (( Y G) (0−1))))))

~> 4 × (3 × (2 × (1 × (1))))

~> 24

再帰的に定義された関数はすべて、追加の引数を持つ再帰呼び出しを包含する、適切に定義された高階関数（関数とも呼ばれる）の不動点と見なすことができます。したがって、Yを用いることで、すべての再帰関数をラムダ式として表現できます。特に、再帰を用いることで、自然数の減算、乗算、比較述語を簡潔に定義することが可能になります。

Yコンビネータを厳密なプログラミング言語で直接コーディングすると、そのような言語で使用される評価の適用順序により、内部自己適用を完全に展開しようとする試みが発生します。 $(xx)$ 時期尚早にスタックオーバーフローを引き起こしたり、末尾呼び出し最適化の場合は無限ループを引き起こしたりする。^{[ 24 ]} Y の遅延バリアントであるZ コンビネータは、このような言語で使用できる。内部の自己適用は、イータ展開による追加の抽象化の背後に隠されている。 $(\lambda v.xxv)$ それによって時期尚早な拡大を防ぐ：^{[ 25 ]}

Z=\lambda f.(\lambda x.f(\lambda v.xxv))\ (\lambda x.f(\lambda v.xxv))\ .

標準規約

特定の用語には一般的に認められた名称があります: ^{[ 26 ]}^{[ 27 ]}^{[ 28 ]}

I := λ x . x

S := λ x .λ y .λ z。x z ( y z )

K := λ x .λ y . x

B := λ x .λ y .λ z。x ( y z )

C := λ x .λ y .λ z . x z y

W := λ x .λ y . x y y

ωまたはΔまたはU := λ x . x x

Ω := ω ω

Iは恒等関数です。SKとBCKW は、任意のラムダ項を表現できる完全なコンビネータ計算システムを形成します。次のセクションを参照してください。ΩはUUであり、正規形を持たない最小の項です。YIも同様の項です。Y は標準であり、上記で定義されています。また、 Y = BU(CBU)と定義することもできるため、 Y g=g( Y g)となります。上記で定義されたTRUEとFALSE は、一般的にTとFと略記されます。

抽象化の排除

N が抽象化を持たないラムダ項であり、名前付き定数 (コンビネータ) を含む可能性がある場合、 λ x . Nと同等でありながら抽象化を持たないラムダ項T ( x , N )が存在する(名前付き定数の一部である場合を除く。ただし、これらが非原子的であるとみなされる場合)。これは変数の匿名化とも考えられ、T ( x , N ) はNからxのすべての出現箇所を削除する一方で、 Nにxが含まれている位置に引数の値を代入することは可能である。変換関数T は次のように定義できる。

T ( x , x ) := I

T ( x , N ) := K N、xがNに含まれていない場合

T ( x , M N ) := S T ( x , M ) T ( x , N )

いずれの場合も、 T ( x , N ) Pの形式の項は、最初のコンビネータI、K、またはS が引数Pを取得することによって、 (λ x . N ) Pの β 還元と同様に還元されます。I はその引数を返します。K N は、 Nにx の自由な出現がない場合の(λ x . N )と同様に、引数を破棄します。S は、引数を適用の 2 つのサブ項に渡してから、最初の結果を 2 番目の結果に適用します。これは、(λ x . MN ) Pが((λ x . M ) P ) ((λ x . N ) P )と同じであるのと同様です。

コンビネータBとCはSと似ていますが、引数をアプリケーションのサブタームの 1 つだけに渡します ( Bは「引数」サブタームに、Cは「関数」サブタームに)。これにより、サブタームの 1 つにxが出現しない場合は、後続のKを節約できます。BとCと比較すると、Sコンビネータは実際には 2 つの機能、つまり引数の並べ替えと、引数を 2 箇所で使用できるように複製する機能を統合しています。Wコンビネータは後者のみを実行するため、SKI コンビネータ計算の代替としてB、C、K、W システムが得られます。

最後のルールの前にさらにルールを追加すると、

T ( x , N x ) := N 、xがNに含まれていない場合

表現する $\eta$ -削減、なぜなら(λ x . N x ) P は、このような場合N Pと同じであり、より長いシーケンスS ( K N ) Iの作成を回避できるからである。

型付きラムダ計算

型付きラムダ計算は、ラムダ記号 ( $\lambda$ ）匿名関数の抽象化を表す。この文脈では、型は通常、ラムダ項に割り当てられる構文的な性質のオブジェクトである。型の正確な性質は、考慮される計算体系によって異なる（型付きラムダ計算の種類を参照）。ある観点からは、型付きラムダ計算は型なしラムダ計算の改良と見なすことができるが、別の観点からは、型付きラムダ計算はより基本的な理論であり、型なしラムダ計算は1つの型のみを持つ特殊なケースであると考えることもできる。^{[ 29 ]}

型付きラムダ計算はプログラミング言語の基礎であり、MLやHaskellなどの型付き関数型プログラミング言語、そして間接的には型付き命令型プログラミング言語の基盤となっています。型付きラムダ計算はプログラミング言語の型システムの設計において重要な役割を果たします。型付け可能性は通常、プログラムの望ましい特性、例えばメモリアクセス違反を引き起こさないといった特性を捉えます。

型付きラムダ計算は、カリー・ハワード同型性を介して数理論理学や証明論と密接に関連しており、圏のクラスの内部言語とみなすことができる。例えば、単純型付きラムダ計算は、デカルト閉圏（CCC）の言語である。^[³⁰^]

削減戦略

項が正規化であるかどうか、また正規化する場合にどれだけの作業が必要かは、使用される縮約戦略に大きく依存します。一般的なラムダ計算縮約戦略には、次のものがあります。^{[ 31 ]}^{[ 32 ]}^{[ 33 ]}

通常注文: 最も左端の最も外側のredexが最初に還元されます。つまり、可能な限り、引数は還元される前に抽象化の本体に代入されます。項がベータ正規形を持つ場合、正規順序還元は必ずその正規形に到達します。
申請命令: 最も左の最も内側の縮約式が最初に縮約されます。結果として、関数の引数は、関数に代入される前に必ず縮約されます。通常の順序縮約とは異なり、適用順序縮約では、そのような正規形が存在する場合でも、式のベータ正規形を見つけることができない場合があります。たとえば、次の項 $(\;\lambda x.y\;\;(\lambda z.(zz)\;\lambda z.(zz))\;)$ 適用順序によって自身に還元されるが、正規順序ではベータ正規形に還元される $y$ 。
完全なβ還元: いかなるredexもいつでも削減できる。これは基本的に、特定の削減戦略が存在しないことを意味する。削減可能性に関しては、「あらゆる可能性が考えられる」ということだ。

弱い削減戦略はラムダ抽象化の下では削減を行いません。

値渡し呼び出し: 適用順序に似ていますが、抽象化内部では還元は行われません。これは、C言語のような厳密な言語の評価順序に似ています。関数の引数は関数呼び出し前に評価され、引数が代入されるまで関数本体は部分的にも評価されません。
名前で呼ぶ: 通常の順序と同様ですが、抽象化内部では還元は実行されません。たとえば、λ x .(λ y . y ) xは、redex (λ y . y ) xを含みますが、この戦略によれば正規形です。

共有を用いた戦略は、並列処理において「同じ」計算を削減する。

最適な削減: 通常の順序で行われますが、同じラベルを持つ計算は同時に削減されます。
必要に応じて呼び出し: 名前による呼び出し（つまり弱い呼び出し）ですが、関数アプリケーションで用語が重複する場合は、代わりに引数に名前を付けます。引数は「必要に応じて」評価され、その時点で名前のバインディングが縮小された値で更新されます。これは、通常の順序での評価と比較して時間を節約できます。

計算可能性

任意の 2 つのラムダ式を入力として受け取り、一方の式が他方の式に還元されるかどうかに応じてTRUEまたはFALSEを出力するアルゴリズムは存在しません。 ^[¹⁵^]より正確には、計算可能な関数ではこの問題を決定できません。これは、歴史的に決定不能性が証明された最初の問題でした。このような証明の場合、通常どおり、計算可能とは、チューリング完全な計算モデルによって計算可能であることを意味します。実際、計算可能性自体はラムダ計算によって定義できます。自然数の関数F : N → Nは、任意のペアx、y ∈ Nに対して、f ( x ) = yとなるようなラムダ式fが存在する場合に限り、計算可能な関数です。ここで、xとy_はそれぞれxとyに対応するチャーチ数であり、 = _βは β 還元との等価性を意味します。計算可能性とその等価性を定義する他のアプローチについては、チャーチ・チューリングのテーゼを参照してください。

チャーチの計算不能性の証明は、まず与えられたラムダ式が正規形を持つかどうかを判定することに問題を帰着させる。次に、この述語は計算可能であり、したがってラムダ計算で表現できると仮定する。クリーネの以前の研究に基づき、ラムダ式のゲーデル数を構築することで、ゲーデルの第一不完全性定理の証明に非常に近いラムダ式eを構築する。eを自身のゲーデル数に適用すると、矛盾が生じる。

複雑

ラムダ計算の計算複雑性の概念は、β 還元のコストが実装方法によって異なる可能性があるため、少し厄介です。^{[ 34 ]} 正確には、式E内の束縛変数Vのすべての出現位置を何らかの方法で見つける必要があり、これは時間コストを意味します。または、自由変数の位置を何らかの方法で追跡する必要があり、これは空間コストを意味します。E内のVの位置を単純に検索すると、 Eの長さnに対してO ( n )になります。ディレクターストリングは、この時間コストを 2 乗の空間使用と交換する初期のアプローチでした。^[³⁵^]より一般的には、これは明示的な置換を使用するシステムの研究につながりました。

2014年に、通常の順序の縮約によって項を縮約するために要するβ縮約ステップの数が妥当な時間コストモデルであることが示されました。つまり、縮約はステップ数に比例する多項式時間でチューリングマシン上でシミュレートできます。^{[ 36 ]}これは、各β縮約でサイズが指数関数的に増加するラムダ項の存在によるサイズ爆発のため、長年の未解決問題でした。この結果は、コンパクトな共有表現を使用することでこれを回避します。この結果は、縮約中にラムダ項を評価するために必要なスペースの量が項のサイズに比例しないことを明らかにしています。スペース複雑性の適切な尺度が何であるかは現在わかっていません。^{[ 37 ]}

不合理なモデルが必ずしも非効率を意味するわけではありません。最適削減では、同じラベルを持つすべての計算を 1 つのステップで削減し、重複作業を回避しますが、与えられた項を正規形に削減するための並列 β 削減ステップの数は、項のサイズに対してほぼ線形です。これは、任意のチューリングマシンをチューリングマシンのサイズに線形に比例するサイズでラムダ計算にエンコードできるため、妥当なコスト尺度としては小さすぎます。ラムダ項を削減する真のコストは、β 削減自体によるものではなく、β 削減中の redex の重複の処理によるものです。^{[ 38 ]}最適削減の実装が、正規形への最左端ステップ数などの妥当なコストモデルに関して測定した場合に妥当かどうかはわかりませんが、ラムダ計算の断片については、最適削減アルゴリズムが効率的であり、最左端と比較して最大で 2 乗のオーバーヘッドがあることが示されています。^{[ 37 ]}さらに、BOHM プロトタイプによる最適縮約の実装は、純粋なラムダ項においてCaml Light と Haskell の両方を上回った。^{[ 38 ]}

ラムダ計算とプログラミング言語

ピーター・ランディンの1965年の論文「ALGOL 60とチャーチのラムダ記法との対応関係」 ^{[ 39 ]}で指摘されているように、逐次手続き型プログラミング言語はラムダ計算の観点から理解することができ、これは手続き的抽象化と手続き（サブルーチン）適用の基本的なメカニズムを提供する。

匿名関数

例えば、Pythonでは「square」関数はラムダ式として次のように表現できます。

(ラムダx : x ** 2 )

上記の例は、第一級関数に評価される式です。この記号はlambda、パラメータ名のリスト（xこの場合は単一の引数）と、関数の本体として評価される式を指定して、匿名関数を作成しますx**2。匿名関数は、ラムダ式と呼ばれることもあります。

Pascalをはじめとする多くの命令型言語では、関数ポインタの仕組みを通して、サブルーチンを他のサブルーチンへの引数として渡す機能が長らくサポートされてきました。しかし、関数ポインタは関数が第一級データ型となるための十分条件ではありません。なぜなら、関数が第一級データ型となるのは、実行時にその関数の新しいインスタンスを作成できる場合に限られるからです。このような実行時の関数作成は、Smalltalk、JavaScript、Wolfram Language、そして最近ではScala、Eiffel（エージェントとして）、C#（デリゲートとして）、C++11などでサポートされています。

並列処理と並行処理

ラムダ計算のチャーチ・ロッサー特性は、評価（β還元）を任意の順序で、並列でも実行できることを意味します。これは、さまざまな非決定論的な評価戦略が有効であることを意味します。しかし、ラムダ計算には並列処理のための明示的な構成要素がありません。ラムダ計算にフューチャーなどの構成要素を追加することは可能です。通信と並行性を記述するために、他のプロセス計算が開発されています。

意味論

ラムダ計算の項が他のラムダ計算の項、さらには自分自身に対しても関数として作用するという事実は、ラムダ計算の意味論に関する疑問を生じさせた。ラムダ計算の項に意味のある意味を割り当てることはできるだろうか？自然な意味論としては、関数空間D → Dと同型な、それ自身に対する関数の集合Dを見つけることである。しかし、 DからDへのすべての関数の集合はDよりも大きな濃度を持つため、濃度制約により、 Dが単一集合でない限り、そのような非自明な Dは存在し得ない。

1970年代に、ダナ・スコットは、連続関数のみを考慮すれば、必要な性質を持つ集合または領域Dが見つかることを示し、ラムダ計算のモデルを提供した。 ^{[ 40 ]}

この研究は、プログラミング言語の表示的意味論の基礎も形成した。

バリエーションと拡張

これらの拡張機能はラムダキューブに含まれています。

型付きラムダ計算– 型付き変数（および関数）を用いたラムダ計算
システムF – 型変数を持つ型付きラムダ計算
構成の計算– 型を第一級の値とする型付きラムダ計算

これらの形式体系は、ラムダ計算の拡張であり、ラムダキューブには含まれていない。

バイナリラムダ計算– バイナリ入出力（I/O）、項のバイナリ符号化、および指定されたユニバーサルマシンを備えたラムダ計算のバージョン。
ラムダμ計算–古典論理を扱うためのラムダ計算の拡張

これらの形式体系はラムダ計算の変形である。

カッパ計算― ラムダ計算の1階版

これらの形式体系はラムダ計算に関連している。

組み合わせ論理― 変数を用いない数理論理の表記法
SKIコンビネータ計算– S、K、Iコンビネータに基づく計算システムであり、ラムダ計算と同等であるが、変数置換なしで簡約可能である。

注記

↑「どこ $M[x:=N]$ 置換を表す $N$ の各発生について $x$ で $M$ 「. ^{[ 1 ]}^{: 7}また表記される $M[N/x]$ 「 $N$ のために $x$ で $M$ 「. ^{[ 2 ]}
↑ Barendregt, Barendsen (2000) はこの規則を公理 βと呼んでいます
↑詳しい歴史については、CardoneとHindleyの「ラムダ計算と組み合わせ論理の歴史」（2006年）を参照してください。
1 2 $\mapsto$ は「」と発音され、にマッピングされます。
↑ (λ f . M ) N は「f を M の N とする」と発音できます。
↑ Ariola と Blom^{[ 23 ]}は、1) letrecで拡張された整形式循環ラムダグラフを使用した表現計算の公理を使用して、無限に展開する可能性のある木を検出します。2) スコープ付きラムダグラフの β 縮約を使用した表現計算は、Ariola/Blom によるラムダ計算の循環拡張を構成します。3) Ariola/Blom は、 § 値渡しを使用して厳密言語について推論し、Moggi の計算および Hasegawa の計算と比較します。結論は p. 111 にあります。^[²³^]

参考文献

この記事の一部は、FOLDOCの資料に基づいており、許可を得て使用しています。

1 2 Barendregt, ヘンク; Erik Barendsen (2000 年 3 月)、ラムダ計算入門(PDF)
↑ n Labでの明示的な置換
↑ de Queiroz, Ruy JGB (1988). "プログラミングの証明論的説明と還元規則の役割". Dialectica . 42 (4): 265– 282. doi : 10.1111/j.1746-8361.1988.tb00919.x .
↑チューリング、アラン M. (1937年12月)。「計算可能性と λ-定義可能性」。記号論理学ジャーナル。2 ( 4): 153–163。doi : 10.2307 / 2268280。JSTOR 2268280。S2CID 2317046。
↑ Tait, WW (1967年8月) 「有限型Iの関数の内包的解釈」『記号論理学ジャーナル』32 (2): 198–212 . doi : 10.2307/2271658 . ISSN 0022-4812 . JSTOR 2271658. S2CID 9569863 .
↑コカン、ティエリー（2006年2月8日）。ザルタ、エドワード・N（編）。「型理論」。スタンフォード哲学百科事典（2013年夏版）。 2020年11月17日取得。
↑モートガット、マイケル（1988）。『カテゴリー的探究：ランベック計算の論理的および言語的側面』。フォリス出版。ISBN 9789067653879。
↑ハリー、バント。マスケンス、ラインハルト編。（2008年）。コンピューティングの意味。スプリンガー。ISBN 978-1-4020-5957-5。
↑ミッチェル、ジョン・C. (2003).プログラミング言語の概念. ケンブリッジ大学出版局. p. 57. ISBN 978-0-521-78098-8。。
↑ Chacón Sartori, Camilo (2023-12-05). Racket を使用したラムダ計算入門(技術レポート)。2023-12-07のオリジナルからアーカイブ済み。
↑ピアース、ベンジャミン C. 『コンピュータ科学者のための基礎圏論』 53ページ。
↑ Church, Alonzo (1932). "論理の基礎のための公準のセット". Annals of Mathematics . Series 2. 33 (2): 346– 366. doi : 10.2307/1968337 . JSTOR 1968337 .
↑ Kleene, Stephen C. ; Rosser, JB (1935 年 7 月). 「ある種の形式論理の矛盾」. The Annals of Mathematics . 36 (3): 630. doi : 10.2307/1968646 . JSTOR 1968646 .
↑ Church, Alonzo (1942 年 12 月). 「Haskell B. Curry 著『特定の形式論理の矛盾性』の書評」. The Journal of Symbolic Logic . 7 (4): 170–171 . doi : 10.2307/2268117 . JSTOR 2268117 .
1 2 Church, Alonzo (1936). 「初等整数論の解決不可能な問題」。American Journal of Mathematics . 58 (2): 345–363 . doi : 10.2307/2371045 . JSTOR 2371045 .
↑ Church, Alonzo (1940). "A Formulation of the Simple Theory of Types". Journal of Symbolic Logic . 5 (2): 56–68 . doi : 10.2307/2266170 . JSTOR 2266170 . S2CID 15889861 .
↑ Partee, BBH; ter Meulen, A. ; Wall, RE (1990). Mathematical Methods in Linguistics . Springer. ISBN 97890277224542016年12月29日に取得。
↑ Alama, Jesse. Zalta, Edward N. (編). "ラムダ計算" .スタンフォード哲学百科事典(2013 年夏版) . 2020 年11 月 17 日取得.
↑ダナ・スコット、「過去を振り返り、未来を見据える」、ダナ・スコットの85歳の誕生日とドメイン理論50周年を記念するワークショップでの招待講演、FLoC 2018、7月7日～8日（講演7日、2018年）。該当箇所は32分50秒から。（英国バーミンガム大学での2016年5月の講演の抜粋も参照
↑ Felleisen, Matthias; Flatt, Matthew (2006), Programming Languages and Lambda Calculi (PDF) , p. 26, 2009年2月5日にオリジナル(PDF)からアーカイブ済み元の場所にある注記（2017年アクセス）によると、著者らは、最初に参照された作品は書籍によって置き換えられたと考えているようです。
↑ 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
↑ブルース、キム・B. (2002).オブジェクト指向言語の基礎：型と意味論. MIT Press. p. 151. ISBN 978-0-262-02523-2。
1 2 Zena M. Ariola および Stefan Blom、 Proc. TACS '94仙台、日本 1997 (1997) 巡回ラムダ計算114 ページ。
↑ベネ、アダム（2017年8月17日）。「JavaScriptにおける固定小数点コンビネータ」。ベネスタジオ。Medium 。 2020年8月2日取得。
↑ "CS 6110 S17 講義 5. 再帰と固定点コンビネータ" (PDF)。コーネル大学。4.1 CBV 固定点コンビネータ。
↑ Ker, Andrew D. 「ラムダ計算と型」(PDF) . p. 6 . 2022年1月14日取得.
↑ Dezani-Ciancaglini, Mariangiola; Ghilezan, Silvia (2014). "Preciseness of Subtyping on Intersection and Union Types" (PDF) . Rewriting and Typed Lambda Calculi . Lecture Notes in Computer Science. Vol. 8560. p. 196. doi : 10.1007/978-3-319-08918-8_14 . hdl : 2318/149874 . ISBN 978-3-319-08917-12022年1月14日に取得。
↑ Forster, Yannick; Smolka, Gert (2019年8月) 「Coqにおける計算モデルとしての呼び出し値ラムダ計算」(PDF) . Journal of Automated Reasoning . 63 (2): 393– 413. doi : 10.1007/s10817-018-9484-2 . S2CID 53087112 . 2022年1月14日取得.
↑型とプログラミング言語、273ページ、ベンジャミン・C・ピアース
↑ 「スコットの表現定理と単葉カルービ包絡線」(PDF)。 Dagstuhl Publishing 。 2026年5月19日取得。
↑ピアース、ベンジャミン C. (2002).型とプログラミング言語. MIT Press . p. 56. ISBN 0-262-16209-1。
↑ Sestoft, Peter (2002). "ラムダ計算の簡約の実証" (PDF) . The Essence of Computation . Lecture Notes in Computer Science. Vol. 2566. pp. 420–435 . doi : 10.1007/3-540-36377-7_19 . ISBN 978-3-540-00326-72022年8月22日に取得。
↑ビエルナツカ、マウゴルザタ。キャラトニク、ヴィトルド。ドラブ、トマシュ (2022)。アンドロニック、6月。デ・モウラ、レオナルド（編）。ラムダ微積分削減戦略と Coq の動物園(PDF)。ライプニッツ国際情報学会議 (LIPIcs)。 Vol. 237. ダグシュトゥール城 – Leibniz-Zentrum für Informatik。 7 :1–7:19。土井：10.4230/LIPIcs.ITP.2022.7。ISBN 978-3-95977-252-52022年8月22日に取得。
↑ Frandsen, Gudmund Skovbjerg; Sturtivant, Carl (1991年8月26日). 「λ計算の効率的な実装とは何か？」 .関数型プログラミング言語とコンピュータアーキテクチャ：第5回ACM会議。米国マサチューセッツ州ケンブリッジ、1991年8月26日～30日。議事録。Lecture Notes in Computer Science。第523巻。Springer -Verlag。pp. 289–312。CiteSeerX 10.1.1.139.6913。doi : 10.1007/ 3540543961_14。ISBN 9783540543961。
↑ Sinot, F.-R. (2005). "Director Strings Revisited: A Generic Approach to the Efficient Representation of Free Variables in Higher-order Rewriting" (PDF) . Journal of Logic and Computation . 15 (2): 201– 218. doi : 10.1093/logcom/exi010 .
↑ Accattoli, Beniamino; Dal Lago, Ugo (2014年7月14日). 「ベータ還元は確かに不変である」.第23回EACSLコンピュータサイエンス論理年次会議（CSL）および第29回ACM/IEEEコンピュータサイエンス論理シンポジウム（LICS）合同会議議事録. pp. 1–10 . arXiv : 1601.01233 . doi : 10.1145/2603088.2603105 . ISBN 9781450328869. S2CID 11485010 .
1 2 Accattoli, Beniamino (2018 年 10 月). "(非)効率性と妥当なコストモデル" . Electronic Notes in Theoretical Computer Science . 338 : 23– 43. doi : 10.1016/j.entcs.2018.10.003 .
1 2 Asperti, Andrea (2017年1月16日). 「ラムダ項の効率的な削減について」. arXiv : 1701.04240v1 [ cs.LO ].
↑ Landin, PJ (1965). "ALGOL 60 と Church のラムダ記法との対応関係" . Communications of the ACM . 8 (2): 89– 101. doi : 10.1145/363744.363749 . S2CID 6505810 .
↑ Scott, Dana (1993). "ISWIM、CUCH、OWHYに対する型理論的代替案" (PDF) . Theoretical Computer Science . 121 ( 1– 2): 411– 440. doi : 10.1016/0304-3975(93)90095-B . 2022年12月1日取得.1969年に執筆され、未発表原稿として広く流通した。

さらに読む

アベルソン、ハロルド＆ジェラルド・ジェイ・サスマン。『コンピュータプログラムの構造と解釈』MIT 出版。ISBN 0-262-51087-1。
Barendregt、Hendrik Pieterラムダ微積分の入門。
Barendregt, Hendrik Pieter、「論理学とコンピュータ科学におけるラムダ計算の影響」。『記号論理学紀要』第3巻、第2号、1997年6月。
Barendregt, Hendrik Pieter、「型自由ラムダ計算」、『数理論理学ハンドブック』 1091–1132ページ、North-Holland (1977) ISBN 0-7204-2285-X
Cardone, Felice および Hindley, J. Roger、2006 年。「ラムダ計算と組み合わせ論理の歴史」。Wayback Machineに 2021 年 5 月6 日にアーカイブされました。Gabbay および Woods (編)、Handbook of the History of Logic、第 5 巻。Elsevier。
チャーチ、アロンゾ、「初等整数論の解決不可能な問題」、アメリカ数学ジャーナル、58（1936）、pp. 345–363。この論文には、ラムダ式の同値性が一般に決定不可能であることの証明が含まれています。
チャーチ、アロンゾ（1941）。ラムダ変換の計算。プリンストン：プリンストン大学出版局。2020年4月14日取得。( ISBN) 978-0-691-08394-0）
Frink Jr., Orrin (1944). 「レビュー: Alonzo Church によるラムダ変換の計算」 (PDF) . Bulletin of the American Mathematical Society . 50 (3): 169– 172. doi : 10.1090/s0002-9904-1944-08090-7 .
クリーネ、スティーブン、「形式論理における正の整数の理論」、アメリカ数学ジャーナル、57（1935）、pp. 153–173および219–244。いくつかのよく知られた関数のラムダ計算の定義が含まれています。
ランディン、ピーター、「ALGOL 60 とチャーチのラムダ記法との対応関係」、Communications of the ACM、第 8 巻、第 2 号 (1965 年)、89～101 ページ。ACMサイトから入手可能。プログラミング言語の基礎としてのラムダ計算の重要性を強調した古典的な論文。
ラーソン、ジム著『ラムダ計算とScheme入門』。プログラマーのための分かりやすい入門書。
マイケルソン、グレッグ（2013年4月10日）。ラムダ計算による関数型プログラミング入門。クーリエ・コーポレーション。ISBN 978-0-486-28029-5。^{[ 1 ]}
Schalk, A. および Simmons, H. (2005) λ-計算と算術入門、適切な演習問題付き。マンチェスター大学数理論理学修士課程の講義ノート。
de Queiroz, Ruy JGB (2008). 「還元規則、使用としての意味、証明論的意味論について」. Studia Logica . 90 (2): 211– 247. doi : 10.1007/s11225-008-9150-5 . S2CID 11321602 . この論文は、「意味は使用である」という考え方を形式的に裏付けるものであり、証明に基づいているとはいえ、意味を与える規則として還元を採用している点で、ダメット＝プラウィッツの伝統における証明論的意味論とは異なる。
ハンキン、クリス、『コンピュータ科学者のためのラムダ計算入門』、ISBN 0954300653

大学院生向けの専門書／教科書

Sørensen, Morten Heine および Urzyczyn, Paweł (2006)、『Curry–Howard の同型性に関する講義』、Elsevier、ISBN 0-444-52077-5本書は、型なしラムダ計算から、ほとんどの型付きラムダ計算まで、ラムダ計算の主要なトピックを網羅した最新の専門書であり、純粋型システムやラムダキューブといった最近の発展についても解説しています。ただし、サブタイピング拡張については扱っていません。
ピアース、ベンジャミン（2002）、『型とプログラミング言語』、MIT Press、ISBN 0-262-16209-1本書は、実用的な型システムの観点からラムダ計算を解説しています。依存型などのトピックは言及されるにとどまりますが、サブタイピングは重要なトピックです。

文書

ラムダ計算入門（ PDF）アヒム・ユング著
ラムダ計算のタイムライン（ PDF） - ダナ・スコット著
ラムダ計算入門チュートリアル（ PDF）著：ラウル・ロハス
ラムダ計算に関する講義ノート（ PDF）ピーター・セリンジャー著
マリウス・ブリガによるグラフィックラムダ計算
Peter Kelly、Paul Coddington、Andrew Wendelbornによる「ワークフローモデルとしてのラムダ計算」では、ラムダ式を評価する一般的な手段としてグラフ縮約について言及し、ラムダ計算の分散コンピューティングへの適用可能性（ラムダ式の並列グラフ縮約を可能にするChurch–Rosser特性による

外部リンク

グラハム・ハットン著「ラムダ計算」：ラムダ計算に関するComputerphileの短い（12分）ビデオ
ヘルムート・ブランドル著『ラムダ計算入門（ステップバイステップ）』
「ラムダ計算」、数学百科事典、EMS Press、2001年 [1994年]
デイビッド・C・キーナン著『モッキンバードを解剖する：アニメーションによる還元を用いたラムダ計算の図式表記法』
L. Allison、いくつかの実行可能な λ 計算の例
ゲオルク・P・ロチェフスキー著『ラムダ計算とA++』
ブレット・ビクター著『アリゲーター・エッグス：ラムダ微積分に基づいたパズルゲーム』
LCIラムダインタープリタ：シンプルながら強力な純粋微積分インタープリタ
Lambda Calculus のリンクは Lambda-the-Ultimate に掲載されています。
Mike Thyer氏によるLambda Animatorは、代替的な削減戦略を示すグラフィカルなJavaアプレットです。
C++テンプレートを使用したラムダ計算の実装
シェーン・スタイナート・スレルケルド、「ラムダ計算」、インターネット哲学百科事典
アントン・サリフメトフ著『マクロラムダ計算』

↑ 「グレッグ・マイケルソンのホームページ」。数学およびコンピュータ科学。リッカートン、エジンバラ：ヘリオット・ワット大学。 2022年11月6日取得。

[3] 「どこ $M[x:=N]$ 置換を表す $N$ の各発生について $x$ で $M$ 「. ^{[ 1 ]}^{: 7}また表記される $M[N/x]$ 「 $N$ のために $x$ で $M$ 「. ^{[ 2 ]}

[beta-5] Barendregt, Barendsen (2000) はこの規則を公理 βと呼んでいます

[15] 詳しい歴史については、CardoneとHindleyの「ラムダ計算と組み合わせ論理の歴史」（2006年）を参照してください。

[mapsTo-23] 1 2 $\mapsto$ は「」と発音され、にマッピングされます。

[27] (λ f . M ) N は「f を M の N とする」と発音できます。

[ariola-29] Ariola と Blom^{[ 23 ]}は、1) letrecで拡張された整形式循環ラムダグラフを使用した表現計算の公理を使用して、無限に展開する可能性のある木を検出します。2) スコープ付きラムダグラフの β 縮約を使用した表現計算は、Ariola/Blom によるラムダ計算の循環拡張を構成します。3) Ariola/Blom は、 § 値渡しを使用して厳密言語について推論し、Moggi の計算および Hasegawa の計算と比較します。結論は p. 111 にあります。^[²³^]

[BarendregtBarendsen-1] 1 2 Barendregt, ヘンク; Erik Barendsen (2000 年 3 月)、ラムダ計算入門(PDF)

[2] Labでの明示的な置換

[4] Queiroz, Ruy JGB (1988). "プログラミングの証明論的説明と還元規則の役割". Dialectica . 42 (4): 265– 282. doi : 10.1111/j.1746-8361.1988.tb00919.x .

[6] チューリング、アラン M. (1937年12月)。「計算可能性と λ-定義可能性」。記号論理学ジャーナル。2 ( 4): 153–163。doi : 10.2307 / 2268280。JSTOR 2268280。S2CID 2317046。

[Tait_1967-7] Tait, WW (1967年8月) 「有限型Iの関数の内包的解釈」『記号論理学ジャーナル』32 (2): 198–212 . doi : 10.2307/2271658 . ISSN 0022-4812 . JSTOR 2271658. S2CID 9569863 .

[8] コカン、ティエリー（2006年2月8日）。ザルタ、エドワード・N（編）。「型理論」。スタンフォード哲学百科事典（2013年夏版）。 2020年11月17日取得。

[9] モートガット、マイケル（1988）。『カテゴリー的探究：ランベック計算の論理的および言語的側面』。フォリス出版。ISBN 9789067653879。

[10] ハリー、バント。マスケンス、ラインハルト編。（2008年）。コンピューティングの意味。スプリンガー。ISBN 978-1-4020-5957-5。

[11] ミッチェル、ジョン・C. (2003).プログラミング言語の概念. ケンブリッジ大学出版局. p. 57. ISBN 978-0-521-78098-8。。

[12] Chacón Sartori, Camilo (2023-12-05). Racket を使用したラムダ計算入門(技術レポート)。2023-12-07のオリジナルからアーカイブ済み。

[13] ピアース、ベンジャミン C. 『コンピュータ科学者のための基礎圏論』 53ページ。

[14] Church, Alonzo (1932). "論理の基礎のための公準のセット". Annals of Mathematics . Series 2. 33 (2): 346– 366. doi : 10.2307/1968337 . JSTOR 1968337 .

[16] Kleene, Stephen C. ; Rosser, JB (1935 年 7 月). 「ある種の形式論理の矛盾」. The Annals of Mathematics . 36 (3): 630. doi : 10.2307/1968646 . JSTOR 1968646 .

[17] Church, Alonzo (1942 年 12 月). 「Haskell B. Curry 著『特定の形式論理の矛盾性』の書評」. The Journal of Symbolic Logic . 7 (4): 170–171 . doi : 10.2307/2268117 . JSTOR 2268117 .

[Church1936-18] 1 2 Church, Alonzo (1936). 「初等整数論の解決不可能な問題」。American Journal of Mathematics . 58 (2): 345–363 . doi : 10.2307/2371045 . JSTOR 2371045 .

[19] Church, Alonzo (1940). "A Formulation of the Simple Theory of Types". Journal of Symbolic Logic . 5 (2): 56–68 . doi : 10.2307/2266170 . JSTOR 2266170 . S2CID 15889861 .

[mm-linguistics-20] Partee, BBH; ter Meulen, A. ; Wall, RE (1990). Mathematical Methods in Linguistics . Springer. ISBN 97890277224542016年12月29日に取得。

[21] Alama, Jesse. Zalta, Edward N. (編). "ラムダ計算" .スタンフォード哲学百科事典(2013 年夏版) . 2020 年11 月 17 日取得.

[22] ダナ・スコット、「過去を振り返り、未来を見据える」、ダナ・スコットの85歳の誕生日とドメイン理論50周年を記念するワークショップでの招待講演、FLoC 2018、7月7日～8日（講演7日、2018年）。該当箇所は32分50秒から。（英国バーミンガム大学での2016年5月の講演の抜粋も参照

[24] Felleisen, Matthias; Flatt, Matthew (2006), Programming Languages and Lambda Calculi (PDF) , p. 26, 2009年2月5日にオリジナル(PDF)からアーカイブ済み元の場所にある注記（2017年アクセス）によると、著者らは、最初に参照された作品は書籍によって置き換えられたと考えているようです。

[Selinger-25] 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

[26] ブルース、キム・B. (2002).オブジェクト指向言語の基礎：型と意味論. MIT Press. p. 151. ISBN 978-0-262-02523-2。

[AB94-28] 1 2 Zena M. Ariola および Stefan Blom、 Proc. TACS '94仙台、日本 1997 (1997) 巡回ラムダ計算114 ページ。

[30] ベネ、アダム（2017年8月17日）。「JavaScriptにおける固定小数点コンビネータ」。ベネスタジオ。Medium 。 2020年8月2日取得。

[31] "CS 6110 S17 講義 5. 再帰と固定点コンビネータ" (PDF)。コーネル大学。4.1 CBV 固定点コンビネータ。

[32] Ker, Andrew D. 「ラムダ計算と型」(PDF) . p. 6 . 2022年1月14日取得.

[33] Dezani-Ciancaglini, Mariangiola; Ghilezan, Silvia (2014). "Preciseness of Subtyping on Intersection and Union Types" (PDF) . Rewriting and Typed Lambda Calculi . Lecture Notes in Computer Science. Vol. 8560. p. 196. doi : 10.1007/978-3-319-08918-8_14 . hdl : 2318/149874 . ISBN 978-3-319-08917-12022年1月14日に取得。

[34] Forster, Yannick; Smolka, Gert (2019年8月) 「Coqにおける計算モデルとしての呼び出し値ラムダ計算」(PDF) . Journal of Automated Reasoning . 63 (2): 393– 413. doi : 10.1007/s10817-018-9484-2 . S2CID 53087112 . 2022年1月14日取得.

[35] 型とプログラミング言語、273ページ、ベンジャミン・C・ピアース

[36] 「スコットの表現定理と単葉カルービ包絡線」(PDF)。 Dagstuhl Publishing 。 2026年5月19日取得。

[37] ピアース、ベンジャミン C. (2002).型とプログラミング言語. MIT Press . p. 56. ISBN 0-262-16209-1。

[38] Sestoft, Peter (2002). "ラムダ計算の簡約の実証" (PDF) . The Essence of Computation . Lecture Notes in Computer Science. Vol. 2566. pp. 420–435 . doi : 10.1007/3-540-36377-7_19 . ISBN 978-3-540-00326-72022年8月22日に取得。

[39] ビエルナツカ、マウゴルザタ。キャラトニク、ヴィトルド。ドラブ、トマシュ (2022)。アンドロニック、6月。デ・モウラ、レオナルド（編）。ラムダ微積分削減戦略と Coq の動物園(PDF)。ライプニッツ国際情報学会議 (LIPIcs)。 Vol. 237. ダグシュトゥール城 – Leibniz-Zentrum für Informatik。 7 :1–7:19。土井：10.4230/LIPIcs.ITP.2022.7。ISBN 978-3-95977-252-52022年8月22日に取得。

[40] Frandsen, Gudmund Skovbjerg; Sturtivant, Carl (1991年8月26日). 「λ計算の効率的な実装とは何か？」 .関数型プログラミング言語とコンピュータアーキテクチャ：第5回ACM会議。米国マサチューセッツ州ケンブリッジ、1991年8月26日～30日。議事録。Lecture Notes in Computer Science。第523巻。Springer -Verlag。pp. 289–312。CiteSeerX 10.1.1.139.6913。doi : 10.1007/ 3540543961_14。ISBN 9783540543961。

[41] Sinot, F.-R. (2005). "Director Strings Revisited: A Generic Approach to the Efficient Representation of Free Variables in Higher-order Rewriting" (PDF) . Journal of Logic and Computation . 15 (2): 201– 218. doi : 10.1093/logcom/exi010 .

[42] Accattoli, Beniamino; Dal Lago, Ugo (2014年7月14日). 「ベータ還元は確かに不変である」.第23回EACSLコンピュータサイエンス論理年次会議（CSL）および第29回ACM/IEEEコンピュータサイエンス論理シンポジウム（LICS）合同会議議事録. pp. 1–10 . arXiv : 1601.01233 . doi : 10.1145/2603088.2603105 . ISBN 9781450328869. S2CID 11485010 .

[Reasonable-43] 1 2 Accattoli, Beniamino (2018 年 10 月). "(非)効率性と妥当なコストモデル" . Electronic Notes in Theoretical Computer Science . 338 : 23– 43. doi : 10.1016/j.entcs.2018.10.003 .

[Asperti-44] 1 2 Asperti, Andrea (2017年1月16日). 「ラムダ項の効率的な削減について」. arXiv : 1701.04240v1 [ cs.LO ].

[45] Landin, PJ (1965). "ALGOL 60 と Church のラムダ記法との対応関係" . Communications of the ACM . 8 (2): 89– 101. doi : 10.1145/363744.363749 . S2CID 6505810 .

[46] Scott, Dana (1993). "ISWIM、CUCH、OWHYに対する型理論的代替案" (PDF) . Theoretical Computer Science . 121 ( 1– 2): 411– 440. doi : 10.1016/0304-3975(93)90095-B . 2022年12月1日取得.1969年に執筆され、未発表原稿として広く流通した。

[47] 「グレッグ・マイケルソンのホームページ」。数学およびコンピュータ科学。リッカートン、エジンバラ：ヘリオット・ワット大学。 2022年11月6日取得。

[ a ]

[ 3 ]

b

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[

[

[

[

[ 15 ]

[ 16 ]

[ 17 ]とコンピュータ科学

[

[ 19 ]

[ d ]

[ 20 ]

[ 21 ]

[ 1 ]

[22]

[

[

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 2 ]

[ 23 ]

[ 1 ]