Kann ein objektorientiertes Programm als endliche Zustandsmaschine angesehen werden?

13

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

Peretz
quelle
6
Computer + Software ist eine Zustandsmaschine, solange Sie Speicher, Speicherplatz und andere Arten von Speicher (wie das Internet) einschränken. Sobald die Verbindung mit dem Internet oder anderer externer Hardware zulässig ist (dies impliziert unbegrenzten Speicherplatz), ähnelt dies eher einer Turing-Maschine. Schon mal was von einem Satz "Turing complete" gehört? Wie dem auch sei, funktionale und obj-orientierte Programme enden beide als Assembler-Code. Ich kenne Haskel (eine reine funktionale Sprache) / Monaden nicht, aber es muss eine interessante Beziehung zwischen dieser und einer Turing-Maschine geben.
Job
Neben dem Punkt Jobs übertrifft jede Form von Nicht-Determinismus auch die Modelle der Zustandsmaschine und der Turing-Maschine. Im Internet gibt es mehrere nicht synchronisierte Computer, Datenverlust durch unvollständige Verbindungen usw. Selbst bei einem einfachen Computer mit einem Kern kann der Benutzer keine deterministischen Eingaben machen, aber normalerweise ignorieren Sie dieses Problem und tun so, als würden alle Daten verloren gehen Die Eingabe war im Voraus bekannt.
Steve314
@ Steve314: Formal sind deterministische Automaten in einem einzigen Zustand. Jeder Eingang führt zu einem neuen Zustand. Bei nicht deterministischen Automaten kann jede Eingabe zu mehreren Zuständen führen. Ein nicht deterministischer Automat mit N Zuständen kann durch einen deterministischen Automaten mit 2 ^ N Zuständen emuliert werden.
Kevin Cline
@cline - In diesem Fall haben Sie vollkommen recht, aber ich denke, ich dachte an die Art von Nebenläufigkeit und zeitlichen Abweichungen, die in einer realen Maschine auftreten - Dinge wie ein Kern, der etwas langsamer läuft, weil er zu heiß ist Dies alles passt natürlich in das nicht deterministische endliche Automatenmodell, das Sie beschreiben, also sind Sie absolut korrekt - aber die Anzahl der Zustände wird wahnsinnig groß sein. Ich schätze, ich hätte kontinuierliche Messungen wie diese Temperaturen auch als Teil des Systemzustands im Auge gehabt (nicht nur als Konsequenzen).
Steve314

Antworten:

16

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.

Steve314
quelle
1
Msgstr "Es ist möglich, ein einzelnes OOP - Objekt als Zustandsmaschine zu modellieren". Richtig, aber schwach. Es ist nicht möglich". Es ist eine Frage der Definition. Die Aufgabe einer Programmiersprache besteht darin, eine FSM in einer ordentlichen Schreibweise auszudrücken. OOP ist eine Implementierung eines FSM mit einer einfacheren Notation für alle verschiedenen Zustände.
S.Lott
1
@ S.Lott - Ja, aber die meisten Leute denken nicht, dass ein OOP-Objekt eine FSM ausdrückt, zumindest nicht die meiste Zeit. Die Verwendung des Namens "Zustandsmaschine" deutet darauf hin, dass Sie eine bestimmte Implementierung verwenden, z. B. das Zustandsentwurfsmuster oder eine Zustands-ID-Mitgliedsvariable. "Modellierung als Zustandsmaschine" impliziert häufig auch etwas über die Spezifikation oder Konstruktionsdokumentation, das sich von der Implementierung dieser Klasse unterscheidet. Das Modellieren einer Klasse als endliches Zustandsmodell bedeutet daher subjektiv etwas anderes als nur das Bereitstellen des Quellcodes für die Klasse.
Steve314
"Leute denken nicht". Wahr. Und ein tiefes Problem. Alle Programme sind Zustandsautomaten. Sie haben viele Staaten. Das erfordert der "Turing Complete" -Test für eine Programmiersprache. Es ist eine sehr, sehr starke (und absolute) Regel. Anstatt vorzuschlagen, dass es "möglich" ist, ist es eher "notwendig" und "ausreichend".
S.Lott
1
-1: Push-Down-Automaten sind NICHT so leistungsstark wie Turing-Maschinen.
Kevin Cline
1
@ Kevin Cline - danke - und was dachte ich !!! Bearbeitet, um das Stück herauszustreichen. Trotz allem, was ich über das formale Studium gesagt habe, weiß ich es besser und hätte es damals besser wissen sollen.
Steve314
5

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.

Mike Dunlavey
quelle
1

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.

Bruce Ediger
quelle
0

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

Jerry Sarg
quelle
"sein aktueller Zustand" kann viele Informationen enthalten. Ein FSM kann trivial zählen, indem er Zustände für jede Zahl hat, die er zählt. Es ist endlich (im Gegensatz zu einer Turing-Maschine), aber es ist immer noch perfekt in der Lage zu zählen. Ich denke, Sie brauchen vielleicht ein besseres Beispiel.
S.Lott
Die Software in Ihrem Handy ist eine Sammlung von schrecklich komplexen Zustandsautomaten, die sich viele Daten merken und sie entsprechend dem aktuellen Zustand interpretieren.
Mawg sagt, Monica am
-2

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.

James Fremen
quelle
dies lediglich Wiederholungen Punkte gemacht und erklärten in Antworten gepostet vor 3 Jahren, zum Beispiel in diesem
gnat