Kázeň typu křižovatka - Intersection type discipline

v matematická logika, disciplína typu křižovatka je pobočkou teorie typů zahrnující systémy typu které používají konstruktor typu křižovatky ${ displaystyle ( cap)}$ přiřadit více typů jednomu termínu.^[1]Zejména pokud je termín ${ displaystyle M}$ lze přiřadit oba typ ${ displaystyle varphi _ {1}}$ a typ ${ displaystyle varphi _ {2}}$, pak ${ displaystyle M}$ lze přiřadit typ křižovatky ${ displaystyle varphi _ {1} cap varphi _ {2}}$ (a naopak). Proto lze konstruktor typu křižovatky použít k vyjádření konečných heterogenních ad hoc polymorfismus (naproti tomu parametrický polymorfismus ). Například λ-termín ${ displaystyle lambda x. ! (x ; x)}$ lze přiřadit typ ${ displaystyle (( alpha to beta) cap alpha) to beta}$ ve většině systémů typu křižovatka, za předpokladu pro termín proměnná ${ displaystyle x}$ oba typ funkce ${ displaystyle alpha to beta}$ a odpovídající typ argumentu ${ displaystyle alpha}$.

Mezi významné systémy typu křižovatky patří systém přiřazení typů Coppo – Dezani,^[2] systém přiřazování typů Barendregt-Coppo – Dezani,^[3] a základní systém přiřazování typů křižovatek.^[4]Nejpozoruhodnější je, že systémy typu křižovatky úzce souvisí s (a často přesně charakterizují) normalizační vlastnosti λ-podmínky pod β-redukce.

V programovacích jazycích, jako je TypeScript^[5] a Scala,^[6] typy křižovatek se používají k vyjádření ad hoc polymorfismus.

Dějiny

Průkopníkem disciplíny typu křižovatky byl Mario Coppo, Mariangiola Dezani-Ciancaglini, Patrick Sallé a Garrel Pottinger.^[2][7][8]Základní motivací bylo studium sémantických vlastností (např normalizace ) z λ-kalkul pomocí teorie typů.^[9]Zatímco počáteční práce Coppa a Dezaniho zavedla typovou teoretickou charakterizaci silné normalizace pro λI-kalkul,^[2] Pottinger rozšířil tuto charakterizaci na λK-kalkul.^[7]Kromě toho Sallé přispěl k pojmu univerzálního typu ${ displaystyle omega}$ které lze přiřadit libovolnému λ-členu, což odpovídá prázdné křižovatce.^[8]Použití univerzálního typu ${ displaystyle omega}$ umožnil jemnozrnnou analýzu normalizace hlavy, normalizace a silné normalizace.^[10]Ve spolupráci s Henk Barendregt, byl dán filtr λ-model pro systém typů křižovatek, vázající typy křižovatek stále více na sémantiku λ-kalkulu.

Kvůli korespondenci s normalizací typovatelnost v prominentních systémech typu křižovatky (kromě univerzálního typu) je nerozhodnutelný.Dodatečně, nerozhodnutelnost dvojího problému obydlí typu v prominentních systémech typu křižovatky prokázal Paweł Urzyczyn.^[11]Později byl tento výsledek vylepšen úplnost exponenciálního prostoru obydlí křižovatky 2. stupně a nerozhodnutelnost obydlení křižovatkového typu 3. úrovně.^[12]Pozoruhodně, ředitel školy bydlení typu je rozhodnutelné v polynomiální čas.^[13]

Systém přiřazování typů Coppo – Dezani

The Systém přiřazování typů Coppo – Dezani ${ displaystyle ( vdash _ { text {CD}})}$ rozšiřuje jednoduše zadejte λ-kalkul povolením převzetí více typů pro termínovou proměnnou.^[2]

Termínový jazyk

Termín jazyk ${ displaystyle ( vdash _ { text {CD}})}$ darováno λ-podmínky (nebo, výrazy lambda ):

${ displaystyle { begin {zarovnáno} M, N & :: = x mid ( lambda x. ! M) mid (M ; N) && { text {kde}} x { text {přesahuje proměnné termínu}} end {zarovnáno}}}$

Zadejte jazyk

Jazyk typu ${ displaystyle ( vdash _ { text {CD}})}$ je indukčně definována následující gramatikou:

${ displaystyle { begin {aligned} varphi & :: = alpha mid sigma to varphi && { text {where}} alpha { text {rozsahy přes proměnné typu}} sigma & :: = varphi _ {1} cap cdots cap varphi _ {n} && { text {where}} n geq 1 end {aligned}}}$

Konstruktor typu křižovatky (${ displaystyle cap}$) se bere modulo asociativita, komutativita a idempotence.

Zadejte pravidla

The pravidla typu ${ displaystyle ( to ! ! { text {I}})}$, ${ displaystyle ( to ! ! { text {E}})}$, ${ displaystyle ( cap { text {I}})}$, a ${ displaystyle ( cap { text {E}})}$ z ${ displaystyle ( vdash _ { text {CD}})}$ jsou:

${ displaystyle { begin {pole} {cc} { dfrac { Gamma, x: sigma vdash _ { text {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}} ( do ! ! { text {E}}) { dfrac { Gamma vdash _ { text {CD}} M: varphi _ {1} quad ldots 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} cap cdots cap varphi _ {n} vdash _ { text {CD}} x: varphi _ {i}}} ( cap { text {E}}) end {pole}}}$

Vlastnosti

Typičnost a normalizace spolu úzce souvisí ${ displaystyle ( vdash _ { text {CD}})}$ podle následujících vlastností:^[2]

• Redukce subjektu: Pokud ${ displaystyle Gamma vdash _ { text {CD}} M: sigma}$ a ${ displaystyle M až _ { beta} N}$, pak ${ displaystyle Gamma vdash _ { text {CD}} N: sigma}$.
• Normalizace: Pokud ${ displaystyle Gamma vdash _ { text {CD}} M: sigma}$, pak ${ displaystyle M}$ má β-normální forma.
• Typizovatelnost silně normalizující λ-podmínky: Pokud ${ displaystyle M}$ je silně normalizující, pak ${ displaystyle Gamma vdash _ { text {CD}} M: sigma}$ pro některé ${ displaystyle Gamma}$ a ${ displaystyle sigma}$.
• Charakterizace λI-normalizace: ${ displaystyle M}$ má normální tvar v λI-kalkulu, právě když ${ displaystyle Gamma vdash _ { text {CD}} M: sigma}$ pro některé ${ displaystyle Gamma}$ a ${ displaystyle sigma}$.

Pokud je jazyk typu rozšířen tak, aby obsahoval prázdnou křižovatku, tj. ${ displaystyle sigma = varphi _ {1} cap cdots cap varphi _ {n} { text {kde}} n = 0}$, pak ${ displaystyle ( vdash _ { text {CD}})}$ je uzavřen pod β-rovností a je solidní a úplný pro sémantiku odvození.^[14]

Systém přiřazování typů Barendregt – Coppo – Dezani

The Systém přiřazování typů Barendregt – Coppo – Dezani ${ displaystyle ( vdash _ { text {BCD}})}$ rozšiřuje systém přiřazování typů Coppo – Dezani o následující tři aspekty:^[3]

• ${ displaystyle ( vdash _ { text {BCD}})}$ zavádí konstanta univerzálního typu ${ displaystyle omega}$ (blízký prázdné křižovatce), které lze přiřadit libovolnému λ-členu.
• ${ displaystyle ( vdash _ { text {BCD}})}$ umožňuje konstruktor typu křižovatky ${ displaystyle ( cap)}$ se zobrazí na pravé straně konstruktoru typu šipky ${ displaystyle ( to)}$.
• ${ displaystyle ( vdash _ { text {BCD}})}$ zavádí podtypování typu křižovatky ${ displaystyle ( leq)}$ částečné pořadí na typech společně s odpovídajícím pravidlem psaní.

Termínový jazyk

Termín jazyk ${ displaystyle ( vdash _ { text {BCD}})}$ darováno λ-podmínky (nebo, výrazy lambda ):

${ displaystyle { begin {zarovnáno} M, N & :: = x mid ( lambda x. ! M) mid (M ; N) && { text {kde}} x { text {přesahuje proměnné termínu}} end {zarovnáno}}}$

Zadejte jazyk

Jazyk typu ${ displaystyle ( vdash _ { text {BCD}})}$ je indukčně definována následující gramatikou:

${ displaystyle { begin {zarovnáno} sigma, tau & :: = alpha mid omega mid sigma to tau mid sigma cap tau && { text {kde}} alfa { text {rozsahy přes proměnné typu}} end {zarovnáno}}}$

Podtypování typu křižovatky

Podtypování typu křižovatky ${ displaystyle ( leq)}$ je definován jako nejmenší předobjednávka (reflexní a tranzitivní relace) přes typy křižovatek splňující následující vlastnosti:

${ displaystyle { begin {zarovnáno} & 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 {if}} sigma leq tau _ {1} { text {and}} sigma leq tau _ {2} { text {, then} } sigma leq tau _ {1} cap tau _ {2}, & { text {if}} sigma _ {2} leq sigma _ {1} { text {and} } tau _ {1} leq tau _ {2} { text {, pak}} sigma _ {1} to tau _ {1} leq sigma _ {2} to tau _ {2} end {zarovnáno}}}$

Podtypování typu křižovatky je rozhodnutelné v kvadratickém čase.^[15]

Zadejte pravidla

The pravidla typu ${ displaystyle ( to ! ! { text {I}})}$, ${ displaystyle ( to ! ! { text {E}})}$, ${ displaystyle ( cap { text {I}})}$, ${ displaystyle ( leq)}$, ${ displaystyle ({ text {A}})}$, a ${ displaystyle ( omega)}$ z ${ displaystyle ( vdash _ { text {BCD}})}$ jsou:

${ displaystyle { begin {array} {cc} { dfrac { Gamma, x: sigma vdash _ { text {BCD}} M: tau} { Gamma vdash _ { text {BCD} } lambda x. ! M: sigma to tau}} ( to ! ! { text {I}}) & { dfrac { Gamma vdash _ { text {BCD}} M : sigma to tau quad Gamma vdash _ { text {BCD}} N: sigma} { Gamma vdash _ { text {BCD}} M ; N: tau}} ( do ! ! { text {E}}) { dfrac { Gamma 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 {pole}}}$

Vlastnosti

• Sémantika: ${ displaystyle ( vdash _ { text {BCD}})}$ je zvuk a kompletní wrt. filtr λ-model, ve kterém se interpretace λ-termínu shoduje s množinou typů, které mu lze přiřadit.^[3]
• Redukce subjektu: Pokud ${ displaystyle Gamma vdash _ { text {BCD}} M: sigma}$ a ${ displaystyle M až _ { beta} N}$, pak ${ displaystyle Gamma vdash _ { text {BCD}} N: sigma}$.^[3]
• Rozšíření předmětu: Pokud ${ displaystyle Gamma vdash _ { text {BCD}} N: sigma}$ a ${ displaystyle M až _ { beta} N}$, pak ${ displaystyle Gamma vdash _ { text {BCD}} M: sigma}$.^[3]
• Charakterizace silná normalizace: ${ displaystyle M}$ silně normalizuje wrt. β-redukce, právě když ${ displaystyle Gamma vdash _ { text {BCD}} M: sigma}$ je odvoditelné bez pravidla ${ displaystyle ( omega)}$ pro některé ${ displaystyle Gamma}$ a ${ displaystyle sigma}$.^[16]
• Hlavní páry: Pokud ${ displaystyle M}$ se silně normalizuje, pak existuje pár principů ${ displaystyle ( Gamma, sigma)}$ tak, že pro jakékoli psaní ${ displaystyle Gamma ' vdash _ { text {BCD}} M: sigma'}$ dvojice ${ displaystyle ( Gamma ', sigma')}$ lze získat od hlavního páru ${ displaystyle ( Gamma, sigma)}$ pomocí rozšíření typu, zvedání a nahrazování.^[17]

Reference