Az automatikus programozás olyan programozási paradigma , amelynek használatakor egy programot vagy annak töredékét valamilyen formális automata modelljeként értelmezzük . Ismert egy másik "automatikus programozás paradigmája is, amely az összetett viselkedésű entitások ábrázolásából áll automatizált vezérlőobjektumok formájában, amelyek mindegyike egy vezérlőobjektum és egy automata." Ugyanakkor azt javasoljuk, hogy egy programot az automatikus vezérléshez hasonlóan automatizált vezérlőobjektumok rendszereként tekintsünk.
Az automatikus programozásban az adott feladattól függően véges automaták és bonyolultabb felépítésű automaták is használhatók.
A következő jellemzők meghatározóak az automatikus programozásnál:
A teljes automata-stílusú kódvégrehajtás az automata lépéseiből álló ciklus (esetleg implicit).
Az automatikus programozás elnevezést az is indokolja, hogy a gondolkodási stílus (a végrehajtási folyamat észlelése) az ebben a technikában történő programozás során szinte pontosan visszaadja a formális automaták (például Turing -gép , Markov-gép stb. ) összeállításánál alkalmazott gondolkodásmódot. )
Tegyük fel, hogy például egy C programot akarunk írni, amely a szabványos beviteli adatfolyamból olvas be szöveget, amely sorokból áll, és minden sorhoz kiírja ennek a sornak az első szavát és a soremelést. Nyilvánvaló, hogy ehhez az egyes sorok olvasása közben először ki kell hagyni a szóközöket, ha vannak, a sor elején; majd olvassa el a szót alkotó betűket, és addig nyomtassa ki őket, amíg a szó be nem fejeződik (vagyis vagy a sor véget nem ér, vagy egy szóköz karaktert nem talál); végül, ha az első szót sikeresen elolvasta és kinyomtatta, el kell olvasni a sort a végéig anélkül, hogy bármit is nyomtatnánk. Miután találkozott (bármely fázisban) egy újsor karakterrel, nyomtasson új sort, és folytassa az elejétől. Ha (ismét, bármelyik fázisban) a „fájl vége” helyzet következik be, a munkát le kell állítani.
Egy program, amely ezt a problémát a hagyományos felszólító stílusban oldja meg, így nézhet ki ( C nyelv ):
#include <stdio.h> int main () { int c ; do { csináld c = getchar (); while ( c == ' ' ); while ( c != ' ' && c != '\n' && c != EOF ) { putchar ( c ); c = getchar (); } putchar ( '\n' ); while ( c != '\n' && c != EOF ) c = getchar (); } while ( c != EOF ); return 0 ; }Ugyanez a probléma megoldható véges automatákban való gondolkodással. Vegye figyelembe, hogy a karakterlánc elemzése három fázisra oszlik: a vezető szóközök kihagyása, egy szó kinyomtatása és a karakterlánc többi részének kihagyása. Nevezzük ezt a három fázist állapotnak before , insideés after. A program most így nézhet ki:
#include <stdio.h> int main () { enum állapotok { előtte , belül , utána } állapot ; int c ; állapot = előtt ; while (( c = getchar ()) != EOF ) { kapcsoló ( állapot ) { előtti eset : if ( c == '\n' ) { putchar ( '\n' ); } else if ( c != ' ' ) { putchar ( c ); állapot = belül ; } szünet ; tok belül : kapcsoló ( c ) { eset " " : állapot = után ; szünet ; eset '\n' : putchar ( '\n' ); állapot = előtt ; szünet ; alapértelmezett : putchar ( c ); } szünet ; eset után : if ( c == '\n' ) { putchar ( '\n' ); állapot = előtt ; } } } return 0 ; }vagy így:
#include <stdio.h> static void ( * állapot )( int ); statikus üresség előtt ( int c ); statikus üreg belül ( int c ); static void after ( int c ); érvénytelen előtt ( int c ) { if ( c == '\n' ) { putchar ( '\n' ); } else if ( c != ' ' ) { putchar ( c ); állapot = & belül ; } } belül üres ( int c ) { kapcsoló ( c ) { eset " " : állapot = & után ; szünet ; eset '\n' : putchar ( '\n' ); állapot = & előtt ; szünet ; alapértelmezett : putchar ( c ); } } érvénytelen után ( int c ) { if ( c == '\n' ) { putchar ( '\n' ); állapot = & előtt ; } } int main () { int c ; állapot = & előtt ; while (( c = getchar ()) != EOF ) { ( * állapot )( c ); } return 0 ; }Annak ellenére, hogy a kód nyilvánvalóan hosszabb lett, van egy kétségtelen előnye: az olvasás (vagyis egy függvény meghívása getchar()) most pontosan egy helyen történik . Ezenkívül meg kell jegyezni, hogy az előző verzióban használt négy hurok helyett most csak egy hurok használatos. A ciklus törzse (a fejlécben végrehajtott műveletek kivételével) az automata lépése , míg maga a ciklus határozza meg az automata ciklusát .
A program az ábrán látható véges állapotú gép működését valósítja meg (szimulálja). Az N betű a diagramon a sorvégi karaktert, az S betű a szóközt, az A betű pedig az összes többi karaktert jelöli. Az automata egy lépésben pontosan egy átmenetet hajt végre, az aktuális állapottól és a beolvasott karaktertől függően. Néhány átmenetet a beolvasott karakter nyomtatása követ; az ilyen átmeneteket a diagramon csillagok jelölik.
Általánosságban elmondható, hogy nem szükséges szigorúan betartani a kód különálló állapotú kezelőkre való felosztását. Ezenkívül bizonyos esetekben az állapot fogalma több változó értékéből is összeállítható, így szinte lehetetlen lesz figyelembe venni ezek összes lehetséges kombinációját. Ebben a példában sok kódot menthet el, ha észreveszi, hogy a "sorvég" karakteren végrehajtott műveletek állapotfüggetlenek. Az előzővel egyenértékű, de ezzel a megjegyzéssel megírt program így fog kinézni:
#include <stdio.h> int main () { enum állapotok { előtte , belül , utána } állapot ; int c ; állapot = előtt ; while (( c = getchar ()) != EOF ) { if ( c == '\n' ) { putchar ( '\n' ); állapot = előtt ; tovább ; } kapcsoló ( állapot ) { előtti eset : if ( c != ' ' ) { putchar ( c ); állapot = belül ; } szünet ; tok belül : if ( c == ' ' ) állapot = után ; más putchar ( c ); szünet ; eset után : szünet ; } } return 0 ; }A fenti programban továbbra is az automata lépéséért felelős kód egyértelmű kiválasztása. Ezt a körülményt még erősebben hangsúlyozhatjuk, ha az automata lépését külön funkcióra különítjük el.
#include <stdio.h> enum state_t { előtt , belül , után }; static void step ( enum state_t * state , int * c ) { if ( * állapot == előtt ) { if ( * c == '\n' ) putchar ( '\n' ); else if ( * c != ' ' ) * állapot = belül ; } if ( * állapot == belül ) { if ( * c == ' ' ) { * állapot = után ; } else if ( * c == '\n' ) { putchar ( '\n' ); * állapot = előtt ; } másik { putchar ( * c ); } } if ( * állapot == után ) { if ( * c == '\n' ) { putchar ( '\n' ); * állapot = előtt ; } } } int main () { int c ; enum állapot_t állapot = előtt ; while (( c = getchar ()) != EOF ) lépés ( & állapot , & c ); return 0 ; }Ez a példa egyértelműen bemutatja azt a fő tulajdonságot, amely miatt a kód az automatikus programozás stílusában tervezettnek tekinthető:
Egy véges automatát, mint ismeretes, egy ugrótáblázattal is megadhatunk. Általánosságban elmondható, hogy egy véges automatát szimuláló program kódja jól tükrözheti az automatának ezt a tulajdonságát. A következő programban egy tömb the_tabledefiniál egy ugrótáblát. A táblázat sorai az automata három állapotának, az oszlopok olvasható karaktereknek felelnek meg (az első oszlop egy szóköz, a második oszlop egy soremelés, a harmadik oszlop az összes többi karakter). A táblázat minden cellája tartalmazza az új állapot számát és egy karakter kinyomtatásának szükségességének jelét (a fenti kódban a bitmezők memóriatakarékosságra szolgálnak). Természetesen egy valós feladatnál sokkal összetettebb táblaszerkezetre is szükség lehet, amely tartalmazhat például függvénymutatókat az átmenetekkel kapcsolatos műveletek végrehajtásához, de ebben a példában ez nem szükséges:
#include <stdio.h> enum states { előtt = 0 , belső = 1_ _ után = 2 }; typedef struct branch { enum states new_state ; int should_putchar ; } ág ; static const elágazás a_tábla [ 3 ][ 3 ] = { /* ' ' '\n' mások */ /* before */ { { before , 0 }, { before , 1 }, { inside , 1 } }, /* inside */ { { after , 0 }, { before , 1 }, { inside , 1 } }, /* after */ { { after , 0 }, { before , 1 }, { after , 0 } } }; statikus üres lépés ( enum states * state , int c ) { int idx2 = ( c == ' ' ) ? 0 : ( c == '\n' ) ? 1 : 2 ; ág * b = & a_tábla [ * állapot ][ idx2 ]; * állapot = b -> új_állapot ; if ( b -> should_putchar ) putchar ( c ); } int main () { int c ; enum states state = before ; while (( c = getchar ()) != EOF ) lépés ( & állapot , c ); return 0 ; }Ha a használt programozási nyelv támogatja az objektum-orientált szolgáltatásokat , akkor célszerű az állapotgépet egy objektumba foglalni, elrejteni a megvalósítás részleteit. Például egy hasonló C++ program így nézhet ki:
#include <stdio.h> class StateMachine { enum states { előtt = 0 , belső = 1_ _ után = 2 } állapot ; typedef struct { enum states new_state ; unsigned should_putchar ; } ág ; static const elágazás a_tábla [ 3 ][ 3 ]; nyilvános : StateMachine () : állapot ( előtte ) {} void FeedChar ( int c ) { int idx2 = ( c == ' ' ) ? 0 : ( c == '\n' ) ? 1 : 2 ; ág * b = & a_tábla [ állapot ][ idx2 ]; állapot = b -> új_állapot ; if ( b -> should_putchar ) putchar ( c ); } }; const StateMachine :: elágazás ÁllapotGép :: the_table [ 3 ][ 3 ] = { /* ' ' '\n' mások */ /* before */ { { before , 0 }, { before , 1 }, { inside , 1 } }, /* inside */ { { after , 0 }, { before , 1 }, { inside , 1 } }, /* after */ { { after , 0 }, { before , 1 }, { after , 0 } } }; int main () { int c ; StateMachine ; _ while (( c = getchar ()) != EOF ) gép . FeedChar ( c ); return 0 ; }Ezenkívül az állapotgép minden állapota leírható egy osztályként.
#include <stdio.h> osztály állapot { nyilvános : virtuális ~ állapot () {} virtuális void Művelet ( int ch , const Állapot *& next_state ) const = 0 ; }; sablon < classT > _ class TState : védett állapot { statikus állapot * p ; nyilvános : statikus állapot * Get () { ha ( ! p ) p = új T ; return p ; } védett : Tállapot () {} }; class Előtte : public TState < Before > { virtual void Művelet ( int ch , const Állapot *& next_state ) const ; }; class Inside : public TState < Inside > { virtual void Művelet ( int ch , const Állapot *& next_state ) const ; }; class After : public TState < After > { virtual void Művelet ( int ch , const Állapot *& next_state ) const ; }; sablon <> Állapot * TSállapot < Előtte >:: p = 0 ; sablon <> Állapot * TSállapot < Belül >:: p = 0 ; sablon <> Állapot * TSállapot < Utána >:: p = 0 ; void Before::Action ( int ch , const Állapot *& next_state ) const { if ( ch != ' ' && ch != '\n' ) { putchar ( ch ); next_state = belső :: get (); } } void Inside::Action ( int ch , const Állapot *& next_state ) const { if ( ch != ' ' && ch != '\n' ) { putchar ( ch ); } másik { putchar ( '\n' ); next_state = ( ch == '\n' ? Before :: Get () : After :: Get ()); } } void After::Action ( int ch , const Állapot *& next_state ) const { if ( ch == '\n' ) next_state = előtt :: get (); } osztály FiniteStateMachine { const Állam * állam ; nyilvános : FiniteStateMashine () : állapot ( Előtte :: Get ()) {} üres lépés ( int ch ) { állapot -> Művelet ( ch , állapot ); } }; int main () { FiniteStateMachine fsm ; int ch ; while (( ch = getchar ()) != EOF ) fsm . lépés ( ch ); return 0 ; }Vegye figyelembe, hogy ebben a példában a C könyvtárat használtuk az I/O-hoz, hogy elkerüljük a „felesleges” (elterelő) változtatások megjelenését az előző példához képest.
Az automatizált programozást széles körben alkalmazzák lexikális elemzők (klasszikus véges automaták) és elemzők ( push-down memóriával rendelkező automaták ) felépítésében [1] .
Emellett az állapotgépekben való gondolkodás (vagyis a program végrehajtásának gépi lépésekre bontása és az információ átadása lépésről lépésre az állapoton) elengedhetetlen az eseményvezérelt alkalmazások felépítésénél. Ebben az esetben az FSM-stílusú programozás az egyetlen alternatíva több folyamat vagy szál létrehozására .
Gyakran az állapotok és állapotgépek fogalmát használják a programok specifikálására . Tehát, amikor UML -t használó szoftvereket tervezünk , állapotgép diagramokat használunk az objektumok viselkedésének leírására. Ezenkívül a hálózati protokollok leírásánál explicit állapotkiosztást használnak (lásd például RFC 793 [2] ).
Az automatákban (lépésekben és állapotokban) való gondolkodás egyes programozási nyelvek szemantikájának leírásában is alkalmazható. Tehát egy program végrehajtása a Refal nyelven a Refal gép látómezejében bekövetkezett változások sorozata, vagy más szóval a Refal gép lépéseinek sorozata, amelynek állapota a mező tartalma. nézet (egy tetszőleges Refal kifejezés, amely nem tartalmaz változókat).
A Scheme folytatási mechanizmusa is megköveteli az állapotokban és a megvalósítás lépéseiben való gondolkodást, bár maga a Scheme semmiképpen sem automata. Ahhoz azonban, hogy a folytatást „lefagyhassuk” , a Scheme nyelv számítási modelljének implementálásakor össze kell vonni a futási környezet összes összetevőjét, beleértve azon műveletek listáját is, amelyeket még végre kell hajtani a program befejezéséhez. számítás , egyetlen egységbe, amelyet általában folytatásnak is neveznek . Az ilyen folytatás az automata állapotának bizonyul, és a program végrehajtási folyamata olyan lépésekből áll, amelyek mindegyike a következő folytatási értéket származtatja az előzőből .
Alexander Ollongren könyvében [3] leírja az úgynevezett bécsi módszert a programozási nyelvek szemantikájának leírására, amely teljes egészében formális automatákon alapul.
Az automata paradigma alkalmazásának egyik példája a STAT rendszer [1] ; ez a rendszer különösen magában foglalja a beépített STATL nyelvet, amely tisztán automatikus szemantikával rendelkezik.
Javaslatok vannak arra is, hogy az automatikus programozást mint univerzális megközelítést alkalmazzák a számítógépes programok létrehozásához, szakterülettől függetlenül. Így a cikk szerzői [4] azzal érvelnek, hogy az automatikus programozás betöltheti a legendás ezüstgolyó szerepét .
Úgy tűnik, hogy az automata-programozási paradigma alkalmazásának legkorábbi esetei olyan tématerületekhez kapcsolódnak, amelyekben az automata elméleten alapuló algoritmikus elméletet dolgoztak ki , és mindenekelőtt a formális nyelvek szövegeinek elemzéséhez. [1] Az egyik legkorábbi munka ebben a témában a cikk. [5]
Az egyik első utalás az automata programozási technikák használatára, függetlenül a véges állapotú gépeken alapuló elméleti fejlesztésektől, Peter Naur cikke . [6] Ebben a cikkben a szerző az alkalmazott megközelítést "Turing-gép megközelítés"-nek ( Turing-gép megközelítésnek ) nevezi, de valójában a cikkben nem épül fel Turing-gép ; a cikkben megadott megközelítés megfelel az automatikus programozás fenti definíciójának .
A programállapot fogalma nem kizárólagos jellemzője az automatikus programozásnak. Általánosságban elmondható, hogy egy állapot bármely számítógépes program végrehajtása során fellép, és minden olyan információ gyűjteménye, amely a végrehajtás során megváltozhat. Így a hagyományos felszólító stílusban végrehajtott program állapota abból áll
Az állapot összetevői feloszthatók explicitre (például változó értékek) és implicitekre (visszatérési címek és programszámláló értéke).
A bevezetett definíciókkal összefüggésben a véges automata modellként megtervezett program egy imperatív program speciális esetének tekinthető, amelynél az implicit állapotkomponens szerepe minimális. Ha az automata programot az automata következő lépésének kezdetének pillanataiban vesszük figyelembe, akkor a program állapotai ezekben a pillanatokban csak az explicit komponensben térnek el. Ez a körülmény nagyban leegyszerűsíti a programtulajdonságok elemzését.
Az objektum-orientált programozás elmélete szerint az objektumnak belső állapota van , és képes üzeneteket fogadni , válaszolni rájuk, üzeneteket küldeni más objektumoknak, és megváltoztatni belső állapotát az üzenetek feldolgozása során. Gyakorlatiasabb, hogy az objektum metódusának meghívása az objektumnak küldött üzenet szinonimájának tekinthető .
Így egyrészt az objektum-orientált programozásban az objektumok véges automatáknak (vagy, ha úgy tetszik, véges automaták modelljeinek) tekinthetők, amelyek állapota belső mezők halmaza, míg egy vagy több metódus Az objektum akkor tekinthető az automata lépésének, ha ezek a metódusok sem közvetlenül, sem közvetve nem hívják magukat vagy egymást.
Másrészt nyilvánvaló, hogy az objektum fogalma jó eszköz a véges automata modell megvalósításához. Az automata programozási paradigma objektumorientált nyelvekben történő alkalmazásakor az automata modelleket általában osztályokként ábrázolják, az automata állapotát az osztály belső (privát) mezői írják le, az automata lépéskódját pedig osztálymetódusként formázzák, ill. Ez a módszer valószínűleg az egyetlen nyilvános módszer (a konstruktorokat és a destruktorokat nem számítva), amely megváltoztatja az automata állapotát. Más nyilvános módszerek is szolgálhatnak információszerzésre az automata állapotáról, de nem változtatják meg. Ilyen esetekben minden segédmetódus (például az egyes állapotok vagy kategóriáik kezelői) általában az osztály privát részébe kerül.
Az SFC-ben a programot átmenetekkel összekapcsolt lépések sematikus sorozataként írják le.