Spil, Fuld Abstraktion Og Fuldstændighed

Indholdsfortegnelse:

Spil, Fuld Abstraktion Og Fuldstændighed
Spil, Fuld Abstraktion Og Fuldstændighed

Video: Spil, Fuld Abstraktion Og Fuldstændighed

Video: Spil, Fuld Abstraktion Og Fuldstændighed
Video: ЛУЧШИЙ ФИНАЛ КВАЛ в ИСТОРИИ! НИКС и КИЧ Комментируют OG vs Tundra | 1-3 Карты | ИНТЕРНЕШНЛ 2021 2024, Marts
Anonim

Indtastningsnavigation

  • Indtastningsindhold
  • Bibliografi
  • Akademiske værktøjer
  • Venner PDF-forhåndsvisning
  • Forfatter og citatinfo
  • Tilbage til toppen

Spil, fuld abstraktion og fuldstændighed

Først offentliggjort tors 12 jan. 2017

Computerprogrammer er bestemte slags tekster. Det er derfor naturligt at spørge, hvad der er meningen med et program, eller mere generelt, hvordan kan vi oprette en formel semantisk redegørelse for et programmeringssprog.

Der er mange mulige svar på sådanne spørgsmål, hver enkelt motiveret af et bestemt aspekt af programmerne. Så for eksempel er det faktum, at programmer skal udføres på en slags computermaskine, anledning til operationel semantik, hvorimod lighederne mellem programmeringssprog med de formelle sprog i matematisk logik har motiveret den denotational tilgang, der fortolker programmer og deres bestanddele ved middel til sætteoretiske modeller.

Hvert af disse konti inducerer sin egen synonymerelation på programmeringssprogets sætninger: i et nøddeskal angiver den fulde abstraktionsejendom, at denotations- og operationelle tilgange definerer den samme relation. Dette er en benchmarkegenskab for en semantisk redegørelse for et programmeringssprog, og dens fiasko for en intuitiv denotationsberetning af et simpelt sprog baseret på lambda-calculus har til sidst ført til forfininger af de tekniske værktøjer til denotational semantik, der kulminerer med spil semantik, delvis inspireret ved de dialogspil, der oprindeligt blev brugt i semantikken i den intuitionistiske logik af Lorenzen og hans skole, og senere udvidet af Blass og andre til at fortolke Girards lineære logik. Denne bro mellem konstruktiv logik og programmering har også antydet stærkere former for forhold mellem semantik og bevisteori, hvor forestillingen om fuldstændighed måske er det mest bemærkelsesværdige tilfælde.

  • 1. Introduktion

    • 1.1 Fortolkninger af programmeringssprog
    • 1.2 Sammensætning
    • 1.3 Programækvivalens og fuld abstraktion
  • 2. Sekventiel beregning af højere orden: det fulde abstraktionsproblem for PCF

    • 2.1 Syntaks af PCF
    • 2.2 Operativ semantik
    • 2.3 Denotational semantik

      • 2.3.1 Typer som domæner
      • 2.3.2 En abstrakt teori om højere typer beregbare funktioner
      • 2.3.3 Kontinuerlig semantik for PCF
    • 2.4 Forbindelse med operationel og denotational semantik
    • 2.5 Mod en sekventiel semantik

      • 2.5.1 Stabilitet
      • 2.5.2 Sekventielle funktioner
      • 2.5.3 Konkrete datastrukturer og sekventielle algoritmer
    • 2.6 Historiske noter og yderligere læsninger
  • 3. Spil semantik

    • 3.1 Fuld fuldstændighed
    • 3.2 Interaktion
    • 3.3 Spil og strategier

      • 3.3.1 Spil
      • 3.3.2 Strategier og deres sammensætning
    • 3.4 Særlige strategier
    • 3.5 Historiske noter og yderligere læsninger
  • Bibliografi
  • Akademiske værktøjer
  • Andre internetressourcer
  • Relaterede poster

1. Introduktion

1.1 Fortolkninger af programmeringssprog

Forestillingen om fuld abstraktion stammer fra Scott-Strachey-metoden til den semantiske analyse af programmeringssprog (Scott & Strachey 1971; Strachey 1966, 1967), også kendt som denotational semantik. Et grundlæggende mål med en denotational semantik for et programmeringssprog ({L}) er at give en kompositionsfortolkning ({ mathcal {M}}: {L} til D) af programfraserne til ({ L}) som elementer i abstrakte matematiske strukturer (domæner) (D).

Vi kan vælge en anden måde at give mening til programmer på grundlag af deres udførelse. Denne operationelle fortolkning er kun defineret på sættet Prog af programmer af ({L}) og involverer definitionen af et passende sæt af programværdier, som er observerbare af ({L}). Hvis udførelsen af program (e) afsluttes med værdien (v), en situation udtrykt af notationen (e / opDownarrow v), er (v) den operationelle betydning af (e). Dette definerer den operationelle fortolkning af programmer som en delvis funktion ({ mathcal {O}}) fra programmer til værdier, hvor ({ mathcal {O}} (e) = v) når (e / opDownarrow v).

Begge fortolkninger inducerer naturlige ækvivalensrelationer på programfraser. I en af dens formuleringer angiver fuld abstraktion sammenfaldet af denotationsækvivalens på et sprog med et induceret af den operationelle semantik. Fuld abstraktion er først defineret i en artikel af Robin Milner (1975), der også afslører de væsentlige begrebsmæssige ingredienser i denotational semantik: kompositionalitet og forholdet mellem observations- og denotationsækvivalens af programmer. Af denne grund kan fuld abstraktion betragtes som et udsigtspunkt i det store landskab inden for semantik af programmeringssprog, og er derfor ganske relevant for kerneproblemerne i filosofien om programmeringssprog (White 2004) og computervidenskab (Turner 2016).

1.2 Sammensætning

Kompositionalitet (Szabó 2013) er et ønskeligt træk ved en semantisk analyse af et programmeringssprog, fordi det tillader en at beregne betydningen af et program som en funktion af betydningen af dets bestanddele. Faktisk, i Milners beretning (se især 1975: sek. 1, 4), gælder sammensætningen endnu mere generelt for computermidler, der er samlet fra mindre ved hjælp af passende sammensætningsoperationer. Disse agenter kan foruden programmer omfatte hardwaresystemer som en computer, der er sammensat af en hukommelse, sammensat efter tur af to hukommelsesregistre og en behandlingsenhed, hvor alle komponenter er computermidler. Dette tillader en at inkludere i et rammesystem, der består af hardware, software og endda af begge dele. Nu,de syntaktiske regler, der induktivt definerer de forskellige kategorier af sætninger i et programmeringssprog giver os mulighed for at betragte ({L}) som en algebra af programfraser, hvis signatur bestemmes af disse regler. En beretning om kompositionalitet, der er specielt egnet til den nuværende indstilling (Szabó 2013: s. 2), identificerer en sammensætningstolkning af programmer med en homomorfisme fra denne algebra til domænet for denotationer, der associerer med hver operation i programalgebraen en tilsvarende semantisk operation om betegnelser.2) identificerer en sammensætningstolkning af programmer med en homomorfisme fra denne algebra til domænet af denotationer, der er knyttet til hver operation i algebraen til programmer en tilsvarende semantisk operation på denotationer.2) identificerer en sammensætningstolkning af programmer med en homomorfisme fra denne algebra til domænet af denotationer, der er knyttet til hver operation i algebraen til programmer en tilsvarende semantisk operation på denotationer.

Overvej som et eksempel et simpelt imperativsprog, hvis programmer (mathtt {c}) betegner tilstandstransformationer ({ mathcal {M}} (mathtt {c}): / Sigma / til / Sigma). Blandt operationerne på programmer på dette sprog er der sekventiel sammensætning, der bygger et program (mathtt {c} _1; / mathtt {c} _2) fra programmer (mathtt {c} _1) og (mathtt {c} _2). Den påtænkte operationelle betydning af dette program er, at hvis (mathtt {c} _1; / mathtt {c} _2) udføres fra en tilstand (sigma / in / Sigma), udfører vi først (mathtt {c} _1) startformtilstand (sigma). Hvis udførelsen ophører, får vi en tilstand (sigma '), hvorfra vi starter udførelsen af (mathtt {c} _2), når udførelsen afsluttes, en tilstand (sigma' '). Den sidstnævnte stat er den tilstand, der opnås ved henrettelsen af (mathtt {c} _1;\ mathtt {c} _2) fra tilstand (sigma). Fra et denotationsmæssigt synspunkt har vi en operation af sammensætning af tilstande som funktioner (Sigma / til / Sigma), og den sammensatte fortolkning af vores program er givet ved følgende identitet, der skal læses som en klausul i en definition af ({ mathcal {M}}) ved induktion i strukturen af programmer: [{ mathcal {M}} (mathtt {c} _1; / mathtt {c} _2) = { mathcal { M}} (mathtt {c} _2) circ { mathcal {M}} (mathtt {c} _1)) eller, mere eksplicit, for enhver tilstand (sigma): [{ mathcal {M}} (mathtt {c} _1; / mathtt {c} _2) (sigma) = { mathcal {M}} (mathtt {c} _2) ({ mathcal {M}} (mathtt {c} _1) (sigma)).) Da de fleste programmeringssprog har flere kategorier af sætninger (for eksempel udtryk, erklæringer, instruktioner), vil algebras i programmer generelt være multi-sorteret, med en sortering for hver kategori af sætninger. Denotational semantik forfølger systematisk ideen om at sammensætte sammensætning til hvert programfrase en betegnelse af den matchende sortering (se Stoy 1977 for en tidlig beretning).

1.3 Programækvivalens og fuld abstraktion

Eksistensen af en fortolkning af et programmeringssprog ({L}) fremkalder på en standard måde en ækvivalens af programfraser:

Definition 1.1 (Denotational ækvivalens). I betragtning af to programfraser (e, e ') er de denotationsmæssigt ækvivalente, skrevet (e / simeq _ { mathcal {M}} e'), når ({ mathcal {M}} (e) = { mathcal {M}} (e ')).

Hvis ({ mathcal {M}}) er sammensat, er ({ simeq _ { mathcal {M}}}) en kongruens over algebraen i programmer, hvis afledte operation, dem opnået ved sammensætning af operationer af underskriften kaldes sammenhænge. En kontekst (C / blbr) repræsenterer en programfrase med et "hul", der kan udfyldes af programfraser (e) af passende type for at give programfrasen (C [e]). Ved hjælp af kontekster kan vi let karakterisere sammensætningen af en semantisk kortlægning:

Forslag 1.1. Hvis ({ mathcal {M}}) er sammensat, er det for alle sætninger (e, e ') og alle sammenhænge (C / blbr):) tag {1} label {composality} {e / simeq _ { mathcal {M}} e '} Højre højre {C [e] simeq _ { mathcal {M}} C [e']}.)

Denne formulering fremhæver et andet værdifuldt aspekt af kompositionalitet, nemlig referencemæssigt gennemsigtighed i alle kontekster, ligesom deres ekstensivitet er ækvivalent: denotationsækvivalente sætninger kan substitueres i enhver sammenhæng, hvorved denoterede sætning ikke ændres. Implikationen ((ref {composality})) angiver især, at ({ simeq _ { mathcal {M}}}) er en kongruens. For at sammenligne denotational og operationel kongruens, må vi derfor skære en kongruens ud af den naive operationelle ækvivalens, der er defineret ved at indstille (e / sim e '), hvis og kun hvis ({ mathcal {O}} (e) = { mathcal {O}} (e ')). Dette kan gøres ved at udnytte programkontekster (C / blbr), der repræsenterer et program med et "hul", der kan udfyldes af programfraser (e) af passende type for at give et komplet program (C [e]).

Definition 1.2 (Observationsækvivalens) I betragtning af to programfraser (e, e ') er de observationsækvivalenter, skrevet (e / simeq _ { mathcal {O}} e'), når, for alle programkontekster (C / blbr) og alle programværdier (v): [C [e] opDownarrow v / \ tekst {hvis og kun hvis} C [e '] opDownarrow v.)

Observationsækvivalens er derefter en kongruens over algebraen for programfraser, og faktisk er det den største kongruens indeholdt i (sim). Fra det generelle synspunkt på beretningen om Milner (1975), som vi følger nøje, repræsenterer konteksten af et databehandlingsagent et af dets mulige miljøer. Hvis vi vedtager princippet om, at "åben adfærd udgør hele betydningen af et databehandlingsagent" (Milner 1975: 160), repræsenterer sammenhængen intuitivt de iagttagelser, som vi kan foretage af computermedlets opførsel. For programmer er observerbare værdier værdier, så observationsækvivalens identificerer sætninger, der ikke kan skelnes ved hjælp af observationer, hvis resultater er forskellige værdier. En konsekvens af Milners metodologiske princip er, at et computermiddel bliver en

transducer, hvis indgangssekvens består af forespørgsler fra eller svar fra dets miljø, og hvis udgangssekvens består af forespørgsler om eller svar på dets miljø. (Milner 1975: 160)

En opførsel af et databehandlingsagent tager formen af en dialog mellem agenten og dets miljø, en metafor, der vil være kernen i spillet teoretiske tilgange til semantik, der skal drøftes i afsnit 3. Denne adfærdsmæssige holdning, der har sine rødder i arbejdet med ingeniører på finite state-enheder er Milner også udvidet til en metode til modellering af samtidige systemer med det formål

til at beskrive et samtidigt system fuldt ud til at bestemme nøjagtigt, hvilken adfærd der vil blive set eller oplevet af en ekstern observatør. Tilnærmelsen er således grundigt ekstensiv; to systemer kan ikke skelnes, hvis vi ikke kan skille dem fra hinanden uden at trække dem fra hinanden. (Milner 1980: 2)

Derudover er systemets og observatørens roller symmetriske, i en sådan grad, at

vi vil gerne repræsentere observatøren som en maskine, derefter for at repræsentere den sammensatte observatør / maskine som en maskine, for derefter at forstå, hvordan denne maskine opfører sig for en ny observatør. (Milner 1980: 19)

Mens observationsækvivalens er blind for det indre detaljer i et databehandlingsagent, men kun observerer de mulige interaktioner med det miljø, hvori det deltager, tager denotationsækvivalens i betragtning af den interne struktur af et databehandlingsagent og på en sammensat måde syntetiserer dets beskrivelse fra dets interne dele. Forestillingen om fuld abstraktion er netop beregnet til at fange sammenfaldet mellem disse dobbeltperspektiver:

Definition 1.3 (Fuld abstraktion). En denotational semantik ({ mathcal {M}}) er fuldstændig abstrakt med hensyn til en operationel semantik ({ mathcal {O}}) hvis de inducerede ækvivalenser ({ simeq _ { mathcal {M}} }) og ({ simeq _ { mathcal {O}}}) falder sammen.

Som et værktøj til at undersøge programegenskaber kan fuld abstraktion ses som en komplementære egenskab for denotational semantik: enhver ækvivalens af programmer, der kan bevises operationelt, kan også bevises på denotationsmidler. Tilsvarende vil et denotationsbevis for, at to udtryk ikke er ækvivalente, være nok til at vise, at de ikke kan udskiftes i enhver programkontekst.

Fuld abstraktion fungerer også som et kriterium til vurdering af en oversættelse (vartheta) fra et sprog ({L} _1) til et (ikke nødvendigvis anderledes) sprog ({L} _2), forudsat at de to sprog har de samme sæt observerbare ting, siger Obs (Riecke 1993). Derefter er (vartheta) fuldstændig abstrakt, hvis observationsækvivalens (defineret med hensyn til Obs) af (e, e '\ i {L} _1) er ækvivalent med observationsækvivalensen af (vartheta (e), / vartheta (e ')). Eksistensen af fuldstændig abstrakt oversættelse mellem sprog kan bruges til at sammenligne deres udtrykskraft efter et forslag af (Mitchell 1993; Riecke 1993): ({L} _1) er ikke mere udtryksfuld end ({L} _2) hvis der er en fuldstændig abstrakt oversættelse af ({L} _1) til ({L} _2).

Før man går videre med denne generelle introduktion til fuld abstraktion og relaterede forestillinger inden for programmering af sprogs semantik, for at vise den brede relevans af disse forestillinger, er det interessant at bemærke, at der er en meget generel ramme, hvor det er muligt at undersøge den fulde abstraktionsejendom, som er foreslået af nylige undersøgelser af sammensætning på naturlige og kunstige sprog af Hodges (2001) og andre. I denne indstilling er fuld abstraktion forbundet med problemet med at finde en sammensat udvidelse af en semantisk fortolkning af et undersæt (X) af et sprog (Y) til en fortolkning af hele sproget via Freges kontekstprincip (se se Janssen 2001 om dette), hvor han siger, at betydningen af et udtryk i (Y) er det bidrag, det yder til betydningen af udtrykket af (X), der indeholder det. I den originale formulering af Frege (X) var sætningen sæt og (Y) sættet af alle udtryk, mens i programmeringsteori (X) er det sæt programmer, (Y) sættet af alle programfraser.

En svækkelse af definitionen af fuld abstraktion repræsenterer et væsentligt tilstrækkelighedskrav til en denotational fortolkning af et sprog:

Definition 1.4 (Computational adequacy). En denotational semantik ({ mathcal {M}}) er beregningsmæssigt tilstrækkelig med hensyn til en operationel semantik ({ mathcal {O}}) hvis, for alle programmer (e) og alle værdier (v) [{ mathcal {O}} (e) = v / \ tekst {hvis og kun hvis} { mathcal {M}} (e) = { mathcal {M}} (v).)

En ækvivalent formulering af beregningstilstrækkelighed gør det muligt at fremhæve dens forhold til fuld abstraktion:

Forslag 1.2. Antag, at ({ mathcal {M}}) er en sammensat denotational fortolkning, således at ({ mathcal {O}} (e) = v) indebærer ({ mathcal {M}} (e) = { mathcal {M}} (v)). De følgende to udsagn er ækvivalente:

  1. ({ mathcal {M}}) er beregningsmæssigt tilstrækkelig med hensyn til ({ mathcal {O}});
  2. for alle to programmer (e, e '\ i { texttt {Prog}}), [e / simeq _ { mathcal {M}} e' / \ tekst {hvis og kun hvis} e / simeq_ { mathcal {O}} e ')

Mens definitionen af den fulde abstraktionsejendom er ligetil, har fuldstændigt abstrakte modeller til meget naturlige eksempler på programmeringssprog vist sig undvikende, hvilket har ført til et fuldstændigt abstraktionsproblem. I vores diskussion af fuld abstraktion vil vi hovedsageligt koncentrere os om det fulde abstraktionsproblem for sproget PCF (Programmeringssprog for Computable Functions, Plotkin 1977), en simpelt indtastet (lambda) - beregning med aritmetiske primitiver og en fastpunktskombinator til alle typer foreslået i Scott 1969b. Dette sprog er vigtigt, fordi det inkluderer de fleste af de programmeringsfunktioner, som semantisk analyse skal klare: funktioner af højere orden, typer og rekursion, med reduktionsregler, der giver en abstrakt ramme for eksperimentering med flere evalueringsstrategier. Desuden,PCF er også en model til andre udvidelser af simpelt indtastet (lambda) - beregning, der bruges til at eksperimentere med programmeringsfunktioner, ligesom den idealiserede algol fra Reynolds (1981). Bestræbelserne på at løse det fulde abstraktionsproblem for PCF bidrog som en bivirkning til den systematiske udvikling af et sæt matematiske teknikker til semantisk analyse, hvis brugbarhed går ud over deres originale anvendelser. Vi vil beskrive nogle af dem i afsnit 2, der er afsat til den semantiske analyse af PCF baseret på delvist ordnede strukturer, de domæner introduceret af Dana Scott (1970), som vi undersøger i afsnit 2.3. Den tekniske udvikling inden for teorien om domæner og også inden for det nye forskningsområde, der fokuserer på Girards lineære logik (Girard 1987), har ført til spil-semantik (Abramsky, Jagadeesan, & Malacaria 2000; Hyland & Ong 2000),som nu betragtes som et levedygtigt alternativ til standard denotational semantik baseret på domæner. Det er denne tilgang, vi afsætter Afsnit 3, der forsøger at give tilstrækkelige detaljer til at orientere læseren i en omfattende og stadig voksende litteratur, der dokumenterer anvendelser af spil til fortolkningen af et bredt spektrum af programmeringssprogsfunktioner.

2. Sekventiel beregning af højere orden: det fulde abstraktionsproblem for PCF

Det komplette abstraktionsproblem har vist sig specielt svært for en version af simpelt indtastet (lambda) - beregning med aritmetiske primitiver kaldet PCF (Programming with Computable Functions) (Plotkin 1977), et legetøjsprogrammeringssprog baseret på Logic for Computable Functions of Scott (1969) og Milner (1973). I dette afsnit introducerer vi (en version af) sproget med dets operationelle og denotationelle semantik og skitserer, hvordan det fulde abstraktionsproblem opstår for dette sprog. Problemet har været et af de største bekymringer ved den teoretiske undersøgelse af programmeringssprog i cirka to årtier, fra dets oprindelige formulering i landemærkepapirerne (Milner 1977; Plotkin 1977) til de første løsninger, der blev foreslået i 1993 (Abramsky et al. 2000; Hyland & Ong 2000) bruger spil semantik, som se Afsnit 3.

2.1 Syntaks af PCF

PCF er et sprog baseret på simpelt indtastet (lambda) - beregning udvidet med aritmetiske og boolske primitiver, og dens typesystem er defineret i overensstemmelse hermed:

Definition 2.1 (PCF-typer). Sættet Typer af typer PCF defineres induktivt som følger

  • jordtyper num (for termer, der repræsenterer naturlige tal), bool (for termer, der repræsenterer boolske værdier) er typer,
  • hvis (sigma, / tau) er typer, er også ((sigma / til / tau)) en type.

Parhesjoner vil blive udeladt når det er muligt med den konvention, de knytter til højre, så en type (sigma_1 / til / cdots / sigma_n / to / tau) svarer til ((sigma_1 / to (sigma_2) til (cdots (sigma_n / to / tau) cdots))))

PCF-udtryk er udtryk for simpelt indtastet (lambda) - beregning udvidet med følgende aritmetiske konstanter af den angivne type:

  • en konstant ({0}: / texttt {num}), der repræsenterer det naturlige tal 0;
  • en konstant (texttt {succ}) af typen (texttt {num} til / texttt {num}), der repræsenterer efterfølgerfunktionen i forhold til naturlige tal;
  • en konstant (texttt {pred}) af typen (texttt {num} til / texttt {num}), der repræsenterer foregående funktion over naturlige tal;
  • konstanter (texttt {tt}) og (texttt {ff});
  • konstanter af typen (texttt {bool} til / texttt {num} til / texttt {num} til / texttt {num}) og (texttt {bool} til / texttt {bool} til / texttt {bool} til / texttt {bool}) for betingelser af henholdsvis type num og type bool: disse er begge skrevet som ({ texttt {if} cdot / texttt {derefter} cdot / texttt {else} cdot}), og vi lader kontekst tydeliggøre, hvad der er den tilsigtede type af resultatet;
  • en konstant (texttt {nul?}) til testen for nul af typen (texttt {num} til / texttt {bool});
  • et unært funktionssymbol ({ mathtt {Y} (cdot)}) for fastpunktskombinatoren, hvor ({ mathtt {Y} (e)}: / sigma) for enhver (e: / sigma / til / sigma).

Betegnelser er induktivt bygget efter regler, der gør det muligt at udlede domme af formen (B / vdash e: / sigma), hvor de angiver, at udtrykket (e) er af typen (sigma) under antagelse af, at variabler der forekommer gratis i (e) får unikke typer i en basis (B) af formen [{ {x_1: / sigma_1, / ldots, x_k: / sigma_k }}.) Reglen for opbygning PCF-vilkår er derfor inferensregler for sådanne vurderinger. Der er især regler for indtastede konstanter, for eksempel på ethvert grundlag (B) er der en dom (B / vdash / texttt {zero?}: / Texttt {num} to / texttt {bool}), og vi har regler for indtastet (lambda) - abstraktioner) frac {B, x: / sigma / vdash e: / tau} {B / vdash { lambda x: / sigma {,. \,} e}: / sigma / til / tau}) og applikationer) frac {B / vdash e_1: / sigma / til / tau / qquad B / vdash e_2: / sigma} {B / vdash e_1 e_2:\ tau}) og en regel for fastpunktsoperatøren:) frac {B / vdash e: / sigma / til / sigma} {B / vdash { mathtt {Y} (e)}: / sigma}.)

2.2 Operativ semantik

Et PCF-program er en lukket periode af jordtype. Vi specificerer, hvordan programmer skal udføres ved at definere en evalueringsrelation (e / opDownarrow v) mellem lukkede vilkår (e) og værdier (v), hvor værdierne er konstanterne og abstraktionerne af formen ({ lambda x: / sigma {,. \,} e}). Værdier af grundtypen bool er især (texttt {tt}, / texttt {ff}), og værdierne for jordtypenum er ({0}) og alle udtryk i formen) mathtt {n} = / underbrace { texttt {succ} (ldots / texttt {succ}} _ {n} ({0}) ldots).) Evaluering defineres af sager i henhold til strukturen af udtryk, ved hjælp af af inferensregler for vurderinger af formularen (e / opDownarrow v). Disse regler angiver, hvordan resultatet af evalueringen af et udtryk afhænger af resultatet af evalueringen af andre termer, de eneste aksiomer med formen (v / opDownarrow v) for hver værdi (v). Der er for eksempel en regel) frac {e / opDownarrow v} {{ texttt {succ} e} opDownarrow { texttt {succ} v}}), der siger, at hvis resultatet af evalueringen af (e) er (v), derefter er resultatet af evalueringen af ({ texttt {succ} e}) ({ texttt {succ} v}). Tilsvarende kan vi beskrive evalueringen af de andre konstanter. Evalueringen af et udtryk med formularen (e_1 / e_2) foregår som følger: først (e_1) evalueres; Hvis evalueringen afsluttes med værdien (v '), fortsætter evalueringen af (e_1 / e_2) med evalueringen af (v' / e_2); hvis dette slutter med værdien (v), er dette værdien af (e_1 / e_2), formelt) frac {e_1 / opDownarrow v '\ qquad v' / e_2 / opDownarrow v} {e_1 / e_2 / opDownarrow v}) For en værdi af formularen ({ lambda x: / sigma {,. \,} e_1}),dens anvendelse på et udtryk (e_2) har den (hvis nogen) opnåede værdi ved at evaluere udtrykket (e_1 [e_2 / x]) resulterende ved at substituere (e_2) i alle frie forekomster af (x) i (e_1):) frac {e_1 [e_2 / x] opDownarrow v} {({ lambda x: / sigma {,. \,} e_1}) e_2 / opDownarrow v}.) Disse implementere en call-by-name evalueringsstrategi: i en applikation skal udtrykket i funktionsposition evalueres fuldstændigt inden udtrykket i argumentposition, som derefter sendes som faktisk parameter. Fastpunktkombinatoren er afgørende for kodning af rekursive definitioner. Evalueringen heraf er beskrevet af reglen) frac {e ({ mathtt {Y} (e)}) opDownarrow v} {{ mathtt {Y} (e)} opDownarrow v}) som er den eneste regel, hvis forudsætning involverer evaluering af et større udtryk end det, der skal evalueres:dette er grunden til, at definitionen af evalueringsrelationen ikke kan reduceres til strukturel induktion.

Vi vil være specielt interesserede i situationer, hvor evalueringen af et udtryk (e) ikke har en værdi; i disse tilfælde siger vi, at (e) afviger og skriver (e / opUparrow). Det er i tilstedeværelsen af divergerende udtryk, som årsagsstrukturen i evalueringsprocessen udsættes. Det oprindelige eksempel er faktisk et udtryk, der divergerer i en meget stærk forstand:

Definition 2.2 (Ikke defineret). For enhver jordtype (gamma) skal du definere (Omega: / gamma) som [{ mathtt {Y} ({ lambda x: / gamma {,. \,} X})}]

Ved at inspicere evalueringsreglerne ser vi, at den eneste mulige evalueringsproces giver anledning til en uendelig regress, derfor (Omega / opUparrow).

Vi kan definere de sædvanlige boolske operationer ved hjælp af den betingede operatør som i de følgende eksempler:) start {align} tag {2} texttt {og} & = { lambda x: / texttt {bool}, y: / texttt {bool} {,. \,} { texttt {if} x / texttt {derefter} y / texttt {else} texttt {ff}}}. / label {etbivalente} / \ tag {3} texttt {eller} & = { lambda x: / texttt {bool}, y: / texttt {bool} {,. \,} { texttt {if} x / texttt {derefter} texttt {tt} texttt {else} y}} label {velbivalente} end {align}) med de sædvanlige sandhedstabeller. Vi skal dog nu tage hensyn til muligheden for afvigelse af evalueringsprocessen, f.eks. I et udtryk som (texttt {eller} (Omega, / texttt {tt})), derfor udvider vi den sædvanlige sandhed tabeller ved at tilføje en ny boolesk værdi, der repræsenterer fravær af information, (bot) (læst som "udefineret") til (texttt {tt}) og (texttt {ff}),som værdien af udtrykket (Omega). Her er det første argument, der skal evalueres, det til venstre, og hvis evalueringen af dette afviger, afviger hele evalueringsprocessen. Overvej nu en operatør por, hvis fortolkning er givet af tabellen) tag {4} label {por} begin {array} {r | lll} texttt {por} & / textit {tt} & / textit {ff } & / bot \\\ hline / textit {tt} & / textit {tt} & / textit {tt} & / textit {tt} / \ textit {ff} & / textit {tt} & / textit {ff} & / bot \\ / bot & / textit {tt} & / bot & / bot / end {array}) I dette tilfælde (texttt {por} (texttt {tt}, / Omega) = / texttt { por} (Omega, / texttt {tt}) = / texttt {tt}): dette er parallellen - eller som spiller en central rolle i det komplette abstraktionsproblem for PCF. Det viser sig, at det ikke kan defineres ved nogen PCF-udtryk, netop på grund af dens parallelle karakter. For at udføre en semantisk analyse af PCF har vi brug for en teori om datatyper med delvise elementer og funktioner over dem, der understøtter en abstrakt form for rekursiv definition gennem faste punkt-ligninger: det er dette, der opnås i Scotts teorien om domæner, det originale matematiske grundlag for denotational semantik af programmeringssprog som udtænkt af Strachey (1966, 1967).

2.3 Denotational semantik

2.3.1 Typer som domæner

Hvad er de generelle strukturelle egenskaber ved et rum med delvise data? Den matematiske teori om beregning udarbejdet af Dana Scott (1970) er et svar på dette spørgsmål, der tager delvist ordnede sæt generisk kaldte domæner som grundlæggende strukturer. Den delvise rækkefølge af et domæne beskriver en kvalitativ opfattelse af "information" båret af elementerne. I en sådan ramme er det naturligt at genere divergens ved at indføre et nyt element (bot), der repræsenterer fravær af information. Når (x / sqsubseteq y) i denne delvise rækkefølge,

(y) er i overensstemmelse med (x) og er (muligvis) mere nøjagtig end (x) ldots]), således (x / sqsubseteq y) betyder, at (x) og (y) vil tilnærme sig den samme enhed, men (y) giver flere oplysninger om det. Dette betyder, at vi skal tillade "ufuldstændige" enheder, som (x), der kun indeholder "delvis" information. (Scott 1970: 171)

De resulterende delvist bestilte sæt skal også have den egenskab, at sekvenser af tilnærmelser, især uendelige kæder (x_0 / sqsubseteq x_1 / sqsubseteq / ldots) skal konvergere til en grænse, der indeholder informationen kumulativt leveret af (x_i). Den samme struktur udnyttes også i Kleene's bevis for den første rekursionsteorem i Kleene 1952 (sek. 66, 348–50), og giver mulighed for at definere en forestilling om kontinuerlig funktion med hensyn til bevarelse af grænser.

Definition 2.3 (Fuldfør delvise ordrer). En komplet delordre (cpo) er et delvist ordnet sæt ({ langle D, / sqsubseteq / rangle}) med et mindstelement (bot), og sådan at enhver stigende kæde (x_0 / sqsubseteq x_1 / sqsubseteq / ldots) af elementer i (D) har mindst øvre grænse (bigsqcup_n x_n).

Givet ethvert sæt (X), skriver vi (X _ { bot}) for det sæt (X / cup { bot }), der opnås ved at tilføje et nyt element (bot). Det er naturligt at bestille elementerne i (X _ { bot}) i henhold til deres informationsmængde ved at indstille til (x, y / i X _ { bot}),) begynde {justeret} x / sqsubseteq y & / Longleftrightarrow (x = / bot / \ text {eller} x = y). / end {lined}) Delvist ordnede strukturer i formularen (X_ / bot) kaldes flade domæner, blandt hvilke vi har (texttt {bool} = { {{ textit {tt}}, { textit {ff}} }} _ / bot) og (texttt {num} = { mathbb {N }} _ / bot), der vil blive brugt til at fortolke jordtyperne af PCF.

Et generelt krav til domæner er, at hvert element er en grænse for dets begrænsede tilnærmelser for en forestilling om finhed (eller kompakthed), der kan formuleres fuldstændigt med hensyn til den delvise ordensstruktur:

Definition 2.4 (Endelige elementer i en cpo). Hvis (D) er en cpo, er et element (d / i D) endeligt, hvis der for hver stigende kæde (x_0 / sqsubseteq x_1 / sqsubseteq / ldots) [d / sqsubseteq / bigsqcup_n x_n / Longrightarrow / eksisterer x_i / \ venstre (d / sqsubseteq x_i / højre).) For (d / i D) angiver notationen (mathcal {A} (d)) sæt af begrænsede elementer nedenfor (d); (mathcal {A} (D)) er sættet med begrænsede elementer i (D). Endelige elementer kaldes også kompakte.

Bemærk, at begrænsede delmængder af et sæt (X) er nøjagtigt de begrænsede elementer i det komplette gitter af undergrupper af (X). Det er også nyttigt at bemærke, at denne definition kun delvist matcher vores intuition: overveje for eksempel det endelige element (infty + 1) i cpo [0 / sqsubseteq 1 / sqsubseteq 2 / sqsubseteq / cdots / sqsubseteq / infty / sqsubseteq / infty + 1.)

Definition 2.5 (Algebraisk cpo). A (D) er algebraisk, hvis der for hver (d / i D) er en stigende kæde (x_0 / sqsubseteq x_1 / sqsubseteq / ldots) af begrænsede tilnærmelser af (d) sådan at [d = / bigsqcup_n x_n.) Hvis (D) er algebraisk, siger vi, at de endelige elementer danner et grundlag for (D).

En sidste antagelse om algebraiske cpo'er er nødvendigt for at få en kategori af domæner, der er egnede til fortolkning af PCF:

Definition 2.6. Givet en cpo (D), hvis (X / subseteq D) har en øvre grænse, siger vi, at (X) er konsistent, og skriver (opuparrow X), eller (x / opuparrow y) når (X = { {x, y }}). (D) er konsekvent komplet, hvis hver (X / subseteq D) sådan at (opuparrow X) har en mindst øvre grænse.

Følgende begreb om domæne, der har vist sig yderst praktisk som ramme for denotational semantik for programmeringssprog (Scott 1982):

Definition 2.7 (domæne). Et domæne er en konsekvent komplet algebraisk cpo med et tællbart grundlag.

2.3.2 En abstrakt teori om højere typer beregbare funktioner

Hvordan kan vi bruge begrebet information implicit i rækkefølgen af domænes elementer til at udvikle et abstrakt begreb om beregbarhed? Det er klart, at en beregbar funktion skal bevare monotonisk enhver stigning i information om dens input: (f (x) sqsubseteq f (y)) når (x / sqsubseteq y). Især er strenge funktioner (f: D / til E) over flade domæner, dem, for hvilke (f (bot_D) = / bot_E), er monotone.

Overvej domænet ({ {0,1 }} ^ / infty), hvis elementer er endelige og uendelige sekvenser af bit (0,1), hvor (u / sqsubseteq v) hvis en af (u) er uendelig og (u = v), eller (u) er endelig og (u) er et præfiks af (v). Hvilke egenskaber skal være gældende for en beregningsfunktion, der tager som argumenter en uendelig række af bit ({ langle b_1, b_2, b_3, / ldots / rangle})? Tag som eksempel funktionen (textit {search}: { {0,1 }} ^ / infty / til { mathbb {B}} _ / bot) hvis værdi er ({ textit {tt }}) hvis, for (u / i { {0,1 }} ^ / infty), (1) forekommer i (u) mindst en gang, ellers (bot). Tænk på sekvensen ({ langle b_1, b_2, b_3, / ldots / rangle}) som givet ét element ad gangen: de indledende segmenter opnået i denne proces er en stigende kæde af begrænsede elementer af ({ { 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) med ({ langle b_1, b_2, b_3, / ldots / rangle}) som en grænse (dvs. mindst øvre grænse). Ved monotonicitet har vi en tilsvarende stigende kæde af værdier) 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}}), så skal der være et begrænset begyndelsessegment ({ langle b_1, b_2, / ldots, b_n / rangle}), som (textit {search} ({ langle b_1, b_2, / ldots, b_n / rangle}) = { textit {tt}}),og dette vil være den kumulative værdi af funktionen for den uendelige sekvens ({ langle b_1, b_2, b_3, / ldots / rangle}). Generelt bør en beregbar funktion (f: D / til E) (være monotonisk) have den egenskab, at en begrænset mængde information om output (f (x)) allerede skal kunne opnås ved at give en begrænset mængde information om input (x). Dette svarer til forestillingen om kontinuitet, der oprindeligt blev introduceret af Scott i hans teori om computbare funktioner over domæner:Dette svarer til forestillingen om kontinuitet, der oprindeligt blev introduceret af Scott i hans teori om computbare funktioner over domæner:Dette svarer til forestillingen om kontinuitet, der oprindeligt blev introduceret af Scott i hans teori om computbare funktioner over domæner:

Definition 2.8 (Kontinuerlige funktioner). Hvis ({ langle D, / sqsubseteq _D / rangle}, { langle E, / sqsubseteq _E / rangle}) er cpo'er og (f: D / til E) er monotonisk, er (f) kontinuerlig hvis [f (bigsqcup_i x_i) = / bigsqcup_i f (x_i)) for hver stigende kæde (x_0 / sqsubseteq x_1 / sqsubseteq / ldots / subseteq D).

Fra denotational semantik synspunkt er en grundlæggende egenskab ved kontinuerlige funktioner (D / til D), at de indrømmer et mindst fast punkt, hvis konstruktion kan udføres ensartet og kontinuerligt:

Teorem 2.1 (Fast punktsteorem for kontinuerlige funktioner) Lad (f: D / til D) være en kontinuerlig funktion og (x / i D) være sådan at (x / sqsubseteq f (x)). Derefter er elementet) bigsqcup_ {n / i { mathbb {N}}} f ^ {(n)} (x)) det mindste (y / sqsupseteq x) sådan at (f (y) = y).

Definition 2.9. Det mindst faste punkt på en kontinuerlig (f: D / til D) er elementet i (D) defineret af [{ texttt {fix} (f)} = _ { textrm {def}} bigsqcup_ {n / in { mathbb {N}}} f ^ {(n)} (bot).)

De kontinuerlige funktioner fra (D) til (E) for cpo's ({ langle D, / sqsubseteq _D / rangle}) e ({ langle E, / sqsubseteq _E / rangle}), form en cpo ([D / til E]), ordnet punktvis ved at indstille, for (f, g: D / til E): [f / sqsubseteq g / Longleftrightarrow / forall d / i D. f (d) sqsubseteq _E g (d).) ([D / til E]) er et domæne, hvis (D) og (E) er, og ({ texttt {fix} (cdot)}: [D / til D] til D) er kontinuerlig. En yderligere konstruktion af cpo'er, der også strækker sig til domæner og meget ofte bruges, er kartesisk produkt: givne cpo'er (D, E), deres kartesiske produkt er defineret som sæt (D / gange E) af par ({ langle d, e / rangle}) hvor (d / i D) og (e / i E), ordnet punktvis: ({ langle d, e / rangle} sqsubseteq { langle d ', e '\ rangle}) hvis og kun hvis (d / sqsubseteq _D d') og (e / sqsubseteq _E e '). Vi kan sammenfatte disse konstruktioner på kategorisk sprog (Plotkin 1978, Andre internetressourcer) ved at sige, at kategorien, hvis objekter er domæner, og hvis morfismer er de kontinuerlige funktioner, er kartesisk lukket.

2.3.3 Kontinuerlig semantik for PCF

Standardfortolkningen af PCF består af en familie af cpos (D ^ / sigma) for hver type (sigma), hvor (D ^ / texttt {num} = { mathbb {N}} _ { bot}) og (D ^ / texttt {bool} = { mathbb {B}} _ { bot}), (D ^ { sigma / to / tau} = [D ^ / sigma / til D ^ / tau]) og PCF-konstanterne har den naturlige fortolkning som strenge kontinuerlige funktioner af den passende type, for eksempel (texttt {cond}: { mathbb {B}} _ { bot} til { mathbb {N}} _ { bot} til { mathbb {N}} _ { bot} til { mathbb {N}} _ { bot}) fortolkes som:) textit { cond} (b) (x) (y) = / venstre { begin {array} {ll} x & / text {if (b = / texttt {tt})} / y & / text {if (b = / texttt {ff})} / \ bot & / text {if (b = / bot),} end {array} højre.) Desuden operatøren ({ mathtt { Y} (cdot)}) fortolkes som den kontinuerlige funktionelle ({ texttt {fix} (cdot)}) ved den passende type. Dette er fortolkningen, der betragtes i Scott 1969b) og Milner 1973.

Muligheden for, at (e) kan indeholde frie forekomster af variabler (hvis typer er angivet med en basis (B)) komplicerer let fortolkningen af udtryk, hvilket gør det afhængigt af en yderligere parameter, et miljø (rho) kortlægning af hver gratis variabel (x: / tau) af (e) til et element af (D ^ / tau) (hvis sidstnævnte betingelse er opfyldt, siger vi, at (rho) respekterer (B)). Naturligvis er miljøet ikke relevant, når (e) er lukket.

Standardfortolkningen af PCF-termer (e: / sigma) (fra en basis (B)) er derefter et element ({ lll e / rll / rho} i D ^ / sigma), for enhver miljø (rho) sådan, at (rho) respekterer (B), bygget af strukturel induktion på termer, fortolkning af applikation som funktionsapplikation og (lambda) - abstraktioner med (kontinuerlige) funktioner. Mere generelt er en fortolkning kontinuerlig, hvis alle (D ^ / sigma) er en cpo og (D ^ { sigma / til / tau}) består af kontinuerlige funktioner (D ^ / sigma / til D ^ / tau).

En model af PCF er en fortolkning, der tilfredsstiller de forventede identiteter mellem udtryk af samme type. Vi vil udelade detaljerne i den generelle karakterisering af modeller af PCF, som læseren henvises til Ong (1995: s. 3.2) og Berry, Curien, & Lévy (1985: s. 4), men bare for at påpege en eksempel på, hvad der skal tages i betragtning, når en sådan generelitet er nødvendig, for at indrømme fortolkninger, hvor elementerne i funktionstyperne ikke, strengt taget, er funktioner, må vi antage en familie med applikationsoperationer) cdot _ { sigma / tau}: D ^ { sigma / til / tau} gange D ^ / sigma / til D ^ / tau) så, hvis (B / vdash e_1: / sigma / til / tau) og (B / vdash e_2; / sigma), ({ lll e_1e_2 / rll / rho} = { lll e_1 / rll / rho} cdot _ { sigma / tau} { lll e_2 / rll / rho} in {{{D} ^ { tau}}}). En model er ordreudvidet, hvis,for alle elementer (f, g / i {{{D} ^ { sigma / til / tau}}}), (f / sqsubseteq g) hvis og kun hvis (f / cdot x / sqsubseteq g / cdot x) for alle (x / i {{{D} ^ { sigma}}}). En model er ekstensiv, hvis, for alle elementer (f, g / i {{{D} ^ { sigma / til / tau}}}), (f = g) hvis og kun hvis (f / cdot x = g / cdot x) for alle (x / i {{{D} ^ { sigma}}}). Et element (d / i D ^ / sigma) i en model kan defineres, hvis der er et lukkede vilkår (e: / sigma), således at (d = { lll e / rll}).\ sigma) sådan at (d = { lll e / rll}).\ sigma) sådan at (d = { lll e / rll}).

2.4 Forbindelse med operationel og denotational semantik

Den generelle ramme for drøftelse af fuld abstraktion kræver, at vi introducerer følgende forestillinger:

Definition 2.11 (Observationsforudbestilling og ækvivalens) Givet PCF-termer (e) og (e ') af samme type (sigma), skriver vi (e / precsim _ { textrm {obs}} e') (læst (e) er observationsmæssigt mindre defineret end (e ')) hvis, for hver programkontekst (C / blbr) med et hul af typen (sigma) og enhver værdi (v), [C [e] opDownarrow v / \ text {indebærer, at} C [e '] opDownarrow v.) Vi siger, at (e) og (e') er observationsmæssigt ækvivalente, og skriv (e / simeq _ { textrm {obs}} e '), hvis (e / precsim _ { textrm {obs}} e') og (e '\ precsim _ { textrm {obs} } e).

Observationsækvivalens er en kongruens. En anden kongruens på PCF-vilkår er givet ved ligestilling af betegnelser i en model:

Definition 2.11 (Denotational forbestilling og ækvivalens). Givet PCF-termer (e) og (e ') af samme type (sigma) i forhold til et grundlag (B), skriver vi (e / precsim _ { textrm {den}} e ') hvis ({ lll e / rll / rho} sqsubseteq {{ lll e' / rll} rho}) for alle miljøer (rho) med respekt (B). Vi skriver (e / simeq _ { textrm {den}} e ') hvis (e / precsim _ { textrm {den}} e') og (e '\ precsim _ { textrm {den}} e).

Forslag 2.1 (Computational adequacy for PCF). Følgende to udsagn gælder for standardmodellen for PCF og er ækvivalente:

  1. For alle to PCF-termer af samme jordtype (e, e ') betyder (e / simeq _ { textrm {den}} e') (e / simeq _ { textrm {obs}} e ');
  2. For enhver lukket PCF-term (e) af jordtype og enhver værdi (v) af den type, ({ lll e / rll} = { lll v / rll}) hvis og kun hvis (e / opDownarrow v);

Vi kan nu retfærdiggøre vores intuitive fortolkning af (bot) i standardmodellen, hvor jordtyper fortolkes som flade domæner:

Korollar 2.1. For enhver lukket PCF-term (e) af jordtype, (e / opUparrow) hvis og kun hvis ({ lll e / rll} = / bot).

I afsnit 1.3 har vi allerede defineret en meget generel opfattelse af (ligelig) fuld abstraktion baseret på synonym, dvs. ligestilling af fortolkning af termer. I tilfælde af, at PCF, hvis tilsigtede modeller delvist er ordnet til alle typer, kan vi definere en stærkere egenskab:

Definition 2.12 (Inequational fuld abstraktion). En kontinuerlig model ({ langle { {{{{{}} {{sigma}}} mid / sigma / in / texttt {Types}} }, { lll / cdot / rll / cdot} rangle }) af PCF er ulige fuldstændig abstrakt, hvis det for lukkede vilkår (e, e '), (e / precsim _ { textrm {obs}} e') indebærer ({ lll e / rll} sqsubseteq { lll e '\ rll}).

Definibilitet er nøglen til fuld abstraktion, som det fremgår af følgende vigtige resultat af Milner og Plotkin:

Sætning 2.2. En kontinuerlig, ordre-ekstensiv model af PCF er fuldstændig abstrakt, hvis og kun hvis for hver type (sigma), ({{{D} ^ { sigma}}}) er et domæne, hvis endelige elementer er definerbare.

Vi henvender os nu til fiaskoen i den fulde abstraktionsejendom for standardmodellen af PCF, som vist af Plotkin i hans klassiske undersøgelse (Plotkin 1977):

Forslag 2.2. Standardmodellen for PCF er ikke fuldstændig abstrakt med hensyn til opkald-ved-navnevaluering.

Beviset er baseret på observationen af, at vi kan bygge PCF-termer af typen ((texttt {bool} til / texttt {bool} til / texttt {bool}) til / texttt {num}) der genkender parallel eller funktion. Overvej specifikt "test" -udtrykkene (T_i) defineret som følger, hvor (i = {0}, 1):

(lambda f: / texttt {bool} til / texttt {bool} til / texttt {bool.if} (f / texttt {tt} bot _ { texttt {bool}} texttt {derefter}) (texttt {if} (f / bot _ { texttt {bool}} texttt {tt}) texttt {derefter}) (texttt {if} (f / texttt {ff ff}) texttt { derefter}) (bot _ { texttt {num}}) (texttt {else} i) (texttt {else} bot _ { texttt {num}}) (texttt { andet} bot _ { texttt {num}})

Derefter ({ mathcal {D} lll T_ {0} rll} / texttt {por} = {0} neq 1 = { mathcal {D} lll T_1 / rll} / texttt {por }), hvor por er defineret af tabel ((ref {por})), så (T_ {0} { simeq _ { textrm {den}}} T_1) holder ikke. Ingen programkontekst i PCF kan dog adskille (T_ {0}) og (T_1), fordi por ikke er definerbar. Dette kan vises ved at karakterisere en kombinerende måde afhængighedsrelationer, der er fremkaldt af evalueringsprocessen for et program blandt evalueringsprocesserne for dets (sub) udtryk, som Plotkin gør i Activity Lemma (Plotkin 1977: Lemma 4.2). Som et alternativ er det muligt at opbygge en beregningsmæssigt passende modeller af PCF, hvis funktioner har en svag rækkefølgeegenskab (som vi diskuterer nedenfor, i Afsnit 2.5.1), og hvor funktionen por derfor udelukkes:et fuldstændigt formelt bevis i disse linjer er givet i Gunter 1992 (afsnit 6.1).

En mulighed for at løse det fulde abstraktionsproblem er at udvide sproget: et bemærkelsesværdigt resultat af Plotkin (1977) viser, at tilføjelse af parallel-eller er nok:

Forslag 2.3. Standardmodellen er fuldstændig abstrakt for det sprog, PCF udvides med parallel eller.

Milner (1977) har vist, at der findes en fuldstændig abstrakt model af PCF ved at tage sættet med lukkede vilkår ved hver type (sigma), der identificerer observationsækvivalente udtryk og ved at fuldføre det resulterende delvist ordnede sæt og omdanne det til en cpo.

Korollar 2.2. Der er en unik kontinuerlig, ordens ekstensiv, ulige fuldstændig abstrakt model af PCF, op til isomorfisme.

Det fulde abstraktionsproblem for PCF består i at finde en direkte beskrivelse af klassen af domæner og kontinuerlige funktioner, der udgør den fuldstændigt abstrakte model. En løsning på dette problem kræver et nøjagtigt kriterium for vurdering af, i hvilket omfang en foreslået beskrivelse af modellen er tilfredsstillende. Hvis man accepterer den "nøjagtige minimale betingelse, som en semantisk løsning af det fulde abstraktionsproblem skal opfylde", givet af Jung & Stoughton (1993), nemlig muligheden for på en effektiv måde at beskrive domænerne (D ^ / sigma) af en den endelige version af PCF (hvis eneste jordtype er bool), så er historien om mislykkede forsøg på at give en sådan direkte beskrivelse af den fuldstændigt abstrakte model retfærdiggjort af et resultat af Loader (2001):

Sætning 2.3. Observationsækvivalens for finitær PCF kan ikke afgøres.

Det er dog stadig muligt, at man kunne finde en direkte beskrivelse af en intensivt fuldt abstrakt model (Abramsky et al. 2000: 411):

Definition 2.13 (Intensional fuld abstraktion). En model af PCF er intensivt fuldstændigt abstrakt, hvis alle (D ^ / sigma) er algebraiske og alle dens kompakte elementer er definerbare.

Forfølgelse af denne udviklingslinje af det fulde abstraktionsproblem fører os til spil-semantik, som vil være emnet for det næste afsnit. Før det skitserer vi de vigtigste forsøg på at reducere modellen ved hjælp af en semantisk karakterisering af sekventiel beregning af højere orden.

2.5 Mod en sekventiel semantik

Årsagen til fiaskoen med fuld abstraktion af PCF's kontinuerlige semantik er eksistensen af funktioner, hvis evaluering kræver parallel beregning. Vi beskriver nu nogle forslag til karakterisering af rækkefølge af funktioner ved hjælp af egenskaber relateret til strukturen af de domæner, som de er defineret på. Dette har været et område med intensiv forskning i retning af løsningen af det fulde abstraktionsproblem for PCF, og nogle af de indsigter, der fremkom derfra, fører meget naturligt til de spillemodeller, der er omtalt i afsnit 3. Derudover er det følgende resumé af forsøg på en karakterisering af rækkefølge er også en meget interessant demonstration af den udtrykksfulde magt i sproget i delvis orden i den semantiske analyse af programmeringskoncepter.

Intuitivt er en sekventiel funktion en, hvis evaluering forløber serielt: dette betyder, at det er muligt at planlægge evalueringen af dens argumenter, så evalueringen af funktionen afsluttes med den korrekte værdi; hvis evalueringen af en af dem afviger, afviger hele evalueringen. På hvert trin i denne proces er der et argument, hvis værdi er nødvendig for at få mere information om output af funktionen. For at redegøre for denne kausale struktur i beregninger på det semantiske niveau, er vi nødt til at berige domænestrukturen, så ordenen på elementerne afspejler, hvad der sker ved beregningsbegivenheder og deres kausale orden. Dette antyder en anden måde at fortolke den abstrakte opfattelse af information, der motiverede aksiomerne i et cpo i afsnit 2.3.1. Nu,

information har at gøre med (forekomster af) begivenheder: nemlig informationen om, at disse begivenheder opstod. For eksempel i tilfælde af ({ mathbb {N}} _ { bot}), kan (bot) betyde, at der ikke opstod nogen begivenhed og et heltal (n), at begivenheden fandt sted af det heltal (n), der udsendes (eller i en anden situation, der indtastes). (Plotkin 1978, andre internetressourcer)

2.5.1 Stabilitet

Én fortolkning af begivenheder betragter dem som produktion af værdier i evalueringen af et udtryk. Denne fortolkning stammer fra sammenhængen med bottom-up beregning af rekursive programmer udviklet af Berry (1976), hvor en rekursiv definition oversættes til en graf, der viser afhængigheden af resultaterne af et udtryk til resultaterne af dets subexpressions. Denne kontekst antyder naturligvis forestillingen om producent af en begivenhed (x), som et sæt af begivenheder, der skal være sket for at (x) kan ske. Omformulering af denne observation på sproget af delvise ordrer, definerede Berry (1976):

Definition 2.14 (Stabilitet). Lad (D_1, / ldots, D_n, D) være flade cpo'er og (f: D_1 / times / ldots / times D_n / to D) monotonisk (dermed kontinuerlig). Derefter er (f) stabil, hvis der for hver (vec {x} = { langle x_1, / ldots, x_n / rangle} i D_1 / times / ldots / times D_n) er et unikt minimalt element (m (f, x) sqsubseteq / vec {x}) sådan at (f (m (f, / vec {x})) = f (vec {x})).

Parallel- eller funktionen er tydeligvis ikke stabil: værdien (texttt {por} (bot, { textit {tt}}) = { textit {tt}} = / texttt {por} ({ textit {tt}}, / bot)) har ingen minimal producent. En bemærkelsesværdig egenskab ved stabile funktioner er, at de tillader at opbygge en ny model af PCF, hvor ({{{D} ^ { sigma / til / tau}}}) er sættet med stabile funktioner på de domæner, der fortolker typerne (sigma) og (tau), som er forbedringer af Scott-domæner kaldet dI-domæner (Berry 1978). Fra vores synspunkt er det vigtige resultat af disse definitioner følgende tilstrækkelig resultat (Gunter 1992: kap. 6):

Forslag 2.4. Fortolkningen af PCF-termer som elementer i dI-domæner, hvor (D ^ { sigma / til / tau}) er dI-domænet for stabile funktioner fra (D ^ / sigma) til (D ^ / tau) med den stabile rækkefølge, er en beregningsmæssigt passende model for PCF.

Dette resultat afslutter argumentet, der viser mislykket fuld abstraktion for den kontinuerlige model af PCF i slutningen af afsnit 2.4, hvis den uformelle forestilling om sekvensitet, der er anvendt der, formaliseres som stabilitet. Den stabile model af PCF har for nylig vist sig at være fuldstændig abstrakt for en udvidelse af PCF (Paolini 2006).

2.5.2 Sekventielle funktioner

De første definitioner på rækkefølge på grund af Vuillemin (1974) og Milner (1977) erklærede, at en (n) - ary-funktioner (f) over flade domæner er sekventiel ved argument ({ langle x_1, / ldots, x_n / rangle}) hvis der er et sekvensitetsindeks (i) på (f), afhængigt af ({ langle x_1, / ldots, x_n / rangle}), således at hver stigning i output oplysninger skal øge informationen med argumentet (i). F.eks. Funktionen (texttt {cond}: { mathbb {B}} _ { bot} times { mathbb {N}} _ { bot} times { mathbb {N}} _ { bot} til { mathbb {N}} _ { bot}) er sekventiel i denne forstand ved enhver inputtuple. Faktisk er dens sekvensitetsindeks ved ({ langle / bot, m, n / rangle}) 1; dens sekvensitetsindeks ved ({ langle { textit {tt}}, m, n / rangle}) er 2, og dets sekvensitetsindeks på ({ langle { textit {ff}}, m, n / rangle}) er 3. Der er dog intet sekvensitetsindeks for funktionen (texttt {por}: { mathbb {B}} _ { bot} gange { mathbb {B}} _ { bot} til { mathbb {B }} _ { bot}) ved input ({ langle / bot, / bot / rangle}).

Selvom alle sekventielle funktioner (over flade domæner) er stabile, er sekventialiteten strengt stærkere end stabilitet. For eksempel den kontinuerlige funktion fra ({ mathbb {B}} _ / bot / times { mathbb {B}} _ / bot / times { mathbb {B}} _ / bot) til ({ mathbb {B}} _ / bot) defineret som den mindste kontinuerlige udvidelse af de tre opgaver [{ 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}}.) har intet rækkefølgeindeks ved argumentet ({ langle / bot, / bot, / bot / rangle}), men er stabil, fordi argumenterne ({ langle { textit {tt}}, { textit {ff}}, / bot / rangle}, { langle { textit {ff}}, / bot, { textit {tt}} rangle}, { langle / bot, { textit {tt}}, { textit {ff}} rangle}) er parvis modstridende.

Følgende resultat tilføjer understøttelse til søgningen efter en semantisk karakterisering af rækkefølge:

Forslag 2.5. Lad (f: D_1 / times / cdots / times D_n / til D) være en kontinuerlig funktion, hvor (D_i, D) er enten ({ mathbb {N}} _ / bot) eller ({ mathbb {B}} _ / bot). Derefter er (f) sekventiel, hvis og kun hvis det er definerbart i PCF.

2.5.3 Konkrete datastrukturer og sekventielle algoritmer

Hvis de domæner, der er nødvendige for en passende definition af sekvensitet, er at beskrive kausalitetsrelationer mellem forekomster af beregningsbegivenheder, er det nødvendigt at berige vores billede ved at betragte begivenheder som placeret på steder, generalisere forestillingen om argumentplads i definitionerne af Vuillemin og Milner, som afhænger af, hvordan en funktion præsenteres. Dette førte til en forestilling om konkret datastruktur (cds) (Kahn & Plotkin 1993) og til en aksiomatisering af rækkefølge-teoretiske egenskaber for domæner i første ordens data. Kahn og Plotkin opnåede en repræsentationsteorem for de domæner beskrevet af deres aksiomer, de konkrete domæner, med hensyn til tilstande for en efterforskningsproces af en konkret datastruktur, der består i udfyldning, givet en tilstand (x), enhver celle aktiveret ved sæt af begivenheder, der allerede er sket i (x),startende fra startceller aktiveret i den oprindelige, tomme tilstand: dette svarer til at bevise sætninger i et abstrakt deduktivt system, hvis regler er aktiveringerne. Tænk som et motiverende eksempel på en sammenkædet liste med f.eks. Naturlige tal. Den oprindelige celle kan til enhver tid udfyldes med en hvilken som helst værdi (n_1). Denne begivenhed muliggør den anden celle på listen, som derefter (og først derefter) kan udfyldes med en hvilken som helst værdi (n_2) osv. For alle senere celler.som derefter (og kun derefter) kan udfyldes med en hvilken som helst værdi (n_2) osv. for alle senere celler.som derefter (og kun derefter) kan udfyldes med en hvilken som helst værdi (n_2) osv. for alle senere celler.

Bemærk, at rammerne for konkrete datastrukturer giver de nødvendige forestillinger til at rekonstruere en semantisk version af sekvensitet. Groft sagt er en monoton funktion (f) fra tilstande i (M) til tilstande af (M ') sekventiel (i tilstand (x)) hvis, for en hvilken som helst outputcelle (c'), der er en inputcelle (c), der skal udfyldes i enhver overgang fra (x) til (y), således at overgangen fra (f (x)) til (f (y)) udfylder (c ') (hvis en sådan (c') findes) (Curien 1986: Def. 2.4.5). Cellen (c) er sekvensitetsindekset for (f) ved (x) for (c ').

Den kategori, hvis objekter er de konkrete datastrukturer, og hvis morfismer er de netop definerede sekvensfunktioner, er dog ikke kartesisk lukket, ikke uventet. Denne observation (for et enkelt bevis, se Amadio & Curien 1998 (sætning 14.1.12)) forhindrer brugen af denne kategori som en model af PCF. Det er dog muligt at definere for hver to konkrete datastrukturer (M, M ') en ny (M / til M'), hvis tilstande repræsenterer sekventielle algoritmer, og som er det eksponentielle objekt for (M) og (M ') i en kartesisk lukket kategori, hvis morfismer er sekventielle algoritmer (Curien 1986: sek. 2.5). Generaliseringerne af modelteorien for PCF til kategoriske modeller giver os mulighed for at få en model af PCF fra denne nye kategori, selvom dens morfismer ikke er funktioner i den sædvanlige sætteoretiske forstand. Det viser sig, at den sekventielle algoritmemodel ikke er ekstensiv, fordi der er forskellige PCF-termer, der betegner den samme kontinuerlige funktion, men alligevel repræsenterer forskellige algoritmer. Som et eksempel skal du overveje de følgende to udtryk, der betegner den samme funktion men forskellige algoritmer:) begynde {rettet} texttt {lror} (x, y) & = / texttt {hvis} x / texttt {derefter} ({ texttt {if} y / texttt {derefter} texttt {tt} texttt {else} x}) & / quad / texttt {else} ({ texttt {if} y / texttt {derefter} texttt {tt} texttt {else} texttt {ff}}) / \ texttt {rlor} (x, y) & = / texttt {if} y / texttt {derefter} ({ texttt {if} x / texttt {derefter} texttt {tt} texttt {else} y}) & / quad / texttt {else} ({ texttt {if} x / texttt {derefter} texttt {tt} texttt {else} texttt {ff}}). / slut {justeret}) Ved passende introduktion af fejlværdier (textit {error} _1, / textit {error} _2) i semantikken,og håndhævelse af en fejlforplantningsegenskap ved fortolkninger af termer (således udvidelse af sprogets observerbare objekter), kan funktionerne, der svarer til ovenstående vilkår, derefter skelnes: klart, for tolkningsfunktionerne (textit {lror}) og (textit {rlor}) vi har) begynde {justeret} textit {lror} (textit {error} _1, / textit {error} _2) & = / textit {error} _1 & / textit { rlor} (textit {error} _1, / textit {error} _2) & = / textit {error} _2 / end {lined}) hvilket også peger på muligheden for at bevise fuld abstraktion af denne (ikke-standard) ekstensions model med hensyn til en udvidelse af PCF med kontroloperatører (Cartwright, Curien, & Felleisen 1994).funktionerne, der svarer til ovennævnte vilkår, kan derefter skilles: klart, for tolkningsfunktionerne (textit {lror}) og (textit {rlor}) har vi) begynde {justert} textit {lror } (textit {error} _1, / textit {error} _2) & = / textit {error} _1 & / textit {rlor} (textit {error} _1, / textit {error} _2) & = / textit { fejl} _2 / ende {justeret}), som også peger på muligheden for at bevise fuld abstraktion af denne (ikke-standard) ekstensionsmodel med hensyn til en udvidelse af PCF med kontroloperatører (Cartwright, Curien, & Felleisen 1994).funktionerne, der svarer til ovennævnte vilkår, kan derefter skilles: klart, for tolkningsfunktionerne (textit {lror}) og (textit {rlor}) har vi) begynde {justert} textit {lror } (textit {error} _1, / textit {error} _2) & = / textit {error} _1 & / textit {rlor} (textit {error} _1, / textit {error} _2) & = / textit { fejl} _2 / ende {justeret}), som også peger på muligheden for at bevise fuld abstraktion af denne (ikke-standard) ekstensionsmodel med hensyn til en udvidelse af PCF med kontroloperatører (Cartwright, Curien, & Felleisen 1994).= / textit {error} _2 / end {alignet}), der også peger på muligheden for at bevise fuld abstraktion af denne (ikke-standard) ekstensionsmodel med hensyn til en udvidelse af PCF med kontroloperatører (Cartwright, Curien, & Felleisen 1994).= / textit {error} _2 / end {alignet}), som også peger på muligheden for at bevise fuld abstraktion af denne (ikke-standard) ekstensionsmodel med hensyn til en udvidelse af PCF med kontroloperatører (Cartwright, Curien, & Felleisen 1994).

Inden vi forlader denne oversigt over søgen efter en ekstensiv karakterisering af sekvenser af højere orden, skal vi nævne Bucciarelli & Ehrhard (1994), der introducerede en forfining af Ber-dI-domænerne, der understøtter en opfattelse af stærk stabil funktion, der giver dem mulighed for at opbygge en ekstensional model af PCF, som ikke er fuldstændig abstrakt. Årsagen til svigt i fuld abstraktion i dette tilfælde afhænger af det faktum, at PCF-definerbare funktionaliteter tilfredsstiller ekstensivitetsegenskaber, der mislykkes, når funktioner ordnes i den stabile rækkefølge. Dette var også grunden til at motiverede introduktionen af bidomæner (Berry 1978), hvor de stabile og ekstensionsbestemte (= punktvise) ordrer af funktioner sameksisterer.

2.6 Historiske noter og yderligere læsninger

Problemet med fuld abstraktion er blevet forudset i en stor mængde arbejde med forholdet mellem denotationelle og operationelle fortolkninger af programmeringssprog. Især var det banebrydende arbejde med semantikken i rekursive programmer, der blev udført i Stanford i begyndelsen af 1970'erne af en gruppe mennesker, der samledes omkring Zohar Manna, og inklusive Jean Marie Cadiou, Robin Milner og Jean Vuillemin, også i samspil med Gilles Kahn.

En beslægtet tradition var også ganske indflydelsesrig på baggrund af det fulde abstraktionsproblem, nemlig karakteriseringerne af semantiske forestillinger som kontinuitet og sekvensitet i syntaktiske modeller af den (ikke-typede) (lambda) - beregning baseret på Böhm-træer (Barendregt 1984), primært på grund af Lévy og Berry (se Berry et al. 1985 og Curien 1992) for beretninger om søgningen efter fuldstændigt abstrakte modeller af PCF langs denne linje.

De grundlæggende papirer om fuld abstraktion for PCF er Milner 1977; Plotkin 1977. De kan læses sammen som et sammenhængende billede af den semantiske analyse af dette sprog. En uafhængig tilgang til fuld abstraktion kom fra den russiske logiker Vladimir Sazonov, der karakteriserede definibilitet i PCF med hensyn til en bestemt klasse af sekventielle beregningsstrategier (Sazonov 1975, 1976). Hans arbejde havde imidlertid ingen direkte indflydelse på hovedparten af forskningen på det fulde abstraktionsproblem, og først for nylig har der været forsøg på at relatere Sazonovs karakterisering til spilteoretiske tilgange (Sazonov 2007).

En anden, helt anden tilgang til fuld abstraktion, udnytter særlige former for logiske relationer for at isolere kvoter på den kontinuerlige model. Den første brug af logiske relationer i forbindelse med problemet med fuld abstraktion er Mulmuley 1987, men den resulterende konstruktion af en fuldstændig abstrakt model opnås ved brute force og er derfor ikke, hvad det fulde abstraktionsproblem søger efter. Senere har Sieber (1992) og O'Hearn & Riecke (1995) anvendt forbedringer af denne teknik for at få en bedre indsigt i strukturen i de fuldt abstrakte modeller, idet de karakteriserer de definerbare elementer i den standard kontinuerlige model ved hjælp af invariance under speciel logiske forhold, der skærer de ikke-sekventielle funktioner ud.

Detaljerede beretninger om det fulde abstraktionsproblem for PCF kan findes i Gunter 1992 (kap. 5,6), Streicher 2006, Ong 1995, Stoughton 1988 og Amadio & Curien 1998 (kap. 6, 12, 14), i omtrent stigende rækkefølge af tekniske kompleksitet. Vægten på rekursionsteoretiske aspekter af PCF og dets fulde abstraktionsproblem behandles detaljeret i lærebogen (Longley & Normann 2015: kap. 6, 7); en kortere konto findes i Longley 2001 (afsnit 4).

3. Spil semantik

3.1 Fuld fuldstændighed

Teorem 2.2 fremhæver den grundlæggende rolle, som definitive elementer kan defineres i den fuldt abstrakte model af PCF, et aspekt, der er blevet understreget for nylig i Curien 2007. Som en glat overgang til formaliteterne baseret på spil, og delvist efter den historiske udvikling af emnet, pauser vi kort for at undersøge et andet aspekt af definibilitet, der opstår ved grænsen mellem beregning og bevisteorien for konstruktive logiske systemer. Det har været en bemærkelsesværdig opdagelse, at strukturen af naturlige fradragsbeviser for for eksempel det implicative fragment af den intuitionistiske propositionskalkulus er fuldstændigt beskrevet af termerne i den simpelt indtastede (lambda) - kalkulus, hvor en beviselig propositionskomposition af formen (sigma / to / tau) læses som typen af udtryk, der repræsenterer dens bevis. Dette er korrespondancen mellem propositioner og typer, der skal tilskrives Curry, de Bruijn, Scott, Läuchli, Lawvere og Howard, som udvides til meget rigere formelle systemer (for en historie om denne opfattelse se Cardone & Hindley 2009: s. 8.1.4).

Eksistensen af denne korrespondance gør det muligt at tale om en semantik af bevis, der udvider til konstruktive formelle bevis for denotationsfortolkningerne af typede (lambda) - calculi, og i denne sammenhæng giver det også mening at spørge, om et element (x) af nogle (D ^ / sigma) i en model af en indtastet (lambda) - beregning er fortolkningen af et vist bevis på formel (sigma). Et yderligere spørgsmål stilles, om hvert element i (D ^ / sigma), der tilfredsstiller en passende valgt egenskab, er fortolkningen af et bevis på formel (sigma). Egnede egenskaber kan for eksempel være invarians under logiske forhold, passende defineret over hver (D ^ / sigma), ligesom i flere resultater af Plotkin, Statman og andre sammenfattet i Barendregt, Dekkers, & Statman 2013 (I.3, I. 4). Vi kan læse det sidstnævnte spørgsmål som at bede om en stærk form for fuldstændighed for det system, der kaldes fuldstændighed (Abramsky & Jagadeesan 1994), hvis definition bedre kan forstås i en kategorisk semantik af systemer med konstruktiv logik. Det er almindeligt at fortolke formler (A) for sådanne systemer som objekter ({ lll A / rll}) for passende kategorier (mathbb {M}) og bevis (p) af sekvenser (A / vdash B) som morfismer (lll p / rll: / lll A / rll / longrightarrow / lll B / rll). Mens almindelig fuldstændighed angiver, at for hver gyldig sekvens (A / vdash B) er sætet (mathbb {M} ({ lll A / rll}, { lll B / rll})) af morfismer ikke tomt, udtrykker i det nuværende miljø fuldstændighed det stærkere krav, at enhver morfisme (f:\ lll A / rll / longrightarrow / lll B / rll) i en semantisk kategori (mathbb {M}) opstår som fortolkningen af noget bevis, dvs. (f = { lll p / rll}) til noget bevis (p) for den sekvente (A / vdash B). Resultater af fuldstændighed er blevet bevist for adskillige delsystemer i lineær logik Girard (1987), se Abramsky (2000) for en generel ramme. Desuden har det også foreslået teknikker til at opnå definitionen af modeller af PCF, der nyder den stærke egenskab, som kræves ved intensiv fuld abstraktion.det har også foreslået teknikker til at opnå definitionen af modeller af PCF, der nyder den stærke egenskab, som kræves ved intensiv fuld abstraktion.det har også foreslået teknikker til at opnå definitionen af modeller af PCF, der nyder den stærke egenskab, som kræves ved intensiv fuld abstraktion.

3.2 Interaktion

I vores beskrivelse af forfininger til den kontinuerlige model af PCF for at garantere definibiliteten af begrænsede elementer ved hver type, er vi gradvist kommet tættere på en interaktiv forklaring af beregning. F.eks. Udnytter handlingen af en sekventiel algoritme (M / til M ') (Curien 1986: sek. 3.4) et eksternt opkaldsagent, som udløser en cyklus af anmodninger og svar på inputceller, der fører (muligvis) til emissionen af en outputværdi. Denne interaktion skal være en central opfattelse i analysen af beregning, især i relation til fuld abstraktion, er måske et naturligt resultat af den observationsmæssige holdning i definitionen af operationel ækvivalens. Vores korte redegørelse for spelsemantik starter netop fra en analyse af en generel opfattelse af interaktion som en motivation til en første formalisering af spil, som dog er rig nok til at give et univers til fortolkning af et begrænset sæt af typer og vilkår. Senere tilføjer vi til denne definition af spil og strategier de funktioner, der er nødvendige for at udtrykke de begrænsninger, der tillader strategier at karakterisere præcist højere-orden, sekventiel beregning, hvilket er målet, der er sat for denotational semantik ved det fulde abstraktionsproblem. Den nuværende beretning om den begrebsmæssige baggrund af spelsemantik skylder Abramsky og Curiens arbejde meget (Abramsky 1994, 1996, 1997; Curien 2003a). Senere tilføjer vi til denne definition af spil og strategier de funktioner, der er nødvendige for at udtrykke de begrænsninger, der tillader strategier at karakterisere præcist højere-orden, sekventiel beregning, hvilket er målet, der er sat for denotational semantik ved det fulde abstraktionsproblem. Den nuværende beretning om den begrebsmæssige baggrund af spelsemantik skylder Abramsky og Curiens arbejde meget (Abramsky 1994, 1996, 1997; Curien 2003a). Senere tilføjer vi til denne definition af spil og strategier de funktioner, der er nødvendige for at udtrykke de begrænsninger, der tillader strategier at karakterisere præcist højere-orden, sekventiel beregning, hvilket er målet, der er sat for denotational semantik ved det fulde abstraktionsproblem. Den nuværende beretning om den begrebsmæssige baggrund af spelsemantik skylder Abramsky og Curiens arbejde meget (Abramsky 1994, 1996, 1997; Curien 2003a).

Det relevante begreb om interaktion er blevet isoleret som et resultat af bidrag, der kommer fra vidt forskellige forskningsområder, der kun er intensivt undersøgt i de seneste år, især lineær logik (Girard 1987) og teorien om samtidige processer. Det er på disse områder, en forestilling om sammensætning som interaktion mellem moduler tager form. Vi giver her bare et simpelt eksempel, hvor sammensætningen af moduler i form af "parallel sammensætning + skjul" findes i naturen for at forbinde den med oprindelsen af denne idé i semantikken i samtidige processer udviklet af Hoare (1985) og også for at give et første glimt af en forenklet spilformalisme.

Overvej et modul (S) med fire kanaler mærket (a_ / textrm {in}, a_ / textrm {out}, r_ / textrm {in}, r_ / textrm {out}). Modulet er beregnet til at vende tilbage på kanal (a_ / textrm {out}) efterfølgeren til nummeret (n), der kommer ind via kanal (a_ / textrm {in}), derfor kan dens opførsel specificeres som følger:

  • (S) modtager et indgangssignal (mathbf {?} _ / Textrm {in}) på kanal (r_ / textrm {in}), derefter
  • udsender et signal (mathbf {?} _ / textrm {out}) på kanal (r_ / textrm {out}), og
  • venter på en værdi (n) på kanal (a_ / textrm {in}) og derefter efter at have modtaget den
  • udsender en værdi (n + 1) på kanal (a_ / textrm {out}).

(Dette interaktionsmønster er formelt identisk med håndtrykprotokollen, der bruges i hardware-design til at synkronisere komponenter for at undgå farer forårsaget af interferens af signaler.) Denne opførsel kan kortlægges på kanalerne som følger:

[en rektangulær kasse med bogstavet S inden i øverste venstre hjørne en linie, der ender i en hvid cirkel, er mærket '? in', nederst til venstre er en linje, der slutter i en sort cirkel, mærket 'n + 1 out', øverst til højre markeres en foret ender i en sort cirkel '? out', og nederst til højre er en linje, der ender i en hvid cirkel, mærket 'n in']
[en rektangulær kasse med bogstavet S inden i øverste venstre hjørne en linie, der ender i en hvid cirkel, er mærket '? in', nederst til venstre er en linje, der slutter i en sort cirkel, mærket 'n + 1 out', øverst til højre markeres en foret ender i en sort cirkel '? out', og nederst til højre er en linje, der ender i en hvid cirkel, mærket 'n in']

Figur 1: Et modul til efterfølgerfunktionen.

hvor (circ) betyder input eller, mere generelt, en passiv involvering af modulet i den tilsvarende handling, hvorimod (bullet) betyder output eller aktiv involvering i handlingen. Vi kan beskrive adfærden ved (S) ved hjælp af spor (Hoare 1985), dvs. endelige sekvenser af symboler fra det uendelige alfabet (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 }}) Hvis vi overvejer en anden forekomst (S ') af (S) med alfabetet (alpha S' = { { mathbf {?} _ / Textrm {in} ', / mathbf {?} _ / Textrm {ud} 'n_ / textrm {i}', m_ / textrm {ud}'}}) vi kan komponere (S) og (S ') ved at identificere (= forbinde) kanaler (r_ / textrm {out}, r_ / textrm {in}') og (a_ / textrm {in}, a_ / textrm {out} '), og signalerne, der passerer gennem dem, som vist:) begynde {justeret} mathbf {?} _ / textrm {out}, / mathbf {?} _ / textrm {in} '& / leadsto x \\ n + 1_ / textrm {in}, n + 1_ / textrm {out}' & / leadsto y / end {alignet}) Dette repræsenterer den parallelle sammensætning af modulerne, (S / | S '):\ leadsto y / end {lined}) Dette repræsenterer den parallelle sammensætning af modulerne, (S / | S '):\ leadsto y / end {lined}) Dette repræsenterer den parallelle sammensætning af modulerne, (S / | S '):

[to rektangler, den ene til venstre indeholder 'S' og den til højre 'S / prime'. Øverst til venstre på venstre har en linje, der slutter i en hvid cirkel mærket '? In', nederst til venstre en linje, der slutter i en sort cirkel mærket 'n + 2 out'. Den øverste højre del af det højre rektangel har en linje, der slutter i en sort cirkel mærket '? / Prime out' og den nederste højre en linje mærket 'n / prime in'. De to rektangler er forbundet med to linjer. Den øverste med en sort cirkel til venstre og en hvid cirkel til højre mærket 'x'. Den nederste med en hvid cirkel til venstre og den sorte cirkel til højre mærket 'y'.]
[to rektangler, den ene til venstre indeholder 'S' og den til højre 'S / prime'. Øverst til venstre på venstre har en linje, der slutter i en hvid cirkel mærket '? In', nederst til venstre en linje, der slutter i en sort cirkel mærket 'n + 2 out'. Den øverste højre del af det højre rektangel har en linje, der slutter i en sort cirkel mærket '? / Prime out' og den nederste højre en linje mærket 'n / prime in'. De to rektangler er forbundet med to linjer. Den øverste med en sort cirkel til venstre og en hvid cirkel til højre mærket 'x'. Den nederste med en hvid cirkel til venstre og den sorte cirkel til højre mærket 'y'.]

Figur 2

Opførelsen af det sammensatte modul er beskrevet af mængden af spor [{ { 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 }}) Symbolerne (x, y) kan nu skjules, hvilket repræsenterer det endelige systems opførsel

[to rektangler med stiplede linjer for sider, den ene til venstre indeholder 'S' og den til højre 'S / prime'. Øverst til venstre på venstre har en linje, der slutter i en hvid cirkel mærket '? In', nederst til venstre en linje, der slutter i en sort cirkel mærket 'n + 2 out'. Den øverste højre del af det højre rektangel har en linje, der slutter i en sort cirkel mærket '? / Prime out' og den nederste højre en linje mærket 'n / prime in'. De to rektangler er forbundet med to stiplede linjer. Den øverste med en sort cirkel til venstre og en hvid cirkel til højre og ikke mærket. Den nederste med en hvid cirkel til venstre og den sorte cirkel til højre og ikke mærket. Et større rektangel med solide sider lukker de to rektangler, så venstre side af det venstre rektangel og højre side af det højre rektangel er på venstre og højre side af det lukkende rektangel]
[to rektangler med stiplede linjer for sider, den ene til venstre indeholder 'S' og den til højre 'S / prime'. Øverst til venstre på venstre har en linje, der slutter i en hvid cirkel mærket '? In', nederst til venstre en linje, der slutter i en sort cirkel mærket 'n + 2 out'. Den øverste højre del af det højre rektangel har en linje, der slutter i en sort cirkel mærket '? / Prime out' og den nederste højre en linje mærket 'n / prime in'. De to rektangler er forbundet med to stiplede linjer. Den øverste med en sort cirkel til venstre og en hvid cirkel til højre og ikke mærket. Den nederste med en hvid cirkel til venstre og den sorte cirkel til højre og ikke mærket. Et større rektangel med solide sider lukker de to rektangler, så venstre side af det venstre rektangel og højre side af det højre rektangel er på venstre og højre side af det lukkende rektangel]

Figur 3

hvis spor har den krævede form [{ { 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 }}.) Dette eksempel indeholder mange af de ingredienser, som spil semantik er baseret på. Der er ideen om et system, hvis opførsel udløses af en indgående anmodning fra dets miljø: i en spilformalisme er disse rollerne som talsmand og modstander i et to-personers spil. Opførelsen af hvert modul beskrives som sporet af dets mulige interaktioner med andre agenter, og adfærden kan sammensættes af en særegen rolleændring, hvorved modulet, der spiller som System (i ovenstående eksempel,(S), der udsender et anmodningssignal på kanal (r_ / textrm {out})), er gjort til at opføre sig som miljø med hensyn til (S '), når dette signal modtages i input på kanal (r_ / textrm {i} '). Lad os se, hvordan dette eksempel kan generaliseres.

3.3 Spil og strategier

Vi giver kun de nødvendige definitioner for at forstå de grundlæggende konstruktioner på spil og for at se, hvordan disse danner en kategori efter Abramsky 1997 og Hyland 1997, der indeholder mere formelle detaljer og bevis.

3.3.1 Spil

Definition 3.1 Et spil (G) er specificeret ved at give et sæt træk (M_G), en mærkning (ell_G) af bevægelserne som enten bevægelser fra Proponenten ((P)) eller som bevægelser af modstanderen ((O)). Der er desuden et sæt positioner (P_G), som er et sæt af sekvenser af bevægelser, hvor: (1) de to spillere veksler, startende med (O); (2) hvis (s / i P_G), så er hvert præfiks (s ') af (s) også i (P_G).

Overvej som et eksempel et spil, der er forbundet med alt="sep man icon" /> Sådan citeres denne post.

sep mand ikon
sep mand ikon

Forhåndsvis PDF-versionen af denne post hos Friends of the SEP Society.

inpho ikon
inpho ikon

Slå dette emne op på Internet Philosophy Ontology Project (InPhO).

phil papirer ikon
phil papirer ikon

Forbedret bibliografi til denne post på PhilPapers med links til dens database.

Andre internetressourcer

  • Curien, Pierre-Louis, 2006, “Noter om spilsemantik”, kursusnotater
  • Lamarche, François, 1992, "Sekvensitet, spil og lineær logik", fra et foredrag til CLiCS-symposiet Aarhus Universitet 23.-27. Marts, 1992.
  • Plotkin, Gordon, 1978, “Kategorien af komplette delvise ordrer: et værktøj til at gøre betydninger”, Foredrag, sommerskole, Dipartimento di Informatica, Università di Pisa, Italien. Genoptrykt i domæner (1983)
  • Oversættelse af Joyal, André (1977) “Bemærkninger om teorien om to-spiller-spil, oversat af Robin Houston, se den postede note om denne oversættelse.

Anbefalet: