Typteori - Type theory

Inom matematik , logik och datavetenskap är ett typsystem ett formellt system där varje term har en "typ" som definierar dess betydelse och de operationer som kan utföras på den. Typteori är den akademiska studien av typsystem.

Vissa typteorier fungerar som alternativ till uppsättningsteori som grund för matematik . Två välkända sådana teorier är Alonzo Church 's typad λ-kalkyl och Per Martin-Löf är intuitionistisk typteori .

Typteori skapades för att undvika paradoxer i tidigare grunder som naiv uppsättningsteori , formell logik och skriva om system .

Typteori är nära besläktad med och i vissa fall överlappar med beräkningstypsystem , som är ett programmeringsspråk som används för att minska buggar och underlätta vissa kompilatoroptimeringar .

Historia

Mellan 1902 och 1908 föreslog Bertrand Russell olika "teorier om typ" som svar på hans upptäckt att Gottlob Freges version av naiv uppsättningsteori drabbades av Russells paradox . Genom 1908 kom Russell på en "förgrenad" teori typer tillsammans med en " axiom reducerbarhet " som båda framträdande plats i Whitehead och Russell 's Principia Mathematica publicerades mellan 1910 och 1913. De försökte lösa Russells paradox genom att först skapa en hierarki av typer och tilldelar sedan varje konkret matematisk (och eventuellt annan) enhet till en typ. Enheter av en given typ byggs uteslutande från enheter av de typer som är lägre i deras hierarki, vilket förhindrar att en enhet tilldelas sig själv.

På 1920 -talet föreslog Leon Chwistek och Frank P. Ramsey en oramifierad typteori, nu känd som "teorin om enkla typer" eller enkel typteori , som kollapsade hierarkin av typerna i den tidigare ramifierade teorin och som sådan inte krävde reducerbarhetens axiom.

Den vanliga användningen av "typteori" är när dessa typer används med en term omskrivningssystem . Den mest kända tidigt exempel är Alonzo Church 'är helt enkelt skrivit lambdakalkyl . Kyrkans teori om typer hjälpte det formella systemet att undvika Kleene – Rosser -paradoxen som drabbade den ursprungliga oskrivna lambda -kalkylen. Church visade att den kunde fungera som en grund för matematik och det kallades för en logik av högre ordning .

Några andra teorier typ inkluderar Per Martin-Löf är intuitionistisk typteori , som har varit grunden används i vissa områden av konstruktiv matematik . Thierry Coquand s kalkyl av konstruktioner och dess derivat är grunden används av Coq , Lean , och andra. Fältet är ett område med aktiv forskning, vilket framgår av homotopytypsteori .

Grundläggande koncept

Den samtida presentationen av typsystem i samband med typteori har gjorts systematisk genom ett konceptuellt ramverk som introducerades av Henk Barendregt .

Typ, term, värde

I ett system med typteori är en term motsatt en typ . Till exempel 4 , 2 + 2 och är alla separata termer med typen nat för naturliga tal. Traditionellt följs termen av ett kolon och dess typ, till exempel 2: nat - det betyder att talet 2 är av typen nat . Utöver detta motstånd och syntax kan lite sägas om typer i denna allmänhet, men ofta tolkas de som en slags samling (inte nödvändigtvis uppsättningar) av de värden som termen kan utvärdera till. Det är vanligt att beteckna termer med e och typ med τ . Hur termer och typer formas beror på det specifika typsystemet och preciseras av vissa syntaxer och ytterligare begränsningar av välformning . ${\ displaystyle 2 \ cdot 2}$

Skrivmiljö, typuppgift, typbedömning

Typning sker vanligtvis i något sammanhang eller en miljö som symbolen anger . Ofta är en miljö en lista med par . Detta par kallas ibland för en uppgift . Sammanhanget fullbordar ovannämnda opposition. Tillsammans bildar de en dom betecknad . ${\ displaystyle \ Gamma}$${\ displaystyle e: \ tau}$${\ displaystyle \ Gamma \ vdash e: \ tau}$

Omskrivningsregler, konvertering, minskning

Typteorier har tydlig beräkning och den är kodad i regler för omskrivning av termer. Dessa kallas konverteringsregler eller, om regeln fungerar bara i en riktning, en minskning regel . Till exempel och är syntaktiskt olika termer, men den förra reduceras till den senare. Denna minskning är skriven . Dessa regler fastställer också motsvarande likvärdigheter mellan termerna, skrivna . ${\ displaystyle 2+2}$${\ displaystyle 4}$${\ displaystyle 2+2 \ twoheadrightarrow 4}$${\ displaystyle 2+2 \ equiv 4}$

Termen minskar till . Eftersom det inte kan reduceras ytterligare kallas det en normal form . Olika system för typad lambdakalkyl inklusive helt enkelt typad lambdakalkyl , Jean-Yves Girard s System F , och Thierry Coquand s kalkyl av konstruktioner är starkt normalisering . I sådana system innebär en lyckad typkontroll ett avslutningsbevis för termen. ${\ displaystyle 2+1}$${\ displaystyle 3}$${\ displaystyle 3}$

Skriv regler

Baserat på bedömningar och ekvivalenser kan typinferensregler användas för att beskriva hur ett typsystem tilldelar en typ syntaktiska konstruktioner (termer), ungefär som i naturligt avdrag . För att vara meningsfulla är konverterings- och typregler vanligtvis nära besläktade med t.ex. av en ämnesreducerande egenskap, vilket kan fastställa en del av ett typsystems sundhet .

Beslutsproblem

En typ av system är naturligt associerad med beslutsproblem med typkontroll , typability och typ inhabitation .

Typkontroll

Beslutsproblemet med typkontroll (förkortat med ) är: ${\ displaystyle \ Gamma \ vdash e: \ tau?}$

Med tanke på en typmiljö , en term och en typ , avgör om termen kan tilldelas typen i typmiljön .${\ displaystyle \ Gamma}$${\ displaystyle e}$${\ displaystyle \ tau}$${\ displaystyle e}$${\ displaystyle \ tau}$${\ displaystyle \ Gamma}$

Avgörbarhet för typkontroll innebär att typsäkerheten för en given programtext (källkod) kan verifieras.

Typbarhet

Beslutsproblemet med typbarhet (förkortat med ) är: ${\ displaystyle \ exist \ Gamma, \ tau. \ Gamma \ vdash e: \ tau?}$

Ge en term , bestäm om det finns en typmiljö och en typ så att termen kan tilldelas typen i typmiljön .${\ displaystyle e}$${\ displaystyle \ Gamma}$${\ displaystyle \ tau}$${\ displaystyle e}$${\ displaystyle \ tau}$${\ displaystyle \ Gamma}$

En variant av typbarhet är typability wrt. en typmiljö (förkortad med ), för vilken en typmiljö är en del av ingången. Om den givna termen inte innehåller externa referenser (t.ex. variabler med fristående term), sammanfaller typbarhet med typbarhet wrt. den tomma typen av miljö. ${\ displaystyle \ finns \ tau. \ Gamma \ vdash e: \ tau?}$

Typbarhet är nära besläktad med typinferens . Medan typbarhet (som ett beslutsproblem) behandlar förekomsten av en typ för en given term, kräver typinferens (som ett beräkningsproblem) en faktisk typ för att beräknas.

Typ beboelse

Beslutsproblemet med typbefolkning (förkortat med ) är: ${\ displaystyle \ existerar e. \ Gamma \ vdash e: \ tau?}$

Med tanke på en typmiljö och en typ , besluta om det finns en term som kan tilldelas typen i typmiljön .${\ displaystyle \ Gamma}$${\ displaystyle \ tau}$${\ displaystyle e}$${\ displaystyle \ tau}$${\ displaystyle \ Gamma}$

Girards paradox visar att typbefolkningen är starkt relaterad till att ett typsystem är i överensstämmelse med Curry – Howard -korrespondens. För att vara sund måste ett sådant system ha obebodda typer.

Motståndet mellan termer och typer kan också ses som implementering och specifikation . Genom programsyntes (beräkningsmotståndet till) typ beboelse (se nedan) kan användas för att konstruera (alla eller delar av) program från specifikationer som ges i form av typinformation.

Tolkningar av typteori

Typteori är nära kopplad till många områden inom aktiv forskning. Speciellt ger Curry -Howard -korrespondensen en djup isomorfism mellan intuitionistisk logik, typad lambda -kalkyl och kartesiska slutna kategorier.

Intuitionistisk logik

Förutom synen på typer som samling av värden för en term erbjuder typteori en andra tolkning av motståndet mellan term och typer. Typer kan ses som propositioner och termer som bevis . På detta sätt att läsa en typning ses en funktionstyp som en implikation , dvs. som propositionen, som följer av . ${\ displaystyle \ alpha \ rightarrow \ beta}$${\ displaystyle \ beta}$${\ displaystyle \ alpha}$

Kategoriteori

Det interna språket i den kartesiska slutna kategorin är den enkelt skrivna lambda -kalkylen . Denna vy kan utökas till andra typade lambda -beräkningar. Vissa kartesiska slutna kategorier, topoi, har föreslagits som en allmän inställning för matematik, istället för traditionell uppsättningsteori.

Skillnad från uppsättningsteori

Det finns många olika uppsättningsteorier och många olika system för typteori, så det som följer är generaliseringar.

• Uppsättningsteori bygger på logik. Det kräver ett separat system som predikatlogik under det. I typteori kan begrepp som "och" och "eller" kodas som typer i själva typteorin.
• I uppsättningsteori är ett element inte begränsat till en uppsättning. I typteori tillhör termer (i allmänhet) endast en typ. (Där en delmängd skulle användas, tenderar typteori att använda en predikatfunktion som returnerar sant om termen finns i delmängden och returnerar falskt om värdet inte är. Föreningen mellan två typer kan definieras som en ny typ som kallas summa typ , som innehåller nya termer.)
• Uppsättningsteori kodar vanligtvis tal som uppsättningar. (0 är den tomma uppsättningen, 1 är en uppsättning som innehåller den tomma uppsättningen, etc. Se uppsättningsteoretisk definition av naturliga tal .) Typteori kan koda tal som funktioner med hjälp av kyrkkodning eller mer naturligt som induktiva typer . Induktiva typer skapar nya konstanter för efterföljarfunktionen och noll, som liknar Peanos axiom .
• Typteori har en enkel koppling till konstruktiv matematik genom BHK -tolkningen . Den kan kopplas till logik genom Curry -Howard -isomorfismen . Och vissa typteorier är nära kopplade till kategoriteori .

Valfria funktioner

Beroende typer

En beroende typ är en typ som är beroende av en term eller en annan typ. Således kan typen som returneras av en funktion bero på argumentet till funktionen.

Till exempel kan en lista med s med längd 4 vara en annan typ än en lista med s med längd 5. I en typteori med beroende typer är det möjligt att definiera en funktion som tar en parameter "n" och returnerar en lista som innehåller "n" nollor. Att kalla funktionen med 4 skulle ge en term med en annan typ än om funktionen skulle kallas med 5. ${\ displaystyle \ mathrm {nat}}$${\ displaystyle \ mathrm {nat}}$

Ett annat exempel är den typ som består av bevisen för att argumenttermen har en viss egenskap, till exempel termen typ, t.ex. ett givet naturligt tal, är primtal. Se Curry-Howard Correspondence . ${\ displaystyle \ mathrm {nat}}$

Beroende typer spelar en central roll i intuitionistisk typteori och i utformningen av funktionella programmeringsspråk som Idris , ATS , Agda och Epigram .

Jämställdhetstyper

Många system av typteori har en typ som representerar likhet mellan typer och termer. Denna typ skiljer sig från konvertibilitet och betecknas ofta som propositionell jämlikhet .

I intuitionistisk typteori är likhetstypen (även kallad identitetstyp) känd som identitet. Det finns en typ när är en typ och och är båda typtermer . En termtyp tolkas som en mening som är lika med . ${\ displaystyle I}$${\ displaystyle I \ A \ a \ b}$${\ displaystyle A}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle A}$${\ displaystyle I \ A \ a \ b}$${\ displaystyle a}$${\ displaystyle b}$

I praktiken är det möjligt att bygga en typ men det kommer inte att finnas någon term av den typen. I intuitionistisk typteori börjar nya jämlikhetsvillkor med reflexivitet. Om det är en typ av typ , så finns det en term av typ . Mer komplicerade likheter kan skapas genom att skapa en reflexiv term och sedan göra en minskning på ena sidan. Så om det är en typ av typ , så finns det en term av typ och, genom reduktion, generera en term av typ . I detta system anger alltså likhetstypen att två värden av samma typ kan konverteras genom reduktioner. ${\ displaystyle I \ \ mathrm {nat} \ 3 \ 4}$${\ displaystyle 3}$${\ displaystyle \ mathrm {nat}}$${\ displaystyle I \ \ mathrm {nat} \ 3 \ 3}$${\ displaystyle 2+1}$${\ displaystyle \ mathrm {nat}}$${\ displaystyle I \ \ mathrm {nat} \ (2+1) \ (2+1)}$${\ displaystyle I \ \ mathrm {nat} \ (2+1) \ 3}$

Att ha en typ för jämlikhet är viktigt eftersom det kan manipuleras inuti systemet. Det finns vanligtvis ingen dom att säga att två termer inte är lika; istället, som i tolkningen av Brouwer – Heyting – Kolmogorov , kartlägger vi till , var har bottentypen inga värden. Det finns en term med typ , men inte en typ . ${\ displaystyle \ neg (a = b)}$${\ displaystyle (a = b) \ to \ bot}$${\ displaystyle \ bot}$${\ displaystyle (I \ \ mathrm {nat} \ 3 \ 4) \ to \ bot}$${\ displaystyle (I \ \ mathrm {nat} \ 3 \ 3) \ to \ bot}$

Homotopytypsteori skiljer sig från intuitionistisk typteori mestadels genom att hantera likhetstypen.

Induktiva typer

Ett system med typteori kräver några grundläggande termer och typer för att fungera. Vissa system bygger dem ur funktioner med hjälp av kyrkans kodning . Andra system har induktiva typer : en uppsättning bastyper och en uppsättning typkonstruktörer som genererar typer med välskötta egenskaper. Till exempel garanteras vissa rekursiva funktioner som kallas induktiva typer.

Koinduktiva typer är oändliga datatyper som skapas genom att ge en funktion som genererar nästa element. Se Coinduction and Corecursion .

Induktionsinduktion är en funktion för att deklarera en induktiv typ och en typ av familj som beror på den induktiva typen.

Induktionsrekursion tillåter ett bredare utbud av välskötta typer, vilket gör att typen och rekursiva funktioner som fungerar på den kan definieras samtidigt.

Universum typer

Typer skapades för att förhindra paradoxer, till exempel Russells paradox . Motiven som leder till att dessa paradoxer - att kunna säga saker om alla typer - finns dock fortfarande. Så många typteorier har en "universustyp", som innehåller alla andra typer (och inte sig själv).

I system där du kanske vill säga något om universumtyper finns det en hierarki av universumtyper, var och en som innehåller den nedanför i hierarkin. Hierarkin definieras som oändlig, men uttalanden får endast hänvisa till ett begränsat antal universumnivåer.

Typuniversum är särskilt knepiga i typteorin. Det första förslaget om intuitionistisk typteori led av Girards paradox .

Beräkningskomponent

Många system av typteori, såsom den enkelt skrivna lambda-kalkylen , intuitionistisk typteori och konstruktionens kalkyl , är också programmeringsspråk. Det vill säga att de sägs ha en "beräkningskomponent". Beräkningen är minskningen av språkets termer med hjälp av omskrivningsregler .

Ett system av typteori som har en välskött beräkningskomponent har också en enkel koppling till konstruktiv matematik genom BHK-tolkningen .

Icke-konstruktiv matematik i dessa system är möjlig genom att lägga till operatörer på fortsättningar som samtal med aktuell fortsättning . Dessa operatörer tenderar emellertid att bryta efter önskvärda egenskaper såsom kanonicitet och parametricitet .

Skriv teorier

Större

• Helt enkelt skriven lambda-kalkyl som är en logik av högre ordning ;
• intuitionistisk typteori ;
• system F ;
• LF används ofta för att definiera andra typteorier;
• konstruktion och dess derivat.

Mindre

• Automath ;
• ST -typteori ;
• UTT (Luos enhetliga teori om beroende typer)
• några former av kombinatorisk logik ;
• andra definierade i lambda -kuben ;
• andra under namnet maskinskrivna lambda calculus ;
• andra under namnet ren typsystem .

Aktiva

• Homotopytypsteori undersöks.

Praktisk påverkan

Programmeringsspråk

Det finns omfattande överlappning och interaktion mellan områdena typteori och typsystem. Typsystem är ett programmeringsspråk som är avsett att identifiera buggar. Varje analys statiskt program , såsom den typ kontroll algoritmer i semantisk analys fasen av kompilatorn , har en anslutning till typ teori.

Ett bra exempel är Agda , ett programmeringsspråk som använder UTT (Luo's Unified Theory of afhængiga typer) för sitt typsystem. Programmeringsspråket ML utvecklades för att manipulera typteorier (se LCF ) och dess eget typsystem påverkades starkt av dem.

Matematiska grunder

Den första datorsäkra assistenten, kallad Automath , använde typteori för att koda matematik på en dator. Martin-Löf utvecklade specifikt intuitionistisk typteori för att koda all matematik för att fungera som en ny grund för matematik. Det pågår forskning om matematiska grundvalar som använder homotopytypsteori .

Matematiker som arbetar inom kategoriteori hade redan svårt att arbeta med den allmänt accepterade grunden för Zermelo - Fraenkel -teorin . Detta ledde till förslag som Lawvere's Elementary Theory of the Category of Sets (ETCS). Homotopi -teorin fortsätter i denna rad med typteori. Forskare undersöker samband mellan beroende typer (särskilt identitetstypen) och algebraisk topologi (specifikt homotopi ).

Bevisassistenter

Mycket av den aktuella forskningen kring typteori drivs av korrekturcheckare , interaktiva bevisassistenter och automatiska teoremprovers . De flesta av dessa system använder en typteori som den matematiska grunden för kodning av bevis, vilket inte är förvånande, med tanke på det nära sambandet mellan typteori och programmeringsspråk:

• LF används av Twelf , ofta för att definiera andra typteorier;
• många typteorier som faller under logik av högre ordning används av HOL-familjen av bevisare och PVS ;
• beräkningstypsteori används av NuPRL ;
• beräkning av konstruktioner och dess derivat används av Coq , Matita och Lean ;
• UTT (Luo's Unified Theory of afhængiga typer) används av Agda som är både ett programmeringsspråk och bevisassistent

Många typteorier stöds av LEGO och Isabelle . Isabelle stöder också stiftelser förutom typteorier, till exempel ZFC . Mizar är ett exempel på ett bevissystem som endast stöder uppsättningsteori.

Lingvistik

Typteori används också ofta i formella teorier om semantik i naturliga språk , särskilt Montague -grammatik och dess ättlingar. I synnerhet använder kategori grammatik och förgrupps grammatik i stor utsträckning typkonstruktörer för att definiera ord ( substantiv , verb , etc.) av ord.

Den vanligaste konstruktionen tar de grundläggande typerna och för individer respektive sanningsvärden , och definierar uppsättningen typer rekursivt enligt följande: ${\ displaystyle e}$${\ displaystyle t}$

• om och är typer, så är det ;${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ langle a, b \ rangle}$
• ingenting annat än grundtyperna, och det som kan konstrueras av dem med hjälp av föregående klausul är typer.

En komplex typ är typen av funktioner från entiteter av typ till enheter av typ . Således har man typer som tolkas som element i uppsättningen funktioner från enheter till sanning-värden, dvs indikatorfunktioner för uppsättningar av enheter. Ett uttryck för typ är en funktion från uppsättningar av enheter till sanning-värden, dvs en (indikatorfunktion för a) uppsättning uppsättningar. Den sistnämnda typen anses normalt vara kvantifierare av naturliga språk , som alla eller ingen ( Montague 1973, Barwise och Cooper 1981). ${\ displaystyle \ langle a, b \ rangle}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ langle e, t \ rangle}$${\ displaystyle \ langle \ langle e, t \ rangle, t \ rangle}$

Samhällsvetenskap

Gregory Bateson introducerade en teori om logiska typer i samhällsvetenskapen; hans föreställningar om dubbelbindning och logiska nivåer är baserade på Russells typteori.

Relation till kategoriteori

Även om den ursprungliga motivationen för kategoriteori var långt borta från grundläggande, visade sig de två fälten ha djupa förbindelser. Som John Lane Bell skriver: "Faktum är att kategorier själva kan betraktas som typteorier av ett visst slag; detta faktum indikerar ensam att typteori är mycket närmare släkt med kategoriteori än att sätta teori." I korthet kan en kategori ses som en typteori genom att betrakta dess objekt som typer (eller sorter), dvs "Grovt sett kan en kategori ses som en typteori avskuren sin syntax." Ett antal betydande resultat följer på detta sätt:

• kartesiska slutna kategorier motsvarar den typade λ-kalkylen ( Lambek , 1970);
• C-monoider (kategorier med produkter och exponentials och ett icke-terminal objekt) motsvarar den oskrivna λ-kalkylen (observerades oberoende av Lambek och Dana Scott runt 1980);
• lokalt kartesiska slutna kategorier motsvarar Martin-Löf-teorier (Seely, 1984).

Samspelet, känt som kategorisk logik , har varit föremål för aktiv forskning sedan dess; se exempelvis Jacobs monografi (1999).

Se även

• Datatyp för konkreta datatyper i programmering
• Domänteori
• Typ (modellteori)
• Typsystem för en mer praktisk diskussion av typsystem för programmeringsspråk
• Univalent stiftelser

Anteckningar

Referenser

Vidare läsning

externa länkar

• Robert L. Constable (red.). "Beräkningstypsteori" . Scholarpedia .
• TYPES Forum- modererat e-postforum med inriktning på typteori inom datavetenskap, verksamt sedan 1987.
• Nuprl -boken : " Introduktion till typteori. "
• Typer Projektföreläsningsanteckningar för sommarskolor 2005–2008
  • Sommarskolan 2005 har introduktionsföreläsningar
• Typteori i nLab , som har artiklar om många relaterade ämnen.
• Oregon programmeringsspråk Sommarskola , många föreläsningar och några anteckningar.
  • Sommar 2015 Typer, logik, semantik och verifiering