람다 미적분학

람다 미적분학(Lambda calculus)은 수학적 논리학에서 함수의 추상화와 변수 결합과 치환을 이용한 응용에 기반한 계산을 표현하는 형식적인 체계입니다.튜링 기계를 시뮬레이션하는 데 사용할 수 있는 보편적인 계산 모델입니다.수학자 알론조 교회가 1930년대에 수학의 기초에 대한 연구의 일환으로 도입했습니다.

람다 연산은 람다 항을 구성하고 이에 대한 축소 연산을 수행하는 것으로 구성됩니다.가장 간단한 형태의 람다 미적분학에서는 다음 규칙만 사용하여 항을 만듭니다.^[a]

1. $x$ ${\textstyle x}$: 변수는 매개 변수를 나타내는 문자 또는 문자열입니다.
2. ${\textstyle (\lambdax).$$M)$}$$: 람다 추상화는 경계 변수 $x$ ${\displaystyle$ x$}($$λ$와 점/점 사이)을 입력으로 하고 본문 $M$ ${\textstyle$ M$}$을$($를) 반환하는 함수 정의입니다.
3. $(\text{MN})$ ${\textstyle (M\N)}$: $M$ ${\textstyle$ M}$함수$를 $N$ ${\textstyle$ N}$인수$에 적용하는 응용 프로그램입니다$.$ $M$ ${\textstyle M}$과 $N$ ${\textstyle$ N$}$은 $모두$ 람다 항입니다$$.

축소 작업에는 다음이 포함됩니다.

• $($$M[x])\오른쪽 화살표 (\lambday.$$M[y]}$ :$$식에서 바인딩된 변수의 이름을 변경하는 α-변환입니다.이름 충돌을 피하기 위해 사용됩니다.
• $λ$$M)\ N)\rightarrow (M[x:=N]}}$ :$$β-reduction, 추상화 본문의 인수식으로 바운드 변수를 대체합니다.

De Bruijn 인덱싱을 사용하면 이름 충돌이 없기 때문에 α 변환이 더 이상 필요하지 않습니다.축소 단계의 반복적인 적용이 결국 종료되면 처치-로저 정리에 의해 β-정규 형태가 생성됩니다.

Iota 및 Jot과 같은 범용 람다 함수를 사용하는 경우 변수 이름이 필요하지 않습니다. 이 함수는 다양한 조합으로 자체 호출하여 함수 동작을 생성할 수 있습니다.

설명 및 적용

람다 미적분학은 튜링 완료, 즉 모든 튜링 기계를 시뮬레이션하는 데 사용할 수 있는 보편적인 계산 모델입니다.^[3]이 이름과 같은 그리스 문자 람다(λ)는 람다 식을 사용하고 람다 항을 사용하여 함수의 변수에 결합을 나타냅니다.

람다 미적분은 입력하지 않거나 입력할 수 있습니다.유형화된 람다 미적분학에서 함수는 주어진 입력의 "유형" 데이터를 수용할 수 있는 경우에만 적용될 수 있습니다.유형 람다 연산은 유형 람다 연산이 비유형 연산보다 적게 표현할 수 있다는 점에서 이 글의 주요 주제인 비유형 람다 연산보다 약합니다.반면에 유형화된 람다 계산을 통해 더 많은 것을 증명할 수 있습니다.예를 들어, 단순히 유형화된 람다 미적분학에서는 모든 평가 전략이 단순히 유형화된 람다 항에 대해 종료되는 반면, 유형화되지 않은 람다 항에 대한 평가는 종료될 필요가 없다는 정리입니다.다양한 유형의 람다 연산이 존재하는 한 가지 이유는 미적분학에 대한 강력한 정리를 증명하는 것을 포기하지 않고 더 많은 것을 하고 싶었기 때문입니다.

람다 미적분학은 수학, 철학,^[4] 언어학,^[5][6] 그리고 컴퓨터 과학에서 많은 다양한 분야에 응용됩니다.^[7]람다 미적분학은 프로그래밍 언어 이론의 발전에 중요한 역할을 해왔습니다.함수형 프로그래밍 언어는 람다 미적분학을 구현합니다.람다 미적분학은 범주 이론의 현재 연구 주제이기도 합니다.^[8]

역사

람다 미적분학은 수학자 알론조 처치(Alonzo Church)가 1930년대에 수학의 기초에 대한 조사의 일환으로 도입했습니다.^[9][c]원래의 체계는 1935년 스티븐 클린과 J. B.가 논리적으로 일관성이 없는 것으로 나타났습니다. Rosser는 Kleene-Rosser 역설을 개발했습니다.^[10][11]

그 후 1936년에 Church는 계산과 관련된 부분만을 분리하여 발표했는데, 이 부분을 오늘날 무형식 람다 미적분학이라고 합니다.^[12]1940년에 그는 단순히 유형화된 람다 미적분학으로 알려진 계산적으로 약하지만 논리적으로 일관된 시스템을 소개했습니다.^[13]

프로그래밍 언어와의 관계가 명확해졌던 1960년대까지 람다 미적분학은 형식주의에 불과했습니다.자연어의 의미론에 리차드 몬태규와 다른 언어학자들의 응용 덕분에, 람다 미적분학은 언어학과^[14] 컴퓨터 과학 모두에서 훌륭한 위치를 차지하기 시작했습니다.^[15]

λ 기호의 유래

Church가 람다 미적분학에서 그리스 문자 lambda (λ)를 함수-추상 표기로 사용한 이유에 대해 약간의 불확실성이 있는데, 아마도 부분적으로 Church 자신의 상반된 설명 때문일 것입니다.Cardone and Hindley (2006)에 따르면:

그런데 교회는 왜 λ라는 표기를 택했을까요?[해럴드 딕슨에게 보낸 1964년 미발표 편지]에서 그는 함수-추상을 클래스-추상과 구별하기 위해 "${\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\$를 "${\displaystyle x}$ ^ ${\$로 먼저 수정함으로써, 화이트헤드와 러셀이 클래스-추상에 사용한 "${\displaystyle \stackrel{}{}}$^ {\displaystyle {\hat {x}}" 표기에서 "x ${\displaystyle }$ ${\displaystyle \land$ x$\}"$로 시작했다고 분명히 밝혔습니다.그런 다음 $$∧ ${\displaystyle \land}"$을$($를) "λ"로 변경하여 인쇄를 쉽게 할 수 있습니다.

이 기원은 [Roser, 1984, p.338]에서도 보고되었습니다.다른 한편으로, 그의 말년에 처치는 두 명의 질문자에게 그 선택이 더 우연적이었다고 말했습니다: 상징이 필요했고 마침 λ이 선택되었습니다.

데이나 스콧은 또한 다양한 대중 강연에서 이 문제를 다루었습니다.^[16]스콧 박사는 한때 람다 기호의 기원에 대해 Church의 전 제자이자 사위였던 John W. Addison Jr.에게 질문을 던졌고, 그는 그의 장인에게 엽서를 썼습니다.

친애하는 처치 교수님께,

러셀은 아이오타 연산자를, 힐버트는 엡실론 연산자를 가지고 있었습니다.연산자에 람다를 선택한 이유는 무엇입니까?

스콧에 따르면 처치의 전체 응답은 다음과 같은 주석이 달린 엽서를 돌려주는 것으로 구성되었습니다: "eeny, meeny, miny, moe.

비형식적

동기

계산 가능한 함수는 컴퓨터 과학과 수학의 기본 개념입니다.람다 미적분학은 계산의 특성을 공식적으로 연구하는 데 유용한 계산에 대한 간단한 의미론을 제공합니다.람다 미적분학은 의미론을 단순화하는 두 가지 단순화를 포함합니다.첫 번째 단순화는 람다 미적분학이 함수를 "익명으로 취급"한다는 것입니다. 이는 함수에 명확한 이름을 부여하지 않습니다.예를 들어, 함수는

${\displaystyle \operator name {square\_sum}(x,y)=x^{2}+y^{2}}$

익명으로 다시 작성할 수 있습니다.

${\displaystyle(x,y)\maps to x^{2}+y^{2}}$

(이것은 "x와 y의 튜플이 ${x\mathrm{}}^{}{}^{}$ + y ${2\mathrm{}}^{}${\$textstyle$x^{$2}$ + y^{$2}}"$로 읽힙니다.)$$^[d]마찬가지로 함수는

${\displaystyle \operatorname {id}(x)=x}$

익명으로 다시 작성할 수 있습니다.

${\displaystyle x\mapstox}$

입력이 단순히 자신에게 매핑되는 경우.^[d]

두 번째 단순화는 람다 미적분학이 단일 입력의 함수만 사용한다는 것입니다.$\mathrm{예}$를 들어 제곱합 {\$textstyle \operatorname {square\_sum}$ $\mathrm{함수}$와 같이 두 개의 입력이 필요한 일반 함수는 단일 입력을 받아들이는 동등한 함수로 재작업할 수 있으며, 출력이 다른 함수를 반환하므로 다시 단일 입력을 받아들이는 것입니다.예를들면,

${\displaystyle(x,y)\maps to x^{2}+y^{2}}$

재작업이 가능한

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

카레링이라고 알려진 이 방법은 여러 인수를 하나의 인수로 각각 함수의 체인으로 변환하는 함수입니다.

$($5, 2)에 $제곱합$ {\$textstyle \operatorname {square\$_sum} 함수의$$ 함수 적용, 한 번에 산출

${\textstyle ((x,y)\maps to x^{2}+y^{2}(5,2)}$

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

$=29$ ${\textst$

반면에 카레 버전의 평가는 한 단계 더 필요합니다.

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

$=($ $y$ $\mapsto$ ${52}^{}$+ $y^{}$ 2${}^{}$)$$( 2$$) ${\textst$=($y\mapsto 5^{2}$ + $y^{2})(2)}$ // x ${\displaystyle$ x$}$의 정의가 내부 식에 $5$ ${\displaystyle$ 5$}$과(와) 함께 사용되었습니다.이것은 β-환원과 같습니다.

$={52}^{}$+ ${22}^{}$ ${\textst$ + $2^{2}}$ // $y$ ${\displaystyle y}$의 정의가 $2$ ${\displaystyle 2}$과(와) 함께 사용되었습니다$.$ 역시 β-reduction과 유사합니다.

${\textstyle =29}$

동일한 결과에 도달할 수 있습니다.

람다 미적분학

람다 연산은 특정 형식 구문에 의해 정의되는 람다 항 언어와 람다 항을 조작하기 위한 변환 규칙 집합으로 구성됩니다.이러한 변환 규칙은 등식 이론으로 볼 수도 있고 조작적 정의로 볼 수도 있습니다.

위에서 설명한 바와 같이 이름이 없는 람다 미적분학의 모든 함수는 익명 함수입니다.입력 변수를 하나만 허용하기 때문에 여러 변수의 함수를 구현하기 위해 커리를 사용합니다.

람다항

람다 미적분학의 구문은 어떤 식들은 유효한 람다 미적분학 식으로 정의하고 어떤 식들은 유효한 C 프로그램이고 어떤 식들은 유효하지 않은 것으로 정의합니다.유효한 람다 미적분 표현식을 "람다 항"이라고 합니다.

다음 세 가지 규칙은 구문적으로 유효한 모든 람다 항을 만드는 데 적용할 수 있는 귀납적 정의를 제공합니다.^[e]

• 변수 x는 그 자체로 유효한 람다 항입니다.
• t가 람다 항이고 x가 변수인 경우$,$ (λ${\displaystyle x.}$t$)$ {\$displaystyle$(\lambda$x$.t$)}$은 람다 항(추상이라고 함)입니다.
• t 및 s가 람다 항이면${\displaystyle }$(${\displaystyle t}$ ${\displaystyle (t}$${\displaystyle }$) ${\displaystyles)}$은(는) 람다 항입니다(응용 프로그램이라고 함).

다른 건 람다 용어가 아닙니다.따라서 람다 항은 이 세 가지 규칙을 반복 적용하여 얻을 수 있는 경우에만 유효합니다.그러나 괄호는 특정 규칙에 따라 생략할 수 있습니다.예를 들어, 가장 바깥쪽 괄호는 보통 쓰지 않습니다.괄호 포함 시기는 아래의 § 참고 사항 참조

추상화 $\lambda$ ${\displaystyle x.t}$ ${\displaystyle \lambda x.t}$는 단일 입력 x를 취하고 t를 반환하는 § 익명 함수를 나타냅니다.예를 들어 λ ${\displaystyle x}$.${\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle 2^{}}$+ ${\displaystyle 2}$) ${\displaystyle$\lambda $x.(x^{2}+2)}$는 함수 $f$ ( ${\displaystyle x)}$= ${\displaystyle x^{}}$ ${\displaystyle 2^{}}$${\displaystyle {}^{}}$+${\displaystyle {}^{}2}$ ${\displaystyle$ $f(x$) = $x$$^{2}+2}$에 대한 추상화입니다.추상화를 사용할 때 $이름{\displaystyle }$ f${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle$ f$(x)}$이(가) 불필요합니다.${\displaystyle }$($λ$ ${\displaystyle x.t)}$ ${\displaysty$mbda $x.t)}$은(는) t항의 변수 x를 바인딩합니다.추상화가 있는 함수의 정의는 함수를 "설정"할 뿐 함수를 호출하지 않습니다.괄호 사용 방법은 아래 § 참고 사항 참조

$응용{\displaystyle }$ 프로그램$$t {\$displaystyle$$t}$의 {\$displaystyles$}은(는) 입력에 대한 함수 t의 적용을 나타냅니다$$. 즉, $($s) {\$displaystyle$ t(s$)}을($를) 생성하기 위해 입력에 함수 t를 호출하는 행위를 나타냅니다$.$

변수 선언의 람다 미적분학에는 개념이 없습니다.λ $x$ . (${\displaystyle }$x${\displaystyle }$+${\displaystyle y}$ ) ${\displaystyle$ \lambda$$x . (x +$$${\displaystyle y}$$)}($즉, $f$ (${\displaystyle }$x )${\displaystyle }$=$$(${\displaystyle }$x +${\displaystyle y}$ ) ${\displaystyle$ f ($x)$= (x +$y )})$와 같은 정의에서 람다 미적분 y는 아직 정의되지 않은 변수입니다.추상화 λ ${\displaystyle x}$. (${\displaystyle x}$+ ${\displaystyle y}$) ${\displaystyle \lambda$ x$.(x+y)}$이(가) 구문적으로 유효하며, 아직 알 수 없는 것에 해당 입력을 추가하는 함수를 나타냅니다.

괄호를 사용할 수 있으며 용어를 명확하게 정의하는 데 필요할 수 있습니다.예를들면,

1. ${\displaystyle }$ ${\displaystyle x}$${\displaystyle .}$ (${\displaystyle \lambda }$ x${\displaystyle }$. ${\displaystyle x}$) x ${\displaystyle \lambda$ x . $(\lambda$ x $.x$) x$}$ 형${\displaystyle 식}$으로 $\lambda$ x${\displaystyle }$. ${\displaystyle B}$ ${\displaystyle \lambda$ x$$.$B}$ $$— 추상화, 그리고
2. ${\displaystyle }$(${\displaystyle \lambda }$ ${\displaystyle x.}$ (${\displaystyle \lambda }$ x .${\displaystyle }$x )${\displaystyle (\lambda x .x))}$ x $M$$$${\displaystyle$$$M}$N$ ${\displaystyle N}$ 형식의 응용 프로그램입니다.

예제 1과 2는 다른 용어를 나타냅니다. 괄호의 범위를 제외하면 모두 동일합니다.그러나 예제 1은 함수 정의이고 예제 2는 함수 적용입니다.람다 변수 x는 두 예제 모두에서 자리 표시자입니다.

여기서 예제 1은 함수 λ ${\displaystyle x.}$ ${\displaystyle B}$ ${\displaystyle \lambdax$를 정의합니다$.$$B$여기서 $B$ ${\displaystyle B}$는 $($$λ$ x${\displaystyle }$. x${\displaystyle }$) ${\displaystyle x}$ ${\displaystyle (\lambda x.$${\displaystyle x}$$)x}$이고$,$ 입력 $x가 {\displaystyle$ x$}$인 익명 함수$($$λ$ x${\displaystyle }$. x${\displaystyle }$) ${\$displaystyle $(\lambda x.x)}$이고$,$ 예제 $2$에서는 M ${\displaystyle M}$ $N$ ${\displaystyle N}$이$($여기서 $M$ ${\displaystyle M}$은 람다 항$($$λ$ ${\displaystyle x}$. (${\displaystyle x))}$ ${\displaystyle (\lambda$)$x.(\lambda x.x)}$이(가) 입력 $N$ ${\displaystyle N}($$x$ ${\displaystyle x})$에 적용되고 있습니다$.$ 예제 1과 2 모두 ID 함수 $λ$ ${\displaystyle x.x}$ ${\displaystyle \lambda x.x}$로 평가됩니다$.$

함수에서 작동하는 함수

람다 미적분학에서 함수는 '1등급 값'으로 간주되므로 함수를 입력으로 사용하거나 다른 함수의 출력으로 반환할 수 있습니다.

예를 들어, λ x${\displaystyle .}$ ${\displaystyle x}$ ${\displaystyle \lambda$ x$.$${\displaystyle x}$$}$는 ID 함수를 $나타내고$,${\displaystyle x}$ ↦$$x {\$displaystyle$x\$mapsto$ $x$$\}$은(는$)$ ${\displaystyle y}$ ${\displaystyle y}$에 적용된 ID 함수를 나타냅니다$.$ 또한$,$ (λ ${\displaystyle x.y)}$ ${\displaystyle (\lambda x.y)}$은(는) 상수 함수 $x$ ↦ ${\displaystyle y}$ ${\displaystyle x\mapsto y}$를 나타냅니다., $$입력에 관계없이$$항상 $y{\displaystyle }$ ${\displaystyle y}$를(를) 반환하는 함수입니다.람다 미적분학에서 함수 적용은 좌연관으로 간주되므로, ${\displaystyle \mathrm{stx}}$ ${\displaystyle stx}$는${\displaystyle }$(${\displaystyle \mathrm{st})}$ x ${\displaystyle (st)x}$를 의미합니다$.$

람다 항을 "동등한" 람다 항으로 "감소"할 수 있는 "동등한" 람다 항으로 "감소"할 수 있는 여러 개념이 있습니다.

알파 당량

람다 항에서 정의할 수 있는 동등성의 기본 형태는 알파 동등성입니다.추상화에서 경계 변수의 특정 선택이 (보통) 중요하지 않다는 직관을 포착합니다.예를 들어 λ x.${\displaystyle$ \$lambda$ x$.x}과$λ ${\displaystyle$ \$lambda$ x.$y}$은(는) 알파 등가 람다 항이며 둘 다 동일한 함수(ID 함수)를 나타냅니다.$x{\displaystyle }$ ${\displaystyle x}$ 및$$ $y{\displaystyle }$ ${\displaystyle y}$ 용어는 추상화에 바인딩되어 있지 않으므로 알파와 동등하지 않습니다$$.많은 발표에서 알파 등가 람다 항을 식별하는 것이 일반적입니다.

β-환원을 정의하기 위해서는 다음과 같은 정의가 필요합니다.

자유 변수

항의 자유 변수는 추상화에 구속되지 않는 변수입니다.식의 자유 변수 집합은 귀납적으로 정의됩니다.

• $x{\displaystyle }$ ${\displaystyle x}$의 사용 가능한 변수는 $x{\displaystyle }$ ${\displaystyle x}$뿐입니다$$.
• λ $x$.${\displaystyle$ \$lambda$ x$.t}$의 자유 변수 집합은 t ${\displaystyle$ t$}$의 자유 변수 집합이지만 x$$${\displaystyle$ x}이$($가) 제거되었습니다.
• $t{\displaystyle }$ ${\displaystyle$ $t$$}$$s$${\displaystyle }$ ${\displaystyles$}의 $자유$ $변수$ $집합$은 t {\displaystyle t$}$의 자유 변수 집합과$$ ${\displaystyles}$의 자유 변수 집합의 결합입니다$.$

예를 들어 ID λ ${\displaystyle x.x}$ ${\displaystyle \lambda x.x}$을(를) 나타내는 람다 항에는 사용 가능한 변수가 없지만 함수 λ ${\displaystyle x.y}$ ${\displaystyle \lambda x.y}$ $x$ ${\displaystyle x}$에는 $단일$ 사용 가능한 변수 y ${\displaystyle y}$가 있습니다$.$

캡처 회피 대체

${\displaystyle t$ $s{\displaystyle }$ ${\displaystyle s}$ 및$$ $r{\displaystyle }$ ${\displaystyle r}$이(가) 람다 항이고 $x{\displaystyle }$ ${\displaystyle x}$ 및$$ $y{\displaystyle }$ ${\displaystyle y}$이(가) 변수라고$$ $가정$합니다.$t$[${\displaystyle x:}$=${\displaystyle r]}$ ${\displaystyle t[x$:=$r]}$ 표기는 $캡처$ avoiding $방식$으로 x ${\displaystyle$ x$}$을(를) ${\displaystyle$ r$}$로 $대체했음$을 나타냅니다.이는 다음과 같이 정의됩니다.

• ${\displaystyle x[}$ ${\displaystyle x}$:$=$ ${\displaystyle r}$ ]$=$ r ${\displaystyle$=r]=$r};$ $x$ ${\displaystyle r}$이(가) $x$ ${\displaystyle x}$로 대체되면$$$x$ ${\displaystyle$ x$}$은 r ${\displaystyle$ r$}$이(가) 됩니다.
• ${\displaystyle }$$y$${\displaystyle [}$ ${\displaystyle x}$:$=$ ${\displaystyle r}$ ]${\displaystyle =}$ ${\displaystyle x}$ $≠$ y {\$displaystyle$ $x\neqy};$ r {\$displaystyle$ r}이$($$)$ x {\$displaystyle$ x$}$로 대체된 $경우$$$y ${\displaystyle$ y$}($$x$ ${\displaystyle x}$가 아님) y ${\$displaystyle y}이(가$)$ $y$ {\$displaystyle y}$으로 유지됨
• ${\displaystyle (}$ ${\displaystyle t}$ ${\displaystyle ($${\displaystyle t}$$}$ $s$${\displaystyle }$)${\displaystyle }$[${\displaystyle }$x :$=$ ${\displaystyle r}$ ]$=$( t${\displaystyle }$[${\displaystyle }$${\displaystyle x}$ := ${\displaystyle r}$]${\displaystyle }$)${\displaystyle }$( ${\displaystyle s}$[${\displaystyle }$${\displaystyle x}$ := ${\displaystyle r}$]${\displaystyle }$) ${\displaystyle s$${\displaystyle )}$$[x$${\displaystyle :}$=r]=(${\displaystyle t}$$[x$:=$r])($${\displaystyle s}$$[x$:=$r])};$ 대체는 응용 프로그램의 양쪽에 배포됩니다.
• ${\displaystyle }$(${\displaystyle \lambda }$ ${\displaystyle x}$. ${\displaystyle t}$)${\displaystyle }$[ ${\displaystyle x}$ :$=$ ${\displaystyle ]}$ =$λ$x . ${\displaystyle t}$ ${\displaystyl$ x$.t$=$mbda$ x$.t};$ 추상화로 바인딩된 변수는 대체 대상이 아니며 해당 변수를 대체하면 추상화가 변경되지 않습니다.
• ${\displaystyle }$(${\displaystyle \lambda }$ ${\displaystyle y}$. ${\displaystyle t}$)${\displaystyle [}$ $=$ ${\displaystyle r}$ ${\displaystyle ]}$${\displaystyle =}$ $λ$ y${\displaystyle }$.${\displaystyle }$( t${\displaystyle [}$ ${\displaystyle x}$:= r${\displaystyle }$] )${\$$displaystyle x$$\$$}$$$및 $y$ ${\displaystyle y}$가 $r$ ${\$$displaystyle r}$의 사용 가능한 변수 중에 $나타나지$ 않는 경우 ${\displaystyle y$$}($$y$ {\$displaystyle y}$는 r {\$displaystyle r}$의 "신선"이라고 합니다.$$abs로 구속되지 않는 변수를 대입합니다.트랙션은 $추상화$된 변수 {\$displaystyle y}$이$($가) {\displaystyle $r}$ $대체{\displaystyle }$ 항에 대해 "신선"일 경우 추상화의 본문에서 진행됩니다$.$

예를 들어$,$ (λ ${\displaystyle x}$. x${\displaystyle }$)${\displaystyle }$[ ${\displaystyle y}$ := y ]${\displaystyle }$= λ ${\displaystyle x}$.${\displaystyle }$( ${\displaystyle x}$[ y := y${\displaystyle }$] )${\displaystyle }$=$$λ ${\displaystyle x}$. ${\displaystyle x}$ ${\displaystyle (\$lambda x$.x)[y$:=y]=\lambda $x.$ ($x[y$:=$y])$$=$$\$$lambda$ $x$$.x$ $(($$λ$${\displaystyle x.y}$) x${\displaystyle }$)${\displaystyle }$[ x ${\displaystyle :}$$=$ ${\displaystyle y}$] $=$ (${\displaystyle }$( ($λ$ x${\displaystyle .y}$)${\displaystyle }$[ x ${\displaystyle :}$$=$ ${\displaystyle y}$]${\displaystyle }$)${\displaystyle }$( ${\displaystyle x}$[ ${\displaystyle x}$ ${\displaystyle :}$$=$ $y$]${\displaystyle }$) ( x [ x :$=$ y${\displaystyle }$] ) $=$ ($$$λ$$x$ . y ) {\$displaystyle ((\$$lambda$ x$.y)[x:$$=$$$y]$=$ ((\$lambda$ x$.y)[x:$$=$ y$])$ ($x[x:$$=$ y$])$$=(\lambda$ x$.y)y$

대체가 함수의 의미를 변경하지 않도록 하려면 새로 고침 조건($y{\displaystyle }$ ${\displaystyle y}$가 $r{\displaystyle }$ ${\displaystyle r}$의 자유 변수에 있지 않아야$$ 함$)$이 중요합니다.

예를 들어 새로 고침 조건을 무시하면 오류가 발생할 수 있습니다. ($$λ ${\displaystyle x}$. y${\displaystyle }$)${\displaystyle }$[ ${\displaystyle y}$ := x ]${\displaystyle }$= λ ${\displaystyle x}$. (${\displaystyle y}$[ y := ${\displaystyle x}$] )${\displaystyle }$=$$λ ${\displaystyle x}$ .${\displaystyle x}$ ${\displaystyle (\$lambda $x.y)[y$:= x]=\lambda $x.$ ($y[y$:= $x])$$=\lambda$ x$.x$이렇게 잘못하면 상수 함수 λ ${\displaystyle x.y}$ ${\displaystyle \lambda x.y$}이$($가) ID$$λ x.${\displaystyle \lambda$ x.$x}로$바뀝니다.

일반적으로 신선도 조건을 충족하지 못하면 적합한 새 변수를 사용하여 알파 이름을 먼저 변경하여 해결할 수 있습니다.예를 들어$,$ (λ ${\displaystyle x.y)}$[ ${\displaystyle y}$ := x${\displaystyle }$] ${\displaystyle (\$lambda $x.y)[y$ := x$]}$ 추상화의 이름을 새 $변수$ z$${\$displaystyle z}$로 변경하여$$$($λ z${\displaystyle }$.${\displaystyle y}$) [ ${\displaystyle y}$ :=${\displaystyle x}$ ] = λ${\displaystyle }$z${\displaystyle }$. (${\displaystyle y}$ [ ${\displaystyle y}$ :=${\displaystyle x}$] ) =$$λ ${\displaystyle z}$. x ${\displaystyle (\$lambda z$.y)[y$ := x] =\lambda z. (y[y $:$=$x])$$=\lambda$ z$.x}$이며$,$ 함수의 의미는 치환으로 보존됩니다.

함수가 퍼스트 클래스 시민인 함수형 프로그래밍 언어에서(예: SECD machine#Landin's production 참조), 자유 변수의 캡처를 피하기 위한 변수의 이러한 체계적인 변화는 결과적으로 함수를 반환할 때 오류를 발생시킬 수 있습니다.^[17]

β-환원

β-reduction 규칙은$${\$displaystyle$(\lambda$x.t)$ 형식의 응용 프로그램이$$t[$x{\displaystyle :}$=$]$ {\$displaystyle t[x$:=s$]}$라는 용어로 줄어듭니다$.$$($λ ${\displaystyle x}$. t${\displaystyle }$) ${\displaystyle s}$ → t${\displaystyle }$[ ${\displaystyle x}$ :${\displaystyle }$=${\displaystyle s}$ ]$${\$displaystyle (\$lambda x$.t)s\to$t[x : = s$]}$ 표기는$$(λ x${\displaystyle }$. ${\displaystyle t}$)s$${\$displaystyle$(\lambda$x.t)$$s$} β${\displaystyle }$- t [ x :${\displaystyle }$= ${\displaystyle s}$] {\$displaystyle$ t${\displaystyle [x}$ $:$= s]}을(를) 나타내기 위해 $사용$됩니다$.$ 예를 $들어$ 모든 {\displaystyle $s$${\displaystyle \}}$에 대해$$(λ x${\displaystyle }$. x ${\displaystyle )s}$ = x [ x :$$= s ] = s ${\displaystyle$ (\lambda$$.x)$s\to$ x[x : = s]→ s$}$입니다$.$이는 λ ${\displaystyle x.x}$ ${\displaystyle \lambda x.x}$이(가) 실제로 ID임을 보여줍니다.마찬가지로$,$ (λ x${\displaystyle .y}$)${\displaystyle s}$→${\displaystyle y}$ [ ${\displaystyle x}$:=${\displaystyle s}$ ] = ${\displaystyle y}${\$displaystyle (\$lambda x$.y)s\toy[x$:=s]=$y}$이며$,$ 이는 λ x${\displaystyle .y}$ ${\displaystyle \$lambda x$.y}$가 상수 함수임을 보여줍니다.

람다 미적분학은 하스켈이나 표준 ML과 같은 함수형 프로그래밍 언어의 이상화된 버전으로 보일 수 있습니다. 이 관점에서 β-환원은 계산 단계에 해당합니다.이 단계는 더 이상 줄여야 할 애플리케이션이 남지 않을 때까지 추가적인 β 감소를 통해 반복할 수 있습니다.여기에 제시된 바와 같이 유형화되지 않은 람다 미적분학에서는 이 감소 과정이 종료되지 않을 수 있습니다.예를 들어 ω = (${\displaystyle }$λ ${\displaystyle x}$. ${\displaystyle x}$) (${\displaystyle }$λ x${\displaystyle }$. ${\displaystyle x}$) ${\displaystyle \Omega$ = (\lambda x .${\displaystyle \mathrm{xx}}$$) (\$lambda $x$.${\displaystyle \mathrm{xx}}$$)}$ $\{\backslash$displaystyle \Omega$$= (\lambda ${\displaystyle x}$ .${\displaystyle x}$ ) ${\displaystyle (\backslash }$λ x . ${\displaystyle x}$ )${\displaystyle }$→${\displaystyle }$( ${\displaystyle x}$ :${\displaystyle }$= λ ${\displaystyle x}$ .${\displaystyle }$x ]${\displaystyle }$=${\displaystyle }$( ${\displaystyle x}$[ ${\displaystyle x}$ : = λ ${\displaystyle x}$. ${\displaystyle x}$] )${\displaystyle }$( ${\displaystyle x}$[ x : = λ x${\displaystyle }$. x${\displaystyle }$] )${\displaystyle }$= (${\displaystyle }$λ x . x ) (λ ${\displaystyle x}$. ${\displaystyle x}$)${\displaystyle (\$lambda$x.xx$) $(\$lambda $x.xx)]\to (x[$x:=\lambda x$.$x] = ($x[x$:=\λ x])$xx](x[x:=\lambda x.x])$$=(\lambda$ x$.xx)(\lambda x.xx$즉, 이 용어는 단일 β-환원에서 그 자체로 감소하므로 환원 과정은 절대로 종료되지 않습니다.

유형화되지 않은 람다 미적분학의 또 다른 측면은 서로 다른 종류의 데이터를 구별하지 않는다는 것입니다.예를 들어, 숫자에 대해서만 동작하는 함수를 작성하는 것이 바람직할 수 있습니다.그러나 유형화되지 않은 람다 미적분학에서는 함수가 진리값, 문자열 또는 기타 숫자가 아닌 객체에 적용되는 것을 방지할 수 있는 방법이 없습니다.

형식적 정의

정의.

람다 식은 다음과 같이 구성됩니다.

• 변수 v₁, v₂, ...;
• 추상화 기호 λ(lambda) 및 .(점);
• 괄호()

람다 표현식의 집합인 λ는 유도적으로 정의할 수 있습니다.

1. x가 변수이면 x ∈ λ.
2. x가 변수이고 M이 λ ∈ 이면 (λx).M)∈ λ
3. 만약 M, N ∈ λ이면, (MN) ∈ λ.

규칙 2의 인스턴스를 추상화라고 하고 규칙 3의 인스턴스를 응용 프로그램이라고 합니다.^[18][19]

표기법

람다 식 표기를 깔끔하게 유지하기 위해 일반적으로 다음 규칙이 적용됩니다.

• 가장 바깥쪽 괄호는 (MN) 대신 MN으로 떨어집니다.
• 응용 프로그램은 왼쪽 연관성이 있는 것으로 가정합니다. ((MN) P 대신 MN P를 쓸 수도 있습니다.^[20]
• 모든 변수가 한 글자일 경우 응용 프로그램의 공백이 생략될 수 있습니다. MNP 대신 MNP입니다.^[21]
• 추상화 본문은 가능한 한 오른쪽으로 확장됩니다. λx.MN은 λx.(MN)을 의미하고 ( λx.M)N은 아닙니다.
• λx. λ리. λz 등 일련의 추상화들이 수축되어 있습니다.N은 λxyz로 약칭됩니다.N.^[22][20]

자유 변수 및 경계 변수

추상화 연산자인 λ는 추상화의 본체에서 발생하는 모든 변수를 구속한다고 합니다.추상화의 범위에 속하는 변수는 구속(bound)식 λx.M에서 부분 λx는 종종 바인더라고 불리는데, 이는 변수 x가 λx보다 M 앞에 붙임으로써 결합된다는 것을 암시합니다.다른 모든 변수를 free라고 합니다.예를 들어 λy.xxy 식에서 y는 경계 변수이고 x는 자유 변수입니다.또한 변수는 가장 가까운 추상화에 의해 결합됩니다.다음 예제에서는 식에서 x가 한 번만 발생하면 두 번째 람다인 λx.y( λx.z x)에 의해 결합됩니다.

람다 식의 자유 변수 집합 M은 FV(M)로 표시되며 다음과 같이 항 구조에 대한 재귀로 정의됩니다.

1. FV(x) = {x}, 여기서 x는 변수입니다.
2. FV( λx.M) = FV(M) \ {x}.
3. FV(MN) = FV(M) ∪ FV(N).^[j]

자유 변수가 포함되어 있지 않은 식을 닫혔다고 합니다.닫힌 람다 표현식은 조합자라고도 하며 조합 논리의 항과 같습니다.

축소

람다 식의 의미는 식을 줄이는 방법에 따라 정의됩니다.^[23]

감소에는 세 가지 종류가 있습니다.

• α-convers이온: 경계 변수 변경;
• β-환원: 그들의 주장에 함수를 적용합니다.
• η-환원 : 확장성의 개념을 포착합니다.

우리는 또한 결과적인 동등성에 대해 말합니다. 만약 그것들이 α-변환될 수 있다면, 두 표현식은 α-동등식입니다.β-equivalence 및 η-equivalence는 유사하게 정의됩니다.

redex는 축소 가능한 표현의 줄임말로서 축소 규칙 중 하나에 의해 축소될 수 있는 주제를 말합니다.예를 들어, ( λx.M) N은 M의 x에 대한 N의 치환을 나타내는 β-redex입니다.레덱스가 감소하는 표현을 ( λx)의 감소라고 합니다.M)N은 M[x := N]입니다.

만약 M에서 x가 자유롭지 않다면, λx.Mx도 M의 축약을 가진 η-redex입니다.

α-convers이온

α-convers이온(알파-convers이온)은 때때로 α-renaming으로 알려져 있으며, 결합된 변수 이름을 변경할 수 있습니다.예를 들어, λx.x의 α-변환을 사용하면 λy.y가 생성될 수 있습니다.α 변환에 의해서만 다른 항들을 α 동치라고 합니다.흔히 람다 미적분학을 사용할 때 α-등가 항은 동등한 것으로 간주됩니다.

α 변환에 대한 정확한 규칙은 완전히 사소한 것이 아닙니다.첫째, 추상화를 α 변환할 때 이름이 변경되는 변수는 동일한 추상화에 구속되는 변수만 발생합니다.예를 들어 λx. λx.x.x의 α 변환은 λ리를 초래할 수 있습니다.λx.x.x. 그러나 λ리를 생성할 수 없습니다.λx.y. 후자는 원본과 다른 의미를 갖습니다.이는 가변 음영의 프로그래밍 개념과 유사합니다.

둘째, 변수가 다른 추상화에 의해 포착되는 경우 α 변환이 불가능합니다.예를 들어 λx. λy.x에서 x를 y로 바꾸면 λ리가 발생합니다.전혀 같지 않은 λy.y.

정적 스코프가 있는 프로그래밍 언어에서 α 변환을 사용하여 변수 이름이 포함된 스코프에서 이름을 마스킹하지 않도록 함으로써 이름 확인을 단순화할 수 있습니다(이름 확인을 사소한 것으로 만들려면 α 이름 변경 참조).

De Bruijn 지수 표기법에서 임의의 두 α-등가 항은 구문적으로 동일합니다.

대체

M[x := N]으로 표기된 치환은 식 M에서 변수 x의 모든 자유 발생을 식 N으로 대체하는 과정입니다. 람다 미적분학의 용어에 대한 치환은 다음과 같이 용어의 구조에 대한 재귀로 정의됩니다(참고: x와 y는 변수만이고 M과 N은 람다식입니다).

x[x := N] = N

y[x := N] = y, 만약 x ≠y

(MM)[x:= N] = M[x:= N] M[x:= N]

(λx.M)[x:=N] = λx.M

(λy.M)[x:= N] = λy.(M[x:= N]), x ≠ y 및 y가 FV(N)를 ∉하는 경우 FV에 대해서는 위를 참조하십시오.

추상화로 대체하기 위해서는 때때로 식을 α 변환해야 합니다.예를 들어, ( λx.y)[y := x]가 λx.x로 나타나는 것은 올바르지 않습니다. 대체된 x는 자유 상태여야 했지만 바인딩되었기 때문입니다.이 경우 정확한 치환은 α-당량까지 λz.x입니다.치환은 α-동등치까지 고유하게 정의됩니다.위의 캡처-대체 회피 참조

β-환원

β-환원(beta 감소)은 기능 적용의 개념을 포착합니다.β-환원은 (λx)의 β-환원이라는 치환의 관점에서 정의됩니다.M)N은 M[x := N]입니다.

예를 들어, 2, 7, ×의 일부 부호화를 가정하면, 우리는 다음과 같은 β-환원을 갖습니다: ( λn.n × 2) 7 → 7 × 2.

β-환원은 커리-하워드 동형을 통해 자연적 추론에서 국소적 환원성의 개념과 동일하다고 볼 수 있습니다.

η 환원

η 감소(eta reduction)는 확장성의 개념을 표현하는데, 이 맥락에서 두 함수는 모든 인수에 대해 동일한 결과를 주는 경우에만 동일하다는 것입니다.η-reduction은 x가 f에서 free로 나타나지 않을 때마다 λx.f x와 f 사이에서 변환합니다.

η 감소는 커리-하워드 동형을 통해 자연적 추론에서 국소 완전성의 개념과 동일하다고 볼 수 있습니다.

정상형태와 합류점

유형화되지 않은 람다 미적분학의 경우, 다시 쓰기 규칙으로서 β-환원은 강하게 정규화되지도 않고 약하게 정규화되지도 않습니다.

그러나 α-변환까지 작업할 때 β-환원이 합류한다는 것을 보여줄 수 있습니다(즉, 우리는 하나를 α-변환하는 것이 가능하다면 두 개의 정상 형태가 같다고 생각합니다).

따라서 강한 정규화 항과 약한 정규화 항 모두 고유한 정규 형태를 가집니다.강력하게 정규화된 항의 경우 모든 축소 전략이 정상 형태를 산출하는 것이 보장되는 반면, 약하게 정규화된 항의 경우 일부 축소 전략이 이를 찾지 못할 수 있습니다.

데이터 유형 인코딩

기본 람다 미적분학은 산술, 부울, 데이터 구조 및 재귀를 모델링하는 데 사용될 수 있으며, 이는 다음의 하위 섹션 i, ii, iii 및 § iv에 나와 있습니다.

람다 미적분학의 산술

람다 미적분학에서 자연수를 정의하는 몇 가지 가능한 방법이 있지만, 가장 일반적인 것은 다음과 같이 정의할 수 있는 교회 숫자입니다.

0 : = λf. λx.x

1 : = λf.λx.fx

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

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

등등.또는 표기법에서 위에 제시된 대체 구문을 사용하는 경우:

0 := λfx.x

1 : = λfx.fx

2 : = λfx.f (fx)

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

처치 숫자는 고차 함수로 단일 인수 함수 f를 취하고 다른 단일 인수 함수를 반환합니다.Church number n은 함수 f를 인수로 삼고 f의 n번째 구성, 즉 자신과 n번으로 구성된 함수 f를 반환하는 함수입니다.이 값은 f로⁽ⁿ⁾ 표시되며 실제로 n번째 거듭제곱 off(연산자로 간주됨)입니다. f는⁽⁰⁾ 항등식 함수로 정의됩니다.반복되는 (단일 함수 f의) 구성은 지수의 법칙을 따르므로 이 숫자들이 산술에 사용될 수 있습니다.(Church의 원래 람다 미적분학에서는 람다 식의 공식 매개변수가 함수체에서 적어도 한 번 발생해야 하므로 위의 0 정의가 불가능했습니다.)

프로그램을 분석할 때 종종 유용하게 사용되는 Church number n에 대한 한 가지 사고방식은 '반복적인 시간'을 지시로 하는 것입니다.예를 들어, 아래에 정의된 PAIR 및 NIL 함수를 사용하여 빈 목록에서 시작하여 '다른 x 요소를 사용하여'를 n번 반복함으로써 모두 x와 동일한 n개의 요소의 (연결된) 목록을 구성하는 함수를 정의할 수 있습니다.람다 항은

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

반복되는 기능을 다양하게 변경하고 반복되는 기능이 적용되는 인수를 다양하게 변경하면 매우 다양한 효과를 얻을 수 있습니다.

successor 함수를 정의할 수 있는데, 여기서 '(mf)x'는 함수 'f'가 'x'에 'm'번 적용됨을 의미합니다.

SUC : = λn. λf.λx.f(nfx)

n번째 성분 f로 구성된 m번째 성분 f는 m+n번째 성분 f를 제공하기 때문에 덧셈은 다음과 같이 정의될 수 있습니다.

PLUS := λm. λn. λf.λx.mf (nfx)

PLUS는 두 개의 자연수를 인수로 하고 자연수를 반환하는 함수로 생각할 수 있습니다.

PLUS 23

그리고.

5

는 β- equivalent 람다 식입니다.n에 m을 더하면 1 m을 더하면 될 수 있기 때문에 대안적인 정의는 다음과 같습니다.

PLUS : = λm. λn.m SUCKn^[26]

마찬가지로, 곱셈은 다음과 같이 정의될 수 있습니다.

MULT : = λm. λn. λf.m(nf)^[22]

또는

MULT : = λm. λn.m (PLUS n) 0

m과 n을 곱하는 것은 덧셈 함수 m을 반복한 다음 0에 적용하는 것과 같기 때문입니다.지수화는 교회 숫자로 표현하는 것이 다소 간단합니다.

POW : = λb. λe.e.b^[1]

양의 정수 n과 PED 0 = 0에 대해 PED n = n - 1로 정의된 이전 함수는 훨씬 더 어렵습니다.공식을

PED : = λn. λf.λx.n (λg)λh.h(gf))( λu.x)( λu.u)

T가 ( λg)를 나타내는 경우를 유도적으로 보여줌으로써 검증할 수 있습니다.n > 0인 경우 λh.h(gf), 그 다음 T( λu.x) = ( λh.h(f(x))).PRED에 대한 다른 두 가지 정의가 아래에 제시되어 있는데, 하나는 조건을 사용하고 다른 하나는 쌍을 사용합니다.이전 함수에서는 뺄셈이 간단합니다.정의하기

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

Submn은 m > n일 때 m - n을 산출하고, 그렇지 않으면 0을 산출합니다.

논리와 술어

부울 값 TRUE 및 FALSE에는 관례적으로 다음 두 가지 정의(Church booleans라고 함)가 사용됩니다.

TRUE := λx. λy.x

FALSE : = λx. λy.y

그런 다음, 이 두 람다 항을 사용하여 몇 가지 논리 연산자를 정의할 수 있습니다. (이것들은 단지 가능한 공식일 뿐이며, 다른 식들도 똑같이 정확할 수 있습니다.)

AND := λp. λq.pq p

OR : = λp. λq.p q

아님 := λp.p FALSE TRUE

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

이제 다음과 같은 몇 가지 논리 함수를 계산할 수 있습니다.

진정한 거짓

≡ (λ 페이지 λq.p q p) TRUE FALSE → TRUE FALSE TRUE

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

그리고 우리는 진정한 거짓이 거짓과 동일하다는 것을 알고 있습니다.

술어는 부울 값을 반환하는 함수입니다.가장 기본적인 술어는 ISZERO로, 인수가 교회 번호 0이면 TRUE를 반환하고, 인수가 다른 교회 번호이면 FALSE를 반환합니다.

ISZERO : = λn.n ( λx).거짓) 참

다음 술어는 첫 번째 인수가 두 번째 인수보다 작거나 같은지 여부를 검정합니다.

LEQ := λm. λn.ISZERO(서브맨),

그리고 m = n이므로 LEQ mn과 LEQ nm인 경우 수치 동치를 위한 술어를 구축하는 것은 간단합니다.

술어의 사용 가능성과 TRUE 및 FALSE의 위 정의는 람다 미적분학에서 "if-then-else" 식을 편리하게 쓸 수 있게 해줍니다.예를 들어, 이전 함수는 다음과 같이 정의될 수 있습니다.

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

n(예: λk)을 귀납적으로 보여줌으로써 확인할 수 있습니다.ISZERO (g 1) k (PLUS (g k 1)) ( λv.0)은 n > 0에 대한 n - 1 함수입니다.

쌍들

쌍(2-튜플)은 쌍에 대한 Church 인코딩을 사용하여 TRUE 및 FALSE로 정의할 수 있습니다.예를 들어 PAIR은 쌍(x,y)을 캡슐화하고 FIRST는 쌍의 첫 번째 요소를 반환하며 Second는 두 번째 요소를 반환합니다.

Pair : = λx. λy. λf.fxy

FIRST := λp.p TRUE

두번째 : = λp.p FALSE

NIL := λx.TRUE

NULL := λp.p(λx. λ리).거짓)

링크된 목록은 빈 목록에 대한 NIL 또는 요소와 작은 목록의 쌍으로 정의될 수 있습니다.술어 NULL은 NIL 값에 대해 테스트합니다. (또는 NIL := FALSE인 경우에는 구성 l(λh. λt. nilz.deal_with_head_h_and_tail_t)(deal_with_λ)로 명시적 NULL 테스트가 필요하지 않습니다.

쌍을 사용하는 예로서, (m, n)을 (n, n + 1)에 매핑하는 시프트 및 증가 함수는 다음과 같이 정의될 수 있습니다.

φ := λx.쌍(두 번째 x)(SUCC(두 번째 x))

이것은 아마도 가장 투명한 버전의 이전 함수를 제공할 수 있게 해줍니다.

PED : = λ어.먼저(N φ(페어 0)).

부가적인 프로그래밍 기법

람다 미적분학의 프로그래밍 숙어는 상당히 많습니다.이 중 많은 것들은 원래 람다 미적분학을 프로그래밍 언어 의미론의 기초로 사용하면서 낮은 수준의 프로그래밍 언어로서 람다 미적분학을 효과적으로 사용하는 맥락에서 개발되었습니다.여러 프로그래밍 언어에는 람다 미적분학(또는 매우 유사한 것)이 조각으로 포함되어 있기 때문에 이러한 기법은 실제 프로그래밍에서도 사용할 수 있지만 모호하거나 이질적인 것으로 인식될 수 있습니다.

명명 상수

람다 미적분학에서, 라이브러리는 이전에 정의된 함수들의 집합의 형태를 취할 것이고, 람다 항들은 단지 특정 상수들이기 때문입니다.순수 람다 미분적분학은 모든 원자 람다항이 변수이기 때문에 명명된 상수의 개념이 없지만, 추상화를 사용하여 변수를 상수의 이름으로 설정하고 해당 변수를 본체에 바인딩하고 해당 추상화를 의도된 정의에 적용함으로써 명명된 상수를 에뮬레이션할 수 있습니다.따라서 f를 M(다른 람다 항, "주 프로그램")에서 N(일부 명시적 람다 항)을 의미하는 데 사용하면 다음과 같이 말할 수 있습니다.

(λ프.M) N

저자들은 더 직관적인 순서로 위의 글을 쓰는 것을 허용하기 위해 종종 ^[k]let과 같은 통사적 설탕을 소개합니다.

놓아주다 =N인에M

이러한 정의를 체인하면 람다 미적분학 "프로그램"을 0 이상의 함수 정의로 작성한 다음 프로그램의 본체를 구성하는 함수를 사용하여 람다 항 하나를 작성할 수 있습니다.

이 let의 주목할 만한 제한은 이름 f가 N에서 정의되지 않는다는 것이며, N이 추상 바인딩 f의 범위 밖에 있다는 것입니다. 이는 재귀 함수 정의를 N let으로 사용할 수 없음을 의미합니다.레트렉^[l] 구성을 사용하면 재귀 함수 정의를 쓸 수 있습니다.

재귀점 및 고정점

재귀는 함수 자체를 사용하여 함수를 정의하는 것입니다.자신의 내면에 자신을 포함하는 정의는, 가치에 의해, 전체 가치가 무한한 크기가 되게 합니다.재귀를 지원하는 다른 표기법들은 기본적으로 이름에 의한 함수 정의를 참조함으로써 이를 극복합니다.람다 미적분학은 이것을 표현할 수 없습니다. 모든 함수는 람다 미적분학에서 익명이기 때문에 우리는 그 같은 값을 정의하는 람다 항 안에서 아직 정의되지 않은 값을 이름으로 언급할 수 없습니다.그러나 람다 식을 ( λx.x) E와 같이 자체 인수로 사용할 수 있습니다.여기서 E는 재귀를 표현하기 위한 값에 매개 변수를 적용하는 추상화여야 합니다.

다음과 같이 재귀적으로 정의되는 요인 함수 F(n)를 고려합니다.

F(n) = 1, n = 0인 경우, 그렇지 않으면 n × F(n - 1).

이 함수를 나타내는 람다 식에서 매개 변수(일반적으로 첫 번째 것)는 람다 식 자체를 값으로 수신한다고 가정하므로 이를 호출하여 인수에 적용하면 재귀가 됩니다.따라서 재귀를 달성하려면 (여기서는 r이라 함) 자체 참조 인수를 항상 호출 지점에서 함수 본문 내의 자체로 전달해야 합니다.

G : = λr. λn. (1, n = 0인 경우, 그 외 n × (r(n-1))

r x = F x = G x를 보유한 경우, sor = G 및

F := GG = (λx.xx) G

자체 응용 프로그램은 여기서 복제를 수행하여 함수의 람다 식을 인수 값으로 다음 호출에 전달하여 참조하고 호출할 수 있게 합니다.

이렇게 하면 문제가 해결되지만 각 재귀적 호출을 자체 응용 프로그램으로 다시 작성해야 합니다.다시 쓸 필요 없이 포괄적인 솔루션을 제공하고 싶습니다.

G : = λr. λn.(1, n = 0인 경우, 그 외 n × (r(n-1))

r x = F x = Gr x를 보유할 경우 sor = Gr =: FIX Gand

F : = FIX g : = (r = gr) = g (FIX g)

FIX G = G (FIX G) = (1, n = 0인 경우, 그 외 n × (FIX G) (n-1))가 되도록 합니다.

재귀적 호출을 나타내는 첫 번째 인수를 갖는 람다 항이 주어지면(예: 여기서 G), 고정점 조합기 FIX는 재귀적 함수를 나타내는 자기 복제 람다 식을 반환합니다(여기서 F).이 기능은 자기 복제가 생성될 때마다 미리 준비되어 호출될 때마다 수행되기 때문에 어느 시점에서든 자신에게 명시적으로 전달될 필요가 없습니다.따라서 원래의 람다 식(FIXG)은 콜 포인트에서 자체적으로 다시 생성되어 자체 참조를 달성합니다.

실제로 이 FIX 연산자에 대해 가능한 정의는 여러 가지가 있으며, 그 중 가장 간단한 것은 다음과 같습니다.

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

람다 미적분학에서 Yg는 g의 고정점이며, 다음과 같이 확장됩니다.

Y g

(λ h.(λ x.h(x x))(λ x.h(x x)) g

(λx.g(xx))(λx.g(xx))

g ((λx.g(xx))(λx.g(xx))

g (Yg)

이제 요인 함수에 대한 재귀적 호출을 수행하기 위해 단순히 (YG) n을 호출하고, 여기서 n은 요인을 계산하는 숫자입니다.예를 들어 n = 4 가 주어졌을 때 다음을 얻을 수 있습니다.

(YG) 4

G (YG) 4

(λr. λn.(1, n = 0인 경우, 기타 n × (r(n-1)))) (YG) 4

(λn.(1, n = 0인 경우, 또는 n × ((YG))(n-1)))) 4

1, 4 = 0이면 4 × ((YG) (4-1))

4x(G(YG)(4-1))

4 × (((λn.1, n = 0인 경우, 그 외 n × ((YG))(n-1)))) (4-1))

4 × (1, 3 = 0인 경우, 3 × ((YG)) (3-1))

4x(3x(G(YG))(3-1))

4 × (((n = 0인 경우 λn(1)), 그 외 n × (((YG))(n-1))))

4 × (3 × (1, 2 = 0인 경우, 2 × ((YG)) (2-1)))

4 × (3 × (2 × (G(YG))(2-1)))

4 × (3 × (2 × ((n = 0인 경우 λn(1)), 그 외 n × (((YG))(n-1))))))

4 × (3 × (2 × (1, 1 = 0이면), 그 외 1 × ((YG)) (1-1)))

4 × (3 × (2 × (1 × (G(YG))(1-1))))

4 × (2 × (1 × ((n = 0인 경우 λn(1)), 그 외 n × (((YG))(n-1))))))

4 × (3 × (2 × (1 ×, 0 = 0인 경우에는 1 ×, 그 외에는 0 × ((YG)))))

4 × (3 × (2 × (1 × (1))))

24

재귀적으로 정의된 모든 함수는 추가 인수가 있는 재귀적 호출 위에 닫히는 일부 적합하게 정의된 함수의 고정점으로 볼 수 있으므로 Y를 사용하면 재귀적으로 정의된 모든 함수를 람다 식으로 표현할 수 있습니다.특히, 이제 자연수의 뺄셈, 곱셈, 비교 술어를 재귀적으로 깨끗하게 정의할 수 있습니다.

표준항

어떤 용어들은 일반적으로 허용되는 이름을 가지고 있습니다:^[28][29][30]

I := λx.x

S := λx. λ리. λz.x z (yz)

K := λx. λy.x

B : = λx. λ리. λz.x(yz)

C : = λx. λ리. λz.xzy

W := λx. λy.xyyy

ω 또는 δ 또는 U := λx.xx

ω :=

아이덴티티 함수입니다.SK와 BCKW는 모든 람다 항을 표현할 수 있는 완전한 조합 연산 시스템을 구성합니다. 다음 섹션을 참조하십시오.ω는 UU로, 정상적인 형태가 없는 가장 작은 용어입니다.YI는 또 다른 그런 용어입니다.Y는 표준이고 위에서 정의되며, Y=BU(CBU)로 정의될 수 있으므로 Yg=g(Yg)가 됩니다.위에서 정의한 TRUE와 FALSE는 일반적으로 T와 F로 약칭됩니다.

추상제거

N이 추상화되지 않은 람다 항이지만 명명된 상수(결합자)를 포함할 가능성이 있는 경우 λx와 같은 람다 항 T(x,N)가 존재합니다.N이지만 추상화가 부족합니다(비원자로 간주되는 경우 명명된 상수의 일부는 제외).T(x,N)가 N에서 발생하는 모든 x를 제거하는 동시에 N이 x를 포함하는 위치에 인수 값을 대입할 수 있기 때문에 이는 익명 변수로 볼 수도 있습니다.변환 함수 T는 다음과 같이 정의할 수 있습니다.

T(x,x) := I

T(x, N) := N에서 x가 자유롭지 않은 경우 KN.

T(x,MN) := ST(x,M) T(x,N)

어느 경우든 T(x,N) P 형태의 항은 ( λx)의 β-감소와 마찬가지로 초기 조합자 I, K 또는 S가 인수 P를 잡음으로써 감소할 수 있습니다.NP라면 좋습니다.저는 그 논쟁에 답을 드립니다.K는 ( λx)처럼 논쟁을 버립니다.Nn.S.에서 x가 자유롭게 발생하지 않는 경우에 할 것입니다. S는 두 응용 프로그램의 두 부분에 인수를 전달한 다음 첫 번째 결과를 두 번째 결과에 적용합니다.

조합자 B와 C는 S와 비슷하지만, 인수를 응용 프로그램의 한 부분항에만 전달합니다(B는 "논증" 부분항에, C는 "함수" 부분항에 전달). 따라서 한 부분항에 x가 발생하지 않으면 후속 K를 저장합니다.B와 C와 비교하여, S 결합기는 실제로 두 가지 기능을 통합합니다: 인수를 재정렬하는 것과 인수를 복제하여 두 곳에서 사용할 수 있도록 하는 것입니다.W 콤비네이터는 후자만 수행하며, SKI 콤비네이터 미적분학의 대안으로 B, C, K, W 시스템을 산출합니다.

유형 람다 미적분

유형화된 람다 미적분학은 익명 함수 추상화를 나타내기 위해 람다 기호(λ ${\displaystyle \lambda$를 사용하는 유형화된 형식주의입니다.이러한 맥락에서 유형은 일반적으로 람다 항에 할당되는 통사적 성격의 개체입니다. 유형의 정확한 성격은 고려되는 미적분학에 따라 달라집니다(유형 유형 람다 계산 참조).특정한 관점에서, 유형화된 람다 연산은 유형화되지 않은 람다 연산의 개선으로 볼 수 있지만, 다른 관점에서, 더 기본적인 이론과 유형화되지 않은 람다 연산은 한 가지 유형만 있는 특별한 경우로 간주될 수도 있습니다.^[31]

Lambda calci는 기본 프로그래밍 언어이며 ML 및 Haskell과 같은 유형의 함수 프로그래밍 언어와 간접적으로 명령형 프로그래밍 언어의 기본입니다.유형화된 람다 계산은 프로그래밍 언어를 위한 유형 시스템 설계에 중요한 역할을 합니다. 여기서 유형화는 일반적으로 프로그램의 바람직한 속성을 캡처합니다. 예를 들어, 프로그램이 메모리 액세스 위반을 일으키지 않습니다.

형식화된 람다 연산은 커리-하워드 동형화를 통해 수학적 논리 및 증명 이론과 밀접한 관련이 있으며, 단순히 형식화된 람다 연산은 데카르트 닫힌 범주(CCC)의 언어와 같은 범주 클래스의 내부 언어로 간주될 수 있습니다.

감축전략

항이 정규화되는지 여부와 정규화되는 경우에 얼마나 많은 작업을 수행해야 하는지는 사용되는 축소 전략에 크게 의존합니다.일반적인 람다 미적분학 감소 전략은 다음과 같습니다.^[32][33][34]

정상순서

가장 왼쪽, 가장 바깥쪽의 리덱스는 항상 먼저 감소합니다.즉, 가능할 때마다 인수가 축소되기 전에 인수가 추상화 본문에 대체됩니다.

적용순서

가장 왼쪽, 가장 안쪽의 레덱스는 항상 먼저 감소합니다.직관적으로 이것은 함수의 인수가 항상 함수 자체보다 먼저 감소된다는 것을 의미합니다.적용 순서는 기능이 불가능한 경우에도 항상 정상 형태에 기능을 적용하려고 시도합니다.

완전 β-환원

언제라도 모든 리덱스를 줄일 수 있습니다.이는 근본적으로 특정 감축 전략이 없음을 의미합니다. 감축 가능성과 관련해서는 "모든 베팅이 중단"됩니다.

약한 감소 전략은 람다 추상화 하에서 감소하지 않습니다.

값별호출

레덱스는 오른쪽이 값(변수 또는 추상화)으로 감소한 경우에만 감소합니다.가장 바깥쪽의 리덱스만 줄어듭니다.

호명

정상적인 순서이지만 추상화 내부에서는 축소가 수행되지 않습니다.예를 들어, λx.( λy.y)x는 이 전략에 따라 정상 형태이지만, redex ( λy.y)x를 포함합니다.

공유를 사용하는 전략은 "동일한" 병렬 연산을 줄입니다.

최적감축

정상적인 순서이지만 레이블이 동일한 계산은 동시에 줄어듭니다.

필요에 따라 전화하기

이름으로 호출하는 경우(따라서 약함) 대신 용어를 복제하는 함수 응용 프로그램에서 인수 이름을 지정한 다음 "필요할 때"만 줄어듭니다.

계산가능성

두 람다 식을 입력으로 받아 한 식을 다른 식으로 축소하는지 여부에 따라 TRUE 또는 FALSE를 출력하는 알고리즘은 없습니다.^[12]더 정확하게 말하면, 어떤 계산 가능한 함수도 문제를 결정할 수 없습니다.이것은 역사적으로 결정 불가능성이 입증될 수 있는 첫 번째 문제였습니다.그러한 증명에서 보통처럼, 계산 가능한 것은 튜링이 완료된 모든 계산 모델에 의해 계산 가능한 것을 의미합니다.실제로 계산 가능성은 람다 미적분학을 통해 정의될 수 있습니다. 자연수의 함수 F: N → N은 모든 x 쌍에 대해 N에 y, F(x)= y인 람다 식 f가 존재하는 경우에만 계산 가능한 함수이며, 여기서 x와 y는 x와 y에 대응하는 교회수이고,β-환원과의 동등성을 의미하는 =.계산 가능성과 동등성을 정의하는 다른 접근법에 대해서는 Church-Turing 논문을 참조하십시오.

Church의 계산 불가능성 증명은 먼저 주어진 람다 식이 정상적인 형태를 갖는지 여부를 결정하는 것으로 문제를 줄입니다.그런 다음 그는 이 술어가 계산 가능하므로 람다 미적분학으로 표현할 수 있다고 가정합니다.클라인의 초기 연구를 기반으로 람다 식에 대한 괴델 번호를 구축하여, 그는 괴델의 첫 번째 불완전성 정리의 증명을 바짝 따르는 람다 식 e를 구축합니다.만약 e가 자신의 괴델 수에 적용된다면, 모순이 발생합니다.

복잡성

람다 미적분학에 대한 계산 복잡도의 개념은 다소 까다롭습니다. 왜냐하면 β-감소의 비용은 그것이 어떻게 구현되느냐에 따라 달라질 수 있기 때문입니다.^[35]정확히 말하면, 식 E에서 경계 변수 V의 모든 발생 위치를 어떻게든 찾아야 하며, 이는 시간 비용을 의미하거나, 또는 공간 비용을 의미하는 어떤 방식으로든 자유 변수의 위치를 추적해야 합니다.E에서 V의 위치에 대한 ï브 검색은 E의 길이 n에서 O(n)입니다.디렉터 스트링은 2차 공간 사용을 위해 이 시간 비용을 거래한 초기 접근 방식이었습니다.^[36]보다 일반적으로 이것은 명백한 대체를 사용하는 시스템에 대한 연구로 이어졌습니다.

2014년, 항을 줄이기 위해 정상적인 순서 감소에 의해 수행된 β-감소 단계의 수가 합리적인 시간 비용 모델인 것으로 나타났습니다. 즉, 단계 수에 다항식으로 비례하는 시간에 튜링 기계에서 감소를 시뮬레이션할 수 있습니다.^[37]이것은 각각의 β-환원에 대해 기하급수적으로 크기가 증가하는 람다 용어의 존재, 크기 폭발로 인해 오랫동안 열린 문제였습니다.결과는 컴팩트한 공유 표현으로 작업함으로써 이 문제를 해결할 수 있습니다.결과적으로 람다 항을 평가하는 데 필요한 공간의 양이 감소 중에 항의 크기에 비례하지 않음을 알 수 있습니다.우주의 복잡성을 측정하는 데 얼마나 적합한지는 현재 알려져 있지 않습니다.^[38]

비합리적인 모형이라고 해서 반드시 비효율적인 것은 아닙니다.최적의 감소는 동일한 레이블을 가진 모든 계산을 한 단계에서 감소시켜 중복 작업을 방지하지만, 주어진 항을 정상 형태로 줄이기 위한 병렬 β-감소 단계의 수는 항의 크기에서 거의 선형적입니다.이것은 너무 작아서 합리적인 비용 측정치가 될 수 없습니다. 왜냐하면 어떤 튜링 기계도 튜링 기계의 크기에 선형적으로 비례하는 크기로 람다 미적분학에서 인코딩될 수 있기 때문입니다.람다 항을 감소시키는 진정한 비용은 β-환원 그 자체 때문이 아니라 β-환원 동안 레진스의 중복을 처리하기 때문입니다.^[39]정상적인 형태로 가는 최좌측 단계의 수와 같은 합리적인 비용 모델과 관련하여 측정할 때 최적의 감축 이행이 합리적인지 여부는 알 수 없습니다.그러나 람다 미적분학의 조각들에 대해서는 최좌측 outermost에 비해 최적의 감소 알고리즘이 효율적이고 기껏해야 2차적 오버헤드를 갖는 것으로 나타났습니다.또한 최적 감소의 BOHM 프로토타입 구현은 순수 람다 조건에서 Caml Light와 Haskell 모두를 능가했습니다.^[39]

람다 미적분학 및 프로그래밍 언어

피터 랜딘(Peter Landin)의 1965년 논문 "ALGOL 60과 Church's Lambda-notation 사이의 대응"에 의해 지적된 바와 같이,^[40] 순차적 절차 프로그래밍 언어는 절차 추상화 및 절차(하위 프로그램) 적용을 위한 기본 메커니즘을 제공하는 람다 미적분학의 관점에서 이해될 수 있습니다.

익명 함수

예를 들어, 파이썬에서 "제곱" 함수는 다음과 같이 람다 식으로 표현할 수 있습니다.

(람다 x: x**2) 

위의 예는 1등급 함수를 평가하는 표현입니다.기호를lambda매개변수 이름 목록이 주어진 익명 함수를 만듭니다.x– 이 경우에는 단지 하나의 논증, 그리고 그 함수의 본문으로 평가되는 표현,x**2. 익명 함수를 람다 표현식이라고 부르기도 합니다.

예를 들어, 파스칼과 다른 명령어들은 함수 포인터의 메커니즘을 통해 다른 서브프로그램에 인수로서 서브프로그램을 전달하는 것을 오랫동안 지원해 왔습니다.그러나 함수 포인터는 런타임에 함수의 새 인스턴스를 생성할 수 있는 경우에만 함수가 첫 번째 클래스 데이터 유형이기 때문에 함수가 첫 번째 클래스 데이터 유형이 되기에 충분하지 않은 조건입니다.이러한 런타임 함수 생성은 Smalltalk, JavaScript 및 Wolfram Language에서 지원되며, 최근에는 Scala, Eiffel(에이전트), C#(대의원), C++11 등에서 지원됩니다.

병렬성과 동시성

람다 미적분학의 Church-Roser 성질은 평가(β-reduction)를 어떤 순서로든, 심지어 병행하여 수행할 수 있음을 의미합니다.이는 다양한 비결정적 평가 전략이 관련이 있음을 의미합니다.그러나 람다 미적분학은 평행성에 대한 명확한 구성을 제공하지 않습니다.람다 연산에 Future와 같은 구문을 추가할 수 있습니다.의사소통과 동시성을 설명하기 위한 다른 프로세스 계산법이 개발되었습니다.

의미론

람다 미적분학 항들이 다른 람다 미적분학 항들과 심지어 그들 자신에 대해서도 함수로 작용한다는 사실은 람다 미적분학의 의미론에 대한 의문으로 이어졌습니다.람다 미적분학 용어에 의미를 부여할 수 있습니까?자연적 의미론은 함수 공간 D → D와 동형인 집합 D를 찾는 것이었습니다.그러나 D가 단일 톤 집합이 아닌 한, D에서 D까지의 모든 함수의 집합이 D보다 더 큰 카디널리티를 갖기 때문에 카디널리티 제약에 의해 그러한 중요하지 않은 D가 존재할 수 있습니다.

1970년대에 데이나 스콧은 연속 함수만 고려하면 필요한 성질을 가진 집합 또는 도메인 D를 찾을 수 있다는 것을 보여주었고 따라서 람다 미적분학의 모델을 제공했습니다.^[41]

이 작업은 또한 프로그래밍 언어의 표기 의미론의 기초를 형성했습니다.

변형 및 확장

이러한 확장은 람다 큐브에 있습니다.

• 유형화된 람다 미적분 – 유형화된 변수(및 함수)가 있는 람다 미적분
• 시스템 F – 유형 변수가 있는 유형 람다 미적분
• 구성 미적분 – 유형이 1등급 값인 유형의 람다 미적분

이러한 공식 시스템은 람다 큐브에 없는 람다 미적분학의 확장입니다.

• 이진 람다 미적분학 – 이진 I/O, 이진 인코딩 및 지정된 범용 기계가 포함된 람다 미적분학 버전입니다.
• 람다-무 미적분 – 고전 논리를 처리하기 위한 람다 미적분의 확장

이러한 형식 체계는 람다 미적분학의 변형입니다.

• 카파 미적분 – 람다 미적분의 1차 유사체

다음과 같은 형식 체계는 람다 미적분학과 관련이 있습니다.

• 조합 논리 – 변수가 없는 수학적 논리에 대한 표기법
• SKI 콤비네이터 미적분학 – S, K, I 콤비네이터를 기반으로 한 계산 시스템으로, 람다 미적분학과 동일하지만 변수 치환 없이 축소 가능

참고 항목

추가열람

• 아벨슨, 해롤드 & 제럴드 제이 서스먼.컴퓨터 프로그램의 구조와 해석MIT 프레스지. ISBN0-262-51087-1.
• Barendregt, Hendrik Pieter 람다 미적분학 입문
• Barendregt, Hendrik Pieter, 논리학과 컴퓨터 과학에서 람다 미적분학의 영향.기호논리학보 제3권 제2호, 1997년 6월
• Barendregt, Hendrik Pieter, 수학적 논리학 핸드북의 유형 자유 람다 미적분학 pp1091–1132, North-Holland (1977) ISBN 0-7204-2285-X
• 카돈과 힌들리, 2006.Lambda-calculus and Combinatory Logic의 역사Gabbay and Woods (eds.), 논리학사 핸드북, vol. 5. Elsevier
• Church, Alonzo, 풀 수 없는 문제의 초등수 이론, American Journal of Mathematics, 58(1936), pp. 345-363이 문서에는 람다 식의 등가성이 일반적으로 결정할 수 없다는 증거가 포함되어 있습니다.
• Church, Alonzo (1941). The Calculi of Lambda-Conversion. Princeton: Princeton University Press. Retrieved 2020-04-14. (ISBN 978-0-691-08394-0)
• Frink Jr., Orrin (1944). "Review: The Calculi of Lambda-Conversion by Alonzo Church" (PDF). Bull. Amer. Math. Soc. 50 (3): 169–172. doi:10.1090/s0002-9904-1944-08090-7.
• Cleene, Stephen, 형식논리학의 양의 정수론, American Journal of Mathematics, 57(1935), pp. 153–173, 219–244익숙한 여러 함수의 람다 미적분 정의가 들어 있습니다.
• Landin, Peter, A Correspondence Between ALGOL 60 and Church's Lambda-Notation, Communications of the ACM, vol. 8, no. 2(1965), 89-101페이지ACM 사이트에서 사용 가능합니다.프로그래밍 언어의 기초로서 람다 미적분학의 중요성을 강조하는 고전 논문.
• Larson, Jim, Lambda 미적분학과 체계에 대한 소개.프로그래머를 위한 간단한 소개.
• Michaelson, Greg (10 April 2013). An Introduction to Functional Programming Through Lambda Calculus. Courier Corporation. ISBN 978-0-486-28029-5.^[42]
• Schalk, A. and Simmons, H. (2005) 적당한 운동 선택과 함께 λ-계산과 산술에 대한 소개. 맨체스터 대학 수학 논리학 MSC 과정 노트
• de Queiroz, Ruy J.G.B. (2008). "On Reduction Rules, Meaning-as-Use and Proof-Theoretic Semantics". Studia Logica. 90 (2): 211–247. doi:10.1007/s11225-008-9150-5. S2CID 11321602. 증명에 기초하더라도 의미를 부여하는 규칙으로 환원을 취하기 때문에 덤멧-프라위츠 전통에서와 같은 증명이론적 의미론과는 다른 '의미-사용' 개념을 공식적으로 뒷받침하는 논문.
• Hankin, Chris, 컴퓨터 과학자를 위한 Lambda Calculi 소개 ISBN 0954300653

대학원생용 모노그래프/교과서

• Sørensen, Morten Heine 및 Urzyczyn, Paweł(2006), Curry-Howard 동형 사상에 대한 강의, Elsevier, ISBN 0-444-52077-5는 순수 유형 시스템 및 람다 큐브와 같은 보다 최근의 개발을 포함하여 유형이 없는 다양성에서 대부분의 유형의 람다 연산에 대한 주요 주제를 다루는 최근 모노그래프입니다.하위 입력 확장은 다루지 않습니다.
• Pierce, Benjamin (2002), Types and Programming Languages, MIT Press, ISBN 0-262-16209-1 는 실용적인 유형의 시스템 관점에서 람다 계산을 다룹니다. 종속 유형과 같은 일부 항목만 언급되지만 하위 유형은 중요한 항목입니다.

문서.

• 정아침의 람다 미적분학-(PDF)에 대한 간략한 소개
• 다나 스콧의 람다 미적분학-(PDF) 연대표
• 라울 로하스의 람다 미적분학 튜토리얼 소개-(PDF)
• 람다 미적분학 강의 노트-(PDF), Peter Selinger
• 마리우스 불리가의 그림 람다 미적분학
• Peter Kelly, Paul Coddington 및 Andrew Wendelborn의 워크플로우 모델로서의 람다 미적분학은 람다 식을 평가하는 일반적인 방법으로 그래프 감소를 언급하고 분산 컴퓨팅에 대한 람다 미적분학의 적용 가능성에 대해 논의합니다(람다 식에 대한 병렬 그래프 감소를 가능하게 하는 Church-Roser 속성으로 인해).

메모들

참고문헌

이 기사의 일부 부분은 허가를 받아 사용된 FOLDOC의 자료를 바탕으로 합니다.