Kann ein objektorientiertes Programm als endliche Zustandsmaschine angesehen werden?

Dies mag eine philosophische / grundlegende Frage sein, aber ich möchte sie nur klarstellen.

Nach meinem Verständnis ist eine Zustandsmaschine eine Methode zur Modellierung eines Systems, bei der die Ausgabe des Systems nicht nur von den aktuellen Eingaben abhängt, sondern auch vom aktuellen Zustand des Systems. Außerdem kann eine Zustandsmaschine, wie der Name schon sagt, mit ihrem jeweiligen Zustand und Verhalten in eine endliche Anzahl von N Zuständen unterteilt werden.

Wenn dies korrekt ist, sollte dann nicht jedes einzelne Objekt mit Daten- und Funktionselementen ein Zustand in unserem objektorientierten Modell sein, wodurch jedes objektorientierte Design zu einer endlichen Zustandsmaschine wird?

Wenn dies nicht die Interpretation eines FSM im Objektdesign ist, was genau meinen die Leute, wenn sie einen FSM in Software implementieren? Vermisse ich etwas?

Vielen Dank

Jedes Single-Thread-Programm, das auf einer Maschine mit einer begrenzten Menge an Speicher ausgeführt wird, kann als Finite-State-Maschine modelliert werden. Ein bestimmter Zustand in der Zustandsmaschine repräsentiert die spezifischen Werte aller relevanten Speicher - lokale Variablen, globale Variablen, Heapspeicher, Daten, die derzeit im virtuellen Speicher ausgelagert sind, sogar den Inhalt der relevanten Dateien. Mit anderen Worten, es wird viele Zustände in diesem Finite-State-Modell geben, selbst für ganz einfache Programme.

Selbst wenn der einzige Status, den Ihr Programm hat, eine einzelne globale Variable eines 32-Bit-Integer-Typs ist, impliziert dies mindestens 2 ^ 32 (mehr als 4 Milliarden) Status. Und das ohne Berücksichtigung des Programmzählers und des Aufrufstapels.

Ein Push-Down-Automatenmodell ist für solche Dinge realistischer. Es ist wie ein endlicher Automat, hat aber ein eingebautes Konzept eines Stapels. Es ist jedoch nicht wirklich ein Aufrufstapel wie in den meisten Programmiersprachen.

Es gibt eine Wikipedia-Erklärung , aber lassen Sie sich im Abschnitt über formale Definitionen nicht stören.

Push-Down-Automaten werden zur Modellierung allgemeiner Berechnungen verwendet. Turing-Maschinen sind ähnlich , aber IIRC nicht identisch - obwohl ihre Rechenfähigkeiten gleichwertig sind .

Vielen Dank an Kevin Cline, der auf den obigen Fehler hingewiesen hat. Wie Wikipedia ebenfalls betont , sind Push-Down-Automaten leistungsfähiger als Automaten mit endlichen Zuständen, aber weniger leistungsfähig als Turing-Maschinen.

Ich weiß ehrlich gesagt nicht, woher dieser Hirnfurz kommt - ich weiß , dass kontextsensitive Grammatiken leistungsfähiger als kontextfreie sind und dass kontextsensitive Grammatiken nicht mit einem einfachen Push-Down-Automaten analysiert werden können. Ich weiß sogar, dass es zwar möglich ist, eine eindeutige kontextfreie Grammatik in linearer Zeit zu analysieren, dies jedoch im Allgemeinen mehr als einen (deterministischen) Push-Down-Automaten erfordert. Also, wie ich am Ende glauben könnte, dass ein Push-Down-Automat einer Turing-Maschine entspricht, ist bizarr.

Vielleicht dachte ich an einen Push-Down-Automaten mit zusätzlichen Maschinen, aber das wäre, als würde man einen endlichen Automaten einem Push-Down-Automaten gleichsetzen (einfach einen Stapel hinzufügen und ausnutzen).

Push-Down-Automaten sind beim Parsen wichtig. Ich kenne sie in diesem Zusammenhang gut genug, habe sie aber nie wirklich als computerwissenschaftliche Rechenmodelle studiert, daher kann ich nicht viel detaillierter angeben, als ich es bereits getan habe.

Es ist möglich, ein einzelnes OOP-Objekt als Zustandsmaschine zu modellieren. Der Zustand der Maschine wird durch die Zustände aller Mitgliedsvariablen bestimmt. Normalerweise würden Sie nur die gültigen Zustände zwischen (nicht während) Methodenaufrufen zählen. Auch hier müssen Sie sich im Allgemeinen über viele Zustände Gedanken machen - es ist etwas, das Sie möglicherweise als theoretisches Modell verwenden, aber Sie möchten nicht alle diese Zustände aufzählen, außer vielleicht in einem trivialen Fall.

Es ist jedoch ziemlich üblich, einige Aspekte des Zustands eines Objekts mit einer Zustandsmaschine zu modellieren . Ein häufiger Fall ist die KI für Spielobjekte.

Dies ist auch die typische Vorgehensweise beim Definieren eines Parsers mit einem Pushdown-Automatenmodell. Obwohl es in einem Zustandsmodell eine endliche Menge von Zuständen gibt, modelliert dies nur einen Teil des Zustands des Parsers - zusätzliche Informationen werden in zusätzlichen Variablen neben diesem Zustand gespeichert. Dies löst zB das 4-Milliarden-Zustände-für-eine-Ganzzahl-Problem - zähle nicht alle diese Zustände auf, sondern beziehe nur die Ganzzahlvariable mit ein. In gewisser Weise ist es immer noch Teil des Push-Down-Automaten-Zustands, aber es ist viel einfacher zu handhaben, als tatsächlich 4 Milliarden Zustandsblasen in einem Diagramm zu zeichnen.

Die Frage ist nicht, ob etwas "ist" oder "ist nicht" eine endliche Zustandsmaschine. Eine Finite-State-Maschine ist ein mentales Modell, das nützlich sein kann, um etwas zu verstehen, wenn man sich das Ding als eins vorstellen kann.

Typischerweise gilt das Finite-State-Machine-Modell für Dinge mit einer geringen Anzahl von Zuständen, wie z. B. eine reguläre Grammatik oder den Befehlssequenzer eines Computers.

Um Ihre Frage direkt zu beantworten: Mit ziemlicher Sicherheit nicht. Es scheint keine formale mathematische Theorie für OOP zu geben, wie Lambda-Kalkül und / oder kombinatorische Logik der funktionalen Programmierung zugrunde liegen oder Turing Machines der normalen alten imperativen Programmierung zugrunde liegen.

Weitere Informationen finden Sie in dieser Frage zum Stapelüberlauf .

Ich vermute, dass das Fehlen einer zugrunde liegenden mathematischen Theorie der Grund dafür ist, dass jeder weiß, was ein "Objekt" ist, wenn er eines sieht, aber niemand "Objekte" sieht, ganz so wie jeder andere.

Nein, praktisch sowieso nicht. Eine Zustandsmaschine merkt sich normalerweise nur ein Datenelement: ihren aktuellen Zustand.

Eine typische Anwendung eines FSM ist das Lexen oder Parsen. Wenn wir zum Beispiel lexen, ist es (normalerweise) ziemlich einfach, die Aktionen für jede mögliche Eingabe in Bezug auf den aktuellen Status und den Wert der Eingabe zu codieren.

Zum Beispiel könnten wir einen NUMBER-Status haben, in dem wir die Ziffern einer Zahl lesen. Wenn das nächste Zeichen, das wir lesen, eine Ziffer ist, bleiben wir im Zustand NUMBER. Wenn es sich um ein Leerzeichen oder einen Tabulator handelt, geben wir die Ziffern zurück und kehren dann zu einem WHITE_SPACE-Status oder etwas in dieser Reihenfolge zurück.

Nun ist es sicherlich wahr, dass in einem typischen FSM (insbesondere einem, der in Software implementiert ist) Teile und Bestandteile vorhanden sind, die technisch nicht ganz in ein FSM passen, das mit dem FSM selbst gemischt ist. Wenn Sie beispielsweise Ziffern einer Zahl lesen, werden Sie häufig die Position der ersten Ziffer speichern. Wenn Sie also am Ende angelangt sind, können Sie den Wert der Zahl leicht berechnen.

Das FSM selbst hat einige Einschränkungen - es hat keinen Zählmechanismus. Stellen Sie sich zum Beispiel eine Sprache vor, die "/ " zum Starten eines Kommentars und " /" zum Beenden eines Kommentars verwendet. Sein Lexer würde wahrscheinlich einen COMMENT-Status haben, den er eingegeben hat, als er ein '/ ' Token sah. Es gibt derzeit keine Möglichkeit (außer dem Hinzufügen eines weiteren Status wie COMMENT2), ein weiteres "/ " zu erkennen und zu erkennen, dass es sich um einen verschachtelten Kommentar handelt. Vielmehr wird im Kommentarzustand erkannt */, dass der Kommentarzustand verlassen werden soll, und bei allen anderen Änderungen wird der Kommentarzustand beibehalten.

Wie bereits erwähnt, werden Sie sicherlich könnten einen KOMMENTAR2 Zustand für einen verschachtelten Kommentar enthalten - und dass ein comment3 Zustand, und so weiter. Irgendwann werden Sie es jedoch satt haben, weitere Status hinzuzufügen, und das bestimmt die maximale Verschachtelungstiefe, die Sie für Kommentare zulassen. Mit einer anderen Form von Parser (dh nicht einer reinen Zustandsmaschine, sondern mit etwas Speicher, der zählt) können Sie einfach Ihre Verschachtelungstiefe direkt verfolgen, sodass Sie im COMMENT-Zustand bleiben, bis Sie ein enges Kommentarzeichen dafür erhalten Gleicht den ersten Wert aus, sodass Ihr Zähler auf 0 zurückgeht und Sie den COMMENT-Status verlassen.

Wie gesagt, wenn Sie einen solchen Zähler hinzufügen, ist das, was Sie haben, nicht mehr wirklich ein FSM. Zur gleichen Zeit, es ist eigentlich ziemlich nah - speziell, nahe genug , dass Sie den Zähler simulieren können nur mehr Zustände hinzufügen.

In einem typischen Fall jedoch, wenn jemand über die Implementierung einer FSM in Software spricht, wird er diese einigermaßen "rein" halten. Insbesondere reagiert die Software auf die aktuelle Eingabe nur basierend auf dem aktuellen Status und dem Wert der Eingabe selbst. Wenn die Reaktion von vielem abhängt, wird sie normalerweise nicht als Zustandsmaschine bezeichnet (zumindest wenn sie wissen, wovon sie sprechen).

Ich glaube nicht, dass die akzeptierte Antwort völlig richtig ist.

Sie können ein beliebiges Programm, das in einer Turing Complete-Sprache geschrieben ist, unabhängig davon, ob es objektorientiert ist oder nicht, nicht als Finite-State-Machine modellieren. Nahezu alle modernen Computersprachen wie Java, C ++ oder Smalltalk sind Turing Complete.

Beispielsweise können Sie keine Zustandsmaschine erstellen, um eine Folge von Objekten zu erkennen, bei denen n Instanzen eines Objekts gefolgt von n Instanzen eines anderen Objekts vorhanden sind, da Zustandsmaschinen nicht in der Lage sind, n in eine Variable zu schreiben. Sie können nur Eingaben lesen und in einen Zustand wechseln.