Stack-orientiertes Programmieren

Stack-orientiertes Programmieren, ist ein Programmierparadigma das stützt sich auf a Stapelmaschine Modell für das Bestehen Parameter. Stapelorientierte Sprachen arbeiten mit einem oder mehreren Stapeljedes davon kann einen anderen Zweck erfüllen. Programmierkonstrukte in anderen Programmiersprachen müssen für die Verwendung in einem stapelorientierten System geändert werden.[1] Einige stapelorientierte Sprachen arbeiten in Postfix oder Polnische Notation umgekehrt. Alle Argumente oder Parameter für einen Befehl werden angegeben Vor dieser Befehl. Zum Beispiel würde die Postfix -Notation geschrieben werden 2, 3, multiplizieren Sie Anstatt von multiplizieren, 2, 3 (Präfix oder Polnische Notation), oder 2 Multiplizieren 3 (Infix Notation). Die Programmiersprachen Weiter, Rpl, PostScript, Bibtex Stildesignsprache[2] und viele Assemblersprachen Passen Sie dieses Paradigma an.

Stapelbasierte Algorithmen berücksichtigen Daten, indem sie ein Daten von Daten aus dem Stapel verwenden und Daten wieder auf dem Stapel zurückgeben. Die Notwendigkeit von Stapelmanipulationsoperatoren ermöglichen den Stapel zu manipulieren Daten. Um die Auswirkung einer Aussage hervorzuheben, wird ein Kommentar verwendet, der die Oberseite des Stapels vor und nach der Erklärung zeigt. Dies ist als Stapel -Effekt -Diagramm bekannt.

PostScript Stapel Betrachten Sie separate Stapel für zusätzliche Zwecke. Dies berücksichtigt Variablen, Wörterbücher, Verfahren, Anatomie einiger typischer Verfahren, Kontrolle und Durchfluss. Die Analyse der Sprachmodell Ermöglicht, Ausdrücke und Programme einfach und theoretisch zu interpretieren.

Stackbasierte Algorithmen

PostScript ist ein Beispiel für eine nach Postfix-Stack-basierte Sprache. Ein Ausdrucksbeispiel in dieser Sprache ist 2 3 Mul. Die Berechnung des Ausdrucks beinhaltet das Verständnis, wie Stapelorientierung funktioniert.

Stapelorientierung kann als folgende Analogie für Förderbande dargestellt werden. am Ende eines Förderbandes (der Eingang), markierte Platten 2, 3, und Mul werden nacheinander platziert. Die Platte am Ende des Förderers (2) kann genommen werden, aber andere Platten können nicht zugegriffen werden, bis die Platte am Ende entfernt ist. Die Platten können nur in einem Stapel gespeichert werden und nur auf dem Stapel hinzugefügt oder entfernt werden, nicht von der Mitte oder dem Boden. Blindplatten (und ein Marker) können geliefert und Platten dauerhaft verworfen werden.

Human stack.svg

Teller nehmen 2 und legen Sie es auf den Stapel, dann nehmen Sie die Platte 3 und leg es auf den Stapel. Als nächstes nehmen Sie die Mul Teller. Dies ist eine Anweisung zum Ausführen. Nehmen Sie dann die beiden Top -Platten vom Stapel, multiplizieren Sie ihre Etiketten (2 und 3) und schreiben das Ergebnis (6) auf einem neuen Teller. Die beiden alten Teller wegwerfen (2 und 3) und der Teller Mulund legen Sie den neuen Teller auf den Stapel. Ohne mehr Platten auf dem Förderer, das Ergebnis der Berechnung (6) wird auf der Platte auf dem Stapel angezeigt.

Dies ist eine sehr einfache Berechnung. Was ist, wenn eine komplexere Berechnung erforderlich ist, z. B. (2 + 3) × 11 + 1? Wenn es zum ersten Mal in Postfix -Form geschrieben ist, heißt es, 2 3 Fügen Sie 11 Mul 1 hinzuDie Berechnung kann genau auf die gleiche Weise durchgeführt werden und das richtige Ergebnis erzielen. Die Schritte der Berechnung sind in der folgenden Tabelle angezeigt. Jede Spalte zeigt ein Eingangselement (die Platte am Ende des Förderers) und den Inhalt des Stapels nach der Verarbeitung dieses Eingangs.

Eingang 2 3 hinzufügen 11 Mul 1 hinzufügen
Stapel 2 3
2
5 11
5
55 1
55
56

Nach der Verarbeitung der gesamten Eingabe enthält der Stapel 56, was ist die Antwort.

Daraus kann Folgendes abgeschlossen werden: Eine stapelbasierte Programmiersprache hat nur einen Weg, um Daten zu behandeln, indem ein Datenstück auf dem Stapel auf dem Stapel genannt wird PopPing und Daten wieder auf den Stapel einsetzen, bezeichnet drückening. Jeder Ausdruck, der geschrieben werden kann konventionelloder in einer anderen Programmiersprache kann in Postfix- (oder Präfix-) Form geschrieben werden und somit für eine stapelorientierte Sprache zugänglich sein.

Stapelmanipulation

Da der Stapel das Hauptmittel ist, um Daten in einer stapelorientierten Sprache zu manipulieren, bieten solche Sprachen häufig eine Art Stapelmanipulationsoperatoren. Häufig bereitgestellt DUP, um das Element auf dem Stapel zu duplizieren, Börsen (oder Tauschen), um Elemente auf dem Stapel auszutauschen (der erste wird zweiter und der zweite wird zuerst), rollen, zu zyklisch permute Elemente im Stapel oder im Teil des Stapels, Pop (oder fallen), um das Element auf dem Stapel zu verwerfen (Push ist implizit) und andere. Diese werden zu Schlüssel für die Studienverfahren.

Stackeffektdiagramme

Als Hilfe zum Verständnis der Auswirkung der Aussage wird ein kurzer Kommentar verwendet, der die Oberseite des Stapels vor und nach der Erklärung zeigt. Die Oberseite des Stapels ist rechts am weitesten, wenn mehrere Elemente vorhanden sind. Diese Notation wird üblicherweise in der vierten Sprache verwendet, wo Kommentare in Klammern eingeschlossen sind.

( vorher Nachher ) 

Zum Beispiel werden die grundlegenden Forth -Stack -Operatoren beschrieben:

DUP  (a - a a) fallen ( a -- ) Tauschen (a b - b a) Über (a b - a b a) verrotten  (a b c - b c a) 

Und die Flunkerei Funktion unten ist beschrieben:

Flunkerei  (n - n ') 

Es entspricht zu Voraussetzungen und Postconditions in Hoare Logik. Beide Kommentare können auch als bezeichnet werden als Behauptungen, nicht unbedingt im Kontext von Stack-basierten Sprachen.

PostScript -Stapel

PostScript und einige andere Stapelsprachen haben andere separate Stapel für andere Zwecke.

Variablen und Wörterbücher

Die Bewertung verschiedener Ausdrücke wurde bereits analysiert. Die Implementierung von Variablen ist für jede Programmiersprache wichtig, aber für stapelorientierte Sprachen ist es von besonderem Anliegen, da es nur eine Möglichkeit gibt, mit Daten zu interagieren.

Die Art und Weise, wie Variablen in stapelorientierten Sprachen wie Postscript implementiert werden Wörterbücher von Schlüssel -Wert -Paare. Um eine Variable zu erstellen, muss zuerst ein Schlüssel (der variable Name) erstellt werden, mit dem ein Wert zugeordnet ist. In PostScript wird ein Namensdatenobjekt mit a vorangestellt /, Also /x ist ein Namensdatenobjekt, das beispielsweise die Nummer zugeordnet werden kann 42. Das definieren Befehl ist def, Also

/x 42 def

Mitarbeiter mit dem Namen x mit der Nummer 42 im Wörterbuch auf dem Stapel. Ein Unterschied besteht zwischen /x und x - Ersteres ist ein Datenobjekt, das einen Namen darstellt. x steht für das, was unter definiert ist unter /x.

Verfahren

Ein Verfahren in einer stapelbasierten Programmiersprache wird als eigenständiges Datenobjekt behandelt. In PostScript werden Verfahren zwischen den Kennzeichen bezeichnet { und }.

Zum Beispiel in PostScript -Syntax,

{DUP mul}

stellt eine anonyme Prozedur dar, um das zu duplizieren, was sich oben am Stapel befindet, und dann das Ergebnis zu multiplizieren - ein Quadratverfahren.

Da Verfahren als einfache Datenobjekte behandelt werden, können Namen mit Verfahren definiert werden. Wenn sie abgerufen werden, werden sie direkt ausgeführt.

Wörterbücher bieten ein Mittel zur Kontrolle des Scops sowie zur Speicherung von Definitionen.

Da Datenobjekte im obersten Wörterbuch gespeichert werden, entsteht natürlich eine unerwartete Fähigkeit: Wenn eine Definition aus einem Wörterbuch nachgeschlagen wird, wird das oberste Wörterbuch überprüft, dann im nächsten usw. Wenn ein Verfahren definiert ist, das den gleichen Namen hat wie ein anderer, der bereits in einem anderen Wörterbuch definiert ist, wird der lokale aufgerufen.

Anatomie einiger typischer Verfahren

Verfahren nehmen häufig Argumente an. Sie werden durch das Verfahren auf eine sehr spezifische Weise behandelt, unterscheidet sich von der anderer Programmiersprachen.

A. Fibonacci -Nummer Programm in PostScript:

  /Flunkerei  {  DUP DUP 1 Gl Börsen 0 Gl oder nicht  {  DUP 1 Sub Flunkerei  Börsen 2 Sub Flunkerei  hinzufügen  } wenn  } def 

Eine rekursive Definition wird am Stapel verwendet. Die Fibonacci -Nummer -Funktion nimmt ein Argument an. Erstens wird es getestet, 1 oder 0 zu sein.

Die Zersetzung der wichtigsten Schritte des Programms, die den Stapel widerspiegeln, unter der Berechnung der Berechnung von Fib (4):

                Stack: 4 Dup -Stack: 4 4 Dup -Stack: 4 4 4 1 EQ -Stack: 4 4 FALSE BEAR -Stack: 4 Falsch 4 0 EQ Stack: 4 Falsch falsch oder Stack: 4 Falsch nicht Stack: 4 True True

Da der Ausdruck true bewertet wird, wird das innere Verfahren bewertet.

                Stack: 4 Dup -Stack: 4 4 1 Substapel: 4 3 Fib
(rekursiver Anruf hier)
                Stack: 4 f (3) Börsenstack: F (3) 4 2 Substapel: F (3) 2 Fib
(rekursiver Anruf hier)
                Stack: F (3) F (2) Stapel hinzufügen: f (3)+f (2)

Welches ist das erwartete Ergebnis.

In dieser Prozedur werden keine benannten Variablen verwendet, rein den Stapel. Benannte Variablen können mit der Verwendung der Verwendung erstellt werden /ein Börsen defin konstruieren. Zum Beispiel, {/n austausch def n n mul}

ist ein Quadrat mit einer benannten Variablen n. Vorausgesetzt, dass /sq {/n theaud def n n mul} Def und 3 sq wird genannt, das Verfahren sq wird auf folgende Weise analysiert:

               Stack: 3 /n Börse Stack: /n 3 Def Stack: leer (Es wurde definiert) n Stack: 3 n Stack: 3 3 Mul Stack: 9

Welches ist das erwartete Ergebnis.

Kontrolle und Fluss

Da es anonyme Verfahren gibt, kann die Durchflussregelung auf natürliche Weise auftreten. Für eine sind drei Datenstücke erforderlich If-then-else Aussage: Eine Bedingung, ein Verfahren, das durchgeführt werden muss, wenn die Bedingung wahr ist, und eine zu tun, wenn die Bedingung falsch ist. Zum Beispiel in PostScript,

 2 3 gt { (2 ist größer als drei) = } { (2 ist nicht größer als drei) = } ansonsten 

führt das nahezu äquivalent in c durch:

 wenn (2 > 3) { printf("2 ist größer als drei\n"); } anders { printf("2 ist nicht größer als drei\n"); } 

Looping und andere Konstrukte sind ähnlich.

Analyse des Sprachmodells

Das einfache Modell, das in einer stapelorientierten Sprache bereitgestellt wird Syntaxanalyse muss nur gemacht werden, nur lexikalische Analyse. Die Art und Weise, wie solche Programme geschrieben werden, ermöglicht es, von Maschinen interpretiert zu werden, weshalb Postscript -Drucker für die Verwendung gut geeignet sind. Die leicht künstliche Methode zum Schreiben von Postscript-Programmen kann jedoch ein erstes Hindernis für das Verständnis stapelorientierter Sprachen wie PostScript bilden.

Während die Fähigkeit zu beschatten durch überschreiben Eingebaute und andere Definitionen können Programme schwer zu debuggen machen, und die unverantwortliche Verwendung dieser Funktion kann ein unvorhersehbares Verhalten verursachen, es kann einige Funktionen erheblich vereinfachen. Zum Beispiel bei der Verwendung von Postscript die Verwendung Showpage Der Bediener kann mit einem benutzerdefinierten, der einen bestimmten Stil auf die Seite anwendet, anstatt einen benutzerdefinierten Operator zu definieren oder Code zu wiederholen, um den Stil zu generieren.

Siehe auch

Verweise

  1. ^ Luerweg, T. (2015). Stackbasierte Programmierparadigmen. Konzepte von Programmiersprachen - Copl'15, 33.
  2. ^ Oren Patashnik, Entwerfen von Bibtex -Stilen (PDF)[Dead Link]