Denotační sémantika - Denotational semantics - Wikipedia

Sémantika
Výpočetní
Typy
Teorie
Analýza
Aplikace

v počítačová věda, denotační sémantika (původně známé jako matematická sémantika nebo Scott – Strachey sémantika) je přístup formalizace významů programovací jazyky konstrukcí matematických objektů (tzv označení), které popisují význam výrazů z jazyků. Poskytují další přístupy formální sémantika programovacích jazyků počítaje v to axiomatická sémantika a operační sémantika.

Obecně řečeno, denotační sémantika se zabývá hledáním nazývaných matematických objektů domén které představují to, co programy dělají. Například programy (nebo programové fráze) mohou být reprezentovány dílčí funkce nebo hrami mezi prostředím a systémem.

Je to důležitý princip denotační sémantiky sémantika by měla být kompoziční: denotace programové fráze by měla být postavena z jejích denotací podfráze.

Historický vývoj

Denotační sémantika vznikla v díle Christopher Strachey a Dana Scott publikováno na začátku 70. let.[1] Jak původně vyvinuli Strachey a Scott, denotační sémantika poskytla význam počítačového programu jako funkce který mapoval vstup na výstup.[2] Dát význam rekurzivně definované programy, Scott navrhl spolupráci s spojité funkce mezi domén konkrétně kompletní dílčí objednávky. Jak je popsáno níže, pokračovaly práce na zkoumání vhodné denotační sémantiky pro aspekty programovacích jazyků, jako je sekvenčnost, konkurence, nedeterminismus a místní stát.

Denotační sémantika byla vyvinuta pro moderní programovací jazyky, které využívají možnosti jako konkurence a výjimky, např. Souběžné ML,[3] CSP,[4] a Haskell.[5] Sémantika těchto jazyků je kompoziční v tom, že význam fráze závisí na významech jejích subfrází. Například význam aplikační výraz f (E1, E2) je definován z hlediska sémantiky jeho subfrází f, E1 a E2. V moderním programovacím jazyce lze E1 a E2 hodnotit souběžně a provedení jednoho z nich může ovlivnit druhé interakcí prostřednictvím sdílené objekty což způsobí, že jejich významy budou definovány navzájem. Také E1 nebo E2 mohou vyvolat výjimku, která by mohla vypovědět poprava toho druhého. V následujících částech jsou popsány zvláštní případy sémantiky těchto moderních programovacích jazyků.

Význam rekurzivních programů

Denotační sémantika se programové frázi připisuje jako funkce z prostředí (obsahující aktuální hodnoty jeho volných proměnných) do jeho denotace. Například fráze n * m produkuje denotaci, pokud je poskytována v prostředí, které má vazbu pro své dvě volné proměnné: n a m. Pokud v prostředí n má hodnotu 3 a m má hodnotu 5, pak denotace je 15.[Citace je zapotřebí ]

Funkce může být reprezentována jako sada objednané páry argumentu a odpovídajících výsledných hodnot. Například množina {(0,1), (4,3)} označuje funkci s výsledkem 1 pro argument 0, výsledkem 3 pro argument 4 a jinak nedefinováno.

Úkolem, který je třeba vyřešit, je poskytnout význam rekurzivním programům, které jsou definovány samy o sobě, jako je definice faktoriál fungovat jako

int faktoriál(int n) { -li (n == 0) pak vrátit se 1; jiný vrátit se n * faktoriál(n-1); }

Řešením je vybudovat významy aproximací. Faktoriální funkce je a celková funkce od ℕ do ℕ (definované všude v jeho doméně), ale modelujeme to jako a částečná funkce. Na začátku začneme s prázdná funkce (prázdná sada). Dále přidáme uspořádanou dvojici (0,1) do funkce, abychom získali další dílčí funkci, která lépe aproximuje faktoriální funkci. Poté přidáme ještě další objednaný pár (1,1), abychom vytvořili ještě lepší aproximaci.

Je poučné myslet na tento řetězec iterací pro „částečnou faktoriální funkci“ F tak jako F0, F1, F2, ... kde Fn označuje F aplikovaný n krát.

  • F0({}) je zcela nedefinovaná částečná funkce, představovaná jako množina {};
  • F1({}) je částečná funkce představovaná jako množina {(0,1)}: je definována na 0, má být 1 a jinde není definována;
  • F5({}) je částečná funkce představovaná jako množina {(0,1), (1,1), (2,2), (3,6), (4,24)}: je definována pro argumenty 0 , 1,2,3,4.

Tento iterativní proces vytváří posloupnost dílčích funkcí od ℕ do ℕ. Dílčí funkce tvoří a řetěz kompletní částečná objednávka pomocí ⊆ jako objednávání. Navíc tento iterativní proces lepších aproximací faktoriální funkce tvoří expanzivní (také nazývané progresivní) mapování, protože každý pomocí ⊆ jako objednávání. Takže a věta o pevném bodě (konkrétně Bourbakiho-Wittova věta ), existuje pevný bod pro tento iterativní proces.

V tomto případě je pevný bod nejmenší horní mez tohoto řetězce, která je úplná faktoriál funkce, kterou lze vyjádřit jako přímý limit

Zde je symbol „⊔“ řízené spojení (z řízené sady ), což znamená „nejmenší horní mez“. Směrované spojení je v zásadě připojit se řízených sad.

Denotační sémantika nedeterministických programů

Koncept energetické domény byl vyvinut s cílem poskytnout denotační sémantiku nedeterministickým sekvenčním programům. Psaní P pro konstruktor power-domain, doménu P(D) je doménou nedeterministických výpočtů typu označeného D.

Existují potíže se spravedlností a neomezenost v doméno-teoretických modelech nedeterminismu.[6]

Denotační sémantika souběžnosti

Mnoho vědců tvrdí, že výše uvedené modely doménové teorie nestačí pro obecnější případ souběžný výpočet. Z tohoto důvodu různé nové modely byly zavedeny. Na začátku 80. let začali lidé používat styl denotační sémantiky, aby sémantiku získali souběžné jazyky. Mezi příklady patří Will Clinger pracuje s hereckým modelem; Práce Glynna Winskela se strukturami událostí a Petriho sítě;[7] a práce Franceze, Hoare, Lehmanna a de Roevera (1979) o stopové sémantice pro CSP.[8] Všechny tyto linie vyšetřování zůstávají předmětem šetření (viz např. Různé denotační modely pro CSP[4]).

Nedávno společnost Winskel a další navrhli kategorii profesoři jako doménová teorie pro souběžnost.[9][10]

Denotační sémantika státu

Stav (například hromada) a jednoduchý imperativní funkce lze přímo modelovat v denotační sémantice popsané výše. Všechny učebnice níže mají podrobnosti. Klíčovou myšlenkou je považovat příkaz za částečnou funkci v určité doméně států. Význam "x: = 3"je pak funkce, která bere stav do stavu s 3 přiřazen X. Operátor řazení;„je označeno složením funkcí. Konstrukce s pevným bodem se poté používají k poskytnutí sémantiky smyčkovým konstrukcím, jako například„zatímco".

Věci se stávají obtížnějšími při modelování programů s lokálními proměnnými. Jedním z přístupů je přestat pracovat s doménami, ale interpretovat typy jako funktory z nějaké kategorie světů do kategorie domén. Programy jsou pak označeny přírodní spojité funkce mezi těmito funktory.[11][12]

Označení datových typů

Mnoho programovacích jazyků umožňuje uživatelům definovat rekurzivní datové typy. Typ seznamu čísel lze například určit pomocí

datový typ seznam = Nevýhody z nat * seznam | Prázdný

Tato část se zabývá pouze funkčními datovými strukturami, které se nemohou změnit. Konvenční imperativní programovací jazyky by obvykle umožnily změnit prvky takového rekurzivního seznamu.

Pro další příklad: typ označení netypový lambda kalkul je

datový typ D = D z (D → D)

Problém řešení doménových rovnic se zabývá hledáním domén, které modelují tyto druhy datových typů. Jedním z přístupů, zhruba řečeno, je považovat shromažďování všech domén za doménu samotnou a poté tam vyřešit rekurzivní definici. Níže uvedené učebnice uvádějí více podrobností.

Polymorfní datové typy jsou datové typy, které jsou definovány parametrem. Například typ α seznams je definováno

datový typ α seznam = Nevýhody z α * α seznam | Prázdný

Seznamy přirozených čísel jsou tedy typu nat seznam, zatímco seznamy řetězců jsou z seznam řetězců.

Někteří vědci vyvinuli doménové teoretické modely polymorfismu. Modelovali také další vědci parametrický polymorfismus v rámci konstruktivních množin teorií. Podrobnosti najdete v níže uvedených učebnicích.

Nedávná oblast výzkumu zahrnovala denotační sémantiku pro objektové a třídní programovací jazyky.[13]

Denotační sémantika pro programy omezené složitosti

V návaznosti na vývoj programovacích jazyků založených na lineární logika, denotační sémantika byla dána jazykům pro lineární použití (viz např. ochranné sítě, soudržné prostory ) a také polynomiální časová složitost.[14]

Denotační sémantika sekvenčnosti

Problém plného abstrakce pro sekvenční programovací jazyk PCF byla po dlouhou dobu velkou otevřenou otázkou v denotační sémantice. Potíž s PCF spočívá v tom, že se jedná o velmi sekvenční jazyk. Například neexistuje žádný způsob, jak definovat paralelně nebo funkce v PCF. Z tohoto důvodu přístup využívající domény, jak byl představen výše, přináší denotační sémantiku, která není zcela abstraktní.

Tato otevřená otázka byla většinou vyřešena v 90. letech s rozvojem herní sémantika a také s technikami zahrnujícími logické vztahy.[15] Další informace najdete na stránce PCF.

Denotační sémantika jako překlad ze zdroje na zdroj

Často je užitečné přeložit jeden programovací jazyk do jiného. Například souběžný programovací jazyk může být přeložen do a procesní kalkul; programovací jazyk na vysoké úrovni může být přeložen do bajtového kódu. (Konvenční denotační sémantiku lze skutečně chápat jako interpretaci programovacích jazyků do jazyka interní jazyk kategorie domén.)

V této souvislosti pojmy z denotační sémantiky, jako je úplná abstrakce, pomáhají uspokojit bezpečnostní obavy.[16][17]

Abstrakce

Často je považováno za důležité propojit denotační sémantiku s operační sémantika. To je zvláště důležité, když je denotační sémantika spíše matematická a abstraktní a operační sémantika je konkrétnější nebo blíže k výpočetním intuicím. Následující vlastnosti denotační sémantiky jsou často zajímavé.

  1. Nezávislost syntaxe: Označení programů by nemělo zahrnovat syntaxi zdrojového jazyka.
  2. Přiměřenost (nebo spolehlivost): Všechno viditelně odlišný programy mají odlišné označení;
  3. Plná abstrakce: Všechny observačně rovnocenné programy mají stejné denotace.

Pro sémantiku v tradičním stylu lze přiměřenost a úplnou abstrakci chápat zhruba jako požadavek, že „operativní ekvivalence se shoduje s denotační rovností“. Pro denotační sémantiku ve více intenzionálních modelech, jako je herec model a zpracovat kalkul, v rámci každého modelu existují různé pojmy ekvivalence, a proto jsou pojmy přiměřenosti a úplné abstrakce předmětem debaty a je těžší je určit. Také matematická struktura operativní sémantiky a denotační sémantiky se může velmi přiblížit.

Mezi další žádoucí vlastnosti, které si můžeme přát mezi provozní a denotační sémantikou, patří:

  1. Konstruktivismus: Konstruktivismus se zabývá otázkou, zda lze doménové prvky prokázat existencí konstruktivními metodami.
  2. Nezávislost denotační a operativní sémantiky: Denotační sémantika by měla být formalizována pomocí matematických struktur, které jsou nezávislé na operační sémantice programovacího jazyka; Základní koncepty však mohou úzce souviset. Viz část o Kompozičnost níže.
  3. Úplnost nebo definovatelnost: Každý morfismus sémantického modelu by měl být denotací programu.[18]

Kompozičnost

Důležitým aspektem denotační sémantiky programovacích jazyků je kompozičnost, při které je denotace programu konstruována z denotací jeho částí. Zvažte například výraz „7 + 4“. Kompozičnost v tomto případě znamená poskytnout význam slova „7 + 4“ ve smyslu významů „7“, „4“ a „+“.

Základní denotační sémantika v doménové teorii je kompoziční, protože je uvedena následovně. Začneme zvážením fragmentů programů, tj. Programů s volnými proměnnými. A kontext psaní přiřadí typ každé volné proměnné. Například ve výrazu (X + y) lze považovat v kontextu psaní (X:nat,y:nat). Nyní dáváme denotační sémantiku programovým fragmentům pomocí následujícího schématu.

  1. Začneme popisem významu typů našeho jazyka: významem každého typu musí být doména. Napíšeme 〚τ〛 pro doménu označující typ τ. Například význam typu nat by měla být doménou přirozených čísel: 〚nat〛 = ℕ⊥.
  2. Z významu typů odvozujeme význam pro psaní kontextů. Jsme si stanovili [ X1: τ1,..., Xn: τn〛 = 〚Τ1〛 × ... × 〚τn〛. Například, [X:nat,y:nat>〛 = ℕ⊥× ℕ⊥. Jako zvláštní případ je významem prázdného kontextu psaní bez proměnných doména s jedním prvkem, označeným 1.
  3. Nakonec musíme dát každému kontextu fragmentu programu při psaní smysl. Předpokládejme to P je programový fragment typu σ, v kontextu psaní Γ, často psaný Γ⊢P: σ. Poté musí být významem tohoto kontextu při psaní programu spojitá funkce 〚Γ⊢P: σ〛: 〚Γ〛 → 〚σ〛. Například 〚⊢7:nat〛: 1 → ℕ⊥ je funkce „7“, zatímco 〚X:nat,y:nat⊢X+y:nat〛: ℕ⊥× ℕ⊥→ ℕ⊥ je funkce, která sčítá dvě čísla.

Nyní je význam složeného výrazu (7 + 4) určen složením tří funkcí 〚⊢7:nat〛: 1 → ℕ⊥, 〚⊢4:nat〛: 1 → ℕ⊥, a [X:nat,y:nat⊢X+y:nat〛: ℕ⊥× ℕ⊥→ ℕ⊥.

Ve skutečnosti se jedná o obecné schéma pro kompoziční denotační sémantiku. O doménách a nepřetržitých funkcích zde není nic konkrétního. Jeden může pracovat s jiným kategorie namísto. Například v herní sémantice má kategorie her hry jako objekty a strategie jako morfismy: typy můžeme interpretovat jako hry a programy jako strategie. U jednoduchého jazyka bez obecné rekurze si vystačíme s kategorie množin a funkcí. U jazyka s vedlejšími účinky můžeme pracovat v Kategorie Kleisli pro monad. U jazyka se státem můžeme pracovat v a kategorie funktorů. Milner obhajoval umístění a interakci modelování prací v kategorii s rozhraními jako objekty a bigrafy jako morfismy.[19]

Sémantika versus implementace

Podle Dany Scottové (1980):[20]

Pro sémantiku není nutné určit implementaci, ale měla by poskytnout kritéria pro prokázání, že implementace je správná.

Podle Clingera (1981):[21]:79

Obvykle však může být formální sémantika konvenčního sekvenčního programovacího jazyka sama interpretována tak, aby poskytovala (neefektivní) implementaci jazyka. Formální sémantika nemusí vždy poskytovat takovou implementaci a věřit, že sémantika musí poskytovat implementaci, vede k nejasnostem ohledně formální sémantiky souběžných jazyků. Takový zmatek je bolestně evidentní, když se říká, že přítomnost neomezeného nedeterminismu v sémantice programovacího jazyka znamená, že programovací jazyk nelze implementovat.

Propojení s dalšími oblastmi počítačové vědy

Některé práce v denotační sémantice interpretovaly typy jako domény ve smyslu teorie domén, na které lze pohlížet jako na větev teorie modelů, vedoucí ke spojení s teorie typů a teorie kategorií. V rámci počítačové vědy existují vazby na abstraktní interpretace, ověření programu, a kontrola modelu.

Reference

  1. ^ Dana S. Scott. Nástin matematické teorie výpočtu. Technická monografie PRG-2, Oxford University Computing Laboratory, Oxford, Anglie, listopad 1970.
  2. ^ Dana Scott a Christopher Strachey. Směrem k matematické sémantice pro počítačové jazyky Technická monografie Oxford Programming Research Group. PRG-6. 1971.
  3. ^ John Reppy „Souběžný ML: design, aplikace a sémantika“ ve Springer-Verlag, Přednášky z informatiky, Sv. 693. 1993
  4. ^ A b A. W. Roscoe. „Teorie a praxe souběžnosti“ Prentice-Hall. Revidováno 2005.
  5. ^ Simon Peyton Jones Alastair Reid, Fergus Henderson, Tony Hoare a Simon Marlow. "Sémantika pro nepřesné výjimky „Konference o návrhu a implementaci programovacího jazyka. 1999.
  6. ^ Levy, Paul Blain (2007). „Amb rozbíjí špičatost, Ground Amb ne“. Elektr. Poznámky Theor. Comput. Sci. 173: 221–239. doi:10.1016 / j.entcs.2007.02.036.
  7. ^ Sémantika struktury událostí pro CCS a související jazyky. Zpráva o výzkumu DAIMI, University of Aarhus, 67 s., Duben 1983.
  8. ^ Nissim Francez, C. A. R. Hoare, Daniel Lehmann a Willem-Paul de Roever. "Sémantika nedeterminismu, souběžnosti a komunikace ", Journal of Computer and System Sciences. Prosinec 1979.
  9. ^ Cattani, Gian Luca; Winskel, Glynn (2005). "Profunktory, otevřené mapy a bisimulace". Matematické struktury v informatice. 15 (3): 553–614. CiteSeerX  10.1.1.111.6243. doi:10.1017 / S0960129505004718.
  10. ^ Nygaard, Mikkel; Winskel, Glynn (2004). "Teorie domén pro souběžnost". Teor. Comput. Sci. 316 (1–3): 153–190. doi:10.1016 / j.tcs.2004.01.029.
  11. ^ Peter W. O'Hearn John Power, Robert D. Tennent, Makoto Takeyama. Znovu navštíveno syntaktické řízení rušení. Elektr. Poznámky Theor. Comput. Sci. 1. 1995.
  12. ^ Frank J. Oles. Kategorie-teoretický přístup k sémantice programování. Disertační práce, Syrakuská univerzita, New York, USA. 1982.
  13. ^ Reus, Bernhard; Streicher, Thomas (2004). "Sémantika a logika objektových kalkulů". Teor. Comput. Sci. 316 (1): 191–213. doi:10.1016 / j.tcs.2004.01.030.
  14. ^ Baillot, P. (2004). "Stratifikované koherenční prostory: denotační sémantika pro Light Linear Logic". Teor. Comput. Sci. 318 (1–2): 29–55. doi:10.1016 / j.tcs.2003.10.015.
  15. ^ O'Hearn, P.W .; Riecke, J.G. (Červenec 1995). „Kripke Logical Relations and PCF“. Informace a výpočet. 120 (1): 107–116. doi:10.1006 / inco.1995.1103.
  16. ^ Martin Abadi. "Ochrana v překladech do programovacího jazyka". Proc. ICALP'98. LNCS 1443. 1998.
  17. ^ Kennedy, Andrew (2006). "Zabezpečení .NET programovacího modelu". Teor. Comput. Sci. 364 (3): 311–7. doi:10.1016 / j.tcs.2006.08.014.
  18. ^ Curien, Pierre-Louis (2007). „Definovatelnost a úplná abstrakce“. Elektronické poznámky v teoretické informatice. 172: 301–310. doi:10.1016 / j.entcs.2007.02.011.
  19. ^ Milner, Robin (2009). Prostor a pohyb komunikujících agentů. Cambridge University Press. ISBN  978-0-521-73833-0. Návrh z roku 2009 Archivováno 02.04.2012 na Wayback Machine.
  20. ^ „What is Denotational Semantics?“, MIT Laboratory for Computer Science Distinguished Lecture Series, 17. dubna 1980, citovaný v Clinger (1981).
  21. ^ Clinger, William D. (1981). „Základy herecké sémantiky“ (PhD). Massachusetts Institute of Technology. hdl:1721.1/6935. AITR-633. Citovat deník vyžaduje | deník = (Pomoc)

Další čtení

Učebnice
Poznámky z přednášky
Další reference

externí odkazy