Die Computerseite von Eckart Winkler
Prozedurtypen in Modula-2

 

Dieser Artikel ist im Heise-Verlag in der Zeitschrift "c't", Ausgabe 05/1989 erschienen.
 



Erläuterung

In den meisten Programmiersprachen ist ein Variablen-Mechanismus vorhanden, der es dem Benutzer gestattet, Daten im Speicher abzulegen, um sie später zu benutzen. Zur Erleichterung in der Handhabung kann man den betreffenden Speicherstellen Namen geben und sie durch Angabe von diesen bezeichnen. Im Normalfall braucht man die Lage dieser Stelle im Speicher nicht zu kennen.

Übliche Datentypen, die auf diese Weise verwendet werden können, sind Zahlen, Zeichen und Zeichenketten oder zusammengesetzte Daten wie Arrays, Records, Listen, Bäume usw. In Modula-2 besteht darüber hinaus die Möglichkeit, sog. Prozedurtypen zu vereinbaren. In diesem Fall können wir einer Variablen eine Prozedur oder Funktion zuweisen. Um eine derartige Prozedur zur Ausführung zu bringen, können wir den Variablennamen genauso verwenden, wie wir das mit dem Originalnamen getan hätten.


Definition im Programm

Wie wird so etwas durchgeführt? Betrachten wir hierzu den Typ einer mathematischen Funktion, die z.B. von dem Modul MathLib exportiert wird. Eine solche Funktion hat ein reelles Argument und liefert eine reelle Zahl. Dies kennzeichnen wir durch die Typbezeichnung PROCEDURE(REAL):REAL. Etwa in einer TYPE-Anweisung könnten wir schreiben: TYPE FUNC = PROCEDURE(REAL):REAL. Ist diese Zeile vorhanden, können wir eine Variable f mit dem Typ FUNC vereinbaren. Dies geschieht so, wie wir es gewohnt sind, nämlich durch VAR f:FUNC. Der Variablen f können wir nun durch f:=sin die Sinusfunktion zuweisen, die wir aus MathLib importiert haben. Der Aufruf f(1.0) wird nun das Ergebnis 0.841471 liefern, genauso wie sin(1.0).

Solange das alles im selben Programmteil stattfindet, ist es wohl nicht mehr als eine Spielerei. Interessant wird es hingegen, wenn Prozedurvariablen an andere Prozeduren übergeben werden. Dann wird es nämlich möglich, Algorithmen für eine ganze Klasse von Funktionen zu formulieren, ohne daß die tatsächlich auftretenden Funktionen bekannt sein müssen.


Beispiel aus der numerischen Mathematik

Dies kann leicht bei Algorithmen aus der numerischen Mathematik benutzt werden. Im folgenden ist ein Beispiel hierfür angegeben. Die betrachteten mathematischen Funktionen sind jeweils von einer reellen Variablen abhängig und liefern einen reellen Wert. Sie haben also den eben schon betrachteten Typ PROCEDURE(REAL):REAL. In einer TYPE-Anweisung wird diesem der Name FUNC gegeben.

MODULE Nullstellen;

FROM MathLib IMPORT sin;
FROM InOut IMPORT WriteString, WriteLn;
FROM RealInOut IMPORT ReadReal, WriteReal;

TYPE FUNC = PROCEDURE(REAL):REAL;

VAR a,b,y : REAL;
    m : BOOLEAN;
    f : FUNC;

PROCEDURE RegFal(a,b:REAL;f:FUNC;VAR y:REAL;VAR m:BOOLEAN);
  (* Berechnet eine Nullstelle y der Funktion f mit den Anfangswerten
  a und b mittels der Regula Falsi. Bei Erfolg wird in m TRUE zurueck-
  geliefert, sonst FALSE. In diesem Fall wird sich ein zufaelliger Wert
  in y befinden. Die angestrebte Genauigkeit ist auf 1E-6 festgelegt,
  und es werden hoechstens 20 Iterationen durchgefuehrt. *)
  CONST eps=1.0E-6; n=20;
  VAR x0,x1,r : REAL;
      i : INTEGER;
  BEGIN
    x0:=a; x1:=b;
    FOR i:=1 TO n DO
      r:=x1-f(x1)*(x1-x0)/(f(x1)-f(x0));
      x0:=x1; x1:=r;
      IF ABS(x1-x0)<eps THEN
        m:=TRUE; y:=x1; RETURN
      END (* IF *)
    END; (* FOR *)
    m:=FALSE
  END RegFal;

BEGIN (* Hauptprogramm *)
  f:=sin;
  WriteString('a='); ReadReal(a); WriteLn;
  WriteString('b='); ReadReal(b); WriteLn;
  WHILE a<b DO
    RegFal(a,b,f,y,m);
    IF m THEN
      WriteReal(y,15,8)
    ELSE
      WriteString('Keine Nullstelle')
    END; (* IF *)
  WriteLn;
  WriteString('a='); ReadReal(a); WriteLn;
  WriteString('b='); ReadReal(b); WriteLn;
  END (* WHILE *)
END Nullstellen.

Bei diesem Programm geht es darum, eine Nullstelle einer Funktion f numerisch zu berechnen. Wir verwenden hierfür den Algorithmus der Regula Falsi. Dabei sind in jedem Iterationsschritt zwei Werte vorhanden, wir nennen sie x1 und x0. x1 soll am Ende als Lösung ausgegeben werden. Der neue Wert von x1 wird jeweils durch den Ausdruck x1-f(x1)*(x1-x0)/(f(x1)-f(x0)) berechnet. x0 erhält den bisherigen Wert von x1.

Realisiert ist dies in der Prozedur RegFal. Sie hat fünf Parameter mit den folgenden Bedeutungen: a und b sind die Anfangswerte des Algorithmus. Sie werden gleich zu Beginn an x0 und x1 zugewiesen. f ist die Funktion, um die es geht. Sie hat den Typ FUNC, den wir soeben vereinbart haben. In y wird das Resultat zurückgeliefert. In m findet der Anwender eine logische Variable, die ihn über Erfolg (TRUE) oder Mißerfolg (FALSE) des Verfahrens informiert.

Die Konstante eps gibt die gewünschte Genauigkeit an, n die Maximalzahl an Iterationen. Für uns sind zwei Stellen von Interesse. Zum einen die Parameterliste, in der f in derselben Weise wie alle anderen Parameter angegeben ist. Zum anderen die Anweisung, in der der jeweils nächste Iterationswert berechnet wird. Hier wird f wie eine real existierende Funktion behandelt.

Das Hauptprogramm fragt in einer WHILE-Schleife jeweils die Anfangswerte a und b ab. Solange a<b ist, wird die Prozedur RegFal aufgerufen. Falls eine Lösung gefunden wurde, wird diese ausgegeben. Interessant sind wieder zwei Stellen: In der ersten Zeile des Hauptprogramms wird an f die Funktion sin zugewiesen. Beim Aufruf von RegFal wird dieses f als Argument übergeben. Wir könnten auch diese zwei Schritte zu einem zusammenfassen, indem wir einfach sin in die Argumentliste schreiben.

Eine Einschränkung ist in diesem Zusammenhang zu beachten: Eine Prozedurvariable darf keine Standardfunktion als Wert annehmen. In unserem Fall wäre etwa die Funktion ABS in Frage gekommen, die für reelle Argumente auch reelle Werte liefert. Diese ist jedoch nicht gestattet. Die Funktion sin ist hingegen keine Standardprozedur, sie wird ja aus dem Modul MathLib importiert.

Ein mathematischer Algorithmus, wie wir ihn jetzt kennengelernt haben, ist wohl die häufigste Anwendung dieses Konzepts. Daher sind auch in der hauptsächlich von Mathematikern genutzten Sprache Fortran ähnliche Mittel bereitgestellt. Gebiete, die sich so leicht behandeln lassen, sind neben der Berechnung von Nullstellen die numerische Differentiation und Integration, nichtlineare Gleichungssysteme sowie Differentialgleichungen.


Beispiel zur Verarbeitung von Arrays

Es sind jedoch genügend andere Anwendungen denkbar, bei denen die Verwendung von Prozedurtypen eine einfach zu handhabende Alternative darstellt. Im folgenden wollen wir einige Prozeduren programmieren, die gewisse Elemente eines Arrays behandeln. Welche Elemente das sind, wird durch eine Bedingung festgelegt, die als Prozedurtyp übergeben wird. Hier ist das zugehörige Programm:

MODULE Felder;

FROM InOut IMPORT Write, WriteInt, WriteLn;

TYPE Bedingung = PROCEDURE(INTEGER):BOOLEAN;

VAR A : ARRAY[1..20] OF INTEGER;

PROCEDURE sum(VAR A:ARRAY OF INTEGER; B: Bedingung):INTEGER;
  VAR i,s : INTEGER;
  BEGIN
    s:=0;
    FOR i:=0 TO HIGH(A) DO
      IF B(A[i]) THEN s:=s+A[i] END
    END; (* FOR *)
    RETURN s
  END sum;

PROCEDURE out(VAR A:ARRAY OF INTEGER; B:Bedingung);
  VAR i : INTEGER;
  BEGIN
    Write('[');
    FOR i:=0 TO HIGH(A) DO
      IF B(A[i]) THEN WriteInt(A[i],3) END
    END; (* FOR *)
    Write(']')
  END out;

PROCEDURE all(x:INTEGER):BOOLEAN;
  BEGIN
    RETURN TRUE
  END all;

PROCEDURE odd(x:INTEGER):BOOLEAN;
  (* x ungerade? *)
  BEGIN
    RETURN ODD(x)
  END odd;

PROCEDURE positiv(x:INTEGER):BOOLEAN;
  (* x positiv? *)
  BEGIN
    RETURN x>0
  END positiv;

PROCEDURE prim(x:INTEGER):BOOLEAN;
  (* x prim? *)
  VAR i : INTEGER;
  BEGIN
    IF x<2 THEN RETURN FALSE END;
    FOR i:=2 TO (x DIV 2) DO
      IF (x DIV i)*i=x THEN RETURN FALSE END
    END; (* FOR *)
    RETURN TRUE;
  END prim;

PROCEDURE Init(VAR A:ARRAY OF INTEGER);
  VAR i : INTEGER;
  BEGIN
    FOR i:=0 TO HIGH(A) DO
      IF ODD(i) THEN A[i]:=i*i DIV 9 ELSE A[i]:=2*i-13 END
    END (* FOR *)
  END Init;

BEGIN (* Hauptprogramm *)
  Init(A);
  out(A,all); WriteLn;                (* Ausgabe aller Elemente *)
  out(A,prim); WriteLn;               (* Ausgabe der primen Elemente *)
  WriteInt(sum(A,odd),3); WriteLn;    (* Summe der ungeraden Elemente *)
  WriteInt(sum(A,positiv),3); WriteLn (* Summe der positiven Elemente *)
END Felder.

Zunächst definieren wir den Typ einer Bedingung. Da unser Array Integer-Zahlen beinhalten soll, muß das Argument der Bedingung ebenfalls eine Integer-Zahl sein. Geliefert wird ein logischer Wert. Das Feld A soll als Testobjekt dienen.

Es folgen nun die zwei Prozeduren sum und out, die zur Behandlung eines Arrays vorgesehen sind. In der Parameterliste steht jeweils als erstes das betreffende Feld A. Es wird als offenes Feld vereinbart, deshalb muß davor das Wort VAR stehen. Außerdem wird eine Bedingung B angegeben, die den eben definierten Typ hat.

Die Prozedur sum soll alle Elemente des Arrays summieren, die der Bedingung genügen. Der Wert wird zurückgegeben. out gibt alle durch B selektierten Werte auf dem Bildschirm aus. Der Aufbau beider ist recht ähnlich. In einer FOR-Schleife werden alle Elemente angesprochen. Bei offenen Arrays ist die Untergrenze immer 0, die Obergrenze wird von der Standardfunktion HIGH ermittelt. Die IF-Abfrage stellt sicher, daß das jeweilige Element die Bedingung erfüllt. Im ersten Fall wird dann der Wert zur Variablen s hinzuaddiert, im zweiten Fall mittels WriteInt ausgegeben.

An Unterschieden sind ansonsten nur Kleinigkeiten zu nennen: In der Prozedur sum muß s mit 0 initialisiert werden, am Ende wird der Wert von s mit RETURN zurückgegeben. Bei out werden am Beginn und am Ende eckige Klammern ausgegeben, um die Zusammengehörigkeit der Zahlen zu betonen.


Bedingungen

Wir kommen nun zu den Bedingungen, die natürlich alle den Typ PROCEDURE(INTEGER):BOOLEAN haben müssen. Getestet wird jeweils eine Eigenschaft der übergeben Integer-Zahl, das logische Ergebnis zurückgegeben. Am Anfang steht eine Prozedur, die die Behandlung aller Feldelemente ermöglichen soll. Daher wird unabhängig von x immer TRUE ausgegeben.

Die Bedingungen odd und positiv sind sehr einfach, hier wird lediglich der notwendige Ausdruck ODD(x) bzw. x>0 hingeschrieben. Wie wir wissen, ist ja die Verwendung der Standardprozedur ODD als Parameter nicht gestattet. Die Prozedur prim prüft, ob das Argument eine Primzahl ist. Um diese Eigenschaft festzustellen, werden die Zahlen von 2 bis zu (x DIV 2) auf Teilerschaft überprüft.

Die Summe aller Feldelemente von A, die der Bedingung B genügen, erhalten wir nun mit sum(A,B). Ausgeben können wir alle Elemente, für die B gilt, durch out(A,B). Derartige Konstruktionen wollen wir im Hauptprogramm benutzen. Hierfür benötigen wir jedoch noch die Prozedur Init. Hier wird das Feld A mit Werten belegt, um im Hauptprogramm einen Effekt zu erzielen.

Dort wird das Feld A zunächst initialisiert, sodann mehrere Elemente ausgegeben, schließlich die ungeraden bzw. positiven Elemente summiert. Bei Bereitstellung geeigneter Prozeduren könnten auf dieselbe Art gewisse Elemente multipliziert, ebenso könnten Maximum und Minimum bestimmt werden, oder man könnte selektiv Elemente ändern.


Prozeduren

Haben wir bisher nur Prozedurtypen besprochen, die in Pascal als Funktionen bezeichnet werden, so sind auch Prozeduren, die ihre Argumente ändern, von diesem Konzept nicht ausgeschlossen. Wie üblich, ist auch hier das Wort VAR nötig. In folgendem Programm geht es um die Codierung von Texten durch verschiedene Verfahren.

MODULE Code;

FROM InOut IMPORT ReadString, WriteString, WriteLn;

TYPE MethTyp = PROCEDURE(VAR CARDINAL,CARDINAL);

VAR E,Z : ARRAY[0..59] OF CHAR;
    i : INTEGER;

PROCEDURE code(Meth:MethTyp;VAR E,Z:ARRAY OF CHAR);
  VAR a,i : CARDINAL;
  BEGIN
    FOR i:=0 TO HIGH(Z) DO
      a:=ORD(E[i]);
      IF (a>=65) AND (a<=90) THEN
        Meth(a,i); WHILE a>90 DO a:=a-26 END
      ELSIF (a>=97) AND (a<=122) THEN
        Meth(a,i); WHILE a>122 DO a:=a-26 END
      END; (* IF *)
      Z[i]:=CHR(a)
    END (* FOR *)
  END code;

PROCEDURE Meth1(VAR a:CARDINAL;i:CARDINAL);
  CONST n=5;
  BEGIN
    a:=a+n
  END Meth1;

PROCEDURE Meth2(VAR a:CARDINAL;i:CARDINAL);
  BEGIN
    a:=a+i
  END Meth2;

PROCEDURE Meth3(VAR a:CARDINAL;i:CARDINAL);
  CONST n=5;
  BEGIN
    IF ODD(a+i) THEN a:=a+n ELSE a:=a+i END
  END Meth3;

BEGIN (* Hauptprogramm *)
  FOR i:=1 TO 10 DO
    WriteString('Eingabe : '); ReadString(E); WriteLn;
    code(Meth1,E,Z); WriteString('Meth.1  : '); WriteString(Z); WriteLn;
    code(Meth2,E,Z); WriteString('Meth.2  : '); WriteString(Z); WriteLn;
    code(Meth3,E,Z); WriteString('Meth.3  : '); WriteString(Z); WriteLn;
    WriteLn; WriteLn
  END (* FOR *)
END Code.

Besprechen wir zunächst die Prozedur code, die die Codierung eines Zeichenfelds vornimmt. Als erstes Element wird eine Prozedur übergeben, die die Codierung eines Zeichens vornimmt. Parameter Nummer 2 ist der Ausgangsstring, im letzten Parameter wird das Resultat der Verschlüsselung zurückgegeben. Beide sollten mit derselben Länge vereinbart werden.

In einer Schleife über alle Feldelemente wird nun zunächst der ASCII-Code des jeweiligen Zeichens ermittelt. Bewegt sich dieser zwischen 65 und 90, ist das Zeichen ein Großbuchstabe, und wir wenden das Verschlüsselungsverfahren darauf an. An die Prozedur wird neben a auch der Laufindex i übergeben, aber nur a wird geändert. Wir vereinbaren auch, daß a durch die Prozedur Meth nur vergrößert werden darf. Wir wollen nämlich erreichen, daß ein Großbuchstabe auf einen Großbuchstaben abgebildet wird. Ist a durch die Codierung größer als 90 geworden, wird so lange 26 abgezogen, bis das nicht mehr der Fall ist.

Analog werden Kleinbuchstaben behandelt, deren ASCII-Codes von 97 bis 122 reichen. Alle anderen Zeichen werden nicht verändert. Am Ende wird das Zeichen, das dem neuen ASCII-Code a entspricht, in das Feld Z geschrieben.

Der Typ einer Prozedur, die die Veränderung eines ASCII-Codes vornimmt, muß also zwei Cardinal-Parameter haben, der erste muß verändert werden, also durch VAR gekennzeichnet. Dies schreibt man einfach als PROCEDURE(VAR CARDINAL,CARDINAL).

Drei Verschlüsselungsverfahren sind vorgesehen. das erste ist unabhängig von der Lage eines Zeichens im String. Es wird jeweils eine Konstante n, hier 5, zu a addiert. Es ergibt sich somit eine einfache Verschiebung um 5. Aus A wird F, aus B wird G, usw. Die letzten 5 Buchstaben des Alphabets werden an den Anfang abgebildet, z.B. wird aus X also C.

Die zweite Methode addiert zu jedem Code die Stellung im String. Das erste Zeichen bleibt somit unverändert, da es den Index 0 besitzt. Das zweite wird um 1 verschoben, das dritte um 2, usw. Methode 3 ist eine Mischung aus beiden. Ist a+i ungerade, wird die Konstante n, hier ebenfalls 5, zum Code addiert, ansonsten wieder die Zeichenposition i.

Das Hauptprogramm fragt in einer Schleife jeweils den String E ab. Dieser wird immer durch alle drei Methoden codiert, die Resultate auf dem Bildschirm ausgegeben.

Neben der Einschränkung, daß Standardprozeduren nicht als Werte von Prozedurvariablen in Frage kommen, sind schließlich noch zwei weitere Punkte zu nennen. Zunächst sind Prozeduren, die lokal zu anderen Prozeduren definiert sind, von der Benutzung durch Prozedurvariablen ausgeschlossen. Zum anderen ist für den Typ einer Prozedur ohne Parameter das Wort PROC bereits vordefiniert.

Am Ende ist zu sagen, daß die Prozedurtypen ein nahezu unbekanntes Sprachkonzept darstellen. Mathematische Anwendungen wie im ersten Beispiel werden hauptsächlich in Fortran, sehr selten jedoch in Modula-2 realisiert. Konstruktionen wie im zweiten und dritten Beispiel benutzt eigentlich überhaupt niemand, obwohl sie in der Anwendung sprachlich klar sind und in der Programmierung die Schachtelung von Bedingungen vermeiden.

Anweisungen wie out(A,all) oder s:=sum(A,prim) sagen doch alles aus. Wollte man Prozedurtypen vermeiden und trotzdem dieselbe Leistungsfähigkeit erreichen, müßte das zweite Argument eine Codezahl sein, die die Bedingung kennzeichnet. Dann müßten aber alle möglichen Bedingungen innerhalb der Prozedur ausgeführt sein, wodurch die Anzahl schon beschränkt wäre.

Zudem unterstützen die Prozedurtypen das Konzept der modularen Programmierung, weil beispielsweise die Prozeduren out und sum in einem externen Modul definiert sein können, während der Anwender in seinem Hauptmodul eine eigene Bedingung programmiert, die an sum übergeben werden kann.

 

Übersicht Modula-2 Index