F rendszer - System F

Az F rendszer , más néven ( Girard – Reynolds ) polimorf lambda-számítás vagy másodrendű lambda-számítás , egy gépelt lambda-számítás, amely a típusok közötti univerzális számszerűsítési mechanizmus bevezetésével különbözik az egyszerűen begépelt lambda-számítástól . Az F rendszer tehát a programozási nyelvekben formalizálja a parametrikus polimorfizmus fogalmát , és elméleti alapot képez az olyan nyelvekhez, mint a Haskell és az ML . Az F rendszert önállóan Jean-Yves Girard (1972) logikus és John C. Reynolds (1974) informatikus fedezte fel .

Míg az egyszerűen begépelt lambda calculus változók változnak a kifejezéseken és kötőanyagokon keresztül, addig az F rendszer emellett típusonként változó változókkal és kötőanyagokkal rendelkezik. Például azt a tényt, hogy az identitásfüggvény bármilyen típusú A → A alakú lehet, az F rendszerben formalizálják ítéletként.

${\ displaystyle \ vdash \ Lambda \ alpha. \ lambda x^{\ alpha} .x: \ forall \ alpha. \ alpha \ to \ alpha}$

ahol egy típusváltozó található . A nagybetűket hagyományosan a típusszintű függvények jelölésére használják, szemben a kisbetűvel, amelyet az értékszintű funkciókhoz használnak. (A felülírott azt jelenti, hogy a kötött x típus ; a kettőspont utáni kifejezés az előtte lévő lambda kifejezés típusa.) ${\ displaystyle \ alpha}$${\ displaystyle \ Lambda}$${\ displaystyle \ lambda}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$

Mint kifejezés átíró rendszer , az F rendszer erősen normalizálódik . A típuskövetkeztetés azonban az F rendszerben (explicit típusjegyzetek nélkül) nem eldönthető. A Curry – Howard izomorfizmus szerint az F rendszer a másodrendű intuíciós logika azon töredékének felel meg , amely csak egyetemes számszerűsítést alkalmaz. Az F rendszer a lambda -kocka részének tekinthető, még kifejezőbb típusú lambda -kalkulákkal együtt, beleértve a függő típusokat is .

Girard szerint az F rendszer "F" -ét véletlenül választották ki.

Gépelési szabályok

Az F rendszer gépelési szabályai az egyszerűen begépelt lambda -számítás szabályai, a következőkkel kiegészítve:

${\ displaystyle {\ frac {\ Gamma \ vdash M {\ mathbin {:}} \ forall \ alpha. \ sigma} {\ Gamma \ vdash M \ tau {\ mathbin {:}} \ sigma [\ tau /\ alpha ]}}}$ (1)

${\ displaystyle {\ frac {\ Gamma, \ alpha ~ {\ text {type}} \ vdash M {\ mathbin {:}} \ sigma} {\ Gamma \ vdash \ Lambda \ alpha .M {\ mathbin {:} } \ teljes \ alfa. \ szigma}}}$ (2)

ahol a típusok, egy típusváltozó, és a kontextusban azt jelzi, hogy kötött. Az első szabály az alkalmazás, a második az absztrakció szabálya. ${\ displaystyle \ sigma, \ tau}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha ~ {\ text {type}}}$${\ displaystyle \ alpha}$

Logika és predikátumok

A típus meghatározása:, ahol egy típusváltozó . Ez azt jelenti: minden olyan függvény típusa, amely bemenetként egy α típust és két α típusú kifejezést vesz fel, és kimenetként egy α típusú kifejezést állít elő (vegye figyelembe , hogy jobb asszociatívnak tekintjük .) ${\ displaystyle {\ mathsf {Boolean}}}$${\ displaystyle \ forall \ alpha. \ alfa \ to \ alpha \ to \ alpha}$${\ displaystyle \ alpha}$${\ displaystyle {\ mathsf {Boolean}}}$${\ displaystyle \ to}$

A következő két meghatározásokat logikai értékeket és használják, kiterjesztve a meghatározása Church logikai értékek : ${\ displaystyle \ mathbf {T}}$${\ displaystyle \ mathbf {F}}$

${\ displaystyle \ mathbf {T} = \ Lambda \ alfa {.} \ lambda x^{\ alfa} \ lambda y^{\ alfa} {.} x}$

${\ displaystyle \ mathbf {F} = \ Lambda \ alfa {.} \ lambda x^{\ alfa} \ lambda y^{\ alfa} {.} y}$

(Vegye figyelembe, hogy a fenti két függvény három - nem kettő - argumentumot igényel . Az utóbbi kettőnek lambda kifejezésnek kell lennie, de az elsőnek típusnak. Ezt a tényt tükrözi az a tény is, hogy ezeknek a kifejezéseknek a típusa ; az univerzális mennyiségi mutató kötődését az α megfelel a Λ kötődését az alfa a lambda expressziós magát. Fontos megjegyezni, hogy egy kényelmes rövidítése , de ez nem egy szimbólum a F-rendszer, hanem inkább egy „meta-szimbólum”. Hasonlóképpen, és vannak az F rendszer "szerelvényeinek" "meta-szimbólumai", kényelmes gyorsírása ( Bourbaki-értelemben ); máskülönben, ha az ilyen funkciókat meg lehetne nevezni (az F rendszeren belül), akkor nem lenne szükség a lambda-kifejező készülékre a függvények névtelen meghatározásához és a rögzített pont kombinátorhoz , amely e korlátozás körül jár.) ${\ displaystyle \ forall \ alpha. \ alfa \ to \ alpha \ to \ alpha}$${\ displaystyle {\ mathsf {Boolean}}}$${\ displaystyle \ forall \ alpha. \ alfa \ to \ alpha \ to \ alpha}$${\ displaystyle \ mathbf {T}}$${\ displaystyle \ mathbf {F}}$

Ezután ezekkel a két feltételekkel definiálhatunk néhány logikai operátort (amelyek típusai ): ${\ displaystyle \ lambda}$${\ displaystyle {\ mathsf {Boolean}} \ rightarrow {\ mathsf {Boolean}} \ rightarrow {\ mathsf {Boolean}}}$

${\ displaystyle {\ begin {aligned} \ mathrm {AND} & = \ lambda x^{\ mathsf {Boolean}} \ lambda y^{\ mathsf {Boolean}} {.} x \, {\ mathsf {Boolean} } \, y \, \ mathbf {F} \\\ mathrm {OR} & = \ lambda x^{\ mathsf {Boolean}} \ lambda y^{\ mathsf {Boolean}} {.} x \, {\ mathsf {Boolean}} \, \ mathbf {T} \, y \\\ mathrm {NOT} & = \ lambda x^{\ mathsf {Boolean}} {.} x \, {\ mathsf {Boolean}} \, \ mathbf {F} \, \ mathbf {T} \ end {aligned}}}$

Ne feledje, hogy a fenti definíciókban egy típus argumentum , amely megadja, hogy a megadott másik két paraméter típus . Az egyházi kódolásokhoz hasonlóan nincs szükség IFTHENELSE függvényre, mivel csak nyers típusú kifejezéseket lehet használni döntési függvényként. Ha azonban egyet kérnek: ${\ displaystyle {\ mathsf {Boolean}}}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle {\ mathsf {Boolean}}}$${\ displaystyle {\ mathsf {Boolean}}}$

${\ displaystyle \ mathrm {IFTHENELSE} = \ Lambda \ alpha. \ lambda x^{\ mathsf {Boolean}} \ lambda y^{\ alpha} \ lambda z^{\ alpha} .x \ alpha yz}$

megteszi. A predikátum olyan függvény, amely egy -típusú értéket ad vissza . A legalapvetőbb predikátum az ISZERO, amely akkor és csak akkor tér vissza, ha az argumentuma a 0 egyházi szám : ${\ displaystyle {\ mathsf {Boolean}}}$${\ displaystyle \ mathbf {T}}$

${\ displaystyle \ mathrm {ISZERO} = \ lambda n^{\ forall \ alpha. (\ alpha \ rightarrow \ alpha) \ rightarrow \ alpha \ rightarrow \ alpha} {.} n \, {\ mathsf {Boolean}} \ , (\ lambda x^{\ mathsf {Boolean}} {.} \ mathbf {F}) \, \ mathbf {T}}$

F rendszer struktúrái

Az F rendszer lehetővé teszi a rekurzív konstrukciók természetes módon történő beágyazását, ami Martin-Löf típuselméletéhez kapcsolódik . Az absztrakt struktúrákat (S) konstruktorok segítségével hozzák létre . Ezek a következőképpen beírt funkciók:

${\ displaystyle K_ {1} \ rightarrow K_ {2} \ rightarrow \ dots \ rightarrow S}$.

A rekurzivitás akkor nyilvánul meg, ha maga megjelenik az egyik típuson belül . Ha rendelkezik ilyen konstruktorokkal, akkor megadhatja a típusát : ${\ displaystyle S}$${\ displaystyle K_ {i}}$${\ displaystyle m}$${\ displaystyle S}$

${\ displaystyle \ forall \ alpha. (K_ {1}^{1} [\ alpha /S] \ rightarrow \ dots \ rightarrow \ alpha) \ dots \ rightarrow (K_ {1}^{m} [\ alpha /S ] \ rightarrow \ dots \ rightarrow \ alpha) \ rightarrow \ alpha}$

Például a természetes számok induktív adattípusként definiálhatók a konstruktorokkal ${\ displaystyle N}$

${\ displaystyle {\ mathit {zero}}: \ mathrm {N}}$

${\ displaystyle {\ mathit {succ}}: \ mathrm {N} \ rightarrow \ mathrm {N}}$

Az ennek a struktúrának megfelelő System F típus az . Az ilyen típusú kifejezések az egyházi számok gépelt változatát tartalmazzák , amelyek közül az első néhány: ${\ displaystyle \ forall \ alpha. \ alfa \ to (\ alpha \ to \ alpha) \ to \ alpha}$

{{{1}}}${\ displaystyle \ Lambda \ alpha. \ lambda x^{\ alpha}. \ lambda f^{\ alfa \ to \ alpha} .x}$

{{{1}}}${\ displaystyle \ Lambda \ alpha. \ lambda x^{\ alpha}. \ lambda f^{\ alfa \ to \ alpha} .fx}$

{{{1}}}${\ displaystyle \ Lambda \ alpha. \ lambda x^{\ alpha}. \ lambda f^{\ alfa \ to \ alpha} .f (fx)}$

{{{1}}}${\ displaystyle \ Lambda \ alpha. \ lambda x^{\ alpha}. \ lambda f^{\ alfa \ to \ alpha} .f (f (fx))}}$

Ha fordított sorrendben a currys érvek ( pl ), akkor az egyház számértékek egy olyan funkció, hogy vesz egy függvény f paraméterként, és visszatér a ^th ereje f . Ez azt jelenti, hogy az egyházi szám magasabb rendű függvény- egy f argumentumú függvényt vesz fel , és egy másik egyetlen argumentum függvényt ad vissza. ${\ displaystyle \ forall \ alpha. (\ alpha \ rightarrow \ alpha) \ rightarrow \ alpha \ rightarrow \ alpha}$${\ displaystyle n}$${\ displaystyle n}$

Használja programozási nyelveken

Az F rendszer ebben a cikkben használt változata kifejezetten gépelt vagy egyházi stílusú számítás. A λ-kifejezésekben található gépelési információk egyszerűvé teszik a típusellenőrzést . Joe Wells (1994) megoldotta a "kínos nyitott problémát" azzal, hogy bebizonyította, hogy a típusellenőrzés eldönthetetlen az F rendszer Curry-stílusú változatánál, vagyis olyannál, amely nem tartalmaz kifejezett gépelési megjegyzéseket.

Wells eredmény arra utal, hogy típusú következtető System F lehetetlen. Az F rendszer „ Hindley – Milner ”, vagy egyszerűen „HM” néven ismert korlátozása egyszerű típusú következtetési algoritmussal rendelkezik, és sok statikusan beírt funkcionális programozási nyelvhez, például a Haskell 98 -hoz és az ML családhoz használatos. Az idő múlásával, ahogy nyilvánvalóvá váltak a HM-típusú rendszerek korlátozásai, a nyelvek folyamatosan a kifejezőbb logika felé fordultak a típusrendszereikhez. A GHC Haskell fordító, túlmutat a HM-en (2008-tól), és nem szintaktikai típusú egyenlőséggel bővített F rendszert használ; az OCaml típusú rendszer nem HM szolgáltatásai közé tartozik a GADT .

A Girard-Reynolds izomorfizmus

A másodrendű intuíciós logika szerint a másodrendű polimorf lambda-számítást (F2) Girard (1972) és függetlenül Reynolds (1974) fedezte fel. Girard bebizonyította az ábrázolási tételt : hogy a másodrendű intuíciós predikátumlogikában (P2) a természetes számoktól kezdve a teljesnek bizonyítható természetes számok függvényei vetületet képeznek a P2-ből az F2-be. Reynolds bebizonyította az absztrakciós tételt : az F2 minden tagja kielégít egy logikai relációt, amely beágyazható a P2 logikai összefüggésekbe. Reynolds bebizonyította, hogy egy Girard-vetület, majd egy Reynolds-beágyazás képezi az identitást, azaz a Girard-Reynolds-izomorfizmust .

F rendszer _ω

Míg F-rendszer megfelel az első tengelyére Barendregt a lambda kocka , F-rendszer _ω vagy a magasabb rendű polimorf lambda kalkulus ötvözi az első tengely (polimorfizmus) a második tengely ( típus szereplők ); ez egy más, összetettebb rendszer.

F-rendszer _ω lehet meghatározni induktív egy család rendszerek, ahol a pályára alapul féle megengedett az egyes rendszerekben:

• ${\ displaystyle F_ {n}}$ engedély típusok:
  • ${\ displaystyle \ star}$ (a típusok) és
  • ${\ displaystyle J \ Rightarrow K}$hol és (a függvények típusa típusról típusra, ahol az argumentum típusa alacsonyabb rendű)${\ displaystyle J \ in F_ {n-1}}$${\ displaystyle K \ in F_ {n}}$

A limit, tudjuk meg a rendszer , hogy ${\ displaystyle F _ {\ omega}}$

• ${\ displaystyle F _ {\ omega} = {\ underet {1 \ leq i} {\ bigcup}} F_ {i}}$

Azaz F _ω az a rendszer, amely lehetővé teszi a függvényeket típusoktól típusokig, ahol az argumentum (és az eredmény) bármilyen sorrendű lehet.

Vegye figyelembe, hogy bár az F _ω nem korlátozza az argumentumok sorrendjét ezekben a leképezésekben, korlátozza az ezekhez tartozó leképezésekhez tartozó érvek univerzumát : ezeknek inkább típusoknak kell lenniük, mint értékeknek. Az F _ω rendszer nem engedélyezi az értékek típusok ( függő típusok ) leképezését, de lehetővé teszi az értékekről az értékekre való leképezést ( absztrakció), a leképezést a típusokról az értékekre ( absztrakció) és a leképezéseket típusokról típusokra ( absztrakció típusok szintjén) ) ${\ displaystyle \ lambda}$${\ displaystyle \ Lambda}$${\ displaystyle \ lambda}$

Lásd még

• Egzisztenciális típusok - az univerzális típusok egzisztenciálisan számszerűsített megfelelői
• F rendszer _<: - kiterjeszti az F rendszert altípusokkal
• U rendszer

Megjegyzések

Hivatkozások

További irodalom

• Pierce, Benjamin (2002). "V polimorfizmus 23. fejezet. Univerzális típusok, 25. fejezet. Az F rendszer ML megvalósítása" . Típusok és programozási nyelvek . MIT Nyomja meg. 339–362., 381–388. ISBN 0-262-16209-1.

Külső linkek

• Franck Binard F rendszer összefoglalója .
• F-rendszer _co : igásló modern fordítóprogramok által Greg Morrisett