Аутоматно програмирање

Аутоматно програмирање засновано је на парадигмама програмирања у којој се програм или његов део посматра као модел на коначном аутомату (ФСМ), или било који други (често компликованије) формални аутомат (види теорију аутомата). Понекад потенцијално бесконачан низ могућих стања се уводи, а такав скуп може имати компликовану структуру, а не само пописивање.

ФСМ-басед програмирање је углавном исто, али, формално гледано, не покрива све могуће варијанте, као ФСМ који се залаже за коначан аутомат и аутоматно програмирање засновано на коришћењу ФСМС у строгом смислу.

Следећа својства су кључни показатељи за аутоматно програмирање:

Временски период извршења програма је јасно одвојен степеницама аутомата. Сваки од корака је заправо и даље извршење дела (исти за све кораке) кода, који има једну улазну тачку. Такав део може бити функција или друга рутина, или само тело циклуса. Корак би могао бити подељен на делове који се извршавају у зависности од стања, иако то није неопходно.

Сва комуникација између корака је једино преко експлицитно наведеног сета варијабли наведених стања. Између било која два корака, програми (или његов део је направљена техником аутомата-основе) не могу имати имплицитне компоненте свог стања, као што су вредности локалних (стацк) варијабли, врати адресе, тренутна инструкција показивач итд. То је, стање целог програма, узети у било која два тренутна уласка у корак са аутоматом, могу да се разликовати само у вредности варијабли које се сматрају стањем аутомата.

Цело извршење код аутомата засновано је на (вероватно експлицитном) циклусу корака у аутомату.

Још један разлог да се користи појам аутоматног програмирања проистиче из чињеница да је програмерски стил размишљања о програму у овој техници веома сличан стилу размишљања који се користи за решавање задатака из математике коришћењем Тјурингове машине, Марковог алгоритма и сл.

Пример

Замислите C програм који чита текст из стандардног улазног сигнала, ред по ред, и штампа прву реч сваке линије. Јасно је да прво треба да прочита и прескочи водеће просторе, ако их има, онда прочита карактере прве речи и штампа их све док се реч завршава, а затим прочита и прескочи све преостале знакове до краја-на-линији карактера на коју је наишао. Након достизања краја-на-линији карактера (без обзира на фазу), поново алгоритам креће од почетка, и када сретне крај фајла у стању је (без обзира на фазу), да заврши програм.

Традиционални (императив) програм у C-у

Програм који решава пример задатка у традиционалном стилу (императив) може да изгледа овако:

#укључујући <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;
}

Аутоматно програмирање стил програма

Исти задатак може се решити размишљањем у погледу коначних својстава машина. Имајте на уму да линија парсинг има три фазе: прескакање водећег простора, штампање речи и прескакање задњег карактера. Назовимо их наводи пред , унутра и после . Програм сада може изгледати овако:

#укључујући <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;
}

Иако код сада изгледа веће, он има најмање једну значајну предност: постоји само једно читање (то јест, позовите на гетцхар () функцију) инструкција у програму. Осим тога, постоји само једна петља уместо четири, колико су претходне верзије имали.

У овом програму, тело док петље је аутоматски корак, а сама петља је циклус рада аутомата.

Програм справе (модели) рад је коначан аутомат на слици. N означава крај линије карактера, S означава просторе, и А стоји за све остале ликове. Аутомат следи тачно једну стрелицу на сваком кораку у зависности од тренутног стања и карактера. Нека стања прекидача су заједно са штампаним карактером; такве стрелице су означене са звездицом.

Није апсолутно неопходно да поделимо код до посебних делова за сваку стање. Осим тога, у неким случајевима појам стања може бити састављен од вредности више променљивих ", тако да може бити немогуће да се рукује свако могуће стање експлицитно. У програму се расправља да ли је могуће смањити дужину кода приметивши да су акције које су предузете као одговор на крају линије карактера исте за сва могућа стања. Следећи програм је једнак претходном, али је мало краћи:

#укључујући <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;
}

Посебна функција за аутоматизацију корака

Најважнија имовина претходног програма је да се корак код секција аутомата јасно локализује. Са посебном функцијом за то, боље може да покаже ову особину:

#укључујући <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;
}

Овај пример јасно показује основне особине аутомата-основе кода:

временски периоди извршења корака код аутоамта се не могу преклапати
једина информација од једног корака до другог је изричито стање аутомата

Експлицитно стање сто транзиција

Коначан аутомат се може дефинисати са експлицитним стањем сто транзиција. Генерално говорећи, програмски код аутомата заснива се не природно одражавању оваквог приступа. У програму испод постоји низ по имену табла , који дефинише табелу. Редови у табели су три стања, а колоне одражавају улазне знакове (први за просторе, други за крај линије карактера, а последњи је за све остале ликове).

За сваку могућу комбинацију, табела садржи ново бројчано стање и заставу, која одређује да ли аутомат мора одштампати симбол. У задатку стварног живота, то може бити компликованије; на пример, табела може да садржи савете на функцији која се позива на сваку могућу комбинацију услова.

#укључујући <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);
}

Аутоматизација и Аутомат

Програмирање аутомата-основа заиста блиско одговара потребама програма који се налазе у области аутоматизације.

Продукција циклуса се обично моделира као:

Низ фаза које газе према улазним подацима (од отмичара).

Скуп акција изведених у зависности од тренутне сцене.

Разни посвећени програмски језици омогућавају изражавање таквог модела на мање или више софистициране начине.

Пример програма

Пример приказан горе може се исказати као у следећем програму. Псеудо код користи такве конвенције:

'сет' и 'ресетовање', односно активирати и неактивирати логичку променљиву (овде стаге)
':' Је задатак, '=' је тест равноправности

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
}

Одвајање рутина, изражавање циклуса напредује на једној страни, и стварна акција на другој страни (који одговарају улаз и излаз) омогућава јаснији и једноставнији код.

Аутоматизација и догађаји

У области аутоматизације, корачање од корака до корак зависи од улазних података из саме машине. Ово је представљено у програму читајући знакове из текста. У стварности, ти подаци обавештавају о положају, брзини, температури, и другим критичним елементима машине.

Као у ГУИ програмирању, промена стања машина могу се сматрати догађајима који изазивају одломак из једног стања у друго, док се постигне. Комбинација могућих стања може генерисати широк спектар догађаја, којим сложенији производи раде. Као последица тога, циклуси су обично далеко од тога да буду једноставне линеарне секвенце. Постоје обично паралелне гране које раде заједно и одабране алтернативе према различитим догађајима, шематски представљене у наставку:

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

Користећи објектно оријентисане могућности

Ако језик имплементације подржава објектно-оријентисано програмирање, једноставно рефакторисање ће да обухвати аутомат у објекат, и тако сакрије своје детаље имплементације. На пример, објектно оријентисана верзија у C++ истог програма је испод. Софистицираније рефакторисање је могло да користи стање обрасца.

#укључујући <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;
}

Напомена: Да бисте умањили промене нису директно везане за тему чланка, улаз / излаз функције из стандардне библиотеке C се користи. Обратите пажњу на коришћење тројног оператора, који би могао да се реализује као ако-друго.

Апликације

Аутомати-основе програмирања се широко користе у лексичкој и синтаксичкој анализи.^[1]

Осим тога, размишља у смислу аутомата (то јест, разбијање процеса извршења до аутоматских корака и преношења информација од корака до корака кроз експлицитно стање) је неопходан за програмирање покретних догађаја као једина алтернатива коришћења паралелног процеса или теме.

Појмови стања и стање машина се често користе у области формалне спецификације. На пример, УМЛ-басед софтваре девелопмент архитектура користи стање дијаграма да одреди понашање програма. Такође, различити комуникациони протоколи често користе експлицитни појам стања.^[2]

Размишљање у смислу аутомата (кораци и стања) може да се користи за описивање семантичких неких програмских језика. На пример, извршење програма написаног у Рефал језику је описано као низ корака тзв апстрактне Рефал машине; стање машине је поглед (произвољан Рефал израз без варијабли).

Наставак у шеми језика захтева размишљање у погледу корака и стања, мада сама шема ниије ни на који начин у вези са аутоматима (то је рекурзивна). Да би била могућа функција позив / сс за рад, имплементација треба да буде у стању да ухвати цело стање извршиоца програма, што је могуће само када нема имплицитног дела стања. Такво стање ствар која се зове наставак, и може се сматрати као стање (релативно компликоване) аутомата. Корак од аутомата је дедуцинг наставак из претходног, а процес извршења је циклус таквих корака.

Александар Оллонгрен у својој књизи^[3] објашњава тзв Виенна метод програмских језика семантике описа који је у потпуности заснован на формалним аутоматима.

СТАТ систем [1] је добар пример коришћењем приступа аутомата; овај систем, поред осталих карактеристика, укључује уграђен језик под називом СТАТЛ који је чисто аутоматно програмирање.

Историја

Технике аутомата засноване су у широкој употреби у областима где постоје алгоритми на основу теорије аутомата, као што су анализе формалних језика.^[1]

Једна од раних чланака о овом јесте Јохнсон et al. 1968.^[4]

Један од најранијих помињања програмирања аутомата засновано као генерална техника налази се у раду Питера Наура, 1963.^[5] Аутор назива технику приступ Тјурингове машине, међутим лажна Тјурингова машина је дата у раду; уместо тога, описана је техника заснована на стањима и корацима.

Поређење императивног и процедуралног програмирања

Појам стање није искључиво власништво аутоматног програмирања.^[6] Уопштено говорећи, стања (или стање програма) се појављују у току извршења било ког рачунарског програма, као комбинација свих информација које се могу променити током извршења. На пример, стање традиционалног императивног програма се састоји од

Вредности свих варијабли и информација се чувају у динамичкој меморији
Вредности се чувају у регистрима
Стацк садржај (укључујући вредности локалне променљиве 'и вратити адресе)
тренутна вредност показивача инструкција

Они се могу поделити на експлицитне делове (као што су вредности које се чувају у варијаблама) и имплицитни део (повратне адресе и инструкција показивача).

Рекавши то, програм за аутомате на бази може се сматрати као посебан случај императивног програма, у којем имплицитни део стања се своди на минимум. Стање целог програма узима два различита тренутка уласка у код секције, корак може разликовати у аутомату само стања. Ово поједностављује анализу програма.

Објектно оријентисано програмерска веза

У теорији објектно-оријентисаног програмирања објекат је рекао да има унутрашње стање и способан је да прима поруке, одговарајући на њих, слање порука на друге објекте и промене унутрашњег стања током руковања поруке. У вишој практичној терминологији, да позовете метод објекта се сматра исто као да пошаљете поруку на објекту.

Тако, са једне стране, предмети са објектно оријентисаног програмирања се могу сматрати аутомати (или модели аутомата), чије стање је комбинација унутрашњих поља, и један или више поступака се сматрају као кораци. Такве методе не смеју звати једни друге, ни себе, ни директно ни индиректно, иначе предмет не може се сматрати да се имплементира на начин аутомата-основе.

С друге стране, очигледно је да објекат је добар за имплементацију модела аутомата. Када је приступ аутомата заснован да се користи у објектно-оријентисаном језику, аутомат модела обично спроводи класе, стања које су заступљене са унутрашњим (приватних) пољима класа, а корак спроводи као метод; такав метод је обично једини неконстантан публик метод класе (поред грађевинаре и деструкторима). Остале јавне методе могу да упитају стање, али то не мења. Све секундарне методе (као што је појединим државним сировина) су обично сакривене у приватном делу класе.

Види још

Недетерминистичко програмирање
Стање обрасца
Естерел, језик аутоматног програмирања
Умпле, алат за додавање аутомата у Јави и C++

Референце

^ ^а ^б 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.
^ РФЦ 793
^ Ollongren, Alexander (1974). Definition of programming languages by interpreting automata. London: Academic Press. ISBN 978-0-12-525750-3.
^ 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.
^ 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. ^{[мртва веза]}
^ „Automata-based programming” (PDF). Scientific and Technicial Journal of Information Technologies, Mechanics and Optics (53). 2008.

Литература

Ollongren, Alexander (1974). Definition of programming languages by interpreting automata. London: Academic Press. ISBN 978-0-12-525750-3.
Harel, David (1987). „Statecharts: A visual formalism for complex systems”. Science of Computer Programming. 8 (3): 231—274. doi:10.1016/0167-6423(87)90035-9.

Спољашње везе

J. V. Noble. «Finite State Machines in Forth» — automata-based programming in Forth
Harel, David; Drusinsky, D. (1989). "Using Statecharts for Hardware Description and Synthesis". IEEE Trans. Computer Aided Design of Integrated Circuits and Systems (8): 798–807.
Polikarpova N. I., Shalyto A. A. Automata-based programming SPb.: Piter. 2009 (rus)
ITMO University, "Programming Technology" department