간단히 입력된 람다 미적분

$\lambda ^{\to }$ 람다 미적분 $\lambda ^{\to }$ ( → ${\$ 형식 이론의 $\lambda ^{\to }$ 한 형태인 람다 미적분 $([→[\displaysty \to$ }})은 함수형태를 구축하는 형식 생성자(→[\displaystystytype \to $\to$ 만 있는 형식 해석이다. 그것은 형식화된 람다 미적분학의 표준적이고 간단한 예다. 단순 타이핑된 람다 미적분은 원래 알론조교회가 1940년 미타입 람다 미적분의 역설적인 사용을 피하기 위한 시도로 도입되었으며, 바람직하고 흥미로운 특성을 많이 보여준다.

단순형(simple type)이라는 용어는 단순히 입력된 람다 미적분(예: 제품, 합금 또는 자연수(System T) 또는 심지어 전체 재귀(PCF와 같은)의 확장을 가리키는 데에도 사용된다. 이와는 대조적으로, 다형성형(시스템 F와 같은)이나 종속형(논리적 프레임워크와 같은)을 도입하는 시스템은 단순히 타이핑된 것으로 간주되지 않는다. 완전한 재귀성을 제외한 전자는 그러한 구조의 교회 인코딩은 오직 $\to$ → $\to$ 과 $\to$ 적절한 유형 변수만을 사용하여 할 수 있지만, 다형성과 의존성은 할 수 없기 때문에 여전히 단순하다고 간주된다.

구문

이 기사에서는 $\sigma$ $\sigma$ 및 $\sigma$ $\tau$ $\tau$ 을(를) 사용하여 $\tau$ 유형을 넘나드는 범위를 지정하십시오. Informally, the function type $\sigma \to \tau$ refers to the type of functions that, given an input of type $\sigma$ , produce an output of type $\tau$ . By convention, $\to$ associates to the right: we read ${\displaystyle \sigma$ $\to \to \rho }$ 을 $\sigma \to \tau \to \rho$ (를 $\sigma \to (\tau \to \rho )$ $\$ → ( $\sigma \to (\tau \to \rho )$ → $\sigma \to (\tau \to \rho )$ ) {\ $displaystyle \to \to \rho$ $\sigma \to (\tau \to \rho )$

유형을 정의하기 위해 $먼저$ B $B$ 기본 유형 집합을 수정하십시오 $B$ 이를 원자형 또는 유형 상수라고도 한다. 이렇게 고정하면, 타입의 구문은 다음과 같다.

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

:

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

→

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

T w

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

e

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

\tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

B

{\displaystyle \tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B

.

For example, $B=\{a,b\}$ , generates an infinite set of types starting with $a,b,$ $a\to a,$ $a\to b,b\to b,$ $b\to a,$ $a\to (a\to a),\ldots ,$ $(b\to a)\to (a\to b),\ldots$ ${\displaystyle (b\to a)\to (a\to$

우리는 또한 기본 유형에 대한 용어 상수 집합을 고정한다. 예를 들어, 기본 유형을 가정해 보면 nat, 그리고 상수라는 용어는 자연수가 될 수 있다. 원래의 발표에서 Church는 "제안 유형"의 $o$ 경우 $\iota$ ${\displaystyle o},$ "개인의 유형"의 $\iota$ 경우 { $\iota$ 의 두 가지 기본 유형만 사용했다. $o$ $o$ 형식에는 용어 상수가 없는 $o$ 반면 $\iota$ $\iota$ 형식에는 하나의 용어 상수가 있다 $\iota$ . 대개 하나의 기본 유형(일반적으로 $o$ ${\displaystyle o$ 만 있는 미적분학을 고려하는 경우가 많다.

단순 타이핑된 람다 미적분학의 구문은 본질적으로 람다 미적분 그 자체의 구문이다. $x{\mathbin {:}}\tau$ $x$ ${\$ $displaystyle$ x ${\mathbin {:}\$ $displaystyle x}$ 이 $x$ (가) $\tau$ $\tau$ 유형임을 나타내기 위해 $x{\mathbin {:}}\tau$ x : $x{\mathbin {:}}\tau$ ${\$ displaystystyle \ $tau }$ 을 쓴다 $\tau$ BNF에서 구문은 다음과 같다.

e::=x\mid \da x{\mathbin {:}\\tau .e\mid e\,e\mid c

$c$ 서 c $c$ 은 $c$ (는) 용어 상수다.

즉, 가변 참조, 추상화, 적용 및 상수. $추상화$ 바인딩 $x$ ${\displaystyle$ x} 안에 있으면 변수 참조 x {\displaystyle x $}$ 이 $($ 가) 바인딩되며 $x$ 바인딩되지 않은 변수가 없으면 항이 닫힌다 $x$

이를 미유형 람다 미적분학의 구문과 비교해 보십시오.

\displaystyle e::=x\mid \da x.e\mid e\,e}

우리는 타이핑된 람다 미적분학에서 모든 함수(추상)가 인수의 유형을 지정해야 한다는 것을 안다.

타이핑 규칙

주어진 유형의 잘 타이핑된 람다 항 집합을 정의하기 위해 항과 유형 간의 타이핑 관계를 정의한다. 먼저, 타이핑 가정의 집합인 $\Gamma ,\Delta ,\dots$ , $\Gamma ,\Delta ,\dots$ , … $\Gamma ,\Delta ,\dots$ 을 $\Gamma ,\Delta ,\dots$ 를) 타이핑 컨텍스트나 타이핑 환경을 소개한다. 타이핑 가정에는 $x{\mathbin {:}}\sigma$ 가 있다: $x{\mathbin {:}}\sigma$ $\sigma$ ${\displaystyle$ x ${\mathbin {:}\sigma$ }, 즉 $x{\mathbin {:}}\sigma$ x ${\$ displaystyle x}이 $(가)$ $\sigma$ $x$ {\ $displaystyle \sigma$

The typing relation $\Gamma \vdash e{\mathbin {:}}\sigma$ indicates that $e$ is a term of type $\sigma$ in context $\Gamma$ . In this case $e$ is said to be well-typed (having type $\sigma$ )타이핑 관계의 예를 타이핑 판정이라고 한다. 타이핑 판단의 타당성은 타이핑 규칙을 사용하여 구성된 타이핑 파생(라인 위의 전제에서는 라인 아래의 결론을 도출할 수 있음)을 제공함으로써 나타난다. 단순 형식 람다 미적분학에서는 다음과 같은 규칙을 사용한다.

{\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x{\mathbin {:}}\sigma }}

:

{\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x{\mathbin {:}}\sigma }}

{\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x{\mathbin {:}}\sigma }}

∈

{\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x{\mathbin {:}}\sigma }}

x

{\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x{\mathbin {:}}\sigma }}

x :

{\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x{\mathbin {:}}\sigma }}

{\

x

{}}}}\mathbin{:}}}}(

1)

{\

T}}}(

2)

{\displaystyle {\frac {\Gamma ,x{\mathbin {:}}\sigma \vdash e{\mathbin {:}}\tau }{\Gamma \vdash (\lambda x{\mathbin {:}}\sigma .

~e){\mathbin{:}}(\mathma \to \tau )}}(

3)

{\frac {\Gamma \vdash e_{1}{\mathbin {:}}\sigma \to \tau \quad \Gamma \vdash e_{2}{\mathbin {:}}\sigma }{\Gamma \vdash e_{1}~e_{2}{\mathbin {:}}\tau }}

(4)

말로 하자면

컨텍스트에 $x$ $\sigma$ ${\displaystyle$ $\sigma }$ 유형이 $\sigma$ ${\displaystyle \$ sigma }인 $x$ $경우$ x {\ $displaystyle$ x}이(가) type $x$ $\sigma$ 인 것으로 알고 있다 $\sigma$
항 상수는 적절한 기본 유형을 가지고 있다.
유형 $\sigma$ 이 $x$ (가) 있는 $x$ ${\$ $displaystyle$ $\sigma$ $\lambda x{\mathbin {:}}\sigma .~e$ $}$ 이 $($ 가 $\sigma$ $\tau$ 특정 컨텍스트에서 $e$ $x$ , $x$ $\lambda x{\mathbin {:}}\sigma .~e$ $\lambda x{\mathbin {:}}\sigma .~e$ : $\lambda x{\mathbin {:}}\sigma .~e$ e ${\displaystystyle \lambda$ x ${}}}}}\mathbin$ . $~e}$ 은 $\lambda x{\mathbin {:}}\sigma .~e$ (는) $\sigma \to \tau$ $\sigma \to \tau$ → $display$ {\ $displaystyle$ \ $\ma \to$ \tau $\sigma \to \tau$
If, in a certain context, $e_{1}$ has type $\sigma \to \tau$ , and $e_{2}$ has type $\sigma$ , then $e_{1}~e_{2}$ has type $\tau$ .

닫힌 용어, 즉 빈 문맥에서 타이핑할 수 있는 용어의 예는 다음과 같다.

모든 유형 $\tau$ 에 대해 $\tau$ $\lambda x{\mathbin {:}}\tau .x{\mathbin {:}}\tau \to \tau$ x $\lambda x{\mathbin {:}}\tau .x{\mathbin {:}}\tau \to \tau$ : $\lambda x{\mathbin {:}}\tau .x{\mathbin {:}}\tau \to \tau$ : $\lambda x{\mathbin {:}}\tau .x{\mathbin {:}}\tau \to \tau$ → $\lambda x{\mathbin {:}}\tau .x{\mathbin {:}}\tau \to \tau$ ${\displaystyle \lambda$ x ${:}\mathbin {:}\mathbin {:}\tau$ \to $\to }($ 식별 함수/I-combinator),
For types $\sigma ,\tau$ , a term $\lambda x{\mathbin {:}}\sigma .\lambda y{\mathbin {:}}\tau .x{\mathbin {:}}\sigma \to \tau \to \sigma$ (the K-combinator), and
For types $\tau ,\tau ',\tau ''$ , a term ${\displaystyle \lambda x{\mathbin {:}}\tau \to \tau '\to \tau ''.$ $\lambda y{\mathbin {:}\tau \tau '.$ $\lambda z{:}\mathbin {:}\tau .xz(yz):(\tau \to \to \tau')\to (\tau \to$ \tau $')\to \to \$ to \ $tau'}($ S 콤비네이터).

이것들은 결합 논리의 기본 결합자의 활자화된 람다 미적분 표현이다.

Each type $\tau$ is assigned an order, a number $o(\tau )$ . For base types, $o(T)=0$ ; for function types, $o(\sigma \to \tau )={\mbox{max}}(o(\sigma )+1,o(\tau ))$ . 즉, 활자의 순서는 가장 좌뇌가 많은 화살표의 깊이를 측정한다. 따라서 다음과 같다.

o(\iota \to \iota \to \iota )=1

o(\iota \to \iota )\to \iota )=2

의미론

내적 해석 대 외적 해석

대체로 간단히 타이핑된 람다 미적분학에 의미를 부여하는 방법에는 두 가지가 있는데, 보다 일반적으로 타이핑된 언어, 때로는 내적인 언어 대 외적인 언어, 또는 교회식 언어 대 교회식 언어라고 한다. 카레 스타일.^[1] 내적/교회 스타일의 의미론에서는 올바른 형식의 용어에 의미를 부여할 뿐, 더 정확히 말하면 타이핑 파생어에 의미를 직접 할당한다. 이는 형식 주석에만 따라 다른 용어들이 그럼에도 불구하고 다른 의미를 부여받을 수 있다는 효과를 가지고 있다. 예를 들어 ID 용어 $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ : $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ n $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ ${\displaystyle \lambda$ x ${\mathbin {:}{{\mathtt {int}}.$ 정수 및 $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ ID 용어 $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ x에 대한 $~x$ $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ . x ${\displaystyle \lambda x{\mathbin {:}{\mathtt {bool}}.$ 술집에 있는 $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ ~ $x}$ 은(는) 다른 의미일 수 있다. (일반적으로 의도된 해석은 정수의 ID 함수와 부울 값의 ID 함수를 의미한다.) 이와는 대조적으로, 외음/커리 스타일의 의미론들은 형식에 구애받지 않는 언어로 해석될 수 있기 때문에 타이핑에 관계 없이 용어에 의미를 부여한다. 이 보기에서 $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ : $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ . $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ ${\displaystyle \lambda$ x ${\mathbin {:}{{\mathtt {int}}.$ $~x}$ 및 $\lambda x{\mathbin {:}}{\mathtt {int}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ x : $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ . ${\displaystyle$ \ \ $da$ x ${\mathbin {:}{\mathtt {bool}}.$ $~x}$ 은 $\lambda x{\mathbin {:}}{\mathtt {bool}}.~x$ (는) 동일한 의미(즉, λ $\lambda x.~x$ . $\lambda x.~x$ ${\displaystyle$ \ \ $da x.~x}$ 과( $\lambda x.~x$ 와) 동일함).

내적 의미론과 외적 의미론의 구별은 때때로 람다 추상화에 대한 주석의 유무와 관련이 있지만, 엄밀히 말하면 이 용법은 부정확하다. 문맥(즉, 유형 추론을 통해)에서 유형을 추론할 수 있을 때 불통된 용어에 대해 교회식 의미를 부여할 수 있기 때문에 유형(즉, 유형 삭제를 통해)을 무시하는 것만으로 주석된 용어에 커리식 의미론을 정의할 수 있다. 본질적 접근법과 외적 접근법의 본질적 차이는 단지 타이핑 규칙을 언어를 정의하는 것으로 보는지 아니면 보다 원시적인 기초 언어의 속성을 검증하는 형식주의로 보는지에 있다. 아래에서 논의되는 다른 의미 해석의 대부분은 Church 또는 Curry 관점을 통해 볼 수 있다.

등가이론

단순 타이핑된 람다 미적분학은 β--등가성의 등가 이론을 가지고 있지만, 형식 제한에 따른다. 베타 감소 방정식

{\displaystyle(\data x{\mathbin {:}\mathbin {:}\mathma .~t)\,u=_{\message }t[x:==u]}

holds in context $\Gamma$ whenever $\Gamma ,x{\mathbin {:}}\sigma \vdash t{\mathbin {:}}\tau$ and $\Gamma \vdash u{\mathbin {:}}\sigma$ , while the equation for eta reduction

\data x{\mathbin {:}\}\mathma .~t\,x=_{\eta }t

γ $\Gamma \vdash t\!:\sigma \to \tau$ $\Gamma \vdash t\!:\sigma \to \tau$ : $\Gamma \vdash t\!:\sigma \to \tau$ → $\Gamma \vdash t\!:\sigma \to \tau$ ${\displaystyle \Gamma \vdash t\!$ $:\displaystyle$ t $}$ 에서 $\Gamma \vdash t\!:\sigma \to \tau$ $\Gamma \vdash t\!:\sigma \to \tau$ $\$ $to$ \ $to$ \ $tau$ } 및 $x$ $x$ 이 $($ 가) 무료로 표시되지 않음 $x$ $t$

운영 의미론

마찬가지로 단순 타이핑된 람다 미적분의 운영 의미도 이름별, 호별 통화 또는 기타 평가 전략을 사용하여 미타입 람다 미적분학에 대해 수정할 수 있다. 모든 타이핑된 언어의 경우, 형식 안전은 이러한 모든 평가 전략의 기본 속성이다. 또한 아래에 기술된 강력한 표준화 특성은 어떤 평가 전략도 단순히 입력된 모든 조건에 의해 종료된다는 것을 의미한다.

범주형 의미론

단순 타이핑된 람다 미적분(β $\beta \eta$ { $\beta \eta$ - 동등성 $\beta \eta$ )은 람베크가 처음 관찰한 바와 같이 카르테시안 폐쇄 범주(CCC)의 내부 언어다. 어떤 특정한 CCC를 감안한다면, 해당 람다 미적분학의 기본 타입은 물체일 뿐이고, 용어는 형태론이다. 반대로, 간단히 타이핑된 람다 미적분학은 CCC에게 그 대상이 유형이고, 형태론은 용어의 동등성 등급이다.

서신을 명확히 하기 위해 일반적으로 위에 데카르트 제품의 형식 생성자를 추가한다. 데카르트 제품의 범주를 보존하기 위해 페어링, 투영 및 단위 용어에 대한 유형 규칙을 추가한다. Given two terms $s{\mathbin {:}}\sigma$ and $t{\mathbin {:}}\tau$ , the term $(s,t)$ has type $\sigma \times \tau$ . Likewise, if one has a term ${\displaystyle u{\mathbin {:}}\tau _{1}\times$ $\tau _{2}}$ , then there are terms $\pi _{1}(u){\mathbin {:}}\tau _{1}$ and $\pi _{2}(u){\mathbin {:}}\tau _{2}$ where the $\pi _{i}$ correspond to the projections of the Cartesian product. 1타입의 단위 용어는 ( $()$ ) ${\displaystyle()}$ 로 쓰고 $()$ 'nil'로 발음하는 것이 최종 목적어다. 평정론도 마찬가지로 확장되어 있어, 한 사람이 한 가지 생각을 가지고 있다.

\pi _{1}(s{\mathbin {:}\mathbin {:}\tau )=s{\mathbin {:}\mathma

\pi _{2}(s{\mathbin {:}\mathma ,t{\mathbin {:}\tau )=t{\mathbin {:}

{\displaystyle(\pi _{1}(u{\mathbin {:}\mathma \tau }),\pi _{2}(u{\mathbin {:}\mathma \tau )=u{\mathbin {:}\matmau \tau}}}

t{\mathbin {:}1=()

이 마지막은 "t가 타입 1을 가지고 있다면, 그러면 nil로 감소한다"로 읽힌다.

그런 다음 유형을 개체로 취함으로써 위의 항목을 범주로 바꿀 수 있다. The morphisms $\sigma \to \tau$ are equivalence classes of pairs $(x{\mathbin {:}}\sigma ,t{\mathbin {:}}\tau )$ where x is a variable (of type $\sigma$ ) and t is a term (of type $\tau$ ), having no free variables in it, ex(선택적으로) x에 대한 cept. 평소와 같이 currering과 application을 통해 폐쇄를 얻는다.

좀 더 정확히 말하면, 카르트 폐쇄 범주의 범주와 단순 형식 람다 이론의 범주 사이에는 functors가 존재한다.

선형형 시스템을 사용하여 닫힌 대칭 단면형 범주로 이 사례를 확장하는 것이 일반적이다. 그 이유는 CCC가 일반적으로 집합 범주로 간주되는 폐쇄 대칭 단면체 범주의 특별한 경우이기 때문이다. 이는 세트 이론의 기초를 다지는 데는 괜찮지만, 일반적인 토포들이 많을수록 우수한 기초를 제공하는 것으로 보인다.

증명-이론적 의미론

단순하게 타이핑된 람다 미적분은 명제적 직관논리의 관계적 파편, 즉 Curry-Howard 이소모르피즘을 통한 최소논리와 밀접하게 관련되어 있다: 용어는 자연적 추론에서의 증거에 정확히 대응하며, 거주형태는 정확히 최소논리의 토폴로지인 것이다.

대체 구문

위에서 주어진 프레젠테이션만이 단순히 입력된 람다 미적분의 구문을 정의하는 유일한 방법이 아니다. 한 가지 대안은 (구문이 형식화되지 않은 람다 미적분학과 동일하도록) 형식 주석을 완전히 제거하는 동시에 용어들이 힌들리-밀너 형식 추론을 통해 잘 형식화되도록 하는 것이다. 추론 알고리즘은 종료, 소리 및 완전하다. 항이 타이핑될 때마다 알고리즘은 그 유형을 계산한다. More precisely, it computes the term's principal type, since often an unannotated term (such as $\lambda x.~x$ ) may have more than one type ( ${\mathtt {int}}\to {\mathtt {int}}$ , ${\mathtt {bool}}\to {\mathtt {bool}}$ , etc., $\alpha \to \alpha$ α → $\alpha \to \alpha$ ${\displaystyle \to \to$ \to \ $to$ \}의 모든 인스턴스. $\alpha \to \alpha$

단순 타이핑된 람다 미적분학의 또 다른 대안적 프레젠테이션은 양방향 유형 확인에 기초하는데, 힌들리-밀너 추론보다 더 많은 유형의 주석을 필요로 하지만 설명하기가 쉽다. $\Gamma \vdash e\Rightarrow \tau$ 시스템은 체크와 $합성$ 을 모두 나타내는 두 가지 판단으로 나뉘는데 $,$ $written$ $\Gamma \vdash e\Rightarrow \tau$ $\Gamma \vdash e\Leftarrow \tau$ $\Gamma \vdash e\Leftarrow \tau$ τ e { $\Gamma \vdash e\Leftarrow \tau$ { \ \ $\$ \ \ \ \ \ \ $\$ \ \ \ \ \ $\Gamma \vdash e\Rightarrow \tau$ \ \ \ $\$ { { { $\Gamma \vdash e\Rightarrow \tau$ $\Gamma \vdash e\Rightarrow \tau$ display display $display display$ $display$ display $\Gamma \vdash e\Leftarrow \tau$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Operationally, the three components $\Gamma$ , $e$ , and $\tau$ are all inputs to the checking judgment $\Gamma \vdash e\Leftarrow \tau$ , whereas the synthesis judgment $\Gamma \vdash e\Rightarrow \tau$ only takes $\Gamma$ $\Gamma$ 및 $\Gamma$ $e$ $e$ 을(를) 입력으로 $e$ 생성하여 $\tau$ $\tau$ 유형을 출력으로 $\tau$ 생성한다. 이러한 판단은 다음 규칙을 통해 도출된다.

${\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}$ : ${\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}$ ${\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}$ ${\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}$ x ${\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}$ x ${\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}$ x ${\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}$ ${\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}$ { { { ${$ { { { { $\prac$ {x{\ $mathbin {:}\}\Sigma \in$ \감마 $\vdash$ x $\Rightarrow \sigma }}}}}[$ 1]	${\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c\Rightarrow T}}$ 는 ${\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c\Rightarrow T}}$ ${\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c\Rightarrow T}}$ ${\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c\Rightarrow T}}$ ${\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c\Rightarrow T}}$ ${\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c\Rightarrow T}}$ ${\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c\Rightarrow T}}$ 의 $상수임 {\$ T $}}[$ 2]
${\frac {\Gamma ,x{\mathbin {:}}\sigma \vdash e\Leftarrow \tau }{\Gamma \vdash \lambda x.~e\Leftarrow \sigma \to \tau }}$ [3]	${\frac {\Gamma \vdash e_{1}\Rightarrow \sigma \to \tau \quad \Gamma \vdash e_{2}\Leftarrow \sigma }{\Gamma \vdash e_{1}~e_{2}\Rightarrow \tau }}$ [4]
${\frac {\Gamma \vdash e\Rightarrow \tau }{\Gamma \vdash e\Leftarrow \tau }}$ e ${\frac {\Gamma \vdash e\Rightarrow \tau }{\Gamma \vdash e\Leftarrow \tau }}$ ${\frac {\Gamma \vdash e\Rightarrow \tau }{\Gamma \vdash e\Leftarrow \tau }}$ e ${\frac {\Gamma \vdash e\Rightarrow \tau }{\Gamma \vdash e\Leftarrow \tau }}$ e e ${\frac {\Gamma \vdash e\Rightarrow \tau }{\Gamma \vdash e\Leftarrow \tau }}$ ${\frac {\Gamma \vdash e\Rightarrow \tau }{\Gamma \vdash e\Leftarrow \tau }}$ { { { { ${$ { { \ $displaystyle {\\Gamma \vdash$ e $\Rightarrow \tau }{\\Gamma \vdash e\$ Le\ $Leftarrow }}}[$ 5]	${\frac {\Gamma \vdash e\Leftarrow \tau }{\Gamma \vdash (e{\mathbin {:}}\tau )\Rightarrow \tau }}$ e e ${\frac {\Gamma \vdash e\Leftarrow \tau }{\Gamma \vdash (e{\mathbin {:}}\tau )\Rightarrow \tau }}$ ${\frac {\Gamma \vdash e\Leftarrow \tau }{\Gamma \vdash (e{\mathbin {:}}\tau )\Rightarrow \tau }}$ ${\frac {\Gamma \vdash e\Leftarrow \tau }{\Gamma \vdash (e{\mathbin {:}}\tau )\Rightarrow \tau }}$ { $⇒$ { { { { { { { ${\frac {\Gamma \vdash e\Leftarrow \tau }{\Gamma \vdash (e{\mathbin {:}}\tau )\Rightarrow \tau }}$ { { { { { { { { { { { \\ $prac \\vvash \vdash$ e $\Leftarrow$ \ \ \} \ $\}{\\\\\\\$ \ $gam \gam$ \ $gam$ \v \gam \v \gam \v}}\ $gam$ \gam ${\frac {\Gamma \vdash e\Leftarrow \tau }{\Gamma \vdash (e{\mathbin {:}}\tau )\Rightarrow \tau }}$ \gam \gam \gam \gam \gam $\$

점검 또는 종합 판단의 신중한 선택을 제외하고, 규칙 [1]–[4]이 위의 규칙 (1)–(4)과 거의 동일하다는 것을 준수한다. 이러한 선택은 다음과 같이 설명할 수 있다.

$x{\mathbin {:}}\sigma$ : ${\displaystyle$ x ${\mathbin {:}\sigma }}$ 이 $x{\mathbin {:}}\sigma$ (가) 컨텍스트에 있으면 $x$ $x$ 에 $\sigma$ 대한 $\sigma$ 타입 $\sigma$ 을(를) 합성할 수 있다 $x$
용어 상수의 유형은 고정되어 있으며 합성할 수 있다.
$\lambda x.~e$ $\lambda x.~e$ . e $\lambda x.~e$ 에 $\lambda x.~e$ $\sigma \to \tau$ $\sigma \to \tau$ → $\sigma \to \tau$ ${\displaystyle \sigma \$ $tau$ $}$ 유형이 있는지 확인하려면 $x{\mathbin {:}}\sigma$ : $x{\mathbin {:}}\sigma$ ${\displaystyle$ x ${:}\mathbin {:}\sigma$ $}$ 로 컨텍스트를 확장하고 $x{\mathbin {:}}\sigma$ ${\displaysty$ }에 \displaystytype ${\displaystytype$ \down.
If $e_{1}$ synthesizes type $\sigma \to \tau$ (in some context), and $e_{2}$ checks against type $\sigma$ (in the same context), then $e_{1}~e_{2}$ synthesizes type $\tau$ .

합성에 대한 규칙은 위에서 아래로 읽는 반면, 점검에 대한 규칙은 아래에서 위로 읽는 것을 관찰한다. 특히 바운드 변수의 유형은 함수를 확인하는 유형에서 추론할 수 있으므로 규칙 [3]에서 람다 추상화에 대한 주석을 사용할 필요가 없다는 점에 유의하십시오. 마지막으로 규칙 [5]와 [6]을 다음과 같이 설명한다.

$e$ $e$ 에 $\tau$ } {\ $displaystyle \tau }$ 유형이 있는지 $e$ 확인하려면 $\tau$ $\tau$ 유형 $\$ {\ $displaystyle \tau$ }을(를) 합성하는 것으로 충분하다 $\tau$
$e$ $e$ 이 $e$ $\tau$ 가) 유형 $\tau$ $\tau$ 을(를) 확인하면 명시적으로 주석이 붙은 용어 $(e{\mathbin {:}}\tau )$ $(e{\mathbin {:}}\tau )$ : $(e{\mathbin {:}}\tau )$ ) $(e{\mathbin {:}}\tau )$ {\ $displaystyle(e{\mathbin {:}\tau$ )이( $) \$ {\ $displaystyty \type$ \}을(합성한다 $\tau$

합성과 확인 사이에 강요하는 이 마지막 두 가지 규칙 때문에, 양방향 시스템에서 잘 다듬어졌지만 고지되지 않은 모든 용어를 확인할 수 있다는 것을 쉽게 알 수 있다, 우리가 "완전한" 타입의 주석을 삽입하는 한 말이다. 그리고 사실 주석은 β-redexes에서만 필요하다.

일반 관측치

표준 의미론을 고려할 때 단순 타이핑된 람다 미적분학은 강하게 정상화되고 있다. 즉, 잘 타이핑된 용어들은 항상 값으로 감소한다. $\lambda$ , { $\lambda$ 추상화 $\lambda$ . This is because recursion is not allowed by the typing rules: it is impossible to find types for fixed-point combinators and the looping term $\Omega =(\lambda x.~x~x)(\lambda x.~x~x)$ . Recursion can be added to the language by either having a special operator ${\$ 표시 $유형$ $(\alpha \to \alpha )\to \alpha$ → ${\mathtt {fix}}_{\alpha }$ $(\alpha \to \alpha )\to \alpha$ )의 ${\mathtt {fix}}_{\alpha }$ 표시 $유형$ {\ $matht$ { $fix$ }_ ${\property$ } → $(\alpha \to \alpha )\to \alpha$ ${\displaystyle(\cHB \to \property \}) 또는$ 일반 $(\alpha \to \alpha )\to \alpha$ 재귀 유형을 추가하거나 둘 다 강한 정규화를 제거한다.

그것은 매우 정상적이기 때문에, 간단히 타이핑된 람다 미적분 프로그램이 중단되는지 아닌지는 확실하다: 사실, 그것은 항상 중단된다. 그러므로 우리는 그 언어가 튜링의 완전한 것이 아니라는 결론을 내릴 수 있다.

중요한 결과

Tait는 1967년에 $\beta$ $\beta$ - 감소가 $\beta$ 강하게 정상화되고 있음을 보여주었다. 코롤러리 $\beta \eta$ $\beta \eta$ $\beta \eta$ - 동등성은 $\beta \eta$ 디커피블이 가능하다. Statman은 1977년에 정상화 문제가 기본적인 재귀성이 아니라는 것을 보여주었는데, 이것은 나중에 메어슨(1992)에 의해 단순화되었다. 문제는 Grzegorczyk 계층 구조 ${\mathcal {E}}^{4}$ E ${\mathcal {E}}^{4}$ ${\$ 에 있는 것으로 알려져 있다.^[2] 1991년 베르거와 쉬치텐베르크에 의해 순수하게 의미론적 정규화 증명(평가에 의한 정규화 참조)이 제시되었다.
$\beta \eta$ $\beta \eta$ $\beta \eta$ - 동등성에 $\beta \eta$ 대한 통일 문제는 이해할 수 없다. Huet은 1973년에 3차 통일은 불해독이라는 것을 보여주었고 이것은 1978년에 백스터에 의해 개선되었고 1981년에 골드파브에 의해 2차 통일은 이미 불해독이라는 것을 보여주었다. 더 높은 순서의 일치(한 용어만 실존 변수를 포함하는 통일)가 디커블이 된다는 증거는 2006년 콜린 스털링에 의해 발표되었고, 2009년에 완전한 증거가 발표되었다.^[3]
자연수를 유형 $(o\to o)\to (o\to o)$ → $(o\to o)\to (o\to o)$ $(o\to o)\to (o\to o)$ → ( $(o\to o)\to (o\to o)$ → $(o\to o)\to (o\to o)$ $(o\to o)\to (o\to o)$ ${\displaystyle (o\to o)\to (o\to o)}($ Church 숫자)로 인코딩할 수 있다. Schwichtenberg는 1976년에 $\lambda ^{\to }$ → ${\$ 에서 $\lambda ^{\to }$ 정확히 확장된 다항식이 교회 숫자를 넘는 함수로 표현될 수 있다는 것을 보여주었다; 이것들은 대략 조건부 연산자에 의해 닫힌 다항식들이다.
$\lambda ^{\to }$ → ${\$ 의 풀모델은 설정기상함수 공간별로 기본형을 세트와 함수형으로 해석하여 $\lambda ^{\to }$ 주어진다. Friedman은 1975년에 기본 유형이 무한 집합으로 해석될 경우 $\beta \eta$ { $\beta \eta$ {\ $displaystyle \beta \eta$ } - 동등성에 $\beta \eta$ 대해 이 해석이 완전하다는 것을 보여주었다. Statman은 1983년에 $\beta \eta$ $\beta \eta$ $\beta \eta$ - 동등성이 $\beta \eta$ 전형적으로 모호한 최대 동등성(즉, 형식 대체(Statman의 전형적인 모호성 정리)임을 보여주었다. 이에 대한 유의점은 유한 모델 속성이 유지된다는 것이다. 즉, 유한 집합은 $\beta \eta$ $\beta \eta$ $\beta \eta \$ - 동등성으로 $\beta \eta$ 식별되지 않는 항을 구별하기에 충분하다.
플롯킨은 람다 항으로 정의할 수 있는 모델의 요소를 특성화하기 위해 1973년에 논리적 관계를 도입했다. 1993년에 융과 티우린은 일반적인 형태의 논리적 관계(다양한 경지를 가진 Kripke 논리적 관계)가 람다 정의 가능성을 정확하게 특징짓는다는 것을 보여주었다. Plotkin과 Statman은 유한 집합에서 생성된 모델의 주어진 요소가 람다 항(Plotkin-Statman 추측)으로 정의 가능한지 여부를 확인할 수 있다고 추측했다. 그 추측이 1993년 로더에 의해 거짓으로 드러났다.

메모들

^ Reynolds, John (1998). Theories of Programming Languages. Cambridge, England: Cambridge University Press.
^ Statman, Richard (July 1979). "The typed λ-calculus is not elementary recursive". Theoretical Computer Science. 9 (1): 73–81. doi:10.1016/0304-3975(79)90007-0. ISSN 0304-3975.
^ Stirling, Colin (22 July 2009). "Decidability of higher-order matching". Logical Methods in Computer Science. 5 (3): 1–52. arXiv:0907.3804. doi:10.2168/LMCS-5(3:2)2009. S2CID 1478837.

참조

A. 교회: JSL 5, 1940의 단순한 유형 이론의 공식화
W.W.Tait: 유한형 I, JSL 32(2), 1967년도의 함수 해석
G.D. 플롯킨: 람다 정의와 논리적 관계, 기술 보고서, 1973
G.P. 휴엣: 제3순서의 논리정보와 통제에 있어서의 통일의 불문율 22(3): 257-267 (1973)
H. 프리드먼: 함수 사이의 평등. 로직콜. '73, 22-37페이지, LNM 453, 1975페이지.
H. Schwichtenberg: 단순 형식의 람다 미적분, 아치에서 정의할 수 있는 함수. Math Logik 17 (1976년) 113-114.
R. Statman: 입력된 람다-미적분은 기본 재귀 FOCS 1977: 90-94
W. D. 골드파브: 제2차 통일문제 TCS(1981년), 제13호, 제225-230호.
R. Statman. $\lambda$ $\lambda$ -정의 $\lambda$ 가능한 함수 및 $\beta \eta$ $\beta \eta$ $\beta \eta$ 변환 $\beta \eta$ . 아치. 수학. 로직, 1983년 23:21–26.
J. 램벡: 데카르트 폐쇄 범주 및 입력된 람다-칼쿨리. 결합기 및 기능 프로그래밍 언어 1985: 136-175
U. Berger, H. Schwichtenberg: 람다-미적분 LICS 1991: 203-211 형식 평가 기능의 역행
H. 메어슨: Statman의 정리를 보여주는 간단한 증거, TCS 103(2):387-394, 1992.
정, A,티린, J:람다 정의성의 새로운 특징, TLCA 1993
R. 로더: 2001년 Church Festschrift에 등장한 불운한 of-definibility의 정의
H. Barendregt, Lambda Calculi with Types, Handa Calculi, Handbook of Logic in Computer Science, 제2권, Oxford University Press, 1993. ISBN 0-19-853761-1
L. 백스터: 제3차 디아디드 통일 문제의 불복성, 정보 및 통제 38(2), 170-178(1978)

외부 링크

Loader, Ralph (February 1998). "Notes on Simply Typed Lambda Calculus".
스탠포드 철학 백과사전의 "교회의 유형론" 항목

[1] Reynolds, John (1998). Theories of Programming Languages. Cambridge, England: Cambridge University Press.

[2] Statman, Richard (July 1979). "The typed λ-calculus is not elementary recursive". Theoretical Computer Science. 9 (1): 73–81. doi:10.1016/0304-3975(79)90007-0. ISSN 0304-3975.

[3] Stirling, Colin (22 July 2009). "Decidability of higher-order matching". Logical Methods in Computer Science. 5 (3): 1–52. arXiv:0907.3804. doi:10.2168/LMCS-5(3:2)2009. S2CID 1478837.

[1]

[2]

[3]

Search