Teorie typů - Type theory - Wikipedia

v matematika, logika, a počítačová věda, a typový systém je formální systém ve kterém má každý výraz „typ“, který definuje jeho význam a operace, které s ním lze provádět. Teorie typů je akademické studium typových systémů.

Některé teorie typů slouží jako alternativa k teorie množin jako základ matematiky. Dvě známé takové teorie jsou Alonzo Church je zadaný λ-kalkul a Per Martin-Löf je intuicionistická teorie typů.

Teorie typů byla vytvořena, aby se zabránilo paradoxům v předchozích základech, jako je naivní teorie množin, formální logika a přepsat systémy.

Teorie typů úzce souvisí s, a v některých případech se překrývá s, systémy výpočetního typu, která oblast programovací jazyk funkce použitá ke snížení hmyz.

Dějiny

V letech 1902 a 1908 Bertrand Russell navrhl různé „teorie typu“ v reakci na jeho objev, že Gottlob Frege verze naivní teorie množin byl postižen Russellův paradox. V roce 1908 Russell dospěl k „rozvětvené“ teorii typů společně s „axiom redukovatelnosti "oba vystupovali prominentně v Whitehead a Russell je Principia Mathematica publikovány v letech 1910 až 1913. Pokusili se vyřešit Russellův paradox tím, že nejprve vytvořili hierarchii typů a poté přiřadili každou konkrétní matematickou (a případně další) entitu k typu. Entity daného typu jsou vytvářeny výhradně z entit těch typů, které jsou nižší v jejich hierarchii, což brání tomu, aby byla entitě přiřazena sama.

Ve 20. letech Leon Chwistek a Frank P. Ramsey navrhl neramifikovanou teorii typů, nyní známou jako „teorie jednoduchých typů“ nebo jednoduchá teorie typů, který zhroutil hierarchii typů v dřívější rozvětvené teorii a jako takový nevyžadoval axiom redukovatelnosti.

Běžné použití „teorie typů“ je, když se tyto typy používají s a systém přepisování termínů. Nejslavnějším časným příkladem je Alonzo Church je jednoduše zadaný lambda kalkul. Církevní teorie typů^[1] pomohl formálnímu systému vyhnout se Paradox Kleene – Rosser který postihl původní netypový lambda kalkul. Církev prokázala, že by mohla sloužit jako základ matematiky, a byla označována jako a logika vyššího řádu.

Některé další teorie typů zahrnují Per Martin-Löf je intuicionistická teorie typů, který byl základem používaným v některých oblastech konstruktivní matematika. Thierry Coquand je počet konstrukcí a jeho deriváty jsou základem, který používá Coq, Opírat se, a další. Tato oblast je oblastí aktivního výzkumu, jak dokládá teorie homotopy.

Základní pojmy

Současná prezentace systémů typů v kontextu teorie typů byla systematizována koncepčním rámcem zavedeným Henk Barendregt^[2].

Typ, termín, hodnota

V systému teorie typů, a období je proti typ. Například, 4, 2 + 2, a ${ displaystyle 2 cdot 2}$ jsou všechny samostatné výrazy s typem nat pro přirozená čísla. Tradičně za výrazem následuje dvojtečka a její typ, například 2: nat - to znamená, že číslo 2 je typu nat. Kromě této opozice a syntaxe lze o typech v této obecnosti říci jen málo, ale často jsou interpretovány jako nějaký druh sbírky (ne nutně sady) hodnoty které by tento výraz mohl vyhodnotit. Je obvyklé označovat termíny pomocí E a typy podle τ. To, jak jsou formovány termíny a typy, závisí na konkrétním typovém systému a je některými upřesněno syntax a další omezení dobře tvarovaná.

Prostředí psaní, přiřazení typu, posouzení typu

Psaní obvykle probíhá u některých kontext nebo životní prostředí označeno symbolem ${ displaystyle Gamma}$. Prostředí je často seznamem párů ${ displaystyle e: tau}$. Tento pár se někdy nazývá úkol. Kontext doplňuje výše uvedenou opozici. Společně tvoří a rozsudek označeno ${ displaystyle Gamma vdash e: tau}$.

Pravidla přepisování, převod, redukce

Teorie typů mají explicitní výpočet a jsou zakódovány v pravidlech pro přepis podmínky. Tito se nazývají pravidla převodu nebo, pokud pravidlo funguje pouze jedním směrem, a snížení pravidlo. Například, ${ displaystyle 2 + 2}$ a ${ displaystyle 4}$ jsou syntakticky odlišné pojmy, ale první se redukuje na druhý. Tato redukce je napsána ${ displaystyle 2 + 2 twoheadrightarrow 4}$. Tato pravidla také stanoví odpovídající ekvivalence mezi psaným výrazem ${ displaystyle 2 + 2 equiv 4}$.

Termín ${ displaystyle 2 + 1}$ snižuje na ${ displaystyle 3}$. Od té doby ${ displaystyle 3}$ nelze dále redukovat, nazývá se a normální forma. Různé systémy zadaný lambda kalkul včetně jednoduše zadaný lambda kalkul, Jean-Yves Girard Systém F a Thierry Coquand počet konstrukcí jsou silně normalizující. V takových systémech znamená úspěšná kontrola typu a důkaz ukončení termínu.

Zadejte pravidla

Na základě typu úsudků a rovnocennosti odvozovací pravidla lze použít k popisu toho, jak typový systém přiřadí typ syntaktickým konstrukcím (výrazům), podobně jako v přirozený odpočet. Aby to bylo smysluplné, pravidla převodu a typu obvykle úzce souvisí, jako např. podle a redukce subjektu majetek, který by mohl založit část zdravost typového systému.

Problémy s rozhodováním

Typový systém je přirozeně spojen s rozhodovací problémy z kontrola typu, typovatelnost, a obydlí typu.^[3]

Kontrola typu

Rozhodovací problém kontrola typu (zkráceně ${ displaystyle Gamma vdash e: tau?}$) je:

Vzhledem k typovému prostředí ${ displaystyle Gamma}$, termín ${ displaystyle e}$a typ ${ displaystyle tau}$, rozhodnout, zda termín ${ displaystyle e}$ lze přiřadit typ ${ displaystyle tau}$ v prostředí typu ${ displaystyle Gamma}$.

Rozhodnutelnost kontrola typu znamená, že bezpečnost typu libovolného daného textu programu (zdrojový kód) lze ověřit.

Typizovatelnost

Rozhodovací problém typovatelnost (zkráceně ${ displaystyle existuje gama, tau. gama vdash e: tau?}$) je:

Vzhledem k termínu ${ displaystyle e}$, rozhodnout, zda existuje prostředí typu ${ displaystyle Gamma}$ a typ ${ displaystyle tau}$ takový, že termín ${ displaystyle e}$ lze přiřadit typ ${ displaystyle tau}$ v prostředí typu ${ displaystyle Gamma}$.

Varianta typovatelnosti je typovatelnost wrt. prostředí typu (zkráceně ${ displaystyle existuje tau. Gamma vdash e: tau?}$), pro které je typové prostředí součástí vstupu. Pokud daný výraz neobsahuje externí odkazy (například proměnné volného výrazu), typovatelnost se shoduje s typovatelností wrt. prostředí prázdného typu.

Typizovatelnost úzce souvisí s odvození typu. Zatímco typovatelnost (jako problém s rozhodováním) řeší existenci typu pro daný termín, odvození typu (jako problém s výpočtem) vyžaduje výpočet skutečného typu.

Typ obydlí

Rozhodovací problém obydlí typu (zkráceně ${ Displaystyle existuje např. Gamma vdash e: tau?}$) je:

Vzhledem k typovému prostředí ${ displaystyle Gamma}$ a typ ${ displaystyle tau}$, rozhodnout, zda existuje výraz ${ displaystyle e}$ kterému lze přiřadit typ ${ displaystyle tau}$ v prostředí typu ${ displaystyle Gamma}$.

Girardův paradox ukazuje, že obydlení typu silně souvisí s konzistencí typového systému s korespondencí Curry – Howard. Aby byl takový systém zdravý, musí mít neobydlené typy.

Protikladem termínů a typů mohou být také pohledy jako jeden z implementace a Specifikace. Podle syntéza programu (výpočetní protějšek) obydlení typu (viz níže) lze použít ke konstrukci (všech nebo jejich částí) programů ze specifikace uvedené ve formě informací o typu.^[4]

Výklady teorie typů

Teorie typů úzce souvisí s mnoha oblastmi aktivního výzkumu. Korespondence Curry – Howard poskytuje zejména hluboký izomorfismus mezi intuicionistickou logikou, zadaným lambda kalkulem a kartézskými uzavřenými kategoriemi.

Intuicionistická logika

Vedle pohledu na typy jako na soubor hodnot termínu nabízí teorie typů druhou interpretaci opozice termínu a typů. Typy lze považovat za propozice a termíny jako důkazy. V tomto způsobu čtení psaní, typ funkce ${ displaystyle alpha rightarrow beta}$ je viděn jako implikace, tj. jako tvrzení, že ${ displaystyle beta}$ vyplývá z ${ displaystyle alpha}$.

Teorie kategorií

The interní jazyk kartézské uzavřené kategorie je jednoduše zadaný lambda kalkul. Tento pohled lze rozšířit i na další zadané lambda kameny. Určité karteziánské uzavřené kategorie, topoi, byly navrženy jako obecné prostředí pro matematiku namísto tradiční teorie množin.

Rozdíl od teorie množin

Existuje mnoho různých teorií množin a mnoho různých systémů teorie typů, takže následuje zobecnění.

• Teorie množin je postavena na logice. Vyžaduje samostatný systém jako predikátová logika pod ním. V teorii typů lze pojmy jako „a“ a „nebo“ zakódovat jako typy v samotné teorii typů.
• V teorii množin není prvek omezen na jednu množinu. V teorii typů patří výrazy (obecně) pouze jednomu typu. (Tam, kde by byla použita podmnožina, má teorie typů tendenci používat a predikátová funkce který vrátí true, pokud je výraz v podmnožině, a vrátí false, pokud hodnota není. Spojení dvou typů lze definovat jako nový typ s názvem a typ součtu, který obsahuje nové výrazy.)
• Teorie množin obvykle kóduje čísla jako množiny. (0 je prázdná množina, 1 je množina obsahující prázdnou množinu atd. Viz Set-teoretická definice přirozených čísel.) Teorie typů může kódovat čísla jako funkce pomocí Kódování kostela nebo přirozeněji jako indukční typy. Induktivní typy vytvářejí nové konstanty pro nástupnická funkce a nula, velmi podobná Peanoovy axiomy.
• Teorie typů má jednoduché spojení s konstruktivní matematikou prostřednictvím Interpretace BHK. Může být připojen k logice pomocí Curry – Howardův izomorfismus. A s některými teoriemi typů úzce souvisí Teorie kategorií.

Volitelné funkce

Závislé typy

A závislý typ je typ, který závisí na termínu nebo jiném typu. Typ vrácený funkcí tedy může záviset na argumentu funkce.

Například seznam ${ displaystyle mathrm {nat}}$s délky 4 může být jiného typu než seznam ${ displaystyle mathrm {nat}}$s délky 5. V teorii typů se závislými typy je možné definovat funkci, která přebírá parametr „n“ a vrací seznam obsahující nuly „n“. Voláním funkce s 4 by vznikl termín s jiným typem, než kdyby byla funkce volána s 5.

Závislé typy hrají ústřední roli v intuicionistická teorie typů a v designu funkční programovací jazyky jako Idrisi, ATS, Agda a Epigram.

Typy rovnosti

Mnoho systémů teorie typů má typ, který představuje rovnost typů a termínů. Tento typ se liší od směnitelnosti a často se označuje výroková rovnost.

V intuicionistické teorii typů je typ rovnosti (nazývaný také typ identity) známý jako ${ displaystyle I}$ pro identitu. Existuje typ ${ displaystyle I A a b}$ když ${ displaystyle A}$ je typ a ${ displaystyle a}$ a ${ displaystyle b}$ jsou oba výrazy typu ${ displaystyle A}$. Termín typu ${ displaystyle I A a b}$ se vykládá v tom smyslu, že ${ displaystyle a}$ je rovný ${ displaystyle b}$.

V praxi je možné stavět typ ${ displaystyle I mathrm {nat} 3 4}$ ale nebude existovat termín tohoto typu. V intuicionistické teorii typů začínají nové pojmy rovnosti reflexivitou. Li ${ displaystyle 3}$ je termín typu ${ displaystyle mathrm {nat}}$, pak existuje výraz typu ${ displaystyle I mathrm {nat} 3 3}$. Složitější rovnosti lze vytvořit vytvořením reflexivního výrazu a následným zmenšením na jedné straně. Takže když ${ displaystyle 2 + 1}$ je výraz typu ${ displaystyle mathrm {nat}}$, pak existuje výraz typu ${ displaystyle I mathrm {nat} (2 + 1) (2 + 1)}$ a zmenšením vygenerovat výraz typu ${ displaystyle I mathrm {nat} (2 + 1) 3}$. V tomto systému tedy typ rovnosti označuje, že dvě hodnoty stejného typu lze převést redukcemi.

Mít typ pro rovnost je důležité, protože s ním lze manipulovat uvnitř systému. Obvykle neexistuje úsudek, který by řekl dva termíny ne rovnat se; místo toho, jako v Brouwer – Heyting – Kolmogorovova interpretace, mapujeme ${ displaystyle neg (a = b)}$ na ${ displaystyle (a = b) na bot}$, kde ${ displaystyle bot}$ je spodní typ nemají žádné hodnoty. Existuje výraz s typem ${ displaystyle (I mathrm {nat} 3 4) na bot}$, ale ani jeden z typu ${ displaystyle (I mathrm {nat} 3 3) na bot}$.

Teorie typu homotopy se liší od intuicionistická teorie typů většinou zpracováním typu rovnosti.

Indukční typy

Systém teorie typů vyžaduje, aby fungovaly některé základní pojmy a typy. Některé systémy je sestavují z funkcí pomocí Kódování kostela. Jiné systémy mají indukční typy: sada základních typů a sada konstruktory typu které generují typy s dobře vychovanými vlastnostmi. Například, určité rekurzivní funkce Je zaručeno, že volané indukční typy budou ukončeny.

Koinduktivní typy jsou nekonečné datové typy vytvořené poskytnutím funkce, která generuje další prvky. Vidět Koindukce a Corecursion.

Indukce-indukce je funkce pro deklaraci indukčního typu a rodiny typů, která závisí na indukčním typu.

Indukční rekurze umožňuje širší škálu dobře vychovaných typů, což umožňuje současně definovat typ a rekurzivní funkce, které na něm pracují.

Typy vesmíru

Byly vytvořeny typy, aby se zabránilo paradoxům, jako např Russellův paradox. Motivy, které vedou k těmto paradoxům - schopnost říkat věci o všech typech - však stále existují. Mnoho teorií typů má tedy „vesmírný typ“, který obsahuje všechny jiný typy (a ne sám).

V systémech, kde byste chtěli něco říci o typech vesmíru, existuje hierarchie typů vesmíru, z nichž každý obsahuje hierarchii pod ní. Hierarchie je definována jako nekonečná, ale příkazy se musí vztahovat pouze na konečný počet úrovní vesmíru.

Typové vesmíry jsou v teorii typů obzvláště složité. Původní návrh intuicionistické teorie typů trpěl Girardův paradox.

Výpočtová složka

Mnoho systémů teorie typů, jako je jednoduše zadaný lambda kalkul, intuicionistická teorie typů a počet konstrukcí, jsou také programovací jazyky. To znamená, že se o nich říká, že mají „výpočetní složku“. Výpočet je redukce podmínek používaného jazyka pravidla přepisování.

Systém teorie typů, který má dobře vychovanou výpočetní složku, má také jednoduché spojení s konstruktivní matematikou prostřednictvím Interpretace BHK.

Nekonstruktivní matematika v těchto systémech je možná přidáním operátorů na pokračování, jako je hovor s aktuálním pokračováním. Tito operátoři však mají tendenci porušovat žádoucí vlastnosti, jako je kanoničnost a parametricita.

Zadejte teorie

Hlavní, důležitý

• Jednoduše zadaný lambda kalkul což je logika vyššího řádu;
• intuicionistická teorie typů;
• systém F;
• LF se často používá k definování jiných teorií typů;
• počet konstrukcí a jeho deriváty.

Méně důležitý

• Automath;
• Teorie typu ST;
• UTT (Laosova jednotná teorie závislých typů)
• některé formy kombinační logika;
• ostatní definované v lambda kostka;
• ostatní pod jménem zadaný lambda kalkul;
• ostatní pod jménem čistý typ systému.

Aktivní

• Teorie typu homotopy je zkoumán.

Praktický dopad

Programovací jazyky

Existuje velké překrývání a interakce mezi poli teorie typů a systémy typů. Typové systémy jsou funkcí programovacího jazyka navrženou k identifikaci chyb. Jakákoli statická analýza programu, například algoritmy kontroly typu v souboru sémantická analýza fáze překladač, má souvislost s teorií typů.

Ukázkovým příkladem je Agda, programovací jazyk, který pro svůj typový systém používá UTT (Luova sjednocená teorie závislých typů). Programovací jazyk ML byl vyvinut pro manipulaci s teoriemi typů (viz LCF ) a jeho vlastní typový systém byl jimi silně ovlivněn.

Matematické základy

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Květen 2008)

Zavolal první počítačový asistent Automath, používá teorii typů ke kódování matematiky na počítači. Speciálně vyvinut Martin-Löf intuicionistická teorie typů kódovat Všechno matematika sloužit jako nový základ pro matematiku. Probíhá výzkum využití matematických základů teorie homotopy.

Matematici pracující v teorie kategorií již měl potíže s prací s široce přijímaným základem Teorie množin Zermelo – Fraenkel. To vedlo k návrhům, jako je Lawvere's Elementary Theory of the Category of Sets (ETCS).^[5] Teorie typu homotopy pokračuje v tomto řádku pomocí teorie typů. Vědci zkoumají souvislosti mezi závislými typy (zejména typ identity) a algebraická topologie (konkrétně homotopy ).

Důkazní asistenti

Velká část současného výzkumu teorie typů je řízena kontrolní dáma, interaktivní důkazní asistenti, a automatizované věty provers. Většina z těchto systémů používá teorii typů jako matematický základ pro kódování důkazů, což není překvapující vzhledem k úzkému spojení mezi teorií typů a programovacími jazyky:

• LF je používán Twelf, často definovat jiné teorie typů;
• mnoho typů teorií, které spadají pod logika vyššího řádu jsou používány Rodina provokátorů HOL a PVS;
• výpočetní typovou teorii používá NuPRL;
• počet konstrukcí a jeho deriváty používá Coq, Matita, a Opírat se;
• UTT (Luova sjednocená teorie závislých typů) používá Agda což je jak programovací jazyk, tak i proof proof asistent

Mnoho teorií typů podporuje LEGO a Isabelle. Isabelle také podporuje nadace kromě teorií typů, jako je ZFC. Mizar je příkladem systému důkazů, který podporuje pouze teorii množin.

Lingvistika

Teorie typů je také široce používána v formální teorie sémantiky z přirozené jazyky, zvláště Montague gramatika a jeho potomci. Zejména, kategoriální gramatiky a předskupinové gramatiky k definování typů intenzivně používejte konstruktory typů (podstatné jméno, slovesoatd.) slov.

Nejběžnější konstrukce má základní typy ${ displaystyle e}$ a ${ displaystyle t}$ pro jednotlivce a pravdivostní hodnoty, respektive, a definuje sadu typů rekurzivně takto:

• -li ${ displaystyle a}$ a ${ displaystyle b}$ jsou typy, pak také je ${ displaystyle langle a, b rangle}$;
• nic kromě základních typů a to, co z nich lze zkonstruovat pomocí předchozí klauze, jsou typy.

Složitý typ ${ displaystyle langle a, b rangle}$ je typ funkce od entit typu ${ displaystyle a}$ entitám typu ${ displaystyle b}$. Jeden má tedy typy jako ${ displaystyle langle e, t rangle}$ které jsou interpretovány jako prvky sady funkcí od entit po pravdivostní hodnoty, tj. funkce indikátorů množin entit. Výraz typu ${ displaystyle langle langle e, t rangle, t rangle}$ je funkce od množin entit k pravdivostním hodnotám, tj. (indikační funkce a) množiny množin. Tento druhý typ se standardně považuje za typ kvantifikátory přirozeného jazyka, jako všichni nebo nikdo (Montague 1973, Barwise a Cooper 1981).

Společenské vědy

Gregory Bateson zavedl teorii logických typů do společenských věd; jeho představy o dvojitá vazba a logické úrovně jsou založeny na Russellově teorii typů.

Vztah k teorii kategorií

Ačkoli počáteční motivace pro teorie kategorií byl daleko od foundationalismu, ukázalo se, že tato dvě pole mají hluboké souvislosti. Tak jako John Lane Bell píše: „Ve skutečnosti kategorie mohou oni sami být vnímán jako teorie typu určitého druhu; tato skutečnost sama o sobě naznačuje, že teorie typů je mnohem více spjata s teorií kategorií než s teorií množin. “Stručně řečeno, na kategorii lze pohlížet jako na teorii typů tím, že její objekty považujeme za typy (nebo druhy), tj.„ Zhruba řečeno , kategorii lze považovat za teorii typů zbavenou své syntaxe. “Tímto způsobem následuje řada významných výsledků:^[6]

• kartézské uzavřené kategorie odpovídají zadanému λ-kalkulu (Lambek, 1970);
• C-monoidy (kategorie s produkty a exponenciály a jedním neterminálním objektem) odpovídají netypickému λ-kalkulu (pozorovanému nezávisle Lambekem a Dana Scott kolem 1980);
• místně kartézské uzavřené kategorie odpovídají Teorie typu Martin-Löf (Seely, 1984).

Souhra, známá jako kategorická logika, je od té doby předmětem aktivního výzkumu; viz například monografii Jacobse (1999).

Viz také

• Datový typ pro konkrétní typy dat v programování
• Teorie domén
• Typ (teorie modelu)
• Typový systém pro praktičtější diskusi o typových systémech pro programovací jazyky
• Univalentní základy

Poznámky

Reference

Další čtení

externí odkazy

• Robert L. Constable (vyd.). "Teorie výpočetního typu". Scholarpedia.
• Fórum TYPY - moderované e-mailové fórum zaměřené na teorii typů v informatice, fungující od roku 1987.
• Kniha Nuprl: "Úvod do teorie typů. "
• Druhy Přednášky k projektu letních škol 2005–2008
  • The Letní škola 2005 má úvodní přednášky