Schleifen

Das letzte Kapitel mag ihnen ein bisschen 'arm' vorgekommen sein. Nur eine einzige Möglichkeit Entscheidungen zu realisieren, wenn man davon absieht, dass es Befehle gibt, die eine Entscheidung 'eingebaut' haben. Nun, ich habe ihnen versprochen, dass ich dieses Problem noch angehen werde, aber hier erst mal ein Kapitel, in dem es mehr Auswahl gibt: Ein Kapitel über Schleifen, für die Forth wesentlich mehr Möglichkeiten bietet, als bei den Entscheidungen.

Festgelegte Schleifen

Unter festgelegten Schleifen versteht man in Forth Schleifen, deren Anzahl von Durchläufen vor Eintritt in die Schleife festgelegt wird. Die einfachste Form der Schleife ist:

... Grenze Index DO ... LOOP ...

Eine solche Schleife kann nur in einer Doppelpunktdefinition verwendet werden, also nur in der Definition eines neuen Wortes. Bevor DO dort erscheinen darf, müssen zwei Werte auf dem Stack liegen, die als Grenze und Index interpretiert werden. Wie wird mit ihnen umgegangen?

Zunächst 'schaufelt' DO die beiden Werte auf den Returnstack, das ist ein weiterer Stack, den Forth nutzt und der später noch eingehender besprochen werden wird. Danach werden die Wörter, die hinter DO stehen ganz normal ausgeführt (Eine DO ... LOOP-Schleife wird also immer einmal ausgeführt!) Erreicht die Ausführung LOOP, dann geschieht folgendes: LOOP erhöht den Index um Eins und testet dann, ob der Index größer oder zumindest gleich der Grenze geworden ist. Ist das der Fall, dann werden Index und Grenze vom Returnstack wieder entfernt und hinter LOOP mit der Ausführung der Wörter weiter gemacht. Ist es hingegen nicht der Fall, dann verzweigt Forth auf das erste Wort hinter DO und die Scheife wird ein zweites Mal durchlaufen.

Kompliziert? Eigentlich nicht! Am einfachsten sieht man sich erst mal ein einfaches Beispiel an:

  : BALKEN 10 0 DO 61 EMIT LOOP ;
  BALKEN ========== ok

Wie man sieht wird der bereich zwischen DO und LOOP einfach zehn mal durchlaufen und das war es. Die Grenze ist hier die '10', der (Anfangs)Index die '0'.

Nachdem das erste Gleichheitszeichen ausgegeben wurde, das erste Mal LOOP erreicht wird, erhöht LOOP den Index zunächst von 0 auf 1. Dann wird getestet, ob der Index gleich oder größer als die 10 ist. Das ist natürlich nicht der Fall und es geht zurück hinter das DO, wo die Sache von vorne beginnt.

Nachdem das 10te Gleichheitszeichen ausgegeben wurde, ist der Index '9'. Auch der wird zunächst erhöht und dann getestet. Nun ist er gleich der Grenze, welche die ganze Zeit hindurch unverändert geblieben ist. Daraufhin entfernt LOOP Grenze und Index vom Returnstack und es geht hinter dem LOOP weiter, wobei bei diesem Beispiel da natürlich nichts mehr passiert.

Kann man in einer DO...LOOP-Schleife auf den Index zugreifen? 'Weiß' man also innerhalb der Schleife, der wievielte Durchlauf gerade 'dran' ist? Ja, man weiß es! Es gibt in Forth natürlich Möglichkeiten auch den Returnstack zu verändern und auszulesen, im Zusammenhang mit DO...LOOP-Schleifen ist es aber einfacher auf ein anderes Wort zu setzen: I. I kopiert einfach den obersten Wert vom Returnstack auf den Zahlenstack. Da das der aktuelle Index ist, hat man ihn dann zur Verfügung.

  : LAUF 10 0 DO I . LOOP ;  ok
  LAUF 0 1 2 3 4 5 6 7 8 9  ok

Man kann den Schleifenindex, wenn man ihn mit I auf den Zahlenstack geholt hat, wie jeden anderen Wert verwenden. Man kann mit ihm rechnen, ihn als Flag verwenden und so weiter:

  : SIEBENER 11 1 DO I 7 * . LOOP ;
  SIEBENER 7 14 21 28 35 42 49 56 63 70  ok

DO-Schleifen lassen sich auch schachteln. Und das in zweifacher Hinsicht. Die einfache Variante geht folgendermaßen:

  : ERREIHE 11 1 DO DUP I * 5 U.R LOOP DROP ;
  : KLEINES 11 1 DO I ERREIHE CR LOOP ;

Das Wort U.D ist eine Sonderform des Ausgabewortes .. Hiermit können Zahlen rechtsbündig in einem Feld ausgegeben werden, dessen Breite vorher angegeben werden muss (hier ist das Feld 5 Zeichen breit).

Man erkennt, dass das Wort KLEINES eine Schleife enthält, die ihrerseits ein Wort (ERREIHE) aufruft, das wiederum eine Scheife enthält.

  KLEINES     1    2    3    4    5    6    7    8    9   10
    2    4    6    8   10   12   14   16   18   20
    3    6    9   12   15   18   21   24   27   30
    4    8   12   16   20   24   28   32   36   40
    5   10   15   20   25   30   35   40   45   50
    6   12   18   24   30   36   42   48   54   60
    7   14   21   28   35   42   49   56   63   70
    8   16   24   32   40   48   56   64   72   80
    9   18   27   36   45   54   63   72   81   90
    10   20   30   40   50   60   70  80   90  100
  ok

Man kann das Ganze aber auch in eine Definition packen. Das sieht dann so aus:

  : GROSSES ( -- )
    CR
    21 11 DO
      21 11 DO
        I J * 5 U.R
      LOOP
    CR LOOP ;
  grosses 
    121  132  143  154  165  176  187  198  209  220
    132  144  156  168  180  192  204  216  228  240
    143  156  169  182  195  208  221  234  247  260
    154  168  182  196  210  224  238  252  266  280
    165  180  195  210  225  240  255  270  285  300
    176  192  208  224  240  256  272  288  304  320
    187  204  221  238  255  272  289  306  323  340
    198  216  234  252  270  288  306  324  342  360
    209  228  247  266  285  304  323  342  361  380
    220  240  260  280  300  320  340  360  380  400
  ok

Alles, was man zum Verständnis wissen muss ist die Bedeutung des Wortes J. Es holt einfach den drittobersten Wert vom Returnstack auf den Datenstack und da liegt der Index der inneren Schleife. Auch auf diese Art können Schleifen verschachtelt werden.

Was passiert nun, wenn man in einer solchen Schleife feststellt, dass eine Bedingung erreicht ist und man die Schleife vorzeitig beenden will? Nach meiner Meinung sollte man dann zwar direkt eine bedingte Schleife verwenden (kommt gleich), aber Forth bietet auch für diesen Fall eine Möglichkeit:

LEAVE

Trifft der Ablauf innerhalb einer Schleife auf auf LEAVE, dann wird die Schleife abgebrochen. Das genaue Vorgehen ist dabei allerdings Implementationsabhängig. Manche Versionen von Forth gehen so vor, dass LEAVE einfach die Grenze so ändert, dass beim nächsten Erreichen von LOOP oder +LOOP die Schleife beendet wird. Bei diesem Verfahren werden alle Worte bis zu diesem LOOP oder +LOOP noch abgearbeitet. Andere Implementation von Forth sorgen bei LEAVE für einen sofortigen Abbruch der Schleife und die weitere Bearbeitung hinter LOOP oder +LOOP. In jedem Fall wäre mit diesem Wort folgendes möglich:

  : URLAUB
    21 1 DO
      STRAND ESSEN DISCO
      GELDALLE? IF LEAVE THEN
    LOOP
    HEIMREISE ;

Ich hoffe natürlich für sie, dass die Bedingung nie wahr wird!

Bedingte Schleifen

Im Gegensatz zu Schleifen, bei denen die Anzahl der Durchläufe vor Beginn der Schleife festgelegt wird, gibt es in nahezu allen Computersprachen auch Schleifen, bei denen das nicht der Fall ist. Sie werden so lange durchlaufen, bis eine Bedingung eintritt (oder nicht mehr der Fall ist); man spricht hier auch von bedingten Schleifen. Forth bietet zwei Konstruktionen für derartig bedingte Schleifen. Die erste hat die Form:

BEGIN ... UNTIL

Der Körper der Schleife, also der Bereich zwischen BEGIN und UNTIL wird in jedem Fall einmal durchlaufen. Das Wort UNTIL wertet dann die oberste Zahl auf dem Stack als Flag aus. Ist dieses Flag 'wahr', dann wird hinter UNTIL weiter gemacht. Ist es 'falsch', dann wird zurück hinter BEGIN gesprungen.

Eine andere Variante unterscheidet sich von der BEGIN ... UNTIL-Schleife durch zwei Unterschiede: Zum einen erfolgt der Test, ob die Schleife abgebrochen werden soll innerhalb der Schleife und nicht erst am Ende, zum Anderen wird die Schleife beenet, wenn die getestete Bedingung 'falsch' ist und nicht, wenn sie 'wahr' ist. Wie funktioniert diese Schleifenkonstruktion?

Zunächst wird die Schleife bis WHILE durchlaufen. WHILE interpretiert die auf dem Stack liegende Zahl als Flag und bricht die Schleife ab, wenn das Flag 'falsch', also die Zahl Null ist. In diesem Fall werden die Worte hinter REPEAT weiter ausgeführt.
Ist das Flag hingegen 'wahr', dann wird die Ausführung hinter WHILE weitergeführt, bis zum REPEAT. Von dort aus verzweigt die Ausführung dann wieder auf das erste Wort hinter BEGIN.

Ein schönes Beispiel ist die Berechnung der Halbwertzeit. Hier wird eine Größe so lange verringert, bis sie kleiner oder gleich der Hälfte der ursprünglichen Zahl ist. Kommentiert sieht das folgendermaßen aus:

  : % 10 */ 5 + 10 / ;
  : HALBWERT     \ Übergeben wird der Prozentsatz
    1000         \ Ein Startwert, der im Prinzip beliebig ist (s.u.)
    BEGIN        \
      OVER %     \ Vom aktuellen Wert der Prozentwert
      DUP 500 >  \ ist der noch größer als 500 (Halber Startwert)
    WHILE        \ wenn nicht, wars das!
      DUP .      \ Sonst mal ausgeben (zum Zählen)
    REPEAT ;     \ und weiter

Eine letzte Schleife wird nicht durchlaufen. Allerdings nur dann, wenn Index und Grenze gleich sind. Das Wort ?DO arbeitet exakt wie DO, abgesehen eben davon, dass der Schleifenkörper nicht durchlaufen wird, wenn Index und Grenze gleich sind.

Aufgaben

  1. Schreiben sie das Wort FIBONACCI. Dieses Wort soll eine Zahl auf dem Stack erwarten und die entsprechende Anzahl von Fibonacci-Zahlen ausgeben. Sie brauchen nicht darauf zu achten, dass diese Zahlen sehr schnell sehr groß werden. Es reicht, wenn es die ersten zehn Fibonacci-Zahlen ausgibt. [Lösung]
  2. Schreiben sie das Wort COLLATZ. Mit diesem Wort soll es möglich sein, dass sogenannte Collatz-Problem zu untersuchen. Die Aufgabenstellung ist die folgende:
    Man beginnt mit einer beliebigen natürlichen Zahl (Die bei dem obigen Wort auf dem Stack übergeben werden soll).
    Ist die Zahl gerade, dann soll die nächste Zahl die Hälfte dieser Zahl sein.
    Ist die Zahl ungerade, dann soll die nächste Zahl das Dreifache der Zahl + 1 sein.
    Die Folge der Zahlen bricht dann ab, wenn eine Eins erreicht wird. So zum Beispiel für die Zahl 3:
    3 10 5 16 8 4 2 1
    Ihr Wort soll nun die Folge der Zahlen für eine übergebene Zahl bestimmen und ausgeben. Wenn die Eins erreicht ist, soll ihr Wort beendet werden.
    Tipp: Wenn eine Zahl ungerade ist, ergibt die Zahl auf dem Stack vorausgesetzt 1 AND 'wahr' wenn die Zahl ungerade war.[Lösung]