Automatenbasierte Programmierung - Automata-based programming

Automatenbasierte Programmierung ist ein Programmierparadigma, bei dem das Programm oder ein Teil davon als Modell eines endlichen Automaten (FSM) oder eines anderen (oft komplizierteren) formalen Automaten gedacht wird (siehe Automatentheorie ). Manchmal wird eine potenziell unendliche Menge möglicher Zustände eingeführt, und eine solche Menge kann eine komplizierte Struktur haben, nicht nur eine Aufzählung.

Finite-State-Machine-basierte Programmierung ist im Allgemeinen gleich, deckt aber formal nicht alle möglichen Varianten ab, da FSM für Finite-State-Machine steht und Automaten-basierte Programmierung nicht unbedingt FSMs im engeren Sinne verwendet.

Die folgenden Eigenschaften sind Schlüsselindikatoren für die automatenbasierte Programmierung:

  • Der Zeitraum der Programmausführung ist bis auf die Automatenschritte klar getrennt . Jeder Schritt ist effektiv eine Ausführung eines Codeabschnitts (der für alle Schritte gleich ist), der einen einzigen Einstiegspunkt hat. Dieser Abschnitt kann in Abhängigkeit von verschiedenen Zuständen in Unterabschnitte unterteilt werden, die ausgeführt werden müssen, obwohl dies nicht erforderlich ist.
  • Jegliche Kommunikation zwischen den Automatenschritten ist nur über den explizit angegebenen Variablensatz namens Automatenzustand möglich . Zwischen zwei beliebigen Schritten darf das Programm keine impliziten Komponenten seines Zustands haben, wie z. B. die Werte lokaler Variablen, Rückkehradressen, der aktuelle Befehlszeiger usw. Das heißt, der Zustand des gesamten Programms, der zu zwei beliebigen Zeitpunkten der Eingabe eines genommen wird Automatenschritt, können sich nur in den Werten der Variablen unterscheiden, die als Automatenzustand betrachtet werden.

Die gesamte Ausführung des auf Automaten basierenden Codes ist ein Zyklus der Automatenschritte.

Ein weiterer Grund für die Verwendung des Konzepts der automatenbasierten Programmierung besteht darin, dass der Denkstil des Programmierers über das Programm bei dieser Technik dem Denkstil sehr ähnlich ist, der verwendet wird, um mathematische Aufgaben mit Turing-Maschinen , Markov-Algorithmen usw. zu lösen .

Beispiel

Aufgabe

Stellen Sie sich die Aufgabe vor, einen Text aus der Standardeingabe zeilenweise zu lesen und das erste Wort jeder Zeile in die Standardausgabe zu schreiben . Zuerst überspringen wir alle führenden Leerzeichen , falls vorhanden. Dann drucken wir alle Zeichen des ersten Wortes. Schließlich überspringen wir alle nachfolgenden Zeichen, bis ein Zeilenumbruchzeichen gefunden wird. Immer wenn eine Folge von Zeilenumbruchzeichen nicht am Anfang des Streams angetroffen wird, drucken wir nur das erste und überspringen die restlichen; sonst überspringen wir alles. Als nächstes starten wir den Prozess in der folgenden Zeile neu. Wenn die End-of-File- Bedingung (unabhängig von der Phase) auftritt, stoppen wir.

Traditionelles Programm

Ein traditionelles Programm in C , das die obige Aufgabe ausführt, könnte so aussehen:

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

Zum Beispiel Kompilieren und Ausführen des obigen Programms für diese Eingabe:

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

ergibt:

foo
qux

Automatenbasiertes Programm

Verfahrensweise

Die gleiche Aufgabe lässt sich lösen, indem man in endlichen Automaten denkt . Beachten Sie, dass das Parsen einer Zeile drei Phasen umfasst: Überspringen der führenden Leerzeichen, Drucken der Zeichen des ersten Wortes und Überspringen der nachfolgenden Zeichen. Nennen wir diese Automatenzustände BEFORE, INSIDEund AFTER. Eine auf Automaten basierende Version des Programms könnte so aussehen:

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

Obwohl das Programm jetzt länger aussieht, hat es zumindest einen wesentlichen Vorteil: Es gibt nur eine Lese- (dh Aufruf der getcharFunktion) Anweisung. Außerdem gibt es nur eine Schleife anstelle der vier, die die traditionelle Version hatte. Der Körper der whileSchleife ist der Automatenschritt und die Schleife selbst ist der Zyklus des Automatenschritts. Das Programm implementiert die Arbeit eines endlichen Automaten, der im Zustandsdiagramm dargestellt ist.

Die wichtigste Eigenschaft des Programms ist, dass der Codeabschnitt des Automatenschritts eindeutig lokalisiert ist. Mit einer expliziten Funktion stepfür den Automatisierungsschritt demonstriert das Programm diese Eigenschaft besser:

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

Das Programm demonstriert nun anschaulich die grundlegenden Eigenschaften von Automaten-basiertem Code:

  • Zeiträume der Ausführung von Automatenschritten dürfen sich nicht überschneiden;
  • die einzige Information, die vom vorherigen Schritt zum nächsten weitergegeben wird, ist der explizit angegebene Automatenzustand .

Ein endlicher Automat kann durch eine Zustandsübergangstabelle definiert werden, deren Zeilen für die aktuellen Zustände, Spalten für die Eingaben und Zellen für die nächsten auszuführenden Zustände und Aktionen stehen.

Zustandsübergangstabelle
Eingang
Aktuellen Zustand
Neue Zeile Leerzeichen Sonstiges
Vor Vor Vor innen/druck
Innerhalb vorher/drucken nach innen/druck
nach vorher/drucken nach nach
Zustandsdiagramm
Das Zustandsdiagramm eines endlichen Automaten, der das erste Wort jeder Zeile eines Eingabestroms druckt. Die Maschine folgt bei jedem Schritt genau einer Transition, abhängig vom aktuellen Zustand und dem angetroffenen Zeichen. Die einen Übergang begleitende Aktion ist entweder eine Nicht-Operation oder das Drucken des angetroffenen Zeichens, das mit print bezeichnet wird .

Im Allgemeinen kann ein auf Automaten basierendes Programm diesen Ansatz natürlich verwenden. Bei einem expliziten zweidimensionalen Array transitionsfür die Zustandsübergangstabelle verwendet das Programm diesen Ansatz:

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

Objektorientierten

Wenn die Implementierungssprache objektorientierte Programmierung unterstützt , besteht eine einfache Umgestaltung des Programms darin, den Automaten in ein Objekt zu kapseln und so seine Implementierungsdetails zu verbergen. Das Programm in C++ im objektorientierten Stil könnte so aussehen:

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

Notiz. — Um Änderungen zu minimieren, die nicht direkt mit dem Thema des Artikels zusammenhängen, werden die Ein-/Ausgabe getchar und putcharFunktionen aus der Standardbibliothek von C verwendet.

Das Zustandsentwurfsmuster ist eine Möglichkeit für ein Objekt, sein Verhalten zur Laufzeit entsprechend seinem internen Zustand zu ändern, ohne auf große bedingte Anweisungen oder Tabellensuchen dank virtueller Funktionsaufrufe zurückgreifen zu müssen . Sein Hauptvorteil gegenüber Code, der große bedingte Anweisungen verwendet, besteht darin, dass zustandsspezifischer Code auf verschiedene Objekte verteilt und nicht in einem monolithischen Block lokalisiert ist, was die Wartbarkeit verbessert. Seine Hauptvorteile gegenüber Code, der Zustandsübergangstabellen verwendet, sind, dass virtuelle Funktionsaufrufe oft effizienter sind als Tabellensuchvorgänge, dass Zustandsübergangskriterien expliziter sind als im Tabellenformat und dass es einfacher ist, Aktionen hinzuzufügen, die Zustandsübergänge begleiten. Es bringt jedoch ein neues Problem mit sich: Die Anzahl der Klassen macht den Code weniger kompakt als die anderen Ansätze. Das Programm, das das State-Design-Pattern verwendet, könnte so aussehen:

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

Automatisierung und Automaten

Die auf Automaten basierende Programmierung entspricht in der Tat sehr gut den Programmieranforderungen im Bereich der Automatisierung .

Ein Produktionszyklus wird üblicherweise wie folgt modelliert:

  • eine Abfolge von Stufen, die gemäß Eingabedaten (von Eroberern) stufenweise ablaufen;
  • eine Reihe von Aktionen, die abhängig von der aktuellen Phase ausgeführt werden.

Verschiedene dedizierte Programmiersprachen ermöglichen es, ein solches Modell auf mehr oder weniger anspruchsvolle Weise auszudrücken.

Automatisierungsprogramm

Das oben dargestellte Beispiel könnte nach dieser Ansicht wie in folgendem Pseudocode ausgedrückt werden ('set' aktiviert eine logische Variable, 'reset' deaktiviert eine logische Variable, ':' weist eine Variable zu und '=' prüft auf Gleichheit) :

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

Die Trennung von Routinen, die den Zyklusverlauf auf der einen Seite ausdrücken, und der tatsächlichen Aktion auf der anderen (die Eingabe und Ausgabe übereinstimmen) ermöglicht einen klareren und einfacheren Code.

Veranstaltungen

Im Bereich der Automatisierung hängt der Schritt von Schritt zu Schritt von Eingabedaten ab, die von der Maschine selbst stammen. Dies wird im Programm durch das Lesen von Zeichen aus einem Text dargestellt. In Wirklichkeit informieren diese Daten über Position, Geschwindigkeit, Temperatur usw. kritischer Elemente einer Maschine.

Wie bei der GUI- Programmierung können Änderungen des Maschinenzustands somit als Ereignisse betrachtet werden, die den Übergang von einem Zustand in einen anderen bewirken, bis der endgültige Zustand erreicht ist. Die Kombination möglicher Zustände kann eine Vielzahl von Ereignissen erzeugen und so einen komplexeren Produktionszyklus definieren. Folglich sind Zyklen in der Regel weit davon entfernt, einfache lineare Folgen zu sein. Üblicherweise laufen parallele Zweige zusammen und es werden Alternativen nach verschiedenen Ereignissen ausgewählt, die unten schematisch dargestellt sind:

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

Anwendungen

Automatenbasierte Programmierung wird häufig in lexikalischen und syntaktischen Analysen verwendet .

Außerdem ist für die ereignisgesteuerte Programmierung als einzige Alternative zu parallelen Prozessen oder Threads das Denken in Automaten (d. h. das Zerlegen des Ausführungsprozesses auf Automatenschritte und das Weitergeben von Informationen von Schritt zu Schritt durch den expliziten Automatenzustand ) notwendig .

Die Begriffe Zustände und Zustandsautomaten werden häufig im Bereich der formalen Spezifikation verwendet . Beispielsweise verwendet die UML- basierte Softwarearchitekturentwicklung Zustandsdiagramme , um das Verhalten des Programms zu spezifizieren. Auch verschiedene Kommunikationsprotokolle werden oft unter Verwendung des expliziten Zustandsbegriffs spezifiziert (zB RFC  793 ).

Das Denken in Automaten (Schritte und Zustände) kann auch verwendet werden, um die Semantik einiger Programmiersprachen zu beschreiben . Beispielsweise wird die Ausführung eines in der Sprache Refal geschriebenen Programms als eine Abfolge von Schritten einer sogenannten abstrakten Refal-Maschine beschrieben; der Zustand der Maschine ist eine Ansicht (ein beliebiger Refal-Ausdruck ohne Variablen).

Fortsetzungen in der Scheme- Sprache erfordern ein Denken in Schritten und Zuständen, obwohl Scheme selbst in keiner Weise automatenbezogen ist (es ist rekursiv). Damit das Call/cc- Merkmal funktioniert, muss die Implementierung in der Lage sein, einen ganzen Zustand des ausführenden Programms abzufangen, was nur möglich ist, wenn es keinen impliziten Teil des Zustands gibt. Ein solcher gefangener Zustand wird als Fortsetzung bezeichnet und kann als Zustand eines (relativ komplizierten) Automaten betrachtet werden. Der Automatenschritt leitet die nächste Fortsetzung aus der vorherigen ab, und der Ausführungsprozess ist der Zyklus solcher Schritte.

Alexander Ollongren erläutert in seinem Buch die sogenannte Wiener Methode der semantischen Beschreibung von Programmiersprachen, die vollständig auf formalen Automaten basiert.

Das STAT-System [1] ist ein gutes Beispiel für die Anwendung des auf Automaten basierenden Ansatzes; dieses System enthält neben anderen Funktionen eine eingebettete Sprache namens STATL, die rein Automatenorientiert ist.

Geschichte

Automatenbasierte Techniken wurden häufig in den Bereichen verwendet, in denen es Algorithmen gibt, die auf der Automatentheorie basieren, wie z. B. formale Sprachanalysen.

Eine der frühen Veröffentlichungen dazu stammt von Johnson et al., 1968.

Eine der frühesten Erwähnungen von Automaten-basierter Programmierung als allgemeine Technik findet sich in dem Artikel von Peter Naur , 1963. Der Autor nennt die Technik Turing-Maschinen-Ansatz , jedoch wird in der Arbeit keine echte Turing-Maschine angegeben; stattdessen wird die auf Schritten und Zuständen basierende Technik beschrieben.

Vergleich mit imperativer und prozeduraler Programmierung

Der Begriff des Zustands ist nicht ausschließliches Eigentum der automatenbasierten Programmierung. Allgemein ausgedrückt erscheint der Zustand (oder Programmzustand ) während der Ausführung eines beliebigen Computerprogramms als eine Kombination aller Informationen, die sich während der Ausführung ändern können. Zum Beispiel besteht ein Zustand eines traditionellen Imperativprogramms aus

  • Werte aller Variablen und der im dynamischen Speicher gespeicherten Informationen;
  • in Registern gespeicherte Werte;
  • Stack-Inhalt (einschließlich lokaler Variablenwerte und Rückkehradressen);
  • aktueller Wert des Befehlszeigers .

Diese lassen sich in den expliziten Teil (zB in Variablen gespeicherte Werte) und den impliziten Teil (Rücksprungadressen und den Befehlszeiger) unterteilen.

Allerdings kann ein auf Automaten basierendes Programm als Sonderfall eines imperativen Programms betrachtet werden, bei dem der implizite Teil des Zustands minimiert wird. Der Zustand des gesamten Programms, der zu den zwei unterschiedlichen Zeitpunkten des Eintritts in den Schrittcodeabschnitt eingenommen wird, kann sich nur im Automatenzustand unterscheiden. Dies vereinfacht die Analyse des Programms.

Objektorientierte Programmierbeziehung

In der Theorie der objektorientierten Programmierung sagt man, dass ein Objekt einen internen Zustand hat und in der Lage ist, Nachrichten zu empfangen , darauf zu antworten , Nachrichten an andere Objekte zu senden und seinen internen Zustand während der Nachrichtenbehandlung zu ändern. In der praktischen Terminologie wird der Aufruf einer Objektmethode als das Senden einer Nachricht an das Objekt angesehen .

So können einerseits Objekte aus der objektorientierten Programmierung als Automaten (oder Modelle von Automaten) betrachtet werden, deren Zustand die Kombination privater Felder ist, und als Schritt werden eine oder mehrere Methoden angesehen . Solche Methoden dürfen sich weder gegenseitig noch sich selbst aufrufen, weder direkt noch indirekt, da sonst das Objekt nicht als automatbasiert implementiert angesehen werden kann.

Auf der anderen Seite eignet sich Objekt gut zum Implementieren eines Modells eines Automaten. Wenn der auf Automaten basierende Ansatz innerhalb einer objektorientierten Sprache verwendet wird, wird normalerweise ein Automatenmodell durch eine Klasse implementiert, der Zustand wird durch private Felder der Klasse dargestellt und der Schritt wird als Methode implementiert; eine solche Methode ist normalerweise die einzige nicht konstante öffentliche Methode der Klasse (neben Konstruktoren und Destruktoren). Andere öffentliche Methoden könnten den Status abfragen, aber nicht ändern. Alle sekundären Methoden (z. B. bestimmte Zustandshandler) sind normalerweise im privaten Teil der Klasse verborgen.

Siehe auch

Verweise

  1. ^ a b Aho, Alfred V.; Ullmann, Jeffrey D. (1973). Die Theorie des Parsens, Übersetzens und Kompilierens . 1 . Englewood Cliffs, NJ: Prentice-Hall. ISBN  0-13-914564-8.
  2. ^ Ollongren, Alexander (1974). Definition von Programmiersprachen durch Interpretieren von Automaten . London: Akademische Presse. ISBN 0-12-525750-3.
  3. ^ Johnson, WL; Porter, JH; Ackley, SI; Ross, DT (1968). „Automatische Generierung effizienter lexikalischer Prozessoren mit endlichen Zustandstechniken“. Komm ACM . 11 (12): 805–813. doi : 10.1145/364175.364185 . S2CID 17253809 .  
  4. ^ Naur, Peter (September 1963). "Das Design des GIER ALGOL Compilers Teil II". BIT Numerische Mathematik . 3 (3): 145–166. doi : 10.1007/BF01939983 . S2CID 189785656 .  
  5. ^ "Automatenbasierte Programmierung" (PDF) . Wissenschaftliche und technische Zeitschrift für Informationstechnologien, Mechanik und Optik (53). 2008.

Externe Links