Programowanie w oparciu o automatykę - Automata-based programming

Programowanie oparte na automatach to paradygmat programowania, w którym program lub jego część jest traktowana jako model maszyny skończonej (FSM) lub dowolnego innego (często bardziej skomplikowanego) automatu formalnego (patrz teoria automatów ). Czasami wprowadzany jest potencjalnie nieskończony zbiór możliwych stanów, a taki zbiór może mieć skomplikowaną strukturę, a nie tylko wyliczenie.

Programowanie oparte na maszynach skończonych jest zasadniczo takie samo, ale formalnie nie obejmuje wszystkich możliwych wariantów, ponieważ FSM oznacza maszynę skończoną, a programowanie oparte na automatach niekoniecznie wykorzystuje FSM w ścisłym tego słowa znaczeniu.

Następujące właściwości są kluczowymi wskaźnikami programowania opartego na automatach:

  • Czas realizacji programu jest wyraźnie rozdzielony na poszczególne kroki automatu . Każdy krok jest faktycznie wykonaniem sekcji kodu (tak samo dla wszystkich kroków), która ma jeden punkt wejścia. Ta sekcja może być podzielona na podsekcje do wykonania w zależności od różnych stanów, chociaż nie jest to konieczne.
  • Jakakolwiek komunikacja między krokami automatu jest możliwa tylko za pośrednictwem wyraźnie zapisanego zestawu zmiennych o nazwie stan automatu . Pomiędzy dowolnymi dwoma krokami program nie może zawierać niejawnych składowych swojego stanu, takich jak wartości zmiennych lokalnych, adresy zwrotne, wskaźnik bieżącej instrukcji itp. To znaczy stan całego programu pobierany w dowolnych dwóch momentach wejścia krok automatu, może różnić się tylko wartościami zmiennych uważanych za stan automatu.

Całe wykonanie kodu opartego na automatach to cykl kroków automatu.

Innym powodem używania pojęcia programowania opartego na automatach jest to, że styl myślenia programisty o programie w tej technice jest bardzo podobny do stylu myślenia używanego do rozwiązywania zadań matematycznych przy użyciu maszyn Turinga , algorytmów Markowa itp.

Przykład

Zadanie

Rozważ zadanie odczytania tekstu ze standardowego wejścia wiersz po wierszu i zapisania pierwszego słowa każdego wiersza na standardowe wyjście . Najpierw pomijamy wszystkie wiodące białe znaki, jeśli takie istnieją. Następnie wypisujemy wszystkie znaki pierwszego słowa. Na koniec pomijamy wszystkie końcowe znaki, aż napotkamy znak nowej linii . Ilekroć zostanie napotkany ciąg znaków nowej linii nie na początku strumienia, wypisujemy tylko pierwszy i pomijamy pozostałe; w przeciwnym razie pomijamy wszystko. Następnie ponownie uruchamiamy proces w następnej linii. Po napotkaniu warunku końca pliku (niezależnie od etapu) zatrzymujemy się.

Program tradycyjny

Tradycyjny program w C, który wykonuje powyższe zadanie, mógłby wyglądać tak:

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

Na przykład kompilacja i uruchomienie powyższego programu na tym wejściu:

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

plony:

foo
qux

Program oparty na automatach

Proceduralny

To samo zadanie można rozwiązać, myśląc w kategoriach maszyn skończonych . Zauważ, że parsowanie linii składa się z trzech etapów: pomijanie wiodących białych znaków, drukowanie znaków pierwszego słowa i pomijanie znaków końcowych. Nazwijmy te stany automatu BEFORE, INSIDEi AFTER. Wersja programu oparta na automatach mogłaby wyglądać tak:

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

Chociaż program wygląda teraz dłużej, ma co najmniej jedną istotną zaletę: jest tylko jednagetchar instrukcja odczytu (czyli wywołania funkcji). Poza tym jest tylko jedna pętla zamiast czterech, które miała tradycyjna wersja. Ciało whilepętli to krok automatu, a sama pętla to cykl kroku automatu. Program implementuje pracę maszyny skończonej przedstawionej na diagramie stanów.

Najważniejszą właściwością programu jest to, że sekcja kodu kroku automatu jest wyraźnie zlokalizowana. Dzięki wyraźnej funkcji stepdla kroku automatyzacji program lepiej demonstruje tę właściwość:

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

Program teraz wyraźnie demonstruje podstawowe właściwości kodu opartego na automatach:

  • okresy czasu wykonywania kroków automatu nie mogą się pokrywać;
  • jedyną informacją przekazaną z poprzedniego kroku do następnego jest jawnie określony stan automatu .

Automat skończony można zdefiniować za pomocą tablicy stanów przejść, której wiersze oznaczają stany bieżące, kolumny stany wejściowe, a komórki kolejne stany i akcje do wykonania.

Tabela stanów przejściowych
Wejście
Stan obecny
Nowa linia Biała przestrzeń inny
przed przed przed wewnątrz/nadruk
wewnątrz przed/drukuj po wewnątrz/nadruk
po przed/drukuj po po
Diagram stanu
Diagram stanów automatu skończonego stanu, która drukuje pierwsze słowo każdej linii strumienia wejściowego. Maszyna wykonuje dokładnie jedno przejście na każdym kroku, w zależności od aktualnego stanu i napotkanego znaku. Akcja towarzysząca przejściu jest albo brakiem operacji, albo wydrukowaniem napotkanego znaku, co oznacza print .

Ogólnie rzecz biorąc, program oparty na automatach może naturalnie korzystać z tego podejścia. W przypadku jawnej dwuwymiarowej tablicy transitionsdla tablicy stanów przejść program wykorzystuje następujące podejście:

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

Zorientowany obiektowo

Jeśli język implementacji obsługuje programowanie obiektowe , prostą refaktoryzacją programu jest enkapsulacja automatu w obiekt, ukrywając w ten sposób szczegóły jego implementacji. Program w C++ używający stylu obiektowego mógłby wyglądać tak:

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

Notatka. - W celu zminimalizowania zmian, które nie są bezpośrednio związane z przedmiotem artykułu, wejścia / wyjścia getchar i putcharfunkcji ze standardowej biblioteki C są używane.

Wzornictwo stan jest sposobem na obiekt, aby zmienić jego zachowanie w czasie wykonywania w zależności od jego stanu wewnętrznego bez uciekania się do dużych instrukcji warunkowych lub Lookups stół dzięki wywołań funkcji wirtualnych. Jego główną zaletą w porównaniu z kodem używającym dużych instrukcji warunkowych jest to, że kod specyficzny dla stanu jest rozproszony w różnych obiektach, a nie zlokalizowany w bloku monolitycznym, co poprawia łatwość konserwacji. Jego główne zalety w stosunku do kodu korzystającego z tabel przejść stanów polegają na tym, że wywołania funkcji wirtualnych są często bardziej wydajne niż wyszukiwania w tabelach, że kryteria przejścia między stanami są bardziej wyraźne niż w formacie tabelarycznym oraz że łatwiej jest dodawać akcje towarzyszące przejściom stanów. Wprowadza jednak nowy problem: liczba klas sprawia, że ​​kod jest mniej zwarty niż inne podejścia. Program korzystający z wzorca projektowego state mógłby wyglądać tak:

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

Automatyzacja i automaty

Programowanie oparte na automatyce rzeczywiście ściśle odpowiada potrzebom programistycznym występującym w dziedzinie automatyzacji .

Cykl produkcyjny jest powszechnie modelowany jako:

  • sekwencja etapów krok po kroku zgodnie z danymi wejściowymi (od porywaczy);
  • zestaw czynności wykonywanych w zależności od aktualnego etapu.

Różne dedykowane języki programowania pozwalają na wyrażenie takiego modelu w mniej lub bardziej wyrafinowany sposób.

Program automatyzacji

Przedstawiony powyżej przykład mógłby być wyrażony zgodnie z tym widokiem jak w poniższym pseudokodzie ('set' aktywuje zmienną logiczną, 'reset' dezaktywuje zmienną logiczną, ':' przypisuje zmienną, a '=' testuje równość) :

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

Oddzielenie procedur wyrażających postęp cyklu z jednej strony i rzeczywiste działanie z drugiej (dopasowanie wejścia i wyjścia) pozwala na jaśniejszy i prostszy kod.

Wydarzenia

W dziedzinie automatyzacji przechodzenie od kroku do kroku zależy od danych wejściowych pochodzących z samej maszyny. W programie jest to reprezentowane przez odczytywanie znaków z tekstu. W rzeczywistości dane te informują o położeniu, prędkości, temperaturze itp. krytycznych elementów maszyny.

Podobnie jak w programowaniu GUI , zmiany stanu maszyny można zatem uznać za zdarzenia powodujące przejście ze stanu do innego, aż do osiągnięcia ostatniego stanu. Kombinacja możliwych stanów może generować różnorodne zdarzenia, definiując w ten sposób bardziej złożony cykl produkcyjny. W konsekwencji cykle są zwykle dalekie od prostych ciągów liniowych. Zwykle istnieją równoległe gałęzie biegnące razem i alternatywy wybrane zgodnie z różnymi zdarzeniami, schematycznie przedstawione poniżej:

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

Aplikacje

Programowanie oparte na automatach jest szeroko stosowane w analizach leksykalnych i składniowych .

Poza tym myślenie w kategoriach automatów (tj. rozbicie procesu wykonywania na kroki automatu i przekazywanie informacji od kroku do kroku przez jawny stan automatu ) jest niezbędne w programowaniu sterowanym zdarzeniami jako jedyna alternatywa dla używania równoległych procesów lub wątków .

Pojęcia stanów i maszyn stanowych są często używane w dziedzinie specyfikacji formalnej . Na przykład rozwój architektury oprogramowania opartej na UML wykorzystuje diagramy stanów do określenia zachowania programu. Również różne protokoły komunikacyjne są często określane przy użyciu jawnego pojęcia stanu (np. RFC  793 ).

Myślenie w kategoriach automatów (kroków i stanów) można również wykorzystać do opisu semantyki niektórych języków programowania . Na przykład wykonanie programu napisanego w języku Refal jest opisane jako sekwencja kroków tak zwanej abstrakcyjnej maszyny Refal; stan maszyny to widok (dowolne wyrażenie Refal bez zmiennych).

Kontynuacje w języku Scheme wymagają myślenia w kategoriach kroków i stanów, chociaż sam Scheme nie jest w żaden sposób związany z automatami (jest rekurencyjny). Aby umożliwić działanie funkcji call/cc , implementacja musi być w stanie przechwycić cały stan programu wykonującego, co jest możliwe tylko wtedy, gdy w stanie nie ma niejawnej części. Taki stan złapany to właśnie kontynuacja i można go uznać za stan (stosunkowo skomplikowanego) automatu. Krok automatu to odejmowanie kolejnej kontynuacji od poprzedniej, a proces wykonania to cykl takich kroków.

Alexander Ollongren w swojej książce wyjaśnia tzw. wiedeńską metodę opisu semantyki języków programowania, która jest w pełni oparta na automatach formalnych.

System STAT [1] jest dobrym przykładem zastosowania podejścia opartego na automatach; system ten, oprócz innych funkcji, zawiera wbudowany język o nazwie STATL, który jest zorientowany wyłącznie na automatykę.

Historia

Techniki oparte na automatach były szeroko stosowane w dziedzinach, w których istnieją algorytmy oparte na teorii automatów, takich jak analizy języka formalnego.

Jedną z pierwszych prac na ten temat jest Johnson i in., 1968.

Jedna z najwcześniejszych wzmianek o programowaniu opartym na automatach jako ogólnej technice znajduje się w artykule Petera Naura , 1963. Autor nazywa technikę podejściem maszyny Turinga , jednak w artykule nie podano prawdziwej maszyny Turinga ; zamiast tego opisana jest technika oparta na krokach i stanach.

Porównanie z programowaniem imperatywnym i proceduralnym

Pojęcie stanu nie jest wyłączną własnością programowania opartego na automatach. Ogólnie rzecz biorąc, stan (lub stan programu ) pojawia się podczas wykonywania dowolnego programu komputerowego , jako połączenie wszystkich informacji, które mogą ulec zmianie podczas wykonywania. Na przykład stan tradycyjnego programu imperatywnego składa się z:

  • wartości wszystkich zmiennych i informacje przechowywane w pamięci dynamicznej;
  • wartości przechowywane w rejestrach;
  • zawartość stosu (w tym wartości i adresy zwrotne zmiennych lokalnych );
  • aktualna wartość wskaźnika instrukcji .

Można je podzielić na część jawną (taką jak wartości przechowywane w zmiennych) i część niejawną (adresy zwrotne i wskaźnik instrukcji).

Powiedziawszy to, program oparty na automatach można uznać za szczególny przypadek programu imperatywnego, w którym niejawna część stanu jest zminimalizowana. Stan całego programu w dwóch różnych momentach wprowadzania sekcji kodu kroku może się różnić tylko w stanie automatu. Upraszcza to analizę programu.

Relacja programowania obiektowego

W teorii programowania obiektowego mówi się , że obiekt ma stan wewnętrzny i jest zdolny do odbierania wiadomości , odpowiadania na nie, wysyłania wiadomości do innych obiektów i zmiany swojego stanu wewnętrznego podczas obsługi wiadomości. W bardziej praktycznej terminologii wywołanie metody obiektu jest traktowane tak samo, jak wysłanie komunikatu do obiektu .

Zatem z jednej strony obiekty z programowania obiektowego można uznać za automaty (lub modele automatów), których stanem jest kombinacja pól prywatnych, a jedną lub więcej metod uważa się za krok . Takie metody nie mogą wywoływać siebie nawzajem ani siebie, ani bezpośrednio, ani pośrednio, w przeciwnym razie obiekt nie może zostać uznany za zaimplementowany w sposób oparty na automatach.

Z drugiej strony obiekt jest dobry do implementacji modelu automatu. Gdy podejście oparte na automatach jest używane w języku obiektowym, model automatu jest zwykle implementowany przez klasę, stan jest reprezentowany przez prywatne pola klasy, a krok jest implementowany jako metoda; taka metoda jest zwykle jedyną niestałą publiczną metodą klasy (poza konstruktorami i destruktorami). Inne metody publiczne mogą wysyłać zapytania do stanu, ale nie zmieniają go. Wszystkie metody drugorzędne (takie jak poszczególne procedury obsługi stanu) są zwykle ukryte w prywatnej części klasy.

Zobacz też

Bibliografia

  1. ^ a b Aho, Alfred V .; Ullman, Jeffrey D. (1973). Teoria parsowania, tłumaczenia i kompilacji . 1 . Englewood Cliffs, NJ: Prentice-Hall. Numer ISBN  0-13-914564-8.
  2. ^ Ollongren Aleksander (1974). Definicja języków programowania poprzez interpretację automatów . Londyn: prasa akademicka. Numer ISBN 0-12-525750-3.
  3. ^ Johnsona, WL; Porter, JH; Ackley, SI; Ross, DT (1968). „Automatyczne generowanie wydajnych procesorów leksykalnych z wykorzystaniem technik skończonych”. Komunikat ACM . 11 (12): 805-813. doi : 10.1145/364175.364185 . S2CID 17253809 .  
  4. ^ Naur, Peter (wrzesień 1963). „Projekt kompilatora GIER ALGOL Część II”. Matematyka numeryczna BIT . 3 (3): 145–166. doi : 10.1007/BF01939983 . S2CID 189785656 .  
  5. ^ „Programowanie oparte na automatach” (PDF) . Czasopismo Naukowo-Techniczne Technologii Informacyjnych, Mechaniki i Optyki (53). 2008.

Zewnętrzne linki