람다 리프팅

람다 리프팅은 기능이 글로벌 범위에서 서로 독립적으로 정의되도록 컴퓨터 프로그램을 재구성하는 메타프로세스다.개인의 "리프트"는 국소 기능을 글로벌 기능으로 변형시킨다.이 프로세스는 2단계로 구성되며,

매개 변수를 추가하여 함수에서 자유 변수 제거.
제한된 범위에서 더 넓은 범위 또는 글로벌 범위로 기능 이동.

'람다 리프팅'이라는 용어는 1982년경 토마스 존슨이 처음 도입했으며 역사적으로 기능 프로그래밍 언어를 구현하는 메커니즘으로 여겨졌다.그것은 몇몇 현대 컴파일러에서 다른 기법과 함께 사용된다.

람다 리프팅은 폐쇄 전환과 같지 않다.그것은 모든 콜 사이트를 조정하도록 요구하고(콜에 추가 논거를 추가함) 해제된 람다 표현에 대해 폐쇄를 도입하지 않는다.대조적으로 폐쇄 변환은 통화 사이트를 조정할 필요는 없지만 람다 식을 자유 변수에 매핑하기 위해 폐쇄를 도입한다.

이 기법은 코드 리팩터링에서, 작성된 범위 밖에서 기능을 사용할 수 있도록 하기 위해 개별 기능에 사용될 수 있다.람다 리프트는 프로그램을 변형시키기 위해 반복될 수도 있다.반복 리프트는 람다 미적분학으로 작성된 프로그램을 람다 없이 일련의 반복 기능으로 변환하는 데 사용할 수 있다.이것은 람다 미적분으로 작성된 프로그램과 함수로 작성된 프로그램의 동등성을 보여준다.^[1]그러나 람다 리프팅에 사용되는 eta 감소는 변수에서 값을 제거하기 때문에 변수에 대한 조건을 만족시키는 값(se)이 하나뿐인지 먼저 확인하지 않고 람다 미적분에 카디널리티 문제를 도입하는 단계인 만큼 추론을 위한 람다 미적분의 건전성을 입증하지 못하고 있다.e Curry의 역설.

람다 리프팅은 컴파일러의 처리 시간이 비싸다.람다 리프팅의 효율적인 구현은 $O(n^{2})$ 처리 시간에 $O(n^{2})$ O $O(n^{2})$ ( n $O(n^{2})$ ) ${\디스플레이$ 스타일 $O(n^{2})$ 이다.^[2]

기본 유형이 함수인 비정형 람다 미적분학에서 리프팅은 람다 표현식의 베타 감소 결과를 바꿀 수 있다.결과함수는 수학적인 의미에서는 같은 의미를 가지겠지만, 정형화되지 않은 람다 미적분학에서는 같은 함수로 간주되지 않는다.강도 대 확장 평등도 참조한다.

람다 리프팅의 역작전은 람다가 떨어지는 것이다.^[3]

람다 드롭은 컴파일러를 위해 프로그램의 컴파일러를 더 빨리 컴파일러로 만들 수 있으며, 파라미터 수를 줄이고 스택 프레임의 크기를 줄임으로써 결과 프로그램의 효율성을 높일 수도 있다.그러나 그것은 기능을 다시 사용하기 어렵게 만든다.떨어뜨린 함수는 그 맥락과 연결되며, 처음 들어올려야만 다른 맥락에서 사용할 수 있다.

알고리즘.

다음 알고리즘은 폐쇄를 지원하지 않는 언어로 임의 프로그램을 첫 번째 등급의 개체로 들어올리는 한 가지 방법이다.

각 함수가 고유한 이름을 갖도록 함수의 이름을 변경하십시오.
각 자유 변수를 포함 함수에 대한 추가 인수로 교체하고 해당 인수를 함수의 모든 사용에 전달하십시오.
자유 변수가 없는 모든 로컬 함수 정의를 동일한 전역 함수로 교체하십시오.
모든 자유 변수와 로컬 기능이 제거될 때까지 2단계와 3단계를 반복하십시오.

언어가 주장으로 전달되거나 다른 함수에서 반환될 수 있는 1등급 객체로 폐쇄를 가지고 있다면, 폐쇄는 자유 변수의 바인딩을 포착하는 데이터 구조로 표현될 필요가 있을 것이다.

예

다음 OCaml 프로그램은 1에서 100까지의 정수의 합계를 계산한다.

하게 하다 읊다 합계를 내다 n =   만일 n = 1 그때     1   다른     하게 하다 f x =       n + x 에     f (합계를 내다 (n - 1)) 에 합계를 내다 100

(더)let rec선언하다sum자신을 부를 수 있는 함수로써)인수보다 적은 숫자의 합에 합계의 인수를 더한 함수 f는 로컬 함수다.f의 정의 내에서 n은 자유 변수다.자유 변수를 매개 변수로 변환하는 것부터 시작:

하게 하다 읊다 합계를 내다 n =   만일 n = 1 그때     1   다른     하게 하다 f w x =       w + x 에     f n (합계를 내다 (n - 1)) 에 합계를 내다 100

다음으로 f를 전역 함수로 들어 올린다.

하게 하다 읊다 f w x =   w + x 그리고 합계를 내다 n =   만일 n = 1 그때     1   다른     f n (합계를 내다 (n - 1)) 에 합계를 내다 100

다음은 자바스크립트(JavaScript)로 쓰인 같은 예다.

// 초기 버전  기능을 하다 합계를 내다(n) {     기능을 하다 f(x) {         돌아오다 n + x;     }      만일 (n == 1)         돌아오다 1;     다른         돌아오다 f(합계를 내다(n - 1)); }  // 자유 변수 n을 공식 매개변수로 변환한 후 w  기능을 하다 합계를 내다(n) {     기능을 하다 f(w, x) {         돌아오다 w + x;     }      만일 (n == 1)         돌아오다 1;     다른         돌아오다 f(n, 합계를 내다(n - 1)); }  // 글로벌 스코프로 리프팅 기능 f 후  기능을 하다 f(w, x) {     돌아오다 w + x; }  기능을 하다 합계를 내다(n) {     만일 (n == 1)         돌아오다 1;     다른         돌아오다 f(n, 합계를 내다(n - 1)); }

람다 리프팅 대 폐쇄

람다 리프팅과 클로징은 블록 구조화 프로그램을 구현하기 위한 두 가지 방법이다.블록 구조를 제거하여 구현한다.모든 기능이 글로벌 수준으로 올라간다.폐쇄 변환은 현재 프레임을 다른 프레임과 연결하는 "폐쇄"를 제공한다.마감 변환은 컴파일 시간이 덜 걸린다.

리프팅이 있거나 없는 재귀 기능 및 블록 구조화 프로그램은 스택 기반 구현을 사용하여 구현될 수 있으며, 간단하고 효율적이다.그러나 스택 프레임 기반 구현은 엄격해야 한다(경고).스택 프레임 기반 구현을 위해서는 기능의 수명이 마지막 인, 퍼스트 아웃(LIFO)이 되어야 한다.즉, 계산을 시작하기 위한 가장 최근의 함수가 가장 먼저 끝나야 한다.

일부 기능 언어(하스켈 등)는 게으른 평가를 사용하여 구현되는데, 이 때문에 값이 필요할 때까지 계산이 지연된다.게으른 실행 전략은 프로그래머에게 유연성을 준다.게으른 평가를 위해서는 함수에 의해 계산된 값에 대한 요청이 이루어질 때까지 함수에 대한 호출을 연기해야 한다.하나의 구현은 가치 대신에 계산을 설명하는 데이터의 "프레임"에 대한 참조를 기록하는 것이다.나중에 값이 필요할 때 프레임을 사용하여 필요한 시간에 맞춰 값을 계산한다.그런 다음 계산된 값이 참조를 대체한다.

"프레임"은 스택 프레임과 유사하며, 스택에 저장되지 않는다는 차이점이 있다.게으른 평가를 위해서는 계산에 필요한 모든 데이터를 프레임에 저장해야 한다.함수가 "lift"인 경우 프레임은 함수 포인터와 함수에 대한 매개변수만 기록하면 된다.일부 현대 언어에서는 변수의 수명을 관리하기 위해 스택 기반 할당 대신 쓰레기 수거를 사용한다.관리되는 가비지 수집 환경에서 폐쇄 기록은 값을 얻을 수 있는 프레임을 참조한다.대조적으로, 해제된 함수는 계산에 필요한 각 값에 대한 매개변수를 가지고 있다.

표현과 람다 미적분학을 그대로 두자.

Let 표현은 리프팅과 드롭을 기술하고, 재귀 방정식과 람다 표현식의 관계를 기술할 때 유용하다.대부분의 기능 언어들은 표현을 허용했다.또한, ALGOL과 Pascal과 같은 블록 구조 프로그래밍 언어는 제한된 범위에서 사용하기 위한 함수의 로컬 정의를 허용한다는 점에서 유사하다.

여기서 사용하는 let 표현식은 많은 기능적 언어로 구현된 let rec의 완전히 상호 재귀적인 버전이다.

표현은 람다 미적분학과 관련이 있다.람다 미적분은 구문과 의미론이 단순하며, 람다 리프팅을 설명하는데 좋다.람다 리프팅은 람다에서 레트 표현으로의 번역으로, 람다 드롭은 그 반대로 설명하면 편리하다.표현에 따라 상호 재귀가 허용되기 때문인데, 어떤 의미에서는 람다 미적분학에서 지지되는 것보다 더 많이 들뜨게 된다.람다 미적분은 상호 재귀성을 지원하지 않으며 가장 바깥쪽 글로벌 범위에서 하나의 기능만 정의할 수 있다.

리프팅 없이 번역을 설명하는 변환 규칙은 Let 표현 기사에 제시되어 있다.

다음 규칙은 람다와 표현식의 동등성을 설명한다.

이름	법
에타 환원 동등성	$\displaystyle f\x=y=equiv f=\da x.y.}$
렛 람다 등가성	$f\notin FV(E)\to(\operatorname {let} f:f=E\operatorname {in} L\equiv(\lambda f).L)\ E)\\\text{{\text{{{}여기서 }f{\text{는 변수 이름)}}$
렛 콤비네이션	$x\notin FV(E)\to(\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)$

람다 리프팅 및 드롭을 설명하는 메타 기능이 제공될 것이다.메타 함수는 프로그램을 매개 변수로 삼는 함수다.프로그램은 메타 프로그램을 위한 데이터다.프로그램과 메타 프로그램은 서로 다른 메타 레벨에 있다.

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

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

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

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

람다 미적분에서의 람다 리프팅

각 람다 리프트는 람다 식의 하위 표현식인 람다 추상화를 취하여 함수 호출(응용프로그램)으로 대체하여 그것이 만드는 함수로 바꾼다.하위 식의 자유 변수는 함수 호출에 대한 매개 변수다.

람다 리프트는 코드 리팩터링에서 기록된 범위 밖에서 기능을 사용할 수 있도록 개별 기능에 사용될 수 있다.프로그램을 변환하기 위해 표현에 람다 추상화가 없을 때까지 그러한 리프트도 반복될 수 있다.

람다 리프트

리프트는 그 표현식의 맨 위로 들어올리기 위해 표현 내에서 하위 표현으로 주어진다.이 표현은 더 큰 프로그램의 일부일 수 있다.이를 통해 하위 표현이 해제되는 위치를 제어할 수 있다.프로그램 내에서 리프트를 수행하는 데 사용되는 람다 리프트 작동은,

\operatorname {lambda-lift-op} [S,L,P]=P[L:=\operatorname {lambda-lift} [S,L]]

하위 식은 람다 추상화 또는 매개변수에 적용된 람다 추상화일 수 있다.

두 가지 종류의 리프트가 가능하다.

익명 리프트
명명된 리프트

익명의 리프트는 람다 추상화일 뿐인 리프트 표현을 가지고 있다.그것은 익명의 함수를 정의하는 것으로 간주된다.함수에 대한 이름을 만들어야 한다.

이름된 리프트 표현식은 표현에 적용된 람다 추상화를 가지고 있다.이 리프트는 함수의 명명된 정의로 간주된다.

익명 리프트

익명의 리프트는 람다 추상화(S라고 한다)를 취한다.S의 경우;

S(V라고 함)를 대체할 함수의 이름을 만드십시오.V로 식별된 이름을 사용하지 않았는지 확인하십시오.
S의 모든 자유 변수에 대해 V에 매개 변수를 추가하여 표현식 G를 생성하십시오(통화 만들기 참조).

람다 리프트는 함수에 대한 정의의 추가와 함께 함수 적용을 위한 람다 추상화 S를 대체하는 것이다.

\operatorname {lambda-lift} [S,L]\equiv \operatorname {let}V:\operatorname {de-lambda} [G=S]\operatorname {in} L[S:=G]

새 람다 표현은 S를 G로 대체했다. 유의사항 L[S:=G]은 L에서 G로 S를 대체하는 것을 의미한다.함수 정의에는 함수 정의 G = S가 추가된다.

위의 규칙에서 G는 S를 대신하는 함수 응용 프로그램이다.정의는 다음과 같다.

G=\operatorname {make-call} [V}[S]

여기서 V는 함수 이름이다.새로운 변수, 즉 람다 표현에서 아직 사용되지 않은 이름이어야 한다.

V\in \in \in \in \operatorname {vars} [\operatorname {let}F\operatorname {in} L]

여기서 $\operatorname {vars} [E]$ $\operatorname {vars} [E]$ [ $\operatorname {vars} [E]$ $\operatorname {vars} [E]$ $\operatorname {vars} [E]$ 은(는) E에서 사용된 변수 집합을 반환하는 메타 함수다 $\operatorname {vars} [E]$ .

익명 리프트의 예.
예를 들어, ${\reasoned}F&=\operatorname {true} \\L&=\lambda f.(\lambda x.f\ (x\ x)\ (\lambda x.f\ (x\x\ x)\)\\S&=\lambda x.f\(x\ x)\\\G&=p\ f\end{aigned}$ $\de-fda} [p\ f=\fda x.f\(x\ x)]\equiv p\ x=f\ (x\ x)$ 식을 허용하려면 람다에서 변환의 de-람바를 참조하십시오.결과는, $\operatorname {lambda-lift} [\lambda x.f\ (x\ x),\operatorname {let} \operatorname {true} \operatorname {in} \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]\equiv \operatorname {let} p\ f\ x=f\ (x\ x)\operatorname {in} \lambda f.(p\ f)\ (p\ f)$

통화 구성

함수 호출 G는 함수 H에 자유 변수 집합(V로 표현됨)의 각 변수에 대한 파라미터를 추가하여 생성된다.

$X\in V\to \operatorname {make-call} [H,V]\equiv \operatorname {make-call} [H,V\cap \neg \{X\}]\ X$
$\operatorname {make-call} [H,\\{\}]\equiv H$

통화 구성의 예.
$[\displaystyle S=\lambda x.f\ (x\ x)}$ $\operatorname {FV}(S)=\{f\}$ $G\equiv \operatorname {make-call} [S]\equiv \operatorname {make-call} [p,\{F\}]\equiv p\f\f$

명명된 리프트

명명된 리프트는 기능명 V가 제공된 것을 제외하고 익명 리프트와 유사하다.

\operatorname {lambda-lift} [(\lambda V).E)\ S,L]\equiv \operatorname {let} V:\operatorname {de-lambda} [G=S]\operatorname {in} L[(\lambda V).E)\S:=E[V:=G]

익명 인양의 경우, G라는 표현은 S의 자유 변수를 적용하여 V로부터 생성된다.정의는 다음과 같다.

G=\operatorname {make-call} [V}[S]

명명된 리프트의 예.
예를 들어, ${\begin}V&=x\\E&=f$x\x)\\\S&=(\lambda x.f\ (x\ x)\\L&=\lambda f.(\lambda x.f\(x\ x)\(\lambda x.f\ (x\ x)\\\\G&=x\ f\end{aigned}}$ $E[V:=G]=f\(x\ x)[x:=x\ f]=f\(x\ f)\(x\ f)$ $L[(\lambda V.E)\ F:=E[V:=G]=L[(\lambda x.f\(x\x$$x\x$]=f$x\f)=\lambda f.f\(x$(x\f)}$ $\de-fda} [x\ f=\fda y.f\(y\ y)]\equiv x\ y=f\(y\ y)$ 식을 허용하려면 람다에서 변환의 de-람바를 참조하십시오.결과는, 주는 것, $\operatorname {lambda-lift} [(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)),\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]\equiv \operatorname {let} x\ f\ y=f\ (y\ y)\operatorname {in} \lambda f.(x\ f)\ (x\ f)$

람다-리프트 변환

람다 리프트 변환은 람다 표현을 사용하고 모든 람다 추상화를 표현식의 맨 위로 들어 올린다.그런 다음 추상화는 람다 추상화를 제거하는 재귀 함수로 번역된다.그 결과, 그 형태는 기능적인 프로그램이고

$\operatorname {let}M\operatorname {in}N$

여기서 M은 함수 정의의 연속이며, N은 반환된 값을 나타내는 표현식이다.

예를 들어,

\operatorname {lambda-lift-tran} [\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]\equiv \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p

그런 다음 디레트 메타 함수를 사용하여 결과를 람다 미적분으로 다시 변환할 수 있다.

[\displaystyle \de-let}[\da-lift-lift-lift-lift-lift-lift-lift-late}][\da x.f\ (x\x\)]]\equiv(\da p.(\da q\)\\da p.\lambda f.(p\ f)\ (p\ f)\\\\\lambda f.\lambda x.f\ (x\ x)}

람다 표현을 변형시키는 과정은 일련의 승강기이다.각각의 리프트는,

리프트 선택 기능에 의해 선택된 하위 표현식.하위 식을 선택하여 람다 없이 방정식으로 변환할 수 있도록 해야 한다.
리프트는 다음 절에서 설명한 람다 리프트 메타 함수에 대한 호출에 의해 수행된다.

{\begin}\operatorname {lambda-lift-tran} [L]=\operatorname {merge-let}[\operatorname {lambda-apply} [L]]\\operatorname {lambda-apply} [L]=\operatorname {lambda-process}[\operatorname {lift-choice}[L]\operda-processname {lambda-process}[\opername {none},L]=L\\\operatorname {lambda-process} [S,L]=\operatorname {lambda-apply}[\operatorname {lambda-lift}[S,L]]\case}}}

리프트를 적용한 후, 렛츠는 하나의 렛츠로 결합된다.

{\begin{case}\operatorname {merge-let}[\operatorname {let}V:E\operatorname {in} \operatorname {let} W:F\operatorname {in}G]=\operatorname {merge-let} [\operatorname {let}V, W:E\land F\operatorname {in}G]\\\\operatorname {merge-let} [E]=E\end{case}

그런 다음 "let" 식에 필요하지 않은 매개변수를 제거하기 위해 매개변수 드롭을 적용한다.let 표현식은 함수 정의가 서로 직접 참조할 수 있도록 하는 반면, 람다 추상화는 엄격히 계층적이며, 함수는 그 자체를 직접 참조하지 않을 수 있다.

리프팅에 사용할 표현식

리프팅을 위해 표현을 선택할 수 있는 두 가지 다른 방법이 있다.첫번째는 모든 람다 추상화를 익명의 함수를 정의하는 것으로 간주한다.둘째, 매개변수에 적용되는 람다 추상화를 함수를 정의하는 것으로 처리한다.매개변수에 적용된 람다 추상화는 함수를 정의하는 레트 식 또는 익명 함수를 정의하는 것으로 이중 해석을 한다.두 해석 모두 유효하다.

이 두 술어는 두 가지 정의에 모두 필요하다.

람다 프리 - 람다 추상화를 포함하지 않는 표현식.

{\begin{case}\operatorname {lambda-free} [\lambda F.X]=\operatorname {false} \\\operatorname {lambda-free} [V]=\operatorname {true} \\operatorname {lambda-free} [M\N]=\land \operatorname {lambda-free} [N]\endcase}

람다-아논 - 익명 함수. $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ . $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ . $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ . . $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ n . $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ ${\displaystyle \lambda x_{1}.\\\\lambda x_{n}.$ $X}$ 여기서 $\lambda x_{1}.\ ...\ \lambda x_{n}.X$ X는 람다 무료.

{\displaystyle {\begin{case}\operatorname {lambda-anon}[\lambda F.X]=\operatorname {lambda-free} [X]\lor \operatorname {lambda-anon} [X]\\\operatorname {lambda-anon} [V]=\operatorname {lambda-anon} [M\n]=\operatorname {fald {case}}}}}}}}.

리프팅 전용 익명 기능 선택

가장 깊은 익명의 추상화를 검색하여 리프트를 적용할 때 해제된 함수가 단순한 방정식이 되도록 한다.이 정의는 매개변수가 있는 람다 추상화를 함수를 정의하는 것으로 인식하지 않는다.모든 람다 추상화는 익명의 기능을 정의하는 것으로 간주된다.

리프트 선택 - 표현식을 가로지르는 과정에서 발견된 첫 번째 익명 또는 함수가 없는 경우 없음.

$\operatorname {lambda-anon} [X]\to \operatorname {lift-선택}[X]=X$
$\operatorname {lift-choice} [\lambda F.X]=\operatorname {lift-choice} [X]$
${\displaystyle \operatorname {lift-choice} [M]\neq \operatorname {none} \to \operatorname {lift-choice} [M]$
$\operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [N]$
$\operatorname {lift-choice} [V]=\operatorname {none}$

예를 들어,

Lambda choice on

\lambda f.(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))

is

\lambda x.f\ (x\ x)

규칙	함수형	선택하다
2		$\proxname {lift-choice}[\da x.f\ (x\ x)\ (\data y.f\ (y\ y)]]$
3		$\propertyname {lift-choice}[(\data x.f\ (x\ x)]\(\data y.f\ (y\ y)]]$
1	아논	$\propertyname {lift-choice}[\data x.f\ (x\ x)]$
		$\displaystyle \putda x.f\ (x\ x)}$

\lambda f.(p\ f)\ (p\ f)

\lambda f.(p\ f)\ (p\ f)

.

\lambda f.(p\ f)\ (p\ f)

(

\lambda f.(p\ f)\ (p\ f)

\lambda f.(p\ f)\ (p\ f)

)

\lambda f.(p\ f)\ (p\ f)

(

\lambda f.(p\ f)\ (p\ f)

f

\lambda f.(p\ f)\ (p\ f)

)

{\displaystyle \lambda f.

(

p\

f

)\(p\

f)\(p\ f

)}

에서

\lambda f.(p\ f)\ (p\ f)

람다를 선택하면

\lambda f.(p\ f)\ (p\ f)

f

\lambda f.(p\ f)\ (p\ f)

(

\lambda f.(p\ f)\ (p\ f)

\lambda f.(p\ f)\ (p\ f)

(

\lambda f.(p\ f)\ (p\ f)

\

\lambda f.(p\ f)\ (p\ f)

)\

displaysty \lambda f.

(p

\

f)\)}이다.

규칙	함수형	선택하다
2	아논	$\designname {lift-choice}[\data f.(p\ f)\(p\ f)]$
2		$\displaystyle \lambda f.(p\ f)\(p\ f)}$

리프팅을 위해 명명된 기능 및 익명 기능 선택

리프트를 적용할 때 해제된 함수가 단순한 방정식이 되도록 가장 깊은 이름 또는 익명의 함수 정의를 검색한다.이 정의는 실제 매개변수가 있는 람다 추상화를 함수를 정의하는 것으로 인식한다.응용 프로그램이 없는 람다 추상화만 익명의 함수로 취급된다.

람다라는 이름의

명명된 함수.(

(\lambda F.M)\ N

(\lambda F.M)\ N

(\lambda F.M)\ N

)

(\lambda F.M)\ N

{\displaystyle (\lambda

F)과 같은 표현

.

M)\ N}

여기서

(\lambda F.M)\ N

M은 람다 프리, N은 람다 프리 또는 익명 함수.

{\begin{array}{l}\operatorname {lambda-name} [(\lambda F).M)\ N]=\operatorname {lambda-free} [M]\land \operatorname {lambda-anon} [N]\\\\operatorname {lambda-name} [\lambda F]X]=\operatorname {false} \\\operatorname {lambda-name} [V]=\operatorname {false} \end{array}}}}

리프트 선택

식을 통과하거나 함수가 없는 경우 none에서 찾을 수 있는 첫 번째 익명 또는 명명된 함수.

$\operatorname {lambda-name} [X]\lor \operatorname {lambda-anon} [X]\to \operatorname {lift-choice} [X]=X$
$\operatorname {lift-choice} [\lambda F.X]=\operatorname {lift-choice} [X]$
${\displaystyle \operatorname {lift-choice} [M]\neq \operatorname {none} \to \operatorname {lift-choice} [M]$
$\operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [N]$
$\operatorname {lift-choice} [V]=\operatorname {none}$

예를 들어,

Lambda choice on

\lambda f.(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))

is

(\lambda x.f\ (x\ x))\ (\lambda y.f\ (y\ y))

규칙	함수형	선택하다
2		$\proxname {lift-choice}[\da x.f\ (x\ x)\ (\data y.f\ (y\ y)]]$
1	이름 지어진	$\propertyname {lift-choice}[(\data x.f\ (x\ x)]\(\data y.f\ (y\ y)]]$
		$(\displaystyle)(\data x.f\ (x\ x)\ (\data y.f\ (y\ y))}$

\lambda f.f\ ((x\ f)\ (x\ f))

\lambda f.f\ ((x\ f)\ (x\ f))

.

\lambda f.f\ ((x\ f)\ (x\ f))

(

\lambda f.f\ ((x\ f)\ (x\ f))

(

\lambda f.f\ ((x\ f)\ (x\ f))

f

\lambda f.f\ ((x\ f)\ (x\ f))

)

\lambda f.f\ ((x\ f)\ (x\ f))

(

\lambda f.f\ ((x\ f)\ (x\ f))

\lambda f.f\ ((x\ f)\ (x\ f))

)

\lambda f.f\ ((x\ f)\ (x\ f))

)

{\displaystyle \lambda f.f\ (x\

f

)\(

\lambda f.f\ ((x\ f)\ (x\ f))

\

f

\lambda f.f\ ((x\ f)\ (x\ f))

의 람다 선택

\lambda f.f\ ((x\ f)\ (x\ f))

은

\lambda f.f\ ((x\ f)\ (x\ f))

f . f .

\lambda f.f\ ((x\ f)\ (x\ f))

(

\lambda f.f\ ((x\ f)\ (x\ f))

x

\lambda f.f\ ((x\ f)\ (x\ f))

)

{\displaystyle \lambda

f

.f\ (x\ f)}

이다

\lambda f.f\ ((x\ f)\ (x\ f))

.

규칙	함수형	선택하다
1	아논	$\putname {lift-choice} [\data f.f\(x\f)\(x\f)]$
		$\displaystyle \lambda f.f\(x\f)\(x\f)}}$

예

예를 들어 Y 콤비네이터,

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

다음과 같이 들어올려진다.

\cHBNAME {let}x\f\ y=f\(y\ y)\land q\f\(x\f)\numbername {in}q\x

매개 변수 삭제 후

\cHBNAME {let}x\f\ y=f\(y\ y)\land q\f\(x\f)\cHBNAME {in}q

람다 식으로(let에서 람다 식으로 변환 참조)

\displaystyle (\displayda x.(\data Q.q)\ \data f.f\ (x\f)\\\data f.\lambda y.f\ (y\ y)}

명명된 기능 및 익명 기능 해제

	람다 표현식	함수	보낸 사람	에게	변수
1	$\displaystyle \lambda f.(\displayda x.f\ (x\ x)\(\displayda x.f\ (x\ x))}$	진실의	${\displaystyle(\data x.f\ (x\ x)\ (\data x.f\ (x\ x)}}$	$(\displaystayle x\ f}$	$\{x,f\}$
2	$(\displaystyle)(\data x.f$x\x$(\data x.f$x\ x))))}$ $[(\data x.f\ (x\ x)$(\data x.f\ (x\ x)):=f\(x\ f)\(x\ f)]$	$[\displaystyle x\ f=\fda y.f\ (y\ y)}$			$\{x,f,p\}$
3	$\displaystyle \lambda f.f\(x\f)\(x\f)}}$	$(y\displaystyle x\ f\ y=f\ (y\ y)}$	$\displaystyle \lambda f.f\(x\f)\(x\f)}}$	$(\displaystyle q\ x}$	$\{x,f,p\}$
4	$[\displaystyle \lambda f.f\(x\f)\(x\f)][\\f.f\ (x\f)\ (x\ f)\ (x\ f)):=q\ x]}$	$[\displaystyle x\ f\ y=f\(y\ y)\land q\ x=\f.f\(x\f)\(x\f)}$			$\{x,f,p,q\}$
5	$(\displaystyle q\ x}$	$[\displaystyle x\ f\ y=f\(y\ y)\land q\ x=f\(x\f)\(x\f)}$			$\{x,f,p,q\}$

익명 기능만 들어 올리면 Y 콤비네이터는

\p\p\x=f\(x\ x)\land q\p\f\p\f\(p\\ f)\(p\ f)\\p\name {in}q\p

매개 변수 삭제 후

\p\p\x=f\(x\ x)\land q\f=(p\ f)\(p\ f)\\p\pairname {in}q

람다 표현으로,

\displaystyle (\displayda p.(\p.da Q.q)\\ \da f.(p\f)\\da f.\lambda x.f\ (x\ x)}

익명 기능만 해제

	람다 표현식	함수	보낸 사람	에게	변수
1	$\displaystyle \lambda f.(\displayda x.f\ (x\ x)\(\displayda x.f\ (x\ x))}$	진실의	$\displaystyle \putda x.f\ (x\ x)}$	$p\displaystyle p\ f}$	$\{x,f\}$
2	$(\displaystyle)(\data x.f\(x\ x)(\data x.f\(x\ x))))[\\cHBDA x.f\(x\ x):=p\f]}$	$(x\displaystyle p\ f=\fda x.f\ (x\ x)}$			$\{x,f,p\}$
3	$\displaystyle \lambda f.(p\ f)\(p\ f)}$	$(x\displaystyle p\ f\ x=f\ (x\ x)}$	$\displaystyle \lambda f.(p\ f)\(p\ f)}$	$(\displaystyle q\ p}$	$\{x,f,p\}$
4	$\displaystyle \pda f.(p\f)\(p\f)\\\\\\=q\p]}$	$\displaystyle p\f\ x=f\(x\ x)\land q\p=\p=\p=\pda f.(p\f)\(p\f)$			$\{x,f,p,q\}$
5	$p}(\displaystyle q\ p})$	$displaystyle p\f\(x\x\x)\land q\p\p\f=(p\f)\(p\f)\(p\f)}$			$displaystyle \{x,f,p,q\}}}$

들어올리기 위해 선택할 첫 번째 하위 표현식은 $\lambda x.f\ (x\ x)$ x . $\lambda x.f\ (x\ x)$ ( $\lambda x.f\ (x\ x)$ $\lambda x.f\ (x\ x)$ $){\displaystyle \lambda$ x $.f\$ ( $x\$ x $)}$ 입니다 $\lambda x.f\ (x\ x)$ 이렇게 하면 람다 식이 $\lambda f.(p\ f)\ (p\ f)$ f $\lambda f.(p\ f)\ (p\ f)$ . $\lambda f.(p\ f)\ (p\ f)$ ( $\lambda f.(p\ f)\ (p\ f)$ $\lambda f.(p\ f)\ (p\ f)$ ) $\lambda f.(p\ f)\ (p\ f)$ ( p f $\lambda f.(p\ f)\ (p\ f)$ ) ${\displaystyle \lambda$ f $.(p\$ f $)\(p$ \ f)\( $p$ $\ f)}$ 로 변환되고 $\lambda f.(p\ f)\ (p\ f)$ p $p\ f\ x=f(x\ x)$ $p\ f\ x=f(x\ x)$ = $p\ f\ x=f(x\ x)$ ( $p\ f\ x=f(x\ x)$ ) ${\displaystyp$ p\ $f\$ x $(x\ x)}$ 방정식이 생성된다 $p\ f\ x=f(x\ x)$

들기 위해 선택할 두 번째 하위 표현식은 $\lambda f.(p\ f)\ (p\ f)$ f $\lambda f.(p\ f)\ (p\ f)$ . $\lambda f.(p\ f)\ (p\ f)$ ( $\lambda f.(p\ f)\ (p\ f)$ $\lambda f.(p\ f)\ (p\ f)$ ) $\lambda f.(p\ f)\ (p\ f)$ ( $\lambda f.(p\ f)\ (p\ f)$ f $\lambda f.(p\ f)\ (p\ f)$ ) ${\displaystyle \lambda f.(p\$ f $)\ (p\$ f $)}$ 입니다 $\lambda f.(p\ f)\ (p\ f)$ 이렇게 하면 람다 식이 $q\ p$ $q\ p$ $q\ p$ 로 변환되고 $q\ p$ $q\ p\ f=(p\ f)\ (p\ f)$ $q\ p\ f=(p\ f)\ (p\ f)$ $q\ p\ f=(p\ f)\ (p\ f)$ = $q\ p\ f=(p\ f)\ (p\ f)$ ( $q\ p\ f=(p\ f)\ (p\ f)$ $q\ p\ f=(p\ f)\ (p\ f)$ ) ${\displaystyle q\p\=(p\$ f $)\(p\$ f $)}$ 등식이 생성된다 $q\ p\ f=(p\ f)\ (p\ f)$

그리고 결과는,

\p\p\x=f\(x\ x)\land q\f\p\f\(p\\ f)\ (p\ f)\\p\in}q\

놀랍게도 이 결과는 명명된 함수를 들어 올려서 얻은 결과보다 간단하다.

실행

$K$ 에 기능을 적용한다.

{\begin{cases}\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\ K&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\ \operatorname {in} \ q\ p\ K\\(\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x))&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\ \operatorname {in} \ p\ K\ (p\ K)\\K\ ((\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x)))&\\\\operatorname {let} \p\x\(x\x\x)\land q\p\f\p\f\\\\\operatorname {in} \ K\(p\ Kcase}\case}\case

그렇게

(\displaystyle)(\lambda x.K\ (x\ x)\ (\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x)))=K\ (\lambda x.K\ (x\ x)\ (\lambda x.K\ (x\ x))\ }\ }

또는

(\displaystyle p\ K\ (p\ K)=K\ (p\ K)}

Y 콤비네이터는 그 파라미터(기능)를 스스로 반복적으로 호출한다.함수에 고정점이 있으면 값을 정의한다.그러나 그 기능은 결코 종료되지 않을 것이다.

람다 미적분에서 람다 강하

람다 드롭은^[4] 함수의 범위를 축소하고 축소된 범위로부터의 컨텍스트를 이용하여 함수에 대한 매개변수의 수를 감소시키고 있다.매개변수 수를 줄이면 함수를 이해하기 쉽다.

람다 리프팅 섹션에서는 먼저 들어올린 다음 결과 람다 식을 재귀 방정식으로 변환하는 메타 함수가 설명되었다.람다 드롭 메타 함수는 먼저 재귀 방정식을 람다 추상화로 변환한 다음 결과 람다 식을 람다 추상화에 대한 모든 참조를 포함하는 가장 작은 범위로 삭제하여 역순을 수행한다.

람다 드롭은 두 단계로 이루어진다.

싱킹
매개 변수 삭제

람다 드롭

람다 드롭은 프로그램의 일부인 표현식에 적용된다.드롭은 드롭이 제외될 일련의 표현에 의해 제어된다.

\operatorname {lambda-drop-op}[L,P,X]=P[L:=\operatorname {drop-params-tran}[\operatorname {sink-test}[L,X]]]

어디에

L은 떨어뜨릴 람다 추상화다.

P는 프로그램이다.

X는 드롭에서 제외할 표현들의 집합이다.

람다 드롭 변환

람다 드롭 변환은 표현에서 모든 추상적 개념을 가라앉힌다.함몰은 일련의 표현에서 제외된다.

\operatorname {lambda-drop-tran} [L,X]=\operatorname {sink-tran}[\operatorname {de-let} [L,X]]

어디에

L은 변형될 표현이다.

X는 드롭에서 제외할 하위 표현식의 집합이다.

싱크홀딩은 가장 안쪽부터 시작하여 각각의 추상화를 가라앉힌다.

{\begin{case}\operatorname {sink-tran}[(\lambda N).B)\ Y,X]=\operatorname {sink-test} [(\lambda N.\operatorname {sink-tran} [B])\ \operatorname {sink-tran} [Y],X]\\\operatorname {sink-tran} [\lambda N.B,X]=\lambda N.\operatorname {sink-tran} [B,X]\\\operatorname {sink-tran} [M\ N,X]=\operatorname {sink-tran} [M,X]\ \operatorname {sink-tran} [M,X]\\\operatorname {sink-tran} [V,X]=V\end{case}

추상화 싱킹

침몰은 람다 추상화를 가능한 한 안쪽으로 이동하여 변수에 대한 모든 참조를 여전히 벗어나도록 하는 것이다.

신청 - 4건

{\displaysty}E\in \in \operatorname {FV} [G]\land E\in \in \in \operatorname {FV} [H]\to \operatorname {sink}[(\lambda E)]G\ H)\ Y,X]=G\ H\\E\not \in \operatorname {FV} [G]\land E\in \operatorname {FV} [H]\\\to \operatorname {sink}[\lambda E] [(\lambda E)]G\ H)\ Y,X]=\operatorname {sink-test} [G\ \operatorname {sink-test} [(\lambda E)]H)\ Y,X]\\\E\in \operatorname {FV}[G]\land E\not \in \in \operatorname {FV}[H]\to \operatorname {sink}[(\lambda E)][\\lambda E]G\ H)\ Y,X]=(\operatorname {sink-test} [(\lambda E).G)\\ Y,X]\\H\\E\in \operatorname {FV}[G]\land E\in \operatorname {FV}[H]\to \operatorname {sink}[(\lambda E)][\lambda E]G\ H)\ Y,X]=(\lambda E)G\H)\ Y\end{case}

추상화.변수 이름이 모두 구별되도록 하려면 이름을 바꾸십시오.

\displaystyle V\neq W\to \operatorname {sink}[(\lambda V).\람바 W.E)\ Y,X]=\lambda W.\operatorname {sink-test}[(\lambda V).E)\ Y,X]}

변수 - 사례 2개

\displaystyle E\neq V\to \operatorname {sink}[(\lambda E).V)\ Y,X]=V}

E=V\to \operatorname {sink} [(\lambda E).V)\ Y,X]=Y

싱크 테스트에서 식이 떨어지는 것을 제외한다.

L\in X\to \operatorname {sink-test}[L,X]=L

L\not \in X\to \operatorname {sink-test} [L,X]=\operatorname {sink} [L,X]

예

싱킹 예

예를 들어,

규칙

표현

디레트

\cHBNAME {de-let}[\dataname {de-let}] [\data.f\ p\ x\(x\\)\land q\p\=(p\f)\\p\name {in}q\]

가라앉은

\photname {displaystyle \p.[(\da q.q\p)\(\data p)]\(\data p.\lambda f.(p\f)\(p\f)\\\\\\\\\\\da f.\lambda x.f\ (x\ x)]

적용

$\computname} [(\da p)]\operatorname {sink} [(\lambda q.q\ p)\(\dada p)\(\dada p.\lambda f.(p\f)\ (p\f)]\\ (\lambda f)\lambda x.f\ (x\ x)]$
$\cHBNAME}[(\da q.q\ p)\\(\da p)\(\data p.\lambda f.(p\ f)\(p\ f)]$
$E\in \operatorname {FV} [G]\land E\in \in \operatorname {FV} [H]\to \operatorname {sink}[(\lambda E)] [(\lambda E)]G\ H)\ Y,X]$
$E=q,G=q,H=p,Y=(\lambda p)\lambda f.(p\f)\(p\f),X=\{\}$
${\displaystyle(\operatorname {sink}) [(\lambda E).G)\Y,X]\H}$
${\displaystyle(\displayname {displayname}[(\da q.q.)\(\da p.\lambda f.(p\f)\(p\f),X]\p}$

변수

$\computname} [(\da p)]\operatorname {sink} [(\lambda q.q.)\(\lambda p.\lambda f.(p\f)\(p\f)\\p)\\\\\\\\\\\\\\\\\bda f.\lambda x.f\ (x\ x)]$
$\computname {displayda q.q)\(\displayda p.\lambda f.(p\ f)\(p\ f)]$
$E=V\to \operatorname {sink} [(\lambda E).V)\ Y,X]$
$(\displaystyle E=q,V=q,Y=(\lambda p)\lambda f.(p\f)\(p\f),X=\{\}}$
$(\디스플레이 스타일 Y})$
$(\displaystyle)(\da p.\lambda f.(p\ f)\ (p\ f)}}$

적용

$\computname {displayname} [(\da p.)(\da p.)(\da p.\lambda f.(p\ f)\(p\f)\p)\\\\\\\\\\\\\\\bda f.\lambda x.f\ (x\ x)]$
$\displaystyle E\in \in \operatorname {FV} [G]\land E\in \operatorname {FV} [H]\\to \operatorname {sink}[(\lambda E)] [(\lambda E)]G\ H)\ Y,X]}$
$(\displaystyle E=p,G=(\lambda p)\lambda f.(p\ f)\(p\ f),H=p,Y=(\lambda f.\lambda x.f\ (x\ x)}$
$\operatorname {sink} [G\ \operatorname {sink}] [(\lambda E).H)\ Y,X]$

변수

$\computname} [(\da p)]\lambda f.(p\ f)\(p\ f)\\\\\ \dataname {pa-test}[(\pa p.p)\(\pairda f).\lambda x.f\(x\ x),X]$
$\putname {displayda p.p)\(\displayda f.\lambda x.f\(x\ x),X]$
$E=V\to \operatorname {sink} [(\lambda E).V)\ Y,X]$
$(\displaystyle E=p,V=p,Y=(\lambda f)\lambda x.f\ (x\ x),X=\{\}}$
$(\디스플레이 스타일 Y})$
$디스플레이 스타일(\displaystyle)(\da f.\lambda x.f\ (x\ x)}$

추상화

$\computname} [(\da p)]\lambda f.(p\ f)\(p\ f)\\(\p\f)\\\\\da f.\lambda x.f\ (x\ x)]$
$\displaystyle V\neq W\to \operatorname {sink}[(\lambda V).\람바 W.E)\ Y,X]}$
$V=p,W=f,E=(p\f)\,Y=(\lambda f)\lambda x.f\ (x\ x)$
$\lambda W.\operatorname {sink} [(\lambda V).E)\ Y,X]$

적용

$\displaystyle \lambda f.\cHB 이름 { {} [(\lambda p.(p\f)$p\f)$\(\dada f)\(\lambda f)\(\lambda f).\lambda x.f\(x\ x),X]}$
$\cHBNAME}[(\da p.(p\f)\(p\f)\\(\da f)\(\da f)]\(\data f)\\lambda x.f\(x\ x),X]$
$E\in \operatorname {FV} [G]\land E\in \in \operatorname {FV} [H]\\to \operatorname {sink}[(\lambda E)][\lambda E]G\ H)\ Y,X]$
$E=p,G=(p\f),H=(p\f),Y=(\lambda f)\lambda x.f\ (x\ x)$
$(\displaystyle)(\lambda E.G\ H)\ Y}$
$(\displaystyle)(\p.da p.(p.p.p.f)\(p\f)\(\p.da f)\\(\p.da f.\lambda x.f\ (x\ x)}$

\displaystyle \lambda f.(\lambda p.(p\f)\(p\f)\(\p\f)\(\\da f)\(\lambda f).\lambda x.f\ (x\ x)}

매개 변수 삭제

매개변수 감소는 함수의 위치에 대한 함수를 최적화하는 것이다.람다 리프팅은 기능이 컨텍스트에서 벗어날 수 있도록 필요한 매개변수를 추가했다.드롭할 때, 이 프로세스는 역전되며, 자유로운 변수를 포함하는 추가 매개변수가 제거될 수 있다.

매개 변수를 삭제하는 것은 함수에서 불필요한 매개 변수를 제거하는 것이며, 여기서 전달되는 실제 매개 변수는 항상 동일한 식입니다.표현의 자유 변수 또한 함수가 정의되는 곳에서 자유로워야 한다.이 경우 삭제되는 파라미터는 함수 정의 본문의 표현으로 대체된다.이것은 파라미터를 불필요하게 만든다.

예를 들어, 고려하라.

\displaystyle \lambda m,p,q.(\\da g)\lambda n.(n\ (g\ m\ p\n)\ (g\ q\ p\ n))\\\ \da x.\lambda o.\lambda y.o\ x\ y}

이 예에서 형식 매개변수 o에 대한 실제 매개변수는 항상 p이다.p는 전체 식에서 자유 변수인 만큼 매개변수가 삭제될 수 있다.형식 매개변수 y의 실제 매개변수는 항상 n이다.그러나 n은 람다 추상화로 묶여 있다.따라서 이 매개변수는 삭제되지 않을 수 있다.

매개변수를 삭제한 결과는,

\drop-params-params-presid}[\dropda m,p,q.(\data g).\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n)\\\ \lambda x.\lambda o.\lambda y.o\ x\ y

\displaystyle \equiv \lambda m,p,q.(\\da g)\lambda n.n\ (g\ m\n)\ (g\ q\n)\\\\ \lambda x.\p\ x\ y}

주요 예로는,

{\drop-params-params-pairname}[\dropda f.(p\f)\(\p\f)\(\data f)\(\dropda f.\lambda x.f\ (x\ x)]}

\displaystyle \equiv \equiv \equda f.p\ p)\\(\displayda x.f\ (x\ x)}}

드롭파람트랜의 정의는

\operatorname {drop-params-tran} [L]\equiv(\operatorname {drop-params}[L]])

어디에

\operatorname {build-param-list} [L,D,V,\_]

빌드 매개 변수 목록

함수를 정의하는 각 추상화에 대해, 이름을 삭제하는 결정을 내리는 데 필요한 정보를 구축한다.이 정보는 각 매개변수를 설명한다. 매개변수 이름, 실제 값에 대한 표현식 및 모든 표현식의 값이 동일하다는 표시.

예를 들어, in,

\displaystyle \lambda m,p,q.(\\da g)\lambda n.(n\ (g\ m\ p\n)\ (g\ q\ p\ n))\\\ \da x.\lambda o.\lambda y.o\ x\ y}

함수 g에 대한 매개변수는,

형식 매개 변수	모두 동일한 값	실제 파라미터 표현식
x	거짓의	_
o	진실의	p
y	진실의	n

각 추상화는 고유한 이름으로 이름이 바뀌며, 매개변수 목록은 추상화의 이름과 연관된다.예를 들어, g에는 매개변수 목록이 있다.

D[g]=[x,\operatorname {false},\_],[o,\_,p],[y,\_,n]]

빌드 매개 변수 리스트는 식을 통과하여 식에 대한 모든 목록을 작성한다.여기에는 네 가지 매개변수가 있다.

분석 중인 람다 식입니다.
테이블 매개 변수는 이름을 나열한다.
매개 변수에 대한 값 표.
반환된 매개 변수 목록(내부적으로 사용됨)

추상화 - $(\lambda N.S)\ L$ 의 람다 표현식 $(\lambda N.S)\ L$ $(\lambda N.S)\ L$ $(\lambda N.S)\ L$ ) L ${\displaystyle(\lambda N)$ $S)\ L}$ 을 $(\lambda N.S)\ L$ (를) 분석하여 함수의 매개변수 이름을 추출한다.

{\begin{case}\operatorname {build-parameter-lists} [(\lamba N).S)\ L,D,V,R]\equiv \operatorname {build-param-lists} [S,D,V,R]\land \operatorname {build-list} [L,D,V,D[N]]\\\operatorname {build-param-lists} [\lambda N.S,D,V,R]\equiv \operatorname {build-param-lists} [S,D,V,R]\end{cases}}

이름을 찾고 이름에 대한 매개 변수 목록을 작성하고 공식 매개 변수 이름을 입력하십시오.또한 표현식의 본문으로부터 실제 매개변수 목록을 수신하고, 이 표현식의 실제 매개변수 목록으로 반환

{\begin}\operatorname {build-list} [\lambda P.B,D,V,[X,\_,\_]::L]\equiv \operatorname {build-list} [B,D,V,L]\\\operatorname {build-param-list}[]\equiv \operatorname {build-param-list}[B,D,V,\]\end{case}}}

변수 - 함수에 대한 호출.

\operatorname {build-param-list} [N,D,V,D[N]]

함수 이름 또는 매개 변수의 경우 이 이름에 대한 매개 변수 목록을 출력하여 실제 매개 변수 목록을 채우기 시작하십시오.

Application - 실제 매개변수 상세정보를 추출하기 위한 Application(기능 호출)을 처리한다.

\operatorname {build-param-list} [E\ P,D,V,R]\equiv \operatorname {build-param-list}[E,D,V,T]\land \operatorname {build-param-list} [P,D,V,K]

\displaystyle \land T=[F,S,A]::R\land (S\implies (\operatorname {equate} [A,P]\land V[F]=A))\land D[F]=K}

식에 대한 매개 변수 목록과 매개 변수를 검색하십시오.표현식에서 매개 변수 목록에서 매개 변수 레코드를 검색하고 현재 매개 변수 값이 이 매개 변수와 일치하는지 확인하십시오.나중에 확인할 때 사용할 매개 변수 이름 값을 기록하십시오.

{\begin}\operatorname {equal} [A,N]\equiv A=N\lor (\operatorname {def}[V[N]]\land A=V[N])&{\text{}}}}}\dext{}}}이 변수다.}}\\\operatorname {equal}[A,E]\equiv A=E&{\text{notherwise.}}}\end{case}

위의 논리는 작용하는 방식이 상당히 미묘하다.동일한 값 표시기는 절대 true로 설정되지 않는다.모든 값을 일치시킬 수 없는 경우에만 false로 설정된다.이 값은 S를 사용하여 S에 허용된 부울 값 집합을 작성함으로써 검색된다.true가 멤버인 경우 이 파라미터의 모든 값이 같으며 파라미터가 삭제될 수 있다.

\operatorname {ask} [S]\equiv S\in \{X:X=S\}

마찬가지로, def는 변수가 값을 부여받았는지 여부를 질의하기 위해 세트 이론을 사용한다.

\operatorname {def} [F]\equiv \{X:X=F\}

Let - 표현.

\operatorname {build-param-list} [\operatorname {let} V:E\operatorname {in} L,D,V,\_]\equiv \operatorname {build-param-list}[E,D,V,\]\land \operatorname {build-param-list}[L,D,V,\]

그리고 - "let"에 사용하기 위해.

\operatorname {build-param-list}[E\land F,D,V,\]\equiv \operatorname {build-param-list}[E,D,V,\]\land \operatorname {build-param-list}[F,V,\]}]

예

예를 들어, 매개변수 목록을 작성하는 경우,

\displaystyle \lambda m,p,q.(\\da g)\lambda n.(n\ (g\ m\ p\n)\ (g\ q\ p\ n))\\\ \da x.\lambda o.\lambda y.o\ x\ y}

주는 것,

D[g]=[x,\operatorname {false},\_],[o,\operatorname {true},p],[y,\operatorname {true},n]

그리고 매개 변수 o는 주어지기 위해 삭제된다.

\displaystyle \lambda m,p,q.(\\da g)\lambda n.(n\ (g\ m\n)\ (g\ q\n))\\\ \lambda x.\lambda y.p\ x\ y}

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

,

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

,

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

(

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

.

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

n

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

.

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

(

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

(

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

m

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

n )

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

(

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

p

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

n ) ) )

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

x .

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

o .

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

y .

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

.

\lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y

.

\lambda m,p,q.(\lambda

g)에 대한 매개변수 목록을 작성한다

.

\lambda n.(n\ (g\ m\ p\n)\ (g\ q\ p\ n))\\\ \da x.\lambda o.

\lambda y.o\ x\ y}

빌드 매개 변수 목록 예제

$\param-list} [\displayda m,p,q.(\displayda g).\lambda n.(n\ (g\ m\ p\n)\ (g\ q\ p\ n))\\\ \da x.\lambda o.\lambda y.o\ x\ y,D,V,\_]$
규칙	표현
추상화	$\param-list} [\displayda m,p,q.(\displayda g).\lambda n.(n\ (g\ m\ p\n)\ (g\ q\ p\ n))\\\ \da x.\lambda o.\lambda y.o\ x\ y,D,V,\_]$
추상화	${build-param-list} [(\build-param-list}).\lambda n.(n\ (g\ m\ p\n)\ (g\ q\ p\ n))\\\ \da x.\lambda o.\lambda y.o\ x\ y,D,V,\_]}$
	$\operatorname {build-param-list}[n\g\m\p\n)\\(g\ q\p\n), D, V,R]\land \operatorname {build-list}[\lambda x.\lambda o. o.\lambda y.o\ x\ y,D,V,D[g]$

${build-list} [\displaystyle \build-list} [\buildda x.\buffda o\lambda y.o\ x\ y,D,V,D[g]}$
규칙	표현
매개 변수 추가	${build-list} [\displaystyle \build-list} [\buildda x.\buffda o\lambda y.o\ x\y,D,V,D[g]\land D[g]=L_{1}:{1}$
매개 변수 추가	${build-list} [\displaystyle \program] [\displayda o\lambda y.o\ x\ y,D,V,L_{1}]\land D[g]=[x,\_,\]::L_{1}}$
매개 변수 추가	${\displaystyle \operatorname {build-list} [\lambda y.o\ x\y,D,V,L_{2}]\land D[g]=[x,\_,\]::[o,\_,\_]::L_{2}}:$
종료 목록	$\operatorname {build-list} [o\ x\ y,D,V,L_{3}]\land D[g]=[x,\_,\]::[o,\_,\_]::[y,\_,\]::L_{3}}$
	$\operatorname {build-param-list} [o\ x\\y,D,V,[]\land D[g]=[x,\_,\]::[o,\_,\_]::[y,\_,\]::[]$

$\operatorname {build-param-list}[n\ (g\ m\ p\ n)\ (g\ q\ p\ n), D, V,R]$
규칙	표현
적용	$\operatorname {build-param-list}[n\ (g\ m\ p\ n)\ (g\ q\ p\ n), D, V,R]$
적용	$\operatorname {build-param-list}[n\ (g\ m\p\n),D,V,T_{1}]\land \operatorname {build-param-list}[g\ q\n,D,V,K_{1}]$ $\land((T_{1}=[F_{1}, S_{1}, A_{1}]:R$ $\land(S_{1}\implies(\operatorname {equate}[A_{1}g\ q\p\n]\land V[F_{1}]=g\p\n)\land D[F_{1}]=K_{1}}}}}}}$
변수	$\operatorname {build-param-lists} [n,D,V,T_{2}]\land \operatorname {build-param-lists} [g\ m\ p\ n,D,V,K_{2}]\land \operatorname {build-param-lists} [g\ q\ p\ n,D,V,K_{1}]$ $\land ((T_{2}=[F_{2}, S_{2}, A_{2}]:[F_{1},S_{1},A_{1}]:R$ $\land(S_{1}\implies(\operatorname {equate}[A_{1}g\ q\p\n]\land V[F_{1}]=g\p\n)\land D[F_{1}]=K_{1}}}}}}}$ $\land(S_{2}\implies)(\operatorname {equal}[A_{2},g\m\n]\land V[F_{2}]=g\m\p\n)\land D[F_{2}]=K_{2}}}}}}$
변수	$\operatorname {build-param-list}[g\ m\p\n,D,V,K_{2}]\land \operatorname {build-param-list}[g\ q\n,D,V,K_{1}]$ $\land((D[n]=[F_{2}, S_{2}, A_{2}]:[F_{1},S_{1},A_{1}]:R$ $\land(S_{1}\implies(\operatorname {equate}[A_{1}g\ q\p\n]\land V[F_{1}]=g\p\n)\land D[F_{1}]=K_{1}}}}}}}$ $\land(S_{2}\implies)(\operatorname {equal}[A_{2},g\m\n]\land V[F_{2}]=g\m\p\n)\land D[F_{2}]=K_{2}}}}}}$

주다,

[\displaystyle D[n]=[\_,\,\,g\m\p\n]::[\_,\,\,g\ q\ p\n]::R}

$\operatorname {build-param-list} [g\ m\p\n, D,V,K_{2}]$
규칙	표현
신청	$\operatorname {build-param-list} [g\ m\p\n, D,V,K_{2}]$
	$\operatorname {build-param-list}[g\ m\p,D,V,T_{3}]\land \operatorname {build-param-list}[n,D,V,K_{3}]$ ${\displaystyle \land ((T_{3}=[F_{3},S_{3},A_{3}]::K_{2}}:$ $\land(S_{3}\implies)(\operatorname {equate}[A_{3},n]\land V[F_{3}]=n)\land D[F_{3}]=D[n]}}}}$
응용 프로그램, 변수	$\operatorname {build-param-list} [g\m,D,V,T_{4}]\land \operatorname {build-param-list} [p,D,V,K_{4}]$ ${\displaystyle \land T_{4}=[\_,S_{4},A_{4}]::[\_,S_{3},A_{3}]::K_{2}}:$ $\land(S_{3}\implies)(\operatorname {equate}[A_{3},n]\land V[F_{3}]=n)\land D[F_{3}]=D[n]}}}}$ $\land (S_{4}\implies (\operatorname {equate}[A_{4},p]\land V[F_{4}]=p)\land D[F_{4}}]=D[p]$
응용 프로그램, 변수	$\operatorname {build-param-list} [g,D,V,T_{5}]\land \operatorname {build-param-list} [m,D,V,K_{5}]$ ${\displaystyle \land T_{5}=[F_{5},S_{5},A_{5}]:[F_{4},S_{4},A_{4}]:[F_{3},S_{3},A_{3}]::K_{2}}:$ $\land(S_{3}\implies)(\operatorname {equate}[A_{3},n]\land V[F_{3}]=n)\land D[F_{3}]=D[n]}}}}$ $\land (S_{4}\implies (\operatorname {equate}[A_{4},p]\land V[F_{4}]=p)\land D[F_{4}}]=D[p]$ $\land(S_{5}\implies(\operatorname {equal}[A_{5},m]\land V[F_{5}]=m)\land D[F_{5}}]=D[m]$
변수	${\displaystyle D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}}:$ $\land (S_{3}\implies(\operatorname {equate}[A_{3}n],\land V[y]=n)\land D[y]=D[n]]}}$ $\land (S_{4}\implies(\operatorname {equal}[A_{4},p]\land V[o]=p)\land D[o]=D[p]$ $\land(S_{5}\implies(\operatorname {equate}[A_{5}m],\land V[x]=m)\land D[x]=D[m]$

$\operatorname {build-param-list} [g\ q\ p\ n,D,V,K_{1}]$
규칙	표현
신청	$\operatorname {build-param-list} [g\ q\ p\ n,D,V,K_{1}]$
	$\operatorname {build-param-list} [g\ q\p,D,V,T_{6}]\land \operatorname {build-param-list}[n,D,V,K_{6}]$ $\land ((T_{6}=[F_{6},S_{6},A_{6}]::K_{1}$ $\land(S_{6}\implies)(\operatorname {equate}[A_{6},n]\land V[F_{6}]=n)\land D[F_{6}]=D[n]]}}$
응용 프로그램, 변수	$\operatorname {build-param-list} [g\ q,D,V,T_{7}]\land \operatorname {build-param-list} [p,D,V,K_{7}]$ $\land T_{7}=[\_,S_{7},A_{7}]::[\_,S_{6},A_{6}]::K_{1}$ $\land(S_{6}\implies)(\operatorname {equate}[A_{6},n]\land V[F_{6}]=n)\land D[F_{6}]=D[n]]}}$ $\land(S_{7}\implies(\operatorname {equal}[A_{7},p]\land V[F_{7}]=p)\land D[F_{7}}]=D[p]$
응용 프로그램, 변수	$\operatorname {build-param-list} [g,D,V,T_{8}]\land \operatorname {build-param-list} [m,D,V,K_{8}]$ $\land T_{8}=[F_{8},S_{8},A_{8}]:[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{1}$ $\land(S_{6}\implies)(\operatorname {equate}[A_{6},n]\land V[F_{6}]=n)\land D[F_{6}]=D[n]]}}$ $\land(S_{7}\implies(\operatorname {equal}[A_{7},p]\land V[F_{7}]=p)\land D[F_{7}}]=D[p]$ $\land (S_{8}\implies (\operatorname {equate}[A_{8}q]\land V[F_{8}]=q)\land D[F_{8}}]=D[q]$
변수	$D[g]=[x,S_{8},A_{8}]::[o,S_{6},A_{7}]::[y,S_{6},A_{6}]::K_{1}$ $\land(S_{6}\implies(\operatorname {equate}[A_{6}n],n]\land V[y]=n)\land D[y]=D[n]]}$ $\land (S_{7}\implies(\operatorname {equal}[A_{7},p]\land V[o]=p)\land D[o]=D[p]$ $\land(S_{8}\implies(\operatorname {eq}[A_{8}q]\land V[x]=q)\land D[x]=D[q]$

$V[n],V[p],V[q],V[m]$ 가 없으므로 V $V[n],V[p],V[q],V[m]$ [ $V[n],V[p],V[q],V[m]$ $V[n],V[p],V[q],V[m]$ , $V[n],V[p],V[q],V[m]$ [ $V[n],V[p],V[q],V[m]$ $V[n],V[p],V[q],V[m]$ , V [ $V[n],V[p],V[q],V[m]$ $V[n],V[p],V[q],V[m]$ , $V[n],V[p],V[q],V[m]$ [ $V[n],V[p],V[q],V[m]$ {\ $displaystyle V[n],$ $V[p],V[q],V[m$ 그러면 다음과 같이 단순화할 수 있다.

\operatorname {equal}[A,N]\equiv A=N\lor(\operatorname {def}[V]]\land A=V[N])\equiv A=N

$D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ 하지 않은 식을 제거함으로써 D $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ [ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ = $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ [ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ , S $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ , $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ A $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ : [ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ , $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ , $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ : [ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ , $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ , $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ : : $D[g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}$ 2 ${\$ D $[g]=[x,S_{5},A_{5}]:$ $:[o,S_{4},A_{4}]:$ $:[y,S_{3},A_{3}]:$ $:K_{2}}:$

\land S_{3}\implies A_{3}=n

\land S_{4}\implies A_{4}=p

\land S_{5}\implies A_{5}=m

$D[g]=[x,S_{8},A_{8}]::[o,S_{6},A_{7}]::[y,S_{6},A_{6}]::K_{1}$

\land S_{6}\implies A_{6}=n

\land S_{7}\implies A_{7}=p

\land S_{8}\implies A_{8}=q

$D[g]$ [ $D[g]$ $D[g]$ $D[g]$ 의 두 식을 비교함으로써 $D[g]$

{\displaystyle S_{5}=S_{8},A_{5}=A_{8},S_{4}=S_{7},A_{4}=A_{7},S_{3}=S_{6}},A_{3}=A_{6}}}.

$S_{3}$ $S_{3}$ ${\$ 이 $S_{3}$ 참인 경우;

n=A_{3}=A_{6}=n

$S_{3}$ $S_{3}$ ${\$ 이 $S_{3}$ (가) 거짓이면 함축성이 없다.그래서 S $S_{3}=\_$ = $S_{3}=\_$ $S_{3}=\_$ 은 $S_{3}=\_$ (는) 진실일 수도 있고 거짓일 수도 있다는 뜻이다.

$S_{4}$ $S_{4}$ ${\$ 이 $S_{4}$ (가) 참인 경우;

p=A_{4}=A_{7}=p

$S_{5}$ $S_{5}$ ${\$ 이 $S_{5}$ (가) 참인 경우;

m=A_{5}=A_{8}=q

$S_{5}$ $S_{5}$ 5 ${\$ 는 거짓이다 $S_{5}$ .

결과 D $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ [ $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ = $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ [ $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ , $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ , $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ : [ $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ , $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ : $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ [ $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ y $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ , $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ , $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ : $D[g]=[x,\operatorname {false} ,\_]::[o,\_,p]::[y,\_,n]::\_$ ${\displaystyle D[g]=[x,\operatorname$ { $false} ,\_]:$ $:[o,\_,p]:$ $:[y,\_,n]:$ $:\_}$

$\operatorname {build-param-list} [o\ x\ y,D,V,L]$
규칙	표현
신청	$\operatorname {build-param-list} [o\ x\ y,D,V,L]$
신청	$\operatorname {build-param-list}[o\x,D,V,T_{9}]\land \operatorname {build-param-list}[y,D,V,K_{9}]$ $\land T_{9}=[F_{9},S_{9},A_{9}]:L$ $\land(S_{9}\implies)(\operatorname {eqe}[A_{9}y]\land V[F_{9}]=A_{9}\land K_{9}=D[F_{9}]$
가변적	${\displaystyle \operatorname {build-param-list} [o,D,V,T_{10}]\land \operatorname {build-param-list}[y,D,V,K_{10}][D,V,K_{10}}]$ $\land T_{10}=[F_{10},S_{10},A_{10}]:[F_{9},S_{9},A_{9}]:L$ $\land(S_{9}\implies)(\operatorname {eqe}[A_{9}y]\land V[F_{9}]=A_{9}\land K_{9}=D[F_{9}]$ $\land(S_{10}\implies)(\operatorname {eqe}[A_{10}y]\land V[F_{10}]=A_{10}\land K_{10}=D[F_{10}]$
	$\displaystyle \land D[o]=[F_{10},S_{10},A_{10}]:[F_{9},S_{9},A_{9}]:L}$ $\land(S_{9}\implies)(\operatorname {eqe}[A_{9}y]\land V[F_{9}]=A_{9}\land K_{9}=D[F_{9}]$ $\land(S_{10}\implies)(\operatorname {eqe}[A_{10}y]\land V[F_{10}]=A_{10}\land K_{10}=D[F_{10}]$

위에서 사용된 것과 유사한 논거에 의해,

[\displaystyle D[o]=[\_,\_,x]::[\_,\_,y]::\_}

그리고 아까부터.

D[g]=[x,\operatorname {false},\_],[o,\operatorname {true},p],[y,\operatorname {true},n]

[\displaystyle D[n]=[\_,\,\, (g\m\p\n)]], [\_,\,\, (g\ q\p\n)]]}

D[m]=\_}

D[p]=\_

D[q]=\_

또 다른 예는,

(\displaystyle \p.f.f.(\da p.f\ (p\p\f))\\\\da q.x\ (q\ q\ x)}}

여기서 x는 f와 같다.파라미터 목록 매핑은,

D[p]=[q,\_,p],[x,\_,f]

x라는 매개 변수가 삭제되어

\displaystyle \lambda f.((\lambda q.f\ (q\ q)\)(\dada q.f\ (q\ q)}}

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

.

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

( (

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

.

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

( p

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

))(

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

.

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

x .

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

(

\lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))

x )

{\displaystyle \lambda

f.f\

(\lambda p.f\ (p\ p\

p\ f

)\\\\\\\\lambda q\x)

에 대한 매개 변수 목록 작성

동일본의 논리는 이 보다 어려운 예에서 사용된다.

$\operatorname {build-param-list}[\lambda p.f\ (p\p\f)]\\\\lambda q.\x\ (q\ q\ q\ q\ x), D, V,\_]$
규칙	표현
추상화	$\operatorname {build-param-list}[\lambda p.f\ (p\p\f)]\\\\lambda q.\x\ (q\ q\ q\ q\ x), D, V,\_]$
추상화	$\operatorname {build-paramba p.f\(p\p\f)\(\lambda q.\lambda x.x\(q\ q\ x), D, V,\_]$
	$\operatorname {build-param-list}[f\p\f]D,\lambda x.x\ (q\ q\x), D,D[p]$
	$\operatorname {build-param-list}[f\p\f]D,\lambda x.x\ (q\ q\x), D,D[p]$

$\operatorname {build-list} [\lambda q.\lambda x.x\ (q\ q\ x), D,D[p]$
규칙	표현
매개 변수 추가	$\operatorname {build-list}[\lambda q.\lambda x.x\ (q\ q\ x),D,D[p]\land D[p]=L_{1}:{1$
매개 변수 추가	${\displaystyle \operatorname {build-list}[\lambda x.x\ (q\ q\ x),D,L_{2}]\land D[p]=[q,\_,\]::L_{2}}:$
종료 목록	$\operatorname {build-list} [x\ (q\ q\ x),D,L_{3}]\land D[p]=[q,\_,\_]::[x,\_,\_]::L_{3}}$
	$\operatorname {build-param-list}[x\ (q\ q\ x),D,[]\land D[p]=[q,\_,\]::[x,\_,\_]::[]$

$\operatorname {build-param-list} [\lambda p.f\ (p\p\f),D,V,T_{1}]$
규칙	표현
추상화	$\operatorname {build-param-list} [\lambda p.f\ (p\p\f),D,V,T_{1}]$
적용	$\operatorname {build-param-list} [f\ (p\p\f), D, V,T_{1}]$
이름	$\operatorname {build-param-list}[f,D,V,T_{2}]\land \operatorname {build-param-list}[p\ p\ f,D,V,K_{2}]$ $\land T_{2}=[F_{2},S_{2},A_{2}]:[F_{1},S_{1},A_{1}]::\_$ $\land (S_{2}\implies)(\operatorname {equal}[A_{2},p\p\p\f]\land V[F_{2}]=A_{2})\land D[F_{2}]=K_{2}$
이름	$\operatorname {build-param-list} [p\ p\ f,D,V,K_{2}]$ $\land D[f]=[F_{2},S_{2},A_{2}]:[F_{1},S_{1},A_{1}]::\_$ $\land (S_{2}\implies)(\operatorname {equal}[A_{2},p\p\p\f]\land V[F_{2}]=A_{2})\land D[F_{2}]=K_{2}$
이름	$\operatorname {build-param-list}[p\p,D,V,T_{3}]\land \operatorname {build-param-list}[f,D,V,K_{3}]$ ${\displaystyle \land T_{3}=[F_{3},S_{3},A_{3}]::K_{2}}:$ $\land (S_{3}\implies)(\operatorname {equate}[A_{3},f]\land V[F_{3}]=A_{3})\land D[F_{3}]=K_{3}$
적용	$\operatorname {build-param-list} [p\p,D,V,T_{3}]$ ${\displaystyle \land T_{3}=[F_{3},S_{3},A_{3}]::K_{2}}:$ $\land (S_{2}\implies)(\operatorname {equal}[A_{2},p\p\p\f]\land V[F_{2}]=A_{2})\land D[F_{2}]=K_{2}$ $\land (S_{3}\implies)(\operatorname {equate}[A_{3},f]\land V[F_{3}]=A_{3})\land D[F_{3}]=D[f]$
이름	$\operatorname {build-param-list} [p,D,V,T_{4}]\land \operatorname {build-param-list} [p,D,V,K_{4}]$ ${\displaystyle \land T_{4}=[F_{4},S_{4},A_{4}]:[F_{3},S_{3},A_{3}]::K_{2}}:$ $\land (S_{3}\implies)(\operatorname {equate}[A_{3},f]\land V[F_{3}]=A_{3})\land D[F_{3}]=D[f]$ $\land (S_{4}\implies)(\operatorname {equate}[A_{4},p]\land V[F_{4}]=A_{4})\land D[F_{4}]=K_{4}$
	$D[p]=[F_{4},S_{4},A_{4}]:[F_{3},S_{3},A_{3}]::K_{2}}:$ $\land (S_{3}\implies)(\operatorname {equate}[A_{3},f]\land V[F_{3}]=A_{3})\land D[F_{3}]=D[f]$ $\land (S_{4}\implies)(\operatorname {equate}[A_{4},p]\land V[F_{4}]=A_{4})\land D[F_{4}]=D[p]$

$\operatorname {build-param-list}[x\ (q\ q\ x), D, V,\_]$
규칙	표현
추상화	$\operatorname {build-param-list}[\lambda q.\lambda x.x\(q\ q\ q\ x), D, V,\_$
적용	$\operatorname {build-param-list}[x\ (q\ q\ x), D, V, K_{1}]$
이름	$\operatorname {build-param-list} [x,D,V,T_{5}]\land \operatorname {build-param-list}[q\ q\ x,D,V,K_{5}]$ $\land T_{5}=[F_{5},S_{5},A_{5}]::\_$ $\land (S_{5}\implies)(\operatorname {eq}[A_{5},q\q\ x]\land V[F_{5}]=A_{5})\land D[F_{5}]=K_{5}$
이름	$\operatorname {build-param-list} [q\ q\ x,D,V,K_{5}]$ $\displaystyle \land D[x]=[F_{5},S_{5},A_{5}]::\_}$ $\land (S_{5}\implies)(\operatorname {eq}[A_{5},q\q\ x]\land V[F_{5}]=A_{5})\land D[F_{5}]=K_{5}$
이름	$\operatorname {build-param-list}[q\q,D,V,T_{6}]\land \operatorname {build-param-list}[x,D,V,K_{6}]$ $\land T_{6}=[F_{6},S_{6},A_{6}]::K_{5}}$ $\land (S_{6}\implies)(\operatorname {equate}[A_{6},x]\land V[F_{6}]=A_{6})\land D[F_{6}]=K_{6}$
적용	$\operatorname {build-param-list} [q\ q,D,V,T_{6}]$ $\land T_{6}=[F_{6},S_{6},A_{6}]::K_{5}}$ $\land (S_{6}\implies)(\operatorname {equate}[A_{6},x]\land V[F_{6}]=A_{6})\land D[F_{6}]=D[x]$
이름	$\operatorname {build-param-list} [q,D,V,T_{7}]\land \operatorname {build-param-list} [q,D,V,K_{7}]$ $\land T_{7}=[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ $\land (S_{6}\implies)(\operatorname {equate}[A_{6},x]\land V[F_{6}]=A_{6})\land D[F_{6}]=D[x]$ $\land(S_{7}\implies)(\operatorname {eq}[A_{7}q]\land V[F_{7}]=A_{7})\land D[F_{7}]=K_{7}$
이름	$\operatorname {build-param-list} [q,D,V,K_{7}]$ $\land D[q]=[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ $\land (S_{6}\implies)(\operatorname {equate}[A_{6},x]\land V[F_{6}]=A_{6})\land D[F_{6}]=D[x]$ $\land(S_{7}\implies)(\operatorname {eq}[A_{7}q]\land V[F_{7}]=A_{7})\land D[F_{7}]=D[q]$

함께 결과를 수집한 후,

[\displaystyle D[p]=[q,\_,\_]::[x,\_,\_]::L_{3}}}

D[p]=[F_{4},S_{4},A_{4}]:[F_{3},S_{3},A_{3}]::K_{2}}:

\land (S_{3}\implies)(\operatorname {equate}[A_{3},f]\land V[F_{3}]=A_{3})\land D[F_{3}]=D[f]

\land (S_{4}\implies)(\operatorname {equate}[A_{4},p]\land V[F_{4}]=A_{4})\land D[F_{4}]=D[p]

D[q]=[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}

{\displaystyle(S_{6}\implies(\operatorname {equal}) [A_{6},x]\land V[F_{6}]=A_{6})\land D[F_{6}]=D[x]}

(S_{7}\implies (\operatorname {equate} [A_{7},q]\land V[F_{7}]=A_{7}))\land D[F_{7}]=D[q]

From the two definitions for $D[p]$ ;

F_{4}=q

F_{3}=x

so

D[p]=[q,S_{4},A_{4}]::[x,S_{3},A_{3}]::K_{2}

(S_{3}\implies (\operatorname {equate} [A_{3},f]\land V[x]=A_{3}))\land D[x]=D[f]

(S_{4}\implies (\operatorname {equate} [A_{4},p]\land V[q]=A_{4}))\land D[q]=D[p]

Using $D[q]=D[p]$ and

D[p]=[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}

(S_{6}\implies (\operatorname {equate} [A_{6},x]\land V[F_{6}]=A_{6}))\land D[F_{6}]=D[x]

(S_{7}\implies (\operatorname {equate} [A_{7},q]\land V[F_{7}]=A_{7}))\land D[F_{7}]=D[q]

by comparing with the above,

F_{7}=q,F_{6}=x,A_{3}=A_{6},A_{4}=A_{7},S_{3}=S_{6},S_{4}=S_{7}

so,

V[x]=A_{3}

V[q]=A_{4}

in,

S_{3}\implies A_{3}=f

S_{3}\implies (A_{3}=x\lor A_{3}=v[x])

reduces to,

S_{3}\implies A_{3}=f

also,

S_{4}\implies A_{4}=p

S_{4}\implies (A_{4}=q\lor A_{4}=v[q])

reduces to,

S_{4}\implies A_{4}=p

So the parameter list for p is effectively;

D[p]=[q,\_,p]::[x,\_,f]::\_

Drop parameters

Use the information obtained by Build parameter lists to drop actual parameters that are no longer required. drop-params has the parameters,

The lambda expression in which the parameters are to be dropped.
The mapping of variable names to parameter lists (built in Build parameter lists).
The set of variables free in the lambda expression.
The returned parameter list. A parameter used internally in the algorithm.

Abstraction

\operatorname {drop-params} [(\lambda N.S)\ L,D,V,R]\equiv (\lambda N.\operatorname {drop-params} [S,D,F,R])\ \operatorname {drop-formal} [D[N],L,F]

where,

F=FV[(\lambda N.S)\ L]

\operatorname {drop-params} [\lambda N.S,D,V,R]\equiv (\lambda N.\operatorname {drop-params} [S,D,F,R])

where,

F=FV[\lambda N.S]

Variable

\operatorname {drop-params} [N,D,V,D[N]]\equiv N

For a function name or parameter start populating actual parameter list by outputting the parameter list for this name.

Application - An application (function call) is processed to extract

(\operatorname {def} [F]\land \operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-params} [E\ P,D,V,R]\equiv \operatorname {drop-params} [E,D,V,[F,S,A]::R]

\neg (\operatorname {def} [F]\land \operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-params} [E\ P,D,V,R]\equiv \operatorname {drop-params} [E,D,V,[F,S,A]::R]\ \operatorname {drop-params} [P,D,V,\_]

Let - Let expression.

\operatorname {drop-params} [\operatorname {let} V:E\operatorname {in} L]\equiv \operatorname {let} V:\operatorname {drop-params} [E,D,FV[E],[]]\operatorname {in} \operatorname {drop-params} [L,D,FV[L],[]]

And - For use in "let".

\operatorname {drop-params} [E\land F,D,V,\_]\equiv \operatorname {drop-params} [E,D,V,\_]\land \operatorname {drop-params} [F,D,V,\_]

Drop parameters from applications

$\lambda g.\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n)$
Condition	Expression
	$\operatorname {drop-param} [\lambda g.\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,\{p,q,m\},\_]$
	$\lambda g.\operatorname {drop-param} [\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,\{p,q,m\},\_]$
$\neg (\operatorname {def} [F_{1}]\land ...)$	$\lambda g.\lambda n.\operatorname {drop-param} [n\ (g\ m\ p\ n),D,\{p,q,m\},[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]$
$\neg (\operatorname {def} [F_{2}]\land ...)$	$\lambda g.\lambda n.\operatorname {drop-param} [n\ ,D,\{p,q,m\},[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-param} [(g\ m\ p\ n),D,\{p,q,m\},\_]\ \operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]$
$D[n]=[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]$	$\lambda g.\lambda n.n\ \operatorname {drop-param} [(g\ m\ p\ n),D,\{p,q,m\},\_]\ \operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]$

From the results of building parameter lists;

D[n]=[[\_,\_,(g\ m\ p\ n)],[\_,\_,(g\ q\ p\ n)]]

so,

F_{1}=\_

F_{2}=\_

so,

\operatorname {def} [F_{1}]=\operatorname {false}

\operatorname {def} [F_{2}]=\operatorname {false}

$\operatorname {drop-param} [(g\ m\ p\ n),D,\{p,q,m\},\_]$
Condition	Expanded	Expression
$V=\{p,q,m\}$		$\operatorname {drop-param} [(g\ m\ p\ n),D,V,\_]$
$FV(A_{1})\not \subset \{p,q,m\}$	$n\not \subset \{p,q,m\}$	$\operatorname {drop-params} [g\ m\ p,D,V,[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-params} [n,D,V,\_]$
$\operatorname {def} [F_{2}]\land \operatorname {ask} [S_{2}]\land FV[A_{2}]\subset V$	$\operatorname {def} [y]\land \operatorname {ask} [\_]\land FV[p]\subset \{p,q,m\}$	$\operatorname {drop-params} [g\ m,D,V,[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-params} [n,D,V,\_]$
$\neg \operatorname {ask} [S_{3}]$	$\neg \operatorname {ask} [\operatorname {false} ]$	$\operatorname {drop-params} [g,D,V,[F_{3},S_{3},A_{3}]::[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-params} [m,D,V,\_]\ \operatorname {drop-params} [n,D,V,\_]$
$D[g]=[[x,\operatorname {false} ,\_],[o,\_,p],[y,\_,n]]$ $=[F_{3},S_{3},A_{3}]::[F_{2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]$	$F_{3}=x,S_{3}=\operatorname {false} ,A_{3}=\_$ $F_{2}=o,S_{2}=\_,A_{2}=p$ $F_{1}=y,S_{1}=\_,A_{1}=n$	$g\ m\ n$

$\operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]$
Condition	Expanded	Expression
V = \{p, q, m\}		$\operatorname {drop-param} [(g\ q\ p\ n),D,V,\_]$
$FV(A_{4})\not \subset V$	$n\not \subset \{p,q,m\}$	$\operatorname {drop-params} [g\ q\ p,D,V,[F_{4},S_{4},A_{4}]::\_]\ \operatorname {drop-params} [n,D,V,\_]$
$\operatorname {def} [F_{5}]\land \operatorname {ask} [S_{5}]\land FV[A_{5}]\subset V$	$\operatorname {def} [o]\land \operatorname {ask} [\_]\land p\subset \{p,q,m\})$	$\operatorname {drop-params} [g\ q,D,V,[F_{5},S_{5},A_{5}]::[F_{4},S_{4},A_{4}]::\_]\ \operatorname {drop-params} [n,D,V,\_]$
$\neg \operatorname {ask} [S-6]$	$\neg \operatorname {ask} [\operatorname {false} ]$	$\operatorname {drop-params} [g,D,V,[F_{6},S_{6},A_{6}]::[F_{5},S_{5},A_{5}]::[F_{4},S_{4},A_{4}]::\_]\ \operatorname {drop-params} [m,D,V,\_]\ \operatorname {drop-params} [n,D,V,\_]$
$D[g]=[[x,\operatorname {false} ,\_],[o,\_,p],[y,\_,n]]$ $=[F_{6},S_{6},A_{6}]::[F_{5},S_{5},A_{5}]::[F_{4},S_{4},A_{4}]::\_]$	$F_{6}=x,S_{6}=\operatorname {false} ,A_{6}=\_$ $F_{5}=o,S_{5}=\_,A_{5}=p$ $F_{4}=y,S_{4}=\_,A_{4}=n$	$g\ q\ n$

Drop formal parameters

drop-formal removes formal parameters, based on the contents of the drop lists. Its parameters are,

The drop list,
The function definition (lambda abstraction).
The free variables from the function definition.

drop-formal is defined as,

$(\operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-formal} [[F,S,A]::Z,\lambda F.Y,V]\equiv \operatorname {drop-formal} [[F,S,A]::Z,Y[F:=A],L]$
$\neg (\operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-formal} [[F,S,A]::Z,\lambda F.Y,V]\equiv \lambda F.\operatorname {drop-formal} [[F,S,A]::Z,Y,V]$
$\operatorname {drop-formal} [Z,Y,V]\equiv Y$

Which can be explained as,

If all the actual parameters have the same value, and all the free variables of that value are available for definition of the function then drop the parameter, and replace the old parameter with its value.
else do not drop the parameter.
else return the body of the function.

Condition	Expression
$\operatorname {false}$	$\operatorname {drop-formal} [D,\lambda x.\lambda o.\lambda y.o\ x\ y,F]$
$\operatorname {true} \land \{p\}\subset F$	$\lambda x.\operatorname {drop-formal} [D,\lambda o.\lambda y.o\ x\ y,F]$
$\neg (\operatorname {true} \land \{n\}\subset F$ )	$\lambda x.\operatorname {drop-formal} [D,(\lambda y.o\ x\ y)[o:=p],F]$
	$\lambda x.\lambda y.\operatorname {drop-formal} [D,p\ x\ y,F]$
	$\lambda x.\lambda y.p\ x\ y$

Example

Starting with the function definition of the Y-combinator,

\operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p\

Transformation	Expression
	$\operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p$
abstract * 4	$\operatorname {let} p=\lambda f.\lambda x.f\ (x\ x)\land q=\lambda p.\lambda f.(p\ f)\ (p\ f)\operatorname {in} q\ p$
lambda-abstract-tran	$(\lambda q.(\lambda p.q\ p)\ (\lambda f.\lambda x.f\ (x\ x)))\ (\lambda p.\lambda f.(p\ f)\ (p\ f))$
sink-tran	$(\lambda p.\lambda f.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))$
sink-tran	$\lambda f.(\lambda p.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))$
drop-param	$\lambda f.(\lambda p.p\ p)\ (\lambda x.f\ (x\ x))$
beta-redex	$\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\$

Which gives back the Y combinator,

\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))

References

^ Johnsson, Thomas (1985). "Lambda Lifting: Transforming Programs to Recursive Equations". In Jouannaud, J.P. (ed.). Functional Programming Languages and Computer Architecture. FPCA 1985. Lecture Notes in Computer Science. Vol. 201. Springer. CiteSeerX 10.1.1.48.4346. doi:10.1007/3-540-15975-4_37. ISBN 3-540-15975-4.
^ Morazán, Marco T.; Schultz, Ulrik P. (2008), "Optimal Lambda Lifting in Quadratic Time", Implementation and Application of Functional Languages — Revised Selected Papers, pp. 37–56, doi:10.1007/978-3-540-85373-2_3, ISBN 978-3-540-85372-5
^ Danvy, O.; Schultz, U. P. (1997). "Lambda-dropping". ACM SIGPLAN Notices. 32 (12): 90. doi:10.1145/258994.259007.
^ Danvy, Olivier; Schultz, Ulrik P. (October 2000). "Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure" (PDF). Theoretical Computer Science. 248 (1–2): 243–287. CiteSeerX 10.1.1.16.3943. doi:10.1016/S0304-3975(00)00054-2. BRICS-RS-99-27.

External links

Explanation on Stack Overflow, with a JavaScript example
Slonneger, Ken; Kurtz, Barry. "5. Some discussion of let expressions" (PDF). Programming Language Foundations. University of Iowa.

[1] Johnsson, Thomas (1985). "Lambda Lifting: Transforming Programs to Recursive Equations". In Jouannaud, J.P. (ed.). Functional Programming Languages and Computer Architecture. FPCA 1985. Lecture Notes in Computer Science. Vol. 201. Springer. CiteSeerX 10.1.1.48.4346. doi:10.1007/3-540-15975-4_37. ISBN 3-540-15975-4.

[Optimal_Lambda_Lifting_in_Quadratic_Time-2] Morazán, Marco T.; Schultz, Ulrik P. (2008), "Optimal Lambda Lifting in Quadratic Time", Implementation and Application of Functional Languages — Revised Selected Papers, pp. 37–56, doi:10.1007/978-3-540-85373-2_3, ISBN 978-3-540-85372-5

[3] Danvy, O.; Schultz, U. P. (1997). "Lambda-dropping". ACM SIGPLAN Notices. 32 (12): 90. doi:10.1145/258994.259007.

[4] Danvy, Olivier; Schultz, Ulrik P. (October 2000). "Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure" (PDF). Theoretical Computer Science. 248 (1–2): 243–287. CiteSeerX 10.1.1.16.3943. doi:10.1016/S0304-3975(00)00054-2. BRICS-RS-99-27.

[1]

[2]

[3]

[4]

Search

람다 리프팅

네임스페이스

더

목차

알고리즘.

예

람다 리프팅 대 폐쇄

표현과 람다 미적분학을 그대로 두자.

람다 미적분에서의 람다 리프팅

람다 리프트

익명 리프트

통화 구성

명명된 리프트

람다-리프트 변환

리프팅에 사용할 표현식

리프팅 전용 익명 기능 선택

리프팅을 위해 명명된 기능 및 익명 기능 선택

예

실행

람다 미적분에서 람다 강하

람다 드롭

람다 드롭 변환

추상화 싱킹

예

매개 변수 삭제

빌드 매개 변수 목록

예

Drop parameters

Drop formal parameters

Example

See also

References

External links