Hlídaný velitelský jazyk - Guarded Command Language

The Hlídaný velitelský jazyk (GCL) je jazyk definovaný Edsger Dijkstra pro sémantika predikátových transformátorů.^[1] Kombinuje programovací koncepty kompaktním způsobem, než je program napsán v nějakém praktickém programovacím jazyce. Jeho jednoduchost usnadňuje ověřování správnosti programů Logika hoare.

Hlídané velení

Strážený příkaz je nejdůležitějším prvkem jazyka stráženého příkazu. V hlídaném příkazu je příkaz, jak již název napovídá, „hlídán“. Strážný je tvrzení, což musí být pravda, než bude tvrzení popraven. Na začátku provádění tohoto prohlášení lze předpokládat, že stráž je pravdivá. Pokud je strážný falešný, příkaz nebude proveden. Použití hlídaných příkazů usnadňuje prokázání program splňuje Specifikace. Toto prohlášení je často dalším střeženým příkazem.

Syntax

Hlídaný příkaz je a prohlášení formy G → S, kde

G je a tvrzení zavolal strážný
S je prohlášení

Pokud je G pravdivé, může být chráněný příkaz napsán jednoduše S.

Sémantika

V okamžiku, kdy se ve výpočtu objeví G, vyhodnotí se.

Pokud je G pravda, proveďte S
Pokud je G nepravdivé, podívejte se na kontext a rozhodněte se, co dělat (v žádném případě neprovádějte S)

Přeskočit a přerušit

Přeskočit a Přerušit jsou velmi jednoduchá i důležitá prohlášení v hlídaném příkazovém jazyce. Abort je nedefinovaná instrukce: dělat cokoli. Prohlášení o zrušení není nutné ani ukončovat. Používá se k popisu programu při formulování důkazu, v takovém případě se důkaz obvykle nezdaří. Přeskočit je prázdná instrukce: nedělat nic. Používá se v samotném programu, když syntaxe vyžaduje příkaz, ale programátor nechce, aby se stroj změnil státy.

Syntax

přeskočit

přerušit

Sémantika

Přeskočit: nedělat nic
Přerušit: dělat cokoli

Úkol

Přiřadí hodnoty proměnné.

Syntax

v: = E

nebo

v0, v1, ..., vn: = E0, E1, ..., En

kde

v jsou programové proměnné
E jsou výrazy stejné datový typ jako jejich odpovídající proměnné

Zřetězení

Výpisy jsou odděleny jedním středníkem (;)

Výběr: pokud

Výběr (často nazývaný „podmíněný příkaz“ nebo „příkaz if“) je seznam chráněných příkazů, z nichž jeden je vybrán k provedení. Pokud má více než jeden strážce pravdu, je jeden příkaz nedeterministicky vybrán k provedení. Pokud žádný ze strážců není pravdivý, výsledek není definován. Protože alespoň jeden ze strážců musí být pravdivý, je často nutné prázdné prohlášení „přeskočit“.

Syntax

-li G0 → S0 | G1 → S1 ... | Gn → Snfi

Sémantika

Po provedení výběru jsou vyhodnoceni všichni strážci. Pokud žádný ze strážců není vyhodnocen jako pravdivý, pak se provedení výběru přeruší, jinak je jeden ze strážců, který má hodnotu true, vybrán nedeterministicky a je proveden odpovídající příkaz.^[2]

Příklady

Jednoduchý

v pseudo kód:

pokud a

else c: = False

V hlídaném příkazovém jazyce:

-li a fi

Použití přeskočení

V pseudokódu:

if error = True then x: = 0

V hlídaném příkazovém jazyce:

-li chyba = pravda → x: = 0 | error = false → přeskočitfi

Pokud je druhý strážný vynechán a chyba = False, výsledek se zruší.

Více stráží pravda

-li a ≥ b → max: = a | b ≥ a → max: = bfi

Pokud a = b, je jako nová hodnota maxima zvoleno buď a nebo b se stejnými výsledky. Někdo však provádění to může zjistit, že jeden je jednodušší nebo rychlejší než druhý. Jelikož programátor nemá žádný rozdíl, může jej implementovat libovolně.

Opakování: dělat

Opakování provádí hlídané příkazy opakovaně, dokud žádný z hlídačů není pravdivý. Obvykle je jen jeden strážce.

Syntax

dělat G0 → S0 | G1 → S1 ... | Gn → Snod

Sémantika

Po provedení opakování jsou všichni strážci vyhodnoceni. Pokud všechny stráže vyhodnotí jako nepravdivé, provede se přeskočení. Jinak je jeden ze strážců, který má hodnotu true, vybrán nedeterministicky a je proveden odpovídající příkaz, po kterém je opakování provedeno znovu.

Příklady

Originál Euklidovský algoritmus

a, b: = A, B;dělat a od

Toto opakování končí, když a = b, v takovém případě a a b drží největší společný dělitel A a B.

Dijkstra v tomto algoritmu vidí způsob synchronizace dvou nekonečných cyklů a: = a - b a b: = b - a takovým způsobem, že a ≥0 a b≥0 zůstává pravdou.

Rozšířený euklidovský algoritmus

a, b, x, y, u, v: = A, B, 1, 0, 0, 1;dělat b ≠ 0 → | q, r: = a div b, a mod b; | a, b, x, y, u, v: = b, r, u, v, x - q * u, y - q * vod

Toto opakování končí, když b = 0, v takovém případě proměnné drží řešení Bézoutova identita: xA + yB = gcd (A, B).

Nedeterministické třídění

dělat a> b → a, b: = b, a | b> c → b, c: = c, b | c> d → c, d: = d, cod

Program udržuje permutující prvky, zatímco jeden z nich je větší než jeho nástupce. To není deterministické třídění bublin není efektivnější než jeho deterministická verze, ale je snazší prokázat: nezastaví se, když prvky nejsou tříděny a že každý krok třídí alespoň 2 prvky.

Arg max

x, y = 1, 1 dělat x ≠ n → | -li f (x) ≤ f (y) → x: = x + 1 | | f (x) ≥ f (y) → y: = x; x: = x + 1 | fiod

Tento algoritmus najde hodnotu 1 ≤ y ≤ n pro které je daná celočíselná funkce F je maximální. Nejen výpočet, ale také konečný stav nemusí být nutně jednoznačně určen.

Aplikace

Programy opravují konstrukci

Zobecnění pozorovacího shoda hlídaných příkazů do a mříž vedlo k Zušlechťovací počet.^[3] Toto bylo mechanizováno dovnitř Formální metody jako B-metoda které umožňují formálně odvodit programy z jejich specifikací.

Asynchronní obvody

Hlídané příkazy jsou vhodné pro obvod necitlivý na kvazi zpoždění design, protože opakování umožňuje libovolné relativní zpoždění pro výběr různých příkazů. V této aplikaci logická brána pohánějící uzel y v obvodu se skládá ze dvou hlídaných příkazů, a to následovně:

PullDownGuard → y: = 0 PullUpGuard → y: = 1

PullDownGuard a PullUpGuard zde jsou funkce vstupů logické brány, které popisují, kdy brána táhne výstup dolů, respektive nahoru. Na rozdíl od klasických modelů vyhodnocení obvodu může opakování sady chráněných příkazů (odpovídající asynchronnímu obvodu) přesně popsat všechna možná dynamická chování daného obvodu. V závislosti na modelu je člověk ochoten žít s prvky elektrického obvodu, další omezení na strážné příkazy mohou být nezbytné, aby byl popis strážného příkazu zcela uspokojivý. Mezi běžná omezení patří stabilita, nezasahování a absence samo-zneplatňujících příkazů.^[4]

Kontrola modelu

V rámci Promela programovací jazyk, který používá Kontrola modelu SPIN. SPIN ověřuje správnou funkci souběžných softwarových aplikací.

jiný

Modul Perl Příkazy :: Hlídané implementuje deterministickou, opravnou variantu na hlídané příkazy Dijkstra.

Reference

^ Dijkstra, Edsger W.. "EWD472: Hlídané příkazy, neurčitost a formální. Odvozování programů" (PDF). Citováno 16. srpna 2006.
^ Anne Kaldewaij (1990), Programování: Odvození algoritmů, Prentice Hall
^ Zpět, Ralph J. (1978). „O správnosti kroků zdokonalení při vývoji programu (disertační práce)“ (PDF). Archivovány od originál (pdf) dne 2011-07-20.
^ Martin, Alain J. "Syntéza asynchronních obvodů VLSI".

[EWD472-1] Dijkstra, Edsger W.. "EWD472: Hlídané příkazy, neurčitost a formální. Odvozování programů" (PDF). Citováno 16. srpna 2006.

[Kal90-2] Anne Kaldewaij (1990), Programování: Odvození algoritmů, Prentice Hall

[3] Zpět, Ralph J. (1978). „O správnosti kroků zdokonalení při vývoji programu (disertační práce)“ (PDF). Archivovány od originál (pdf) dne 2011-07-20.

[synthesis_tr-4] Martin, Alain J. "Syntéza asynchronních obvodů VLSI".

[1]

[2]

[3]

[4]