Oberon-Kurs Kap08 Arrays, Records&Pointer

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>

08 Records, Arrays, Pointer, Objekte

Jede Variable in Oberon hat einen Typ. Der Typ spezifiziert den möglichen Wertebereich für die Variable, legt fest, welche Operatoren anwendbar sind und bestimmt mittelbar, wie die Information der Variablen gespeichert wird und wie gespeicherte Information zu interpretieren ist. In Kapitel 5 haben wir bereits die elementaren Datentypen
BOOLEAN  CHAR
SHORTINT  INTEGER  LONGINT
REAL  LONGREAL
SET
kennengelernt. Diese Typen sind vordefiniert. Oberon erlaubt es, Typen zu kombinieren, Typ-Definitionen zu erweitern und neue Typen zu deklarieren.

Beispiel  0: Eine "universelle" Plot-Prozedur sollte anhand von Wertebereich und zu zeichnender Funktion einen (automatisch skalierten) Plot erzeugen. Geeignete Deklaratione sind:
TYPE
  Function=
    PROCEDURE (x:LONGREAL):LONGREAL;
  ...
  PROCEDURE Plot(from,to:LONGREAL; f: Function);
  BEGIN
    ...
  END Plot;
Beim Aufruf von Plot kann dann irgendeine Prozedur für f übergeben werden, die dem Muster von Function entspricht.
Anstelle Function als neuen Typ zu deklarieren, würde man in diesem einfachen Beispiel den Typ implizit in der Deklaration von Plot definieren, und nur schreiben:
  PROCEDURE Plot(from,to:LONGREAL;
                f: PROCEDURE (x:LONGREAL):LONGREAL);
  BEGIN
    ...
  END Plot;

Beispiel 1: Wir haben im letzten Kapitel drei Zufallsgeneratoren RandLGM, RandPRB und RandUNIX programmiert. Alle drei haben dieselbe Aufrufstruktur:
  PROCEDURE xxxxx(VAR seed:LONGINT): LONGINT;
Wenn wir mit unterschiedlichen Generatoren in einer Simulation experimentieren wollen, ohne jedesmal unser Programm umzuschreiben, so können wir den jeweils aktuellen Generator in einer Variablen notieren, genau wie wir es mit Startwerten oder Parametern machen würden. Dazu deklarieren wir
TYPE
  GeneratorProc =
    PROCEDURE (VAR seed:LONGINT): LONGINT;
  ...
VAR
    NextRandom: GeneratorProc;
    GlobalSeed:LONGINT;
Mit diesen Deklarationen ist ein neuer Typ GeneratorProc eingeführt, der gleichrangig mit allen vordefinierten Typen ist. Dieser Typ wird dann z.B. bei der Deklaration der Variablen NextRandom benutzt. Nach einer Zuweisung
    NextRandom:=RandLGM;
liefert dann NextRandom(GlobalSeed) die nächste Zufallszahl, berechnet mit dem LGM-Generator. Setzen wir
    NextRandom:=RandPRB;
so liefern die nachfolgende Aufrufe von NextRandom(GlobalSeed) Zufallszahlen, berechnet mit dem PRB-Generator.

Beispiel 2: Wir können weitergehen und den aktuellen Startwert eines Zufallszahlengenerators mit der Berechnungsfunktion bündeln. Das erlaubt es auf einfache Weise, verschiedene Zufallszahlengeneratoren reproduzierbar zu kontrollieren. Dazu deklarieren wir:
TYPE
  GeneratorProc
    = PROCEDURE (VAR seed:LONGINT): LONGINT;
    GeneratorType = RECORD
      seed:LONGINT;
      NextRandom: GeneratorProc
    END
  ...
  VAR
    Generator,Generator1,Generator2,...: GeneratorType;
Dann können wir die Generatoren zum Beispiel initialisieren mit
    Generator1.NextRandom:=RandPRB;
    Generator1.seed:=Oberon.Time();
    Generator2.NextRandom:=RandLGM;
    Generator2.seed:=Oberon.Time();
und mit Generator:=Generator1 bzw. Generator:=Generator2 auf den ersten oder zweiten Generator schalten. Um auf die jeweils aktuelle Berechnungsfunktion zuzugreifen, rufen wir jetzt
    Generator.NextRandom(Generator.seed).

Beispiel 3: Um räumliche Prozesse zu simulieren, wollen wir auf Vektoren und Matritzen zugreifen. Wir können diese wie in Beispiel 2 realisieren, etwa mit
  TYPE
    VectorType = RECORD
      x,y,z:REAL
    END;
aber schon einfache lineare Algebra wird damit umständlich. Wir können anstelle dessen deklarieren:
  TYPE
    VectorType = ARRAY 3 OF REAL;
    MatrixType = ARRAY 3,3 OF REAL;
  VAR
    v:VectorType; m:MatrixType;
Auf die i. bzw. i,j. Komponente greifen wir dann zu mit v[i] bzw m[i,j]. Die Komponentenzählung beginnt immer bei null, das heisst v hat hier die Komponenten v[0], v[1], v[2].

Beispiel 4: Für jeden Typ können wir einen Zeiger-Typ definieren. Dieser Typ kann eine Referenz aufnehmen, ähnlich einem "vorwärts" oder "weiter"-Zeiger in einem Hypertext. In der Referenz werden nicht Daten selbst gespeichert, sondern nur ein Verweis, mithilfe dessen auf die Daten zugegriffen werden kann. Eine häufige Verwendung ist es, einen entsprechenden Zeiger gleich in eine Datenstruktur einzubetten. Bei Zeiger-Deklationen ist es ausnahmsweise möglich, ein Objekt zu benutzen, bevor es deklariert ist.
    TYPE
      InfoPointer= POINTER TO InfoPage;
      InfoPage= RECORD
        .. viel Information...;
        NextPage: InfoPointer
      END;

Die formalen Syntax-Definitionen sind
Typen-Deklaration:
  TYPE {Name = Typ;}
Typ
  Typ-Name|Array-Typ| Record-Typ | Pointer-Typ | Prozedur-Typ
Arrays (Vektoren, Matritzen, Tensoren,...) bestehen aus einer (festen) Anzahl von Elementen eines einheitlichen Typs. Unter der Länge eines Arrays versteht man die Anzahl seiner Elemente. Als Parametertypen in Prozeduren können auch offene Arrays, das heisst Arrays ohne Längenangabe benutzt werden. In Oberon-2 ist es auch möglich, offene Array-Typen zu deklarieren.
Array-Typ:
  ARRAY [Länge {, Länge}] OF Typ
Länge :
  konstanter Ausdruck
Die einzelnen Elemente werden durch ihren Index identifiziert, beginnend mit dem Index 0 und endend mit (Länge-1).
Array-Element:
  Array-Name [ index] {[ index] }
Array-Elemente sind Variable, mit denen gearbeitet werden kann wie mit anderen Variablen auch. Der Unterschied zu üblichen Variablen ist, dass Array-Elemente keine individuallen Namen haben: sie sind im Array zusammengefasst und durch Arraynamen und Index innerhalb des Array identifiziert.
Die Elemente von Arrays können jeden Typ haben, insbesondere -wie hier- auch wieder Arrays sein. Damit ist eine Konstruktion möglich wie:
  TYPE
    VectorType  =  ARRAY maxdim OF REAL;
    MatrixType  =  ARRAY maxdim OF VectorType;
    TensorType  =  ARRAY maxdim OF MatrixType;
Damit können Arrays in höheren Dimensionen definiert werden. Die Elemente können auch von anonymem Typ sein. Die Schreibweise
  ARRAY L0, L1, ..., Ln OF T
ist eine Abkürzung für
  ARRAY L0 OF
    ARRAY L1 OF
    ...
      ARRAY Ln OF T
Für den Zugriff auf Elemente in einem mehrdimensionalen Array kann zur Abkürzung eine Index-Liste angegeben werden; zum Beispiel A[i,j,k] anstelle von A[i][j][k].

Beispiel:
  TYPE tMATRIX= ARRAY 2,2 OF REAL;

Übungen:

Welchen Typ haben die folgenden Terme
  x[i]    A[i]  T[i]    T[i,j]
wenn die Variablen wie folgt definiert sind:
  VAR   x,y: VectorType;
      A: MatrixType;
      T:TensorType;
      i,j:INTEGER;

Schreiben Sie das Beispiel Kurs/PIO/IFS.Mod als Operation einer 2*2-Matrix und eines 2-d Verschiebungsvektors auf 2-Vektoren.

Ein Array hat eine feste (möglicherweise offene) Anzahl von Elementen eines einheitlichen Typs, die durch ihren Index identifiziert werden. Im Unterschied dazu hat ein Record-Typ eine feste Anzahl von Elementen (Feldern), möglicherweise unterschiedlichen Typs, die durch ihren Namen identifiziert werden.

Record-Typ:
  RECORD [ ( Basis-Typ ) ]
     [Feld-Liste {; Feld-Liste}]
  END
Basis-Typ:
  Record-Name
Feld-Liste:
  Namens-Liste : Typ
Die einzelnen Elemente werden durch ihren qualifizierten Namen identifiziert.
Record-Feld:
  Variablen-Name.Feld-Name
Ein Record-Typ kann einen zuvor definierten Record-Typ erweitern. Der neue Record-Typ "erbt" dann vom Basis-Typ alle Felder und erhält zusätzlich die neu definierten.
Beispiel:
  Time= RECORD
    Hour, Min, Sec : SHORTINT
  END;
  TimeAndDate = RECORD (Time)
    Month,Day:SHORTINT;
    Year:INTEGER
  END;

In Oberon gibt es immer höchstens einen Basis-Typ für jeden Typ. Auf Typ-Erweiterungen kommen wir in einem späteren Kapitel (Kapitel 9) zurück.

Einzelne Felder werden in der Form
  RecordVarName.FeldName
angesprochen, also für eine Variable t vom Typ Time etwa t.Hour, t.Min, t.Sec.

Wird ein Record-Typ exportiert, so sind damit noch nicht die einzelnen Felder sichtbar. Jedes Feld, das nach ausserhalb des umgebenden Moduls sichtbar sein soll, muss ausdrücklich gekennzeichnet sein.

Variablen vom Zeiger-Typ (Pointer-Typ) nehmen als Werte Verweise auf andere Variablen auf. Ein Zeiger-Typ ist dabei immer an einen Bezugstyp, den Basis-Typ des Zeigers, gebunden.
Pointer-Typ:
  POINTER TO Typ
Der Typ kann dabei ein Array-Typ oder ein Record-Typ sein, das heisst Zeiger auf elementare Typen sind nicht vorgesehen. Alle Pointer können als Wert auch NIL haben. NIL ist ein reservierter Wert, der in der Bedeutung von nichts,nirgendwo benutzt wird. NIL wird häufig auch benutzt, um eine Pointer-Variable als undefiniert zu markieren.
Standardmässig sind in Oberon alle Variable zunächst mit (zufälligen) undefinierten Werten besetzt. POINTER sind die Ausnahme. POINTER-Variable werden immer mit dem Wert NIL vorbesetzt.

Variable vom Prozedur-Typ haben eine Prozedur oder NIL als Wert. Wenn eine Prozedur als Wert zugewiesen wird, muss die formale Parameterliste zu der bei der Typdeklaration angegebenen passen.
Prozedur-Typ
  PROCEDURE [ Formale Parameterliste ]

Wird ein Typ in einer Typ-Deklaration eingeführt, so bekommt der Typ einen Namen, der ihn identifiziert. Typen, die einen Namen bekommen haben, nennen wir deklarierte Typen. Ein Typ kann auch ad-hoc in einer Variablen-Deklaration oder einer Parameterliste eingeführt werden. Dann bleibt der Typ anonym, nur die deklarierte Variable hat einen Namen.

Beispiel:
  VAR  W: ARRAY 3 OF REAL;
  ...
  W[0]:=0; W[1]:=0; W[2]:=2.5;

Durch die Typen ist festgelegt, welche Verträglichkeiten zwischen Variablen bestehen. Dabei gibt es abgestufte Anforderungen für Zuweisungen, Verwendung in Operationen und Verwendung als Parameter.

Zuweisungs-Verträglichkeit

Für Zuweisungen gilt als Faustregel: Ein Ausdruck ist mit einer Variablen zuweisungsverträglich, wenn die Zuweisung
  Variable:=Ausdruck
eine sichere natürliche Interpretation hat. Zuweisungen zwischen zwei Variablen mit demselben erklärten Typ sind immer möglich.
1) wenn die Variable und der Ausdruck denselben Typ haben
2) wenn Variable und Ausdruck numerisch sind, und der Typ der Variablen den des Ausdrucks umfasst. (Ein ganzzahliger Ausdruck kann einer reellen Variablen zugewiesen werden. Umgekehrt nicht: eine reeller Wert muss erst gerundet oder abgeschnitten werden, bevor er einer ganzzahligen Variablen zugewiesen wird).
3) wenn Ausdruck und Variable einen Record-Typ haben, und der Typ des Ausdrucks eine Erweiterung des Variablen-Typs ist. (Umgekehrt nicht: eine Erweiterung kann Felder haben, die im ursprünglichen Typ nicht definierte sind. Der Grund-Typ kann nicht einer echten Erweiterung zugewiesen werden.
4) wenn Ausdruck und Variable Zeiger auf einen Record-Typ sind und 3) entsprechend gilt.
5) wenn der Ausdruck NIL ist und die Variable einen Zeiger- oder Prozedurtyp hat
6) wenn die Variable einen Typ ARRAY OF CHAR hat und der Ausdruck eine String-Konstante ist, die höchstens soviele Stellen hat, wie die Variable aufnehmen kann.
7) wenn die Variable von einem Prozedur-Typ und der Ausdruck der Name einer Funktion mit passender formaler Parameterliste ist.

Die Zuweisung ist in der Regel nicht möglich, wenn Variablen nicht denselben erklärten Typ haben, selbst dann, wenn sie die gleiche Struktur haben.
Beispiel:
  TYPE
    Location  = ARRAY [3] OF REAL;
    Speed    =ARRAY [3] OF REAL;
    NewLocation = Location;
  VAR
    PosA,PosB  : Location;
    VA,VB    : Speed;
    NPos    : NewLocation;
    ...
    :::
    PosA[0]:=0; PosA[1]:=0; PosA[2]:=2.5;
    ...
    PosB := PosA;
      (* erlaubt. Typen sind zuweisungs-verträglich *)
      (* VA:=PosA;  nicht erlaubt. Die gleiche Struktur,
       aber nicht zuweisungs-verträglich *)
    NPos := PosB;
      (* erlaubt. Typen sind zuweisungs-verträglich *)

    VA[0]:=PosA[0];
      (* erlaubt. Typen der Elemente sind
       zuweisungs-verträglich *)

Ergänzungen zu Basistypen

Ein Grundtyp T2 ist zuweisungs-verträglich zu einem Grundtyp T1, wenn T2 in T1 "enthalten" ist, entsprechend der folgenden Ordnung:
LONGREAL >= REAL >= LONGINT >= INTEGER >= SHORTINT

Bei arithmetischen Ausdrücken findet eine automatische Umwandlung statt, wenn diese eindeutig ist. In diesem Fall nennt man die Typen ausdrucks-verträglich. Das Ergebnis ist vom kleinsten Grundtyp, der das Resultat darstellen kann.

Mit der vordefinierten Funktion SHORT wird -falls möglich- eine Konversion zu einem kleineren Zahlentyp erzwungen, mit LONG eine Expansion zu einem grösseren Zahlentyp. Mit ENTIER erhält man zu einer reellen Zahl x die grösste ganze Zahl <= x.

Beispiel:  ENTIER(17/4)  ergibt 4

Ergänzungen zu Arrays

Die vordefinierte Funktion
  LEN(a,n)
gibt die Länge von a in der Dimension n. LEN(a) ist eine Kurzform von LEN(a,0). In Oberon ist also die Grösse eines Arrays zur Ausführungszeit eines Moduls mit Hilfe von LEN abfragbar.

Eine typische Schleife über alle Elemente eines Vektors, geschrieben mit der LEN Funktion ist etwa:

i:=0;
WHILE i< LEN(a) DO
  a[i]:=a[i]*2;
  INC(i)
END;

Diese Schleife ist äquivalent zu:
  FOR i:=0 TO LEN(a)-1 DO a[i]:=a[i]*2 END;

Die Verwendung der WHILE-Konstruktion ist in Oberon für den Durchlauf von Arrays empfohlen.

Array-Typen können auch ohne Angabe der Länge deklariert werden. Arrays ohne explizite Längenangaben heissen offene Arrays. In Oberon können offene Array als Parameter für Funktionen benutzt werden. Oberon-2 erlaubt auch die Definition von Variablen als offene Arrays. Offene Arrays können in Zusammenhang mit der Funktion LEN benutzt werden, um flexible Prozeduren für die lineare Algebra zu implementieren.

Beispiel:
PROCEDURE MaxDiag(A: ARRAY OF ARRAY OF REAL;
            VAR Val:REAL);
  VAR i:INTEGER;
  BEGIN
    Val:=0;   i:=0;
    WHILE i< LEN(A) DO
      IF ABS(A[i,i])>Val THEN Val:=ABS(A[i,i]) END;
      INC(i)
    END
  END MaxDiag;

Wird ein Array wie in diesem Beispiel als Wert-Parameter übergeben, so wird die gesamte Information bei Aufruf der Prozedur auf eine lokale Variable kopiert. Dies ist bei allen Wert-Parametern der Fall. Im Gegensatz dazu wird bei VAR-Parametern immer nur ein Verweis übergeben. Insbesondere Arrays beinhalten oft grosse Informationsmengen. Das Kopieren ist dann zeit- und platzaufwendig. Deshalb ist es üblich, sie auch dann als VAR-Parameter zu übergeben, wenn sie nicht verändert werden.
Beispiel:
  PROCEDURE MaxDiag(VAR A: ARRAY OF ARRAY OF REAL; VAR Val:REAL);

Übungen:

Schreiben Sie eine Prozedur, die das Skalarprodukt von zwei Vektoren A,B ausrechnet und das Resultat einer Variablen C zuweist:
  PROCEDURE SKALPROD(VAR A,B: ARRAY OF REAL;
    VAR C: REAL);
Benutzen Sie diese Prozedur, um das Skalarprodukt der folgenden Vektoren zu berechnen:
  A[i]:= sin(i* (2*pi)/n)  B[i]:= cos(i* (2*pi)/n)
für n=1, ..., 10 mit i=0,...,n-1.
Hinweis: Sinus und Cosinus finden Sie im Modul Math.

Neben der Repräsentation von geometrischen Objekten wie Vektoren ist eine typische Anwendung von Arrays die Repräsentation von (rechteckigen) Tabellen mit Information. Im Unterschied zu den bisherigen Beispielen muss dabei nicht immer die gesamte Tabelle durchgearbeitet werden, sondern Schleifen laufen zum Beispiel nur so lange bis ein bestimmtes Element gefunden ist.

Beispiel: Suche den Index j eines Eintrags mit dem Wert x in einer Tabelle t
  TYPE Table= ARRAY n OF INTEGER;
  VAR t:Table; j,x:INTEGER;
..
  j:=0;
  WHILE (j<n) & (t[j]#x) DO INC(j) END;

Im obigen Beispiel ist
  j:=0;
  WHILE (t[j]#x) & (j<n) DO INC(j) END;
nicht korrekt. Warum?

Ergänzungen zu Records

Zuweisungen von einem Record-Typ T1 zu einem Typ T0 sind möglich, wenn T1 den Typ T0 erweitert. Die Zuweisung überträgt dann nur die Felder, die bereits in T0 enthalten sind. Beispiel:
  VAR
    t: Time;
    ta,tb: TimeAndDate;
  ...
    t:=ta;  (* erlaubt. Überträgt Hour, Min, Sec *)
  ...
    tb:=ta;   (* erlaubt. Überträgt alle Felder *)
  ...
(*    ta:=t  nicht erlaubt *)
    ta.Hour:=t.Hour;  (* erlaubt.
      Zuweisung von Variablen des
      gleichen Basistyps *)

Die Regeln der Typ-Erweiterung gelten analog für Zeiger: ist Typ1 eine Erweiterung von Typ0, so ist ein Zeiger auf Typ1 eine Erweiterung eines Zeigers auf Typ0.

Ergänzungen zu Pointer-Variablen

Wird eine Variable P vom Zeiger-Typ deklariert, so wird damit nur der Speicherplatz für den Verweis bereitgestellt, und noch kein Platz für eine Variable vom Basis-Typ. Der Platz für die bezeichnete Variable wird erst durch einen Aufruf der vordefinierten Prozedur NEW bereitgestellt, zum Beispiel NEW(P).
NEW versucht, den Platz für die Variable bereitzustellen. Konnte der Platz bereitgestellt werden, so wird in P ein Verweis auf diese neue Variable gespeichert. Auf die bezeichnete Variable kann dann mit P^ zugegriffen werden. Konnte kein Platz bereitgestellt werden, so ist das weitere Verhalten implementationsabhängig. Konnte der Platz nicht bereitgestellt werden, so hat P den Wert NIL.
Der einfache Aufruf von NEW stellt eine Variable fester Länge bereit. Ist der Basis-Typ ein offenes ARRAY, so wird mit NEW(P,e0, ..., en-1) eine Matrix der Längen e0, ..., en-1 bereitgestellt.
Jeder Variablen vom Zeiger-Typ kann der Wert NIL zugewiesen werden; NIL verweist auf keine Variable.
Ist der Basis-Typ ein RECORD-Typ, so kann auf die Komponenten mit einer Kurzschreibweise zugegriffen werden, zum Beispiel mit
  P:  POINTER TO Time;  (* Time wie oben *)
ist
  P.Hour  kurz für   P^.Hour.
(Analog kann für den Zugriff auf Felder die Kurzschreibweise verwandt werden, zum Beispiel p[i,j,k] anstelle von p^[i,j,k]).

Einführung in die Programmiersprache Oberon. Kurs/Kap08.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