Programarea automată este o paradigmă de programare , când se utilizează un program sau fragmentul său ca model al unui automat formal . Se mai cunoaște un alt „paradigma de programare automată, care constă în reprezentarea entităților cu comportament complex sub forma unor obiecte de control automatizate, fiecare dintre acestea fiind un obiect de control și un automat”. În același timp, se propune să ne gândim la un program, ca în controlul automat, ca la un sistem de obiecte de control automat.
În funcție de sarcina specifică în programarea automată, pot fi utilizate atât automate finite , cât și automate cu o structură mai complexă.
Următoarele caracteristici sunt decisive pentru programarea automată:
Execuția completă a codului în stil automat este o buclă (posibil implicită) de pași automati.
Denumirea de programare automată este justificată și de faptul că stilul de gândire (percepția procesului de execuție) la programarea în această tehnică reproduce aproape exact stilul de gândire la compilarea automatelor formale (cum ar fi o mașină Turing , o mașină Markov etc. )
Să presupunem, de exemplu, că doriți să scrieți un program C care citește text din fluxul de intrare standard, format din linii, și pentru fiecare linie tipărește primul cuvânt din această linie și avansul de linie. Este clar că pentru aceasta, în timp ce citiți fiecare rând, trebuie mai întâi să săriți peste spațiile, dacă există, de la începutul rândului; apoi citiți literele care alcătuiesc cuvântul și tipăriți-le până când cuvântul se termină (adică se termină linia sau se întâlnește un caracter alb); în sfârșit, când primul cuvânt a fost citit și tipărit cu succes, este necesar să citiți linia până la sfârșit fără a imprima nimic. După ce ați întâlnit (în orice fază) un caracter de linie nouă, ar trebui să imprimați o linie nouă și să continuați de la început. Dacă (din nou, în orice fază) apare situația „sfârșitul fișierului”, lucrul ar trebui oprit.
Un program care rezolvă această problemă în stilul imperativ tradițional ar putea arăta astfel ( limbaj C ):
#include <stdio.h> int main () { int c ; face { do c = getchar (); în timp ce ( c == ' ' ); în timp ce ( c != ' ' && c != '\n' && c != EOF ) { putchar ( c ); c = getchar (); } putchar ( '\n' ); în timp ce ( c != '\n' && c != EOF ) c = getchar (); } în timp ce ( c != EOF ); returnează 0 ; }Aceeași problemă poate fi rezolvată gândind în termeni de automate finite. Rețineți că analizarea unui șir este împărțită în trei faze: săriți peste spațiile de început, imprimare a unui cuvânt și săriți peste restul șirului. Să numim aceste trei faze stări before , insideși after. Programul ar putea arăta acum astfel:
#include <stdio.h> int main () { enum state { înainte , în interior , după } stare ; int c ; stare = înainte ; în timp ce (( c = getchar ()) != EOF ) { comutator ( stare ) { caz inainte : dacă ( c == '\n' ) { putchar ( '\n' ); } else if ( c != ' ' ) { putchar ( c ); stare = interior ; } rupe ; carcasa in interior : comutator ( c ) { cazul ' ' : stare = după ; rupe ; cazul „\n” : putchar ( '\n' ); stare = înainte ; rupe ; implicit : putchar ( c ); } rupe ; caz dupa : dacă ( c == '\n' ) { putchar ( '\n' ); stare = înainte ; } } } returnează 0 ; }sau cam asa:
#include <stdio.h> static void ( * stare )( int ); static void înainte ( int c ); gol static interior ( int c ); gol static după ( int c ); void înainte ( int c ) { dacă ( c == '\n' ) { putchar ( '\n' ); } else if ( c != ' ' ) { putchar ( c ); stare = & interior ; } } void interior ( int c ) { comutator ( c ) { cazul ' ' : stare = & după ; rupe ; cazul „\n” : putchar ( '\n' ); stare = & înainte de ; rupe ; implicit : putchar ( c ); } } nulă după ( int c ) { dacă ( c == '\n' ) { putchar ( '\n' ); stare = & înainte de ; } } int main () { int c ; stare = & înainte de ; în timp ce (( c = getchar ()) != EOF ) { ( * stare )( c ); } returnează 0 ; }În ciuda faptului că codul a devenit în mod evident mai lung, acesta are un avantaj incontestabil: citirea (adică apelarea unei funcții getchar()) este acum efectuată exact într-un singur loc . În plus, trebuie remarcat faptul că în locul celor patru bucle utilizate în versiunea anterioară, acum este folosită o singură buclă. Corpul ciclului (cu excepția acțiunilor efectuate în antet) este o etapă a automatului , în timp ce ciclul în sine stabilește ciclul automatului .
Programul implementează (simulează) funcționarea mașinii cu stări finite prezentată în figură. Litera N din diagramă denotă caracterul de sfârșit de linie, litera S desemnează caracterul spațiu, iar litera A denotă toate celelalte caractere. Într-un singur pas, automatul face exact o tranziție, în funcție de starea curentă și de caracterul citit. Unele tranziții sunt urmate de o imprimare a caracterului citit; astfel de tranziții sunt marcate cu asteriscuri în diagramă.
În general, nu este necesar să se respecte cu strictețe împărțirea codului în manipulatori ai statelor separate. Mai mult, în unele cazuri, însuși conceptul de stare poate fi alcătuit din valorile mai multor variabile, astfel încât va fi aproape imposibil să se ia în considerare toate combinațiile posibile ale acestora. În acest exemplu, puteți salva o mulțime de cod dacă observați că acțiunile efectuate pe caracterul „sfârșit de linie” sunt independente de stare. Un program echivalent cu cel anterior, dar scris cu această remarcă în minte, va arăta astfel:
#include <stdio.h> int main () { enum state { înainte , în interior , după } stare ; int c ; stare = înainte ; în timp ce (( c = getchar ()) != EOF ) { dacă ( c == '\n' ) { putchar ( '\n' ); stare = înainte ; continua ; } comutator ( stare ) { caz inainte : dacă ( c != ' ' ) { putchar ( c ); stare = interior ; } rupe ; carcasa in interior : dacă ( c == ' ' ) stare = după ; altfel putchar ( c ); rupe ; caz dupa : rupe ; } } returnează 0 ; }Fundamental în programul de mai sus este încă o selecție clară a codului responsabil pentru pasul automatului. Această împrejurare poate fi subliniată și mai puternic dacă pasul automatului este separat într-o funcție separată.
#include <stdio.h> enum state_t { înainte , în interior , după }; pas static void ( enum state_t * state , int * c ) { dacă ( * stare == înainte ) { dacă ( * c == '\n' ) putchar ( '\n' ); else if ( * c != ' ' ) * stare = interior ; } if ( * stare == interior ) { dacă ( * c == ' ' ) { * stare = după ; } else if ( * c == '\n' ) { putchar ( '\n' ); * stare = înainte ; } altfel { putchar ( * c ); } } dacă ( * stare == după ) { dacă ( * c == '\n' ) { putchar ( '\n' ); * stare = înainte ; } } } int main () { int c ; enumerare state_t stare = înainte ; în timp ce (( c = getchar ()) != EOF ) pas ( & stare , & c ); returnează 0 ; }Acest exemplu demonstrează în mod clar proprietatea principală datorită căreia codul poate fi considerat a fi proiectat în stilul programării automate:
Un automat finit, după cum se știe, poate fi specificat și printr-un tabel de salt. În general, codul unui program care simulează un automat finit poate reflecta foarte bine această proprietate a automatului. În programul următor, o matrice the_tabledefinește un tabel de salt. Rândurile tabelului corespund celor trei stări ale automatului, coloanele corespund caracterelor care pot fi citite (prima coloană este un spațiu, a doua coloană este un avans de linie, a treia coloană este toate celelalte caractere). Fiecare celulă a tabelului conține numărul noii stări și un semn al necesității de a tipări un caracter (în codul de mai sus, câmpurile de biți sunt folosite pentru a economisi memorie). Desigur, într-o sarcină reală, ar putea fi necesară o structură de tabel mult mai complexă, care să conțină, de exemplu, pointeri către funcții pentru a efectua orice acțiuni legate de tranziții, dar acest lucru nu este necesar în acest exemplu:
#include <stdio.h> enum state { înainte de = 0 , interior = 1 _ după = 2 }; typedef struct branch { enum state new_state ; int ar trebui să_putchar ; } ramură ; static const branch the_table [ 3 ][ 3 ] = { /* ' ' '\n' altele */ /* înainte de */ { { înainte de , 0 }, { înainte de , 1 }, { în interior , 1 } }, /* în interiorul */ { { după , 0 }, { înainte , 1 }, { în interior , 1 } }, /* după */ { { după , 0 }, { înainte de , 1 }, { după , 0 } } }; pas static void ( enum state * state , int c ) { int idx2 = ( c == ' ' ) ? 0 : ( c == '\n' ) ? 1 : 2 ; ramură * b = & the_table [ * stare ][ idx2 ]; * stare = b -> stare_noua ; if ( b -> should_putchar ) putchar ( c ); } int main () { int c ; enum states state = înainte ; în timp ce (( c = getchar ()) != EOF ) pas ( & stare , c ); returnează 0 ; }Dacă limbajul de programare utilizat acceptă caracteristici orientate pe obiecte , este logic să încapsulăm mașina de stări într-un obiect, ascunzând detaliile implementării. De exemplu, un program C++ similar ar putea arăta astfel:
#include <stdio.h> clasa StateMachine { enum state { înainte de = 0 , interior = 1 _ după = 2 } stare ; typedef struct { enum state new_state ; unsigned should_putchar ; } ramură ; static const branch the_table [ 3 ][ 3 ]; public : StateMachine () : stare ( înainte de ) {} void FeedChar ( int c ) { int idx2 = ( c == ' ' ) ? 0 : ( c == '\n' ) ? 1 : 2 ; ramură * b = & the_table [ stare ][ idx2 ]; stare = b -> stare_noua ; if ( b -> should_putchar ) putchar ( c ); } }; const StateMachine :: branch StateMachine :: the_table [ 3 ][ 3 ] = { /* ' ' '\n' altele */ /* înainte de */ { { înainte de , 0 }, { înainte de , 1 }, { în interior , 1 } }, /* în interiorul */ { { după , 0 }, { înainte , 1 }, { în interior , 1 } }, /* după */ { { după , 0 }, { înainte de , 1 }, { după , 0 } } }; int main () { int c ; StateMachine ; _ în timp ce (( c = getchar ()) != EOF ) masina . FeedChar ( c ); returnează 0 ; }De asemenea, fiecare stare a mașinii de stări poate fi descrisă ca o clasă.
#include <stdio.h> clasa de stat { public : virtual ~ stare () {} virtual void Action ( int ch , const State *& next_state ) const = 0 ; }; șablon < classT > _ clasa TState : stat protejat { Stare static * p ; public : Stare static * Obține () { dacă ( ! p ) p = T nou ; întoarcere p ; } protejat : TState () {} }; clasă Înainte : public TState < Înainte > { virtual void Action ( int ch , const State *& next_state ) const ; }; class Inside : public TState < Inside > { virtual void Action ( int ch , const State *& next_state ) const ; }; clasă După : public TState < După > { virtual void Action ( int ch , const State *& next_state ) const ; }; template <> State * TState < Înainte de >:: p = 0 ; template <> State * TState < Inside >:: p = 0 ; template <> State * TState < After >:: p = 0 ; void Înainte de::Acțiune ( int ch , const State *& next_state ) const { dacă ( ch != ' ' && ch != '\n' ) { putchar ( ch ); următoarea_stare = în interior :: get (); } } void Inside::Action ( int ch , const State *& next_state ) const { dacă ( ch != ' ' && ch != '\n' ) { putchar ( ch ); } altfel { putchar ( '\n' ); next_state = ( ch == '\n' ? Înainte :: Obține () : După :: Obține ()); } } void After::Action ( int ch , const State *& next_state ) const { dacă ( ch == '\n' ) următoarea_stare = înainte de :: obține (); } clasa FiniteStateMachine { const Stat * stat ; public : FiniteStateMashine () : stare ( Înainte de :: Obține ()) {} void Step ( int ch ) { stare -> Acțiune ( ch , stare ); } }; int main () { FiniteStateMachine fsm ; int ch ; în timp ce (( ch = getchar ()) != EOF ) fsm . pas ( ch ); returnează 0 ; }Rețineți că în acest exemplu, am folosit biblioteca C pentru I/O pentru a evita apariția unor modificări „inutile” (distractive) în comparație cu exemplul anterior.
Programarea automată este utilizată pe scară largă în construcția analizoarelor lexicale (automate finite clasice) și a parserelor ( automate cu memorie push-down ) [1] .
În plus, gândirea în termeni de mașini de stare (adică defalcarea execuției unui program în pași de mașină și trecerea informațiilor de la pas la pas prin stare) este esențială atunci când construim aplicații bazate pe evenimente . În acest caz, programarea în stil FSM este singura alternativă la generarea mai multor procese sau fire .
Adesea noţiunea de stări şi maşini de stări este folosită pentru specificarea programelor . Deci, atunci când proiectați software folosind UML , diagramele mașinilor de stare sunt folosite pentru a descrie comportamentul obiectelor. În plus, alocarea explicită a stării este utilizată în descrierea protocoalelor de rețea (vezi, de exemplu, RFC 793 [2] ).
Gândirea în termeni de automate (pași și stări) își găsește aplicație și în descrierea semanticii unor limbaje de programare. Astfel, executarea unui program în limbajul Refal este o succesiune de modificări în câmpul vizual al mașinii Refal sau, cu alte cuvinte, o succesiune de pași a mașinii Refal, a cărei stare este conținutul câmpului. de vedere (o expresie Refal arbitrară care nu conține variabile).
Mecanismul de continuare a Schemei necesită, de asemenea, gândirea în termeni de stări și pași pentru a-l implementa, chiar dacă Scheme în sine nu este în niciun caz un automat. Totuși, pentru a putea „îngheța” continuarea , este necesar, la implementarea modelului de calcul al limbajului Scheme, să se combine toate componentele runtime-ului, inclusiv lista acțiunilor care rămân de efectuat pentru a finaliza calcul , într-o singură unitate, care este, de asemenea, numită o continuare . O astfel de continuare se dovedește a fi o stare a automatului, iar procesul de execuție a programului constă din pași, fiecare dintre care derivă următoarea valoare de continuare din cea anterioară.
Alexander Ollongren în cartea sa [3] descrie așa-numita metodă de la Viena pentru descrierea semanticii limbajelor de programare, bazată în întregime pe automate formale.
Un exemplu de aplicare a paradigmei automate este sistemul STAT [1] ; acest sistem, în special, include limbajul STATL încorporat, care are o semantică pur automată.
Există, de asemenea, propuneri de utilizare a programării automate ca abordare universală a creării de programe pentru calculator, indiferent de domeniul de studiu. Astfel, autorii articolului [4] susțin că programarea automată poate juca rolul legendarului glonț de argint .
Cele mai timpurii cazuri de aplicare a paradigmei de programare a automatelor par să se refere la domeniile în care a fost dezvoltată o teorie algoritmică bazată pe teoria automatelor , și mai ales la analiza textelor în limbaje formale. [1] Una dintre cele mai vechi lucrări pe această temă este articolul. [5]
Una dintre primele referiri la utilizarea tehnicilor de programare a automatelor, indiferent de evoluțiile teoretice bazate pe mașini cu stări finite, este un articol de Peter Naur . [6] În acest articol, autorul numește abordarea aplicată „Abordarea mașinii Turing” ( abordarea mașinii Turing ), dar de fapt nicio mașină Turing nu este construită în articol; abordarea dată în articol satisface definiţia de mai sus a programării automate .
Conceptul de stare a programului nu este o caracteristică exclusivă a programării automate. În general, o stare apare în timpul execuției oricărui program de calculator și este o colecție a tuturor informațiilor care se pot schimba în timpul execuției. Astfel, starea unui program executat în stilul imperativ tradițional constă în
Componentele stării pot fi împărțite în explicite (cum ar fi valorile variabilelor) și implicite (adresele de retur și valoarea contorului programului).
În contextul definițiilor introduse, un program conceput ca model de automat finit poate fi considerat un caz special de program imperativ, unul în care rolul componentei implicite de stare este minimizat. Dacă luăm în considerare programul automat în momentele de la începutul următorului pas al automatului, atunci stările programului în aceste momente vor diferi doar în componenta explicită. Această circumstanță simplifică foarte mult analiza proprietăților programului.
În teoria programării orientate pe obiecte , se crede că un obiect are o stare internă și este capabil să primească mesaje , să răspundă la ele, să trimită mesaje către alte obiecte și să-și schimbe starea internă în procesul de procesare a mesajelor. Mai practic, notiunea de a apela metoda unui obiect este considerata sinonima cu notiunea de a trimite un mesaj catre un obiect .
Astfel, pe de o parte, obiectele din programarea orientată pe obiecte pot fi considerate automate finite (sau, dacă doriți, modele de automate finite), a căror stare este o colecție de câmpuri interne, în timp ce una sau mai multe metode ale obiectul poate fi considerat ca o etapă a automatului atunci când aceste metode nu se numesc pe sine sau între ele fie direct, fie indirect.
Pe de altă parte, este evident că conceptul de obiect este un instrument bun pentru implementarea modelului de automat finit. Atunci când se aplică paradigma de programare a automatelor în limbaje orientate pe obiecte, modelele de automate sunt de obicei reprezentate ca clase, starea automatului este descrisă de câmpurile interne (private) ale clasei, iar codul de pas al automatului este formatat ca metodă de clasă și această metodă este cel mai probabil singura metodă publică (fără a număra constructorii și destructorii) care schimbă starea automatului. Alte metode publice pot servi pentru a obține informații despre starea automatului, dar nu o modifică. Toate metodele auxiliare (de exemplu, manipulatorii statelor individuale sau categoriile acestora) în astfel de cazuri sunt de obicei eliminate în partea privată a clasei.
În SFC, un program este descris ca o secvență schematică de pași conectați prin tranziții.