Modula-2 Kurs, Teil 6

Dieser sechste Teil der Serie über Modula-2 wird drei Gebiete behandeln: Rekursion, den Datentypen SET und die eingebauten Standardfunktionen.

Rekursion

In der letzten Folge wurden Prozeduren und Funktionen behandelt. Ein Programm rief eine Prozedur auf, diese wurde abgearbeitet und danach kehrte der Rechner an die Stelle nach dem Aufruf zurück. Was passiert nun aber, wenn sich eine Prozedur selber aufruft, wenn im Prozedurkörper von a ein Aufruf a steht?

Einen solchen Selbstaufruf nennt man Rekursion, und diese wäre fast ein eigenes Kapitel wert. Ich will Ihnen die Rekursion an Beispielen nahebringen; das erste soll Zahlen ausgeben so ausgeben, daß von 1 angefangen jeweils die doppelte Zahl folgt, also 1,2,4,8 usw. Schreiben wir zunächst eine Prozedur, die einfach ihren Parameter ausgibt:

PROCEDURE WriteDoppel(n:INTEGER);
BEGIN
    WriteInt(n,5);
    WriteLn;
END WriteDoppel;

WriteInt und WriteLn müssen dabei natürlich wie bei den anderen Beispielen aus InOut importiert worden sein. Ein Aufruf mit WriteDoppel(1) gibt einmal die Zahl 1 aus und endet dann. Nun soll aber nach der Ausgabe einer Zahl die Ausgabe der nächsten, verdoppelten Zahl folgen. Dafür steht schon eine Prozedur bereit, nämlich WriteDoppel. Also können wir in die Prozedur einen Selbstaufruf einfügen:

PROCEDURE WriteDoppel(n:INTEGER);
BEGIN
    WriteInt(n,5);
    WriteLn;
    WriteDoppel(n*2);
END WriteDoppel;

Was geschieht nun bei einem Aufruf WriteDoppel(1)? Zunächst schreibt WriteInt(n,5) eine 1 auf den Bildschirm. Beim rekursiven Aufruf übergibt n*2 als Parameter eine 2. Der Rechner richtet nun erneut eine Prozedur WriteDoppel ein und führt sie mit dem Parameter 2 aus. Folge ist die Ausgabe von 2 und ein erneuter Selbstaufruf mit dem Parameter 4. Diese Aufruffolge geht immer weiter.

Bei jedem Aufruf richtet der Rechner neuen Platz für die Parametervariable n ein. Das eingerichtete n aus der Write-Doppel-Stufe, von der aus aufgerufen wird, bleibt erhalten. Das “Herabsteigen” in immer wieder eine neue Rekursionsstufe wird “rekursiver Abstieg” genannt.

Mit dieser Prozedurdefinition endet dieser Abstieg allerdings nie. Die Folge ist, daß irgendwann der Platz ausgeht. Hätte der ST unbegrenzten Speicher, würde das Programm niemals enden. Benötigt wird eine Abbruchbedingung, bei der die Selbstaufrufe beendet werden. Dazu nehmen wir hier die Angabe einer Obergrenze für die Ausgabe:

PROCEDURE WriteDoppel(n,ober:INTEGER);
BEGIN
    WriteInt(n,5);
    WriteLn;
    IF (n*2 <= ober) THEN 
        WriteDoppel(n*2,ober);
    END;
END WriteDoppel;

Ein Aufruf mit WriteDoppel(1,16) gibt nun wie gehabt die Zahlen 1,2,4 usw. aus, stoppt aber die Selbstaufrufe in dem Moment, da beim Verdoppeln des Parameters die Obergrenze überschritten wird. Damit ist die letzte ausgegebene Zahl 16. Die oberste Stufe der WriteDoppel-Aufrufe (also die mit Parameter n gleich 16) wird beendet und der gesamte vom Rechner beim Aufruf für n reservierte Speicher freigegeben. Der Computer rechnet nun nach dem Selbstaufruf der Stufe mit n=8 weiter. Diese Prozedur wird ebenfalls beendet, was sich bis zur letzten Stufe fortsetzt. Dieses “Hochklettern” durch die Rekursionsstufen ist der “rekursive Aufstieg”. Damit ist die Rekursion korrekt zu Ende gebracht.

Die Prozedur soll nun so erweitert werden, daß die Zahlen zunächst ansteigen und dann wieder abfallen, also 1,2,4,8,8, 4,2,1. Durch den rekursiven Aufruf wird diese Erweiterung sehr einfach (siehe nächste Spalte).

PROCEDURE WriteDoppel(n, ober:INTEGER); 
BEGIN 
    WriteInt(n,5);
    WriteLn;
    IF (n*2 <= ober) THEN 
        WriteDoppel(n*2,ober);
    END;
    WriteInt(n,5);
END WriteDoppel;

Ein Durchlauf einer Stufe von WriteDoppel läuft nun so ab: Parameter ausgeben, Selbstaufruf, durch den die höheren Zahlen auf den Bildschirm kommen, und danach erneute Ausgabe des - auf dieser Stufe unveränderten - Parameters. Die Obergrenze wird wieder unverändert von Stufe zu Stufe weitergereicht.

Die Ausführungsreihenfolge mit Ab- und Aufstieg soll nochmals schematisch skizziert werden.

Dabei sind die Bildschirmausgaben fett gedruckt. WD bezeichnet den Aufruf WriteDoppel. Sie sehen, wie der Rechner die einzelnen Rekursionsstufen durchläuft und die Zahlen in der gewünschten Reihenfolge (im Bild von links nach rechts) ausgibt. Rekursion besteht also aus dem Abstieg, dem Rekursionsabbruch und dem Aufstieg. Im Programmtext stehen zunächst alle Aktionen des Abstiegs, dann der von einer Abbruchbedingung abhängige Selbstaufruf und schließlich die Anweisungen, die beim Aufstieg ausgeführt werden sollen.

SETs

Neben den schon bekannten Datentypen gibt es in Modula noch die Mengen. Eine Menge kann mehrere Werte gleichzeitig enthalten. Jeder Wert stammt aus einem Aufzählungstypen oder einem Unterbereichstypen. Ein Beispiel zur Deklaration:

TYPE Farben = (Rot, Gelb, Gruen);
      Ampel = SET OF Farben;

Mit den Schlüsselwörtern SET OF wird der Typ Ampel zu einer Menge, die Werte vom Typ Farben aufnehmen kann. Einer entsprechenden Variablen kann nun ein Inhalt zugewiesen werden:

VAR DieAmpel : Ampel;
... DieAmpel:=Ampel{Rot,Gelb};

Damit enthält die Menge DieAmpel die Werte Rot und Gelb. Bei der Zuweisung muß der Mengentyp vor der Liste der Elemente notiert werden. Die in die Menge zu übernehmenden Elemente sind durch Kommata getrennt und mit geschweiften Klammem zusammengefaßt. In dem Mengenausdruck selber dürfen nur Konstanten auftreten, also nur die Bezeichner, die in der Typdeklaration Vorkommen. Ein Programm

VAR i:Farben; 
...
i:=Gelb;
DieAmpel:=Ampel{Rot,i};

ist also nicht möglich. Um auch variable Werte (fest) in die Menge zu nehmen, existiert die Funktion INCL. Erlaubt wäre:

DieAmpel:=Ampel{Rot}
i:=Gelb;
INCL(DieAmpel,i);

Danach hat DieAmpel den Inhalt Ampel{Rot,Gelb}. Um ein Element zu entfernen, steht EXCL bereit:

EXCL(DieAmpel.i);

Somit hätte DieAmpel wieder den Inhalt Ampel {Rot}. Beide Funktionen sind fester Bestandteil von Modula-2.

Für Mengen steht eine Reihe von Operatoren bereit, mit denen Ausdrücke formuliert werden können. Zunächst die vier “Grundrechenarten” für jeweils zwei Mengen:

+ Vereinigung: Beide Mengen werden zusammengefügt. Dabei steht jedes Element nur einmal im Ergebnis.

{Rot,Gelb} + {Gruen} = {Rot, Gelb, Gruen}
{Rot,Gelb) + {Gelb,Gruen} ={Rot, Gelb, Gruen}

- Differenz: Aus der ersten Menge werden alle Elemente entfernt, die in der zweiten auftauchen.

{Rot,Gelb} - {Gelb} = {Rot}
{Rot,Gelb} - {Gelb,Gruen} = {Rot}

*** Durchschnitt:** Ergebnis ist die Menge aller Elemente, die in beiden Mengen vorhanden sind.

{Rot,Gelb} * {Gelb,Gruen} = {Gelb}

/ symmetrische Differenz: Im Ergebnis stehen nur die Elemente, die nicht in beiden Mengen stehen.

{Rot,Gelb} / {Gelb,Gruen} = {Rot,Gruen}

Als Relationen mit einem Ergebnis vom Typ BOOLEAN sind die Gleichheit = und Ungleichheit # bzw. <> definiert. <= und => fragen ab, ob eine Menge in der anderen enthalten ist.

Schließlich gibt es noch den Operator IN, der testet, ob ein bestimmtes Element in einer Menge enthalten ist:

IF Rot IN DieAmpel THEN ...

Der Ausdruck vom Typ BOOLEAN ergibt TRUE, wenn das angegebene Element in der Menge enthalten ist. IN kann natürlich auch mit einer Variablen verwendet werden.

Ein in Modula vordefinierter Mengentyp ist BITSET. Ein BITSET ist eine Menge von CARDINALS einer bestimmten Größe, die wiederum implementationsabhängig ist. BITSETs könnten selber definiert werden mit

TYPE BITSET = [0..31];

Auf BITSETs sind die beschriebenen Mengenoperationen mit gleicher Funktionalität definiert.

Die maximale Größe von Mengen ist jeweils implementationsabhängig. Auf ETH-Compilern und deren Abkömmlingen sind sie normalerweise auf 32 Bit beschränkt. Warum 32 Bit? Jedes mögliche Element kann in einer Menge enthalten sein oder nicht. Dementsprechend wird für jedes Element aus dem Wertebereich ein Bit in einer Menge eingerichtet. Ist das Element in der Menge, schreibt der Rechner eine 1 ein, ansonsten 0. Beschränkt man die maximale Mengengröße auf einen für den Prozessor optimalen Wert, können SETs sehr schnell verarbeitet werden. Auf dem 68000 ergeben sich z.B. 16 oder 32 Elemente pro Menge.

Welchen Wert Ihr System erlaubt, müssen Sie im Handbuch nachschlagen. Es gibt teilweise ein Modul BigSets, mit dem auch größere Mengen möglich sind.

Standardfunktionen

Eine Reihe von Standardfunktionen sind fest in Modula eingebaut. Ein paar davon haben Sie schon kennengelernt, heute soll die Liste vervollständigt werden.

CHR(x)
ergibt ein Zeichen vom Typ CHAR mit der Ordnungszahl a. Im ASCII-System liefert CHR(65) das Zeichen “A”.

ORD(x)
ergibt die Ordnungszahl des übergebenen Wertes. Dabei kann x beispielsweise ein CHAR sein: ORD(“A”) liefert 65 im ASCII-System. Für x sind alle Aufzählungstypen zugelassen, also auch ORD(Gruen), was 2 liefern würde. Das Ergebnis ist ein CARDINAL.

CAP(ch)
liefert - wenn möglich - den entsprechenden Großbuchstaben zum CHAR ch. CAP(“a”) ist “a” und CAP(“A”) ergibt “A”

TRUNC(r)
Das INTEGER-Ergebnis ist der ganzzahlige Teil der REAL-Zahl r.

FLOAT(i)
liefert eine REAL-Zahl mit Wert der ganzen Zahl i.

INC(x) INC(x,i)
erhöht die ganzzahlige Variable x um 1 oder - falls angegeben - um i. Je nach Prozessor kann der Compiler schnelleren Code generieren als bei x:=x+l oder x:=x+i. Aufgrund der Befehle des 68000 lohnt sich der Einsatz bis zu einer Erhöhung um 8. Bei INC handelt es sich um eine Anweisung, nicht um eine Funktion!

DEC(x) DEC(x,i)
erniedrigt die ganzzahlige Variable x um 1 oder i. Erzeugt ebenfalls schnelleren Code bis zu einer Substraktion von 8 beim 68000.

EXCL(set,element)
entfernt aus einer Menge das angegebene Element.

INCL(set,element)
fügt das angegebene Element der Menge hinzu.

HIGH(f)
liefert die Anzahl der Elemente (von 0 an gezählt) eines Feldes f.

HALT
stoppt die Programmausführung. Ein HALT zählt in den meisten Systemen als Laufzeitfehler und wird nur in extremen Ausnahmen zu verwenden sein.

In der nächsten Folge komme ich endlich zu dem Konzept, das Modula-2 den Namen gegeben hat: den Modulen. Es geht um interne und externe Module, um Lebensdauer und Sichtbarkeit und um Strukturierung innerhalb größerer Programmprojekte.

RT

---

---