Mängud, Täielik Abstraktsioon Ja Täielik Terviklikkus

2023 Autor: Noah Black | [email protected]. Viimati modifitseeritud: 2023-05-24 11:17

Sisenemise navigeerimine

• Sissesõidu sisu
• Bibliograafia
• Akadeemilised tööriistad
• Sõprade PDF-i eelvaade
• Teave autori ja tsitaadi kohta
• Tagasi üles

Mängud, täielik abstraktsioon ja täielik terviklikkus

Esmakordselt avaldatud teisipäeval 12. jaanuaril 2017

Arvutiprogrammid on teatud tüüpi tekstid. Seetõttu on loomulik küsida, mis on programmi tähendus või üldisemalt, kuidas saaksime luua programmeerimiskeele ametliku semantilise konto.

Sellistele küsimustele on palju võimalikke vastuseid, millest igaüht motiveerib programmide konkreetne aspekt. Nii et näiteks asjaolu, et programme tuleb täita mingil arvutusmasinal, põhjustab operatiivset semantikat, samas kui programmeerimiskeelte sarnasused matemaatilise loogika ametlike keeltega on motiveerinud denatsionaalset lähenemist, mis tõlgendab programme ja nende koostisosi komplektteoreetiliste mudelite vahendid.

Kõik need kontod indutseerivad programmeerimiskeele fraasidele oma sünonüümilise seose: Lühidalt öeldes väidab täielik abstraktsiooniomadus, et denatsionaalne ja operatiivne lähenemisviis määratlevad sama seose. See on programmeerimiskeele semantilise konto etalonomadus ja selle ebaõnnestumine lambda-calculusel põhineva lihtsa keele intuitiivse denatsioonikonto jaoks on viinud lõpuks mängude semantikas kulmineerunud denatsionaalse semantika tehniliste vahendite täiustamiseni, osaliselt inspireerituna dialoogimängude abil, mida algselt kasutati Lorenzeni ja tema kooli intuitionistliku loogika semantikas ning mida hiljem laiendasid Blass ja teised Girardi lineaarse loogika tõlgendamiseks. See konstruktiivse loogika ja programmeerimise vaheline sild on pakkunud välja ka semantiliste ja tõestusteooria vahelise seose tugevamad vormid, millest kõige tähelepanuväärsem näide on täieliku täielikkuse mõiste.

• 1. Sissejuhatus

  • 1.1 Programmeerimiskeelte tõlgendused
  • 1.2 Kompositsioonilisus
  • 1.3 Programmi samaväärsus ja täielik võtmine

• 2. Järjestikune kõrgema järgu arvutus: PCF-i täielik võtmise probleem

  • 2.1 PCF süntaks
  • 2.2 Operatiivne semantika

  • 2.3 Denotatsiooniline semantika

    • 2.3.1 Tüübid domeenidena
    • 2.3.2 Kõrgemate tüüpide arvutatavate funktsioonide abstraktne teooria
    • 2.3.3 PCF pidev semantika
  • 2.4 Seotud operatiivse ja denatsionaalse semantikaga

  • 2.5 Järjestikuse semantika poole

    • 2.5.1 Stabiilsus
    • 2.5.2 Järjestikused funktsioonid
    • 2.5.3 Konkreetsed andmestruktuurid ja järjestikused algoritmid
  • 2.6 Ajaloolised märkused ja täiendavad lugemised

• 3. Mängu semantika

  • 3.1 Täielik täielikkus
  • 3.2 Koostoimed

  • 3.3 Mängud ja strateegiad

    • 3.3.1 Mängud
    • 3.3.2 Strateegiad ja nende koosseis
  • 3.4 Spetsiaalsed strateegiad
  • 3.5 Ajaloolised märkused ja täiendavad lugemised
• Bibliograafia
• Akadeemilised tööriistad
• Muud Interneti-ressursid
• Seotud kirjed

1. Sissejuhatus

1.1 Programmeerimiskeelte tõlgendused

Täieliku abstraktsiooni mõiste tuleneb programmeerimiskeelte semantilise analüüsi Scott-Strachey lähenemisest (Scott & Strachey 1971; Strachey 1966, 1967), tuntud ka kui denatsionaalne semantika. Programmeerimiskeele ({L}) denatsionaalse semantika üks põhieesmärke on anda {({ L}) abstraktsete matemaatiliste struktuuride (domeenide) elementidena (D).

Programmide tähenduse andmiseks võime lähtuda nende täitmisest. See operatiivne tõlgendus on määratletud ainult programmi ({L}) programmide kogumis Prog ja hõlmab sobiva programmi väärtuste komplekti määratlemist, mis on ({L}) jälgitavad. Kui programmi (e) täitmine lõpeb väärtusega (v), mis on väljendatud märkega (e \ opDownarrow v), siis (v) on (e) operatiivne tähendus. See määratleb programmide operatiivse tõlgendamise osalise funktsioonina ({ matemaatiline {O}}) programmidelt väärtustele, kus ({ matemaatiline {O}} (e) = v), kui (e \ opDownarrow v).

Mõlemad tõlgendused kutsuvad esile programmilausete loomuliku ekvivalentsussideme. Ühes selle sõnastuses osutab täielik abstraktsioon keele denatsioonilise ekvivalentsuse kokkulangevusele keelega, mille on esile kutsunud operatiivne semantika. Täielik abstraktsus on kõigepealt määratletud Robin Milneri (1975) artiklis, kus on välja toodud ka denotatsioonilise semantika olulised kontseptuaalsed koostisosad: kompositsioonilisus ning seosed programmide vaatlus- ja denatsioonilise ekvivalentsuse vahel. Sel põhjusel võib täielikku abstraktsiooni käsitleda kui programmeerimiskeele semantika ulatuslikku maastikku ja on seetõttu üsna asjakohane programmeerimiskeelte filosoofia (Valge 2004) ja arvutiteaduse (Turner 2016) põhiprobleemide osas.

1.2 Kompositsioonilisus

Kompositsioonilisus (Szabó 2013) on programmeerimiskeele semantilise analüüsi soovitav omadus, kuna see võimaldab arvutada programmi tähenduse selle koostisosade tähenduste funktsioonina. Tegelikult kehtib Milneri kontol (vt eriti 1975: ptk 1, 4) kompositsioon veelgi üldisemalt arvutusagentide suhtes, mis on väiksemate hulgast kokku pandud sobivate kompositsioonitoimingute abil. Need ained võivad programmide kõrval hõlmata ka riistvarasüsteeme, näiteks arvutit, mis koosneb mälust, mis koosneb omakorda kahest mäluregistrist, ja protsessorit, kus kõik komponendid on arvutusagendid. See võimaldab lisada ühte raamistikku riistvarast, tarkvarast ja isegi mõlemast koosnevad süsteemid. Nüüdsüntaktilised reeglid, mis määravad induktiivselt programmeerimiskeele erinevad fraasikategooriad, võimaldavad meil käsitleda ({L}) programmifraaside algebranina, mille allkiri on määratud nende reeglitega. Üks kompositsioonilisuse kontseptsioon, mis sobib eriti hästi praegusesse keskkonda (Szabó 2013: teine lõik), määratleb programmide kompositsioonilise tõlgenduse, mille homomorfism on sellest algebrast kuni deotatsioonide valdkonnani, mis seostub programmide algebrani iga toiminguga vastava semantilise operatsiooniga denatsioonide kohta.2) määratleb homomorfismiga programmide kompositsioonilise tõlgenduse sellest algebrast kuni denatsioonide valdkonnani, mis seostub programmide algebrani iga toiminguga vastava demantide semantilise operatsiooniga.2) määratleb homomorfismiga programmide kompositsioonilise tõlgenduse sellest algebrast kuni denatsioonide valdkonnani, mis seostub programmide algebrani iga toiminguga vastava demantide semantilise operatsiooniga.

Vaatleme näiteks lihtsat imperatiivset keelt, mille programmid (mathtt {c}) tähistavad oleku teisendusi ({ mathcal {M}} (mathtt {c}): \ Sigma \ kuni \ Sigma). Selle keele programmidega tehtavate toimingute hulgas on järjestikune kompositsioon, programmi (mathtt {c} _1; \ mathtt {c} _2) ülesehitamine programmidest (mathtt {c} _1) ja (mathtt {c} _2). Selle programmi kavandatud rakenduslik tähendus on see, et kui (mathtt {c} _1; \ mathtt {c} _2) käivitatakse olekust (sigma \ in \ Sigma), siis teostame kõigepealt (mathtt {c} _1) vormi vormi olek (sigma). Kui täitmine lõpeb, saame oleku (sigma '), millest alustame (mathtt {c} _2) täitmist, jõudes täitmise lõppedes olekule (sigma' ').. Viimane olek on seisund, milleni jõutakse (mathtt {c} _1;\ mathtt {c} _2) olekust (sigma). Denatsioonilisest vaatepunktist on meil olekute kui funktsioonide (Sigma \ kuni \ Sigma) kompositsioonide toimimine ja meie programmi kompositsioonilise tõlgenduse annab järgmine identiteet, mida tuleb lugeda sätte klausliks ({ matemaatiline {M}}) määratlus sissejuhatuse kaudu programmide struktuurile: [{ mathcal {M}} (mathtt {c} _1; \ mathtt {c} _2) = { mathcal { M}} (mathtt {c} _2) ring { matemaatiline {M}} (mathtt {c} _1)) või, mis täpsemalt öeldes, mis tahes oleku jaoks (sigma): [{ mathcal {M}} (mathtt {c} _1; \ mathtt {c} _2) (sigma) = { mathcal {M}} (mathtt {c} _2) ({ mathcal {M}} (mathtt {c} _1) (sigma)).) Kuna enamikul programmeerimiskeeltel on mitu fraasikategooriat (näiteks avaldised, deklaratsioonid, juhised), on programmide algebrad üldiselt mitmeti sorteeritud, iga fraasikategooria jaoks üks sort.. Denotatsiooniline semantika taotleb süstemaatiliselt ideed seostada iga programmi fraas kompositsiooniliselt vastavat sorti tähisega (varasema ülevaate leiate Stoy 1977-st).

1.3 Programmi samaväärsus ja täielik võtmine

Programmeerimiskeele ({L}) tõlgenduse olemasolu kutsub tavapäraselt esile programmilausete samaväärsuse:

Definitsioon 1.1 (denotatsiooniline samaväärsus). Mis tahes kahe programmilause korral (e, e '), on nad denatiivselt ekvivalentsed ja kirjutatud (e \ simeq _ { matemaatiline {M}} e'), kui ({ matemaatiline {M}} (e) = { matemaatiline {M}} (e ')).

Kui ({ matemaatiline {M}}) on kompositsiooniline, siis ({ simeq _ { mathcal {M}}}) on kongruents nende programmide algebrani, mille tuletatud toiming, nendest, mis saadakse operatsioonide koostisega allkirja, nimetatakse kontekstideks. Kontekst (C \ blbr) tähistab “auku” programmi fraasi, mida saab täita sobiva tüüpi programmilausetega (e), et saada programmilause (C [e]). Kontekstide abil saame hõlpsalt iseloomustada semantilise kaardistamise kompositsioonilisust:

Ettepanek 1.1. Kui ({ matemaatiline {M}}) on kompositsiooniline, siis kõigi fraaside (e, e ') ja kõigi kontekstide (C \ blbr) korral:) sildi {1} etikett {kompositsioonilisus} {e \ simeq _ { matemaatiline {M}} e '} parempoolne nool {C [e] simeq _ { matemaatiline {M}} C [e']}.)

See sõnastus tõstab esile veel ühe kompositsioonilisuse väärtusliku aspekti, nimelt kõigi kontekstide referentsiaalse läbipaistvuse, samaväärselt nende laiendatavuse: denatiivselt ekvivalentsed fraasid saab asendada igas kontekstis, jättes muutmata saadud fraasi deotatsiooni. Selle implikatsiooni ((ref {koostise}})) kohaselt on ({ simeq _ { matemaatiline {M}}}) ühilduvus. Seetõttu peame denatsioonilise ja operatiivse kongruentsuse võrdlemiseks kongruentsi naiivsest operatiivsest ekvivalentsist välja viima, määrates (e \ sim e ') seadistamise siis ja ainult siis, kui ({ matemaatiline {O}} (e) = { matemaatiline {O}} (e ')). Seda saab teha, kasutades ära programmi kontekste (C \ blbr), esindades programmi, millel on “auk” ja mida saab täita sobiva tüüpi programmilausetega (e), et saada täielik programm (C [e]).

Definitsioon 1.2 (vaatluslik samaväärsus) Arvestades ükskõik millist programmi kahte fraasi (e, e '), on need vaatluslikult samaväärsed, kirjutatud (e \ simeq _ { matemaatiline {O}} e'), kui kõigi programmi kontekstide korral (C \ blbr) ja kõik programmi väärtused (v): [C [e] opDownarrow v \ \ text {ainult siis ja ainult siis, kui} C [e '] opDownarrow v.)

Vaatluslik ekvivalentsus on siis kongruents programmilausete algebrani ja tegelikult on see (sim) suurim kongruents. Milneri (1975) konto üldisest vaatenurgast, mida me tähelepanelikult jälgime, kujutab arvutiagentuuri kontekst ühte selle võimalikest keskkondadest. Kui me võtame omaks põhimõtte, et “ilmne käitumine moodustab arvutusagendi kogu tähenduse” (Milner 1975: 160), siis kontekstid esindavad intuitiivselt tähelepanekuid, mida saame arvutusagendi käitumise kohta teha. Programmide puhul on vaatletavad väärtused, seega tuvastab vaatluslik samaväärsus fraasid, mida ei saa eristada vaatluste abil, mille tulemused on selgelt eristatavad väärtused. Milneri metoodilise põhimõtte üks tagajärg on see, et arvutiagendist saab a

muundur, mille sisestusjada koosneb päringutest selle keskkonna poolt või vastustest selle keskkonna kohta ning mille väljundjada koosneb päringutest selle keskkonna kohta või vastustest selle kohta. (Milner 1975: 160)

Arvutusagendi käitumine toimub siis dialoogi vormis agendi ja selle keskkonna vahel - metafoor, mis on mängu semantiliste teoreetiliste lähenemiste keskmes, mida käsitletakse 3. osas. See käitumisviis, millel on juured Milner on ka piiritletud olekute seadmete inseneride töös laiendanud samaaegsete süsteemide modelleerimise metoodikat eesmärgiga

kirjeldada samaaegset süsteemi piisavalt täielikult, et täpselt määrata, millist käitumist väline vaatleja näeb või kogeb. Seega on lähenemisviis põhjalikult laienev; kaks süsteemi on üksteisest lahutamatud, kui me ei suuda neid lahutada, ilma et me neid lahutaksime. (Milner 1980: 2)

Lisaks on süsteemi ja vaatleja rollid sümmeetrilised sellisel määral, et

tahaksime esindada vaatlejat kui masinat, seejärel esindada liitvaatlejat / masinat kui masinat, siis mõista, kuidas see masin käitub uue vaatleja jaoks. (Milner 1980: 19)

Kui vaatluslik ekvivalentsus on arvuti esindaja sisemiste üksikasjade suhtes pime, kuid jälgitakse ainult võimalikke koostoimeid selle keskkonnaga, milles ta osaleb, võetakse denatsiooniliseks ekvivalentsiks arvutiaine sisestruktuuri arvestades ja sünteesitakse kompositsiooniliselt selle kirjeldus selle sisemistest osadest. Täieliku abstraktsiooni mõiste on mõeldud just nende kahe perspektiivi kokkulangevuse tabamiseks:

Definitsioon 1.3 (täielik abstraktsioon). Denatsiooniline semantika ({ matemaatiline {M}}) on toimiva semantika ({ matemaatiline {O}}) osas täiesti abstraktne, kui indutseeritud ekvivalendid ({ simeq _ { mathcal {M}} }) ja ({ simeq _ { matemaatiline {O}}}) langevad kokku.

Programmi omaduste uurimise vahendina võib täielikku abstraktsiooni vaadelda kui denatsionaalse semantika täielikkuse omadust: programmide iga ekvivalentsust, mida saab operatiivselt tõestada, saab tõestada ka denatiivsete vahenditega. Samaväärselt piisab denatiivsest tõestusest, et kaks terminit ei ole samaväärsed, et näidata, et need pole igas programmi kontekstis asendatavad.

Täielik abstraktsioon toimib ka keele ({L} _1) keelest (mitte tingimata erinevast keelest) ((tingimata erinevasse keelde) (mitte tingimata erinevasse keelde) tõlke ({L} _2) hindamise kriteeriumina, tingimusel et kahel keelel on samad vaatluskomplektid, ütlevad Obs (Riecke 1993). Siis on (vartheta) täiesti abstraktne, kui (e, e '{L} _1 \ -s) vaatluslik samaväärsus (määratletud Obs-iga) võrdub (vartheta (e), \ vartheta (e ')). Täielikult abstraktse tõlke olemasolu keelte vahel saab kasutada nende väljendusjõu võrdlemiseks (Mitchell 1993; Riecke 1993) soovituse kohaselt: ({L} _1) pole ekspressiivsem kui ({L} _2) kui on olemas {({L} _1) täielik abstraktne tõlge keelde ({L} _2).

Enne täielikku abstraktsiooni ja sellega seotud mõistete tutvustamist programmeerimiskeelte semantika üldises sissejuhatuses, et näidata nende mõistete laia asjakohasust, on huvitav jälgida, et on olemas väga üldine seade, milles on võimalik uurida täielikku abstraktsiooni omadust, mida on soovitanud Hodges (2001) jt hiljutised uurimused looduslike ja kunstlike keelte koostise kohta. Selles seadistuses on täielik abstraktsioon seotud probleemiga, kuidas leida Frege'i kontekstipõhimõtte kaudu keele alamhulga (X) semantilise tõlgenduse kompositsiooniline laiendus kogu keele tõlgenduseni (vt Janssen 2001 selle kohta), väites, et väljendi tähendus tähenduses (Y) on selle panus seda sisaldava avaldise (X) tähenduses. Frege'i algses sõnastuses oli (X) lausete komplekt ja (Y) kõigi avaldiste komplekt, programmeerimisteoorias aga (X) on programmide kogum, (Y) komplekt kõigist programmi fraasidest.

Täieliku abstraktsiooni määratluse nõrgendamine kujutab endast keele denotseeriva tõlgendamise olulist piisavuse nõuet:

Definitsioon 1.4 (arvutuslik piisavus). Denatsiooniline semantika ({ matemaatiline {M}}) on arvutuslikult piisav toimiva semantika ({ mathcal {O}}) suhtes, kui kõigi programmide (e) ja kõigi väärtuste (v) [{{matemaatiline {O}} (e) = v \ \ tekst {siis ja ainult siis, kui} { matemaatiline {M}} (e) = { matemaatiline {M}} (v).)

Samaväärne arvutusliku adekvaatsuse sõnastus võimaldab rõhutada selle seost täieliku abstraktsiooniga:

Ettepanek 1.2. Oletame, et ({ matemaatiline {M}}) on kompositsiooniline denatsioonitõlgendus, nii et ({ mathcal {O}} (e) = v) tähendab ({ mathcal {M}} (e) = { matemaatiline {M}} (v)). Järgmised kaks lauset on samaväärsed:

1. ({ matemaatiline {M}}) on arvutuslikult piisav ({ matemaatilise {O}}) suhtes;
2. mis tahes kahe programmi jaoks (e, e '\ rakenduses { texttt {Prog}}), [e \ simeq _ { matemaatiline {M}} e' \ tekst {ainult siis, kui} e \ simeq_ { matemaatiline {O}} e ')

Kuigi täieliku abstraktsiooni omaduste määratlemine on lihtne, on programmeerimiskeelte väga looduslike näidete täiesti abstraktsed mudelid osutunud vaevaliseks, tekitades täieliku abstraktsiooni probleemi. Arutelus täieliku abstraktsiooni üle keskendume peamiselt keele PCF (programmeerimiskeel arvutatavatele funktsioonidele, Plotkin 1977) täieliku abstraktsiooni probleemile, mis on lihtsalt trükitud (lambda) - arvutuskriteerium aritmeetiliste primitiivide ja fikseeritud punktiga kombinaatori jaoks. kõigis tüüpides, mis on välja pakutud Scott 1969b. See keel on oluline, kuna hõlmab enamikku programmeerimisfunktsioonidest, millega semantiline analüüs peab toime tulema: kõrgema järgu funktsioonid, tüübid ja rekursioon koos redutseerimisreeglitega, mis pakuvad abstraktseid seadmeid mitme hindamisstrateegia katsetamiseks. LisaksPCF on mudel ka muudele lihtsalt trükitud (lambda) - kalkulatsiooni laienditele, mida kasutatakse programmeerimisfunktsioonide katsetamiseks, nagu näiteks Reynoldsi idealiseeritud Algol (1981). PCF-i täieliku abstraktsiooni probleemi lahendamiseks tehtud jõupingutused aitasid kõrvalmõjuna semantilise analüüsi jaoks ette näha matemaatiliste tehnikate komplekti süstemaatilist väljatöötamist, mille kasulikkus ületab nende esialgseid rakendusi. Kirjeldame mõnda neist 2. osas, mis on pühendatud PCF-i semantilisele analüüsile osaliselt järjestatud struktuuride alusel, Dana Scotti (1970) tutvustatud domeenid, mida käsitleme jaotises 2.3. Tehnilised arengud domeenide teoorias ja ka Girardi lineaarsele loogikale keskendunud uues uurimisvaldkonnas on viinud mängude semantikani (Abramsky, Jagadeesan ja Malacaria 2000; Hyland & Ong 2000),mida peetakse nüüd elujõuliseks alternatiiviks domeenidel põhinevale standardsele denatsionaalsele semantikale. Just sellele lähenemisele pühendame 3. jao, püüdes anda piisavalt üksikasju, et suunata lugeja ulatuslikku ja endiselt kasvavat kirjandust, mis dokumenteerib mängude rakendusi mitmesuguste programmeerimiskeele funktsioonide tõlgendamiseks.

2. Järjestikune kõrgema järgu arvutus: PCF-i täielik võtmise probleem

Täielik abstraktsiooniprobleem on osutunud eriti keeruliseks lihtsalt trükitud (lambda) - arvutusliku versiooniga aritmeetiliste primitiividega PCF-i (programmeerimine arvutatavate funktsioonidega) (Plotkin 1977), mänguasja programmeerimiskeele, mis põhineb loogikal arvutatavate funktsioonide jaoks, arvutamiseks (Plotkin 1977). Scott (1969) ja Milner (1973). Selles osas tutvustame keelt (selle versiooni) koos selle funktsionaalse ja denatsionaalse semantikaga ning visandame, kuidas selle keele puhul ilmneb täielik abstraktsiooni probleem. Probleem on olnud programmeerimiskeelte teoreetilise uurimise üks peamisi probleeme umbes kaks aastakümmet, alates selle algsest sõnastamisest maamärkides (Milner 1977; Plotkin 1977) kuni 1993. aastal pakutud esimeste lahendusteni (Abramsky jt 2000; Hyland & Ong 2000), kasutades mängude semantikat, mille kohta vaata punkt 3.

2.1 PCF süntaks

PCF on keel, mis põhineb lihtsalt trükitud (lambda) - aritmeetiliste ja tõeväärtuslike primitiividega laiendatud arvutustel ja selle tüübisüsteem on vastavalt määratletud:

Definitsioon 2.1 (PCF tüübid). PCF tüüpide komplekti tüübid on induktiivselt määratletud järgmiselt

• maatüübid num (naturaalarvu tähistavate terminite puhul), bool (tõeväärtusi esindavate terminite puhul) on tüübid,
• kui (sigma, \ tau) on tüübid, on ka ((sigma \ kuni \ tau)) tüüp.

Kui võimalik, jäetakse sulg parempoolse seose järgi välja, nii et tüüp (sigma_1 \ kuni \ cdots \ sigma_n \ kuni \ tau) on samaväärne dokumendiga ((sigma_1 \ kuni (sigma_2) to (cdots (sigma_n \ to \ tau) cdots))))

PCF-terminid on lihtsalt trükitud tüübi (lambda) - calculus terminid, mida laiendatakse järgmiste näidatud tüüpi aritmeetiliste konstantidega:

• konstant ({0}: \ texttt {num}), mis tähistab naturaalarvu 0;
• konstant (texttt {succ}) tüüpi (texttt {num} kuni \ texttt {num}), mis tähistab pärijafunktsiooni naturaalarvude kohal;
• konstant (texttt {pred}) tüüpi (texttt {num} kuni \ texttt {num}), mis tähistab eelkäija funktsiooni naturaalarvude kohal;
• konstandid (texttt {tt}) ja (texttt {ff});
• konstandid tüüp (texttt {bool} to \ texttt {num} to \ texttt {num} to \ texttt {num}) ja (texttt {bool} to \ texttt {bool} to \ texttt {bool} to \ texttt {bool}) vastavalt num-tüüpi ja bool-tingimuste korral: mõlemad on kirjutatud kujul ({ texttt {kui} cdot \ texttt {siis} cdot \ texttt {else} cdot}) ja laseme kontekstil selgeks teha, mis on tulemuse kavandatud tüüp;
• konstantset (texttt {null?}) tüüpi nulltesti jaoks (texttt {num} to \ texttt {bool});
• fikseeritud punktiga kombinaatori ühtne funktsioonisümbol ({ mathtt {Y} (cdot)}), kus ({ mathtt {Y} (e)}: \ sigma) mis tahes (e: \ sigma \ to \ sigma).

Terminid on üles ehitatud induktiivselt vastavalt reeglitele, mis võimaldavad järeldada vormi (B \ vdash e: \ sigma) otsuseid, väites, et mõiste (e) on tüüpi (sigma) eeldusel, et muutujad (e) vabalt esinevatele antakse ainulaadsed tüübid kujul ({ {x_1: \ sigma_1, \ ldots, x_k: \ sigma_k }}.) kordumatut tüüpi.) Ehituse reegel PCF-mõisted on seega selliste kohtuotsuste järelduseeskirjad. Eelkõige kehtivad reeglid tippitud konstandite kohta, näiteks mis tahes alusel (B) on olemas otsus (B \ vdash \ texttt {null?}: \ Texttt {num} to \ texttt {bool}), ja meil on reeglid trükitud (lambda) - abstraktsioonide) frac {B, x: \ sigma \ vdash e: \ tau} {B \ vdash { lambda x: \ sigma {, kohta. \,} e}: \ sigma \ to \ tau}) ja rakendused) frac {B \ vdash e_1: \ sigma \ to \ tau \ qquad B \ vdash e_2: \ sigma} {B \ vdash e_1 e_2:\ tau}) ja reegel fikseeritud punkti operaatorile:) frac {B \ vdash e: \ sigma \ to \ sigma} {B \ vdash { mathtt {Y} (e)}: \ sigma}.]

2.2 Operatiivne semantika

PCF-programm on maatüüpi suletud tähtaeg. Täpsustame, kuidas programme täidetakse, määratledes hindamissuhte (e \ opDownarrow v) suletud tingimuste (e) ja väärtuste (v) vahel, kus väärtused on vormi konstandid ja abstraktsioonid ({ lambda x: \ sigma {,. \,} e}). Eelkõige on maapinna tüüpi booli väärtused (texttt {tt}, \ texttt {ff}) ja maatüübi num väärtused on ({0}) ning vormi kõik tingimused) mathtt {n} = \ alatugi { texttt {succ} (ldots \ texttt {succ}} _ {n} ({0}) ldots).) Hindamine on määratletud juhtudega vastavalt terminite struktuurile, kasutades järgmisi vahendeid: järeldamisreeglite vorming (e \ opDownarrow v) kohtuotsuste jaoks. Nendes reeglites öeldakse, kuidas termini hindamise tulemus sõltub muude terminite hindamise tulemusest; ainsad aksioomid on iga väärtuse (v) jaoks kujul (v \ opDownarrow v). Näiteks on olemas reegel) frac {e \ opDownarrow v} {{ texttt {succ} e} opDownarrow { texttt {succ} v}}), mis ütleb, et kui (e) on (v), siis ({ texttt {succ} e}) hindamise tulemus on ({ texttt {succ} v}). Samamoodi võime kirjeldada teiste konstantide hindamist. Vormi (e_1 \ e_2) tähtaja hindamine toimub järgmiselt: hinnatakse kõigepealt (e_1); kui hindamine lõpeb väärtusega (v '), siis jätkatakse (e_1 \ e_2) hindamist väärtusega (v' \ e_2); kui see lõpeb väärtusega (v), on see väärtus (e_1 \ e_2), ametlikult) frac {e_1 \ opDownarrow v '\ qquad v' \ e_2 \ opDownarrow v} {e_1 \ e_2 \ opDownarrow v}) Vormi ({ lambda x: \ sigma {,. \,} e_1}) väärtuse jaoks,selle rakendamine terminile (e_2) on väärtus (kui see on olemas), mis saadakse, kui hinnatakse mõistet (e_1 [e_2 / x]), mis tuleneb asendades (e_2) kõigi (x) vaba esinemistega asukohas (e_1):) frac {e_1 [e_2 / x] opDownarrow v} {({ lambda x: \ sigma {,. \,} e_1}) e_2 \ opDownarrow v}.) Need rakendage nn nime järgi hindamise strateegia: rakenduses tuleb funktsiooni positsioonis olevat terminit hinnata täielikult enne argumendi positsioonis olevat terminit, mis seejärel edastatakse tegeliku parameetrina. Fikseeritud punktiga kombinaator on oluline rekursiivsete definitsioonide kodeerimiseks. Selle hindamist kirjeldab reegel) frac {e ({ mathtt {Y} (e)}) opDownarrow v} {{ mathtt {Y} (e)} opDownarrow v}), mis on ainus reegel, mille eeldus hõlmab hinnatava laiema tähtaja hindamist:seetõttu ei saa hindamissuhte määratlust taandada struktuursele induktsioonile.

Eriti huvitavad meid olukorrad, kui termini (e) hindamisel pole väärtust; sel juhul ütleme, et (e) lahknevad, ja kirjutame (e \ opUparrow). Hindamisprotsessi põhjuslik struktuur ilmneb lahknevate tingimuste juuresolekul. Esialgne näide on tegelikult mõiste, mis erineb väga tugevas tähenduses:

Definitsioon 2.2 (määratlemata). Mis tahes maatüübi (gamma) jaoks määrake (Omega: \ gamma) kui [{ mathtt {Y} ({ lambda x: \ gamma {,. \,} X})}]

Hindamisreegleid kontrollides näeme, et ainus võimalik hindamisprotsess põhjustab lõpmatut regressi, seega (Omega \ opUparrow).

Tavalised tõeväärtuse toimingud saame määratleda tingimusliku operaatori abil, nagu järgmistes näidetes:) alusta {joondamine} silt {2} texttt {ja} & = { lambda x: \ texttt {bool}, y: \ texttt {bool} {,. \,} { texttt {kui} x \ texttt {siis} y \ texttt {else} texttt {ff}}}. \ silt {etbivalente} \ \ silt {3} texttt {või} & = { lambda x: \ texttt {bool}, y: \ texttt {bool} {,. \,} { texttt {if} x \ texttt {then} texttt {tt} texttt {else} y}} label {velbivalente} end {joondada}) tavaliste tõestabelitega. Nüüd peame aga arvestama hindamisprotsessi lahknemise võimalusega, näiteks sellises terminis nagu (texttt {või} (Omega, \ texttt {tt})), seetõttu laiendame tavalist tõde tabelid, lisades uue tõeväärtuse, mis tähistab teabe puudumist, (bot) (loe kui määratlemata) väärtustele (texttt {tt}) ja (texttt {ff}),kui termini (Omega) väärtus. Siinkohal on esimene hinnatav argument vasakul ja kui see erineb, siis kogu hindamisprotsess lahkneb. Mõelge nüüd operaatorile por, kelle tõlgenduse annab tabel) silt {4} silt {por} alga {massiiv} {r | lll} texttt {por} & \ textit {tt} & \ textit {ff }> & \ bot \\ \ bot & \ textit {tt} & \ bot & \ bot \ end {array}) Sel juhul (texttt {por} (texttt {tt}, \ Omega) = \ texttt { por} (Omega, \ texttt {tt}) = \ texttt {tt}): see on paralleel - või millel on keskne roll PCF-i täielikus abstraktsiooniprobleemis. Selgub, et seda ei saa ühegi PCF-i mõistega määratleda, just selle paralleelsuse tõttu. PCF-i semantilise analüüsi jaoks on vaja teooriatüübilisi andmetüüpe koos osaliste elementide ja nende funktsioonidega, mis toetavad rekursiivse määratluse abstraktset vormi fikseeritud punktide võrrandite abil: see saavutatakse Scotti domeenide teoorias, Strachey (1966, 1967) kavandatud programmeerimiskeelte denatiivse semantika algne matemaatiline alus.

2.3 Denotatsiooniline semantika

2.3.1 Tüübid domeenidena

Millised on osalise andmeruumi üldised struktuurilised omadused? Dana Scotti (1970) välja töötatud matemaatiline arvutusteooria on vastus sellele küsimusele, mis võtab põhistruktuuridena osaliselt järjestatud kogumid, mida üldiselt nimetatakse domeenideks. Domeeni osaline järjekord kirjeldab elementide poolt kantava teabe kvalitatiivset mõistet. Sellises raamistikus on loomulik, et lahknevused kinnitatakse, sisestades uue elemendi, (bot), mis tähistab teabe puudumist. Kui (x \ sqsubseteq y) selles osalises järjekorras,

(y) vastab (x) ja on (võimalik) täpsem kui (x) ldots]), seega (x \ sqsubseteq y) tähendab, et (x) ja (y) tahavad sama olemi lähendada, kuid (y) annab selle kohta rohkem teavet. See tähendab, et peame lubama "mittetäielikke" üksusi, näiteks (x), mis sisaldavad ainult "osalist" teavet. (Scott 1970: 171)

Saadud osaliselt järjestatud komplektidel peaks olema ka omadus, et lähendite jadad, eriti lõpmatud ahelad (x_0 \ sqsubseteq x_1 \ sqsubseteq \ ldots) peaksid ühtima piirini, mis sisaldab teavet, mida kumulatiivselt pakub (x_i). Sama ülesehitust kasutatakse ka Kleene tõendusmaterjalis esimese rekursiooniteoreemi kohta Kleene'is 1952. aastal (66, 348–50) ja see võimaldab määratleda pideva funktsiooni mõiste piiride säilimise osas.

Definitsioon 2.3 (täielikud osalised tellimused). Täielik osaline tellimus (cpo) on osaliselt tellitud komplekt ({ langle D, \ sqsubseteq \ rangle}) vähima elemendiga (bot) ja selline, et iga suurenev ahel (x_0 \ sqsubseteq x_1 (D) elementide sqsubseteq \ ldots) on väikseima ülaosaga (bigsqcup_n x_n).

Mis tahes komplekti (X) korral kirjutame uue elemendi lisamisel saadud komplekti (X _ cup { bot }) jaoks (X _ { bot}), mis on saadud uue elemendi (bot) lisamisega. On loomulik, et elemendid (X _ { bot}) tellitakse vastavalt nende teabekogusele, seadistades (x, y \ X _ { bot}),) alusta {joondatud} x \ sqsubseteq y & \ Longleftrightarrow (x = \ bot \ \ tekst {või} x = y). \ end {joondatud}) Vormi (X_ \ bot) osaliselt järjestatud struktuure nimetatakse tasapinnaliseks domeeniks, mille hulgas meil on (texttt {bool} = { {{ textit {tt}}, { textit {ff}} }} _ \ bot) ja (texttt {num} = { mathbb {N }} _ \ bot), mida kasutatakse PCF-i maapealsete tüüpide tõlgendamiseks.

Üldine nõue domeenidele on see, et iga element peab olema selle lõplike lähendite piir, selleks et piiritleda lõplikkust (või kompaktsust), mida saab täielikult sõnastada osalise järjekorra struktuuri järgi:

Definitsioon 2.4 (cpo lõplikud elemendid). Kui (D) on cpo, on element (d \ in D) piiratud, kui iga suureneva ahela kohta (x_0 \ sqsubseteq x_1 \ sqsubseteq \ ldots) [d \ sqsubseteq \ bigsqcup_n x_n \ Longrightarrow \ eksisteerib x_i \ \ vasakul (d \ sqsubseteq x_i \ paremal).) (d \ sisse D) korral tähistab (matemaatiline {A} (d)) allpool olevate lõplike elementide kogumit (d); (matemaatiline {A} (D)) on (D) lõplike elementide kogum. Lõplikke elemente nimetatakse ka kompaktseteks.

Pange tähele, et hulga (X) lõplikud alamhulgad on täpselt (X) alamhulkade täieliku võre lõplikud elemendid. Samuti on kasulik jälgida, et see määratlus vastab meie intuitsioonile vaid osaliselt: kaaluge näiteks lõplikku elementi (infty + 1) cpo [0 \ sqsubseteq 1 \ sqsubseteq 2 \ sqsubseteq \ cdots \ sqsubseteq \ infty \ sqsubseteq \ infty + 1.)

Definitsioon 2.5 (algebraline cpo). A (D) on algebraline, kui iga (d \ in D) korral kasvab (d) lõplike lähendite ahel (x_0 \ sqsubseteq x_1 \ sqsubseteq \ ldots), nii et [d = \ bigsqcup_n x_n.) Kui (D) on algebraline, siis ütleme, et lõplikud elemendid moodustavad (D) aluse.

PCF-i tõlgendamiseks sobiliku domeenikategooria saamiseks on vaja veel viimast täielikkuse eeldust algebraliste krediidireitingute kohta:

Definitsioon 2.6. Arvestades cpo (D), kui (X \ subseteq D) on ülaservaga, ütleme, et (X) on järjekindel, ja kirjutame (opuparrow X) või (x \ opuparrow y) millal (X = { {x, y }}). (D) on järjepidevalt täielik, kui igal (X \ subseteq D) on nii, et (oparibi X) on vähim ülaserv.

Järgmine mõiste domeenist, mis on osutunud eriti mugavaks programmeerimiskeelte denatiivse semantika raamistikuna (Scott 1982):

Definitsioon 2.7 (domeen). Domeen on järjekindlalt täielik algebraline arvutusliku alusega cpo.

2.3.2 Kõrgemate tüüpide arvutatavate funktsioonide abstraktne teooria

Kuidas saaksime domeenide elementide järjestamisel kaudse teabe mõistet kasutada abstraktse võrreldavuse mõiste väljatöötamiseks? On selge, et arvutatav funktsioon peaks monotoonselt säilitama kogu sisenditeabe suurenemise: (f (x) sqsubseteq f (y)) igal ajal (x \ sqsubseteq y). Täpsemalt, kitsad domeenid, mille jaoks (f (bot_D) = \ bot_E) on monotoonsed, hõlmavad ranged funktsioonid (f: D \ kuni E).

Vaatleme domeeni ({ {0,1 }} ^ \ infty), mille elemendid on piiratud ja lõpmatuid bitijadasid (0,1), kus (u \ sqsubseteq v), kui kumbki (u) on lõpmatu ja (u = v) või (u) on piiratud ja (u) on (v) eesliide. Millised omadused peaksid kehtima arvutatava funktsiooni kohta, võttes argumentidena lõpmatu bittide jada ({ langle b_1, b_2, b_3, \ ldots \ rangle})? Võtame näitena funktsiooni (textit {search}: { {0,1 }} ^ \ infty \ kuni { mathbb {B}} _ \ bot), mille väärtus on ({ textit {tt }}), kui (u { {0,1 }} ^ \ infty) korral esineb (1) vähemalt korra (u), vastasel juhul (bot). Mõelge jaole ({ langle b_1, b_2, b_3, \ ldots \ rangle}) kui ühele elemendile korraga: selles protsessis saadud esialgsed segmendid on järjestus ({ { 0,1 }} ^ \ infty),[{ langle \ rangle} sqsubseteq { langle b_1 \ rangle} sqsubseteq { langle b_1, b_2 \ rangle} sqsubseteq { langle b_1, b_2, b_3 \ rangle} sqsubseteq \ ldots) having ({ langle b_1, b_2, b_3, \ ldots \ rangle}) limiidina (st väikseim ülaosa). Monotoonsuse järgi on meil vastav kasvav väärtusahel) textit {search} ({ langle \ rangle}) sqsubseteq \ textit {search} ({ langle b_1 \ rangle}) sqsubseteq \ textit {search} ({ langle b_1, b_2 \ rangle}) sqsubseteq \ textit {search} ({ langle b_1, b_2, b_3 \ rangle}) sqsubseteq \ ldots) If (textit {search} ({ langle b_1, b_2, b_3, \ ldots \ rangle}) = { textit {tt}}), siis peab olema piiratud algne segment ({ langle b_1, b_2, \ ldots, b_n \ rangle}), mille jaoks (textit {search} ({ langle b_1, b_2, \ ldots, b_n \ rangle}) = { textit {tt}}),ja see on lõpmatu jada ({ langle b_1, b_2, b_3, \ ldots \ rangle}) funktsiooni kumulatiivne väärtus. Üldiselt peaks arvutataval funktsioonil (f: D \ kuni E) olema (olema monotoonne ja) selle omadusega, et lõplikul hulgal teavet väljundi (f (x)) kohta peab olema juba saada, andes lõpliku sisendis oleva teabe hulk (x). See on samaväärne jätkuvuse mõistega, mille Scott algselt kasutusele võttis oma teoorias domeenide arvutatavate funktsioonide kohta:See on samaväärne jätkuvuse mõistega, mille Scott algselt kasutusele võttis oma teoorias domeenide arvutatavate funktsioonide kohta:See on samaväärne jätkuvuse mõistega, mille Scott algselt kasutusele võttis oma teoorias domeenide arvutatavate funktsioonide kohta:

Definitsioon 2.8 (pidevad funktsioonid). Kui ({ langle D, \ sqsubseteq _D \ rangle}, { langle E, \ sqsubseteq _E \ rangle}) on cpo-d ja (f: D \ kuni E) on monotoonne, (f) on pidev, kui [f (bigsqcup_i x_i) = \ bigsqcup_i f (x_i)) iga suureneva ahela kohta (x_0 \ sqsubseteq x_1 \ sqsubseteq \ ldots \ subseteq D).

Denatsioonilise semantika seisukohast on pidevate funktsioonide (D kuni D) põhiline omadus see, et nad võimaldavad kõige vähem fikseeritud punkti, mille konstrueerimist saab teostada ühtlaselt ja pidevalt:

Teoreem 2.1 (püsifunktsioonide püsiva punkti teoreem) Olgu (f: D \ kuni D) pidev funktsioon ja (x \ in D) oleks selline, et (x \ sqsubseteq f (x)). Siis on element) bigsqcup_ {n \ in { mathbb {N}}} f ^ {(n)} (x)) kõige vähem (y \ sqsupseteq x), nii et (f (y) = y).

Mõiste 2.9. Pideva (f: D \ kuni D) kõige vähem fikseeritud punkt on (D) element, mille määratleb [{ texttt {fix} (f)} = _ { textrm {def}} bigsqcup_ {n \ sisse { mathbb {N}}} f ^ {(n)} (bot).)

Pidevad funktsioonid alates (D) kuni (E), cpo jaoks ({ langle D, \ sqsubseteq _D \ rangle}) e ({ langle E, \ sqsubseteq _E \ rangle}), moodustavad cpo ([D \ kuni E]), järjestatud punktides, määrates väärtuseks (f, g: D \ kuni E): [f \ sqsubseteq g \ Longleftrightarrow \ forall d \ in D. f (d) sqsubseteq _E g (d).) ([D \ kuni E]) on domeen, kui (D) ja (E) on, ja ({ texttt {fix} (cdot)}: [D \ kuni D] kuni D) on pidev. Edasine konsoolide konstrueerimine, mis laieneb ka domeenidele ja mida kasutatakse väga sageli, on kartesi toode: antud juhul, kui krediidiasutused ja investeerimisühingud on (D, E), määratletakse nende karteesiatoode paaride ({ langle d, e \ rangle}), kus (d \ sisse D) ja (e \ sisse E), järjestatud suunaga: ({ langle d, e \ rangle} sqsubseteq { langle d ', e '\ rangle}) ainult siis, kui (d \ sqsubseteq _D d') ja (e \ sqsubseteq _E e '). Saame need konstruktsioonid kategoorilises keeles kokku võtta (Plotkin 1978, Muud Interneti ressursid), öeldes, et kategooria, mille objektid on domeenid ja mille morfismid on pidevad funktsioonid, on karteesia poolt suletud.

2.3.3 PCF pidev semantika

PCF standardtõlgendus koosneb cpos-i perekonnast (D ^ \ sigma) igat tüüpi (sigma) jaoks, kus (D ^ \ texttt {num} = { mathbb {N}} _ { bot}) ja (D ^ \ texttt {bool} = { mathbb {B}} _ { bot}), (D ^ { sigma \ to \ tau} = [D ^ \ sigma \ kuni D ^ \ tau]) ja PCF-i konstandid on loomuliku tõlgendusena sobivat tüüpi rangete pidevate funktsioonidena, näiteks (texttt {cond}: { mathbb {B}} _ { bot} to { mathbb {N}} _ { bot} kuni { mathbb {N}} _ { bot} kuni { mathbb {N}} _ { bot}) tõlgendatakse järgmiselt:) textit { cond} (b) (x) (y) = \ vasakul { alusta {array} {ll} x & \ text {if (b = \ texttt {tt})} \ y & \ text {if (b = \ texttt {ff})} \ \ bot & \ text {if (b = \ bot),} end {array} right.) Lisaks on operaator ({ mathtt { Y} (cdot)}) tõlgendatakse pidevat funktsionaalset ({ texttt {fix} (cdot)}) sobivat tüüpi. Seda tõlgendust käsitleti Scott 1969b) ja Milner 1973.

Võimalus, et (e) võib sisaldada muutujaid (mille tüübid on antud alusega (B)) võivad esineda vabade terminite tõlgendamisel, muutes selle sõltuvaks järgmisest parameetrist, keskkonnast (rho) iga (e) vaba muutuja (x: \ tau) kaardistamine elemendiga (D ^ \ tau) (kui viimane tingimus on täidetud, siis öeldakse, et (rho) austab (B)). Muidugi, keskkond ei ole oluline, kui (e) on suletud.

PCF-i terminite (e: \ sigma) (alusest (B)) standardtõlgendus on siis element ({ lll e \ rll \ rho} in D ^ \ sigma) mis tahes keskkond (rho) selline, et (rho) austaks (B), mis on üles ehitatud struktuurse induktsiooni alusel, tõlgendades rakendust funktsioonirakendusena ja (lambda) - (pidevate) funktsioonide abstraktsioonid. Üldisemalt on tõlgendus pidev, kui iga (D ^ \ sigma) on cpo ja (D ^ { sigma \ to \ tau}) koosneb pidevatest funktsioonidest (D ^ \ sigma \ kuni D ^ \ tau).

PCF-mudel on tõlgendus, mis rahuldab sama tüüpi terminite eeldatavat identiteeti. Jätame PCF-i mudelite üldise iseloomustamise üksikasjad, mille lugejale viidatakse Ongile (1995: sek 3.2) ja Berry, Curien, & Lévy (1985: sek. 4), vaid lihtsalt meelde tuletama näide selle kohta, mida tuleb sellise üldistuse korral arvesse võtta, et lubada tõlgendusi, kus funktsioonitüüpide elemendid ei ole rangelt funktsioonid, peame eeldama rakenduste toimingute perekonda) cdot _ { sigma \ tau}: D ^ { sigma \ to \ tau} times D ^ \ sigma \ to D ^ \ tau) nii et, kui (B \ vdash e_1: \ sigma \ to \ tau) ja (B \ vdash e_2; \ sigma), ({ lll e_1e_2 \ rll \ rho} = { lll e_1 \ rll \ rho} cdot _ { sigma \ tau} { lll e_2 \ rll \ rho} {{{D} ^ { tau}}}). Mudel on tellimust laiendav, kui,kõigi elementide jaoks (f, g {{{D} ^ { sigma \ to \ tau}}}), (f \ sqsubseteq g) ainult siis, kui (f \ cdot x \ sqsubseteq g \ cdot x) kõigi jaoks (x {{{D} ^ { sigma}}}). Mudel on laiend, kui kõigi elementide (f, g \ in {{{{D} ^ { sigma \ to \ tau}}}) korral (f = g) siis ja ainult siis, kui (f \ cdot x = g \ cdot x) kõigi \ jaoks (x \ sisse {{{D} ^ { sigma}}}). Mudeli element (d \ in D ^ \ sigma) on määratletav, kas on olemas suletud tingimusi (e: \ sigma), nii et (d = { lll e \ rll}).\ sigma) selliselt, et (d = { lll e \ rll}).\ sigma) selliselt, et (d = { lll e \ rll}).

2.4 Seotud operatiivse ja denatsionaalse semantikaga

Täieliku abstraktsiooni arutamiseks vajalik üldine seade eeldab järgmiste mõistete tutvustamist:

Definitsioon 2.11 (vaatluslik eeltellimus ja samaväärsus) Arvestades sama tüüpi PC (PC) termineid (e) ja (e ') (sigma), kirjutame (e \ precsim _ { textrm {obs}} e') (loe (e) on vaatluslikult vähem määratletud kui (e ')), kui iga programmi kontekstis (C \ blbr) on augu tüüp (sigma) ja suvalise väärtusega (v), [C [e] opDownarrow v \ \ text {tähendab, et} C [e '] opDownarrow v.) Me ütleme, et (e) ja (e') on vaatluslikult samaväärsed, ja kirjutage (e \ simeq _ { textrm {obs}} e '), kui (e \ precsim _ { textrm {obs}} e') ja (e '\ precsim _ { textrm {obs} } e).

Vaatluste ekvivalentsus on kokkusobivus. PCF-i terminite teise ühilduvuse annab mudeli tähiste võrdsus:

Definitsioon 2.11 (denatsionaalne eeltellimus ja samaväärsus). Arvestades PCF-i termineid (e) ja (e ') sama tüüpi (sigma) aluse (B) suhtes, kirjutame (e \ precsim _ { textrm {den}} e ') if ({ lll e \ rll \ rho} sqsubseteq {{ lll e' \ rll} rho}) kõigi keskkondade jaoks (rho) austades (B). Kirjutame (e \ simeq _ { textrm {den}} e '), kui (e \ precsim _ { textrm {den}} e') ja (e '\ precsim _ { textrm {den}} e).

Ettepanek 2.1 (PCF-i arvutuslik piisavus). Järgmised kaks väidet kehtivad PCF-i standardmudeli kohta ja on samaväärsed:

1. Kõigi kahe sama tüüpi maapinna PCF-i termini (e, e ') puhul tähendab (e \ simeq _ { textrm {den}} e') (e \ simeq _ { textrm {obs}} e ');
2. Maapinnatüübi suletud PCF-i terminite (e) ja seda tüüpi väärtuste (v) korral ({ lll e \ rll} = { lll v \ rll}) ainult siis, kui (e \ opDownarrow v);

Nüüd saame õigustada (bot) intuitiivset tõlgendamist standardmudelis, kus maapinna tüüpe tõlgendatakse tasapinnaliste domeenidena:

Järeldus 2.1. Iga suletud PCF Termin (e) jahvatatud tüüp, (e \ opUparrow) siis ja ainult siis, kui ({ lll e \ rll} = \ bot).

Jaotises 1.3 oleme juba määratlenud (võrrandi) täieliku abstraktsiooni väga üldise mõiste, mis põhineb sünonüümil, st mõistete võrdsel tõlgendamisel. PCF-i puhul, mille kavandatud mudeleid tellitakse osaliselt igat tüüpi, saame määratleda tugevama omaduse:

Definitsioon 2.12 (ebavõrdne täielik abstraktsioon). Pidev mudel ({ langle { {{{{D} ^ { sigma}}} mid \ sigma \ in \ texttt {Types}} }, { lll \ cdot \ rll \ cdot} rangle PCF-i}) on võrdselt täiesti abstraktne, kui suletud tingimuste (e, e ') puhul tähendab (e \ precsim _ { textrm {obs}} e') ({ lll e \ rll} sqsubseteq { lll e '\ rll}).

Defineeritavus on täieliku abstraktsiooni võti, nagu näitab Milneri ja Plotkini järgmine oluline tulemus:

Teoreem 2.2. PCF-i pidev, laiendatav mudel on täielikult abstraktne siis ja ainult siis, kui igat tüüpi (sigma), ({{{D} ^ { sigma}}}) on domeen, mille lõplikud elemendid on määratletavad.

Pöördume nüüd PCF-i standardmudeli täieliku abstraktsiooni omaduste rikke juurde, nagu näitas Plotkin oma klassikalises uuringus (Plotkin 1977):

Ettepanek 2.2. PCF-i standardmudel ei ole kõne järgi nimetamise osas täielikult abstraktne.

Tõend põhineb tähelepanekul, et saame luua PCF-i tüüpe ((texttt {bool} to \ texttt {bool} to \ texttt {bool}) to \ texttt {num}), mis tunnevad ära paralleel- või funktsioon. Täpsemalt kaaluge järgmiselt määratletud “test” tingimusi (T_i), kus (i = {0}, 1):

(lambda f: \ texttt {bool} to \ texttt {bool} to \ texttt {bool.if} (f \ texttt {tt} bot _ { texttt {bool}} texttt {then}) (texttt {if} (f \ bot _ { texttt {bool}} texttt {tt}) texttt {then}) (texttt {if} (f \ texttt {ff ff}) texttt { siis}) (bot _ { texttt {num}}) (texttt {else} i) (texttt {else} bot _ { texttt {num}}) (texttt { else} bot _ { texttt {num}})

Siis, ({ matemaatiline {D} lll T_ {0} rll} \ texttt {por} = {0} neq 1 = { matemaatiline {D} lll T_1 \ rll} \ texttt {por }), kus por on defineeritud tabeliga ((ref {por})), seega (T_ {0} { simeq _ { textrm {den}}} T_1) ei kehti. Ükski PCF-i programmi kontekst ei saa eraldada (T_ {0}) ja (T_1), kuna por pole määratletav. Seda saab näidata, iseloomustades kombineeritult programmi hindamisprotsessist põhjustatud sõltuvussuhteid selle (alam) mõistete hindamisprotsesside vahel, nagu seda teeb Plotkin tegevuste Lemmas (Plotkin 1977: Lemma 4.2). Alternatiivina on võimalik luua arvutuslikult sobivad PCF-i mudelid, mille funktsioonidel on nõrk järjestusomadus (mida käsitleme allpool jaotises 2.5.1) ja kus funktsioon por on seetõttu välistatud:sellekohane täielik ametlik tõend on esitatud juhendis Gunter 1992 (punkt 6.1).

Üks võimalus täieliku abstraktsiooni probleemi lahendamiseks on keele laiendamine: Plotkini (1977) tähelepanuväärne tulemus näitab, et paralleeli lisamine või piisab:

Ettepanek 2.3. Standardmudel on täiesti abstraktne keele PCF suhtes, mida on laiendatud paralleel- või.

Milner (1977) on näidanud, et on olemas täiesti abstraktne PCF-i mudel, võttes suvaliste tingimuste komplekti iga tüübi (sigma) järgi, määratledes vaatluslikult samaväärsed mõisted ja viies lõpule saadud osaliselt tellitud komplekti, muutes selle krediidipiirkonnaks.

Järeldus 2.2. On olemas ainulaadne pidev, järjekorralaiendus, ebavõrdselt täielikult abstraktne PCF-i mudel, kuni isomorfismini.

PCF-i täielik abstraktsiooniprobleem seisneb täielikult abstraktse mudeli moodustavate domeenide klassi ja pidevate funktsioonide otsese kirjelduse leidmises. Selle probleemi lahendamiseks oleks vaja täpset kriteeriumi, et hinnata, kas mudeli kavandatud kirjeldus on rahuldav. Kui nõustuda Jung & Stoughtoni (1993) antud „täpse minimaalse tingimusega, mida peaks täitma täieliku abstraktsiooni probleemi semantiline lahendus”, nimelt võimalusega kirjeldada tõhusalt domeeni (D ^ \ sigma) PCF-i lõpliku versiooni (mille ainus maatüüp on bool), õigustab tagantjärele Loaderi (2001) tagantjärele ebaõnnestunud katsete kirjeldada täielikult abstraktset mudelit nii otsene kirjeldus:

Teoreem 2.3. Finantsse PCF vaatluslik samaväärsus ei ole otsustatav.

Siiski on siiski võimalik, et leitakse intentsionaalselt täielikult abstraktse mudeli otsene kirjeldus (Abramsky jt 2000: 411):

Definitsioon 2.13 (intensiivne täielik abstraktsioon). PCF-i mudel on intensiivselt täiesti abstraktne, kui iga (D ^ \ sigma) on algebraline ja kõik selle kompaktsed elemendid on määratletavad.

Selle täieliku abstraktsiooni probleemi arenguliini jätkamine viib meid mängude semantikani, millest saab järgmise osa teema. Enne seda toome välja peamised katsed mudelit taandada kõrgema järgu järjestikuse arvutuse semantilise iseloomustamise abil.

2.5 Järjestikuse semantika poole

PCF pideva semantika täieliku abstraktsiooni ebaõnnestumise põhjuseks on funktsioonide olemasolu, mille hindamine nõuab paralleelset arvutamist. Kirjeldame nüüd mõnda ettepanekut funktsioonide järjestuse iseloomustamiseks omaduste abil, mis on seotud nende domeenide struktuuriga, milles need on määratletud. See on olnud PCF-i täieliku abstraktsiooniprobleemi lahendamise intensiivse uurimise ala ja mõned sellest tekkinud arusaamad viivad väga loomulikult 3. jaos käsitletud mängumudeliteni. Lisaks on järgmine kokkuvõte katsetest järjestuse iseloomustamine on ka väga huvitav osalise korra keele väljendusjõu demonstreerimine programmeerimiskontseptsioonide semantilises analüüsis.

Intuitiivselt on järjestikune funktsioon see, mille hindamine toimub järjestikku: see tähendab, et selle argumentide hindamist on võimalik ajastada nii, et funktsiooni hindamine lõpeb õige väärtusega; kui ühe hindamine lahkneb, lahkneb kogu hindamine. Selle protsessi igas etapis on argument, mille väärtust on vaja funktsiooni väljundi kohta lisateabe saamiseks. Selle arvutuste põhjusliku struktuuri arvestamiseks semantilisel tasandil peame rikastama domeenistruktuuri nii, et elementide järjekord kajastaks arvutuslike sündmuste toimumist ja nende põhjuslikku järjekorda. See soovitab teist moodust teabe abstraktse mõiste tõlgendamiseks, mis ajendas cpo aksioome jaotises 2.3.1. Nüüd

teave on seotud sündmuste (juhtumitega): nimelt teave sündmuste toimumise kohta. Näiteks ({ mathbb {N}} _ { bot}) korral võib (bot) tähendada, et sündmust ei toimunud ja täisarv (n), võib tähendada, et sündmus toimus täisarvu (n) väljundist (või muul juhul sisendist). (Plotkin 1978, muud Interneti-ressursid)

2.5.1 Stabiilsus

Üks sündmuste tõlgendus peab neid väärtuste loomiseks väljendi hindamisel. See tõlgendus pärineb Berry (1976) välja töötatud rekursiivsete programmide alt üles suunatud arvutamise kontekstist, kus rekursiivne määratlus tõlgitakse graafiks, mis näitab avaldise tulemuste sõltuvust selle subekspressioonide tulemustest. See kontekst soovitab loomulikult sündmuse (x) tekitaja mõistet kui sündmuste kogumit, mis peab toimuma, et (x) juhtuda. Selle tähelepaneku osaliste tellimuste keeles ümber sõnastades määratles Berry (1976):

Definitsioon 2.14 (stabiilsus). Olgu (D_1, \ ldots, D_n, D) lamedad cpo-d ja (f: D_1 \ times \ ldots \ times D_n \ to D) monotoonsed (seega pidevad). Siis on (f) stabiilne, kui iga (vec {x} = { langle x_1, \ ldots, x_n \ rangle} in D_1 \ times \ ldots \ times D_n) jaoks on kordumatu minimaalne element (m (f, x) sqsubseteq \ vec {x}) selliselt, et (f (m (f, \ vec {x})) = f (vec {x})).

On selge, et paralleel- või funktsioon pole stabiilne: väärtus (texttt {por} (bot, { textit {tt}}) = { textit {tt}} = \ texttt {por} ({ textit {tt}}, \ bot)) pole minimaalset produtsenti. Stabiilsete funktsioonide tähelepanuväärne omadus on see, et need võimaldavad luua uue PCF-mudeli, kus ({{{D} ^ { sigma \ to \ tau}}}) on stabiilsete funktsioonide komplekt domeenides, mis tõlgendavad tüübid (sigma) ja (tau), mis on Scotti domeenide, mida nimetatakse dI-domeenideks, täpsustused (Berry 1978). Meie arvates on nende määratluste oluline tulemus järgmine adekvaatsuse tulemus (Gunter 1992: 6. peatükk):

Ettepanek 2.4. PCF-i terminite tõlgendamine dI-domeenide elementidena, kus (D ^ { sigma \ kuni \ tau}) on stabiilsete funktsioonide dI-domeen vahemikust (D ^ \ sigma) kuni (D ^ \ tau) stabiilse järjekorraga, on arvutuslikult piisav PCF-i mudel.

See tulemus täiendab argumenti, mis näitab PCF pideva mudeli täieliku abstraktsiooni ebaõnnestumist jaotise 2.4 lõpus, kui seal kasutatud mitteametlik järjestuse mõiste on vormistatud kui stabiilsus. PCF-i stabiilne mudel on hiljuti osutunud PCF-i laiendamiseks täiesti abstraktseks (Paolini 2006).

2.5.2 Järjestikused funktsioonid

Esimesed järjestuslikkuse definitsioonid, mis tulenevad Vuilleminist (1974) ja Milnerist (1977), väitsid, et (n) ary funktsioonid (f) lamedate domeenide korral on argumendis ({ langle x_1, \ ldots, x_n \ rangle}), kui on (f) järjestusindeks (i), sõltuvalt ({ langle x_1, \ ldots, x_n \ rangle}), nii et iga väljundi suurendamine teave peab suurendama argumendi (i) teavet. Näiteks funktsioon (texttt {cond}: { mathbb {B}} _ { bot} times { mathbb {N}} _ { bot} times { mathbb {N}} _ { bot} kuni { mathbb {N}} _ { bot}) on selles mõttes järjestikune mis tahes sisendkorpuse korral. Tegelikult on selle järjestusindeks asukohas ({ langle \ bot, m, n \ rangle}) 1; selle järjestusindeks asukohas ({ langle { textit {tt}}, m, n \ rangle}) on 2 ja selle järjestusindeks asukohas ({ langle { textit {ff}}, m, n \ rangle}) on 3. Funktsioonil (texttt {por}: { mathbb {B}} _ { bot} korda { mathbb {B}} _ { bot} kuni { mathbb {B }} _ { bot}) sisendis ({ langle \ bot, \ bot \ rangle}).

Kuigi kõik järjestikused funktsioonid (üle lamedate domeenide) on stabiilsed, on järjestus rangelt tugevam kui stabiilsus. Näiteks pidev funktsioon alates ({ mathbb {B}} _ \ bot \ times { mathbb {B}} _ \ bot \ times { mathbb {B}} _ \ bot) kuni ({ mathbb {B}} _ \ bot) defineeritakse kui kolme ülesande väikseim pidev laiend [{ langle { textit {tt}}, { textit {ff}}, \ bot \ rangle} mapsto { textit {tt}}, { langle { textit {ff}}, \ bot, { textit {tt}} rangle} mapsto { textit {tt}}, { langle \ bot, { textit { tt}}, { textit {ff}} rangle} mapsto { textit {tt}}.) pole argumendis ({ langle \ bot, \ bot, \ bot \ rangle}), kuid on stabiilne, kuna argumendid ({ langle { textit {tt}}, { textit {ff}}, \ bot \ rangle}, { langle { textit {ff}}, \ bot, { textit {tt}} rangle}, { langle \ bot, { textit {tt}}, { textit {ff}} rangle}) on paarisjärgus.

Järgnevuse semantiliste karakteristikute otsingule lisab tuge järgmine tulemus:

Ettepanek 2.5. Olgu (f: D_1 \ korda \ cdots \ korda D_n \ kuni D) pidev funktsioon, kus (D_i, D) on kas ({ mathbb {N}} _ \ bot) või ({ mathbb {B}} _ \ bot). Siis on (f) järjestikune siis ja ainult siis, kui see on PCF-is määratletav.

2.5.3 Konkreetsed andmestruktuurid ja järjestikused algoritmid

Kui järjestuse adekvaatseks määratlemiseks vajalikud domeenid kirjeldavad arvutuslike sündmuste esinemise põhjuslikke seoseid, siis on vaja oma pilti rikastada, pidades sündmusi paiknevateks, üldistades argumendi koha mõiste Vuillemini ja Milner, mis sõltub funktsiooni esitamisest. See viis konkreetse andmestruktuuri (CD-de) arusaamiseni (Kahn & Plotkin 1993) ja esimese järgu andmete domeenide järjestusteoreetiliste omaduste aksiomatiseerimiseni. Kahn ja Plotkin omandasid nende aksioomidega kirjeldatud domeenide, konkreetsete domeenide, esindatuse teoreemi konkreetse konkreetse andmestruktuuri uurimisprotsessi olekute osas, mis seisneb oleku (x) mis tahes lahtri täitmises lubatud sündmuste komplektidega, mis on juba juhtunud asukohas (x),alustades algsetest tühja olekuga lubatud lahtritest: see sarnaneb teoreemide tõestamisega abstraktses deduktiivsüsteemis, mille reeglid on juhendid. Mõelge motiveeriva näitena lingitud loendile näiteks naturaalarvudest. Esialgse lahtri võib igal ajal täita mis tahes väärtusega (n_1). See sündmus võimaldab loendi teise lahtri, mille siis (ja alles siis) täidetakse kõigi hilisemate lahtritega mis tahes väärtusega (n_2) jne.mis võidakse (ja alles siis) täita mis tahes väärtusega (n_2) ja nii edasi kõigi hilisemate lahtrite korral.mis võidakse (ja alles siis) täita mis tahes väärtusega (n_2) ja nii edasi kõigi hilisemate lahtrite korral.

Pange tähele, et konkreetsete andmestruktuuride raamistik annab vajalikud ideed järjestuse semantilise versiooni rekonstrueerimiseks. Ligikaudu on monotoonne funktsioon (f) olekutest (M) kuni (M ') olekuteni järjestikune (olekus (x)), kui mis tahes väljundlahtri korral (c'), on sisestus lahter (c), mis tuleb täita iga ülemineku korral (x) - (y) nii, et üleminek (f (x)) - (f (y)) täidab (c ') (kui selline (c') on olemas) (Curien 1986: Def. 2.4.5). Lahter (c) on (f) järjestuse indeks (x) jaoks (c ').

Kategooria, mille objektid on konkreetsed andmestruktuurid ja mille morfismid on just määratletud järjestikused funktsioonid, ei ole siiski karteesiaalselt suletud, ja mitte ootamatult. See tähelepanek (lihtsa tõestuse saamiseks vt Amadio & Curien 1998 (teoreem 14.1.12)) takistab selle kategooria kasutamist PCF-i mudelina. Siiski on iga kahe konkreetse andmestruktuuri (M, M ') jaoks võimalik määratleda uus (M \ M'), mille olekud tähistavad järjestikuseid algoritme ja mis on (M) eksponentsiaalne objekt ja (M ') suletud kategoorias, mille morfismid on järjestikused algoritmid (Curien 1986: ptk 2.5). PCF-i mudelateooria üldistused kategoorilisteks mudeliteks võimaldavad meil saada sellest uuest kategooriast PCF-i mudeli, isegi kui selle morfismid ei ole funktsioonid tavalises set-teoreetilises tähenduses. Selgub, et järjestikune algoritmimudel pole laiend, kuna on olemas erinevad PCF-mõisted, mis tähistavad sama pidevat funktsiooni, kuid esindavad siiski eraldiseisvaid algoritme. Vaatleme näiteks kahte järgmist terminit, mis tähistavad sama funktsiooni, kuid erinevaid algoritme:) algab {joondatud} texttt {lror} (x, y) & = \ texttt {kui} x \ texttt {siis} ({ texttt {if} y \ texttt {siis} texttt {tt} texttt {else} x}) & \ quad \ texttt {else} ({ texttt {kui} y \ texttt {siis} texttt {tt} texttt {else} texttt {ff}}) \ \ texttt {rlor} (x, y) & = \ texttt {if} y \ texttt {then} ({ texttt {if} x \ texttt {siis} texttt {tt} texttt {else} y}) & \ quad \ texttt {else} ({ texttt {kui} x \ texttt {siis} texttt {tt} texttt {else} texttt {ff}}). \ end {joondatud}), sisestades semantilisse vealertifikaadid sobivalt (textit {error} _1, \ textit {error} _2),ja terminite tõlgenduste vea leviku omaduse jõustamisel (suurendades seeläbi keele jälgitavust) saab seejärel eristada ülaltoodud mõistetele vastavaid funktsioone: tõlgendamisfunktsioonide (textit {lror}) jaoks selgelt ja (textit {rlor}) meil on) alustame {joondatud} textit {lror} (textit {error} _1, \ textit {error} _2) & = \ textit {error} _1 & \ textit { rlor} (textit {error} _1, \ textit {error} _2) & = \ textit {error} _2 \ end {joondatud}), mis osutab ka võimalusele tõestada selle (mittestandardse) laienduse täielikku abstraktsiooni mudel seoses PCF laiendamisega kontrolloperaatoritega (Cartwright, Curien ja Felleisen 1994).siis saab ülaltoodud mõistetele vastavaid funktsioone eristada: tõlgendusfunktsioonide (textit {lror}) ja (textit {rlor}) tõlkimisfunktsioonide jaoks on meil) alustame {joondatud} textit {lror } (textit {error} _1, \ textit {error} _2) & = \ textit {error} _1 & \ textit {rlor} (textit {error} _1, \ textit {error} _2) & = \ textit { viga} _2 \ end {joondatud}), mis osutab ka võimalusele tõestada selle (mittestandardse) laiendusmudeli täielikku abstraktsiooni seoses PCF-i laiendamisega kontrollioperaatoritega (Cartwright, Curien ja Felleisen 1994).siis saab ülaltoodud mõistetele vastavaid funktsioone eristada: tõlgendusfunktsioonide (textit {lror}) ja (textit {rlor}) tõlkimisfunktsioonide jaoks on meil) alustame {joondatud} textit {lror } (textit {error} _1, \ textit {error} _2) & = \ textit {error} _1 & \ textit {rlor} (textit {error} _1, \ textit {error} _2) & = \ textit { viga} _2 \ end {joondatud}), mis osutab ka võimalusele tõestada selle (mittestandardse) laiendusmudeli täielikku abstraktsiooni seoses PCF-i laiendamisega kontrollioperaatoritega (Cartwright, Curien ja Felleisen 1994).= \ textit {viga} _2 \ end {joondatud}), mis osutab ka võimalusele tõestada selle (mittestandardse) laiendusmudeli täielikku abstraktsiooni seoses PCF-i laiendamisega juhtimisoperaatoritega (Cartwright, Curien ja Felleisen 1994).= \ textit {viga} _2 \ end {joondatud}), mis osutab ka võimalusele tõestada selle (mittestandardse) laiendusmudeli täielikku abstraktsiooni seoses PCF-i laiendamisega juhtimisoperaatoritega (Cartwright, Curien ja Felleisen 1994).

Enne kõrgema astme järjestuse laiendava iseloomustamise otsingu ülevaate jätmist tuleks mainida Bucciarelli & Ehrhard (1994), kes tutvustasid Berry dI-domeenide täpsustamist, toetades tugevalt stabiilse funktsiooni ideed, mis võimaldab neil luua PCF-i laiendusmudel, mis pole täielikult abstraktne. Täieliku abstraktsiooni ebaõnnestumise põhjus sel juhul sõltub asjaolust, et PCF-iga defineeritavad funktsionaalid vastavad laiendusomadustele, mis ebaõnnestuvad, kui funktsioonid on järjestatud stabiilse järjekorra alusel. See oli ka põhjus, mis ajendas pakkuma domeene (Berry 1978), kus funktsioonide stabiilne ja ekstensiivne (= suunaga) järjekord eksisteerivad koos.

2.6 Ajaloolised märkused ja täiendavad lugemised

Programmikeelte denatsionaalse ja operatiivse tõlgendamise vaheliste suhete suures mahus on ette nähtud täieliku abstraktsiooni probleemi. Eriti teedrajav töö rekursiivsete programmide semantika teemal, mille Stanfordis tegi 1970. aastate alguses Zohar Manna ümber kogunenud rühm inimesi, sealhulgas Jean Marie Cadiou, Robin Milner ja Jean Vuillemin, kes suhtlesid ka Gilles Kahniga.

Seotud traditsioon oli üsna abstraktne ka täieliku abstraktsiooni probleemi taustal, nimelt semantiliste mõistete iseloomustamisel, nagu järjepidevus ja järjestus Böhmi puudel põhineva (kirjutamata) (lambda) - kalkulatsiooni süntaktiliste mudelite sees (Balandregt 1984)., peamiselt Lévy ja Berry (vt Berry jt 1985 ja Curien 1992) arvepidamise eest PCR-ide täiesti abstraktsete mudelite otsimise kohta sellel joonel).

PCF täieliku abstraktsiooni põhidokumendid on Milner 1977; Plotkin 1977. Neid võib koos lugeda kui ühtset pilti selle keele semantilisest analüüsist. Sõltumatu lähenemisviis täielikule abstraktsioonile tuli vene loogikult Vladimir Sazonovilt, kes iseloomustas PCF-i määratletavust teatud järjestikuste arvutusstrateegiate klassi järgi (Sazonov 1975, 1976). Tema tööl ei olnud siiski otsest mõju kogu abstraktsiooni probleemi uurimisele ja alles hiljuti on proovitud siduda Sazonovi iseloomustust mänguteoreetiliste lähenemisviisidega (Sazonov 2007).

Teine, täiesti erinev lähenemisviis täielikule abstraktsioonile kasutab pidevat mudeli kvootide eraldamiseks spetsiifilisi loogilisi suhteid. Loogiliste suhete esmakordne kasutamine täieliku abstraktsiooni probleemi kontekstis on Mulmuley 1987, kuid sellest tulenev täielikult abstraktse mudeli konstrueerimine saadakse jõhkra jõuga ja seetõttu pole see täielik abstraktsiooni probleem. Hiljem on Sieber (1992) ja O'Hearn & Riecke (1995) selle tehnika täpsustusi kasutanud, et saada paremini ülevaade täielikult abstraktsete mudelite struktuurist, iseloomustades pideva standardmudeli määratletavaid elemente varieeruvuse abil spetsiaalse variandiga loogilised seosed, mis lõikavad välja järjestikused funktsioonid.

PCF-i täieliku abstraktsiooniprobleemi üksikasjad leiate artiklitest Gunter 1992 (peatükid 5,6), Streicher 2006, Ong 1995, Stoughton 1988 ja Amadio & Curien 1998 (peatükid 6, 12, 14), suurenevas järjekorras keerukus. PCF-i rekursiooniteoreetiliste aspektide rõhuasetust ja selle täielikku abstraktsiooni probleemi käsitletakse üksikasjalikult õpikus (Longley & Normann 2015: 6., 7. peatükk); lühema konto leiate Longley 2001-st (punkt 4).

3. Mängu semantika

3.1 Täielik täielikkus

Teoreem 2.2 toob välja lõplike elementide määratletavuse põhilise rolli PCF-i täielikult abstraktses mudelis, seda aspekti rõhutati hiljuti ajakirjas Curien 2007. Sujuva üleminekuna mängudel põhinevatele formalismidele ja osaliselt pärast subjekti ajaloolist arengut, peatame peagi veel ühe määratletavuse aspekti uurimiseks, mis kerkib arvutamise ja konstruktiivsete loogiliste süsteemide tõestusteooria vahel. See on olnud tähelepanuväärne avastus, et loomulike deduktiivsete tõendite struktuuri, näiteks intuitiivse propositsioonilise kalkulatsiooni implikatiivse fragmendi kohta, kirjeldatakse täielikult lihtsalt trükitud (lambda) - calculus'e mõistetega, kus vormi tõestatav propositsiooniline valem (sigma \ kuni \ tau) loetakse terminitüübina, mis tähistab selle tõestusi. Tegemist on Curry, de Bruijni, Scotti, Läuchli, Lawvere ja Howardile omistatava ettepanekutüübiga kirjavahetusega, mis laieneb palju rikkamatele formaalsetele süsteemidele (selle mõiste ajaloo kohta vt Cardone & Hindley 2009: punkt 8.1).4).

Selle kirjavahetuse olemasolu võimaldab rääkida tõendite semantikast, mis ulatub konstruktiivsete formaalsete tõenditeni trükitud (lambda) - kalkulatsioonide denatsionaalsetes tõlgendustes, ning sellega seoses on mõttekas küsida, kas element (x) mõnest (D ^ \ sigma) trükitud (lambda) mudelis - arvutus on valemi (sigma) mõne tõestuse tõlgendamine. Lisaküsimus küsib, kas (D ^ \ sigma) iga element, mis rahuldab sobivalt valitud omadust, on valemi tõestuse tõlgendamine (sigma). Sobivateks omadusteks võivad olla näiteks invariantsus loogiliste suhete korral, mis on sobivalt määratletud iga (D ^ \ sigma) kohal, nagu näiteks mitmetes Plotkini, Statmani ja teiste tulemuste kokkuvõttes ajakirjas Barendregt, Dekkers ja Statman 2013 (I.3, I). 4). Viimast küsimust võime lugeda nii, et see nõuab täielikku täielikkust selles süsteemis, mida nimetatakse täielikuks terviklikkuseks (Abramsky & Jagadeesan 1994), mille määratlust saab paremini mõista konstruktiivse loogika süsteemide kategoorilises semantikas. Tavaline on selliste süsteemide valemite (A) tõlgendamine sobivate kategooriate objektidena ({ lll A \ rll}) (mathbb {M}) ja jadade tõenditeks (p) (A \ vdash B) kui morfismid (lll p \ rll: \ lll A \ rll \ longrrowar \ lll B \ rll). Kui tavaline täielikkus väidab, et iga kehtiva järgu (A \ vdash B) morfismide komplekt (mathbb {M} ({ lll A \ rll}, { lll B \ rll})) pole tühi, väljendab praegune seade täielikku täielikkust tugevamat nõuet, et iga morfism (f:\ lll A \ rll \ longrrowar \ lll B \ rll) semantilises kategoorias (mathbb {M}) tekib mõne tõestuse tõlgendamise teel, st (f = { lll p \ rll}) mõne järgneva (p) tõestuse jaoks (A \ vdash B). Girardi (1987) mitme lineaarse loogika alamsüsteemi täielik tõestamine on tõestatud, üldise raamistiku leiate Abramsky (2000) alt. Lisaks on ta soovitanud tehnikaid PCF-i mudelite määratluse saavutamiseks, millel on tugev määratletavuse omadus, mida nõuab tahtlik täielik abstraktsioon. Samuti on ta soovitanud tehnikaid PCF-i mudelite määratluse saavutamiseks, millel on intensiivne täielik võtmine nõutavat tugevat määratletavust. Samuti on ta soovitanud tehnikaid PCF-i mudelite määratluse saavutamiseks, millel on intensiivne täielik võtmine nõutavat tugevat määratletavust.

3.2 Koostoimed

PCF-i pideva mudeli täpsustuste kirjelduses, et tagada igat tüüpi lõplike elementide määratletavus, oleme järk-järgult lähenenud arvutamise interaktiivsele selgitusele. Näiteks järjestikuse algoritmi (M \ kuni M ') (Curien 1986: sek 3.4) toiming kasutab välist kutsuvat agenti, mis käivitab sisendrakkudes päringute ja vastuste tsükli, mis viib (võimalusel) emissiooni väljundväärtus. See koosmõju peaks olema arvutamise analüüsis keskne mõiste, eriti seoses täieliku abstraktsiooniga, mis on võib-olla loomulik tulemus operatiivse samaväärsuse määratlemisel võetud vaatluskäsitlusest. Meie lühike mängude semantika ülevaade algab täpselt interaktsiooni kui motivatsiooni üldise mõiste analüüsist mängude esimese vormistamiseni, mis on siiski piisavalt rikas, et pakkuda universumit piiratud tüüpide ja terminite kogumi tõlgendamiseks. Hiljem lisame sellele mängude ja strateegiate määratlusele funktsioonid, mis on vajalikud piirangute väljendamiseks, mis võimaldavad strateegiatel iseloomustada täpselt kõrgema järgu järjestikuseid arvutusi, mis on denatsionaalse semantika eesmärk täieliku abstraktsiooni probleemi abil. Mängude semantika kontseptuaalse tausta praegune ülevaade võlgneb palju Abramsky ja Curieni tööd (Abramsky 1994, 1996, 1997; Curien 2003a). Hiljem lisame sellele mängude ja strateegiate määratlusele funktsioonid, mis on vajalikud piirangute väljendamiseks, mis võimaldavad strateegiatel iseloomustada täpselt kõrgema järgu järjestikuseid arvutusi, mis on denatsionaalse semantika eesmärk täieliku abstraktsiooni probleemi abil. Mängude semantika kontseptuaalse tausta käesolev ülevaade võlgneb palju Abramsky ja Curieni tööd (Abramsky 1994, 1996, 1997; Curien 2003a). Hiljem lisame sellele mängude ja strateegiate määratlusele funktsioonid, mis on vajalikud piirangute väljendamiseks, mis võimaldavad strateegiatel iseloomustada täpselt kõrgema järgu järjestikuseid arvutusi, mis on denatsionaalse semantika eesmärk täieliku abstraktsiooni probleemi abil. Mängude semantika kontseptuaalse tausta käesolev ülevaade võlgneb palju Abramsky ja Curieni tööd (Abramsky 1994, 1996, 1997; Curien 2003a).

Asjakohane koostoime mõiste on eraldatud eraldiseisvana väga viimastel aastatel intensiivselt uuritud väga erinevatest uurimisvaldkondadest pärinevate kaastööde, eriti lineaarse loogika (Girard 1987) ja samaaegsete protsesside teooria tulemusel. Nendes valdkondades kujuneb ettekujutus kompositsioonist kui moodulite interaktsioonist. Toome siin lihtsalt lihtsa näite, kus moodulite kompositsioon “paralleelse kompositsiooni + peitmise” vormis leitakse loodusest, et siduda see idee algusega Hoare (1985) väljatöötatud samaaegsete protsesside semantikas. ning ühtlasi ka esmapilgul lihtsustatud mängude formalism.

Mõelge moodulile (S), millel on neli kanalit märgistusega (a_ \ textrm {sisse}, a_ \ textrm {välja}, r_ \ textrm {sisse}, r_ \ textrm {välja}). Moodul on mõeldud kanalile (a_ \ textrm {out}) kanali kaudu saabuva numbri (n) järeltulija tagastamiseks (a_ \ textrm {in}), seetõttu saab selle käitumist täpsustada järgmiselt:

• (S) võtab sisendsignaali (mathbf {?} _ \ Textrm {sisse}) kanalil (r_ \ textrm {in}), siis
• väljastab kanalil signaali (mathbf {?} _ \ textrm {out}) (r_ \ textrm {out}) ja
• ootab kanalil (a_ \ textrm {in}) väärtust (n) ja pärast selle saamist
• väljastab kanalil (a_ \ textrm {out}) väärtuse (n + 1).

(See koostoimemuster on formaalselt identne käepigistusprotokolliga, mida kasutatakse riistvara kujundamisel komponentide sünkroonimiseks, et vältida signaalide häiretest tulenevaid ohte.) Seda käitumist saab kanalitel kaardistada järgmiselt:

Joonis 1: Järgmise funktsiooni moodul.

kus (ring) tähendab sisendit või üldisemalt mooduli passiivset kaasamist vastavasse toimingusse, samal ajal kui (täpp) tähendab väljundit või aktiivset osalemist toimingus. (S) käitumist saab kirjeldada jälgede abil (Hoare 1985), st sümbolite lõplikke jadasid lõpmatust tähestikust (alpha S = { { mathbf {?} _ \ Textrm {in}, \ mathbf {?} _ \ textrm {out}, n_ \ textrm {in}, m_ \ textrm {out} }}:)) tau S = { { varepsilon, \ mathbf {?} _ \ textrm {in}, \ mathbf {?} _ \ textrm {in} mathbf {?} _ \ textrm {out}, \ mathbf {?} _ \ textrm {in} mathbf {?} _ \ textrm {out} n_ \ textrm {in}, \ mathbf {?} _ \ textrm {in} mathbf {?} _ \ textrm {out} n_ \ textrm {in} n + 1_ \ textrm {out}, \ ldots }}) Kui arvestada veel ühte ((S)) tähestikku (S ') tähestikuga (alpha S' = { { mathbf {?} _ \ Textrm {in} ', \ mathbf {?} _ \ Textrm {out} ', n_ \ textrm {in}', m_ \ textrm {out} '}}) saame koostada (S) ja (S '), tuvastades (= ühendades) kanalid (r_ \ textrm {out}, r_ \ textrm {in}') ja (a_ \ textrm {in}, a_ \ textrm {out} ') ja neid läbivad signaalid, nagu näidatud:) algavad {joondatud} mathbf {?} _ \ textrm {out}, \ mathbf {?} _ \ textrm {in} 'ja \ viib x / \ n + 1_ \ textrm {in}, n + 1_ \ textrm {out}' ja \ viib kuni y \ lõpp {joondatud}) See tähistab moodulite paralleelset koostist, (S \ | S '):\ viibsu y \ lõppu {joondatud}) See tähistab moodulite paralleelset koostist, (S \ | S '):\ viibsu y \ lõppu {joondatud}) See tähistab moodulite paralleelset koostist, (S \ | S '):

Joonis 2

Liitmooduli käitumist kirjeldab jälgede kogum: [{ { varepsilon, \ mathbf {?} _ \ Textrm {in}, \ mathbf {?} _ \ Textrm {in} x, \ mathbf {? } _ \ textrm {in} x \ mathbf {?} _ \ textrm {out} ', \ mathbf {?} _ \ textrm {in} x \ mathbf {?} _ \ textrm {out}' n_ \ textrm {in } ', \ mathbf {?} _ \ textrm {in} x \ mathbf {?} _ \ textrm {out}' n_ \ textrm {in} 'y, \ mathbf {?} _ \ textrm {in} x \ mathbf {?} _ \ textrm {out} 'n_ \ textrm {in}' y n + 2_ \ textrm {out}, \ ldots }}) Sümbolid (x, y) saab nüüd peidetud, tähistades lõppsüsteemi käitumine

Joonis 3

kelle jälgedel on nõutav vorm [{ { varepsilon, \ mathbf {?} _ \ textrm {in}, \ mathbf {?} _ \ textrm {in} mathbf {?} _ \ textrm {out} ', \ mathbf {?} _ \ textrm {in} mathbf {?} _ \ textrm {out} 'n_ \ textrm {in}', \ mathbf {?} _ \ textrm {in} mathbf {?} _ \ textrm {out} 'n_ \ textrm {in}' n + 2_ \ textrm {out}, \ ldots }}.) See näide sisaldab paljusid koostisosi, millel mängude semantika põhineb. Tekib idee süsteemist, mille käitumise kutsub esile tema keskkonnast saabuv taotlus: mänguformaalsuses on need pooldaja ja vastase rollid kahe inimese mängus. Iga mooduli käitumist kirjeldatakse selle võimalike koostoimete jäljena teiste ainetega ja käitumist võib moodustada omapärane rollimuutus, mille käigus moodul, kes mängib süsteemina (ülaltoodud näites,(S), mis kiirgab taotlussignaali kanalil (r_ \ textrm {out})) pannakse käituma keskkonnana seoses (S ') -ga, kui see signaal võetakse vastu sisendina kanalil (r_ \ textrm {in} '). Vaatame, kuidas seda näidet saab üldistada.

3.3 Mängud ja strateegiad

Anname ainult definitsioonid, mis on vajalikud mängude põhikonstruktsioonide mõistmiseks ja kategooria moodustamiseks, järgides Abramsky 1997 ja Hyland 1997, mis sisaldavad ametlikumaid üksikasju ja tõestusi.

3.3.1 Mängud

Definitsioon 3.1 Mängu (G) täpsustamiseks antakse käikude komplekt (M_G), märgistatakse (ell_G) liigutused kas pooldaja käikudena ((P)) või käikudena vastasest ((O)). Lisaks on positsioonide komplekt (P_G), mis on käikude jada, kus: (1) kaks mängijat vahelduvad, alustades (O); (2) kui (s \ in P_G), siis on (s) iga prefiks (s ') ka (P_G).

Näitena kaaluge mängu, mis on seotud alt = "sep mehe ikoon" /> Kuidas seda kirjet tsiteerida.

Vaadake selle sissekande PDF-versiooni SEP-i sõprade veebisaidil.

Otsige seda sisenemisteema Interneti-filosoofia ontoloogiaprojekti (InPhO) alt.

Selle kande täiustatud bibliograafia PhilPapersis koos linkidega selle andmebaasi.

Muud Interneti-ressursid

• Curien, Pierre-Louis, 2006, “Märkused mängude semantika kohta”, kursuse märkused
• Lamarche, François, 1992, “Järjestus, mängud ja lineaarne loogika”, loengust Aarhusi ülikooli CLiCS Symposiumisse 23. – 27. Märtsil 1992.
• Plotkin, Gordon, 1978, “Täielike osaliste tellimuste kategooria: tööriist tähenduste tegemiseks”, loengud, suvekool, Dipartimento di Informatica, Pisa ülikool, Itaalia. Domeenide kordustrükk (1983)
• Joyali tõlge, André (1977) “Märkused kahe mängijaga mängude teooria kohta, tõlkinud Robin Houston, vaata selle tõlke postitatud märkust.