Automatisk baseret programmering - Automata-based programming

For anden anvendelse, se Automatabaseret programmering (Shalytos tilgang) .
Programmeringsparadigmer

Automatabaseret programmering er et programmeringsparadigme , hvor programmet eller en del af det betragtes som en model af en finite-state-maskine (FSM) eller en hvilken som helst anden (ofte mere kompliceret) formel automat (se automatteori ). Nogle gange introduceres et potentielt uendeligt sæt af mulige tilstande, og et sådant sæt kan have en kompliceret struktur, ikke kun en opregning.

Finite-state maskinbaseret programmering er generelt den samme, men dækker formelt set ikke alle mulige varianter, da FSM står for finite-state machine, og automatbaseret programmering ikke nødvendigvis anvender FSM'er i streng forstand.

Følgende egenskaber er nøgleindikatorer for automatbaseret programmering:

  • Tidsperioden for programmets udførelse er klart adskilt til automatiktrinene . Hvert trin er effektivt en udførelse af en kodesektion (ens for alle trin), der har et enkelt indgangspunkt. Denne sektion kan opdeles i underafsnit, der skal udføres afhængigt af forskellige tilstande, selvom dette ikke er nødvendigt.
  • Enhver kommunikation mellem automatiktrinene er kun mulig via det eksplicit noterede sæt variabler, der hedder automatstatus . Mellem to trin kan programmet ikke have implicitte komponenter i sin tilstand, f.eks. Lokale variabels værdier, returadresser, den aktuelle instruktionsmarkør osv. Det vil sige hele programmets tilstand taget på et hvilket som helst to øjeblikke for at indtaste en automatiktrin, kan kun afvige i værdierne for de variabler, der betragtes som automatstatus.

Hele udførelsen af ​​den automatbaserede kode er en cyklus af automatiktrinene.

En anden grund til at bruge begrebet automatbaseret programmering er, at programmørens tankegang om programmet i denne teknik ligner meget den tankegang, der bruges til at løse matematiske opgaver ved hjælp af Turing-maskiner , Markov-algoritmer osv.

Eksempel

Opgave

Overvej opgaven med at læse en tekst fra standardinput linje for linje og skrive det første ord i hver linje til standardoutput . Først springer vi alle ledende whitespace -tegn over, hvis nogen. Derefter udskriver vi alle tegnene i det første ord. Endelig springer vi alle de efterfølgende tegn over, indtil der er stødt på en ny linje . Når der opstår en sekvens af nylinjetegn ikke i begyndelsen af ​​strømmen, udskriver vi kun den første og springer de resterende over; ellers springer vi alt over. Derefter genstarter vi processen på følgende linje. Når vi støder på slutningen af ​​filen (uanset fase), stopper vi.

Traditionelt program

Et traditionelt program i C, der udfører ovenstående opgave, kan se sådan ud: 

#include <ctype.h>
#include <stdio.h>


int main(void) {
  int c;

  do {
    do {
      c = getchar();
    } while (isspace(c));

    while (!isspace(c) && c != EOF) {
      putchar(c);
      c = getchar();
    }
    
    while (c != '\n' && c != EOF) {
      c = getchar();
    }
    
    if (c == '\n') {
      putchar(c);
    }
  } while (c != EOF);

  return 0;
}

For eksempel kompilering og kørsel af ovenstående program på dette input: 

$ clang program.c && (printf "\t\v\f\r \n\n\t\v\f\r foo bar baz\n\n\t\v\f\r qux quux corge" | ./a.out)

udbytter: 

foo
qux

Automatabaseret program

Proceduremæssig

Den samme opgave kan løses ved at tænke i form af finite-state-maskiner . Bemærk, at analysen af ​​en linje har tre faser: springe de ledende mellemrumstegn over, udskrivning af tegnene i det første ord og springning af de efterfølgende tegn. Lad os kalde disse automatstater BEFORE, INSIDEog AFTER. En automatbaseret version af programmet kunne se sådan ud: 

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    switch (s) {
      case BEFORE:
        if (!isspace(c)) {
          putchar(c);
          s = INSIDE;
        }
        
        break;
      case INSIDE:
        if (c == '\n') {
          putchar(c);
          s = BEFORE;
        } else if (isspace(c)) {
          s = AFTER;
        } else {
          putchar(c);
        }
          
        break;
      case AFTER:
        if (c == '\n') {
          putchar(c);
          s = BEFORE;
        }
        
        break;
    }
  }

  return 0;
}

Selvom programmet nu ser længere ud, har det mindst en væsentlig fordel: der er kun en læsning (det vil sige opkald til getcharfunktionen) instruktion. Udover det er der kun en sløjfe i stedet for de fire, den traditionelle version havde. Loopens krop whileer automatiktrinnet og selve sløjfen er cyklussen for automatiktrinnet. Programmet implementerer arbejdet i en finite-state maskine vist i tilstandsdiagrammet.

Den vigtigste egenskab ved programmet er, at sektionen for automatiktrinskode er klart lokaliseret. Med en eksplicit funktion steptil automatiseringstrinnet demonstrerer programmet denne egenskab bedre: 

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


void step(enum State* const s, int const c) {
  switch (*s) {
    case BEFORE:
      if (!isspace(c)) {
        putchar(c);
        *s = INSIDE;
      }
      
      break;
    case INSIDE:
      if (c == '\n') {
        putchar(c);
        *s = BEFORE;
      } else if (isspace(c)) {
        *s = AFTER;
      } else {
        putchar(c);
      }
        
      break;
    case AFTER:
      if (c == '\n') {
        putchar(c);
        *s = BEFORE;
      }
      
      break;
  }
}


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    step(&s, c);
  }

  return 0;
}

Programmet viser nu klart de grundlæggende egenskaber ved automatbaseret kode:

  • tidsperioder for automatiske trinudførelser må ikke overlappe hinanden;
  • den eneste information, der sendes fra det foregående trin til det næste, er den eksplicit angivne automatstatus .

En endelig automat kan defineres af en tilstandsovergangstabel, hvis rækker står for de aktuelle tilstande, kolonner står for input, og celler står for de næste tilstande og handlinger, der skal udføres.

Statens overgangstabel
Input
Nuværende tilstand
 ny linje hvidt rum Andet
Før Før Før indvendigt/print
inde før/udskriv efter indvendigt/print
efter før/udskriv efter efter
Stat diagram
Den tilstandsdiagram af en endelig tilstandsmaskine, der udskriver det første ord i hver linie i en input stream. Maskinen følger nøjagtigt en overgang på hvert trin, afhængigt af den aktuelle tilstand og den stødte karakter. Handlingen, der ledsager en overgang, er enten en no-operation eller udskrivning af den stødte karakter, betegnet med print .

Generelt kan et automatbaseret program naturligvis bruge denne fremgangsmåde. Med et eksplicit todimensionalt array transitionstil tilstandsovergangstabellen bruger programmet denne fremgangsmåde: 

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


void nop(int const c) {}


void print(int const c) {
  putchar(c);
}


struct Branch {
  enum State const next_state;
  void (*action)(int);
};


struct Branch const transitions[3][3] = {
  //   newline         whitespace         other             Inputs/States
  {{BEFORE,   &nop}, {BEFORE, &nop}, {INSIDE, &print}},  // before
  {{BEFORE, &print}, {AFTER,  &nop}, {INSIDE, &print}},  // inside
  {{BEFORE, &print}, {AFTER,  &nop}, {AFTER,    &nop}}   // after
};


void step(enum State* const s, int const c) {
  int const row = (*s == BEFORE) ? 0 : (*s == INSIDE) ? 1 : 2;
  int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2;
  struct Branch const* const b = &transitions[row][column];
  *s = b->next_state;
  b->action(c);
}


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    step(&s, c);
  }

  return 0;
}

Objektorienteret

Hvis implementeringssproget understøtter objektorienteret programmering , er en simpel refaktorering af programmet at indkapsle automaten til et objekt og dermed skjule dens implementeringsdetaljer. Programmet i C ++ ved hjælp af objektorienteret stil kunne se sådan ud: 

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


struct Branch {
  enum State const next_state;
  void (*action)(int);
};


class StateMachine {
  public:
    StateMachine();
    void feedChar(int);

  protected:
    static void nop(int);
    static void print(int);

  private:
    enum State _state;
    static struct Branch const _transitions[3][3];
};


StateMachine::StateMachine(): _state(BEFORE) {}


void StateMachine::feedChar(int const c) {
  int const row = (_state == BEFORE) ? 0 : (_state == INSIDE) ? 1 : 2;
  int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2;
  struct Branch const* const b = &_transitions[row][column];
  _state = b->next_state;
  b->action(c);
}


void StateMachine::nop(int const c) {}


void StateMachine::print(int const c) {
  putchar(c);
}


struct Branch const StateMachine::_transitions[3][3] = {
  //   newline         whitespace         other             Inputs/States
  {{BEFORE,   &nop}, {BEFORE, &nop}, {INSIDE, &print}},  // before
  {{BEFORE, &print}, {AFTER,  &nop}, {INSIDE, &print}},  // inside
  {{BEFORE, &print}, {AFTER,  &nop}, {AFTER,    &nop}}   // after
};


int main() {
  int c;
  StateMachine m;

  while ((c = getchar()) != EOF) {
    m.feedChar(c);
  }

  return 0;
}

Bemærk. - at minimere ændringer ikke er direkte relateret til emnet af artiklen, at input / output getchar og putcharfunktioner fra standard bibliotek af C bliver brugt.

Den statslige design mønster er en måde for en genstand til at ændre adfærd ved runtime i henhold til dens indre tilstand uden at ty til store betingede udsagn eller tabelopslag takket være virtuelle funktionskald. Dens største fordel i forhold til kode ved hjælp af store betingede udsagn er, at statsspecifik kode distribueres på tværs af forskellige objekter frem for lokaliseret i en monolitisk blok, hvilket forbedrer vedligeholdelsesevnen. Dens største fordele i forhold til kode ved hjælp af tilstandsovergangstabeller er, at virtuelle funktionsopkald ofte er mere effektive end tabelopslag, at tilstandsovergangskriterier er mere eksplicitte end i tabelformat, og at det er lettere at tilføje handlinger, der ledsager tilstandsovergange. Det introducerer imidlertid et nyt problem: antallet af klasser gør koden mindre kompakt end de andre tilgange. Programmet, der bruger statens designmønster, kan se sådan ud: 

#include <ctype.h>
#include <stdio.h>

class StateMachine;


class State {
  public:
    virtual void feedChar(StateMachine*, int) const = 0;
};


class Before: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    Before() = default;

  private:
    static State const* _instance;
};


class Inside: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    Inside() = default;

  private:
    static State const* _instance;
};


class After: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    After() = default;

  private:
    static State const* _instance;
};


class StateMachine {
  public:
    StateMachine();
    void feedChar(int);

  protected:
    void setState(State const*);

  private:
    State const* _state;
    friend class Before;
    friend class Inside;
    friend class After;
};


State const* Before::instantiate() {
  if (!_instance) {
    _instance = new Before;
  }

  return _instance;
}


void Before::feedChar(StateMachine* const m, int const c) const {
  if (!isspace(c)) {
    putchar(c);
    m->setState(Inside::instantiate());
  }
}


State const* Before::_instance = nullptr;


State const* Inside::instantiate() {
  if (!_instance) {
    _instance = new Inside;
  }

  return _instance;
}


void Inside::feedChar(StateMachine* const m, int const c) const {
  if (c == '\n') {
    putchar(c);
    m->setState(Before::instantiate());
  } else if (isspace(c)) {
    m->setState(After::instantiate());
  } else {
    putchar(c);
  }
}


State const* Inside::_instance = nullptr;


State const* After::instantiate() {
  if (!_instance) {
    _instance = new After;
  }

  return _instance;
}


void After::feedChar(StateMachine* const m, int const c) const {
  if (c == '\n') {
    putchar(c);
    m->setState(Before::instantiate());
  }
}


State const* After::_instance = nullptr;


StateMachine::StateMachine(): _state(Before::instantiate()) {}


void StateMachine::feedChar(int const c) {
  _state->feedChar(this, c);
}


void StateMachine::setState(State const* const s) {
  _state = s;
}


int main() {
  int c;
  StateMachine m;

  while ((c = getchar()) != EOF) {
    m.feedChar(c);
  }

  return 0;
}

Automatisering og automatik

Automatbaseret programmering matcher faktisk nøje programmeringsbehovet inden for automatisering .

En produktionscyklus modelleres almindeligvis som:

  • en sekvens af trin, der træder i henhold til inputdata (fra fangere);
  • et sæt handlinger, der udføres afhængigt af den aktuelle fase.

Forskellige dedikerede programmeringssprog gør det muligt at udtrykke en sådan model på mere eller mindre sofistikerede måder.

Automatiseringsprogram

Eksemplet ovenfor kan udtrykkes i henhold til denne opfattelse som i den følgende pseudokode ('sæt' aktiverer en logisk variabel, 'nulstil' inaktiverer en logisk variabel, ':' tildeler en variabel og '=' test for lighed) : 

newline: '\n'
whitespace: ('\t', '\n', '\v', '\f', '\r', ' ')
states: (before, inside, after)


setState(c) {
  if before and (c != newline and c not in whitespace) then set inside
  if inside then (if c in whitespace then set after else if c = newline then set before)
  if after and c = newline then set before
}


doAction(c) {
  if before and (c != newline and c not in whitespace) then write(c)
  if inside and c not in whitespace then write(c)
  if after and c = newline then write(c)
}


cycle {
  set before

  loop until (c: readCharacter) = EOL {
    setState(c)
    doAction(c)
  }
}

Adskillelsen af ​​rutiner, der udtrykker cyklusprogression på den ene side, og faktisk handling på den anden (matchende input og output) tillader klarere og enklere kode.

Begivenheder

Inden for automatisering afhænger trin fra trin til trin af inputdata, der kommer fra selve maskinen. Dette repræsenteres i programmet ved at læse tegn fra en tekst. I virkeligheden informerer disse data om position, hastighed, temperatur osv. For kritiske elementer i en maskine.

Ligesom ved GUI -programmering kan ændringer i maskintilstanden således betragtes som hændelser, der forårsager passage fra en tilstand til en anden, indtil den sidste er nået. Kombinationen af ​​mulige tilstande kan generere en lang række begivenheder og dermed definere en mere kompleks produktionscyklus. Som en konsekvens er cyklusser normalt langt fra simple lineære sekvenser. Der er sædvanligvis parallelle grene, der kører sammen og alternativer valgt efter forskellige begivenheder, skematisk vist nedenfor: 

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

Ansøgninger

Automatabaseret programmering bruges meget i leksikale og syntaktiske analyser .

Udover det er tankegang i form af automatik (det vil sige at nedbryde udførelsesprocessen til automatiktrin og overføre information fra trin til trin gennem den eksplicitte automatstatus ) nødvendig for hændelsesdrevet programmering som det eneste alternativ til at bruge parallelle processer eller tråde .

Forestillinger om stater og statsmaskiner bruges ofte inden for formel specifikation . For eksempel bruger UML -baseret softwarearkitekturudvikling tilstandsdiagrammer til at specificere programmets adfærd. Også forskellige kommunikationsprotokoller er ofte specificeret ved hjælp af den eksplicitte statsopfattelse (f.eks. RFC  793 ).

Tænkning i form af automatik (trin og tilstande) kan også bruges til at beskrive semantik i nogle programmeringssprog . Eksempelvis beskrives udførelsen af ​​et program skrevet på Refal- sproget som en sekvens af trin i en såkaldt abstrakt Refal-maskine; maskinens tilstand er en visning (et vilkårligt Refal -udtryk uden variabler).

Fortsættelser i ordningssproget kræver tænkning i trin og tilstande, selvom selve ordningen på ingen måde er automatiseret (det er rekursivt). For at gøre det muligt for call/cc -funktionen at fungere, skal implementeringen være i stand til at fange en hel tilstand af det udførende program, hvilket kun er muligt, når der ikke er nogen implicit del i staten. En sådan fanget tilstand er det, der kaldes fortsættelse , og den kan betragtes som tilstanden for en (relativt kompliceret) automat. Automatontrinnet udleder den næste fortsættelse fra det foregående, og udførelsesprocessen er cyklussen af ​​sådanne trin.

Alexander Ollongren forklarer i sin bog den såkaldte Wien-metode til programmering af sprogs semantikbeskrivelse, der er fuldt ud baseret på formelle automater.

STAT-systemet [1] er et godt eksempel på at bruge den automatbaserede tilgang; dette system omfatter udover andre funktioner et indlejret sprog kaldet STATL, som er rent automatisk-orienteret.

Historie

Automatabaserede teknikker blev brugt bredt i de domæner, hvor der er algoritmer baseret på automatteori, såsom formelle sproganalyser.

Et af de tidlige papirer om dette er af Johnson et al., 1968.

En af de tidligste omtaler af automatbaseret programmering som en generel teknik findes i avisen af Peter Naur , 1963. Forfatteren kalder teknikken for Turing-maskine-tilgang , men der er ikke givet nogen egentlig Turing-maskine i papiret; i stedet beskrives teknikken baseret på trin og tilstande.

Sammenligning med tvingende og proceduremæssig programmering

Begrebet stat tilhører ikke automatbaseret programmering. Generelt vises tilstand (eller programtilstand ) under udførelsen af ​​et computerprogram som en kombination af alle oplysninger, der kan ændre sig under udførelsen. For eksempel består en tilstand af et traditionelt imperativprogram af

  • værdier for alle variabler og de oplysninger, der er gemt i dynamisk hukommelse;
  • værdier gemt i registre;
  • stak indhold (inklusive lokale variabels værdier og returadresser);
  • den aktuelle værdi af instruktionsmarkøren .

Disse kan opdeles i den eksplicitte del (f.eks. Værdier gemt i variabler) og den implicitte del (returadresser og instruktionsmarkøren).

Når dette er sagt, kan et automatbaseret program betragtes som et specielt tilfælde af et bydende program, hvor implicit del af staten minimeres. Tilstanden for hele programmet taget på de to forskellige øjeblikke ved indtastning af trinkodesektionen kan kun variere i automatiktilstanden. Dette forenkler analysen af ​​programmet.

Objektorienteret programmeringsforhold

I teorien om objektorienteret programmering siges et objekt at have en intern tilstand og er i stand til at modtage beskeder , svare på dem, sende meddelelser til andre objekter og ændre dets interne tilstand under beskedhåndtering. I mere praktisk terminologi betragtes det at kalde et objekts metode som det samme som at sende en besked til objektet .

På den ene side kan objekter fra objektorienteret programmering betragtes som automater (eller modeller af automater), hvis tilstand er kombinationen af ​​private felter, og en eller flere metoder anses for at være trin . Sådanne metoder må hverken direkte eller indirekte kalde hinanden eller sig selv, ellers kan objektet ikke betragtes som implementeret på en automatbaseret måde.

På den anden side er objektet godt til at implementere en model af en automat. Når den automatbaserede tilgang bruges inden for et objektorienteret sprog, implementeres en automatmodel normalt af en klasse, staten er repræsenteret med private felter i klassen, og trinnet implementeres som en metode; en sådan metode er normalt den eneste ikke-konstante offentlige metode i klassen (udover konstruktører og destruktorer). Andre offentlige metoder kan forespørge staten, men ændrer den ikke. Alle de sekundære metoder (f.eks. Særlige statsbehandlere) er normalt skjult i den private del af klassen.

Se også

Referencer

  1. ^ a b Aho, Alfred V .; Ullman, Jeffrey D. (1973). Teorien om analyse, oversættelse og kompilering . 1 . Englewood Cliffs, NJ: Prentice-Hall. ISBN  0-13-914564-8.
  2. ^ Ollongren, Alexander (1974). Definition af programmeringssprog ved fortolkning af automater . London: Academic Press. ISBN 0-12-525750-3.
  3. ^ Johnson, WL; Porter, JH; Ackley, SI; Ross, DT (1968). "Automatisk generering af effektive leksikale processorer ved hjælp af finite state -teknikker". Comm. ACM . 11 (12): 805–813. doi : 10.1145/364175.364185 . S2CID 17253809 .  
  4. ^ Naur, Peter (september 1963). "Designet af GIER ALGOL -kompilatoren Del II". BIT Numerisk matematik . 3 (3): 145–166. doi : 10.1007/BF01939983 . S2CID 189785656 .  
  5. ^ "Automatisk baseret programmering" (PDF) . Videnskabelig og teknisk tidsskrift for informationsteknologi, mekanik og optik (53). 2008.

eksterne links