Nachdem sie sich nun klar gemacht haben sollten wie man Forth startet und wie man es wieder beendet, ist es an der Zeit, dass zwei Dinge passieren: Zum einen soll hier erklärt werden, was denn der Stack ist und zum Zweiten sollten sie ab hier anfangen parallel zum Lesen dieses Textes ein Forth laufen zu lassen, um alles, was hier erklärt wird sofort ausprobieren zu können. Es ist generell eine gute Idee alles mal auszuprobieren, vielleicht auch über das hinaus, was hier beschrieben ist. So erhalten sie eine gute Vorstellung davon, was Forth ist und wie es arbeitet.
Ein Stack ist zunächst mal nichts anderes als ein Stapel; genauer genommen ist 'Stack' das englische Wort für das deutsche Wort 'Stapel'. Und dieser Stapel ist ein Stapel auf dem Sachen abgelegt werden. Der vermutlich weitverbreitetste Stapel dürfte der Tellerstapel sein und er gibt ein sehr gutes Bild davon ab, was in Forth unter Stapel zu verstehen ist.
Genau genommen gibt es in Forth nicht den Stapel oder Stack, sondern gleich mehrere. Der erste, mit dem man üblicherweise in Berührung kommt ist der Zahlenstack und nur von dem soll hier in diesem Kapitel die Rede sein. Tja, und wie der Name schon sagt, werden auf diesem Zahlenstack eben Zahlen und nicht Teller abgelegt, wie auf dem Tellerstapel.
Trotzdem gibt es einige Gemeinsamkeiten. Vor allem, dass man immer nur an das oberste Element, Zahl oder Teller, dran kommt. Es sind zwar einige Klimmzüge möglich, auch an das heran zu kommen, was nicht gerade ganz oben liegt, aber in der Regel ist eben nur das oberste Element erreichbar. Die zweite Gemeinsamkeit liegt darin, dass die Wichtigkeit eines Tellerstapels für ein Restaurant adäquat ist zur Wichtigkeit des Zahlenstapels für Forth. Der Zahlenstapel ist das wichtigste Instrument für Forth, um mit Zahlen umgehen zu können. Daher soll hier ein bisschen gezeigt werden, wie der Stack arbeitet. Es kommt noch ein Kapitel, in dem gezeigt wird, was man mit dem Stack noch so alles anstellen kann, aber hier werden erst mal nur die Grundkenntisse vermittelt.
Zwei wichtige Worte sind nötig, um die folgenden Erklärungen
verstehen und bestenfalls auch selber durchführen zu können. Das
erste Wort ist das Wort ., also ein einfacher
Punkt. Dieses Wort von Forth nimmt den obersten Wert vom Stack und
gibt ihn auf dem Bildschirm aus. In der Praxis sieht das
folgendermaßen aus:
Zuerst mal muss man ein paar Zahlen auf dem Stack ablegen. Das ist sehr einfach, man muss die Zahlen nur der Reihe nach eingeben und danach dann die Return-Taste betätigen. Machen wir mal:
1 ok 2 ok 3 ok
Aus technischer Sicht hätte man auch einfach eingeben können:
1 2 3 ok
Nun liegen die drei Zahlen '1', '2' und '3' auf dem Stack und zwar
zuunterst die '1', da sie als erste eingegeben wurde, darüber die
'2' und dann die '3'. Gibt man nun das oben vorgestellte Wort
. ein, dann wird die oberste Zahl, die '3', ausgegeben.
Außerdem wird sie dazu vom Stack genommen, und es sind dann nur noch
die Zahlen '1' und '2' auf dem Stack:
. 3 ok
Will man auch sie ausgeben und so wieder vom Stack verschwinden
lassen, dann braucht man nur nochmal das .-Wort zu
verwenden, her gleich zweimal hintereinander.
. . 2 1 ok
Man sieht, dass als erstes die '2' ausgegeben wurde, denn nachdem die '3' vom Stapel weggenommen wurde, lag sie ja an oberster Stelle und danach erst die '1'. Was passiert, wenn man nun noch mehr Zahlen vom Stack nehmen will? Probieren sie es aus, bei mir sieht da folgendermaßen aus:
. :1: Stack underflow
Da keine Zahl mehr auf dem Stack lag, gibt Forth eine Fehlermeldung aus. Bei ihnen kann die anders aussehen, aber auf jeden Fall werden sie eine Fehlermeldung erhalten und sei es nur, dass Forth nicht mit ok antwortet, wie sie es sonst schon gewohnt sein sollten.
Ein weiteres wichtiges Wort, den man zum Rumprobieren brauchen
kann, ist .S, leider ist er nicht bei allen
Forth-Systemen verfügbar. Wenn es ihn gibt, dann ist er hervorragend
geeignet um mit dem Zahlenstack zu experimentieren, denn er gibt
einfach den gesamten Inhalt des Zahlenstacks aus ohne ihn zu
verändern! Damit ist es möglich sich den Stack zu jedem
Zeitpunkt anzusehen. Das wird vor allem wichtig, wenn wir zu den
Wörtern kommen, mit denen man den Stack manipulieren kann. Hier
aber erst mal ein kleines Beispiel für dieses wichtige Wort:
1 2 3 ok .S <3> 1 2 3
Wie man sieht gibt das Wort zuerst (in spitzen Klammern) aus, wieviele Elemente auf dem Stack liegen, danach folgen dann alle Elemente und das auch noch in der 'richtigen' Reihenfolge. Ich denke, dass ich ihnen nicht erklären muss, wie wichtig dieses Wort sein kann. Nebenbei hat er noch eine weitere nette Eigenschaft: Er führt nicht zu einem Fehler, wenn der Stack leer ist. Das folgende Beispiel zeigt es:
.S <0> ok
Es wird einfach ausgegeben, dass der Stack keine Elemente enthält und das war es.
Mit UPN wird die Umgekehrte Polnische Notation bezeichnet. Diese orientiert sich an einer Notation, die von dem polnischen Mathematiker Jan Łukasiewicz in den 1920er Jahren erdacht worden ist. Bevor ich ins Detail gehen will, möchte ich ihnen zeigen, dass es damit eigentlich nichts besonderes auf sich hat.
Stellen sie sich vor, sie wollen jemandem eine Additionsaufgabe stellen; für dieses Beispiel sollen einfach mal die beiden Zahlen 2 und 3 addiert werden. Sie können die Aufgabe auf drei verschiedene Arten stellen:
Sie werden mir sicher zustimmen, dass alle drei Aufgabenstellungen das Gleiche bedeuten und dass sicherlich auch die meisten Menschen diese Aufgabenstellung verstehen werden. Bei genauerer Betrachtung ergibt sich allerdings eine Besonderheit: In allen drei Fällen gibt es einen Operator, die Summe oder Addition und zwei Operanden, die beiden Zahlen, die addiert werden sollen. Im ersten Fall ist allerdings die Reihenfolge:
Operator Operand1 Operand2 ('+' '2' '3')
Im zweiten Fall steht der Operator zwischen den Operanden, also eher
Operand1 Operator Operand2 ('2' '+' '3')
Tja, und im dritten Fall wird der Operator erst hinter den Operanden genannt:
Operand1 Operand2 Operator ('2' '3' '+')
Mathematisch gesehen spricht man von einer Präfix-Notation, wenn der Operator zuerst genannt wird, von einer Infix-Notation, wenn er zwischen den Operanden steht und von einer Postfix-Notation, wenn er erst nach den Operanden genannt wird. Wie ich oben schon gezeigt habe, ist das alles kein Problem, solange man die Aufgabe sprachlich stellt. Etwas anders sieht es allerdings aus, wenn man das ganze als 'Rechenaufgabe' im mathematischen Stil schreiben will, wie ich es oben in Klammern geschrieben habe.
Beim zweiten Beispiel fehlt eigentlich nur noch das Gleichheitszeichen, bis wir es als 'normale' mathematische Aufgabe erkennen, wohingegen die erste und die dritte Variante ungewöhnlich erscheinen, aber gerade die sind es, die polnische Notation (Präfix) oder umgekehrte polinische Notation (Postfix) genannt werden.
Es sollte nun klar sein, dass Forth eine Postfix-Notation verwendet. Im Kapitel über die Arithmetik mit Forth werde ich noch mehr darüber erklären. Hier soll allerdings noch die Erklärung folgen, was das Ganze denn soll. Wir sind es von Kindesbeinen an gewöhnt in der Infix-Notaion zu schreiben und zu rechnen. Wieso brauchen die Mathematiker (nicht Forth!) denn noch die beiden anderen Notationen?
Der Grund ist sehr einfach! Łukasiewicz hat die Präfixnotation erfunden, weil es damit möglich ist jeden mathematischen Ausdruck ohne Klammern zu schreiben. Es stellt ein nicht unerhebliches Problem dar, dass die Reihenfolge der Operatoren in der Mathematik durch Regeln vorgegeben ist, die man lernen muss (Wer erinnert sich nicht an die Regel: "Punktrechung geht vor Strichrechnung!")
Bei der Punkt- und der Strichrechnung mag das ja noch angehen, aber schon bei der Unterscheidung von
-24 und (-2)4
haben viele Menschen Probleme (beim ersten ergibt sich als Wert '-16' und beim zweite '16'). Noch interessanter wird das Ganze, wenn man einen Computer programmieren will. Gerade in den Anfängen des Computerzeitalters gab es Computer, welche die Vorrangregeln für Berechnungen nicht beherrschten, da wurde dann mal schnell aus:
2 + 5 * 3 = 21 (und nicht 17, wie die Punkt- vor Strichregel besagt)
Auch vor diesem Hintergrund ist es sinnvoll eine Schreibweise zu verwenden, bei der es nicht zu solchen Zweifelsfällen kommen kann und das ist dann eben die Präfix-Notation, oder die Postfix-Notation, die sich in dieser Hinsicht nicht unterscheiden. Die letzte Rechnung würde in Präfix-Notation folgendermßen geschrieben:
+ * 5 3 2
Sie besagt, dass der Multiplikationsoperator ('*') sich auf die unmittelbar folgenden Zahlen '5' und '3' bezieht. Der Additionsoperator ('+') bezieht sich dann auf das Ergebnis der Multiplikation und die '2'.
Auch in Postfix-Notation ist das natürlich möglich:
2 5 3 * +
Hier bezieht sich das '*' auf die unmittelbar davor stehenden '5' und die '3'. Das '+' dann auf die '2' und das sich ergebende Ergebnis der Multiplikation.
Soweit, so gut! Wie siht die Sache nun aber aus, wenn man in der Infix-Notation Klammern braucht, also zum Beispiel bei:
(2 + 5) * 3
Nun, in Postfix-Notation sieht das Ganze einfach folgendermaßen aus:
3 2 5 + *
Überlegen sie sich ruhig selber mal, dass das Ergebnis nun auch wieder stimmt (jetzt kommt wirklich 21 raus). Denken sie nur daran, dass ein Operator sich immer auf die beiden davor stehenden Zahlen bezieht.
Forth arbeitet (im Wesentlichen aus technischen Gründen) mit der UPN, also einer Postfix-Notation. Im Kapitel über Arithmetik werde ich noch genauer darauf eingehen.