Eine neuere Version dieses Skriptums ist das Gforth-Tutorial (http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/gforth.html#Tutorial, in Englisch, in einem 900KB-HTML-file). Wie verwende ich diese Notizen? Diese Kursnotizen verwenden Sie am besten, indem Sie sich die gegebenen Beispiele ansehen, sich überlegen, was herauskommen sollte, sie dann eingeben. Wenn etwas anderes herausgekommen ist als erwartet, sollten Sie sich überlegen, warum, und eventuell weitere Versuche anstellen, um Ihre Theorie zu überprüfen. Weiters führen sie die gegebenen Übungsbeispiele aus. Wenn Sie mit irgend etwas große Schwierigkeiten haben, wenden Sie sich an mich, am besten per Email. Start von Gforth Gforth starten sie einfach mit gforth und sie sind im interaktiven Modus. Aussteigen koennen Sie mit "bye". Wenn sie zuerst auch noch ein paar Files laden (compilieren und interpretieren) wollen, starten sie es mit gforth file1 file2 Syntax Ein Wort ist eine Sequenz von beliebigen Zeichen (ausser Leerzeichen). Woerter werden durch Leerzeichen voneinander getrennt. Woerter: wort !@#$%^&*() 1234567890 Gforth ignoriert Unterschiede in der Gross/Kleinschreibung, "wort" ist also das gleiche wie "Wort". Crash-Kurs Tippen Sie 0 0 ! here execute ' catch >body 20 erase abort ' (quit) >body 20 erase Die letzten beiden Zeilen zerstoeren Teile von Gforth, sodass man nachher Gforth beenden sollte (was bei der vorletzten Zeile normalerweise von selbst geschieht), wenn noetig mit Ctrl-C oder kill. Nachdem Sie jetzt gelernt hat, wie man einen Crash produziert, wenden wir uns den Moeglichkeiten zu, sinnvolle, crashfreie Programme zu schreiben. Stack Das auffaelligste Merkmal von Forth und Postscript ist der Stack. Wenn man eine Zahl eintippt, wird sie auf den Stack geschoben. Mit ".s" kann man sich den Inhalt des Stacks anschauen. 1 2 3 .s Wie sie sehen, wird der Stack im allgemeinen mit dem obersten Element rechts dargestellt, in der selben Reihenfolge wie bei der Eingabe. Mit . kann man das obserste Stackelement ausdrucken 1 2 3 . . . Übung: Was ist nach "5 6 7 ." auf dem Stack? Arithmetik Die arithmetischen Operatoren +, -, *, / und mod arbeiten immer auf den obersten beiden Stack-elementen (Postfix-Schreibweise): 2 2 + . 2 1 - . 7 3 mod . Die Operanden bei -, / und mod (und auch sonst) sind in der gleichen Reihenfolge wie beim Infix-Ausdruck. Klammern sind ueberfluessig, die Reihenfolge der Ausfuehrung und die Operanden ergeben sich eindeuting durch die Anordnung der Woerter: 3 4 + 5 * . 3 4 5 * + . Übung: Welchen Infix-Ausdrücken entsprechen diese Postfix-Ausdrücke? Schreiben Sie 6-7*8+9 in Postfix-Notation. negate verursacht einen Vorzeichenwechsel: 2 negate . Übung: Schreiben Sie -(-3)*4-5 in Postfix-Notation. /mod vereint / und mod: 7 3 /mod . . Stackmanipulationen 1 .s drop .s 1 .s dup .s drop drop .s 1 2 .s over .s drop drop drop 1 2 .s swap .s drop drop 1 2 3 .s rot .s drop drop drop Das sind die wichtigsten Stackmanipulationswoerter. Es gibt auch noch Varianten, die auf doppelt sovielen Stackelementen arbeiten: 1 2 3 4 .s 2swap .s 2drop 2drop Außerdem noch einige weniger verbreitete Stackmanipulationswörter: 1 2 .s nip .s drop 1 2 .s tuck .s 2drop drop übung: Mit welchen Kombinationen der anderen Stackmanipulationswörter lassen sich nip und tuck ersetzen? Gegeben: Wie bekommt man: 1 2 3 3 2 1 1 2 3 1 2 3 2 1 2 3 1 2 3 3 1 2 3 1 3 3 1 2 3 2 1 3 1 2 3 4 4 3 2 1 1 2 3 1 2 3 1 2 3 1 2 3 4 1 2 3 4 1 2 1 2 3 1 2 3 1 2 3 4 1 2 3 1 3 5 dup * . Übung: Schreiben Sie 17^3 und 17^4 in Forth, wobei Sie 17 nur je einmal hinschreiben. Schreiben Sie ein Forth-Fragment, das auf dem Stack zwei Zahlen erwartet (a und b, b an oberster Stelle), und (a-b)(a+1) ausrechnet. Kommentare \ das ist ein Kommentar ( das auch; Ende: ) .s \ und ( sind normale Forth-Wörter und müssen daher durch Leerzeichen vom folgenden Text getrennt werden: (so funktioniert's nicht) Ich verwende \-Kommentare fuer beschreibenden Text; im Emacs-Forth-mode (gforth.el) wird das auch unterstützt: man kann solche Kommentare absatzweise füllen (M-q). Die (-Kommentare verwende ich für Beschreibungen von Stack-Effekten, von Stack-Inhalten, oder um Wörter auszukommentieren. Definitionen sind das Äquivalent zu Prozeduren in anderen Programmiersprachen: : quadrat ( n -- n^2 ) dup * ; 5 quadrat . 7 quadrat . : startet die Definition, quadrat ist ihr Name. Der darauffolgende Kommentar beschreibt den Stack-Effekt. Die Worte "dup *" werden nicht exekutiert, wie sonst, sondern in die Definition hineincompiliert. ";" beendet die Definition. Das neu definierte Wort kann man genauso verwenden wie ein vordefiniertes, man kann es natuerlich auch in weitere Definitionen einbauen: : zur-dritten ( n -- n^3 ) dup quadrat * ; -5 zur-dritten . : zur-vierten ( n -- n^4 ) quadrat quadrat ; 3 zur-vierten . Übung: Schreiben Sie Definitionen für nip, tuck, negate, und /mod, und überprüfen sie, ob sie funktionieren; lassen Sie sich dabei von "redefined"-Meldungen nicht stören, das sind nur Warnings. Decompiler Definition können mit SEE decompiliert werden see quadrat see zur-dritten Dabei sieht man nur eine Rekonstruktion aus dem ausführbaren Code. Informationen, die im Source-Code vorhanden waren, aber nur zur Übersetzungs-Zeit verwendet werden, und nicht zur Laufzeit, gehen verloren (z.B. Kommentare). Stack-Effekt-Kommentare Der Kommentar hinter dem Namen einer Definition beschreibt den Stack-Effekt: Vor dem -- findet sich der Zustand des Stack vor der Ausführung des Wortes, dahinter der Zustand danach. Es werden nur die obersten Elemente des Stack gezeigt (in unserem Fall das oberste), auf die das Wort zugreift und die es eventuell verändert. Man sollte jeder Definition einen (korrekten) Stack-Effekt verpassen, selbst wenn er so aussieht: ( -- ). Bei komplizierteren Wörtern sollte man auch einen beschreibenden Kommentar dazufügen (ich mache das normalerweise in der Zeile unter dem ":"). Wenn man das nicht tut, wird der Code unleserlich (weil man jede Definition samt all seiner aufgerufenen Definitionen durcharbeiten muß, um es zu verstehen). Bei MPE (Southampton, England) wird man gekündigt, wenn man die Stack-Effekt-Kommentare wegläßt. Übung: Der Stack-Effekt von swap wird üblicherweise mit ( x1 x2 -- x2 x1 ) beschrieben. Beschreiben Sie den Stack-Effekt von -, drop, dup, over, rot, nip, und tuck. Typen Die Elemente des Stack-Effekt-Kommentars geben im Standard (und auch sonst oft) den Typ des Stack-Elements an, und zwar durch ihre Anfangsbuchstaben: n ganze Zahl +n positive ganze Zahl u vorzeichenlose ganze Zahl (entspricht unsigned in C) c Character f Flag (0 oder -1) addr Adresse c-addr character-aligned address a-addr cell-aligned address xt execution token wid Wordlist-ID x eine Zelle, also irgendeiner von den obigen Typen d doppelzellige ganze Zahl (2 Zellen) ud vorzeichenlose doppeltzellige Zahl (2 Zellen) r Gleitkommazahl (am FP-Stack) ...-sys abstrakte Typen undefinierter Größe, tw. undefinierter Stack Eine Zelle entspricht einem Maschinenwort; der etwas ungewöhnliche Name ergibt sich daraus, dass "Wort" schon für etwas anderes verwendet wird. In Forth sind die Wörter nicht überladen (overloading). Ähnliche Operationen für verschiedene Typen haben verschiedene Namen; z.B. heißt die Addition ganzer Zahlen +, und die Addition von Gleitkommazahlen F+. Dabei werden folgende Prefixe verwendet: (keiner) ganze Zahl u vorzeichenlose ganze Zahl c Zeichen (Character), vorzeichenlos d doppelzellige Zahl du,ud vorzeichenlose doppelzellige Zahl 2 zwei Zellen (aber nicht unbedingt als Doppelzellenzahl) m,um gemischt (einzellige und doppelzellige Zahlen) f Gleitkommazahl sf einfachgenaue IEEE-Zahl df doppeltgenaue IEEE-Zahl In Fällen, in denen es keinen Unterschied zwischen vorzeichenbehafteten und vorzeichenlosen Zahlen gibt (z.B. bei "+"), gibt es nur die Variante ohne "u". Forth führt keine Typüberprüfung aus, weder zur Übersetzungszeit, noch zur Laufzeit. Wenn Sie die falsche Operation verwenden, werden die Daten einfach falsch interpretiert. -1 u. -1 1 u< . -1 1 < . Übung: Geben sie Stack-Effekte für die von Ihnen bisher geschriebenen Definitionen. Factoring Bei längeren Definitionen verliert man leicht den Überblick über den Inhalt des Stacks. Gute Forth-Programmierer schreiben daher nur kurze Definitionen (meist weniger als 7 Zeilen). Die Kunst, sinnvolle kurze Definitionen zu finden, heißt Factoring, analog zur Faktorisierung von Polynomen: a^2 + ab - 2b^2 = (a-b)(a+2b) Ein gut faktorisiertes Programm hat weitere Vorteile: Kleinere, allgemeinere Wörter sind leichter zu debuggen, und sie können besser wiederverwendet werden als große spezialisierte Wörter. Wenn Sie also beim Schreiben einer Definition Schwierigkeiten haben, nachzuvollziehen, was am Stack passiert (typischerweise bei mehr als drei Stack-Elementen), versuchen Sie, die Definition in mehrere sinnvolle Fakoren zu teilen. Und wenn dabei Definitionen herauskommen, die selbst nur zwei Wörter enthalten, ist das auch gut. Gutes Factoring ist nicht leicht, und die richtige Lösung fällt auch geübten Forth-Programmierern nicht gleich ein, oft erst beim Überarbeiten eines Programms. Wenn's also nicht gleich klappt, geben Sie nicht auf. Der Stack-Effekt von Definitionen In anderen Sprachen ist die Reihenfolge der Parameter einer Prozedur relative beliebig, und da es nur ein Ergebnis gibt, braucht man sich da auch für keine Reihenfolge entscheiden. In stack-basierten Sprachen spielt die Reihenfolge der Parameter aber eine Rolle und sollte gut überlegt werden. Und zwar sollte man den Stack-Effekt eines Wortes so gestalten, dass die Verwendung des Wortes in den meisten Fällen möglichst einfach ist. Die Implementation des Wortes ist dabei manchmal komplizierter als bei anderen Stack-Effekten. Regeln für die Parameter: Parameter, die meistens nur kurze oder gar keine Berechnung erfordern (weil es z.B. meistens Konstante sind), sollten eher auf der Spitze des Stacks übergeben werden. Hingegen sollten Parameter, die meist eine lange Berechnungskette hinter sich haben, oder die meist als Parameter weitergereicht werden, eher tiefer im Stack sein. Im allgemeinen sollten alle Parameter konsumiert werden. Regeln für die Ergebnisse: Hier sollten dementsprechend Ergebnisse, die meistens rasch konsumiert werden, auf der Spitze des Stacks übergeben werden, und Ergebnisse, die später konsumiert werden (z.B. in langen Berechnungen weiterverwendet werden), sollten tiefer im Stack liegen. Lokale Variablen In einer Definition können Sie lokale Variablen definieren: : swap { a b -- b a } b a ; 1 2 swap .s 2drop Die Definition der lokalen Variablen nimmt in diesem Beispiel zwei Zellen vom Stack und steckt den top-of-stack in b und das zweithöchste Stackelement in a. Alles von -- bis } ist Kommentar. Die lokalen Variablen können über ihren Namen angesprochen werden. Der Teil von -- bis exclusive } kann auch ausgelassen werden: : swap ( x1 x2 -- x2 x1 ) { a b } b a ; In Gforth können Sie lokale Variablen in einer Definition an beliebiger Stelle und beliebig oft definieren. Im Standard dagegen ist nur eine Locals-Definition erlaubt und nur außerhalb von Kontrollstrukturen. Lokale Variablen erlauben es, etwas längere Definitionen zu schreiben, ohne zu faktorisieren. Widerstehen Sie der Versuchung, dann haben Sie mehr von der Lehrveranstaltung (außerdem hat Postscript keine lokalen Variablen). Übung: Schreiben Sie Ihre Definitionen um, sodass sie lokale Variable benützen. Bedingte Ausführung Kontrollstrukturen können in Forth nur in Definitionen verwendet werden. Eine IF-Struktur sieht so aus: : abs ( n1 -- +n2 ) dup 0 < if negate endif ; 5 abs . -5 abs . IF nimmt ein flag vom Stack. Ist es ungleich 0 ("wahr"), wird der folgende Code ausgeführt, ansonsten zum zugehörigen ENDIF (oder ELSE) gesprungen. < vergleicht die beiden obersten Stackelemente und produziert ein Flag: 1 2 < . 2 1 < . 1 1 < . weitere Vergleichswörter sind =, >, <>, <=, >= (nicht alle Kombinationen aus Typen und Vergleichswörtern sind im Standard). Optional kann man auch einen ELSE-Abschnitt verwenden: : min ( n1 n2 -- n ) 2dup < if drop else nip endif ; 2 3 min . 3 2 min . Übung: Schreiben Sie MIN ohne ELSE-Teil (Hinweis: wie sieht die Definition von nip aus?). Flags und logische Operationen Ein true-Flag hat alle bits gesetzt, false keines: hex true u. decimal true . false . Zum Verknüpfen von Flags kann man die Wörter AND, OR, XOR und 0= und INVERT verwenden. Dabei arbeiten AND, OR, XOR, und INVERT bitweise, produzieren also nur aus wohlgeformten flags wieder flags: 1 2 and . 1 2 or . 1 3 xor . 1 invert . 0= dagegen nimmt beliebige Zellen als Eingabe und produziert ein Flag. 1 0= . Um aus einer Zelle ein wohlgeformtes Flag zu machen, verwendet man 0<>: 1 0<> . Die Eingenschaft "alle bits gesetzt" kann man verwenden, um IFs zu vermeiden: : foo ( n1 -- n2 ) 0= if 14 else 0 endif ; 0 foo . 1 foo . : foo ( n1 -- n2 ) 0= 14 and ; 0 foo . 1 foo . Übung: Schreiben Sie MIN ohne IF. Allgemeine Schleifen Die einfachste Schleife ist die Endlosschleife: : endless ( -- ) 0 begin dup . 1+ again ; endless (mit Ctrl-C abbrechen). BEGIN macht nichts (zur Laufzeit), AGAIN springt zurueck zum BEGIN. Eine Schleife mit einer Ausstiegsbedingung an beliebiger Stelle sieht so aus: : log2 ( +n1 -- n2 ) \ logarithmus dualis von n1>0, zum nächsten integer abgerundet assert( dup 0> ) 2/ 0 begin over 0> while 1+ swap 2/ swap repeat nip ; 7 log2 . 8 log2 . WHILE konsumiert ein Flag; ist es gleich 0 (falsch), wird hinter dem REPEAT fortgesetzt. REPEAT springt zurueck zum BEGIN, wie AGAIN. In Forth gibt es viele Abkürzungen (z.B. 1+), 2/ ist aber keine, sondern verschiebt seinen Operanden um ein Bit nach rechts (arithmetic shift right): -5 2 / . -5 2/ . "assert(" ist kein Standard-Wort. Was es macht, sieht man an 0 log2 . Und hier ist eine Schleife mit Ausstieg am Ende: : log2 ( +n1 -- n2 ) \ logarithmus dualis von n1>0, zum nächsten integer abgerundet assert( dup 0 > ) -1 begin 1+ swap 2/ swap over 0 <= until nip ; UNTIL konsumiert ein Flag; ist es wahr (<>0), wird beim BEGIN weitergemacht. Übung: Schreiben Sie eine Definition zur Berechnung des größten gemeinsamen Teilers. Zählschleifen : ^ ( n1 n2 -- n ) \ n = n1 hoch n2 1 swap 0 ?do over * loop nip ; 3 2 ^ . 4 3 ^ . ?DO nimmt zwei Zahlen vom stack ( n1 n2 -- ), und die Schleife zwischen ?DO und LOOP wird dann n1-n2 mal ausgeführt. Auf den Zähler kann man mit I zugreifen: : fac ( n -- n! ) 1 swap 1+ 1 ?do i * loop ; 5 fac . 7 fac . Übung: Schreiben Sie eine Definition zur Berechnung der n-ten Fibonacci-Zahl. Rekursion Der Name einer Definition ist normalerweise während der Definition nicht sichbar, dafür der einer eventuellen Vordefinition: 1 0 / . : / ( n1 n2 -- n ) dup 0= if -10 throw \ melde division by zero endif / \ alte Version ; 1 0 / Für rekursive Definitionen gibt es RECURSIVE (non-standard) oder RECURSE: : fac1 ( n -- n! ) recursive dup 0> if dup 1- fac1 * else drop 1 endif ; 7 fac1 . : fac2 ( n -- n! ) dup 0> if dup 1- recurse * else drop 1 endif ; 8 fac2 . Übung: Schreiben Sie eine rekursive Definition zur Berechnung der Fibonacci-Zahlen. Ausstieg EXIT steigt vorzeitig aus einer Definition aus; für jede Zählschleife, die man dabei verläßt, muß vorher ein UNLOOP ausgeführt werden. Z.B.: : ... ... ?DO ... IF ... UNLOOP EXIT ENDIF ... LOOP ... ; LEAVE steigt vorzeitig aus einer Zählschleife aus. Return-Stack Neben dem normalen Stack (dem Daten-Stack) gibt es in Forth den Return-Stack, der vor allem dazu dient, die Rücksprungadressen bei Definitionsaufrufen zu speichern. Dieser Stack ist auch für Programmierer zugänglich: : foo ( n1 n2 -- ) .s >r .s r@ . >r .s r@ . r> . r@ . r> . ; 1 2 foo >R schiebt also ein Element vom Daten- auf den Return-Stack, R> umgekehrt, und R@ kopiert das oberste Return-Stack-Element auf den Datenstack. Der Returnstack wird dazu verwendet, Daten zwischenzuspeichern, wenn eine alleinige Speicherung auf dem Datenstack zu kompliziert würde (und wenn man keine Faktoren findet und lokale Variablen nicht verwenden kann oder will): : 2swap ( x1 x2 x3 x4 -- x3 x4 x1 x2 ) rot >r rot r> ; Da die Rücksprungadresse und die Schleifenkontrollparameter von Zählschleifen auf dem Returnstack liegen (können), müssen alle Elemente, die in einer Definition bzw. Zählschleife auf den Returnstack geschoben werden, vor dem Ende der Definition bzw. Zählschleifen wieder entfernt werden; Elemente, die außerhalb auf den Return-Stack geschoben wurden, können in der Definition bzw. Zählschleife nicht verwendet werden. Wenn man sich beim Return-Stack verzählt, endet das meistens in einem Crash: : crash ( n -- ) >r ; 5 crash Lokale Variablen und der Return-Stack vertragen sich (laut Standard) auch nicht; da sie einander ersetzen, stört das aber nicht besonders. Übung: Können Sie eine der bisherigen Definitionen leichter schreiben, indem Sie den Return-Stack benutzen? Speicher Mit variable v v . können Sie eine globale Variable v anlegen. v liefert die Adresse einer Zelle im Speicher. Mit ! (store) und @ (fetch) können Sie Werte in den Speicher schreiben und daraus lesen: v . 5 v ! .s v @ . Sie können auch mehr Speicher reservieren, mit create v2 20 cells allot erzeugensie einb Wort v2, das eine Adresse liefert, und reservieren an dieser Adresse Platz für 20 Zellen. Mittels Adressarithmetik können Sie auf einzelne Elemente zugreifen: 3 v2 5 cells + ! Übung: Schreiben Sie eine Definition vsum ( addr u -- n ), das die Summe von u Zellen berechnet, wobei die erste auf addr liegt, die nächste unmittelbar dahinter etc. Mit "," kann man Speicher reservieren und initialisieren: create v3 5 , 4 , 3 , 2 , 1 , v3 @ . v3 cell+ @ . v3 2 cells + @ . Man kann natuerlich auch Speicher reservieren, ohne eine neues Wort zu produzieren: here 10 cells allot .s HERE liefert dabei die Anfangsadresse des Speichers, die man möglichst irgendwo abspeichern sollte, sonst findet man den Bereich nicht wieder. Der mit ALLOT verwaltete Speicher kommt aus dem Dictionary (das auch Wörter speichert) und wird als Stack verwaltet; mit -10 cells allot können die letzten 10 angelegten Zellen wieder freigegeben werden. Alternativ kann man auch eine heap-Verwaltung wie C's malloc verwenden: 10 cells allocate throw .s free throw wobei ALLOCATE den Bereich reserviert und FREE ihn wieder freigibt; die THROWs sind zur Fehlerbehandlung da. Zeichen und Strings Auf dem Stack sind Zeichen Elemente wie alle anderen, im Speicher haben sie aber ihre eigene Größe, und dementsprechend eigene Wörter zum Zugriff: create v4 104 c, 97 c, 108 c, 108 c, 111 c, v4 4 chars + c@ . Strings werden in Forth vorzugsweise im Format "addr count" dargestellt, wobei addr die Anfangsadresse ist und count die Anzahl der Zeichen im String beschreibt: v4 5 type String-konstanten erhält man mit s" hallo, welt" .s type Allerdings ist S" interaktiv recht beschränkt: der String ist nur bis zum nächsten Aufruf von S" vorhanden. Wenn es in einer Definition verwendet wird, ist der String aber dauerhaft. Übung: EMIT ( c -- ) gibt c als Zeichen aus. Implementieren Sie TYPE ( addr u -- ). Alignment Auf den meisten Prozessoren müssen Zellen ausgerichtet (aligned) gespeichert werden (u.a. auf der Alpha-Architektur, die die mips.complang.tuwien.ac.at antreibt). Der Bereich, der nach einem CREATE reserviert wird, ist ausgerichtet, desgleichen der von ALLOCATE reservierte Speicher. Durch Addieren von Zellengrößen erhält man wieder eine ausgerichtete Adresse. Bei Addressarithmetik mit CHAR+ und CHARS kann allerdings eine nicht (zellen-)ausgerichtete Adresse entstehen. Dann erhält man mit aligned die nächste ausgerichtete Adresse: v3 char+ aligned @ . v3 char+ @ . Datenstrukturen Forth stellt standardmäßig keine eigenen Datenstrukturwörter zur Verfügung, aber man kann sich selbst welche bauen, aufbauend auf der Adressarithmetik. Ein Beispiel dafür ist in http://www.complang.tuwien.ac.at/forth/objects/structs.html zu bewundern (und der Code befindet sich in .../struct.fs; eine etwas ältere Version ist in Gforth-0.3.0 enthalten). Übung: Schreiben Sie mit Hilfe der Datenstrukturwörter die Definition eines binären Baums, der Strings enthält, und ein Wort zum Einfügen eines Strings in einen Suchbaum. Übersetzungssemantik und Interpretationssemantik Die Eingabe an der Tastatur (und auch der von einem File gelesene Text) wird vom Textinterpreter verarbeitet. Im Interpreter-Zustand führt er von jedem Wort, das er verarbeitet, die Interpretationssemantik aus. Im Compiler-Zustand führt der Textinterpreter die Übersetzungssemantik jedes Wortes aus. : schaltet in den Compiler-Zustand, und ; schaltet zurück in den Interpreter-Zustand. Daneben machen sie noch einiges andere. Sie enthalten die Faktoren ] und [, die nur die Umschaltung vornehmen. : xxx ( -- ) [ 5 . ] ; xxx Die übersetzungssemantik der meisten Wörter (z.B. +) ist, einfach die Interpretationssemantik des Wortes an die des gerade definierten Wortes (z.B. foo) anzuhängen. Mit anderen Worten, wenn foo irgendwann ausgeführt wird, wird unter anderem die Interpretationssemantik von + (nämlich das Addieren von zwei Zahlen) ausgeführt (außer der Kontrollfluß umgeht den entsprechenden Teil von foo). Auch benutzerdefinierte Wörter werden normalerweise so compiliert. Es gibt allerdings auch Wörter mit besonderer Übersetzungssemantik, zum Beispiel die Kontrollflußwörter (die gar keine Interpretationssemantik haben). Als Benutzer kann man mit IMMEDIATE das letzte Wort ändern, sodaß es die gleiche Übersetzungssemantik wie Interpretationssemantik hat: : FOO ( -- ) 5 . ; immediate FOO : bar ( -- ) FOO ; bar In Gforth (und vielen anderen Systemen, aber nicht im Standard) kann man außerdem mit COMPILE-ONLY die Interpretationssemantik entfernen (wobei sich die Übersetzungssemantik dabei von der ursprünglichen Interpretationssemantik ableitet): : flip ( -- ) 6 . ; compile-only \ aber nicht immediate FLIP : flop ( -- ) flip ; flop Im obigen Fall ist die Interpretationssemantik von flop gleich der ursprünglichen Interpretationssemantik von flip. POSTPONE Mit POSTPONE können Sie die übersetzungsemantik eines Wortes compilieren: : my-+ ( Compilation: -- ; Run-time of compiled code: n1 n2 -- n ) POSTPONE + ; immediate : foo ( n1 n2 -- n ) my-+ ; 1 2 foo . see foo Wenn MY-+ ausgeführt wird (in unserem Fall während der Definition von FOO), führt es die übersetzungssemantik von + aus, d.h. es compiliert + in das aktuelle Wort (also FOO). Da MY-+ immediate ist und daher schon während der Übersetzung ausgeführt wird, sehen Sie im decompilierten Code nicht MY-+, sondern nur das von MY-+ compilierte +. : my-- ( Compilation: -- ; Run-time of compiled code: n1 n2 -- n ) POSTPONE negate POSTPONE + ; immediate : bar ( n1 n2 -- n ) my-- ; 2 1 bar . see bar Auf diese Weise ist auch ENDIF definiert; eigentlich heißt das Wort, das eine IF-Struktur abschließt, THEN. Um aber Umsteiger von anderen Programmiersprachen nicht zu verwirren, bevorzugen viele Leute ENDIF. : ENDIF ( Compilation: orig -- ) POSTPONE then ; immediate Übung: Schreiben Sie MY-2DUP, dessen Übersetzungssemantik äquivalent zur Übersetzungssemantik von 2DUP ist, das aber OVER OVER compiliert. LITERAL Mit POSTPONE kann man keine Zahlen in künftige Wörter compilieren: : foo POSTPONE 500 ; immediate Stattdessen kann man Literal verwenden: : foo ( compilation: --; run-time: -- n ) 500 POSTPONE literal ; immeidate Eine häufigere Verwendung von Literal ist, eine Zahl in das aktuelle Wort zu compilieren: : bar ( -- n ) [ 2 2 + ] literal ; see bar Eine typische Anwendung ist, wie man sieht, das Berechnen von Konstanten zur Compile-Zeit. Übung: Schreiben Sie ]L, sodass das obige Beispiel bequemer als : bar ( -- n ) [ 2 2 + ]L ; geschrieben werden kann. Execution Tokens Mit ' Wort erhalten Sie das Execution Token (XT) von Wort. Das Execution Token repräsentiert die Interpretationssemantik des Worts. Mit EXECUTE kann diese Semantik ausgeführt werden: ' + .s 1 2 rot execute . Das XT ähnelt einem Funktionszeiger in C. Allerdings ist man durch die Parameterübergabe über den Stack etwas flexibler: : map-array ( ... addr u xt -- ... ) \ führt xt ( ... x -- ... ) für jedes Element des Arrays aus, \ das bei addr beginnt und u Elemente enthält { xt } cells over + swap ?do i @ xt execute 1 cells +loop ; create a 3 , 4 , 2 , -1 , 4 , a 5 ' . map-array .s 0 a 5 ' + map-array . s" max-n" environment? drop .s a 5 ' min map-array . MAP-ARRAY ist also mit XTs von Worten zu gebrauchen, die ein Element mehr vom Stack nehmen als sie drauflegen. Im Prinzip kann man es für XTs anderer Wörter verwenden, aber dann ist der Stackeffekt abhängig von der Größe des Arrays, was normalerweise etwas unpraktisch und meistens schwer zu verstehen ist. Das XT paßt in eine Zelle; es kann dementsprechend abgespeichert und auf dem Stack manipuliert werden. Abgesehen von diesen normalen Operationen und EXECUTE kann man das XT auch mit "COMPILE," in ein Wort compilieren: : foo1 ( n1 n2 -- n ) [ ' + compile, ] ; see foo (Das ist nicht ganz Standard, weil "COMPILE," im Standard keine Interpretationssemantik hat, aber es funktioniert in Gforth). Mit COMPILE, und POSTPONE können Sie dem System das EXECUTE ersparen (indirekte Aufrufe sind auf den meisten Prozessoren relativ teuer) und Code produzieren, der das aufzurufende Wort direkt enthält: : compile-map-array ( compilation: xt -- ; run-time: ... addr u -- ... ) \ führt zur Laufzeit xt ( ... x -- ... ) für jedes Element des Arrays aus, \ das bei addr beginnt und u Elemente enthält { xt } POSTPONE cells POSTPONE over POSTPONE + POSTPONE swap POSTPONE ?do POSTPONE i POSTPONE @ xt compile, 1 cells POSTPONE literal POSTPONE +loop ; : sum-array ( addr u -- n ) 0 rot rot [ ' + compile-map-array ] ; see sum-array a 5 sum-array . Die Erzeugung von Code kann man mit der vollen Mächtigkeit von Forth steuern und unterstützen; hier ein Beispiel, in dem Code in einer Schleife erzeugt wird: : compile-vmul-step ( compilation: n --; run-time: n1 addr1 -- n2 addr2 ) \ n2=n1+(addr1@)*n, addr2=addr1+cell POSTPONE tuck POSTPONE @ POSTPONE literal POSTPONE * POSTPONE + POSTPONE swap POSTPONE cell+ ; : compile-vmul ( compilation: addr1 u -- ; run-time: addr2 -- n ) \ n=v1*v2 (inneres Produkt), wobei die v_i als addr_i u repräsentiert sind 0 postpone literal postpone swap [ ' compile-vmul-step compile-map-array ] postpone drop ; see compile-vmul : a-vmul ( addr -- n ) \ n=a*v, wobei v ein Vektor ist, der so lang ist wie a und bei addr anfängt [ a 5 compile-vmul ] ; see a-vmul a a-vmul . Hier wurde compile-map-array verwendet, aber Sie können compile-vmul-step auch mit map-array verwenden. Mit dieser Technik kann man zum Beispiel eine effizientere Matrizenmultiplikation durchführen: Bei der Matrizenmultiplikation wird jede Zeile der einen Matrix mit jeder Spalte der anderen multipliziert; den Code fuer die Multiplikation einer Zeile braucht man nur einmal erzeugen, und kann ihn dann fuer jede Spalte verwenden. Compilation Token "' wort COMPILE," compiliert die Interpretationssemantik; für die meisten Wörter ist das die Übersetzungssemantik. In Gforth gibt es außerdem noch COMP', das ein Compilation Token (CT) liefert, das die Übersetzungssemantik repräsentiert; ein CT belegt zwei Zellen. Mit EXECUTE können Sie dann diese Übersetzungssemantik ausführen. : foo2 ( n1 n2 -- n ) [ comp' + execute ] ; see foo Mit "POSTPONE," können Sie diese Übersetzungssemantik compilieren. "[ COMP' wort POSTPONE, ]" ist äquivalent zu "POSTPONE wort". : foo3 ( -- ) [ COMP' + POSTPONE, ] ; see foo3 COMP' is besonders nützlich bei Wörtern, die keine Interpretationssemantik haben: ' IF COMP' IF Exceptions THROW ( n -- ... ) löst eine Exception aus, wenn n ungleich 0 ist: 100 THROW .s 0 THROW .s CATCH ( ... xt -- ... n ) verhält sich ähnlich wie EXECUTE, es fängt aber exceptions auf und liefert die Nummer der Exception bzw. (wenn's keine gab) 0. Wenn's eine Exception gab, sind die Stacks genauso tief wie beim Aufruf von CATCH: .s 3 0 ' / CATCH .s 3 2 ' / CATCH .s Übung: Probieren Sie das gleiche mit EXECUTE statt mit CATCH. THROW springt immer zum dynamisch nächstäusseren CATCH, auch wenn es dabei mehrere Ebenen von Aufrufen verlassen muß: : foo 100 throw ; : foo1 foo ; : bar ' foo1 catch ; bar Eine wichtige Programmiertechnik ist folgende: : ... verändere-x ' wort CATCH ( ... n ) stelle-x-wieder her ( ... n ) THROW ; Auf diese Weise werden Veränderungen auch dann wieder rückgängig gemacht, wenn eine Exception auftritt. Dictionary, Wordlists und Suchreihenfolge Das Dictionary ist nicht nur ein Speicherbereich, in dem man mit ALLOT Speicher reservieren kann, sondern es enthält auch die Forth-Wörter, und zwar in verschiedenen Wordlists. Wird in einer Wordlist nach einem Wort gesucht, werden dabei konzeptuell die Wörter vom jüngsten anfangend bis zum ältesten durchsucht (tatsächlich verwenden die meisten Systeme heute Hash-Tabellen). Welche Wordlists durchsucht werden, legt die Suchreihenfolge (search order) fest. Die Suchreihenfolge kann man mit ORDER ausgeben: order Die Ausgabe enthält zuerst die Suchreihenfolge, beginnend mit der ersten durchsuchten Wordlist, und ausserdem die Wordlist, in die die neu definierten Wörter kommen. Eine neue Wordlist legt man mit WORDLIST ( -- wid ) an: wordlist constant mywords Mit SET-CURRENT ( wid -- ) stellt man ein, in welche Wordlist neue Definitionen eingetragen werden: mywords set-current order Diese wordlist kann man mit GET-CURRENT ( -- wid ) wieder lesen. Die Suchreihenfolge wird mit SET-ORDER ( wid1 ... widn n -- ) geschrieben und mit GET-ORDER ( -- wid1 ... widn n ) gelesen. Dabei liegt die erste durchsuchte Wordlist als zuoberst am Stack etc. get-order mywords swap 1+ set-order order Die Ausgabe von ORDER ist etwas unintuitiv. Übung: Definitieren Sie >ORDER ( wid -- ), das wid als erste durchsuchte Wordlist der Suchreihenfolge hinzufügt, und PREVIOUS ( -- ), das die erste durchsuchte Wordlist aus der Suchreihenfolge entfernt. Experimentieren Sie mit Randbedingungen (Achtung, Crash-Kurs). Definitionswörter :, CREATE und VARIABLE sind Definitionswörter: Sie definieren andere Wörter. Ein weiteres Definitionswort ist CONSTANT: 5 CONSTANT FOO FOO . Von VARIABLE und CONSTANT gibt's auch noch Varianten mit Prefix 2 (für Doppelzellen) oder F (für Gleitkommazahlen). Man kann sich auch selbst ein neues Definitionswort definieren. Eine einfache Variante ist: : variable ( "name" -- ) create 0 , ; Man kann auch Definitionswörter definieren, deren Kreaturen etwas anderes machen als nur ihre Adresse zu liefern: : constant ( n "name" -- ) create , does> ( -- n ) ( addr ) @ ; 5 constant foo foo . Eigentlich endet die Definition von CONSTANT mit dem DOES>; DOES> ersetzt also ";", es macht aber noch etwas mehr: Es bewirkt, dass das letzte definierte Wort den Code hinter dem DOES> ausführt, wenn es aufgerufen wird. Dabei wird zuerst die Adresse des mit CREATE angelegten Wortes auf den Stack gelegt und dann der Code aufgerufen. Der Stack-Kommentar, den ich geschrieben habe, spiegelt den Stack-Effekt des definierten Wortes wieder und nicht den Stack-Effekt des Codes hinter DOES> (der Unterschied ist, dass der Code hinter DOES> eine Adresse erwartet, die ich im Stack-Kommentar nicht zeige). Diese Art von Definitionswörtern erlaubt Factoring, bei dem Definitionswörter enthalten sind. So wird z.B. ein Feld-Offset immer zu einer Adresse addiert. Statt der Definition 2 cells constant offset-field1 und der Verwendung ( addr ) offset-field1 + definiert man sich ein Definitionswort : simple-field ( n "name" -- ) create , does> ( n1 -- n1+n ) ( addr ) @ + ; Die Definition und Verwendung des Offsets sehen nun so aus: 2 cells simple-field field1 ( addr ) field1 Für den Fall, dass man mit dem Wort etwas anderes machen will, als den Code im DOES>-Teil ausfuehren, kann man auf den Speicher eines mit CREATE definierten Wortes auch noch mit >BODY ( xt -- addr ) zugreifen: : value ( n "name" -- ) create , does> ( -- n1 ) @ ; : to ( n "name" -- ) ' >body ! ; 5 value foo foo . 7 to foo foo . Übung: Definieren Sie DEFER ( "name" -- ), das ein xt speichert (per Default den xt von ABORT), und beim Aufruf mit EXECUTE ausführt; definieren Sie weiters IS ( xt "name" -- ), das ein xt in ein mit DEFER definiertes Wort speichert. Eine Anwendung von DEFER ist die indirekte Rekursion.