교차로유형규율

수학 논리학에서 교차로 유형 부문은 교차로 유형 생성자${\displaystyle (\cap )}$ ${\displaystyle (\cap )}$을 사용하여$$ 단일 용어에 여러 유형을 할당하는 형식 시스템을 포괄하는 유형 이론의 한 분야다.^[1]In particular, if a term ${\displaystyle M}$ can be assigned both' the type ${\displaystyle \varphi _{1}}$ and the type ${\displaystyle \varphi _{2}}$, then ${\displaystyle M}$ can be assigned the intersection type ${\displaystyle \varphi _{1}\cap \varphi _{2}}$ (and vice versa).따라서 교차로형 생성자는 유한 이질적인 임의의 다형성(parametric polymorism)을 표현하는데 사용될 수 있다(파라메트릭 다형성과는 반대로).For example, the λ-term ${\displaystyle \lambda x.\!(x\;x)}$ can be assigned the type ${\displaystyle ((\alpha \to \beta )\cap \alpha )\to \beta }$ in most intersection type systems, assuming for the term variable ${\displaystyle x}$ both the function type ${\displaystyle \alpha$$\to \property }$ 및$$ 해당하는 인수 $유형{\displaystyle }$α {\$displaystyle \property$ $\}.$

눈에 띄는 교차로형 시스템으로는 코포-데자니형 배정 시스템,^[2] 바렌드레그-코포-데자니형 배정 시스템,^[3] 필수 교차로형 배정 시스템 등이 있다.^[4]가장 눈에 띄는 점은 교차로형 시스템이 β-축소 하의 β-단말기의 정규화 특성과 밀접하게 관련되고(그리고 종종 정확히 특성화) 있다는 점이다.

TypeScript와^[5] Scala와 같은 프로그래밍 언어에서,^[6] 교차로 유형은 임시 다형성을 표현하기 위해 사용된다.

역사

교차로형 규율은 마리오 코포, 마리앙기올라 데자니-첸카글리니, 패트릭 살레, 가렐 포틴저 등이 개척했다.^[2][7][8]근본적인 동기는 λ-미적분학의 의미적 특성(정상화 등)을 유형이론을 이용하여 연구하는 것이었다.^[9]코포와 데자니의 초창기 작업이 λI-미적분학의 강력한 정상화의 유형 이론적 특성화를 확립한 반면, 포틴저는 이 특성화를 λK-미적분학까지 확대했다.^[2][7]또, 살레는 어떤 λ기에도 할당할 수 있는$$ 범용 타입 $\Omega {\displaystyle }$ ${\displaystyle \omega }$의 개념에 기여하여, 빈 교차로에 해당한다.^[8]$\Omega {\displaystyle }$ ${\displaystyle \omega }$ 범용 유형 사용으로 헤드 표준화, 정규화 및 강력한 정규화에 대한 세분화된 분석이 가능하다$$.^[10]Henk Barendregt와 협력하여 교차로형 시스템에 필터 λ 모델을 부여하여 교차로형을 λ-미적분 의미론에 더욱 가깝게 연결하였다.

정규화와의 일치성 때문에 저명한 교차로 유형 시스템(범용 유형 제외)에서의 타이핑은 판독할 수 없다.보완적으로 Pawew Urzyzyn에 의해 저명한 교차로형 시스템에서 발생하는 유형의 이중 문제에 대한 불찰성이 입증되었다.^[11]이후, 이 결과는 2등급 교차로 유형의 거주 지수 공간 완전성과 3등급 교차로 유형의 거주에 대한 불해독성을 보여줌으로써 개선되었다.^[12]주목할 만한 것은 다항식 시간에 주형 거주가 해제된다는 점이다.^[13]

코포-데자니형 할당제

Copo-Dezani 유형 할당 시스템${\displaystyle {}_{\text{CD}}}$) ${\displaystyle(\vdash _{\text{CD})}$은 용어에 대해 여러 유형을 가정할 수 있도록 하여 단순 유형인 λ-미적분을 확장한다.^[2]

용어 언어

(${\displaystyle {}_{}}$ ${\displaystyle {\text{CD}}_{}}$) ${\displaystyle(\vdash _{\text{CD}})$의 용어는 λ-terms(또는 람다 식)로 주어진다$$.

${\displaystyle {\begin{arged}M,N&:=x\mid(\lambda x.\!M)\mid(M\;N)&#{\text{{{}\text{{{}여기서 }x{\text{{ term variable}\\end{arged}}}}$

유형 언어

(${\displaystyle {}_{}}$ ${\displaystyle {\text{CD}}_{}}$) ${\displaystyle(\vdash _{\text{CD}})$의 형식 언어는 다음 문법에 의해 귀납적으로 정의된다$$.

${\displaystyle {\begin{aligned}\varphi &::=\alpha \mid \sigma \to \varphi &&{\text{ where }}\alpha {\text{ ranges over type variables}}\\\sigma &::=\varphi _{1}\cap \cdots \cap \varphi _{n}&&{\text{ where }}n\geq 1\end{aligned}}}$

교차로 유형 생성자( ${\displaystyle }$ ${\displaystyle \cap }$)는 modulo 연관성, 동시성 및 특이성을 취한다.

유형 규칙

유형 규칙$({\displaystyle }$→ ${\displaystyle I}$) ${\displaystyle(\to \!\!)!$${\text{I$${\displaystyle }$(${\displaystyle }$→ ${\displaystyle E}$) ${\displaystyle(\to \!\!)!$${\text{E$ (${\displaystyle \cap }$ ${\displaystyle I}$) ${\displaystyle(\cap {\text${\text$})$$I}}},$및 (${\displaystyle \cap }$ ${\displaystyle E}$) ${\displaystyle(\cap{\text{E}})},$${\displaystyle {}_{}}$ ${\displaystyle {\text{CD}}_{}}$) ${\displaystyle(\vdash _{\text{CD})}$은(는$$) 다음과 같다.

${\displaystyle {\begin{array}{cc}{\dfrac {\Gamma ,x:\sigma \vdash _{\text}{\data.CD}M:\varphi }{\Gamma \vdash _{\text{CD}\lambda x.\!M:\sigma \to \varphi }}}}(\to \!\!)!{\text{I})&#{\dfrac {\Gamma \vdash _{\text}CD}M:\sigma \to \varphi \quad \Gamma \vdash _{\text{CD}}N:\sigma }{\Gamma \vdash _{\text{CD}M\;N:\varphi }}}}(\to \!\!)!{\text{E})\\\\\\dfrac {\\Damma \vdash _{\text{CD}M:\varphi _{1}\quad \dots \quad \quad \Quad \Gamma \vdash _{\text{CD}M:\varphi _{n}{\Gamma \vdash _{\text{CD}M:\varphi _{1}\cap \cdots \cap \varphi _{n}}(\cap {\text})I}})&{\dfrac {(1\leq i\leq n)}{\Gamma ,x:\varphi _{1}\cdots \cap \varphi _{n}\vdash _{\text{\cap{\cdash{\cap}CD}x:\varphi _{i}}(\cap {\text{E})\end{array}}}$

특성.

활자성 및 정규화는 (${\displaystyle {}_{}}$ ${\displaystyle {\text{CD}}_{}}$) ${\displaystyle(\vdash _{\text{CD})$에 다음$$ 속성과 밀접하게 관련되어 있다.^[2]

• 환자 감소:$if{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\text{CD}}_{}}$ ${\displaystyle {}_{}}$: : ${\displaystyle \Gamma \vdash _{\text{$$CD}M$$:\sigma }$과($와{\displaystyle {}_{}}$ M → ${\displaystyle {}_{}}$N {\$displaystyle$ M$\to _${\${\displaystyle {}_{}}$$}N$},$$$then{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}}$ ⊢ CD ${\displaystyle {\text{N}}_{}}$: ${\displaystyle \sigma }$ ${\displaysty \Gamma \vdash _{\text${\text$}$$CD}}N:\sigma$ $\}.$
• 정규화:$if{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\text{CD}}_{}}$ ${\displaystyle {}_{}}$: : ${\displaystyle \Gamma \vdash _{\text{$$CD}}M:\sigma$ $\},$ 그 $다음{\displaystyle }$ M ${\displaystyle M}$에 β-정규형 형식이 있다.
• 강력하게 정규화된 λ-terms의 타이핑 가능성:$$M {\${\displaystyle {}_{}}$ $}$이(가) 강력하게 정규화되고 있는$$ 경우 $cd{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{cd}}$ ${\displaystyle {}_{}}$ ⊢${\displaystyle }$⊢ ⊢ ⊢ \ $\displaystyle \Gamma \vdash _{\text${\text$}$$CD$$}M:\sigma }$ 일부$$some{\$displaystyle \Gamma }$ $및$ } ${\displaystyle \sigma$ $\}$ .
• λI 정규화의 특성화:${\displaystyle }$${\displaystyle {\text{M}}_{}}$ ${\displaystyle M$${\displaystyle \}}$은(는) λI-계산서에 ${\displaystyle {}_{}}$인 형태를 가지고$$ 있으며, 만일 $\gamma {\displaystyle \mathrm{}}$ ⊢ $⊢$ ${\displaystyle \mathrm{CD}}$ M :$display$ {\displaystyle \$Gamma$ \$vdash _${\text${.$$CD$$}M:\sigma }$ 일부$$some{\$displaystyle \Gamma }$ $및$ } ${\displaystyle \sigma$ $\}$ .

If the type language is extended to contain the empty intersection, i.e. ${\displaystyle \sigma =\varphi _{1}\cap \cdots \cap \varphi _{n}{\text{ where }}n=0}$, then ${\displaystyle (\vdash _{\text{CD}})}$ is closed under β-equality and is sound and complete for inference semantics.^[14]

바렌레그트-코포-데자니형 배정 시스템

Barendregt-Copo-Dezani 유형 할당 시스템 (${\displaystyle {}_{}}$ ${\displaystyle {\text{BCD}}_{}}$) ${\displaystyle (\vdash _{\text{B$)$CD}})}$은(는) 다음과 같은 세 가지 측면에서 코포-데자니 유형 할당 시스템을 확장한다$$.^[3]

• ${\displaystyle(\vdash _{\text{B$$$$CD}}}}$은(는) 임의의 λ 기간에 할당할 수 있는 범용 유형 상수$\Omega {\displaystyle }$ {\$displaystyle \omega }($빈 교차로에 있음)를$$ 소개한다.
• ${\displaystyle(\vdash _{\text{B$$$$CD}})}$은(는) 교차 유형 생성자$({\displaystyle (\cap )})$를 화살표 유형 생성자$({\displaystyle }$→$){\displaystyle (\to )}$의 오른쪽에 표시할 수 있도록$$ 허용한다$.$
• ${\displaystyle(\vdash _{\text{B$$$$CD}}}}$은(는) 해당 타이핑 규칙과 함께 유형에 대한 교차로 유형 하위 유형$({\displaystyle(\leq )}$ 부분 순서$$ 소개$$

용어 언어

(${\displaystyle {}_{}}$ ${\displaystyle {\text{BCD}}_{}}$) ${\displaystyle(\vdash _{\text{B$)의 용어$CD}})}$은(는) λ-단어(또는 람다 식)로 제공된다$$.

${\displaystyle {\begin{arged}M,N&:=x\mid(\lambda x.\!M)\mid(M\;N)&#{\text{{{}\text{{{}여기서 }x{\text{{ term variable}\\end{arged}}}}$

유형 언어

(${\displaystyle {}_{}}$ ${\displaystyle {\text{BCD}}_{}}$) ${\displaystyle(\vdash _{\text{B$)의 유형 언어$CD}})}$은(는) 다음 문법에 의해 귀납적으로 정의된다$$.

${\displaystyle {\regated}\basedma,\tau &:=\mid \\mid \\mid \to \to \to \to \mid \cap \tau &>{\texture{}여기서 }\text{}}}}}}}$

교차로 유형 하위 유형

교차로 유형 하위 유형(${\displaystyle \le }$) ${\displaystyle(\leq )}$은 다음 특성을 만족하는 교차로 유형에 대한 최소 사전 순서(반복적 및 전이적 관계)로 정의된다$$.

${\displaystyle{\begin{정렬}&, \sigma\leq \omega,\quad\omega\leq\omega\to \omega,\quad \sigma \cap\tau\leq \sigma,\quad \sigma \cap\tau\leq \tau ,\\&,(\sigma \to \tau_{1})\cap(\sigma \to \tau_{2})\leq \sigma \to\tau _{1}\cap \tau _{2},\\&,{\text{만약}}\sigma\leq \tau _{1}{\text{과}}\sigma\leq \tau _{2}{\text{,}}.\sigma \leq\tau _{1}\cap \tau _{2},\\&{\text{if }}\sigma _{2}\leq \sigma _{1}{\text{ and }}\tau _{1}\leq \tau _{2}{\text{, then }}\sigma _{1}\to \tau _{1}\leq \sigma _{2}\to \tau _{2}\end{aligned}}}$

교차로 유형 하위 형식은 2차 시간 내에 해제할 수 있다.^[15]

유형 규칙

유형 규칙$({\displaystyle }$→ ${\displaystyle I}$) ${\displaystyle(\to \!\!)!$${\text{I$${\displaystyle }$(${\displaystyle }$→ ${\displaystyle E}$) ${\displaystyle(\to \!\!)!$${\text{E$ (${\displaystyle \cap }$ ${\displaystyle I}$) ${\displaystyle(\cap {\text${\text$})$$I}}},$(${\displaystyle \le }$) ${\displaystyle (\leq$ $)\},$${\displaystyle }$( ${\displaystyle A}$) ${\displaystyle({\text${\text$})$$A$${\displaystyle }$및 (${\displaystyle \Omega }$) ${\displaystyle (\omega )}$의 (${\displaystyle {}_{}}$ ${\displaystyle {\text{BCD}}_{}}$) ${\displaystyle (\vdash _{\text{B$)$CD}})}$은(는) 다음과 같다.

${\displaystyle {\begin{array}{cc}{\dfrac {\Gamma ,x:\sigma \vdash _{\text{B}CD}M:\tau }{\Gamma \vdash _{\text{BCD}\lambda x.\!M:\sigma \to \tau }}}(\to \!\!)!{\text{I})&#{\dfrac {\Gamma \vdash _{\text{B)CD}M:\sigma \to \to \to \quad \Gamma \vdash _{\text{BCD}}N:\sigma }{\Gamma \vdash _{\text{BCD}M\;N:\tau }}}(\to \!\!)!{\text{E})\\\\\\dfrac {\\Damma \vdash _{\text{BCD}M:\sigma \quad \Gamma \vdash _{\text{BCD}M:\tau }{\Gamma \vdash _{\text{BCD}M:\sigma \cap \tau }}}(\cap {\text{I}})&#{\dfrac {\Gamma \vdash _{\text{BCD}M:\sigma \quad(\sigma \leq \tau )}{\Gamma \vdash _{\text{BCD}M:\tau }}}(\leq )\\\\\\\\\\dfrac {}{\\Gamma ,x:\sigma \vdash _{\text{BCD}}x:\sigma }}{\text{A}})&#{\dfrac {}{\Gamma \vdash _{\text{BCD}M:\omega}(\omega )\end{array}}}$

특성.

• 의미론: (${\displaystyle {}_{}}$ ${\displaystyle {\text{BCD}}_{}}$) ${\displaystyle (\vdash _{\text{B$)$CD}})}$은(는) 건전하고 완전한 wrt. 필터 λ-모델로, λ- 기간의 해석은 여기에 할당할 수 있는 유형 집합과 일치한다.^[3]
• 환자 감소:만약 $\gamma {\displaystyle \mathrm{}{}_{\text{d}}}$ ${\displaystyle {}_{}}$ ${\displaystyle M}$: $\$ {\$displaystyle \Gamma \vdash _${\text${B$$CD}}M:\sigma }$과($와{\displaystyle {}_{}}$ M → ${\displaystyle {}_{}}$N {\$displaystyle M\to _${\${\displaystyle {}_{}}$$}N$ $then{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\text{BCD}}_{}}$ N${\displaystyle }$: ${\displaystyle \sigma }$ ${\displaysty \Gamma \vdash _{\text${\$b.$$CD}}N:\sigma$ $\}.$^[3]
• 제목 확장:만약 $\gamma {\displaystyle \mathrm{}{}_{\text{d}}}$ ${\displaystyle {}_{}}$ ${\displaystyle N}$: $\$ {\$displaystyle \Gamma \vdash _${\text${B$$CD}}N$$:\sigma }$ 및 $M{\displaystyle {}_{}}$→ ${\displaystyle {}_{}}$ N ${\displaystyle M\to _{\beta }N$}, $}$$then{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}}$ M${\displaystyle }$: ${\displaystyle \sigma }$ ${\displaystyle \Gamma \vdash _$${\text{$B$CD}}M:\sigma$^[3]
• 강력한 정규화의 특성화:${\displaystyle M}$ ${\displaystyle M}$이(가) $\gamma {\displaystyle \mathrm{}{}_{}}$ M${\displaystyle }$: ${\displaystyle \sigma }$ ${\displaystyle \Gamma \vdash _{\text{B$)인 경우에만 wrt. β 감소를 강하게 정규화하고 있다$$.$CD}M:\sigma }$은(는) 규칙$({\displaystyle \Omega }$) ${\displaystyle(\omega )}$이(가) 없이 파생 가능하며, 일부 $some$ ${\displaystyle \Gamma$ }$$및 $and$ ${\displaystyle \sigma$^[16]$}.$
• 주체 쌍: M ${\displaystyle M}$이(가) 강하게 정규화되고 있는$$ 경우${\displaystyle }$typing ,${\displaystyle \sigma }$) ${\displaystyle (\Gamma ,\sigma )}$이(가) 존재하며, 이는 모든 타이핑 $\gamma {\displaystyle {\mathrm{}}^{}{}_{}}$γ ${\displaystyle {\text{BCD}}_{}}$ ${\displaystyle {}_{}}$: ${\displaystyle {}^{}}$ ${\displaystyle {\backslash }^{}}$ \ \ { \$dash$\\$dash _${\$dash$}\$data$.$CD}M:\$${\displaystyle {}^{}}$ $'}$쌍$$$({\displaystyle }$ (,${\displaystyle {}^{},,{}^{})}$ )$${\$displaystyle(\Gamma ',\sigma ')}$은(는) 주쌍$({\displaystyle }$ ${\displaystyle \mathrm{\gamma },}$ ${\displaystyle \sigma }$) ${\displaystyle(\Gamma,\sigma )}$에서 확장, 상승, 대체의 방법으로$$ 얻을 수 있다$$.^[17]

참조