Sémantické kódování - Semantics encoding

A kódování sémantiky je překlad mezi formální jazyky. Pro programátory je nejznámější formou kódování kompilace programovacího jazyka do strojového kódu nebo bajtového kódu. Konverze mezi formáty dokumentů jsou také formami kódování. Kompilace TeX nebo Latex dokumenty do PostScript se také běžně vyskytují v procesech kódování. Některé preprocesory na vysoké úrovni, jako např OCaml je Camlp4 také zahrnovat kódování programovacího jazyka do jiného.

Formálně je kódování jazyka A do jazyka B mapováním všech výrazů A do B. Pokud existuje a uspokojivý uvažuje se kódování A do B, B. přinejmenším stejně silný (nebo přinejmenším stejně expresivní) jako.

Vlastnosti

Neformální pojem překladu nestačí k určení expresivity jazyků, protože umožňuje triviální kódování, jako je mapování všech prvků A na stejný prvek B. Proto je nutné určit definici „dostatečně dobrého“ kódování . Tato představa se liší podle aplikace.

Běžně kódování ${ displaystyle [ cdot]: A longrightarrow B}$ Očekává se, že zachová řadu vlastností.

Uchování skladeb

zdravost: Pro každého operátora n-ary ${ displaystyle op_ {A}}$ z A existuje operátor n-ary ${ displaystyle op_ {B}}$ B takové, že; ${ displaystyle forall T_ {A} ^ {1}, T_ {A} ^ {2}, dots, T_ {A} ^ {n}, [op_ {A} (T_ {A} ^ {1}, T_ {A} ^ {2}, cdots, T_ {A} ^ {n})] = op_ {B} ([T_ {A} ^ {1}], [T_ {A} ^ {2}], cdots, [T_ {A} ^ {n}])}$
úplnost: Pro každého operátora n-ary ${ displaystyle op_ {A}}$ z A existuje operátor n-ary ${ displaystyle op_ {B}}$ z B takové, že; ${ displaystyle forall T_ {B} ^ {1}, T_ {B} ^ {2}, dots, T_ {B} ^ {n}, existuje T_ {A} ^ {1}, dots, T_ {A} ^ {n}, op_ {B} (T_ {B} ^ {1}, cdots, T_ {B} ^ {N}) = [op_ {A} (T_ {A} ^ {1}, T_ {A} ^ {2}, cdots, T_ {A} ^ {n})]}$

(Poznámka: pokud si je autor vědom, toto kritérium úplnosti se nikdy nepoužívá.)

Zachování kompozic je užitečné, protože zaručuje, že komponenty lze zkoumat buď samostatně, nebo společně, aniž by došlo k „rozbití“ jakékoli zajímavé vlastnosti. Zejména v případě kompilací tato spolehlivost zaručuje možnost pokračovat v samostatné kompilaci komponent, zatímco úplnost zaručuje možnost dekompilace.

Zachování redukcí

To předpokládá existenci pojmu redukce jak pro jazyk A, tak pro jazyk B. Typicky je v případě programovacího jazyka redukce relací, která modeluje provádění programu.

Píšeme ${ displaystyle longrightarrow}$ pro jeden krok redukce a ${ displaystyle longrightarrow ^ {*}}$ pro libovolný počet kroků redukce.

zdravost: Za každé období ${ displaystyle T_ {A} ^ {1}, T_ {A} ^ {2}}$ jazyka A, pokud ${ displaystyle T_ {A} ^ {1} longrightarrow ^ {*} T_ {A} ^ {2}}$ pak ${ displaystyle [T_ {A} ^ {1}] longrightarrow ^ {*} [T_ {A} ^ {2}]}$ .
úplnost: Pro každý termín ${ displaystyle T_ {A} ^ {1}}$ jazyka A a všech termínů ${ displaystyle T_ {B} ^ {2}}$ jazyka B, pokud ${ displaystyle [T_ {A} ^ {1}] longrightarrow ^ {*} T_ {B} ^ {2}}$ pak nějaké existují ${ displaystyle T_ {A} ^ {2}}$ takhle ${ displaystyle T_ {B} ^ {2} = [T_ {A} ^ {2}]}$ .

Toto zachování zaručuje, že se oba jazyky chovají stejně. Zdravost zaručuje, že jsou zachována všechna možná chování, zatímco úplnost zaručuje, že kódování nepřidá žádné chování. Zejména v případě kompilace programovacího jazyka znamená spolehlivost a úplnost dohromady to, že se kompilovaný program chová odpovídající sémantice programovacího jazyka na vysoké úrovni.

Zachování ukončení

To také předpokládá existenci pojmu redukce jak pro jazyk A, tak pro jazyk B.

zdravost: na jakýkoli termín ${ displaystyle T_ {A}}$ , pokud všechna snížení o ${ displaystyle T_ {A}}$ konvergovat, pak všechna snížení o ${ displaystyle [T_ {A}]}$ konvergovat.
úplnost: na jakýkoli termín ${ displaystyle [T_ {A}]}$ , pokud všechna snížení o ${ displaystyle [T_ {A}]}$ konvergovat, pak všechna snížení o ${ displaystyle T_ {A}}$ konvergovat.

V případě kompilace programovacího jazyka zaručuje spolehlivost, že kompilace nezavádí nekončení, jako jsou nekonečné smyčky nebo nekonečné rekurze. Vlastnost úplnosti je užitečná, když se jazyk B používá ke studiu nebo testování programu napsaného v jazyce A, případně extrahováním klíčových částí kódu: pokud tato studie nebo test prokáže, že program končí v B, končí také v A.

Uchovávání pozorování

To předpokládá existenci pojmu pozorování jak v jazyce A, tak v jazyce B. V programovacích jazycích jsou typické pozorovatelné výsledky vstupů a výstupů, na rozdíl od čistého výpočtu. V jazyce popisu, jako je HTML, typický pozorovatelný je výsledek vykreslování stránky.

zdravost: pro každého pozorovatelného ${ displaystyle obs_ {A}}$ z hlediska A existuje pozorovatelný ${ displaystyle obs_ {B}}$ podmínek B tak, že pro jakýkoli termín ${ displaystyle T_ {A}}$ s pozorovatelným ${ displaystyle obs_ {A}}$ , ${ displaystyle [T_ {A}]}$ má pozorovatelný ${ displaystyle obs_ {B}}$ .
úplnost: pro každého pozorovatelného ${ displaystyle obs_ {A}}$ z hlediska A existuje pozorovatelný ${ displaystyle obs_ {B}}$ za podmínek B tak, že pro jakýkoli termín ${ displaystyle [T_ {A}]}$ s pozorovatelným ${ displaystyle obs_ {B}}$ , ${ displaystyle T_ {A}}$ má pozorovatelný ${ displaystyle obs_ {A}}$ .

Zachování simulací

To předpokládá existenci pojmu simulace jak v jazyce A, tak v jazyce B. V programovacích jazycích program simuluje jiný, pokud může provádět všechny stejné (pozorovatelné) úkoly a případně i některé další. Simulace se obvykle používají k popisu optimalizace při kompilaci.

zdravost: za každé období ${ displaystyle T_ {A} ^ {1}, T_ {A} ^ {2}}$ , pokud ${ displaystyle T_ {A} ^ {2}}$ simuluje ${ displaystyle T_ {A} ^ {1}}$ pak ${ displaystyle [T_ {A} ^ {2}]}$ simuluje ${ displaystyle [T_ {A} ^ {1}]}$ .
úplnost: za každé období ${ displaystyle T_ {A} ^ {1}, T_ {A} ^ {2}}$ , pokud ${ displaystyle [T_ {A} ^ {2}]}$ simuluje ${ displaystyle [T_ {A} ^ {1}]}$ pak ${ displaystyle T_ {A} ^ {2}}$ simuluje ${ displaystyle T_ {A} ^ {1}}$ .

Zachování simulací je mnohem silnější vlastností než uchování pozorování, které s sebou nese. Na druhé straně je slabší než vlastnost zachování bisimulace. Stejně jako v předchozích případech je pro kompilaci důležitá spolehlivost, zatímco úplnost je užitečná pro testování nebo prokázání vlastností.

Zachování rovnocennosti

To předpokládá existenci pojmu ekvivalence jak pro jazyk A, tak pro jazyk B. Typicky to může být pojem rovnosti strukturovaných dat nebo pojem syntakticky odlišných, ale sémanticky identických programů, jako je strukturální shoda nebo strukturální ekvivalence.

zdravost: pokud dva termíny ${ displaystyle T_ {A} ^ {1}}$ a ${ displaystyle T_ {A} ^ {2}}$ jsou tedy ekvivalentní v A ${ displaystyle [T_ {A} ^ {1}]}$ a ${ displaystyle [T_ {A} ^ {2}]}$ jsou ekvivalentní v B.
úplnost: pokud dva termíny ${ displaystyle [T_ {A} ^ {1}]}$ a ${ displaystyle [T_ {A} ^ {2}]}$ jsou tedy ekvivalentní v B ${ displaystyle T_ {A} ^ {1}}$ a ${ displaystyle T_ {A} ^ {2}}$ jsou ekvivalentní v A.

Zachování distribuce

To předpokládá existenci pojmu distribuce jak v jazyce A, tak v jazyce B. Typicky pro kompilaci distribuovaných programů napsaných v Akutní, JoCaml nebo E, to znamená distribuci procesů a dat mezi několik počítačů nebo procesorů.

zdravost: pokud termín ${ displaystyle T_ {A}}$ je složení dvou látek ${ displaystyle T_ {A} ^ {1} ~ | ~ T_ {A} ^ {2}}$ pak ${ displaystyle [T_ {A}]}$ musí být složení dvou látek ${ displaystyle [T_ {A} ^ {1}] ~ | ~ [T_ {A} ^ {2}]}$ .
úplnost: pokud termín ${ displaystyle [T_ {A}]}$ je složení dvou látek ${ displaystyle T_ {B} ^ {1} ~ | ~ T_ {B} ^ {2}}$ pak ${ displaystyle T_ {B}}$ musí být složení dvou látek ${ displaystyle T_ {A} ^ {1} ~ | ~ T_ {A} ^ {2}}$ takhle ${ displaystyle [T_ {A} ^ {1}] = T_ {B} ^ {1}}$ a ${ displaystyle [T_ {A} ^ {2}] = T_ {B} ^ {2}}$ .

Viz také

externí odkazy

Program Transformace Wiki