Semantik (datalogi) - Semantics (computer science)
Ved programmering sprog teori , semantik er den pågældende med den strenge matematiske undersøgelse af betydningen af feltet programmeringssprog . Det gør det ved at evaluere betydningen af syntaktisk gyldige strenge, der er defineret af et specifikt programmeringssprog, og viser den involverede beregning. I et sådant tilfælde, at evalueringen ville være af syntaktisk ugyldige strenge, ville resultatet være ikke-beregning. Semantik beskriver de processer, en computer følger, når der udføres et program på det specifikke sprog. Dette kan vises ved at beskrive forholdet mellem input og output af et program eller en forklaring på, hvordan programmet vil blive udført på en bestemt platform , og dermed oprette en beregningsmodel .
Oversigt
Området for formel semantik omfatter alt følgende:
- Definitionen af semantiske modeller
- Forholdet mellem forskellige semantiske modeller
- Forholdet mellem forskellige tilgange til mening
- Forholdet mellem beregning og de underliggende matematiske strukturer fra områder som logik , sætteori , modelteori , kategoriteori osv.
Det har tætte forbindelser til andre områder inden for datalogi såsom programmeringssprogsdesign , typeteori , kompilatorer og tolke , programverifikation og modelkontrol .
Tilgange
Der er mange tilgange til formel semantik; disse tilhører tre hovedklasser:
- Denotationssemantik , hvor hver sætning i sproget tolkes som en betegnelse , altså en begrebsmæssig betydning, der kan tænkes abstrakt. Sådanne betegnelser er ofte matematiske objekter, der lever i et matematisk rum, men det er ikke et krav, at de skal være det. Som en praktisk nødvendighed beskrives betegnelser ved hjælp af en form for matematisk notation, som igen kan formaliseres som en denotationel metalsprog. For eksempeloversætterdenotationssemantik for funktionelle sprog ofte sproget til domæneteori . Denotationssemantiske beskrivelser kan også tjene som kompositionelle oversættelser fra et programmeringssprog til denotationelle metalsprog og bruges som grundlag for at designe kompilatorer .
- Operationel semantik , hvorved sprogets eksekvering beskrives direkte (snarere end ved oversættelse). Operationel semantik svarer løst til fortolkning , selvom tolken "implementeringssprog" generelt set generelt er en matematisk formalisme. Operationel semantik kan definere en abstrakt maskine (såsom SECD -maskinen ) og give mening til sætninger ved at beskrive de overgange, de fremkalder på maskinens tilstande. Alternativt, som med den rene lambda -beregning , kan operationel semantik defineres via syntaktiske transformationer på selve sprogets sætninger;
- Aksiomatisk semantik , hvorved man giver mening til sætninger ved at beskrive de aksiomer, der gælder for dem. Axiomatisk semantik skelner ikke mellem en sætnings betydning og de logiske formler, der beskriver den; dens betydning er præcis, hvad der kan bevises om det i en eller anden logik. Det kanoniske eksempel på aksiomatisk semantik er Hoare -logik .
Bortset fra valget mellem denotationelle, operationelle eller aksiomatiske tilgange, stammer de fleste variationer i formelle semantiske systemer fra valget af understøttende matematisk formalisme.
Variationer
Nogle variationer af formel semantik omfatter følgende:
- Handlingssemantik er en tilgang, der forsøger at modulere denotationssemantik, opdele formaliseringsprocessen i to lag (makro og mikrosemantik) og foruddefinere tre semantiske enheder (handlinger, data og giver) for at forenkle specifikationen;
- Algebraisk semantik er en form for aksiomatisk semantik baseret på algebraiske love til at beskrive og ræsonnere om programsemantik på en formel måde;
- Attributgrammatik definerer systemer, der systematisk beregner " metadata " (kaldet attributter ) for de forskellige tilfælde af sprogets syntaks . Attributgrammatik kan forstås som en denotationssemantik, hvor målsproget simpelthen er originalsproget beriget med attributkommentarer. Bortset fra formel semantik er attributgrammatik også blevet brugt til kodegenerering i kompilatorer og til at udvide almindelige eller kontekstfrie grammatikker med kontekstfølsomme betingelser;
- Kategorisk (eller "functorial") semantik bruger kategoriteori som den matematiske kerneformalisme. En kategorisk semantik viser sig normalt at svare til nogle aksiomatiske semantikker, der giver en syntaktisk præsentation af de kategoriske strukturer. Denotationssemantik er også ofte forekomster af en generel kategorisk semantik,
- Samtidssemantik er et overordnet udtryk for enhver formel semantik, der beskriver samtidige beregninger. Historisk vigtige samtidige formalismer har inkluderet aktørmodellen og procesberegningerne ;
- Spilsemantik bruger en metafor inspireret af spilteori .
- Predicate transformer semantics , udviklet af Edsger W. Dijkstra , beskriver betydningen af et programfragment som funktionen, der transformerer en postbetingelse til den forudsætning, der er nødvendig for at etablere den.
Beskrivelse af relationer
Af forskellige årsager kan man ønske at beskrive forholdet mellem forskellige formelle semantikker. For eksempel:
- At bevise, at en bestemt operationel semantik for et sprog opfylder de logiske formler for en aksiomatisk semantik for dette sprog. Et sådant bevis viser, at det er "sundt" at ræsonnere om en bestemt (operationel) fortolkningsstrategi ved hjælp af et bestemt (aksiomatisk) bevissystem .
- For at bevise, at operationel semantik over en maskine på højt niveau hænger sammen med en simulering med semantikken over en maskine på lavt niveau, hvorved den abstrakte maskine på lavt niveau indeholder mere primitive operationer end den abstrakte maskindefinition på højt niveau for et givet sprog. Et sådant bevis viser, at maskinen på lavt niveau "trofast implementerer" maskinen på højt niveau.
Det er også muligt at relatere flere semantikker gennem abstraktioner via teorien om abstrakt fortolkning .
Historie
Robert W. Floyd krediteres for at have grundlagt området programmeringssprogssemantik i Floyd (1967) .
Se også
- Computational semantics
- Formel semantik (logik)
- Formel semantik (lingvistik)
- Ontologi
- Ontologi (informationsvidenskab)
- Semantisk ækvivalens
- Semantisk teknologi
Referencer
Yderligere læsning
- Lærebøger
- Floyd, Robert W. (1967). "Tildeling af betydninger til programmer" (PDF) . I Schwartz, JT (red.). Matematiske aspekter af datalogi . Proceedings of Symposium on Applied Mathematics. 19 . American Mathematical Society. s. 19–32. ISBN 0821867288.
- Hennessy, M. (1990). Semantikken i programmeringssprog: en elementær introduktion ved hjælp af strukturel operationel semantik . Wiley. ISBN 978-0-471-92772-3.
- Tennent, Robert D. (1991). Semantik i programmeringssprog . Prentice Hall. ISBN 978-0-13-805599-8.
- Gunter, Carl (1992). Semantik i programmeringssprog . MIT Tryk. ISBN 0-262-07143-6.
- Nielson, HR; Nielson, Flemming (1992). Semantik med applikationer: En formel introduktion (PDF) . Wiley. ISBN 978-0-471-92980-2.
- Winskel, Glynn (1993). Den formelle semantik i programmeringssprog: En introduktion . MIT Tryk. ISBN 0-262-73103-7.
- Mitchell, John C. (1995). Fundamenter til programmeringssprog (efterskrift) .
- Slonneger, Kenneth ; Kurtz, Barry L. (1995). Formel syntaks og semantik i programmeringssprog . Addison-Wesley. ISBN 0-201-65697-3.
- Reynolds, John C. (1998). Teorier om programmeringssprog . Cambridge University Press. ISBN 0-521-59414-6.
- Harper, Robert (2006). Praktiske grundlag for programmeringssprog (PDF) . Arkiveret fra originalen (PDF) den 2007-06-27. (Arbejdsudkast)
- Nielson, HR; Nielson, Flemming (2007). Semantik med applikationer: En appetitvækker . Springer. ISBN 978-1-84628-692-6.
- Stump, Aaron (2014). Programmeringssprogfundamenter . Wiley. ISBN 978-1-118-00747-1.
- Krishnamurthi, Shriram (2012). "Programmeringssprog: Anvendelse og fortolkning" (2. udgave).
- Foredragsnotater
- Winskel, Glynn. "Denotational Semantics" (PDF) . University of Cambridge.
eksterne links
- Aaby, Anthony (2004). Introduktion til programmeringssprog . Arkiveret fra originalen 2015-06-19.CS1 -vedligeholdelse: bot: original URL -status ukendt ( link ) Semantik.