Automatisk programmering är ett programmeringsparadigm , när man använder vilket ett program eller dess fragment uppfattas som en modell av någon formell automat . Ett annat "paradigm för automatisk programmering är också känt, vilket består i att representera enheter med komplext beteende i form av automatiserade kontrollobjekt, som var och en är ett kontrollobjekt och en automat." Samtidigt föreslås att man tänker på ett program, som vid automatisk styrning, som ett system med automatiserade styrobjekt.
Beroende på den specifika uppgiften inom automatisk programmering kan både finita automater och automater med en mer komplex struktur användas.
Följande egenskaper är avgörande för automatisk programmering:
Helautomatisk kodexekvering är en loop (möjligen implicit) av automatsteg.
Namnet automatisk programmering motiveras också av att tankestilen (uppfattningen av exekveringsprocessen) vid programmering i denna teknik nästan exakt återger tankestilen vid sammanställning av formella automater (som en Turingmaskin , Markovmaskin , etc. ). )
Anta att du till exempel vill skriva ett C- program som läser text från standardinmatningsströmmen, bestående av rader, och för varje rad skriver ut det första ordet i denna rad och radmatningen. Det är tydligt att för detta, när du läser varje rad, måste du först hoppa över mellanslag, om några, i början av raden; läs sedan bokstäverna som utgör ordet och skriv ut dem tills ordet slutar (det vill säga antingen raden slutar eller ett blanksteg påträffas); slutligen, när det första ordet har lästs och skrivits ut, är det nödvändigt att läsa raden till slutet utan att skriva ut någonting. Efter att ha träffat (i något skede) ett nyradstecken bör du skriva ut en nyrad och fortsätta från början. Om (igen, i något skede) situationen "filslut" inträffar, bör arbetet avbrytas.
Ett program som löser detta problem i traditionell imperativstil kan se ut så här ( C-språk ):
#include <stdio.h> int main () { int c ; gör { do c = getchar (); while ( c == ' ' ); while ( c != ' ' && c != '\n' && c != EOF ) { putchar ( c ); c = getchar (); } putchar ( '\n' ); medan ( c != '\n' && c != EOF ) c = getchar (); } while ( c != EOF ); returnera 0 ; }Samma problem kan lösas genom att tänka i termer av finita automater. Observera att analys av en sträng är uppdelad i tre faser: hoppa över inledande mellanslag, skriva ut ett ord och hoppa över resten av strängen. Låt oss kalla dessa tre faser tillstånd before , insideoch after. Programmet kan nu se ut så här:
#include <stdio.h> int main () { enum tillstånd { före , inuti , efter } tillstånd ; int c ; state = före ; while (( c = getchar ()) != EOF ) { switch ( tillstånd ) { fall innan : if ( c == '\n' ) { putchar ( '\n' ); } annat om ( c != ' ' ) { putchar ( c ); state = inuti ; } bryta ; fodral inuti : switch ( c ) { fall '' : state = efter ; bryta ; fall '\n' : putchar ( '\n' ); state = före ; bryta ; standard : putchar ( c ); } bryta ; fall efter : if ( c == '\n' ) { putchar ( '\n' ); state = före ; } } } returnera 0 ; }eller så här:
#include <stdio.h> statiskt tomrum ( * state )( int ); statiskt tomrum före ( int c ); statiskt tomrum inuti ( int c ); statiskt tomrum efter ( int c ); void före ( int c ) { if ( c == '\n' ) { putchar ( '\n' ); } annat om ( c != ' ' ) { putchar ( c ); state = & inuti ; } } tomrum inuti ( int c ) { switch ( c ) { fall '' : state = & efter ; bryta ; fall '\n' : putchar ( '\n' ); state = & före ; bryta ; standard : putchar ( c ); } } void efter ( int c ) { if ( c == '\n' ) { putchar ( '\n' ); state = & före ; } } int main () { int c ; state = & före ; while (( c = getchar ()) != EOF ) { ( * tillstånd )( c ); } returnera 0 ; }Trots att koden uppenbarligen har blivit längre har den en obestridlig fördel: läsning (det vill säga anropa en funktion getchar()) utförs nu på exakt ett ställe . Dessutom bör det noteras att istället för de fyra slingorna som användes i den tidigare versionen, används nu bara en slinga. Cykelns kropp (med undantag för de åtgärder som utförs i rubriken) är ett steg i automaten , medan cykeln själv ställer in automatens cykel .
Programmet implementerar (simulerar) driften av den finita tillståndsmaskinen som visas i figuren. Bokstaven N i diagrammet betecknar radsluttecknet, bokstaven S betecknar mellanslagstecknet och bokstaven A betecknar alla andra tecken. I ett steg gör automaten exakt en övergång, beroende på det aktuella tillståndet och det avlästa tecknet. Vissa övergångar följs av en utskrift av det lästa tecknet; sådana övergångar är markerade med asterisker i diagrammet.
Generellt sett är det inte nödvändigt att strikt följa uppdelningen av kod i hanterare i separata stater. Dessutom, i vissa fall, kan själva begreppet tillstånd bestå av värdena för flera variabler, så att det blir nästan omöjligt att ta hänsyn till alla möjliga kombinationer av dem. I det här exemplet kan du spara mycket kod om du märker att de åtgärder som utförs på "radens slut"-tecknet är tillståndsoberoende. Ett program motsvarande det föregående, men skrivet med denna kommentar i åtanke, kommer att se ut så här:
#include <stdio.h> int main () { enum tillstånd { före , inuti , efter } tillstånd ; int c ; state = före ; while (( c = getchar ()) != EOF ) { if ( c == '\n' ) { putchar ( '\n' ); state = före ; fortsätta ; } switch ( tillstånd ) { fall innan : if ( c != '' ) { putchar ( c ); state = inuti ; } bryta ; fodral inuti : if ( c == ' ' ) state = efter ; annan putchar ( c ); bryta ; fall efter : bryta ; } } returnera 0 ; }Grundläggande i programmet ovan är fortfarande ett tydligt urval av koden som ansvarar för automatens steg. Denna omständighet kan framhållas ännu starkare om automatens steg separeras i en separat funktion.
#include <stdio.h> enum state_t { före , inuti , efter }; statiskt void steg ( enum state_t * state , int * c ) { if ( * state == före ) { if ( * c == '\n' ) putchar ( '\n' ); annat om ( * c != ' ' ) * state = inuti ; } if ( * state == inuti ) { if ( * c == ' ' ) { * state = efter ; } annat om ( * c == '\n' ) { putchar ( '\n' ); * state = före ; } annat { putchar ( * c ); } } if ( * state == efter ) { if ( * c == '\n' ) { putchar ( '\n' ); * state = före ; } } } int main () { int c ; enum state_t state = före ; while (( c = getchar ()) != EOF ) steg ( & tillstånd , & c ); returnera 0 ; }Detta exempel visar tydligt huvudegenskapen på grund av vilken koden kan anses vara utformad i stil med automatisk programmering:
En finit automat, som är känt, kan också specificeras av en hopptabell. Generellt sett kan koden för ett program som simulerar en finit automat mycket väl återspegla denna egenskap hos automaten. I följande program the_tabledefinierar en array en hopptabell. Raderna i tabellen motsvarar automatens tre tillstånd, kolumnerna motsvarar läsbara tecken (den första kolumnen är ett mellanslag, den andra kolumnen är en radmatning, den tredje kolumnen är alla andra tecken). Varje cell i tabellen innehåller numret på det nya tillståndet och ett tecken på behovet av att skriva ut ett tecken (i ovanstående kod används bitfält för att spara minne). Naturligtvis, i en verklig uppgift, kan en mycket mer komplex tabellstruktur krävas, innehållande till exempel pekare till funktioner för att utföra åtgärder relaterade till övergångar, men detta är inte nödvändigt i detta exempel:
#include <stdio.h> enum stater { före = 0 , inuti = 1 _ efter = 2 }; typedef struct branch { enum tillstånd new_state ; int should_putchar ; } gren ; statisk konstgren the_table [ 3 ] [ 3 ] = { /* ' ' '\n' andra */ /* före */ { { före , 0 }, { före , 1 }, { inuti , 1 } }, /* inside */ { { after , 0 }, { before , 1 }, { inside , 1 } }, /* efter */ { { efter , 0 }, { före , 1 }, { efter , 0 } } }; statiskt void steg ( enum states * state , int c ) { int idx2 = ( c == ' ' ) ? 0 : ( c == '\n' ) ? 1 : 2 ; branch * b = & the_table [ * state ][ idx2 ]; * state = b -> new_state ; if ( b -> should_putchar ) putchar ( c ); } int main () { int c ; enum tillstånd tillstånd = före ; while (( c = getchar ()) != EOF ) steg ( & tillstånd , c ); returnera 0 ; }Om programmeringsspråket som används stöder objektorienterade funktioner är det vettigt att kapsla in tillståndsmaskinen i ett objekt och dölja implementeringsdetaljerna. Till exempel kan ett liknande C++- program se ut så här:
#include <stdio.h> klass StateMachine { enum stater { före = 0 , inuti = 1 _ efter = 2 } tillstånd ; typedef struct { enum tillstånd new_state ; osignerad should_putchar ; } gren ; static const branch the_table [ 3 ][ 3 ]; offentliga : StateMachine () : state ( före ) {} void FeedChar ( int c ) { int idx2 = ( c == ' ' ) ? 0 : ( c == '\n' ) ? 1 : 2 ; branch * b = & the_table [ state ][ idx2 ]; tillstånd = b -> nytt_tillstånd ; if ( b -> should_putchar ) putchar ( c ); } }; const StateMachine :: branch StateMachine :: the_table [ 3 ][ 3 ] = { /* ' ' '\n' andra */ /* före */ { { före , 0 }, { före , 1 }, { inuti , 1 } }, /* inside */ { { after , 0 }, { before , 1 }, { inside , 1 } }, /* efter */ { { efter , 0 }, { före , 1 }, { efter , 0 } } }; int main () { int c ; StateMachine ; _ while (( c = getchar ()) != EOF ) maskin . FeedChar ( c ); returnera 0 ; }Dessutom kan varje tillstånd hos tillståndsmaskinen beskrivas som en klass.
#include <stdio.h> klass State { offentliga : virtuell ~ State () {} virtuell void Action ( int ch , const State *& next_state ) const = 0 ; }; mall < classT > _ klass TState : skyddad stat { statiskt tillstånd * p ; offentliga : statiskt tillstånd * Get () { om ( ! p ) p = nytt T ; returnera p ; } skyddad : TState () {} }; klass Före : offentlig TState < Före > { virtuell void Action ( int ch , const State *& next_state ) const ; }; class Inside : public TState < Inside > { virtuell void Action ( int ch , const State *& next_state ) const ; }; klass Efter : offentlig TState < Efter > { virtuell void Action ( int ch , const State *& next_state ) const ; }; mall <> Tillstånd * TState < Före >:: p = 0 ; mall <> State * TState < Inside >:: p = 0 ; mall <> Tillstånd * TState < Efter >:: p = 0 ; void Before::Action ( int ch , const State *& next_state ) const { if ( ch != ' ' && ch != '\n' ) { putchar ( ch ); nästa_tillstånd = inuti :: get (); } } void Inside::Action ( int ch , const State *& next_state ) const { if ( ch != ' ' && ch != '\n' ) { putchar ( ch ); } annat { putchar ( '\n' ); next_state = ( ch == '\n' ? Före :: Get () : Efter :: Get ()); } } void Efter::Action ( int ch , const State *& next_state ) const { if ( ch == '\n' ) nästa_tillstånd = före :: get (); } klass FiniteStateMachine { const State * state ; offentliga : FiniteStateMashine () : state ( Före :: Get ()) {} void Steg ( int ch ) { state -> Action ( ch , state ); } }; int main () { FiniteStateMachine fsm ; int ch ; medan (( ch = getchar ()) != EOF ) fsm . steg ( ch ); returnera 0 ; }Observera att i det här exemplet använde vi C-biblioteket för I/O för att undvika uppkomsten av "onödiga" (distraherande) ändringar jämfört med föregående exempel.
Automatiserad programmering används i stor utsträckning i konstruktionen av lexikalanalysatorer (klassiska finita automater) och parsers ( automater med nedtryckt minne ) [1] .
Dessutom är det viktigt att tänka i termer av tillståndsmaskiner (det vill säga att bryta ner exekveringen av ett program i maskinsteg och skicka information från steg till steg genom tillståndet) när man bygger händelsedrivna applikationer. I det här fallet är programmering i FSM-stil det enda alternativet till att skapa flera processer eller trådar .
Ofta används begreppet tillstånd och tillståndsmaskiner för specifikation av program . Så, när du designar programvara med UML , används tillståndsmaskindiagram för att beskriva beteendet hos objekt. Dessutom används explicit tillståndsallokering i beskrivningen av nätverksprotokoll (se t.ex. RFC 793 [2] ).
Att tänka i termer av automater (steg och tillstånd) finner också tillämpning i att beskriva semantiken i vissa programmeringsspråk. Sålunda är exekveringen av ett program på Refal- språket en sekvens av ändringar i synfältet för Refal-maskinen eller, med andra ord, en sekvens av steg i Refal-maskinen, vars tillstånd är innehållet i fältet of view (ett godtyckligt Refal-uttryck som inte innehåller variabler).
Schemes fortsättningsmekanism kräver också att man tänker i termer av stater och steg för att implementera det, även om Scheme i sig inte på något sätt är automatiserat . Men för att kunna "frysa" fortsättningen är det nödvändigt, när man implementerar beräkningsmodellen för Scheme-språket, att kombinera alla komponenter i körtiden, inklusive listan över åtgärder som återstår att utföra för att slutföra beräkning , till en enda enhet, som också brukar kallas en fortsättning . En sådan fortsättning visar sig vara ett tillstånd för automaten, och programexekveringsprocessen består av steg, som vart och ett härleder nästa fortsättningsvärde från det föregående.
Alexander Ollongren beskriver i sin bok [3] den så kallade Wienmetoden för att beskriva programmeringsspråkens semantik, helt baserad på formella automater.
Ett exempel på tillämpningen av automatparadigmet är STAT-systemet [1] ; Detta system inkluderar i synnerhet det inbyggda STATL-språket, som har en ren automatisk semantik.
Det finns också förslag på att använda automatisk programmering som ett universellt tillvägagångssätt för att skapa datorprogram, oavsett ämnesområde. Således hävdar författarna till artikeln [4] att automatisk programmering kan spela rollen som den legendariska silverkulan .
De tidigaste fallen av tillämpning av automatiseringsparadigmet verkar relatera till ämnesområden där en algoritmisk teori baserad på automatteori har utvecklats , och framför allt till analys av texter i formella språk. [1] Ett av de tidigaste verken om detta ämne är artikeln. [5]
En av de första referenserna till användningen av automatprogrammeringstekniker, oavsett den teoretiska utvecklingen baserad på finita tillståndsmaskiner, är en artikel av Peter Naur . [6] I den här artikeln kallar författaren det tillämpade tillvägagångssättet för "Turing machine approach" ( Turing machine approach ), men egentligen finns ingen Turing maskin inbyggd i artikeln; det tillvägagångssätt som ges i artikeln uppfyller ovanstående definition av automatisk programmering .
Konceptet med programtillstånd är inte ett exklusivt inslag i automatisk programmering. Generellt sett uppstår ett tillstånd under körningen av ett datorprogram och är en samling av all information som kan ändras under körningen. Tillståndet för ett program som körs i traditionell imperativ stil består alltså av
Komponenterna i tillståndet kan delas in i explicita (som variabelvärden) och implicita (returadresser och programräknarevärde).
I samband med de införda definitionerna kan ett program utformat som en finit automatmodell betraktas som ett specialfall av ett imperativt program, ett där rollen för den implicita tillståndskomponenten minimeras. Om vi betraktar automatprogrammet vid början av nästa steg av automaten, kommer programmets tillstånd vid dessa ögonblick endast att skilja sig åt i den explicita komponenten. Denna omständighet förenklar avsevärt analysen av programegenskaper.
I teorin om objektorienterad programmering tror man att ett objekt har ett internt tillstånd och kan ta emot meddelanden , svara på dem, skicka meddelanden till andra objekt och ändra dess interna tillstånd i processen att bearbeta meddelanden. Mer praktiskt är att begreppet att anropa ett objekts metod anses vara synonymt med begreppet att skicka ett meddelande till ett objekt .
Således kan å ena sidan objekt i objektorienterad programmering betraktas som ändliga automater (eller, om du vill, modeller av ändliga automater), vars tillstånd är en samling interna fält, medan en eller flera metoder för objekt kan betraktas som ett steg i automaten förutsatt att dessa metoder inte anropar sig själva eller varandra varken direkt eller indirekt.
Å andra sidan är det uppenbart att konceptet med ett objekt är ett bra verktyg för att implementera den finita automatmodellen. När man tillämpar automatprogrammeringsparadigmet i objektorienterade språk representeras automatmodeller vanligtvis som klasser, automatens tillstånd beskrivs av klassens interna (privata) fält och automatens stegkod formateras som en klassmetod, och den här metoden är troligen den enda offentliga metoden (utan att räkna konstruktörer och destruktörer) som ändrar automatens tillstånd. Andra offentliga metoder kan tjäna till att få information om automatens tillstånd, men ändrar den inte. Alla hjälpmetoder (till exempel hanterare av enskilda stater eller deras kategorier) i sådana fall tas vanligtvis bort till den privata delen av klassen.
I SFC beskrivs ett program som en schematisk sekvens av steg förbundna med övergångar.