Automatno programiranje

S Vikipedije, slobodne enciklopedije
Paradigme programiranja

Automatno programiranje zasnovano je na paradigmama programiranja u kojoj se program ili njegov deo posmatra kao model na konačnom automatu (FSM), ili bilo koji drugi (često komplikovanije) formalni automat (vidi teoriju automata). Ponekad potencijalno beskonačan niz mogućih stanja se uvodi, a takav skup može imati komplikovanu strukturu, a ne samo popisivanje.

FSM-based programiranje je uglavnom isto, ali, formalno gledano, ne pokriva sve moguće varijante, kao FSM koji se zalaže za konačan automat i automatno programiranje zasnovano na korišćenju FSMS u strogom smislu.

Sledeća svojstva su ključni pokazatelji za automatno programiranje:

  1. Vremenski period izvršenja programa je jasno odvojen stepenicama automata. Svaki od koraka je zapravo i dalje izvršenje dela (isti za sve korake) koda, koji ima jednu ulaznu tačku. Takav deo može biti funkcija ili druga rutina, ili samo telo ciklusa. Korak bi mogao biti podeljen na delove koji se izvršavaju u zavisnosti od stanja, iako to nije neophodno.
  1. Sva komunikacija između koraka je jedino preko eksplicitno navedenog seta varijabli navedenih stanja. Između bilo koja dva koraka, programi (ili njegov deo je napravljena tehnikom automata-osnove) ne mogu imati implicitne komponente svog stanja, kao što su vrednosti lokalnih (stack) varijabli, vrati adrese, trenutna instrukcija pokazivač itd. To je, stanje celog programa, uzeti u bilo koja dva trenutna ulaska u korak sa automatom, mogu da se razlikovati samo u vrednosti varijabli koje se smatraju stanjem automata.

Celo izvršenje kod automata zasnovano je na (verovatno eksplicitnom) ciklusu koraka u automatu.

Još jedan razlog da se koristi pojam automatnog programiranja proističe iz činjenica da je programerski stil razmišljanja o programu u ovoj tehnici veoma sličan stilu razmišljanja koji se koristi za rešavanje zadataka iz matematike korišćenjem Tjuringove mašine, Markovog algoritma i sl.

Primer[uredi | uredi izvor]

Zamislite C program koji čita tekst iz standardnog ulaznog signala, red po red, i štampa prvu reč svake linije. Jasno je da prvo treba da pročita i preskoči vodeće prostore, ako ih ima, onda pročita karaktere prve reči i štampa ih sve dok se reč završava, a zatim pročita i preskoči sve preostale znakove do kraja-na-liniji karaktera na koju je naišao. Nakon dostizanja kraja-na-liniji karaktera (bez obzira na fazu), ponovo algoritam kreće od početka, i kada sretne kraj fajla u stanju je (bez obzira na fazu), da završi program.

Tradicionalni (imperativ) program u C-u[uredi | uredi izvor]

Program koji rešava primer zadatka u tradicionalnom stilu (imperativ) može da izgleda ovako: 

#укључујући <stdio.h>
#укључујући <ctype.h>
int main(void)
{
    int c;
    do {
        do
            c = getchar();
        while(c == ' ');
        while(c != EOF && !isspace(c) && c != '\n') {
            putchar(c);
            c = getchar();
        }
        putchar('\n');
        while(c != EOF && c != '\n')
            c = getchar();
    } while(c != EOF);
    return 0;
}

Automatno programiranje stil programa[uredi | uredi izvor]

Isti zadatak može se rešiti razmišljanjem u pogledu konačnih svojstava mašina. Imajte na umu da linija parsing ima tri faze: preskakanje vodećeg prostora, štampanje reči i preskakanje zadnjeg karaktera. Nazovimo ih navodi пред , унутра i после . Program sada može izgledati ovako: 

#укључујући <stdio.h>
#укључујући <ctype.h>
int main(void)
{
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        switch(state) {
            case before:
                if(c != ' ') {
                    putchar(c);
                    if(c != '\n')
                        state = inside;
                }
                break; 
            case inside:
                if(!isspace(c))
                    putchar(c);
                else {
                    putchar('\n');
                    if(c == '\n')
                        state = before;
                    else
                        state = after;
                }
                break;
            case after:
                if(c == '\n')
                    state = before;
        }
    }
    return 0;
}

Iako kod sada izgleda veće, on ima najmanje jednu značajnu prednost: postoji samo jedno čitanje (to jest, pozovite na гетцхар () funkciju) instrukcija u programu. Osim toga, postoji samo jedna petlja umesto četiri, koliko su prethodne verzije imali.

U ovom programu, telo док petlje je automatski korak, a sama petlja je ciklus rada automata.

Automaton's diagram
Automaton's diagram

Program sprave (modeli) rad je konačan automat na slici. N označava kraj linije karaktera, S označava prostore, i A stoji za sve ostale likove. Automat sledi tačno jednu strelicu na svakom koraku u zavisnosti od trenutnog stanja i karaktera. Neka stanja prekidača su zajedno sa štampanim karakterom; takve strelice su označene sa zvezdicom.

Nije apsolutno neophodno da podelimo kod do posebnih delova za svaku stanje. Osim toga, u nekim slučajevima pojam stanja može biti sastavljen od vrednosti više promenljivih ", tako da može biti nemoguće da se rukuje svako moguea stanje eksplicitno. U programu se raspravlja da li je moguće smanjiti dužinu koda primetivši da su akcije koje su preduzete kao odgovor na kraju linije karaktera iste za sva moguća stanja. Sledeći program je jednak prethodnom, ali je malo kraći: 

#укључујући <stdio.h>
#укључујући <ctype.h>
int main(void)
{
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        if(c == '\n') {
            putchar('\n');
            state = before;
        } else
        switch(state) {
            case before:
                if(c != ' ') {
                    putchar(c);
                    state = inside;
                }
                break;
            case inside:
                if(c == ' ') {
                    state = after;
                } else {
                    putchar(c);
                }
                break;
            case after:
                break;
        }
    }
    if(state != before)
        putchar('\n');
    return 0;
}

Posebna funkcija za automatizaciju koraka[uredi | uredi izvor]

Najvažnija imovina prethodnog programa je da se korak kod sekcija automata jasno lokalizuje. Sa posebnom funkcijom za to, bolje može da pokaže ovu osobinu: 

#укључујући <stdio.h>
enum states { before, inside, after };
void step(enum states *state, int c)
{
    if(c == '\n') {
        putchar('\n');
        *state = before;
    } else
    switch(*state) {
        case before:
            if(c != ' ') {
                putchar(c);
                *state = inside;
            }
            break;
        case inside:
            if(c == ' ') {
                *state = after;
            } else {
                putchar(c);
            }
            break;
        case after:
            break;
    }
}
int main(void)
{
    int c;
    enum states state = before;
    while((c = getchar()) != EOF) {
        step(&state, c);
    }
    if(state != before)
        putchar('\n');
    return 0;
}

Ovaj primer jasno pokazuje osnovne osobine automata-osnove koda:

  1. vremenski periodi izvršenja koraka kod autoamta se ne mogu preklapati
  2. jedina informacija od jednog koraka do drugog je izričito stanje automata

Eksplicitno stanje sto tranzicija[uredi | uredi izvor]

Konačan automat se može definisati sa eksplicitnim stanjem sto tranzicija. Generalno govoreći, programski kod automata zasniva se ne prirodno odražavanju ovakvog pristupa. U programu ispod postoji niz po imenu табла , koji definiše tabelu. Redovi u tabeli su tri stanja, a kolone odražavaju ulazne znakove (prvi za prostore, drugi za kraj linije karaktera, a poslednji je za sve ostale likove).

Za svaku moguću kombinaciju, tabela sadrži novo brojčano stanje i zastavu, koja određuje da li automat mora odštampati simbol. U zadatku stvarnog života, to može biti komplikovanije; na primer, tabela može da sadrži savete na funkciji koja se poziva na svaku moguću kombinaciju uslova. 

#укључујући <stdio.h>
enum states { before = 0, inside = 1, after = 2 };
struct branch {
    unsigned char new_state:2;
    unsigned char should_putchar:1;
};
struct branch the_table[3][3] = {
                 /* ' '         '\n'        others */
    /* before */ { {before,0}, {before,1}, {inside,1} },
    /* inside */ { {after, 1}, {before,1}, {inside,1} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }
};
void step(enum states *state, int c)
{
    int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
    struct branch *b = & the_table[*state][idx2];
    *state = (enum states)(b->new_state);
    if(b->should_putchar) putchar(c);
}

Automatizacija i Automat[uredi | uredi izvor]

Programiranje automata-osnova zaista blisko odgovara potrebama programa koji se nalaze u oblasti automatizacije.

Produkcija ciklusa se obično modelira kao:

  • Niz faza koje gaze prema ulaznim podacima (od otmičara).
  • Skup akcija izvedenih u zavisnosti od trenutne scene.

Razni posvećeni programski jezici omogućavaju izražavanje takvog modela na manje ili više sofisticirane načine.

Primer programa[uredi | uredi izvor]

Primer prikazan gore može se iskazati kao u sledećem programu. Pseudo kod koristi takve konvencije:

  • 'set' i 'resetovanje', odnosno aktivirati i neaktivirati logičku promenljivu (ovde stage)
  • ':' Je zadatak, '=' je test ravnopravnosti
SPC : ' '
EOL : '\n'

states : (before, inside, after, end, endplusnl)

setState(c) {
    if c=EOF then if inside or after then set endplusnl else set end
    if before and (c!=SPC and c!=EOL) then set inside
    if inside and (c=SPC or c=EOL) then set after
    if after and c=EOL then set before
}

doAction(c) {
    if inside then write(c)
    else if c=EOL or endplusnl then write(EOL)
}

cycle {
    set before
    loop {
        c : readCharacter
        setState(c)
        doAction(c)
    }
    until end or endplusnl
}

Odvajanje rutina, izražavanje ciklusa napreduje na jednoj strani, i stvarna akcija na drugoj strani (koji odgovaraju ulaz i izlaz) omogućava jasniji i jednostavniji kod.

Automatizacija i događaji[uredi | uredi izvor]

U oblasti automatizacije, koračanje od koraka do korak zavisi od ulaznih podataka iz same mašine. Ovo je predstavljeno u programu čitajući znakove iz teksta. U stvarnosti, ti podaci obaveštavaju o položaju, brzini, temperaturi, i drugim kritičnim elemenatima mašine.

Kao u GUI programiranju, promena stanja mašina mogu se smatrati događajima koji izazivaju odlomak iz jednog stanja u drugo, dok se postigne. Kombinacija mogućih stanja može generisati širok spektar događaja, kojim složeniji proizvodi rade. Kao posledica toga, ciklusi su obično daleko od toga da budu jednostavne linearne sekvence. Postoje obično paralelne grane koje rade zajedno i odabrane alternative prema različitim događajima, šematski predstavljene u nastavku: 

   s:stage   c:condition
   
   s1
   |
   |-c2
   |
   s2
   |
   ----------
   |        |
   |-c31    |-c32
   |        |
  s31       s32
   |        |
   |-c41    |-c42
   |        |
   ----------
   |
   s4

Koristeći objektno orijentisane mogućnosti[uredi | uredi izvor]

Ako jezik implementacije podržava objektno-orijentisano programiranje, jednostavno refaktorisanje će da obuhvati automat u objekat, i tako sakrije svoje detalje implementacije. Na primer, objektno orijentisana verzija u C++ istog programa je ispod. Sofisticiranije refaktorisanje je moglo da koristi stanje obrasca. 

#укључујући <stdio.h>
class StateMachine {
    enum states { before = 0, inside = 1, after = 2 } state;
    struct branch {
        enum states new_state:2;
        int should_putchar:1;
    };
    static struct branch the_table[3][3];
public:
    StateMachine() : state(before) {}
    void FeedChar(int c) {
        int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
        struct branch *b = & the_table[state][idx2];
        state = b->new_state;
        if(b->should_putchar) putchar(c);
    }
};
struct StateMachine::branch StateMachine::the_table[3][3] = {
                 /* ' '         '\n'        others */
    /* before */ { {before,0}, {before,1}, {inside,1} },
    /* inside */ { {after, 0}, {before,1}, {inside,1} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }
};
int main(void)
{
    int c;
    StateMachine machine;
    while((c = getchar()) != EOF)
        machine.FeedChar(c);
    return 0;
}

Napomena: Da biste umanjili promene nisu direktno vezane za temu članka, ulaz / izlaz funkcije iz standardne biblioteke C se koristi. Obratite pažnju na korišćenje trojnog operatora, koji bi mogao da se realizuje kao ako-drugo.

Aplikacije[uredi | uredi izvor]

Automati-osnove programiranja se široko koriste u leksičkoj i sintaksičkoj analizi.[1]

Osim toga, razmišlja u smislu automata (to jest, razbijanje procesa izvršenja do automatskih koraka i prenošenja informacija od koraka do koraka kroz eksplicitno stanje) je neophodan za programiranje pokretnih događaja kao jedina alternativa korišćenja paralelnog procesa ili teme.

Pojmovi stanja i stanje mašina se često koriste u oblasti formalne specifikacije. Na primer, UML-based softvare development arhitektura koristi stanje dijagrama da odredi ponašanje programa. Takođe, različiti komunikacioni protokoli često koriste eksplicitni pojam stanja.[2]

Razmišljanje u smislu automata (koraci i stanja) može da se koristi za opisivanje semantičkih nekih programskih jezika. Na primer, izvršenje programa napisanog u Refal jeziku je opisano kao niz koraka tzv apstraktne Refal mašine; stanje mašine je pogled (proizvoljan Refal izraz bez varijabli).

Nastavak u šemi jezika zahteva razmišljanje u pogledu koraka i stanja, mada sama šema niije ni na koji način u vezi sa automatima (to je rekurzivna). Da bi bila moguća funkcija poziv / ss za rad, implementacija treba da bude u stanju da uhvati celo stanje izvršioca programa, što je moguće samo kada nema implicitnog dela stanja. Takvo stanje stvar koja se zove nastavak, i može se smatrati kao stanje (relativno komplikovane) automata. Korak od automata je deducing nastavak iz prethodnog, a proces izvršenja je ciklus takvih koraka.

Aleksandar Ollongren u svojoj knjizi[3] objašnjava tzv Vienna metod programskih jezika semantike opisa koji je u potpunosti zasnovan na formalnim automatima.

STAT sistem [1] je dobar primer korišćenjem pristupa automata; ovaj sistem, pored ostalih karakteristika, uključuje ugrađen jezik pod nazivom STATL koji je čisto automatno programiranje.

Istoirija[uredi | uredi izvor]

Tehnike automata zasnovane su u širokoj upotrebi u oblastima gde postoje algoritmi na osnovu teorije automata, kao što su analize formalnih jezika.[1]

Jedna od ranih članaka o ovom jeste Johnson et al. 1968.[4]

Jedan od najranijih pominjanja programiranja automata zasnovano kao generalna tehnika nalazi se u radu Pitera Naura, 1963.[5] Autor naziva tehniku pristup Tjuringove mašine, međutim lažna Tjuringova mašina je data u radu; umesto toga, opisana je tehnika zasnovana na stanjima i korakcima.

Poređenje imperativnog i proceduralnog programiranja[uredi | uredi izvor]

Pojam stanje nije isključivo vlasništvo automatnog programiranja.[6] Uopšteno govoreći, stanja (ili stanje programa) se pojavljuju u toku izvršenja bilo kog računarskog programa, kao kombinacija svih informacija koje se mogu promeniti tokom izvršenja. Na primer, stanje tradicionalnog imperativnog programa se sastoji od

  1. Vrednosti svih varijabli i informacija se čuvaju u dinamičkoj memoriji
  2. Vrednosti se čuvaju u registrima
  3. Stack sadržaj (uključujući vrednosti lokalne promenljive 'i vratiti adrese)
  4. trenutna vrednost pokazivača instrukcija

Oni se mogu podeliti na eksplicitne delove (kao što su vrednosti koje se čuvaju u varijablama) i implicitni deo (povratne adrese i instrukcija pokazivača).

Rekavši to, program za automate na bazi može se smatrati kao poseban slučaj imperativnog programa, u kojem implicitni deo stanja se svodi na minimum. Stanje celog programa uzima dva različita trenutka ulaska u kod sekcije, korak može razlikovati u automatu samo stanja. Ovo pojednostavljuje analizu programa.

Objektno orijentisano programerska veza [uredi | uredi izvor]

U teoriji objektno-orijentisanog programiranja objekat je rekao da ima unutrašnje stanje i sposoban je da prima poruke, odgovarajući na njih, slanje poruka na druge objekte i promene unutrašnjeg stanja tokom rukovanja poruke. U višoj praktičnoj terminologiji, da pozovete metod objekta se smatra isto kao da pošaljete poruku na objektu.

Tako, sa jedne strane, predmeti sa objektno orijentisanog programiranja se mogu smatrati automati (ili modeli automata), čije stanje je kombinacija unutrašnjih polja, i jedan ili više postupaka se smatraju kao koraci. Takve metode ne smeju zvati jedni druge, ni sebe, ni direktno ni indirektno, inače predmet ne može se smatrati da se implementira na način automata-osnove.

S druge strane, očigledno je da objekat je dobar za implementaciju modela automata. Kada je pristup automata zasnovan da se koristi u objektno-orijentisanom jeziku, automat modela obično sprovodi klase, stanja koje su zastupljene sa unutrašnjim (privatnih) poljima klasa, a korak sprovodi kao metod; takav metod je obično jedini nekonstantan publik metod klase (pored građevinare i destruktorima). Ostale javne metode mogu da upitaju stanje, ali to ne menja. Sve sekundarne metode (kao što je pojedinim državnim sirovina) su obično sakrivene u privatnom delu klase.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ a b Aho, Alfred V.; Ullman, Jeffrey D. (1973). The theory of parsing, translation and compiling. 1. Englewood Cliffs, N. J.: Prentice-Hall. ISBN 978-0-13-914564-3. 
  2. ^ RFC 793
  3. ^ Ollongren, Alexander (1974). Definition of programming languages by interpreting automata. London: Academic Press. ISBN 978-0-12-525750-3. 
  4. ^ Johnson, W. L.; Porter, J. H.; Ackley, S. I.; Ross, D. T. (1968). „Automatic generation of efficient lexical processors using finite state techniques”. Comm ACM. 11 (12): 805—813. S2CID 17253809. doi:10.1145/364175.364185. 
  5. ^ Naur, Peter (1963). „The design of the GIER ALGOL compiler Part II”. BIT Numerical Mathematics. 3 (3): 145—166. S2CID 189785656. doi:10.1007/BF01939983. [mrtva veza]
  6. ^ „Automata-based programming” (PDF). Scientific and Technicial Journal of Information Technologies, Mechanics and Optics (53). 2008. 

Literatura[uredi | uredi izvor]

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Аутоматно_програмирање&oldid=27672953”