표현으로 하자

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "표현 허용" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2017년 3월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

컴퓨터 과학에서 "let" 표현은 함수 정의를 제한된 범위와 연관시킨다.

"let" 표현식은 부울 조건을 제한된 범위와 연관시키는 수학에서도 정의될 수 있다.

"let" 표현은 값에 적용되는 람다 추상화로 간주될 수 있다.수학 내에서, 레트 표현은 또한 변수의 범위를 제한하는 실존적 계량기 내에서 표현들의 결합으로 간주될 수 있다.

다른 식을 정의하는 데 사용할 수 있도록 표현식의 로컬 정의를 허용하기 위해 여러 기능 언어로 표현식이 존재한다.let-expression은 let 또는 "let rec"의 두 가지 형태로 기능 언어에 존재한다.Let rec는 반복을 구현하기 위해 고정 포인트 결합기를 사용하는 단순 허용 표현식의 확장이다.

역사

다나 스콧의 LCF 언어는^[1] 람다 미적분이 현대 기능 언어로 진화하는 단계였다.이 언어는 그 때부터 대부분의 기능 언어에서 나타난 레트 표현을 소개했다.

언어 체계,^[2] ML, 그리고 더 최근에 Haskell은^[3] LCF로부터 레트 표현을 물려받았다.

ALGOL과 Pascal과 같은 상태 저장 명령어는 기능의 제한된 범위를 블록 구조로 구현하기 위해 기본적으로 Let 식을 구현한다.^{[citation needed]}

그 재귀 변종인 "where rec"와 밀접하게 연관된 "where" 조항은 이미 피터 랜딘의 표현에 대한 기계적 평가에 등장했다.^[4]

설명

"let" 표현식은 다른 표현식에서 사용하기 위한 함수 또는 값을 정의한다.많은 기능 프로그래밍 언어에서 사용되는 구조일 뿐만 아니라, 그것은 수학적인 텍스트에서 자주 사용되는 자연 언어 구조다.그것은 where 절에 대한 대체 구문이다.

표현으로 하자	Where 절
내버려두다 ${\displaystyle a=3}$ 그리고 $(\displaystyle b=4}$ 에 ${\displaystyle {\sqrt {a^{2}+b^{2}}}}}$	${\displaystyle {\sqrt {a^{2}+b^{2}}}}}$ 어디에 ${\displaystyle a=3}$ 그리고 $(\displaystyle b=4}$

두 경우 모두 전체 구문은 값이 5인 식입니다.if-ten-else와 마찬가지로 식에서 반환되는 형식이 반드시 부울 형식은 아니다.

표현은 4가지 주요 형태로 나타난다.

형태	그리고	재귀적	정의/제약	설명
심플	아니요.	아니요.	정의	단순 비재귀 함수 정의.
재귀적	아니요.	네	정의	재귀 함수 정의(Y 콤비네이터를 사용하여 구현됨).
상호	네	네	정의	상호 재귀 함수 정의.
수학적	네	네	제약	일반 부울 허용 조건을 지원하는 수학 정의.

기능 언어에서 let 표현식은 표현에서 호출될 수 있는 함수를 정의한다.함수 이름의 범위는 let 표현 구조로 제한된다.

수학에서 let 표현은 조건을 정의하는데, 이것은 표현에 제약이 된다.구문은 또한 let 표현에 국소적으로 실존적으로 정량화된 변수의 선언을 지지할 수 있다.

용어, 구문, 의미론 등은 언어마다 다르다.체계에서 let은 단순한 형태에 사용되며 recurration 형태에 대해 roc를 사용한다.ML에서는 함수 정의의 시작을 재미있게 표시하면서 선언 블록의 시작만 표시하도록 한다.하스켈에서는 컴파일러가 무엇이 필요한지 알아내면서 상호 재귀적일 수 있다.

정의

람다 추상화는 이름이 없는 함수를 나타낸다.이것은 람다 추상화의 정의에서 모순을 일으키는 원천이다.그러나 람다 추상화는 이름을 가진 함수를 나타내기 위해 구성될 수 있다.이 형식에서는 불일치가 제거된다.람다 용어,

$(\displaystyle (\data f.z)\ (\data x.y)}$

$z{\displaystyle }$ ${\displaystyle z}$ ${\displaystyle \text{식}}$에서 $f{\displaystyle }$ $x{\displaystyle }$= ${\displaystyle y}$ ${\displaystyle$ f\ x$=y}$을$($를) 정의하는 것과 동일하며$,$ 이 함수는 let 표현식으로 쓸 수 있다.

${\displaystyle \propertname {let} f\ x=y\propertname {in} z}$

그 표현은 자연어 표현으로 이해할 수 있다.let 식은 변수의 값 치환을 나타낸다.대체 규칙은 평등의 의미를 대체로서 설명한다.

수학에서 정의를 내리자.

수학에서 표현은 표현식의 결합으로 설명된다.기능 언어에서 허용 표현은 범위를 제한하는데도 사용된다.수학 범위에서는 정량자에 의해 설명된다.레트 표현은 실존적 정량화기 내의 결합이다.

${\displaystyle(\exists xE\land F)\iff \operatorname {let} x:E\operatorname {in}F}$

여기서 E와 F는 Boolean 유형이다.

let 식은 치환을 다른 식에 적용할 수 있도록 한다.이 대체는 제한된 범위 내에서 하위 표현식에 적용될 수 있다.let 표현식의 자연적 사용은 제한된 범위( 람다 드롭이라고 함)에 적용된다.이 규칙은 범위를 제한하는 방법을 정의한다.

${\displaystyle {\begin{cases}x\not \in \operatorname {FV} (E)\land x\in \operatorname {FV} (F)\implies \operatorname {let} x:G\operatorname {in} E\ F=E\ (\operatorname {let} x:G\operatorname {in} F)\\x\in \operatorname {FV} (E)\land x\not \in \operatorname {FV} (F)\implies \operatorname {let} x:G\operatorname {in} E\ F=(\operatorname {let} x:G\operatorename {in} E)\ F\\x\not \in \operatorname {FV}(E)\land x\not \in \operatorname {FV}(F)\implies \operatorname {let} x:G\operatorname {in}F=E\end{case}}}}}$

여기서 F는 부울 유형이 아니다.이 정의에서 기능 언어에서 사용되는 다음과 같은 표준 표현식을 도출할 수 있다.

${\displaystyle x\not \in \in \operatorname {FV}(y)\implies(\operatorname {let} x:x=y\operatorname {in}z)=z[x:=y]=(\lambda x.z)\y}$

단순성을 위해 실존 변수를 지정하는 마커($x{\displaystyle }$: ${\displaystyle$ x$:\})$는 컨텍스트에서 명확해지는 표현에서 생략된다.

${\displaystyle x\not \in \in \operatorname {FV}(y)\implies(\operatorname {let} x=y\operatorname {in} z)=z[x:=y]=(\lambda x.z)\y}$

파생

이 결과를 도출하기 위해서,

${\displaystyle x\not \in \in \operatorname {FV}(L)}$

그때

${\displaystyle {\begin{aigned}L\(\operatorname {let} x:x=y\operatorname {in} z)&\f(\operatorname {x:x=y\operatorname {in}L\in)\&\iff x=land L\end{aigned}}}}}}}$

대체의 법칙을 이용해서,

${\displaystyle {\begin{aigned}&\iff x=y\land(L\ z)[x:=y]\\&\iff x=y\land (L[x:=y]\ z[x:==y])\&\iff x=y\land L\z[x:=y]\\&\implies L\z[x:=y]\end{aigned}}}$

그래서 모든 L에게

${\displaystyle L\operatorname {let} x:x=y\operatorname {in} z\implies L\z[x:=y]}$

$L{\displaystyle }$ ${\displaystyle \text{X}}$=${\displaystyle }$( ${\displaystyle X}$= K${\displaystyle }$) ${\displaystyle L\ X=(X=K)}$을(를) 두십시오. 여기서$$ K는 새로운 변수입니다.그때

${\displaystyle(\operatorname {let} x:x=y\operatorname {in} z)=K\implies z[x:=y]==K}$

그렇게

${\displaystyle \propertname {let} x:x=y\propertname {in} z=z[x:=y]}$

하지만 베타 축소에 대한 수학적인 해석으로 볼 때

$(\displaystyle (\data x.z)\y=z[x:=y]}$

여기서 y가 변수 x의 함수인 경우, z의 x와 같지 않다.알파 이름을 변경할 수 있다.그래서 우리는 반드시,

${\displaystyle x\not \in \operatorname {FV}(y)}$

그렇게

${\displaystyle x\not \in \in \operatorname {FV}(y)\implies \operatorname {let} x:x=y\operatorname {in} z=(\lambda x.z)\y}$

이 결과는 약어 형태의 기능 언어로 표현되며, 여기서 의미는 모호하지 않다.

${\displaystyle x\not \in \in \operatorname {FV}(y)\implies(\operatorname {let} x=y\operatorname {in} z)=z[x:=y]=(\lambda x.z)\y}$

여기서 변수 x는 x를 정의하는 방정식의 부분과 실존적 계량기에서 변수를 모두 암묵적으로 인식한다.

부울에서 들어올리지 않음

$E{\displaystyle }$ =${\displaystyle \mathrm{\neg }}$ ${\displaystyle E=\neg }$에 의해 정의되는 경우 모순이 발생한다$.$ 이 경우

${\displaystyle x\in \operatorname {FV}(E)\land x\in \in \operatorname {FV}(F)\implies \operatorname {let} x:G\operatorname {in}E\(\operatorname {let}x:G\operatorname {in}F})$

된다

${\displaystyle \operatorname {let} x:G\operatorname {in} \neg F=\neg(\operatorname {let}x:G\operatorname {in}F)}$

그리고 사용하는 것,

${\displaystyle(\exists xE\land F)\iff \operatorname {let} x:E\operatorname {in}F}$

${\displaystyle(\exists xG\land \neg F)=\neg \(\exists xG\land F)}$

$(\displaystyle = (\exists x\neg G\lor \neg F)}$

만약 G가 거짓이라면 이것은 거짓이다.이 모순을 피하기 위해 F는 부울 타입이 될 수 없다.부울 F의 경우, 드롭 규칙의 올바른 문장은 동등성 대신 함축성을 사용한다.

${\displaystyle x\not \in \operatorname {FV}(E)\land x\in \in\inplies(\operatorname {FV})(\operatorname {let}x\f\to E\(\operatorname {let}x:G\operatorname {in}F})$

다른 유형의 부울에 다른 규칙이 적용되는 것은 이상하게 보일 수 있다.그 이유는 규칙이

${\displaystyle(\exists xE\land F)\iff \operatorname {let} x:E\operatorname {in}F}$

F가 부울인 경우에만 적용된다.두 규칙의 조합은 모순을 만들어 내므로, 한 규칙이 가지고 있는 곳에서는 다른 규칙이 그렇지 않다.

결합 레트 식

여러 변수로 식을 정의할 수 있다.

${\displaystyle(\exists v\cdots \exists w\exists xE\land F)\iff \operatorname {let}v,\ldots,w,x:E\operatorname {in}F}$

그러면 파생될 수 있고,

$\displaystyle x\not \in FV(E)\implies(\exists v\cdots \exists w\exists w\exists w\exists w\exists w(E\land\exists xF))\iff(exists v\cdotes w.$

그렇게

${\displaystyle x\not \in FV(E)\implies(\operatorname {let} v,\ldots ,w,x:E\land F\operatorname {in} L\equiv \operatorname {let} v,\ldots ,w:E\operatorname {in} \operatorname {let} x:F\opername {in} L)}$

람다 미적분 및 표현에 관한 법칙

에타 감소는 람다 추상화를 설명하는 규칙을 제공한다.이 규칙은 위에서 파생된 두 가지 법칙과 함께 람다 미적분과 표현 사이의 관계를 정의한다.

이름	법
에타 환원 동등성	$\displaystyle f\x=y=equiv f=\da x.y.}$
렛 람다 등가성	${\displaystyle f\notin FV(E)\implies (\operatorname {let} f:f=)$$E\operatorname {in} L\equiv(\lambda f).$$L)\ E}($여기서 $f{\displaystyle }$ ${\displaystyle f}$은(는) 변수 이름임)
렛 콤비네이션	${\displaystyle x\notin FV(E)\implies(\operatorname {let} v,\dots,w,x:E\land F\operatorname {in} L\equiv \operatorname {let} v,\dots ,w:E\operatorname {in} \operatorname {let} x:F\opername {in} L)}$

람다 미적분학에서 정의하도록 두십시오.

수학적 정의와 관련된 잠재적인 문제를 피하기 위해, 다나 스콧은 원래 람다 미적분학에서 let 식을 정의했다.이는 하향식 또는 자명한 수학적 정의와 대조적으로, 허용식의 상향식 또는 건설적인 정의로 간주될 수 있다.

단순하고 반복적이지 않은 표현은 용어에 적용된 람다 추상화에 대한 통사적 설탕으로 정의되었다.그 정의에서,

${\displaystyle(\displayname {let} _{s}x=y\dataname {in} z)\equiv(\data x.z)\y}$

그런 다음 단순 허용 표현식 정의가 확장되어 고정 점 결합기를 사용한 재귀가 허용되었다.

고정점 결합기

고정점 결합기는 표현으로 나타낼 수 있다.

$\displaystyle \lambda f.\cHBNAME {let} x=f\ x\cHBNAME {in} x}$

이 표현은 람다 용어로 변환될 수 있다.람다 추상화는 적용된 식에서 변수 이름에 대한 참조를 지원하지 않으므로 x는 x에 대한 매개 변수로 전달되어야 한다.

$\displaystyle \lambda f.\cHBNAME {let} x\ x=f\(x\ x)\n3\in}x\x}$

eta 감소 규칙을 사용하여,

$\displaystyle f\x=y=equiv f=\da x.y.}$

주는 것,

$\displaystyle \lambda f.\cHBNAME {let} x=\cHBDA x.f\(x\ x)\paBNAME {in}x\x}$

let 표현은 다음을 사용하여 람다 추상화로 표현될 수 있다.

${\displaystyle n\in \in FV(E)\to(\operatorname {let}n=E\operatorname {in}L\equiv(\lambda n).L)\E)}$

주는 것,

$\displaystyle \lambda f.(\displayda x.x\ x)\(\displayda x.f\ (x\ x)}}$

이것은 아마도 람다 미적분학에서 고정점 결합기의 가장 간단한 구현일 것이다.그러나 한 번의 베타 감소는 커리의 Y 콤비네이터의 보다 대칭적인 형태를 준다.

$\displaystyle \lambda f.(\displayda x.f\ (x\ x)\(\displayda x.f\ (x\ x))}$

재귀적 허용 식

"let rec"라고 불리는 재귀적 let 식은 재귀 let 식에 Y 결합기를 사용하여 정의된다.

${\displaystyle(\operatorname {let\rec}x=y\operatorname {in} z)\equiv(\lambda x.z)\(Y\ (\lambda x.y)}}}$

상호 재귀적 허용 식

이 접근법은 상호 재귀성을 지원하기 위해 일반화된다.상호 재귀적 표현은 어떤 표현과 조건을 제거하도록 표현을 재정렬하여 구성할 수 있다.이것은 여러 함수 정의를 하나의 함수 정의로 대체하여 달성되는데, 변수 목록을 식 목록과 동일하게 설정한다.Y* 다변량 고정점 결합기(Poly-various fix-point combinator)라고 불리는 Y 결합기 버전을 사용하여 모든 기능의 고정점을 동시에 계산한다.그 결과는 Let표현의 상호 재귀적 구현이다.

다중값

집합의 멤버인 값을 나타내기 위해 허용 식을 사용할 수 있다.

${\displaystyle \operatorname {let} x\in X\operatorname {in} x}$

함수 적용에서 한 표현은 다른 표현으로,

${\displaystyle {\begin{aligned}&(\operatorname {let} x\in X\operatorname {in} x)\ (\operatorname {let} y\in Y\operatorname {in} y)\\&=\operatorname {let} x\in X\land y\in Y\operatorname {in} x\ y\\&=\operatorname {let} (x,y)\in X\times Y\operatorname {in} x\ y\end{aligned}}}$

그러나 다른 규칙이 자신에게 허용 표현을 적용하는 데 적용된다.

${\displaystyle {\begin{aigned}&(\operatorname {in} x)\(\operatorname {in} x)\(\operatorname {let} x\in}\=\operatorname {let} x\in} x\x\end{aigned}}}}}}}}}}}}}}$

값을 조합하는 간단한 규칙은 없어 보인다.필요한 것은 값이 값 집합의 멤버인 변수를 나타내는 일반적인 형태의 표현이다.표현은 변수와 집합에 기초해야 한다.

이 양식에 적용되는 함수 적용은 동일한 형태로 다른 표현을 제공해야 한다.이와 같이 복수의 값의 기능에 대한 어떤 표현도 하나의 값을 가진 것처럼 취급할 수 있다.

형식은 값 집합만을 나타내기에는 충분하지 않다.각 값에는 식이 값을 가져가는 시기를 결정하는 조건이 있어야 한다.결과적 구성은 조건과 값의 쌍 집합으로, "값 집합"이라고 불린다.대수 값 집합의 축소를 참조하십시오.

람다 미적분과 표현식 사이의 변환 규칙

람다와 렛 식 사이의 변환을 설명하는 메타 기능이 제공될 것이다.메타 함수는 프로그램을 매개 변수로 삼는 함수다.프로그램은 메타 프로그램을 위한 데이터다.프로그램과 메타 프로그램은 서로 다른 메타 레벨에 있다.

다음 규약은 메타 프로그램과 프로그램을 구별하기 위해 사용될 것이다.

• 대괄호 []는 메타 프로그램의 기능 적용을 나타내기 위해 사용된다.
• 메타 프로그램의 변수에 대문자가 사용될 것이다.소문자는 프로그램의 변수를 나타낸다.
• ${\displaystyle }$메타 프로그램에서 동급의 경우$【\displaystyle \equiv$ }이$($가) 사용된다$$.

단순성을 위해 일치하는 첫 번째 규칙이 적용된다.이 규칙들은 또한 람다 표현이 각 람다 추상화에 고유한 이름을 가지도록 사전 처리되었다고 가정한다.

대체 연산자도 사용된다.$L{\displaystyle }$[ ${\displaystyle G}$ ${\displaystyle :=}$ ${\displaystyle S}$ ${\displaystyle ]}$ ${\displaystyle L[G:=S]}$이라는 표현은 L에서 발생하는 G의 모든 발생을 S로 대체하고 그 표현을 반환하는 것을 의미한다$$.사용된 정의는 람다 미적분 페이지에 주어진 정의에서 표현식의 대체를 다루기 위해 확장된다.표현식의 일치는 알파 등가성(변수의 이름 바꾸기)에 대한 식을 비교해야 한다.

람다에서 식으로 변환

다음 규칙은 구조를 변경하지 않고 람다 표현식에서 레트 표현으로 변환하는 방법을 설명한다.

1. ${\displaystyle \operatorname {de-lambda} [V]\equiv V}$
2. ${\daystyle \operatorname {de-lambda} [M\ N]\equiv \operatorname {de-lambda} [N]$
3. ${\displaystyle \operatorname {de-lambda} [F=\lambda P.E]\equiv \operatorname {de-lambda} [F\ P=E]}$
4. ${\daystyle \operatorname {de-lambda} [E=F]\equiv \operatorname {de-lambda} [F]}$
5. ${\displaystyle \operatorname {de-lambda} [(\lambda F).E)L]\equiv \operatorname {let-combine} [\operatorname {let}F:\operatorname {de-lambda} [F=L]\operatorname {in}E]}$
6. $\in \operatorname {FV}[\lambda F]에서 {FV}[\lambda F.E]\\\operatorname {de-lambda} [\lambda F.E]\equiv \operatorname {let-combine} [\operatorname {let} V:\operatorname {de-lambda} [V\ F=E]\operatorname {in}V]}$
7. ${\displaystyle V\neq W\to \operatorname {let-combine}[\operatorname {let} V:E\operatorname {in} \operatorname {let} W:F\operatorname {in} G]\equiv \operatorname {let} V,W:E\land F\operatorname {in}G}$
8. ${\displaystyle \operatorname {let-combine} [\operatorname {let} V:E\operatorname {in}F]\equiv \operatorname {let}V:E\operatorname {in} F}$

규칙 6은 함수의 이름으로 고유한 변수 V를 생성한다.

예

예를 들어 Y 콤비네이터,

$\displaystyle \lambda f.(\displayda x.f\ (x\ x)\(\displayda x.f\ (x\ x))}$

로 변환됨,

${\displaystyle \p\f=\ftname {let} x:x\ q\(q\ q)\pxname {in} f\(x\ x)\pin}$

규칙	람다식
6	${\displaystyle \de-fda}[\da f.f\(x\x\)\(\data x.f\)(x\x\)]}$ $\in \operatorname {FV}[\lambda F]에서 {FV}[\lambda F.E]\\\operatorname {de-lambda} [\lambda F.E]}$ ${\displaystyle V=p,F=f,E=(\lambda x.f\(x\ x)\(\lambda x.f\)(x\x\)}$ ${\displaystyle \operatorname {let-combine} [\operatorname {let}V:\operatorname {de-lambda} [V\F=E]\operatorname {in}V]}$
4	${\displaystyle \displayname {let-lit}p:\desname {de-filda}[p\f=(\fda x.f\ (x\ x)]\displayda x.f\ (x\ x)]\dismname {in}}$ ${\displaystyle \de-fda}[p\f=(\fda x.f\)(x\x\)\(\displayda x.f\ (x\ x)]]}$ ${\displaystyle \operatorname {de-lambda} [E=F]}$ $(\displaystyle E=p\ f,F=(\lambda x.f\ (x\ x)\(\lambda x.f\)(\lambda x.f\ (x\ x))}$ ${\daystyle \operatorname {de-lambda} [E]=\operatorname {de-lambda} [F]}$ ${\displaystyle \photda} [p\f]=\de-fda}[(\displayda x.f\ (x\ x)]\\(\(\displayda x.f\ (x\ x))]}$ ${\displaystyle \displayname {let-lit}p:\de-latname {de-laughda}[p\f]=\de-laughda}[\da x.f\ (x\ x)]\\dismname {in}}$
5	${\displaystyle \displayname {let-lit}p:\de-latname {de-laughda}[p\f]=\de-laughda}[\da x.f\ (x\ x)]\\dismname {in}}$ ${\displaystyle \de-fda}[(\de-da x.f\ (x\ x)]\(\displayda x.f\ (x\ x)]}$ ${\displaystyle \operatorname {de-lambda} [(\lambda F).E)L]}$ ${\displaystyle F=x,E=f\(x\ x),L=(\lambda x.f\(x\ x))}$ ${\displaystyle \operatorname {let-combine} [\operatorname {let}F:\operatorname {de-lambda} [F=L]\operatorname {in}E]}$ ${\displaystyle \displayname {let-lates} [\desame {de-data}[x=\da x.f\ (x\ x)]\displayname {in} f\ (x\ x)]}$
3	${\displaystyle \operatorname {let-combine} [\operatorname {let} p:\operatorname {de-lambda} [p\ f]=\operatorname {let-combine} [\operatorname {let} x:\operatorname {de-lambda} [x=\lambda x.f\ (x\ x)]\operatorname {in} f\ (x\ x)]\operatorname {in} p]}$ ${\displaystyle \designname {de-de-da} [x=\data x.f\ (x\ x)]}$ ${\displaystyle \operatorname {de-lambda} [F=\lambda P.E]}$ ${\displaystyle F=x,P=x,E=f\(x\ x)}$ ${\displaystyle \operatorname {de-lambda} [F\ P=E]}$ ${\displaystyle \designname {de-filda} [x\ x=f\ (x\ x)]}$
8	${\displaystyle \cHBNAME {let}p:\de-hostname {de-fda}[p\f]=\cHBNAME {letname}x:\de-hostname {da}[x\f\(x\x)]\p}$ ${\displaystyle \propertname {let-limitname} [\de-limitname {de-limitname}[x\f\ (x\ x)]\propertname {in} f\ (x\ x)]}$ ${\displaystyle \operatorname {let-combine} [Y]}$ ${\displaystyle Y=\operatorname {let}x:\operatorname {de-lambda}[x\ x=f\(x\)]\operatorname {in} f\(x\ x)}$ $(\디스플레이 스타일 Y})$ ${\displaystyle \propertname {let} x:\de-propertname {de-fda} [x\=f\(x\ x)]\propertname {in} f\(x\ x)}$
8	${\displaystyle \cHBNAME {let} p:\depname {de-havidda}[p\f]=\cHBNAME {de-da}[x\ x=f\ (x\)]\iename {in}$ ${\displaystyle \operatorname {let-combine} [Y]}$ ${\displaystyle Y=\operatorname {let}p:\operatorname {de-lambda}[p\f\(x\)]\operatorname {de-lambda}[x\ x\]\operatorname {in}p}$ $(\디스플레이 스타일 Y})$ ${\displaystyle \p\f=\ftname {let}x:\de-filename {de-filename}[x\f\(x\ x)]\displayname {in} f\(x\ x)\in}p}$
4	${\displaystyle \designame {let}p:\de-f]=\de-da}x:\de-daname {de-daida}[x\=f\(x\)]\javename {in}p}$ ${\displaystyle \designname {de-filda} [x\ x=f\ (x\ x)]}$ ${\displaystyle \operatorname {de-lambda} [E=F]}$ ${\displaystyle E=x\ x,F=f\(x\ x)}$ ${\daystyle \operatorname {de-lambda} [E]=\operatorname {de-lambda} [F]}$ ${\displaystyle \propertyname {de-propertda} [x\ x]=\de-propertname {de-properda} [f\ (x\ x)]}$
2	${\displaystyle \designame {let}p:\de-f]=\de-da}x:\de-daname {de-da}[x\ x]\de-da}\in}\in}$ ${\displaystyle \propertname {de-data}[x\ x],\de-propertname {de-properda}[f\ (x\ x)]}$ ${\displaystyle \operatorname {de-lambda}[p\f],\operatorname {de-lambda}[M_{1}\{1}],\operatorname {de-lambda}[M_{2}\N_{2}],},},},}$ ${\displaystyle M_{1}=p,N_{1}=f,M_{2}=x,N_{2}=x,M_{3}=f,N_{3}=x\x}$ ${\displaystyle \operatorname {de-lambda} [M_{1}]\ \operatorname {de-lambda} [N_{1}],\operatorname {de-lambda} [M_{2}]\ \operatorname {de-lambda} [N_{2}],\operatorname {de-lambda} [M_{3}]\ \operatorname {de-lambda} [N_{3}]}$ ${\displaystyle \de-data} [p]\\\de-da}[f]\de-da}[x]\de-da}[x]\de-da]\de-da}[x]$
1	${\displaystyle \operatorname {let} p:\operatorname {de-lambda} [p]\ \operatorname {de-lambda} [f]=\operatorname {let} x:\operatorname {de-lambda} [x]\ \operatorname {de-lambda} [x]=\operatorname {de-lambda} [f]\ (\operatorname {de-lambda} [x]\ \operatorname {de-lambda} [x])\cHB 이름 {in}f\(x\ x)\\cHB 이름 {in}p}$ ${\displaystyle \operatorname {de-lambda} [V]}$ $(\displaystyle V}$
	${\displaystyle \p\f=\pname {let} x:x\ x=f\(x\ x)\pxname {in} f\(x\ x)\pin}$

let에서 람다 식로의 변환

이러한 규칙은 위에서 설명한 변환을 반대로 한다.그들은 구조를 바꾸지 않고 레트 표현에서 람다 표현으로 전환한다.모든 표현식이 이 규칙을 사용하여 변환되도록 놔두지는 않는다.규칙은 표현들이 이미 뎀브다에 의해 생성된 것처럼 배열되어 있다고 가정한다.

1. ${\displaystyle \operatorname {get-lambda}[F,G\V=E]=\operatorname {get-lambda}[F,G=\lambda V].E]}$
2. ${\displaystyle \operatorname {get-lambda} [F,F=E]=\operatorname {de-let} [E]}$
3. ${\displaystyle \operatorname {de-let} [\lambda V.E]\equiv \lambda V.\operatorname {de-let} [E]}$
4. ${\daystyle \operatorname {de-let} [M\ N]\equiv \operatorname {de-let} [N]$
5. ${\displaystyle \operatorname {de-let} [V]\equiv V}$
6. ${\displaystyle V\not \in FV[\operatorname {get-lambda}[V,E]]\\to \operatorname {de-let}[\operatorname {let}V:E\ \operatorname {in} V]\equiv \operatorname {get-lambda} [V,E]}$
7. ${\displaystyle V\not \in FV[\operatorname {get-lambda}[V,E]]\\to \operatorname {de-let}[\operatorname {let}V:E\ \operatorname {in} L]\equiv(\lambda V.\operatorname {de-let}[L]\ \operatorname {get-lambda} [V,E]}$
8. ${\displaystyle W\not \in \operatorname {FV} [\operatorname {get-lambda} [V,E]]\to \operatorname {de-let} [\operatorname {let} V,W:E\land F\ \operatorname {in} G]\equiv \operatorname {de-let} [\operatorname {let} V:E\ \operatorname {in} \operatorname {let} W:F\ \operatorname {in} G]}$
9. ${\displaystyle V\in \operatorname {FV}[\operatorname {get-lambda}[V,E]]\to \operatorname {de-let}[\operatorname {let}V:E\ \operatorname {in} L]\equiv \operatorname {de-let}[\operatorname {let} V:V\ V=\operatorname {get-lambda} [V,E][V:V\ V]\\ \operatorname {in} L[V:=V\V\V]]}$
10. ${\displaystyle W\in \operatorname {FV} [\operatorname {get-lambda} [V,E]]\to \operatorname {de-let} [\operatorname {let} V,W:E\land F\ \operatorname {in} L]\equiv \operatorname {de-let} [\operatorname {let} V:V\ W=\operatorname {get-lambda} [V,E][V:=V\ W]\ \operatorname {in} \operatorname {let} W:F[V:=V\ W]\ \operatorname {in} L[V:=V\ W]}$

자유 변수를 재귀적으로 사용하는 식에 대해 람다 미적분학에는 정확한 구조적 등가물이 없다.이 경우 매개변수를 일부 추가해야 한다.규칙 8과 10은 이러한 매개변수를 추가한다.

규칙 8과 10은 let 식에서 두 개의 상호 재귀 방정식에 충분하다.그러나 그들은 3개 이상의 상호 재귀 방정식에 대해서는 작동하지 않을 것이다.일반적인 경우는 메타 기능을 조금 더 어렵게 만드는 추가적인 루핑이 필요하다.일반사례를 이행함에 있어서 준칙은 8과 10을 대체한다.더 간단한 사례가 먼저 연구될 수 있도록 규칙 8과 10을 남겨두었다.

1. 람다 형식 - 식을 각 형식 변수 = 식의 조합으로 변환하십시오.
   1. ${\displaystyle \operatorname {lambda-form} [G\ V=E]=\operatorname {lambda-form} [G=\lambda V]E]}$
   2. ${\displaystyle \operatorname {lambda-form} [E\land F]=\operatorname {lambda-form} [F]}$
   3. ${\displaystyle \mathrm{l}}$ ${\displaystyle \mathrm{m}}$ b ${\displaystyle \mathrm{a}}$ d ${\displaystyle \mathrm{a}}$ -${\displaystyle \mathrm{f}}$ ${\displaystyle o}$ ${\displaystyle }$[ V${\displaystyle }$= ${\displaystyle E}$ ${\displaystyle ]}$= ${\displaystyle V}$= ${\displaystyle E}$ ${\displaystyle \operatorname {lambda-form} [V=E]=V=E}$ ......$$ 여기서 V는 변수다.
2. lift-vars - 식에 자유 변수로 X가 있기 때문에 매개 변수로 X가 필요한 변수 집합을 가져오십시오.
   1. ${\displaystyle X\in \operatorname {FV}[E]\to \operatorname {lifft-vars}[X,V=E]=\{V\}}]$
   2. ${\displaystyle X\not \in \in \operatorname {FV}[E]\to \operatorname {lifft-vars}[X,V=E]=\{\}}]$
   3. ${\displaystyle \operatorname {liff-vars} [X,E\land F]=\operatorname {liff-vars} [X,E]\컵 \operatorname {liff-vars} [X]F]}$
3. 하위 변수 - 세트의 각 변수에 대해 식에서 X에 적용된 변수에 대해 대체하십시오.이렇게 되면 X는 방정식의 오른쪽에서 자유 변수가 되는 것이 아니라 매개변수로 전달되는 변수가 된다.
   1. ${\displaystyle \operatorname {sub-vars} [E,\{V\}\컵 S,X]=\operatorname {sub-vars}[E[V:=V\ X]]$
   2. ${\displaystyle \operatorname {sub-vars}[E,\\{\},X]=E}$
4. 삭제 - X가 방정식의 오른쪽에 자유 변수가 되지 않도록 E의 각 조건을 들어 올린다.
   1. ${\displaystyle {\reasoned}L&,=\operatorname{lambda-form}S=\operatorname{lift-vars}[X,L]\to\operatorname{de-let}[\operatorname{}V\ldots W,X:E\land F\ \operatorname{}에 G자]\\&[E]\land, \equiv\operatorname{de-let}\operatorname{에서}\operatorname{ 알려 주세요}\operatorname[\operatorname{}[L,S,X V\ldots W:\operatorname{sub-vars}자]\{sub-vars}는 경우에는 \operatorname{.lambda-form} [F],S,X]\\ \operatorname {in} \operatorname {sub-vars} [G,S,X]]\end{aligned}}}}$

예

예를 들어 Y 콤비네이터에서 얻은 let 식,

${\displaystyle \p\f=\pname {let} x:x\ q\(q\ q)\\\displayname {in}f\(x\ x)\\displayname {in}p}$

로 변환됨,

$\displaystyle \lambda f.(\displayda x.f\ (x\ x)\ (\displayda q.f\ (q\ q)}}}$

규칙	람다식
6	${\displaystyle \de-let}[\displayname {let}p:p\ f=\p=\pairname {let}x\q\(q\q)\\\pairname {in}$ ${\displaystyle \operatorname {de-let} [\operatorname {let} V:E\ \operatorname {in} V]}$ ${\displaystyle V=p,E=p\f=\operatorname {let} x:x\ q=f\(q\ q)\\ \operatorname {in} f\(x\ x)}$ ${\displaystyle \operatorname {get-lambda} [V,E]}$
1	${\displaystyle \computname {get-baskda} [p,p\f=\basname {let} x:x\ q\ (q\ q)\\\displayname {in} f\ (x\ x)]}$ ${\displaystyle \operatorname {get-lambda} [F,G\ V=E]}$ ${\displaystyle F=p,G=p,V=f,E=\operatorname {let}x\ q=f\(q\ q)\\ \operatorname {in} f\(x\ x)}$ ${\displaystyle \operatorname {get-lambda} [F,G=\lambda V.E]}$
2	${\displaystyle \computname {get-pitda} [p,p=\putda f.\cHBNAME {let} x:x\ q=f\ (q\ q)\\\\dBNAME {in} f\ (x\ x)}}$ ${\displaystyle \operatorname {get-lambda} [F,F=E]}$ $F=p,E=\lambda f.\cHBNAME {let} x:x\ q=f\(q\ q)\ \dBNAME {in} f\(x\ x)}$ ${\displaystyle \operatorname {de-let} [E]}$
3	${de-let} [\displaystyle \designname] [\data f.\cHBNAME {let} x:x\ q=f\ (q\ q)\\\\dBNAME {in} f\ (x\ x)}}$ ${\displaystyle \operatorname {de-let} [\lambda V.E]}$ ${\displaystyle V=f,E=\operatorname {let} x:x\ q=f\(q\ q)\ \operatorname {in} f\(x\ x)}$ $\displaystyle \lambda V.\operatorname {de-let} [E]}$
7	$\displaystyle \lambda f.\cHBNAME {de-let} [\cHBNAME {let}x\ q=f\(q\ q)\ \cHBNAME {in} f\ (x\ x)]}$ ${\displaystyle \de-let} [\designname {let} x:x\ q=f\ (q\ q)\\\designname {in} f\ (x\ x)]}$ ${\displaystyle V\not \in FV[\operatorname {get-lambda}[V,E]]\\to \operatorname {de-let}[\operatorname {let}V:E\ \operatorname {in} L]}$ ${\displaystyle V=x, E=x\ q=f\(q\ q),L=f\(x\ x)}$ $(\displaystyle(\lambda V.\operatorname {de-let}[L]\ \operatorname {get-lambda} [V,E]}$
4	${\displaystyle(\displaystyle)(\de-let}[f\(x\ x)]\\get-da}[x\ q\ (q\ q)]}$ ${\displaystyle \de-letname} [f\(x\ x)]}$ ${\displaystyle \operatorname {de-let} [M\ N]}$ ${\displaystyle M=f,N=(x\ x)}$ ${\daystyle \operatorname {de-let} [M]\ \operatorname {de-let} [N]}$ ${\displaystyle \de-let} [f]\\\de-let}[x\ x]}$
4	${\displaystyle(\displaystyle)(\de-letname {de-let}[x\ x])\\de-letname {de-let}[x\ q\ q]}$ ${\displaystyle \desname {de-let} [x\ x]}$ ${\displaystyle \operatorname {de-let} [M\ N]}$ ${\displaystyle M=x, N=x}$ ${\daystyle \operatorname {de-let} [M]\ \operatorname {de-let} [N]}$ ${\displaystyle \de-letname {de-let} [x]\\desname {de-let} [x]}$
5	${\displaystyle(\displaystyle)(\de-letname {de-let}[x]]\de-let}\\de-letname {de-let}[x])\\get-da}[x\q\ q\]}$ ${\displaystyle \operatorname {de-let} [V]}$ $(\displaystyle V}$
1	${\displaystyle(\displaystyle)(\displayda x.f\(x\ x)\\\get-fda}[x,x\ q=f\ (q\ q)]}$ ${\displaystyle \propertname {get-bigda} [x,x\ q=f\ (q\ q)]}$ ${\displaystyle \operatorname {get-lambda} [F,G\ V=E]}$ ${\displaystyle F=x, G=x, V=q, E=f\(q\ q)}$ ${\displaystyle \operatorname {get-lambda} [F,G=\lambda V.E]}$ ${\displaystyle \propertname {get-propertda} [x,x=\fda q.f\ (q\ q)]}$
2	${\displaystyle(\displaystyle)(\displayda x.f\ (x\ x)\\\get-fda}[x,x=\fda q.f\ (q\ q)]}}$ ${\displaystyle \propertname {get-propertda} [x,x=\fda q.f\ (q\ q)]}$ ${\displaystyle \operatorname {get-lambda} [F,F=E]}$ ${\displaystyle F=x, E=\lambda q.f\ (q\ q)}$ ${\displaystyle \operatorname {de-let} [E]}$ ${\displaystyle \de-letname {\de-let} [\da q.f\ (q\ }$
3	${\displaystyle(\displaystyle)(\data x.f\ (x\ x)\\\de-let}[\da q.f\ (q\ q)]}}$ ${\displaystyle \de-letname {\de-let} [\da q.f\ (q\ }$ ${\displaystyle \operatorname {de-let} [\lambda V.E]}$ ${\displaystyle V=q,E=f\ (q\ q)}$ $\displaystyle \lambda V.\operatorname {de-let} [E]}$ ${\displaystyle \putda q.\putname {de-let} [f\ (q\ q)]}$
4	${\displaystyle(\displaystyle)(\displayda x.f\(x\ x)\(\de-letname {de-let}[f\ (q\ q)]]}$ ${\displaystyle \de-letname} [f\ (q\ q)]}$ ${\daystyle \operatorname {de-let} [M_{1}\ N_{1}]}$ ${\displaystyle M_{1}=f,N_{1}=q\ q}$ ${\daystyle \operatorname {de-let} [M_{1}]\ \operatorname {de-let} [N_{1}]}$ ${\displaystyle \de-let} [f]\\\de-let}[q\ q]}$ ${\daystyle \operatorname {de-let} [M_{2}\ N_{2}]}$ ${\displaystyle M_{2}=q,N_{2}=q}$ ${\displaystyle \de-letname {de-let} [q]\ \desname {de-let}$
5	${\displaystyle(\displaystyle)(\displaystyle)(\da q.\de-letname {de-let}[q]\de-let}[q])}$ ${\displaystyle \operatorname {de-let} [V]}$ ${\displaystyle }$ $(\displaystyle V}$
	$(\displaystyle)(\data x.f\ (x\ x)\ (\data q.f\ (q\ q)}}$

두 번째 예에서는 Y 콤비네이터의 해제 버전을 예로 들어보자.

${\displaystyle \p\f\ x=f\(x\ x)\land q\p\f=(p\ f)\\\displayname {in}q\p}$

로 변환됨,

$\displaystyle(\data p.)(\da q.q\ p)\\\\da p.\lambda f.(p\ f)\ (p\ f)\\\\\lambda f.\lambda x.f\ (x\ x)}$

규칙	람다식
8	${\displaystyle \de-let}[\displayname {let}p,q:p\ f\ x=f\(x\ x)\land q\p\f\p\(p\ f)\\displayname {in}q\]}$
7	${\displaystyle \de-let}[\designname {let}p:p\ f\ x=f\(x\ x)\\\cHNAME {in} \in} \in} \cHBNAME {:q\ p=(p\ f)\\\p\p\p}}$
1, 2	$(\displaystyle)(\da p.\cHB 이름 {de-let} [\de-let} q:q\ p\f=(p\f)\\\\p\p\{in}q\p]\\\get-messda}[p\ f\ x=f\(x\)]}$
7, 4, 5	$(\displaystyle)(\da p.\cHBNAME {de-let} [\depname {let} q:q\ p\f=(p\f)\\\p\ \pda f.\lambda x.f\ (x\ x)}$
1, 2	$\displaystyle (\data q.q\p)\\\get-bigname {get-bigda}[q,q\p\f=(p\ f)\\\pda f]\\\ \da f.\lambda x.f\ (x\ x)}$
	$\displaystyle(\data p.)(\da q.q\ p)\\\\da p.\lambda f.(p\ f)\ (p\ f)\\\\\lambda f.\lambda x.f\ (x\ x)}$

세 번째 예로,

${\displaystyle \propername {let} x:x\ f=f\(x\ f)\\\displayname {in}x}$

는

$(\displaystyle(\displaystyle)(\displayda x.x\ x)\(\displayda x.x\ x)\\\\\\$

규칙	람다식
9	${\displaystyle \propername {let} x:x\ f=f\(x\ f)\\\displayname {in}x}$
1	${\displaystyle \propertname {let} x:\putda} [x,x\ f=f\(x\ f)][x:=x\ x]\\propertname {in} x[x:=x\ x]}$
2	${\displaystyle \propertname {let} x:\dataname {get-data} [x,x=\f\ (x\f)][x:=x\x]\\desname {in} x\x}$
	${\displaystyle \propertname {let}x:(x=\da f.f\(x\f)][x:=x\ x]\\designname {in}x\x}$
7	${\displaystyle \propername {let}x:(x\ x=\fda f.f\(x\ x\ f)\\\\desname {in}x\x}$
1	${\displaystyle(\displaystyle)(\data x.x\ x)\\\get-bigda}[x,x\ x=\f\ (x\ x\ f)]}$
2	${\displaystyle(\displaystyle)(\data x.x\x\ x)\\get-da 이름 {get-da}[x,x=\xda x.\f\ (x\ x\ f)]}}$
	$(\displaystyle(\displaystyle)(\displayda x.x\ x)\(\displayda x.x\ x)\\\\\\$

주요인

• 다나 스콧

참고 항목

• 범위(컴퓨터 과학)
• 람다 리프팅
• 고정점 결합기
• 람다 미적분학
• 커리의 역설
• 연역 람다 미적분학
• 구속조건 논리 프로그래밍
• 대수적 값 집합의 축소

참조