Programování na základě automatů - Automata-based programming

Programování na základě automatů je paradigma programování ve kterém je program nebo jeho část považována za model a konečný stavový stroj (FSM) nebo jakýkoli jiný (často komplikovanější) formální automat (viz teorie automatů ). Někdy je zavedena potenciálně nekonečná množina možných stavů a ​​taková množina může mít komplikovanou strukturu, nejen výčet.

Konečné stavové strojové programování je obecně stejný, ale formálně vzato nepokrývá všechny možné varianty, protože FSM znamená stroj s konečným stavem a programování na základě automatů nemusí nutně využívat FSM v užším slova smyslu.

Následující vlastnosti jsou klíčové indikátory pro programování na základě automatů:

• Časové období provádění programu je jasně odděleno až k automatické kroky. Každý krok je ve skutečnosti provedení části kódu (stejná pro všechny kroky), která má jediný vstupní bod. Tato část může být rozdělena na podsekce, které mají být provedeny v závislosti na různých státech, i když to není nutné.
• Jakákoli komunikace mezi kroky automatu je možná pouze prostřednictvím výslovně uvedené sady proměnných s názvem stav automatu. Mezi jakýmikoli dvěma kroky nemůže program mít implicitní složky svého stavu, jako jsou hodnoty lokálních proměnných, zpáteční adresy, ukazatel aktuální instrukce atd. To znamená stav celého programu, který se bere v jakýchkoli dvou okamžicích vstupu do krok automatu, může se lišit pouze v hodnotách proměnných považovaných za stav automatu.

Celé provedení kódu založeného na automatech je a cyklus automatických kroků.

Dalším důvodem pro použití pojmu programování na základě automatů je to, že programátorův styl myšlení o programu v této technice je velmi podobný stylu myšlení používaného k řešení matematických úkolů pomocí Turingovy stroje, Markovovy algoritmy, atd.

Příklad

Úkol

Zvažte úlohu čtení textu z standardní vstup řádek po řádku a psaní prvního slova každého řádku do standardní výstup. Nejprve přeskočíme všechny vedoucí mezery znaky, pokud existují. Poté vytiskneme všechny znaky prvního slova. Nakonec přeskočíme všechny koncové znaky až do a nový řádek znak je narazen. Kdykoli se na začátku streamu setkáte se sekvencí znaků nového řádku, vytiskneme pouze první a zbývající vynecháme; jinak přeskočíme vše. Dále proces restartujeme na následujícím řádku. Po setkání s konec souboru stav (bez ohledu na fázi), zastavíme.

Tradiční program

Tradiční program v C který provádí výše uvedený úkol, může vypadat takto:

#zahrnout <ctype.h>#zahrnout <stdio.h>int hlavní(prázdnota) {  int C;  dělat {    dělat {      C = getchar();    } zatímco (isspace(C));    zatímco (!isspace(C) && C != EOF) {      putchar(C);      C = getchar();    }        zatímco (C != ' n' && C != EOF) {      C = getchar();    }        -li (C == ' n') {      putchar(C);    }  } zatímco (C != EOF);  vrátit se 0;}

Například kompilace a spuštění výše uvedeného programu na tomto vstupu:

$ clang program. c && (printf " t  v  f  r  n  n  t  v  f  r foo bar baz  n  n  t  v  f  r qux quux corge" | ./a.out)

výnosy:

fooqux

Program založený na automatech

Procesní

Stejný úkol lze vyřešit uvažováním v pojmech stroje konečného stavu. Všimněte si, že analýza řádku má tři fáze: přeskočení úvodních prázdných znaků, tisk znaků prvního slova a přeskočení koncových znaků. Říkejme tyto stavy automatu PŘED, UVNITŘ a PO. Verze programu založená na automatech může vypadat takto:

#zahrnout <ctype.h>#zahrnout <stdio.h>výčet Stát {PŘED, UVNITŘ, PO};int hlavní(prázdnota) {  int C;  výčet Stát s = PŘED;  zatímco ((C = getchar()) != EOF) {    přepínač (s) {      případ PŘED:        -li (!isspace(C)) {          putchar(C);          s = UVNITŘ;        }                přestávka;      případ UVNITŘ:        -li (C == ' n') {          putchar(C);          s = PŘED;        } jiný -li (isspace(C)) {          s = PO;        } jiný {          putchar(C);        }                  přestávka;      případ PO:        -li (C == ' n') {          putchar(C);          s = PŘED;        }                přestávka;    }  }  vrátit se 0;}

Přestože program nyní vypadá déle, má alespoň jednu významnou výhodu: existuje pouze jedno čtení (tj. volání na getchar funkce). Kromě toho existuje pouze jedna smyčka místo čtyř, které měla tradiční verze. Tělo zatímco smyčka je automatický krok a samotná smyčka je cyklus kroku automatu. Program implementuje práci stroje s konečným stavem znázorněným ve stavovém diagramu.

Nejdůležitější vlastností programu je, že část kódu kroku automatu je jasně lokalizována. S explicitní funkcí krok pro krok automatizace program lépe demonstruje tuto vlastnost:

#zahrnout <ctype.h>#zahrnout <stdio.h>výčet Stát {PŘED, UVNITŘ, PO};prázdnota krok(výčet Stát* konst s, int konst C) {  přepínač (*s) {    případ PŘED:      -li (!isspace(C)) {        putchar(C);        *s = UVNITŘ;      }            přestávka;    případ UVNITŘ:      -li (C == ' n') {        putchar(C);        *s = PŘED;      } jiný -li (isspace(C)) {        *s = PO;      } jiný {        putchar(C);      }              přestávka;    případ PO:      -li (C == ' n') {        putchar(C);        *s = PŘED;      }            přestávka;  }}int hlavní(prázdnota) {  int C;  výčet Stát s = PŘED;  zatímco ((C = getchar()) != EOF) {    krok(&s, C);  }  vrátit se 0;}

Program nyní jasně demonstruje základní vlastnosti kódu založeného na automatech:

• časová období provádění kroků automatu se nemusí překrývat;
• jediná informace předaná z předchozího kroku do dalšího je výslovně uvedena stav automatu.

Konečný automat lze definovat a tabulka přechodu stavu jejichž řádky představují aktuální stavy, sloupce představují vstupy a buňky představují další stavy a akce, které mají být provedeny.

Stavový diagram

The stavový diagram stroje s konečným stavem, který vytiskne první slovo každého řádku vstupního proudu. Stroj sleduje přesně jeden přechod v každém kroku, v závislosti na aktuálním stavu a zjištěném znaku. Akce provázející přechod je buď ne-operace, nebo tisk znaku, se kterým se setkal, označený jako tisk.

Obecně řečeno, program založený na automatech může tento přístup přirozeně použít. S explicitním dvourozměrným polem přechody pro tabulku přechodu stavu program používá tento přístup:

#zahrnout <ctype.h>#zahrnout <stdio.h>výčet Stát {PŘED, UVNITŘ, PO};prázdnota nop(int konst C) {}prázdnota tisk(int konst C) {  putchar(C);}struktur Větev {  výčet Stát konst next_state;  prázdnota (*akce)(int);};struktur Větev konst přechody[3][3] = {  // newline whitespace other Inputs / States  {{PŘED,   &nop}, {PŘED, &nop}, {UVNITŘ, &tisk}},  // před  {{PŘED, &tisk}, {PO,  &nop}, {UVNITŘ, &tisk}},  // uvnitř  {{PŘED, &tisk}, {PO,  &nop}, {PO,    &nop}}   // po};prázdnota krok(výčet Stát* konst s, int konst C) {  int konst řádek = (*s == PŘED) ? 0 : (*s == UVNITŘ) ? 1 : 2;  int konst sloupec = (C == ' n') ? 0 : isspace(C) ? 1 : 2;  struktur Větev konst* konst b = &přechody[řádek][sloupec];  *s = b->next_state;  b->akce(C);}int hlavní(prázdnota) {  int C;  výčet Stát s = PŘED;  zatímco ((C = getchar()) != EOF) {    krok(&s, C);  }  vrátit se 0;}

Objektově orientovaný

Pokud implementační jazyk podporuje objektově orientované programování, jednoduché refaktorování programu je zapouzdřit automat do objektu, čímž skryje podrobnosti jeho implementace. Program v C ++ použití objektově orientovaného stylu může vypadat takto:

#zahrnout <ctype.h>#zahrnout <stdio.h>výčet Stát {PŘED, UVNITŘ, PO};struktur Větev {  výčet Stát konst next_state;  prázdnota (*akce)(int);};třída StateMachine {  veřejnost:    StateMachine();    prázdnota feedChar(int);  chráněný:    statický prázdnota nop(int);    statický prázdnota tisk(int);  soukromé:    výčet Stát _Stát;    statický struktur Větev konst _přechody[3][3];};StateMachine::StateMachine(): _Stát(PŘED) {}prázdnota StateMachine::feedChar(int konst C) {  int konst řádek = (_Stát == PŘED) ? 0 : (_Stát == UVNITŘ) ? 1 : 2;  int konst sloupec = (C == ' n') ? 0 : isspace(C) ? 1 : 2;  struktur Větev konst* konst b = &_přechody[řádek][sloupec];  _Stát = b->next_state;  b->akce(C);}prázdnota StateMachine::nop(int konst C) {}prázdnota StateMachine::tisk(int konst C) {  putchar(C);}struktur Větev konst StateMachine::_přechody[3][3] = {  // newline whitespace other Inputs / States  {{PŘED,   &nop}, {PŘED, &nop}, {UVNITŘ, &tisk}},  // před  {{PŘED, &tisk}, {PO,  &nop}, {UVNITŘ, &tisk}},  // uvnitř  {{PŘED, &tisk}, {PO,  &nop}, {PO,    &nop}}   // po};int hlavní() {  int C;  StateMachine m;  zatímco ((C = getchar()) != EOF) {    m.feedChar(C);  }  vrátit se 0;}

Poznámka. - Aby se minimalizovaly změny, které přímo nesouvisejí s předmětem článku, vstup výstup getchar a putchar funkce ze standardní knihovny C jsou používány.

The státní návrhový vzor je způsob, jak může objekt změnit své chování za běhu podle svého vnitřního stavu aniž byste se uchýlili k velkým podmíněným příkazům nebo vyhledáváním v tabulce díky virtuálním voláním funkcí. Jeho hlavní výhodou oproti kódu používajícím velké podmíněné příkazy je to, že stavově specifický kód je distribuován napříč různými objekty, místo aby byl lokalizován v monolitickém bloku, což zlepšuje údržbu. Jeho hlavní výhody oproti kódu používajícímu tabulky přechodu stavu spočívají v tom, že volání virtuálních funkcí jsou často efektivnější než vyhledávání tabulek, že kritéria přechodu stavu jsou explicitnější než v tabulkovém formátu a že je snazší přidat akce doprovázející přechody stavu. Zavádí však nový problém: počet tříd činí kód méně kompaktní než ostatní přístupy. Program využívající návrhový vzor stavu může vypadat takto:

#zahrnout <ctype.h>#zahrnout <stdio.h>třída StateMachine;třída Stát {  veřejnost:    virtuální prázdnota feedChar(StateMachine*, int) konst = 0;};třída Před: veřejnost Stát {  veřejnost:    statický Stát konst* vytvořit instanci();    virtuální prázdnota feedChar(StateMachine*, int) konst přepsat;  chráněný:    Před() = výchozí;  soukromé:    statický Stát konst* _instance;};třída Uvnitř: veřejnost Stát {  veřejnost:    statický Stát konst* vytvořit instanci();    virtuální prázdnota feedChar(StateMachine*, int) konst přepsat;  chráněný:    Uvnitř() = výchozí;  soukromé:    statický Stát konst* _instance;};třída Po: veřejnost Stát {  veřejnost:    statický Stát konst* vytvořit instanci();    virtuální prázdnota feedChar(StateMachine*, int) konst přepsat;  chráněný:    Po() = výchozí;  soukromé:    statický Stát konst* _instance;};třída StateMachine {  veřejnost:    StateMachine();    prázdnota feedChar(int);  chráněný:    prázdnota setState(Stát konst*);  soukromé:    Stát konst* _Stát;    příteli třída Před;    příteli třída Uvnitř;    příteli třída Po;};Stát konst* Před::vytvořit instanci() {  -li (!_instance) {    _instance = Nový Před;  }  vrátit se _instance;}prázdnota Před::feedChar(StateMachine* konst m, int konst C) konst {  -li (!isspace(C)) {    putchar(C);    m->setState(Uvnitř::vytvořit instanci());  }}Stát konst* Před::_instance = nullptr;Stát konst* Uvnitř::vytvořit instanci() {  -li (!_instance) {    _instance = Nový Uvnitř;  }  vrátit se _instance;}prázdnota Uvnitř::feedChar(StateMachine* konst m, int konst C) konst {  -li (C == ' n') {    putchar(C);    m->setState(Před::vytvořit instanci());  } jiný -li (isspace(C)) {    m->setState(Po::vytvořit instanci());  } jiný {    putchar(C);  }}Stát konst* Uvnitř::_instance = nullptr;Stát konst* Po::vytvořit instanci() {  -li (!_instance) {    _instance = Nový Po;  }  vrátit se _instance;}prázdnota Po::feedChar(StateMachine* konst m, int konst C) konst {  -li (C == ' n') {    putchar(C);    m->setState(Před::vytvořit instanci());  }}Stát konst* Po::_instance = nullptr;StateMachine::StateMachine(): _Stát(Před::vytvořit instanci()) {}prázdnota StateMachine::feedChar(int konst C) {  _Stát->feedChar(tento, C);}prázdnota StateMachine::setState(Stát konst* konst s) {  _Stát = s;}int hlavní() {  int C;  StateMachine m;  zatímco ((C = getchar()) != EOF) {    m.feedChar(C);  }  vrátit se 0;}

Automatizace a automaty

Programování na základě automatů skutečně úzce odpovídá programovacím potřebám v oblasti automatizace.

Výrobní cyklus je běžně modelován jako:

• posloupnost kroků krokujících podle vstupních údajů (od věznitelů);
• soubor akcí prováděných v závislosti na aktuální fázi.

Různé specializované programovací jazyky umožňují vyjádřit takový model víceméně sofistikovaným způsobem.

Automatizační program

Výše uvedený příklad lze vyjádřit podle tohoto pohledu, jako v následujícím pseudo kód ('set' aktivuje logickou proměnnou, 'reset' deaktivuje logickou proměnnou, ':' přiřadí proměnnou a '=' testuje rovnost):

newline: ' n'whitespace: ('  t ','  n ','  v ','  f ','  r ',' ') uvádí: (před, uvnitř, po) setState (c) {if before and (c! = newline and c not in whitespace) then set inside if inside then (if c in whitespace then set after else if c = newline then set before) if after and c = newline then set before} doAction ( c) {if before and (c! = newline and c not in whitespace) then write (c) if inside and c not in whitespace then write (c) if after and c = newline then write (c)} cycle {set before smyčka dokud (c: readCharacter) = EOL {setState (c) doAction (c)}}

Oddělení rutin vyjadřujících průběh cyklu na jedné straně a skutečná akce na druhé straně (odpovídající vstup a výstup) umožňuje jasnější a jednodušší kód.

Události

V oblasti automatizace závisí krok za krokem na vstupních datech pocházejících ze samotného stroje. To je v programu reprezentováno čtením znaků z textu. Ve skutečnosti tato data informují o poloze, rychlosti, teplotě atd. Kritických prvků stroje.

Jako v GUI programování, Změny ve stavu stroje lze tedy považovat za události způsobující přechod ze stavu do druhého, dokud není dosaženo konečné. Kombinace možných stavů může generovat širokou škálu událostí, a tím definovat složitější produkční cyklus. V důsledku toho jsou cykly obvykle zdaleka jednoduché lineární sekvence. Společně běží společně paralelní větve a alternativy vybrané podle různých událostí, které jsou schematicky znázorněny níže:

   s: fáze c: stav s1 | | -c2 | s2 | ---------- | | | -c31 | -c32 | | s31 s32 | | | -c41 | -c42 | | ---------- | s4

Aplikace

Programování na základě automatů je široce používáno v lexikální a syntaktické analýzy.^[1]

Kromě toho uvažování v pojmech automatů (to znamená rozbití procesu provádění na automatické kroky a předávání informací krok za krokem přes explicitní stav automatu) je nutné pro programování řízené událostmi jako jediná alternativa k použití paralelních procesů nebo vláken.

Pojmy stavů a ​​stavových strojů se často používají v oblasti formální specifikace. Například, UML -vývoj využití architektury softwarové architektury stavové diagramy určit chování programu. Také různé komunikační protokoly jsou často specifikovány pomocí explicitního pojmu stát (např. RFC  793 ).

Přemýšlení ve smyslu automatů (kroků a stavů) lze také použít k popisu sémantiky některých programovací jazyky. Například spuštění programu napsaného v souboru Refal jazyk je popsán jako posloupnost kroky takzvaného abstraktního stroje Refal; stav stroje je a Pohled (libovolný výraz Refal bez proměnných).

Pokračování v Systém jazyk vyžaduje přemýšlení z hlediska kroků a stavů, i když samotné schéma v žádném případě nesouvisí s automaty (je rekurzivní). Aby to bylo možné pro call / cc funkce fungovat, implementace musí být schopna zachytit celý stav provádějícího programu, což je možné pouze v případě, že ve stavu není žádná implicitní část. Takový chycený stav se nazývá právě ta věc pokračování, a lze jej považovat za stav (relativně komplikovaného) automatu. Krok automatu odvozuje další pokračování od předchozího a proces provádění je cyklem těchto kroků.

Alexander Ollongren ve své knize^[2] vysvětluje tzv Vídeňská metoda popis sémantiky programovacích jazyků, který je plně založen na formálních automatech.

Systém STAT [1] je dobrým příkladem použití přístupu založeného na automatech; tento systém, kromě dalších funkcí, obsahuje vložený jazyk s názvem STATL který je čistě automatizovaný.

Dějiny

Techniky založené na automatech byly široce používány v doménách, kde existují algoritmy založené na teorii automatů, jako jsou formální jazykové analýzy.^[1]

Jedním z prvních článků o tom je Johnson a kol., 1968.^[3]

Jednu z prvních zmínek o programování na základě automatů jako obecné techniky nalezneme v příspěvku od Peter Naur, 1963.^[4] Autor tuto techniku ​​nazývá Přístup Turingova stroje, nicméně žádný skutečný Turingův stroj je uveden v příspěvku; místo toho je popsána technika založená na krocích a stavech.

Srovnání s imperativním a procedurálním programováním

Pojem Stát není výlučným vlastnictvím programování na základě automatů.^[5]Obecně řečeno, uveďte (nebo stav programu ) se objeví během provádění jakékoli počítačový program, jako kombinace všech informací, které se mohou během provádění změnit. Například stav tradičního rozkazovací způsob program se skládá z

• hodnoty všech proměnných a informace uložené v dynamické paměti;
• hodnoty uložené v registrech;
• obsah zásobníku (včetně hodnot lokálních proměnných a zpáteční adresy);
• aktuální hodnota ukazatele instrukce.

Ty lze rozdělit na explicitní část (například hodnoty uložené v proměnných) a implicitní část (zpáteční adresy a ukazatel instrukce).

Program automatů lze tedy považovat za zvláštní případ imperativního programu, ve kterém je implicitní část stavu minimalizována. Stav celého programu přijatý ve dvou odlišných okamžicích vstupu do krok sekce kódu se může lišit pouze ve stavu automatu. To zjednodušuje analýzu programu.

Vztah objektově orientovaného programování

V teorii objektově orientované programování, an objekt se říká, že má interní Stát a je schopen přijímání zpráv, reagovat jim, odesílání zprávy do jiných objektů a změna jeho vnitřního stavu během zpracování zprávy. V praktičtější terminologii zavolat metodu objektu je považován za stejný jako odeslat zprávu objektu.

Na jedné straně lze tedy objekty z objektově orientovaného programování považovat za automaty (nebo modely automatů), jejichž Stát je kombinace soukromých polí a jedna nebo více metod se považuje za krok. Takové metody nesmí volat sebe navzájem ani sebe, ani přímo, ani nepřímo, jinak nelze objekt považovat za implementovaný způsobem založeným na automatech.

Na druhou stranu je objekt vhodný pro implementaci modelu automatu. Když se v objektově orientovaném jazyce používá přístup založený na automatech, model automatu je obvykle implementován třídou, stav je reprezentován soukromými poli třídy a krok je implementován jako metoda; taková metoda je obvykle jedinou nekonstantní veřejnou metodou třídy (kromě konstruktorů a destruktorů). Jiné veřejné metody by mohly dotazovat stav, ale neměňte to. Všechny sekundární metody (například konkrétní obslužné rutiny stavu) jsou obvykle skryty v soukromé části třídy.

Viz také

• Buněčný automat
• Nedeterministické programování
• Stavový vzor
• Esterel, automatizovaný jazyk
• Dobře, nástroj pro přidání automatů do prostředí Java a C ++

Reference

externí odkazy

• J. V. Noble. «Konečné státní stroje ve Forth» - automatizované programování v Forth
• Harel, David (1987). „Statecharts: A Visual Formalism for Complex Systems“ (PDF). Sci. Comput. Programování. 8 (3): 231–274. doi:10.1016/0167-6423(87)90035-9.
• Harel, David; Drusinsky, D. (1989). Msgstr "Použití stavových diagramů pro popis a syntézu hardwaru". Transakce IEEE na počítačově podporovaném návrhu integrovaných obvodů a systémů. 8 (7): 798–807. doi:10.1109/43.31537. S2CID  8754800.
• Polikarpova N. I., Shalyto A. A. Programování na základě automatů SPb .: Piter. 2009 (rus)
• Univerzita ITMO, oddělení „Programovací technologie“