Automataalapú programozás

Az automataalapú programozás egy olyan programozási paradigma, amelyben a programot vagy annak egy részét egy véges állapotú gép (Finite-State Machine = FSM) vagy más (gyakran bonyolultabb) formális automata modelljeként gondoljuk el (lásd automataelmélet). Néha a lehetséges állapotok potenciálisan végtelen halmazát vezetik be, ami nem csak egy felsorolás, hanem egy ilyen halmaz bonyolult szerkezetű lehet.

A véges állapotú gép alapú programozás általában ugyanez, de formailag nem fedi le az összes lehetséges változatot, mivel az FSM a véges állapotú gépet jelenti, és az automataalapú programozás nem feltétlenül alkalmazza a szoros értelemben vett FSM-et.

A következő tulajdonságok az automatikus programozás kulcsfontosságú mutatói:

• A program végrehajtásának időszaka egyértelműen elkülönül az automata lépésekig. Gyakorlatilag minden lépés egy kódrészlet végrehajtása (minden lépésnél ugyanaz), amely egyetlen belépési ponttal rendelkezik. Ez a szakasz felosztható alszakaszokra, amelyeket a különböző állapotoktól függően kell végrehajtani, bár ez nem szükséges.
• Az automatalépések közötti bármilyen kommunikáció csak az automaták állapotának nevezett, explicit módon feljegyzett változókon keresztül lehetséges. Bármely két lépés között a program állapotának nem lehetnek implicit összetevői, mint például a helyi változók értékei, visszatérési címek, az aktuális utasításmutató stb. Tehát a teljes program állapota, amelyet az automatikus belépés bármely két pillanatában veszünk, csak az automatikusnak tekintett változók értékeiben különbözhet.

Az automataalapú kód teljes végrehajtása az automatikus lépések ciklusának tekinthető.

Az automatikus programozás mellett szól az is, hogy a programozó gondolkodásmódja a programról ebben a technikában nagyon hasonlít ahhoz a gondolkodásmódhoz, amelyet a matematikai feladatok megoldásához használnak a Turing-gépek, Markov-algoritmusok segítségével.

Példa

Feladat

Tekintsük azt a feladatot, hogy soronként beolvasunk egy szöveget egy szabványos bemenetről, majd minden sor első szavát kiírjuk egy szabványos kimenetre. Először kihagyjuk az összes vezető szóköz karaktert, ha van ilyen. Ezután kiírjuk az első szó összes karakterét. Végül kihagyjuk az összes hátralévő karaktert, amíg egy újsor karakterrel nem találkozunk. Amikor egy sor újsoros karakter nem a sor elején található, csak az elsőt írjuk ki, és a többit kihagyjuk, máskülönben az összeset kihagyjuk. Ezután a következő sorban újraindítjuk a folyamatot. A fájl végét jelző feltétel bekövetkezésekor (függetlenül a szakasztól) leállunk.

Hagyományos program

Egy hagyományos C nyelven írt program, amely a fenti feladatot végzi, így nézhetne ki:

#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;
}

Például a fenti program lefordítása és futtatása ezen a bemeneten:

$ 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)

Eredmény

foo
qux

Automataalapú program

Eljárás

Ugyanez a feladat megoldható, ha véges állapotú gépekben gondolkodunk. Vegyük észre, hogy egy sornak az elemzése három szakaszból áll: a vezető szóköz karakterek kihagyása, az első szó karaktereinek kiírása és az utolsó karakterek kihagyása. Nevezzük ezeket az automata állapotokat BEFORE, INSIDE és AFTER állapotoknak. A program automataalapú változata így nézhetne ki:

#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;
}

Bár a program hosszabbnak tűnik, legalább egy jelentős előnye van: csak egy olvasási (azaz a getchar függvény meghívása) utasítás van. Ezen kívül csak egy ciklus van a hagyományos változat négy ciklusa helyett. A while ciklus teste az automatalépés, a ciklus maga pedig az automatalépés ciklusa. A program az állapotdiagramon látható véges állapotú gép működését implementálja. A program legfontosabb tulajdonsága, hogy az automatikus lépés kódrésze egyértelműen lokalizált. Az automatizálási lépés (step) explicit függvénylépéssel a program jobban demonstrálja ezt a tulajdonságot.

#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;
}

A program egyértelműen bemutatja az automataalapú kód alapvető tulajdonságait:

•  a lépések végrehajtási időszakai nem fedhetik egymást
• az egyetlen információ, amely az előző lépésből a következőbe kerül, az explicit módon megadott automata állapot.

Egy véges automatát egy állapot-átmenet táblázattal lehet definiálni, amelynek sorai az aktuális állapotokat, oszlopai a bemeneteket, cellái pedig a következő állapotokat és végrehajtandó műveleteket jelölik.

Állapotátmeneti táblázat

Input Current state	új sor	szóköz	Egyéb
előtte	előtte	előtte	belül / kiír
belül	előtte / kiír	utána	belül / kiír
utána	előtte / kiír	utána	utána

Állapotdiagram

Egy véges állapotú gép állapotdiagramja, amely egy bemeneti adatfolyam minden sorának első szavát kiírja. A gép minden lépésnél pontosan egy átmenetet követ, az aktuális állapottól és a megtalált karaktertől függően. Az átmenetet kísérő művelet vagy egy nem-művelet, vagy a megtalált karakter kiíratása, amit print-el jelölünk.

Általánosságban elmondható, hogy egy automataalapú program természetesen használhatja ezt a megközelítést. Egy explicit kétdimenziós tömb átmenetekkel (transitions) az állapotátmenet-táblázathoz, a program ezt a megközelítést használja:

#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;
}

Objektumorientált

Ha az implementációs nyelv támogatja az objektumorientált programozást, a program egyszerű átalakítása lévén az automatát egy objektumba tárolja, így elrejtve a megvalósítás részleteit. Az objektumorientált stílust használó C++ nyelven a program így nézhetne ki:

#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;
}

Megjegyzés. - A cikk témájához közvetlenül nem kapcsolódó változások minimalizálása érdekében a C szabványos könyvtárából származó getchar és putchar be- és kimeneti függvényeket használjuk. Az állapot tervezési minta egy módja annak, hogy egy objektum futási időben megváltoztassa a viselkedését a belső állapotának megfelelően anélkül, hogy nagy, feltételes utasításokhoz vagy táblázatos keresésekhez folyamodna a virtuális függvényhívásoknak köszönhetően. Fő előnye a feltételes utasításokat használó kóddal szemben az, hogy az állapot-specifikus kód különböző objektumok között oszlik el, nem pedig egy monolitikus blokkban lokalizálódik, ami javítja a karbantarthatóságot. Fő előnyei az állapotátmeneti táblázatokat használó kóddal szemben, hogy a virtuális függvényhívások gyakran hatékonyabbak, mint a táblázatos keresés, az állapotátmeneti kritériumok egyértelműbbek, mint a táblázatos formátumban, és hogy könnyebb az állapotátmeneteket kísérő műveleteket hozzáadni. Ez azonban új problémát vet fel: az osztályok száma miatt a kód kevésbé kompakt, mint a többi megközelítés esetében. Az állapottervezési mintát használó program így nézhet ki:

#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;
}

Automatizálás és automaták

Az automata-alapú programozás valóban szorosan megfelel az automatizálás területén felmerülő programozási igényeknek.

Egy termelési ciklus általában a következőképpen modellezhető:

• bemeneti adatoknak megfelelően lépcsőzetes szakaszok sorozata (fogadóktól kapott adat)
• az aktuális stádiumtól függően végrehajtott műveletek összessége.

Különböző programozási nyelvek lehetővé teszik egy ilyen modell többé-kevésbé kifinomult módon történő kifejezését.

Automatizálási program

A fent bemutatott példa a következő pszeudokód szerint fejezhető ki ('set' egy logikai változót aktivál, 'reset' egy logikai változót inaktivál, ':' egy változót rendel hozzá, és '=' az egyenlőséget teszteli):

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)
  }
}

Az egyik oldalon a ciklus előrehaladását kifejező rutinok szétválasztása a másik oldalon a tényleges cselekvés szétválasztása (a bemenet és a kimenet megfeleltetése) zajlik, ami világosabb és egyszerűbb kódot tesz lehetővé.

Események

Az automatizálás területén a lépésről lépésre történő előrehaladás magától a géptől származó bemeneti adatoktól függ. Ezt a programban egy szövegből történő karakterolvasással reprezentálják. A valóságban ezek az adatok a gép kritikus elemeinek pozíciójáról, sebességéről, hőmérsékletéről tájékoztatnak.

A GUI-programozáshoz hasonlóan a gép állapotában bekövetkező változások olyan eseményeknek tekinthetők, amelyek az egyik állapotból a másik állapotba való átmenetet okozzák, egészen a végső állapot eléréséig. A lehetséges állapotok kombinációja sokféle eseményt generálhat, így egy összetettebb termelési ciklust határozhat meg. Ennek következtében a ciklusok általában egyszerű lineáris sorozatoknak tekinthetők. Egymás mellett általában párhuzamos ágak futnak és a különböző eseményeknek megfelelő alternatívák vannak, amelyeket az alábbiakban sematikusan ábrázolunk:

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

Alkalmazások

Az automataalapú programozást széles körben használják a lexikai és szintaktikai elemzésekben.

Emellett az automatákban való gondolkodás (azaz a végrehajtási folyamat automatalépésekre bontása és az információ lépésről lépésre történő átadása az explicit automaták állapotán keresztül) szükséges az eseményvezérelt programozáshoz, mivel ez az egyetlen alternatívája a párhuzamos folyamatok vagy szálak használatának.

Az állapotok és állapotgépek fogalmát gyakran használják a formális specifikáció területén. Az UML-alapú szoftverarchitektúra-fejlesztés például állapotdiagramokat használ a program viselkedésének meghatározására. A különböző kommunikációs protokollokat is gyakran specifikálják az állapotok explicit fogalmával (pl. RFC 793).

Az automatákban való gondolkodás (lépések és állapotok) egyes programozási nyelvek szemantikájának leírására is használható. Például egy Refal nyelven írt program végrehajtása egy úgynevezett absztrakt Refal automata lépéseinek sorozataként írható le, a gép állapota egy nézet (egy tetszőleges, változók nélküli Refal kifejezés).

A Scheme nyelvben a folytonosságok lépésekben és állapotokban való gondolkodást igényelnek, bár a Scheme maga semmiképpen sem automatizált (rekurzív). Ahhoz, hogy a call/cc funkció működhessen, az implementációnak képesnek kell lennie a végrehajtó program teljes állapotát elkapni, ami csak akkor lehetséges, ha az állapotnak nincs implicit része. Az ilyen elkapott állapot maga az úgynevezett folytatás, és egy (viszonylag bonyolult) automata állapotának tekinthető. Az automata lépése a következő folytatás levezetése az előzőből, a végrehajtási folyamat pedig az ilyen lépések ciklusa.

Alexander Ollongren könyvében ismerteti a programozási nyelvek szemantikai leírásának úgynevezett bécsi módszerét, amely teljes mértékben formális automatákon alapul.

A STAT rendszer [1] jó példa az automatikus megközelítés alkalmazására; ez a rendszer egyéb jellemzői mellett tartalmaz egy beágyazott nyelvet, a STATL, amely tisztán automata-orientált.

Története

Az automata-alapú technikákat széles körben használják azokon a területeken, ahol léteznek automata elméleten alapuló algoritmusok, mint például a formális nyelvi elemzések.

Az egyik korai tanulmány erről a Johnson és társai 1968-as munkája.

Az automataalapú programozás, mint általános technika egyik legkorábbi említése Peter Naur 1963-as tanulmányában található. A szerző Turing-gépes megközelítésnek nevezi a technikát, azonban a tanulmányban nem szerepel valódi Turing-gép, hanem a lépéseken és állapotokon alapuló technikát írja le.

Összehasonlítás az imperatív és procedurális programozással

Az állapot fogalma nem kizárólagos tulajdonsága az automataalapú programozásnak. Általánosságban az állapot (vagy programállapot) bármely számítógépes program végrehajtása során megjelenik, mint a végrehajtás során megváltozható összes információ kombinációja. Például egy hagyományos imperatív program állapota a következőkből áll:

• az összes változó értékei és a dinamikus memóriában tárolt információk;
• a regiszterekben tárolt értékek;
• a verem tartalma (beleértve a helyi változók értékeit és a visszatérési címeket);
• az utasítás mutató aktuális értéke.

Ezek feloszthatók explicit részre (például a változókban tárolt értékek) és implicit részre (visszatérési címek és az utasításmutató).

Egy automataalapú program az imperatív program speciális esetének tekinthető, amelyben az állapot implicit része minimalizálódik. A teljes programnak a kódrészletbe való belépés két különböző pillanatában felvett állapota csak az automata állapotában különbözhet. Ez leegyszerűsíti a program elemzését.

Objektumorientált programozással való kapcsolat

Az objektumorientált programozás elméletében egy objektumról azt mondják, hogy belső állapottal rendelkezik, és képes üzeneteket fogadni, válaszolni rájuk, üzeneteket küldeni más objektumoknak, és az üzenetkezelés során megváltoztatja belső állapotát. Gyakorlatiasabb terminológiában egy objektum metódusának meghívása ugyanannak tekinthető, mint egy üzenet küldése az objektumnak.

Így egyrészt az objektumorientált programozásból származó objektumok tekinthető automatáknak (vagy automata modelleknek), amelyek állapota a privát mezők kombinációja és egy vagy több metódus tekinthető egy lépésnek. Az ilyen metódusok nem hívhatják meg egymást, sem önmagukat, sem közvetlenül, sem közvetve, különben az objektum nem tekinthető automataalapúan implementáltnak.

Másrészről az objektum jó egy automata modelljének megvalósítására. Ha az automataalapú megközelítést egy objektumorientált nyelven belül alkalmazzák, az automata modellt gyakran egy osztály valósítja meg, az állapotot az osztály privát mezőivel reprezentálják, a lépést pedig metódusként valósítják meg. Egy ilyen metódus általában az osztály egyetlen nem konstans nyilvános metódusa (a konstruktorok és destruktorok mellett). Más nyilvános metódusok lekérdezhetik az állapotot, de azt nem változtathatják meg. Az összes másodlagos metódus (például az egyes állapotkezelők) általában az osztály privát részeiben vannak elrejtve.

Fordítás

Ez a szócikk részben vagy egészben az Automata-based programming című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• JV Noble. «Véges állapotú gépek Forthban» - automatákon alapuló programozás a Forth-ban
• Harel (1987). „Statecharts: A Visual Formalism for Complex Systems”. Sci. Comput. Programming 8 (3), 231–274. o. DOI:10.1016/0167-6423(87)90035-9. 
• Harel (1989). „Using Statecharts for Hardware Description and Synthesis”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 8 (7), 798–807. o. DOI:10.1109/43.31537. 
• Polikarpova NI, Shalyto AA Automataalapú programozás SPb .: Piter. 2009 (orosz)
• ITMO Egyetem, "Programozás Technológia" részleg

Kapcsolódó szócikkek

• Sejtautomata
• Állapot programtervezési minta