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 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 . Prostředí je často seznamem párů . Tento pár se někdy nazývá úkol. Kontext doplňuje výše uvedenou opozici. Společně tvoří a rozsudek označeno .
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, a jsou syntakticky odlišné pojmy, ale první se redukuje na druhý. Tato redukce je napsána . Tato pravidla také stanoví odpovídající ekvivalence mezi psaným výrazem .
Termín snižuje na . Od té doby 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ě ) je:
- Vzhledem k typovému prostředí , termín a typ , rozhodnout, zda termín lze přiřadit typ v prostředí typu .
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ě ) je:
- Vzhledem k termínu , rozhodnout, zda existuje prostředí typu a typ takový, že termín lze přiřadit typ v prostředí typu .
Varianta typovatelnosti je typovatelnost wrt. prostředí typu (zkráceně ), 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ě ) je:
- Vzhledem k typovému prostředí a typ , rozhodnout, zda existuje výraz kterému lze přiřadit typ v prostředí typu .
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 je viděn jako implikace, tj. jako tvrzení, že vyplývá z .
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 s délky 4 může být jiného typu než seznam 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 pro identitu. Existuje typ když je typ a a jsou oba výrazy typu . Termín typu se vykládá v tom smyslu, že je rovný .
V praxi je možné stavět typ ale nebude existovat termín tohoto typu. V intuicionistické teorii typů začínají nové pojmy rovnosti reflexivitou. Li je termín typu , pak existuje výraz typu . 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ž je výraz typu , pak existuje výraz typu a zmenšením vygenerovat výraz typu . 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 na , kde je spodní typ nemají žádné hodnoty. Existuje výraz s typem , ale ani jeden z typu .
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 a pro jednotlivce a pravdivostní hodnoty, respektive, a definuje sadu typů rekurzivně takto:
- -li a jsou typy, pak také je ;
- nic kromě základních typů a to, co z nich lze zkonstruovat pomocí předchozí klauze, jsou typy.
Složitý typ je typ funkce od entit typu entitám typu . Jeden má tedy typy jako které jsou interpretovány jako prvky sady funkcí od entit po pravdivostní hodnoty, tj. funkce indikátorů množin entit. Výraz typu 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
- ^ Kostel, Alonzo (1940). "Formulace jednoduché teorie typů". The Journal of Symbolic Logic. 5 (2): 56–68. doi:10.2307/2266170. JSTOR 2266170.
- ^ Barendregt, Henk (1991). "Úvod do systémů zobecněného typu". Journal of Functional Programming. 1 (2): 125–154. doi:10.1017 / s0956796800020025. hdl:2066/17240. ISSN 0956-7968.
- ^ Henk Barendregt; Wil Dekkers; Richard Statman (20. června 2013). Lambda kalkul s typy. Cambridge University Press. str. 66. ISBN 978-0-521-76614-2.
- ^ Heineman, George T .; Bessai, Jan; Düdder, Boris; Rehof, Jakob (2016). "Dlouhá a klikatá cesta k modulární syntéze". Využití aplikací formálních metod, ověřování a validace: základní techniky. ISoLA 2016. Přednášky v informatice. 9952. Springer. 303–317. doi:10.1007/978-3-319-47166-2_21.
- ^ ETCS v nLab
- ^ Bell, John L. (2012). „Typy, sady a kategorie“ (PDF). V Kanamory, Akihiro (ed.). Sady a rozšíření ve dvacátém století. Příručka dějin logiky. 6. Elsevier. ISBN 978-0-08-093066-4.
Reference
- Farmář, William M. (2008). "Sedm ctností teorie jednoduchého typu". Journal of Applied Logic. 6 (3): 267–286. doi:10.1016 / j.jal.2007.11.001.
Další čtení
- Aarts, C .; Backhouse, R .; Hoogendijk, P .; Voermans, E .; van der Woude, J. (prosinec 1992). „Relační teorie datových typů“. Technische Universiteit Eindhoven.
- Andrews B., Peter (2002). Úvod do matematické logiky a teorie typů: K pravdě skrz důkaz (2. vyd.). Kluwer. ISBN 978-1-4020-0763-7.
- Jacobs, Bart (1999). Teorie kategorické logiky a typů. Studie v logice a základech matematiky. 141. Elsevier. ISBN 978-0-444-50170-7. Pokrývá teorii typů do hloubky, včetně polymorfních a závislých rozšíření typu. Dává kategorická sémantika.
- Cardelli, Luca (1996). "Type Systems". V Tucker, Allen B. (ed.). Příručka o informatice a inženýrství. CRC Press. str. 2208–36. ISBN 9780849329098.
- Collins, Jordan E. (2012). Historie teorie typů: Vývoj po druhém vydání Principia Mathematica. Lambert Academic Publishing. hdl:11375/12315. ISBN 978-3-8473-2963-3. Poskytuje historický přehled vývoje teorie typů se zaměřením na úpadek teorie jako základu matematiky v průběhu čtyř desetiletí po vydání druhého vydání knihy „Principia Mathematica“.
- Constable, Robert L. (2012) [2002]. „Naivní teorie výpočetního typu“ (PDF). V Schwichtenberg, H .; Steinbruggen, R. (eds.). Důkaz a spolehlivost systému. Nato Science Series II. 62. Springer. 213–259. ISBN 9789401004138. Určeno jako protějšek teorie typů Paul Halmos (1960) Naivní teorie množin
- Coquand, Thierry (2018) [2006]. "Teorie typů". Stanfordská encyklopedie filozofie.
- Thompson, Simon (1991). Teorie typu a funkční programování. Addison – Wesley. ISBN 0-201-41667-0.
- Hindley, J. Roger (2008) [1995]. Základní teorie jednoduchého typu. Cambridge University Press. ISBN 978-0-521-05422-5. Dobrý úvod do teorie jednoduchých typů pro počítačové vědce; popsaný systém však není přesně církevní STT. Knižní recenze
- Kamareddine, Fairouz D .; Laan, Twan; Nederpelt, Rob P. (2004). Moderní pohled na teorii typů: od jejích počátků až do současnosti. Springer. ISBN 1-4020-2334-0.
- Ferreirós, José; Domínguez, José Ferreirós (2007). "X. Teorie logiky a typu v meziválečném období". Labyrint myšlení: historie teorie množin a její role v moderní matematice (2. vyd.). Springer. ISBN 978-3-7643-8349-7.
- Laan, T.D.L. (1997). Vývoj teorie typů v logice a matematice (PDF) (PhD). Eindhoven University of Technology. doi:10,6100 / IR498552. ISBN 90-386-0531-5.
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