Home Up Intro Contents Chapter 1 2 3 4 5 6 7 8 9 10 Design Assert Timing EBNF Report Pas Last Changed: Nov. 19, 1997
This is a conversion from Oberon text to HTML. The converter software is still under development, and some features or information may be missing in this converted version. HTML hypertext facilities are not yet active in this document. To exploit the interactive facilities, use Oberon System 3 and the source of this text, available as ASCII-coded Oberon System 3 documents. A previous version is also available for Oberon V4. To access this and other additional material use ftp.
For the convenience of our students, most of this information and the related material is in German. Sorry if this is not one of your languages.

Einführung in die Programmiersprache Oberon.

G. Sawitzki <gs@statlab.uni-heidelberg.de>



06 Kontrollstrukturen

In Oberon, wie in den meisten Programmiersprachen, ist der eigentliche Programmablauf als eine Anweisungsfolge beschrieben. Wir haben diese Anweisungsfolgen im Rumpfteil des Moduls, aber auch in den Prozedurdeklarationen kennengelernt. Die Beispiele, die wir bis jetzt gesehen haben, waren strikt sequentiell: die Anweisungen sind in genau der Reihenfolge ausgeführt worden, in der sie aufgeschrieben sind.

Nur wenige Probleme lassen sich in dieser strikt sequentiellen Weise lösen. Damit ein Problem strikt sequentiell zu lösen ist, muss ein Algorithmus existieren, der in einer festen, vorab bekannten Zahl von Schritten zu einer Lösung führt. Selbst elementare Probleme, zum Beispiel die Aufgabe, eine rationale Zahl dezimal darzustellen, fallen nicht in diese Klasse. Es muss eine Möglichkeit eingeführt werden, einen Algorithmus abhängig von Zwischenergebnisen zu steuern. Damit gibt es ausser der linearen Struktur, in der ein Programm aufgeschrieben ist, noch eine zweite Struktur oder eine Gruppe von Strukturen, genannt Kontrollstrukturen.

In Oberon gibt es zwei elementare Kontrollstrukturen: die IF-Anweisung und die LOOP-Anweisung. Die IF-Anweisung führt eine Anweisungsfolge nur aus, falls ein kontrollierender logischer Ausdruck wahr ist. Die LOOP-Anweisung führt eine Anweisungsfolge wiederholt aus.

Formal sind die elementaren Kontrollstrukturen in Oberon:
Elementare IF-Anweisung:
  IF Ausdruck THEN
    Anweisungsfolge
  END

LOOP-Anweisung:
  LOOP
    Anweisungsfolge
  END


Die Interpretation der IF-Anweisung ist naheliegend. An der Stelle von Ausdruck kann dabei jeder Ausdruck stehen, der als Resultat einen logischen Wert hat. Die Bedeutung entspricht dabei dem, was die englisch-sprachige Formulierung vermuten lässt. Die Anweisungsfolge in der IF-Anweisung wird dann (und nur dann) ausgeführt, wenn der Ausdruck als wahr (TRUE) ausgewertet wird.
Beispiel
  IF ( i MOD 3) = 0 THEN
    Texts.WriteString(W,"i ist durch 3 teilbar.")
  END;

Die Interpretation der LOOP-Anweisung ist eher problematisch. Die Anweisungsfolge in der LOOP-Anweisung wird wiederholt ausgeführt. In wenigen speziellen Ausnahme-Situationen soll wirklich eine Anweisungsfolge immer wiederholt werden. Das Betriebssystem ist eine der wenigen Ausnahmen. Im Prinzip sollte es eine LOOP-Anweisung der folgenden Form sein:
LOOP
  ... (* nächstes Kommando identifizieren *)
  ... (* Kommando ausführen *)
END

In den meisten Fällen aber soll eine Anweisungsfolge aber nicht immer wieder, sondern nur bis zur Erfüllung einer kontrollierten Bedingung durchlaufen werden: die LOOP-Anweisung muss terminierbar sein. Dies führt zu einer Reihe von Spezialisierungen.

Alle Kontrollstrukturen können genau so wie eine einzelne Anweisung benutzt werden. In der formalen Definition sind sie deshalb nur Spezialfälle für Anweisungen. Will man ihre komplexere interne Struktur herausheben, so spricht man von strukturierten Anweisungen. Sprachen mit strukturierten Anweisungen heissen strukturierte Programmiersprachen.

Von beiden elementaren Kontrollstrukturen gibt es Varianten. Diese Varianten könnten zwar logisch als Anweisungsfolgen mit den elementaren Kontrollstrukturen ausgedrückt werden. Weil sie aber sehr häufig benutzt werden, sind sie als eigene Sprachbestandteile aufgenommen. Wir betrachten zunächst die IF-Anweisung, und kommen dann später auf die LOOP-Anweisung zurück.

Die IF-Anweisung darf eine Alternative haben. Beispiel:
  IF ( i MOD 3) = 0 THEN
    Texts.WriteString(W,"i ist durch 3 teilbar.")
  ELSE
    Texts.WriteString(W,"i ist nicht durch 3 teilbar.")
  END;

IF-Anweisungen können eine "Kaskade" bilden. Kaskaden können mit oder ohne Alternative benutzt werden. Beispiel:
  IF Laenge >= 1000 THEN
    Texts.WriteReal(W,Laenge/1000,6);
    Texts.WriteString(W,"km.")
  ELSEIF Laenge >= 1 THEN
    Texts.WriteReaFixl(W,Laenge,6,2);
    Texts.WriteString(W,"m.")
  ELSE
    Texts.WriteRealFix(W,Laenge*100,6,2);
    Texts.WriteString(W,"cm.")
  END;

Die vollständige Syntax ist
IF-Anweisung:
  IF Ausdruck THEN
    Anweisungsfolge
   {ELSIF Ausdruck THEN
    Anweisungsfolge}
  [ELSE
Anweisungsfolge]
  END

Für den Spezialfall, dass eine Abfrage eine Reihe von Fällen abarbeitet, die man als Liste von ganzzahligen oder CHAR-Werten schreiben könnte, gibt es die CASE-Anweisung. Die Fälle in dieser CASE-Anweisung müssen konstante Ausdrücke sein, das heisst ihr Wert muss zur Compilierungszeit festgelegt sein. Während bei einer Folge von IF-Anweisungen die Anweisungen in der angegebenen Folge ausgewertet werden, erfolgt die Auswertung des Entscheidungs-Ausdrucks bei der CASE-Anweisung nur einmal bei Eintritt in die CASE-Anweisung.

CASE-Anweisung:
  CASE Ausdruck OF
    Fall
    {
| Fall }
  [ELSE
Anweisungsfolge]
  END
mit
Fall:
  Fall-Liste : Anweisungsfolge
Fall-Liste:
  Fall-Marke {, Fall-Marke}
Fall-Marke:
  Fall-Ausdruck [.. Fall-Ausdruck]

Beispiel:
  CASE ch OF
    "A".."Z":  Texts.WriteString(W,"Buchstabe (gross)")
  |  "a".."z":  Texts.WriteString(W,""Buchstabe (klein)")
  |  "0".."9":  Texts.WriteString(W,"Ziffer")
  |  ".", ",", ":", "?", "!":  Texts.WriteString(W,"Satzzeichen")
  ELSE  Texts.WriteString(W,"sonstiges")
  END

LOOP-Anweisung:

Die LOOP-Anweisung wird nur durch eine EXIT-Anweisung in der Anweisungsfolge verlassen. Die Anweisung EXIT führt zum Verlassen der umgebenden LOOP_Anweisung. Die Bearbeitung wird mit der nächsten Anweisung hinter der LOOP-Anweisung fortgesetzt.

Beispiel:
LOOP
  ... (* irgendeine Anweisungsfolge, zum Beispiel eine Rechnung mit I *)
  IF I>IMAX OR I<IMIN THEN EXIT;
  ... (* irgendeine Anweisungsfolge, zum Beispiel eine Rechnung mit I *)
END


Der innere Kern von Oberon ist im Prinzip nur eine LOOP-Anweisung. Vereinfacht kann man sich vorstellen:
LOOP
  ... (* nächstes Kommando identifizieren *)
  IF ... (* Kommando = System.Quit *) THEN EXIT END;
  ... (* Sonst: Kommando ausführen *)
END

Die LOOP-Konstruktion ist grundlegend gefährlich: der Programmierer hat zu garantieren, dass die LOOP-Konstruktion (korrekt) verlassen wird. Die LOOP-Konstruktion wird durch EXIT verlassen. Das Programm wird aber natürlich nicht hinter der EXIT-Anweisung forgesetzt, sondern hinter dem Ende der zugehörigen LOOP-Anweisung: Nicht-lokale Kenntnis der Programm-Struktur ist notwendig, um die Konstruktion interpretieren zu können. Selbst harmlos erscheinende LOOP-Konstruktionen können heimtückisch sein. Beispiel:

LOOP
IF X=1 THEN EXIT
  ELSIF X MOD 2 = 0 THEN X:=X DIV 2 ELSE X:= X*3+1 END;
END;

Versuchen Sie herauszufinden, ob dieses Programm-Fragment für jeden ganzzahligen Wert von X verlassen wird. Seien sie nicht enttäuscht, wenn Sie die Lösung bis zum nächsten Morgen nicht gefunden haben.


Zur LOOP-Anweisung gibt es folgende Varianten:
REPEAT-Anweisung:
  REPEAT
    Anweisungsfolge
  UNTIL Ausdruck ;

Die Anweisungsfolge in der REPEAT-Anweisung wird ausgeführt und dann so lange wiederholt, bis die Auswertung des Ausdrucks das Resultat wahr ergibt.

WHILE-Anweisung:
  WHILEAusdruck
  DO
    Anweisungsfolge
  END


Die REPEAT-Anweisung wird auf jeden Fall mindestens einmal ausgeführt. Nach der Ausführung der Anweisungsfolge wird überprüft, ob der Ausdruck wahr ergibt. Bei der WHILE-Anweisung wird zunächst überprüft, ob der Ausdruck den Wert TRUE hat. Nur dann wird die Anweisungsfolge ausgeführt und wiederholt, bis der Ausdruck FALSE ist. Ist der Ausdruck bei der ersten Überprüfung FALSE, so wird die Anweisungsfolge überhaupt nicht ausgeführt.



Übungen:

Seien i,k ganzzahlig, k=0. Was macht die folgende WHILE-Anweisung?
k:=0;  WHILE i > 0 DO i := i DIV 2; k := k + 1 END

Geben Sie eine LOOP-Anweisung an, die äquivalent zu dieser WHILE-Anweisung ist.

Was macht die folgende REPEAT-Anweisung?
k:=0;  REPEAT i := i DIV 2; k := k + 1 UNTIL i<=0
(Hinweis: Untersuchen Sie getrennt die Situationen i>0, i=0, i<0).




In Oberon-2 ist darüber hinaus die foldende Konstruktion definiert:

FOR-Anweisung:
  FOR name := Ausdruck TO Ausdruck [BY Konst.-Ausdruck ] DO
    Anweisungsfolge
  END


Die Anweisung

  FOR v := beg TO end BY step DO statements END

ist äquivalent zu

temp := end; v := beg;
IF step > 0 THEN
  WHILE v <= temp DO statements; v := v + step END
ELSE
  WHILE v >= temp DO statements; v := v + step END
END

Die FOR-Anweisung wird benutzt, wenn eine Anweisungsfolge für eine aufeinanderfolgende Reihe von Werten einer Variable ausgeführt werden soll. Dabei muss name eine Variable von ganzzahligem Typ bezeichnen. Ihr Wert wird auf den des ersten Ausdrucks gesetzt und bei jedem Durchlauf um den Wert der Schrittweite Konst.-Ausdruck verändert, solange der zweite Ausdruck nicht überschritten ist. Der Konstanten-Ausdruck muss denselben Typ haben wie die Variable. Sie darf nicht den Wert 0 haben. Ist keine Schrittweite angegeben, so wird die Schrittweite 1 genommen.



Übungen:

Welche Ausgaben werden durch die folgenden FOR-Anweisungen erzeugt:
a)  FOR I:= 1 TO 10 DO Texts.WriteInt(W,I,20) END
b)  FOR I:= 8 TO 8 DO Texts.WriteInt(W,I,20) END
c)  FOR I:= 10 TO 0 DO Texts.WriteInt(W,I,20) END
d)  FOR I:= 5 TO 0 BY -1 DO Texts.WriteInt(W,I,20) END
e)  FOR I:= 5 TO 0 BY -2 DO Texts.WriteInt(W,I,20) END
f)  FOR I:= 5 TO 10 BY -5 DO Texts.WriteInt(W,I,20) END



Die FOR-Anweisung macht einige Iterations-Konstruktionen einfacher. Sie sollte jedoch nur in trivialen Situationen benutzt werden. In kritischen Situationen ist ihre Bedeutung nicht klar. Z. B. welche Bedeutung sollte folgende (formal zulässige) Konstruktion haben:
...
FOR I:= I-11 TO I+1 DO ... END



Übungen:

1.) Berechnen und tabellieren Sie n! für n=0,... 10

2.) Berechnen und tabellieren Sie n! soweit n! als Zahl vom Typ INTEGER bzw. LONGINT dargestellt werden kann.

3.) Tabellieren Sie für k=1,2,...-soweit als möglich- min {n: n! >= 2k}

4.) Ein linearer Kongruenzgenerator ist ein Pseudo-Zufallszahlengenerator, der nach der Regel
    x -> (ax + b) mod m
Zahlen generiert.
a)  Schreiben Sie ein Programm, dass für Konstanten a, b, m und n jeweils n Pseudo-Zufallszahlen generiert und ausschreibt. Probieren Sie verschiedene Konstanten. Wie wählen Sie einen Startwert ?
b)  Überprüfen und modifizieren Sie ggf. Ihr Programm so, dass es für alle a,x,b,m: MAX(LONGINT)>=a,x>0, MAX(LONGINT)>=b>=0, korrekt läuft.
Generieren Sie jeweils 1000 Pseudo-Zufallszahlen mit folgenden Generatoren:
  (Lewis, Goodman, Miller ) a=75=16807, b=0, m=231-1
  (Payne, Rebung, Bogyo)  a=630360016, b=0, m=231-1
  (UNIX rand)      a=1103515245, b=12345, m=231
  [Literatur: B.D. Ripley, Computer Generation of Random Variables: A Tutorial. International Statistical Review 51 (1983) 301-319;
siehe auch Reiser&Wirth, Kap.2]

5.) Messen Sie die Zeit, die benötigt wird, um 10, 100, 1000, 10000 Zufallszahlen zu generieren. Benutzen Sie dazu das Programmfragment Test2 in Kurs/Time06.Mod . Welche Messungen liegen unterhalb der Mess-Auflösung? Wie verlässlich sind die Messungen?



Die vordefinierte Prozedur HALT gibt eine Möglichkeit, aktuelle Kontrollstrukturen zu durchbrechen und einen Prozess zu verlassen. HALT wird aufgerufen in der Form HALT(status), wobei status ein Wert ist, der der globalen Umgebung zurückgeliefert wird. HALT ist gewissermassen der letzte Fehlerausgang. Oberon-Module sind resident. Dies gilt auch nach einem Abbruch mit HALT: das Modul bleibt geladen, und auf alle exportierten Variablen kann auch nach dem Abbruch zugegriffen werden. Die Behandlung von HALT ist implementationsabhägig. Üblicherweise wird die Kontrolle an das Modul Oberon übergeben, und Oberon öffnet dann ein Fenster mit einer diagnostischen Meldung.

Kontrollanweisungen spielen eine unterschiedliche Rolle in verschiedenen Stadien der Programmentwicklung. Neben den vom Programmierer selbst zu nützenden Kontrollanweisungen gibt es deshalb -je nach Implementierung- weitere Unterstützungen für die Fehlerbehandlung. Die wichtigste ist die ASSERT-Prozedur. Sie wird aufgerufen in der Form ASSERT(Bedingung,status). Ihre Bedeutung ist gleich mit
  IF Bedingung THEN HALT(status) END;
In der Implementierung aber wird sie vom Compiler kontrolliert. In der Regel gibt es eine Compiler-Option, die es erlaubt, die Code-Generierung für ASSERTs an oder abzuschalten. Mit der entsprechenden Option werden ASSERT-Anweisungen generiert und die entsprechenden Prüfungen durchgeführt. Ohne diese Option wird kein ASSERT-Code generiert. Da die ASSERT-Anweisungen vom Compiler verwaltet werden, bieten sie eine Basis für Code-Analyse und Diagnostik. Die Verwendung von ASSERTs und weiteren Prüfungen ist Bestandteil eines eigenen Kapitels im zweiten Durchlauf.

Verschiedene Compiler bieten weitere unterschiedliche Möglichkeiten zur Diagnostik und Programm-Prüfung, die in den entsprechenden Compiler-Unterlagen dokumentiert sind.



Übungen:

Welche Kontroll- und Testmöglichkeiten bietet Ihr Compiler? Für System 3 finden Sie nähere Information in der Datei   Compiler.Tool




Einführung in die Programmiersprache Oberon. Kurs/Kap06.Text
gs (c) G. Sawitzki, StatLab Heidelberg
<http://statlab.uni-heidelberg.de/projects/oberon/kurs/>

Home Up Intro Contents Chapter 1 2 3 4 5 6 7 8 9 10 Design Assert Timing EBNF Report Pas