System F

System F ( polymorphic lambda calculus , system $\lambda 2$ , andra ordningens typad lambda calculus ) är ett maskinskrivet lambda-kalkylsystem som skiljer sig från ett enkelt maskinskrivet system genom närvaron av en universell kvantifieringsmekanism över typer. Detta system utvecklades 1972 av Jean-Yves Girard [1] i samband med bevisteori i logik. Oberoende av honom föreslogs ett liknande system 1974 av John Reynolds [2] . F-systemet låter dig formalisera begreppet parametrisk polymorfism i programmeringsspråk och fungerar som en teoretisk grund för sådana programmeringsspråk som Haskell och ML .

Systemet F tillåter konstruktion av termer beroende på typer. Tekniskt sett uppnås detta genom mekanismen att abstrahera en term för typ, vilket resulterar i en ny term. Traditionellt, för en sådan abstraktion, används den stora lambda-symbolen . Om vi till exempel tar en term av typ och abstraherar över en variabel av typ , får vi term . Denna term är en funktion från typer till termer. Genom att tillämpa denna funktion på olika typer får vi termer med identisk struktur men olika typer: $\lambda$ $\lambda x^{\alpha }.~x$ $\alpha \to \alpha$ $\alfa$ $\Lambda \alpha .~\lambda x^{\alpha }.~x$

(\Lambda \alpha .~\lambda x^{\alpha }.~x)~{\texttt {Bool}}\ \to _{\beta }\ \lambda x^{\texttt {Bool}} .~x

- typterm ;

{\texttt {Bool}}\to {\texttt {Bool}}

(\Lambda \alpha .~\lambda x^{\alpha }.~x)~{\texttt {Nat))\ \to _{\beta }\ \lambda x^{\texttt {Nat)) .~x

är en term av typ .

{\texttt {Nat}}\to {\texttt {Nat}}

Det kan ses att termen har polymorft beteende, det vill säga den definierar ett gemensamt gränssnitt för olika datatyper. I System F tilldelas denna term typen . Den universella kvantifieraren i en typ understryker möjligheten att ersätta en typvariabel med vilken giltig typ som helst. $\Lambda \alpha .~\lambda x^{\alpha }.~x$ $\forall \alpha .~\alpha \to \alpha$ $\alfa$

Formell beskrivning

Skriv syntax

Typerna av System F är konstruerade från en uppsättning typvariabler med hjälp av operatorerna och . Av tradition används grekiska bokstäver för typvariabler. Reglerna för att bilda typer är följande: $\till$ $\för alla$

( Typvariabel ) Om är en typvariabel, då är en typ; $\alfa$ $\alfa$
( Piltyp ) Om och är typer, då är en typ; $A$ $B$ $(A till B)$
( Generisk typ ) Om är en typvariabel och är en typ, då är en typ. $\alfa$ $B$ $(\forall \alpha .~B)$

Yttre parenteser utelämnas ofta, operatören anses vara högerassociativ och operatörens agerande fortsätter till höger så långt det är möjligt. Till exempel är standardförkortningen för . $\höger pil$ $\för alla$ $\forall \alpha .~\forall \beta .~\alpha \to \beta \to \alpha$ $(\forall \alpha .~(\forall \beta .~(\alpha \to (\beta \to \alpha ))))$

Syntax för termer

Termerna för System F är konstruerade från en uppsättning termvariabler ( , , etc.) enligt följande regler $x$ $y$ $z$

( Variabel ) Om är en variabel, då är en term; $x$ $x$
( Abstraktion ) Om är en variabel, är en typ och är en term, då är en term; $x$ $A$ $M$ $(\lambda x^{A}.~M)$
( Tillämpning ) Om och är termer, då är en term; $M$ $N$ $(M~N)$
( Universal Abstraction ) Om är en typvariabel och är en term, då är en term; $\alfa$ $M$ $(\Lambda \alpha .~M)$
( Universal Application ) Om är en term och är en typ, då är en term. $M$ $A$ $(M~A)$

Yttre parenteser utelämnas ofta, båda typerna av tillämpning anses vara vänsterassociativa, och abstraktionernas verkan anses fortsätta till höger så långt det är möjligt.

Det finns två versioner av det enkelt skrivna systemet. Om, som i reglerna ovan, termen variabler i lambdaabstraktionen är kommenterad med typer, så sägs systemet vara kyrkligt . Om abstraktionsregeln ersätts av

( Abstraktion enligt Curry ) Om är en variabel, och är en term, då är en term, $x$ $M$ $(\lambda x.~M)$

och kassera de två sista reglerna, då kallas systemet Curry-typat . Faktum är att villkoren för det Curry-typade systemet är desamma som i den otypade lambda-kalkylen.

Reduktionsregler

Förutom standarden -reduktionsregeln för lambdakalkyl $\beta$

(\lambda a^{A}.~M)~N\ \to _{\beta }\ M[a:=N]

Kyrkoliknande system F introducerar en ytterligare regel,

(\Lambda \alpha .~M)~A\ \to _{\beta }\ M[\alpha :=A]

gör det möjligt att beräkna tillämpningen av en term på en typ genom mekanismen för typsubstitution istället för en typvariabel.

Skrivkontexter och typpåstående

Kontexten, som i den enkelt skrivna lambdakalkylen , är en uppsättning påståenden om att tilldela typer till olika variabler, åtskilda med kommatecken

\Gamma =x_{1}\!:\!A_{1},x_{2}\!:\!A_{1},\ldots ,x_{n}\!:\!A_{n}

Du kan lägga till en variabel "fresh" för detta sammanhang till sammanhanget: om är ett giltigt sammanhang som inte innehåller variabeln och är en typ, så är det också ett giltigt sammanhang. $\Gamma$ $x$ $B$ $\Gamma ,x\!:\!B$

Den allmänna formen för ett skrivpåstående är:

\Gamma \vdash M\!:\!A

Detta lyder som följer: i sammanhanget har en term typ . $\Gamma$ $M$ $A$

Kyrkans skrivregler

I kyrkligt system F görs tilldelningen av typer till termer enligt följande regler:

( Initialregel ) Om en variabel finns med en typ i ett sammanhang , så har den en typ i det sammanhanget . I form av en slutledningsregel $x$ $A$ $\Gamma$ $x$ $A$

{\displaystyle {x\!:\!A\in \Gamma } \över {\Gamma \vdash x\!:\!A))

( Introduktionsregel $\höger pil$ ) Om termen i något sammanhang utökas med påståendet som har typ , har termen typ , så har lambdaabstraktionen i nämnda sammanhang (utan ) typ . I form av en slutledningsregel $a$ $A$ $M$ $B$ $a$ $\lambda a^{A}.~M$ $A till B$

{\Gamma ,a\!:\!A\vdash M\!:\!B} \över {\Gamma \vdash (\lambda a^{A}.~M)\!:\!(A \till B)}

( Removal regel $\höger pil$ ) Om en term i något sammanhang har en typ och en term har en typ , så har applikationen en typ . I form av en slutledningsregel $M$ $A till B$ $N$ $A$ $M~N$ $B$

{\Gamma \vdash M\!:\!(A\to B)\quad \Gamma \vdash N\!:\!A} \över {\Gamma \vdash (M~N)\!:\ !B}

( Introduktionsregel $\för alla$ ) Om en term i något sammanhang har en typ , så har termen i det sammanhanget en typ . I form av en slutledningsregel $M$ $A$ $\Lambda \alpha .~M$ $\forall \alpha .~A$

{\displaystyle {\Gamma \vdash M\!:\!A} \över {\Gamma \vdash (\Lambda \alpha .~M)\!:\!(\forall \alpha .~A)))

Den här regeln kräver en varning: en typvariabel får inte förekomma i kontextskrivningspåståenden . $\alfa$ $\Gamma$

( Borttagningsregel $\för alla$ ) Om en term i något sammanhang har typ , och är en typ, så har termen i detta sammanhang typ . I form av en slutledningsregel $M$ $\forall \alpha .~A$ $B$ $M~B$ $A[\alpha :=B]$

{\Gamma \vdash M\!:\!(\forall \alpha .~A)} \över {\Gamma \vdash (M~B)\!:\!(A[\alpha :=B] )}

Currys skrivregler

I Curry-typat System F görs tilldelningen av typer till termer enligt följande regler:

( Initialregel ) Om en variabel finns med en typ i ett sammanhang , så har den en typ i det sammanhanget . I form av en slutledningsregel $x$ $A$ $\Gamma$ $x$ $A$

{\displaystyle {x\!:\!A\in \Gamma } \över {\Gamma \vdash x\!:\!A))

{\Gamma ,a\!:\!A\vdash M\!:\!B} \över {\Gamma \vdash (\lambda a.~M)\!:\!(A\to B) }

( Removal regel $\höger pil$ ) Om en term i något sammanhang har en typ och en term har en typ , så har applikationen en typ . I form av en slutledningsregel $M$ $A till B$ $N$ $A$ $M~N$ $B$

{\Gamma \vdash M\!:\!(A\to B)\quad \Gamma \vdash N\!:\!A} \över {\Gamma \vdash (M~N)\!:\ !B}

( Introduktionsregel $\för alla$ ) Om en term i något sammanhang har en typ , så kan denna term i detta sammanhang också tilldelas en typ . I form av en slutledningsregel $M$ $A$ $M$ $\forall \alpha .~A$

{\displaystyle {\Gamma \vdash M\!:\!A} \över {\Gamma \vdash M\!:\!(\forall \alpha .~A)))

Den här regeln kräver en varning: en typvariabel får inte förekomma i kontextskrivningspåståenden . $\alfa$ $\Gamma$

( Borttagningsregel $\för alla$ ) Om en term i något sammanhang har typ , och är en typ, kan i detta sammanhang även denna term tilldelas typ . I form av en slutledningsregel $M$ $\forall \alpha .~A$ $B$ $M$ $A[\alpha :=B]$

{\displaystyle {\Gamma \vdash M\!:\!(\forall \alpha .~A)} \över {\Gamma \vdash M\!:\!(A[\alpha :=B])))

Exempel. Enligt den ursprungliga regeln:

x\!:\!(\forall \alpha .~\alpha \to \alpha )\vdash x\!:\!(\forall \alpha .~\alpha \to \alpha )

Låt oss tillämpa borttagningsregeln , ta som typen $\för alla$ $B$ $\forall \alpha .~\alpha \to \alpha$

x\!:\!(\forall \alpha .~\alpha \to \alpha )\vdash x\!:\!(\forall \alpha .~\alpha \to \alpha )\to (\forall \alpha .~\alpha \to \alpha )

Nu, enligt regeln om borttagning , har vi möjlighet att tillämpa termen på sig själv $\höger pil$ $x$

x\!:\!(\forall \alpha .~\alpha \to \alpha )\vdash (x~x)\!:\!(\forall \alpha .~\alpha \to \alpha )

och slutligen enligt introduktionsregeln $\höger pil$

\vdash (\lambda x.~x~x)\!:\!(\forall \alpha .~\alpha \to \alpha )\to (\forall \alpha .~\alpha \to \alpha )

Det här är ett exempel på en term som skrivs i System F, men inte i ett enkelt maskinskrivet system .

Representation av datatyper

System F är tillräckligt uttrycksfullt för att direkt implementera många av de datatyper som används i programmeringsspråk. Vi kommer att arbeta i kyrkans version av system F.

Tom typ. Sorts

\bot \ \equiv \ \forall \alpha .~\alpha

är obebodd i systemet F, det vill säga det finns inga termer med denna typ i det.

Enkel typ. Y typ

\top \ \equiv \ \forall \alpha .~\alpha \to \alpha

systemet F har en enda normalform invånare, term

{\mathtt {id}}\ \equiv \ \Lambda \alpha .~\lambda x^{\alpha }.~x

boolesk typ. I system F ges följande:

{\mathtt {Bool))\ \equiv \ \forall \alpha .~\alpha \to \alpha \to \alpha

Denna typ har exakt två invånare, identifierade med två booleska konstanter

{\mathtt {true))\ \equiv \ \Lambda \alpha .~\lambda x^{\alpha }.~\lambda y^{\alpha }.~x

{\mathtt {false))\ \equiv \ \Lambda \alpha .~\lambda x^{\alpha }.~\lambda y^{\alpha }.~y

Villkorlig operatörskonstruktion

{\mathtt {ifThenElse}}\ \equiv \ \Lambda \alpha .~\lambda b^{\mathtt {Bool)).~\lambda x^{\alpha }.~\lambda y^{\alpha }.~b\,\alpha \,x\,y

Denna funktion uppfyller de naturliga kraven

{\mathtt {ifThenElse}}\,A\,{\mathtt {true}}\,M\,N=M

och

{\mathtt {ifThenElse}}\,A\,{\mathtt {false}}\,M\,N=N

för en godtycklig typ och godtycklig och . Det är lätt att verifiera detta genom att utöka definitionerna och utföra -reduktioner. $A$ $M\!:\!A$ $N\!:\!A$ $\beta$

Typ av konstverk. För godtyckliga typer och typen av deras kartesiska produkt $A$ $B$

A\times B~\equiv ~\forall \alpha .~(A\to B\to \alpha )\to \alpha

bebos av ett par

\langle M;N\rangle ~\equiv ~\Lambda \alpha .~\lambda f^{(A\to B\to \alpha )}.~f~M~N

för varje och . Projektionerna av ett par ges av funktionerna $M\!:\!A$ $N\!:\!B$

{\mathtt {fst))\ \equiv \ \Lambda \alpha .~\Lambda \beta .~\lambda p^{\alpha \times \beta }.~p\,\alpha \,(\lambda x^{\alpha }.\,\lambda y^{\beta }.\,x)~:~\forall \alpha .~\forall \beta .\,\alpha \times \beta \to \alpha

{\mathtt {snd))\ \equiv \ \Lambda \alpha .~\Lambda \beta .~\lambda p^{\alpha \times \beta }.~p\,\beta \,(\lambda x^{\alpha }.\,\lambda y^{\beta }.\,y)~:~\forall \alpha .~\forall \beta .\,\alpha \times \beta \to \beta

Dessa funktioner uppfyller de naturliga kraven för och . ${\mathtt {fst}}\,A\,B\,\langle M;N\rangle =M$ ${\mathtt {snd}}\,A\,B\,\langle M;N\rangle =N$

Typ av belopp. För godtyckliga typer och typen av deras summa $A$ $B$

A+B~\equiv ~\forall \alpha .~(A\to \alpha )\to (B\to \alpha )\to \alpha

fylls med antingen en term av type , eller en term av typ , beroende på den tillämpade konstruktorn $A$ $B$

{\mathtt {injL}}\,M~\equiv ~\Lambda \alpha .\,\lambda f^{A\to \alpha }.\,\lambda g^{B\to \alpha }. \,f\,M

{\mathtt {injR}}\,N~\equiv ~\Lambda \alpha .\,\lambda f^{A\to \alpha }.\,\lambda g^{B\to \alpha }. \,g\,N

Här , . Funktionen som utför fallanalys (mönstermatchning) har formen $M\!:\!A$ $N\!:\!B$

{\mathtt {match}}~\equiv ~\Lambda \alpha .\,\Lambda \beta .\,\Lambda \gamma .\,\lambda s^{\alpha +\beta }.\,\ lambda f^{\alpha \to \gamma }.\,\lambda g^{\beta \to \gamma }.\,s\,\gamma \,f\,g~:~\forall \alpha .~\ forall \beta .~\forall \gamma .~\alpha +\beta \to (\alpha \to \gamma )\to (\beta \to \gamma )\to \gamma

Denna funktion uppfyller följande naturliga krav

{\mathtt {match}}\,A\,B\,C\,({\mathtt {injL}}\,M)\,F\,G=F\,M

och

{\mathtt {match}}\,A\,B\,C\,({\mathtt {injR}}\,N)\,F\,G=G\,N

för godtyckliga typer , och och godtyckliga termer och . $A$ $B$ $C$ $F\!:\!A\to C$ $G\!:\!B\to C$

Kyrkans nummer. Typ av naturliga tal i systemet F

{\mathtt {Nat))\ \equiv \ \forall \alpha .~\alpha \to (\alpha \to \alpha )\to \alpha

bebos av ett oändligt antal olika element, erhållna genom två konstruktörer och : ${\mathtt {noll}}\!:\!{\mathtt {Nat}}$ ${\mathtt {succ}}\!:\!{\mathtt {Nat}}\to {\mathtt {Nat}}$

{\mathtt {noll))\ \equiv \ \Lambda \alpha .\,\lambda z^{\alpha }.\,\lambda s^{\alpha \to \alpha }.\,z

{\mathtt {succ}}\ \equiv \ \lambda n^{\mathtt {Nat)).\,\Lambda \alpha .\,\lambda z^{\alpha }.\,\lambda s^ {\alpha \to \alpha }.\,s\,(n\,\alpha \,z\,s)

Ett naturligt tal kan erhållas genom att tillämpa den andra konstruktorn - gånger på den första, eller på motsvarande sätt representeras av en term $n$ $n$

{\overline {n))\ \equiv \ \Lambda \alpha .\,\lambda z^{\alpha }.\,\lambda s^{\alpha \rightarrow \alpha }.\,\underbrace { s(s(s\ldots (s} _{n}\,z)\ldots ))

Egenskaper

Ett enkelt maskinskrivet system har egenskapen typsäkerhet: underreduktioner, typen av lambdatermen förblir oförändrad och själva skrivningen stör inte beräkningarnas framsteg. $\beta$

I sin avhandling visade Jean-Yves Girard [1] att System F har den starka normaliseringsegenskapen: vilken som helst tillåten term kan reduceras till en unik normalform efter ett ändligt antal -reduktioner. $\beta$

F-systemet är ett impredikativt system, eftersom typvariabeln som är associerad med den universella kvantifieraren när en generisk typ definieras kan ersättas av objektet som definieras själv. Till exempel kan en enskild typterm appliceras på sin egen typ, vilket ger en term av typ . Som Joe Wells visade 1994 [3] är problemet med typinferens för Currys version av System F olösligt. Därför, i den praktiska implementeringen av programmeringsspråk, används vanligtvis begränsade, predikativa versioner av polymorfism: prenex polymorfism ( ML style polymorphism ), rank 2 polymorphism , etc. När det gäller prenex-polymorfism är omfattningen av typvariabler endast typer utan kvantifierare. I dessa system är problemet med typinferens lösbart, sådan slutledning är baserad på Hindley-Milner-algoritmen . ${\texttt {id}}$ $\top \equiv \forall \alpha .~\alpha \to \alpha$ $\top \to \top$

Curry-Howard-korrespondensen länkar System F till minimal andra ordningens intuitionistisk propositionslogik konstruerade från propositionella variabler genom implikation och universell propositionell kvantifiering I det här fallet kan värdena (true), (false), connectives (negation), (konjunktion) och (disjunktion), samt (existenskvantifierare) definieras enligt följande $\topp$ $\bot$ $\linte$ $\landa$ $\lor$ $\existerar$

\top ~\equiv ~\forall \alpha .\,\alpha \to \alpha

\bot ~\equiv ~\forall \alpha .\,\alpha

\lnot A~\equiv ~A\to \bot

A\land B~\equiv ~\forall \alpha .\,(A\to B\to \alpha )\to \alpha

A\lor B~\equiv ~\forall \alpha .\,(A\to \alpha )\to (B\to \alpha )\to \alpha

\exists \alpha .\,M[\alpha ]~\equiv ~\forall \gamma .\,(\forall \alpha .\,M[\alpha ]\to \gamma )\to \gamma

Observera att Curry-Howard-korrespondensen tilldelar sant en enskild typ, false en tom typ, konjunktioner en produkt av typer och disjunktioner en summa av dem.

Anteckningar

↑ 1 2 Girard, Jean-Yves. Tolkning fonctionnelle et elimination des coupures de l'arithmétique d'ordre supérieur : Ph.D. avhandling. — Université Paris 7, 1972.
↑ John C. Reynolds. Mot en teori om typstruktur . - 1974. Arkiverad 31 oktober 2014.
↑ Wells JB Typbarhet och typkontroll i andra ordningens lambda-kalkyl är likvärdiga och obestämbara // Proceedings of the 9th Annual IEEE Symposium on Logic in Computer Science (LICS). - 1994. - S. 176-185 . Arkiverad från originalet den 22 februari 2007.

Litteratur

Pierce, Benjamin C. Typer och programmeringsspråk. - MIT Press , 2002. - ISBN 0-262-16209-1 .
- Översättning till ryska: Pierce B. Typer i programmeringsspråk. - Dobrosvet , 2012. - 680 sid. — ISBN 978-5-7913-0082-9 .
Barendregt, Henk. Lambda Calculi med typer // Handbook of Logic in Computer Science. - Oxford University Press, 1992. - Vol. II . - S. 117-309 .
Jean-Yves Girard, Paul Taylor, Yves Lafont. Bevis och typer . - Cambridge University Press , 1989. - ISBN 0 521 37181 3 .