Egyszerűen beírt lambda számítás - Simply typed lambda calculus

Az egyszerűen gépelt lambda-kalkulus ( ), egyfajta típusú elmélet , egy gépelt értelmezése a lambda-kalkulus egyetlen típus kivitelező ( ), amely épít a funkció típusok . Ez a gépelt lambda -számítás kanonikus és legegyszerűbb példája. Az egyszerűen beírt lambda -kalkulust eredetileg Alonzo Church vezette be 1940 -ben, hogy elkerülje a tipizálatlan lambda -számítás paradox használatát , és sok kívánatos és érdekes tulajdonsággal rendelkezik. ${\ displaystyle \ lambda ^{\}}}$${\ displaystyle \ to}$

Az egyszerű típus kifejezés az egyszerűen begépelt lambda -számítás kiterjesztéseire is vonatkozik, mint például termékek , társtermékek vagy természetes számok ( T rendszer ), vagy akár teljes rekurzió (például PCF ). Ezzel szemben a polimorf típusokat (például F rendszer ) vagy függő típusokat (például a logikai keretrendszert ) bevezető rendszereket nem tekintik egyszerűen gépeltnek . Az előbbi a teljes rekurzió kivételével még mindig egyszerűnek tekinthető, mert az ilyen struktúrák egyházi kódolása csak és megfelelő típusú változók felhasználásával végezhető el , míg a polimorfizmus és a függőség nem. ${\ displaystyle \ to}$

Szintaxis

Ebben a cikkben a típusokat használjuk és soroljuk. Informálisan a függvénytípus azokra a függvénytípusokra utal, amelyek adott típusú bemenet alapján típus típusú kimenetet eredményeznek . Megegyezés alapján, a társult jobbra: olvasunk , mint . ${\ displaystyle \ sigma}$${\ displaystyle \ tau}$ ${\ displaystyle \ sigma \ to \ tau}$${\ displaystyle \ sigma}$${\ displaystyle \ tau}$${\ displaystyle \ to}$${\ displaystyle \ sigma \ to \ tau \ to \ rho}$${\ displaystyle \ sigma \ to (\ tau \ to \ rho)}$

Ahhoz, hogy határozza meg az egyes, kezdjük rögzítésével egy sor bázis típusú , . Ezek néha atomi típusok vagy típusú állandók . Javítva, a típusok szintaxisa a következő: ${\ displaystyle B}$

${\ displaystyle \ tau :: = \ tau \ to \ tau \ mid T \ quad \ mathrm {where} \ quad T \ in B}$.

Például generál egy végtelen típusú halmazt, kezdve ezzel${\ displaystyle B = \ {a, b \}}$${\ displaystyle a, b,}$${\ displaystyle a \ a,}$${\ displaystyle a \ b, b \ b,}$${\ displaystyle b \ to a,}$${\ displaystyle a \ to (a \ to a), \ ldots,}$${\ displaystyle (b \ a) \ \ (a \ b), \ ldots}$

Ezenkívül rögzítünk egy konstanskészletet az alaptípusokhoz. Például feltételezhetjük a nat alaptípust , és az állandók kifejezések lehetnek a természetes számok. Az eredeti prezentációban Church csak két alaptípust használt: "az állítások típusához" és "az egyének típusához". A típusnak nincsenek konstansai, míg van egy terminál állandója. Gyakran a csak egy alaptípussal rendelkező számítást veszik figyelembe. ${\ displaystyle o}$${\ displaystyle \ iota}$${\ displaystyle o}$${\ displaystyle \ iota}$${\ displaystyle o}$

Az egyszerűen beírt lambda -számítás szintaxisa lényegében maga a lambda -számítás. Azért írunk, hogy jelezzük, hogy a változó típusa . A szintaxis kifejezés a BNF -ben a következő: ${\ displaystyle x {\ mathbin {:}} \ tau}$${\ displaystyle x}$${\ displaystyle \ tau}$

${\ displaystyle e :: = x \ mid \ lambda x {\ mathbin {:}} \ tau .e \ mid e \, e \ mid c}$

ahol egy kifejezés állandó. ${\ displaystyle c}$

Vagyis változó hivatkozás , absztrakciók , alkalmazás és állandó . A változó referencia van kötve , ha benne van egy absztrakció kötődését . A kifejezés lezárult, ha nincsenek kötetlen változók. ${\ displaystyle x}$${\ displaystyle x}$

Hasonlítsa össze ezt a tipizálatlan lambda -számítás szintaxisával:

${\ displaystyle e :: = x \ mid \ lambda xe \ mid e \, e}$

Látjuk, hogy a begépelt lambda számításban minden függvénynek ( absztrakciónak ) meg kell adnia az argumentum típusát.

Gépelési szabályok

Az adott típusú jól begépelt lambda kifejezések halmazának meghatározásához definiálunk egy gépelési összefüggést a kifejezések és típusok között. Először bemutatjuk a gépelési kontextusokat vagy a gépelési környezeteket , amelyek gépelési feltételezések halmazai. A gépelési feltételezésnek formája van , a jelentésnek típusa . ${\ displaystyle \ Gamma, \ Delta, \ dots}$${\ displaystyle x {\ mathbin {:}} \ sigma}$${\ displaystyle x}$${\ displaystyle \ sigma}$

A gépelési reláció azt jelzi, hogy ez egy típusú kifejezés a kontextusban . Ebben az esetben azt mondják, hogy jól gépelt (típusa van ). A gépelési reláció példányait gépelési ítéleteknek nevezzük . A gépelési ítélet érvényességét egy gépelési levezetés biztosítja , amelyet gépelési szabályok alkalmazásával állítanak elő (ahol a vonal feletti premisszák lehetővé teszik számunkra, hogy levonjuk a vonal alatti következtetést). Az egyszerűen beírt lambda-számítás a következő szabályokat használja: ${\ displaystyle \ Gamma \ vdash e {\ mathbin {:}} \ sigma}$${\ displaystyle e}$${\ displaystyle \ sigma}$${\ displaystyle \ Gamma}$${\ displaystyle e}$${\ displaystyle \ sigma}$

${\ displaystyle {\ frac {x {\ mathbin {:}} \ sigma \ in \ Gamma} {\ Gamma \ vdash x {\ mathbin {:}} \ sigma}}}$ (1)	$A {\ displaystyle {\ frac {c {\ text {típusú konstans}} T} {\ Gamma \ vdash c {\ mathbin {:}} T}}}$ (2)
${\ displaystyle {\ frac {\ Gamma, x {\ mathbin {:}} \ sigma \ vdash e {\ mathbin {:}} \ tau} {\ Gamma \ vdash (\ lambda x {\ mathbin {:}} \ szigma. ~ e) {\ mathbin {:}} (\ sigma \ to \ tau)}}}$ (3)	${\ displaystyle {\ frac {\ Gamma \ vdash e_ {1} {\ mathbin {:}} \ sigma \ to \ tau \ quad \ Gamma \ vdash e_ {2} {\ mathbin {:}} \ sigma} {\ Gamma \ vdash e_ {1} ~ e_ {2} {\ mathbin {:}} \ tau}}}$ (4)

Szavakban,

1. Ha van szöveg a szövegkörnyezetben, tudjuk, hogy típusa van .${\ displaystyle x}$${\ displaystyle \ sigma}$${\ displaystyle x}$${\ displaystyle \ sigma}$
2. A terminálállandók megfelelő alaptípusokkal rendelkeznek.
3. Ha egy adott kontextusban, amelynek típusa van , van típusa , akkor ugyanabban a kontextusban anélkül , hogy típusa van .${\ displaystyle x}$${\ displaystyle \ sigma}$${\ displaystyle e}$${\ displaystyle \ tau}$${\ displaystyle x}$${\ displaystyle \ lambda x {\ mathbin {:}} \ sigma. ~ e}$${\ displaystyle \ sigma \ to \ tau}$
4. Ha egy adott kontextusban van típusa és típusa , akkor van típusa .${\ displaystyle e_ {1}}$${\ displaystyle \ sigma \ to \ tau}$${\ displaystyle e_ {2}}$${\ displaystyle \ sigma}$${\ displaystyle e_ {1} ~ e_ {2}}$${\ displaystyle \ tau}$

Példák a zárt kifejezésekre, azaz az üres kontextusban tipizálható kifejezésekre:

• Minden típushoz egy kifejezés (identitásfüggvény/I-kombinátor),${\ displaystyle \ tau}$${\ displaystyle \ lambda x {\ mathbin {:}} \ tau .x {\ mathbin {:}} \ tau \ to \ tau}$
• A típusoknál egy kifejezés (a K-kombinátor), és${\ displaystyle \ sigma, \ tau}$${\ displaystyle \ lambda x {\ mathbin {:}} \ sigma. \ lambda y {\ mathbin {:}} \ tau .x {\ mathbin {:}} \ sigma \ to \ tau \ to \ sigma}$
• A típusoknál egy kifejezés (az S-kombinátor).${\ displaystyle \ tau, \ tau ', \ tau' '}$${\ displaystyle \ lambda x {\ mathbin {:}} \ tau \ to \ tau '\ to \ tau' '. \ lambda y {\ mathbin {:}} \ tau \ to \ tau'. \ lambda z {\ mathbin {:}} \ tau .xz (yz): (\ tau \ to \ tau '\ to \ tau' ') \ to (\ tau \ to \ tau') \ to \ tau \ to \ tau ''}$

Ezek a kombinált logika alapkombinátorainak gépelt lambda -számításai .

Minden típushoz rendelés, szám tartozik . Alaptípusokhoz ,; függvény típusok . Vagyis egy típus sorrendje méri a leginkább balra ágyazott nyíl mélységét. Ennélfogva: ${\ displaystyle \ tau}$${\ displaystyle o (\ tau)}$${\ displaystyle o (T) = 0}$${\ displaystyle o (\ sigma \ to \ tau) = {\ mbox {max}} (o (\ sigma)+1, o (\ tau))}$

${\ displaystyle o (\ iota \ to \ iota \ to \ iota) = 1}$

${\ displaystyle o ((\ iota \ to \ iota) \ to \ iota) = 2}$

Szemantika

Belső és külső értelmezések

Általánosságban elmondható, hogy az egyszerűen begépelt lambda -számításnak két különböző módja van a jelentés hozzárendelésének, mint a gépelt nyelveknek általánosságban, amelyeket néha belső vagy külső vagy egyházi stílusú vagy Curry -stílusnak neveznek . A belső/egyházi stílusú szemantika csak a jól begépelt kifejezésekhez rendel jelentést, pontosabban, közvetlenül a gépelési levezetésekhez. Ennek az a hatása, hogy a csak típusjegyzetekben eltérő kifejezéseknek mindazonáltal különböző jelentései lehetnek. Például az egész számok azonossági kifejezése és a logikai kifejezések esetében az identitás kifejezés különböző dolgokat jelenthet. (A klasszikus szándékolt értelmezések az identitásfüggvény egész számokon és az azonosságfüggvény a logikai értékeken.) Ezzel szemben egy külső/Curry-stílusú szemantika a gépeléstől függetlenül jelentést ad a kifejezéseknek, mivel azokat gépelés nélküli nyelven értelmezik. Ebben a nézetben, és ugyanazt jelenti ( azaz ugyanazt, amit ). ${\ displaystyle \ lambda x {\ mathbin {:}} {\ mathtt {int}}. ~ x}$${\ displaystyle \ lambda x {\ mathbin {:}} {\ mathtt {bool}}. ~ x}$${\ displaystyle \ lambda x {\ mathbin {:}} {\ mathtt {int}}. ~ x}$${\ displaystyle \ lambda x {\ mathbin {:}} {\ mathtt {bool}}. ~ x}$${\ displaystyle \ lambda x. ~ x}$

A belső és külső szemantika megkülönböztetése néha a lambda -absztrakciókhoz fűzött megjegyzések jelenlétével vagy hiányával függ össze, de szigorúan véve ez a használat pontatlan. Lehetséges a Curry-stílusú szemantika meghatározása megjegyzésekkel ellátott kifejezésekkel egyszerűen a típusok figyelmen kívül hagyásával ( azaz a típus törlésével ), mivel lehetséges egyházi stílusú szemantikát adni megjegyzés nélküli kifejezésekre, amikor a típusok a kontextusból levezethetők ( pl. , típus -következtetéseken keresztül ). A lényegi különbség az intrinzik és az extrinsic megközelítések között éppen abban áll, hogy a gépelési szabályokat úgy tekintik -e, mint a nyelv meghatározását, vagy formalizmusként egy primitívebb alapnyelv tulajdonságainak ellenőrzésére. Az alább tárgyalt különböző szemantikai értelmezések többsége egyházi vagy curry szemszögből is látható.

Egyenletelmélet

Az egyszerűen begépelt lambda-számításnak ugyanaz az βη -ekvivalencia- elmélete , mint a típus nélküli lambda-számításnak , de típuskorlátozásoknak kell alávetni. A béta redukció egyenlete

${\ displaystyle (\ lambda x {\ mathbin {:}} \ sigma. ~ t) \, u = _ {\ beta} t [x: = u]}$

tartja a kontextusban , amikor és , míg az egyenletet eta csökkentés${\ displaystyle \ Gamma}$${\ displaystyle \ Gamma, x {\ mathbin {:}} \ sigma \ vdash t {\ mathbin {:}} \ tau}$${\ displaystyle \ Gamma \ vdash u {\ mathbin {:}} \ sigma}$

${\ displaystyle \ lambda x {\ mathbin {:}} \ sigma. ~ t \, x = _ {\ eta} t}$

bármikor megmarad, és nem jelenik meg ingyen . ${\ displaystyle \ Gamma \ vdash t \!: \ sigma \ to \ tau}$${\ displaystyle x}$${\ displaystyle t}$

Működési szemantika

Hasonlóképpen, a működési szemantika egyszerűen gépelt lambda kalkulus lehet rögzíteni, mint az típustalan lambda kalkulus segítségével hívás név szerint , hogy hívás érték , vagy más értékelési stratégiák . Mint minden gépelt nyelv, a típusbiztonság mindezen értékelési stratégiák alapvető tulajdonsága. Ezenkívül az alábbiakban leírt erős normalizálási tulajdonság azt sugallja, hogy minden értékelési stratégia megszűnik minden egyszerűen beírt kifejezéssel.

Kategorikus szemantika

Az egyszerűen begépelt lambda -számítás ( egyenértékűséggel) a derékszögű zárt kategóriák (CCC) belső nyelve , amint azt Lambek először megfigyelte . Bármely specifikus CCC alapján a megfelelő lambda -számítás alaptípusai csak az objektumok , a kifejezések pedig a morfizmusok . Ezzel szemben minden egyszerűen begépelt lambda számítás olyan CCC -t ad, amelynek objektumai a típusok, a morfizmusok pedig a kifejezések ekvivalenciaosztályai. ${\ displaystyle \ beta \ eta}$

Ahhoz, hogy a levelezést egyértelmű, egy típusú kivitelező a Descartes-szorzat az tipikusan a fenti. Megőrizni a kategoricitású a Descartes-szorzat egy hozzáteszi típusú szabályokat az párosítás , vetítés és egy egységnyi távon . Adott két kifejezés és , a kifejezésnek típusa van . Hasonlóképpen, ha valakinek van kifejezése , akkor vannak kifejezések, és ahol ezek megfelelnek a derékszögű termék előrejelzéseinek. Az egység kifejezés , az 1-es típusú, van írva, mint , és vocalized a „nulla”, a végső tárgy . Az egyenletelméletet ugyanígy kiterjesztik, így az embernek van ${\ displaystyle s {\ mathbin {:}} \ sigma}$${\ displaystyle t {\ mathbin {:}} \ tau}$${\ displaystyle (s, t)}$${\ displaystyle \ sigma \ times \ tau}$${\ displaystyle u {\ mathbin {:}} \ tau _ {1} \ times \ tau _ {2}}$${\ displaystyle \ pi _ {1} (u) {\ mathbin {:}} \ tau _ {1}}$${\ displaystyle \ pi _ {2} (u) {\ mathbin {:}} \ tau _ {2}}$${\ displaystyle \ pi _ {i}}$${\ displaystyle ()}$

${\ displaystyle \ pi _ {1} (s {\ mathbin {:}} \ sigma, t {\ mathbin {:}} \ tau) = s {\ mathbin {:}} \ sigma}$

${\ displaystyle \ pi _ {2} (s {\ mathbin {:}} \ sigma, t {\ mathbin {:}} \ tau) = t {\ mathbin {:}} \ tau}$

${\ displaystyle (\ pi _ {1} (u {\ mathbin {:}} \ sigma \ times \ tau), \ pi _ {2} (u {\ mathbin {:}} \ sigma \ times \ tau)) = u {\ mathbin {:}} \ sigma \ times \ tau}$

${\ displaystyle t {\ mathbin {:}} 1 = ()}$

Ez utóbbi így olvasható: " ha t típusa 1, akkor nullára csökken ".

A fentieket ezután kategóriává alakíthatjuk, ha a típusokat vesszük objektumnak . A morfizmusok vannak ekvivalencia osztályok párok , ahol X jelentése egy változó (típusú ), és t egy olyan kifejezés (típusú ), amelynek nincs szabad változó benne, kivéve az (adott esetben) x . A lezárás a szokásos módon a currying és az alkalmazás segítségével történik . ${\ displaystyle \ sigma \ to \ tau}$${\ displaystyle (x {\ mathbin {:}} \ sigma, t {\ mathbin {:}} \ tau)}$${\ displaystyle \ sigma}$${\ displaystyle \ tau}$

Pontosabban, a derékszögű zárt kategóriák és az egyszerűen begépelt lambda-elméletek kategóriája között vannak funktorok .

Gyakori, hogy ezt az esetet lineáris típusú rendszer alkalmazásával kiterjeszti zárt szimmetrikus monoid kategóriákra . Ennek az az oka, hogy a CCC a zárt szimmetrikus monoidális kategória speciális esete, amelyet általában a halmazok kategóriájának tekintünk . Ez jó a halmazelmélet megalapozásához , de úgy tűnik, hogy az általánosabb toposz kiváló alapot nyújt.

Bizonyításelméleti szemantika

Az egyszerűen beírt lambda -számítás szorosan kapcsolódik a propozicionális intuíciós logika implikatív töredékéhez , azaz a minimális logikához a Curry – Howard -izomorfizmus révén : a kifejezések pontosan megfelelnek a természetes dedukció bizonyításainak , és a lakott típusok pontosan a minimális logika tautológiái .

Alternatív szintaxisok

A fenti bemutatás nem az egyetlen módja az egyszerűen beírt lambda -számítás szintaxisának meghatározására. Az egyik alternatíva a típuskommentárok teljes eltávolítása (hogy a szintaxis azonos legyen a tipizálatlan lambda-kalkulussal), miközben biztosítja, hogy a kifejezések jól gépelhetők a Hindley – Milner típusú következtetéseken keresztül . A következtetési algoritmus befejező, hangos és teljes: amikor egy kifejezés gépelhető, az algoritmus kiszámítja a típusát. Pontosabban azt kiszámítja a kifejezés fő típusa , mivel gyakran el nem látott kifejezést (pl ) lehet egynél több típusú ( , stb, melyek minden példányát a fő típus ). ${\ displaystyle \ lambda x. ~ x}$${\ displaystyle {\ mathtt {int}} \ - {\ mathtt {int}}}$${\ displaystyle {\ mathtt {bool}} \ - {\ mathtt {bool}}}$${\ displaystyle \ alpha \ to \ alpha}$

Az egyszerűen beírt lambda -számítás egy másik alternatívája kétirányú típusellenőrzésen alapul , amely több típusjegyzést igényel, mint Hindley – Milner következtetés, de könnyebben leírható. A típusú rendszer két részre van osztva értékelések, ami mind ellenőrzés és szintézisét , írásbeli és rendre. Működési szempontból a három összetevő ,, és mind bemenet az ellenőrző ítélethez , míg a szintézis megítélése csak és csak bemenetként veszi fel a típust kimenetként. Ezek az ítéletek a következő szabályok alapján születnek: ${\ displaystyle \ Gamma \ vdash e \ Leftarrow \ tau}$${\ displaystyle \ Gamma \ vdash e \ Rightarrow \ tau}$${\ displaystyle \ Gamma}$${\ displaystyle e}$${\ displaystyle \ tau}$${\ displaystyle \ Gamma \ vdash e \ Leftarrow \ tau}$${\ displaystyle \ Gamma \ vdash e \ Rightarrow \ tau}$${\ displaystyle \ Gamma}$${\ displaystyle e}$${\ displaystyle \ tau}$

${\ displaystyle {\ frac {x {\ mathbin {:}} \ sigma \ in \ Gamma} {\ Gamma \ vdash x \ Rightarrow \ sigma}}}$ [1]	${\ displaystyle {\ frac {c {\ text {típusú konstans}} T} {\ Gamma \ vdash c \ Rightarrow T}}}$ [2]
${\ displaystyle {\ frac {\ Gamma, x {\ mathbin {:}} \ sigma \ vdash e \ Leftarrow \ tau} {\ Gamma \ vdash \ lambda x. ~ e \ Leftarrow \ sigma \ to \ tau}}}$ [3]	${\ displaystyle {\ frac {\ Gamma \ vdash e_ {1} \ Rightarrow \ sigma \ to \ tau \ quad \ Gamma \ vdash e_ {2} \ Leftarrow \ sigma} {\ Gamma \ vdash e_ {1} ~ e_ { 2} \ Jobbra mutató nyíl \ tau}}}$ [4]
${\ displaystyle {\ frac {\ Gamma \ vdash e \ Rightarrow \ tau} {\ Gamma \ vdash e \ Leftarrow \ tau}}}$ [5]	${\ displaystyle {\ frac {\ Gamma \ vdash e \ Leftarrow \ tau} {\ Gamma \ vdash (e {\ mathbin {:}} \ tau) \ Rightarrow \ tau}}}$ [6]

Vegye figyelembe, hogy az [1] - [4] szabályok közel azonosak a fenti (1) - (4) szabályokkal, kivéve az ellenőrző vagy szintézis ítéletek gondos megválasztását. Ezeket a választásokat így lehet magyarázni:

1. Ha van összefüggésben, tudjuk szintetizálni típus számára .${\ displaystyle x {\ mathbin {:}} \ sigma}$${\ displaystyle \ sigma}$${\ displaystyle x}$
2. A terminálállandók típusai fixek és szintetizálhatók.
3. Annak ellenőrzéséhez, hogy van -e típusa valamilyen kontextusban, kibővítjük a kontextust, és ellenőrizzük, hogy van -e típusa .${\ displaystyle \ lambda x. ~ e}$${\ displaystyle \ sigma \ to \ tau}$${\ displaystyle x {\ mathbin {:}} \ sigma}$${\ displaystyle e}$${\ displaystyle \ tau}$
4. Ha szintetizálja a típust (bizonyos kontextusban), és ellenőrzi a típust (ugyanabban a kontextusban), akkor szintetizálja a típust .${\ displaystyle e_ {1}}$${\ displaystyle \ sigma \ to \ tau}$${\ displaystyle e_ {2}}$${\ displaystyle \ sigma}$${\ displaystyle e_ {1} ~ e_ {2}}$${\ displaystyle \ tau}$

Vegye figyelembe, hogy a szintézis szabályait felülről lefelé olvassák, míg az ellenőrzés szabályait alulról felfelé. Különösen vegye figyelembe, hogy a [3] szabályban nincs szükségünk megjegyzésekre a lambda -absztrakcióra, mert a kötött változó típusa levezethető abból a típusból, amelynél a funkciót ellenőrizzük. Végül a következőképpen magyarázzuk az [5] és [6] szabályokat:

5. Annak ellenőrzéséhez, hogy van -e típusa , elegendő a típus szintetizálása .${\ displaystyle e}$${\ displaystyle \ tau}$${\ displaystyle \ tau}$
6. Ha a típus ellenõrzi , akkor a kifejezetten kommentált kifejezés szintetizál . ${\ displaystyle e}$${\ displaystyle \ tau}$${\ displaystyle (e {\ mathbin {:}} \ tau)}$${\ displaystyle \ tau}$

Az utóbbi két szabály miatt, amelyek a szintézis és az ellenőrzés között kényszerülnek, könnyen belátható, hogy bármely jól begépelt, de megjegyzés nélküli kifejezés ellenőrizhető a kétirányú rendszerben, amennyiben "elég" típusú megjegyzéseket illesztünk be. És valójában annotációkra csak a β-redexeknél van szükség.

Általános megfigyelések

A szokásos szemantika ismeretében az egyszerűen beírt lambda-számítás erősen normalizálódik : vagyis a jól begépelt kifejezések mindig értékre, azaz absztrakcióra redukálódnak . Ennek oka, hogy a rekurziót a gépelési szabályok nem teszik lehetővé: lehetetlen megtalálni a fixpontos kombinátorok típusait és a ciklusfogalmat . A rekurziót hozzá lehet adni a nyelvhez úgy, hogy van egy speciális operátora , vagy általános rekurzív típusokat ad hozzá , bár mindkettő kiküszöböli az erős normalizálást. ${\ displaystyle \ lambda}$${\ displaystyle \ Omega = (\ lambda x. ~ x ~ x) (\ lambda x. ~ x ~ x)}$${\ displaystyle {\ mathtt {fix}} _ {\ alpha}}$${\ displaystyle (\ alpha \ to \ alpha) \ to \ alpha}$

Mivel erősen normalizálódik, eldönthető, hogy egy egyszerűen begépelt lambda -kalkulus program leáll -e vagy sem: valójában mindig leáll. Ezért arra a következtetésre juthatunk, hogy a nyelv nem teljes Turingban .

Fontos eredmények

• Tait 1967 -ben kimutatta, hogy a redukció erősen normalizálódik . Következésképpen az egyenértékűség eldönthető . Statman 1977 -ben kimutatta, hogy a normalizálási probléma nem elemi rekurzív , ezt bizonyítja Mairson (1992). A probléma köztudottan a Grzegorczyk -hierarchia halmazában van . Berger és Schwichtenberg 1991 -ben pusztán szemantikai normalizálási bizonyítékot (lásd normalizálás értékeléssel ) adott.${\ displaystyle \ beta}$${\ displaystyle \ beta \ eta}$${\ displaystyle {\ mathcal {E}}^{4}}$
• Az -ekvivalencia egyesítési problémája eldönthetetlen. Huet 1973 -ban megmutatta, hogy a harmadik rendű egyesítés eldönthetetlen, és ezt Baxter 1978 -ban, majd Goldfarb 1981 -ben javította azzal, hogy a második rendű egyesítés már eldönthetetlen. Colin Stirling 2006 -ban bejelentette annak bizonyítékát, hogy a magasabb rendű egyezés (egyesítés, ahol csak egy kifejezés tartalmaz egzisztenciális változókat) eldönthető, és 2009 -ben teljes bizonyítékot tettek közzé.${\ displaystyle \ beta \ eta}$
• A természetes számokat kódolhatjuk a típus szerint ( egyházi számok ). Schwichtenberg 1976 -ban kimutatta, hogy pontosan a kiterjesztett polinomok ábrázolhatók függvényként az egyházi számok felett; ezek nagyjából a feltételes operátor alatt bezárt polinomok.${\ displaystyle (o \ to o) \ to (o \ to o)}$${\ displaystyle \ lambda ^{\}}}$
• A teljes modell a adja értelmezése bázis típusok készletek és funkciója típusok a halmazelméleti funkció helyet . Friedman 1975 -ben kimutatta, hogy ez az értelmezés teljes az -ekvivalencia szempontjából, ha az alaptípusokat végtelen halmazok értelmezik. Statman 1983 -ban kimutatta, hogy az -ekvivalencia az a maximális egyenértékűség, amely jellemzően kétértelmű , azaz típuscserék alatt zárt ( Statman tipikus kétértelműségi tétele ). Ennek következménye, hogy a véges modelltulajdonságok érvényesek, azaz a véges halmazok elegendőek a -ekvivalencia által nem azonosított kifejezések megkülönböztetéséhez .${\ displaystyle \ lambda ^{\}}}$${\ displaystyle \ beta \ eta}$${\ displaystyle \ beta \ eta}$${\ displaystyle \ beta \ eta}$
• Plotkin 1973 -ban vezetett be logikai összefüggéseket, hogy jellemezze a modell azon elemeit, amelyeket lambda kifejezésekkel lehet meghatározni. 1993 -ban Jung és Tiuryn ​​kimutatták, hogy a logikai kapcsolat általános formája (Kripke logikai relációk változó aritással) pontosan jellemzi a lambda meghatározhatóságát. Plotkin és Statman sejtette, hogy eldönthető, hogy a véges halmazokból generált modell adott eleme meghatározható -e egy lambda kifejezéssel ( Plotkin – Statman sejtés ). A sejtést Loader 1993 -ban hamisnak bizonyította.

Megjegyzések

Hivatkozások

• A. Church: A típusok egyszerű elméletének megfogalmazása , JSL 5, 1940
• WWTait : Intensional Interpretations of Functionals of Finite Type I, JSL 32 (2), 1967
• GD Plotkin: Lambda-meghatározhatóság és logikai összefüggések, Műszaki jelentés, 1973
• GP Huet: Az egyesítés határozatlansága a harmadik rendű logikai információban és ellenőrzésben 22 (3): 257-267 (1973)
• H. Friedman: Funkcionalisták közötti egyenlőség . LogicColl. '73, 22-37. Oldal, LNM 453, 1975.
• H. Schwichtenberg: Az egyszerűen beírt lambda-számításban meghatározható függvények, Arch. Math Logik 17 (1976) 113-114.
• R. Statman: A gépelt lambda-számítás nem elemi rekurzív FOCS 1977: 90-94
• WD Goldfarb: A 2. rendű egyesítési probléma eldönthetetlensége, TCS (1981), sz. 13, 225-230.
• R. Statman. -definiálható függvények és konverzió. Boltív. Math. Logik, 23: 21–26, 1983.${\ displaystyle \ lambda}$${\ displaystyle \ beta \ eta}$
• J. Lambek : A derékszögű zárt kategóriák és a gépelt lambda-számítások . Kombinátorok és funkcionális programozási nyelvek 1985: 136-175
• U. Berger, H. Schwichtenberg: Inverse of the Evaluation Functional for Typed lambda-calculus LICS 1991: 203-211
• H. Mairson: Egy egyszerű bizonyíték Statman tételére , TCS 103 (2): 387-394, 1992.
• Jung, A., Tiuryn, J .: A Lambda Definability új jellemzése , TLCA 1993
• R. Loader: The Undecidability of λ-definability , megjelent a Church Festschrift-ben, 2001
• H. Barendregt, Lambda Calculi with Types , Handbook of Logic in Computer Science, II. Kötet, Oxford University Press, 1993. ISBN  0-19-853761-1 .
• L. Baxter: A harmadik rendű diadikus egyesítési probléma eldönthetetlensége , Információ és ellenőrzés 38 (2), 170-178 (1978)

Külső linkek

• Loader, Ralph (1998. február). "Megjegyzések az egyszerűen beírt lambda -számításhoz" .
• "Church's Type Theory" bejegyzés a Stanford Encyclopedia of Philosophy -ban