Stand: 7.12.2000
© 2001 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung
angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht
oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses
Lehrmaterials bedarf der Erlaubnis des Autors.
Zeitplan: Das Kapitel 2 kann in den 3., 4. und 5. Sitzungen behandelt werden.
Überblick:
In diesem Kapitel wird am Beispiel der funktionalen Programmiersprache SML in die Programmierung eingeführt. Ziel ist es, dass jeder Student sich die für ein Informatikstudium unabdingbaren Programmierfertigkeiten schnell aneignet. Jeder Student soll sich daran gewöhnen, häufig -- auch ohne Auftrag! -- zu programmieren. Programmierung und Programmiersprachen können nur mit viel Übung gelernt werden.
SML bedeutet "Standard ML". Wie die meisten Programmiersprachen entstand das heutige SML aus Verfeinerungen einer ursprünglichen Programmiersprache. Die ursprüngliche Programmiersprache, aus der SML entstand, hieß ML. Heute bezeichnen beide Namen, SML und ML, dieselben Programmiersprache. Dazu gibt es ein paar ML-Dialekte, die in einigen Aspekten von SML abweichen.
Inhalt:
In einem italienischen Essen sind die Antipasti eine mehr oder weniger große Sammlung von kleinen schmackhaften Appetitanregern, die am Anfang des Essens angeboten werden. In ähnlicher Weise werden in diesem Abschnitt einige -- hoffentlich schmackhafte -- Aspekte von SML vermittelt.
SML wird mit dem Linux-Kommando sml aufgerufen. Eine SML-Sitzung wird mit ^D (Ctrl + D gleichzeitig) beendet.
SML bietet eine interaktive, d.h. dialogorientierte, Benutzerschnittstelle, die auf einer Treiberschleife beruht. Wenn die Treiberschleife das Zeichen - am Anfang einer Zeile anzeigt, dann kann der Benutzer einen Ausdruck angeben, das Ende des Ausdrucks mit dem Zeichen ; kennzeichnen und die Auswertung des Ausdruckes mit "enter" (auch "return" genannt) anfordern. SML wertet dann den Ausdruck unter Verwendung der ihr zu der Zeit bekannten Definitionen aus und liefert den ermittelten Wert auf einer neuen Zeile.
Beispiel einer SML-Sitzung:
linux% sml
Standard ML of New Jersey, Version 110.0.6, October 31, 1999
val use = fn : string -> unit
- 2;
val it = 2 : int
- ~1;
val it = ~1 : int
- ~(~2);
val it = 2 : int
- 2 * 3 + 1;
val it = 7 : int
- (2 * 3) + 1;
val it = 7 : int
- 2 * (3+1);
val it = 8 : int
- 4 div 2;
val it = 2 : int
- 5 div 2;
val it = 2 : int
- 100 mod 4;
val it = 0 : int
- 012;
val it = 12 : int
- Ctrl+D
linux%
"int" bezeichnet den (Daten-)Typ "integer" oder "ganze Zahl". In SML wie in den meisten modernen Programmiersprachen besitzt jeder Ausdruck einen (Daten-)Typ. Typen sind wichtige Bestandteile von Programmiersprachen. Die vordefinierte Typen von SML werden im Kapitel 6 eingeführt.
it bezeichnet den unbenannten Wert des Ausdrucks, dessen Auswertung angefordert wird. Wir werden sehen, dass Werte von Ausdrücken an weitere Namen gebunden werden können.
In diesem Kapitel werden vorwiegend Ausdrücke behandelt, deren Werte ganze Zahlen sind, also Ausdrücke vom Typ "ganze Zahl". Neben dem Typ "ganze Zahl" wird auch der Typ "boolean", Boole'scher Wert, in diesem Kapitel eingeführt. Der Typ "reelle Zahl" wird auch in diesem Kapitel kurz erwähnt. Der Typ "reelle Zahl" wird aber erst im Kapitel 6 ausführlich behandelt.
In SML sind bei ganzen Zahlen führende Nullen zulässig. Zum Beispiel ist 012 eine andere Notation für 12, ~0012 eine andere Notation für ~12.
SML bietet die folgenden vordefinierte Operationen über natürlichen Zahlen: + - * div und mod, die alle infix notiert werden.
Auf die sogenannten "Präzedenzen" der vordefinierten Operationen muss geachtet werden: 2 * 3 + 1 steht z.B. für (2 * 3) + 1.
Vorsicht: ~ (Vorzeichen für negative ganze Zahlen) und - (Substraktion) sind in SML nicht austauschbar.
~ ist ein unärer (oder einstelliger) Operator (oder Operation). - und + und * sind binäre (oder zweistellige) Operatoren.
Zum Vergleich von ganzen Zahlen bietet SML die vordefinierte Funktion =
- 2 = 2;
val it = true : bool
- 2 = 3;
val it = false : bool
Eine Funktion, die wie = als Wert entweder true oder false liefert, wird "Prädikat", d.h. Test, gennant.
Die Werte der Ausdrücke 2 = 2 und 2 = 3 sind sogenannte "Wahrheitswerte" oder Boole'sche Werte. Es gibt zwei Boole'sche Werte: "true" (wahr) und "false" (falsch).
SML bietet die folgenden Operationen über Boole'schen Ausdrücken: not (präfix notiert), andalso (infix notiert) und orelse (infix notiert).
- true;
val it = true : bool
- not true;
val it = false : bool
- not (not false);
val it = false : bool
- true andalso not false;
val it = true : bool
- false orelse true;
val it = true : bool
- not (2 = 3);
val it = true : bool
Der Ausdruck not not false kann nicht ausgewertet werden, weil er von SML wie (not not) false verstanden wird. (not not) false ist aus zwei Gründen inkorrekt:
not ist ein unärer Operator (oder Operation). orelse (Disjunktion) und andalso (Konjunktion) sind binäre Operatoren (oder Operationen).
Boole'sche Ausdrücke können mit der vordefinierten Funktion = verglichen werden:
- true = not (not true);
val it = true : bool
- false = (false andalso not true);
val it = true : bool
Bemerkung:
Allerdings ist der Vergleich von Wahrheitswerten mit = fast immer schlechter Programmierstil und unnötig kompliziert. Besonders Anfänger neigen oft zu Konstruktionen wie:
if Bedingung = true then Ausdruck else Ausdruck'
ohne zu beachten, dass Bedingung = true immer genau den selben Wert hat wie Bedingung. Es ist einfacher und übersichtlicher,
if Bedingung then Ausdruck else Ausdruck'
zu schreiben. In ähnlicher Weise lässt sich
if Bedingung = false then Ausdruck else Ausdruck'
stets vereinfachen zu
if not Bedingung then Ausdruck else Ausdruck'
oder noch besser zu
if Bedingung then Ausdruck' else Ausdruck
Obwohl die Gleichheit für Boole'sche Ausdrücke und die Gleichheit für ganze Zahlen identisch geschrieben werden, handelt es sich um grundverschiedene Funktionen, weil ihre Argumente verschiedene Typen besitzen. Zur Feststellung der Gleichheit, um die es sich in einem Ausdruck handelt, zieht das SML-System die Typen der Operanden in Betracht.
Wenn derselbe Name oder dasselbe Symbol, wie hier =, zur Bezeichnung unterschiedlicher Operationen oder Funktionen verwendet wird, die vom System unterschieden werden, dann sagt man, dass der Name oder das Symbol "überladen" (overloaded) ist.
Das Überladen von Bezeichnern ist nicht ungefährlich und wird deswegen nur selten angewandt.
Weitere Fälle von Überladen in SML sind + und *, die die arithmetischen Operationen Addition und Multiplikation sowohl für ganze Zahlen als auch für reelle Zahlen bezeichnen:
- 2 + 3;
val it = 5 : int
- 2.1 + 3.3;
val it = 5.4 : real
- 2 * 3;
val it = 6 : int
- 2.1 * 3.3;
val it = 6.93 : real
Es ist wichtig zu bemerken, dass in SML sowie in den meisten Programmiersprachen ganze Zahlen und reelle Zahlen Zahlen unterschiedlicher Typen sind. Im Gegensatz dazu sind in der Mathematik ganze Zahlen ein Untertyp der reellen Zahlen. Der Unterschied kommt daher dass Programmiersprachen völlig unterschiedliche Darstellungen für ganze Zahlen und für reelle Zahlen benutzen (und dass diese "reellen Zahlen" im Sinne von Programmiersprachen auch gar nicht die Menge der "reellen Zahlen" im mathematischen Sinn repräsentieren, sondern nur eine Teilmenge der rationalen Zahlen). In SML wie in den meisten Programmiersprachen kennt die Ganzzahlarithmetik keine Rundung und damit auch keine Ungenauigkeit, wogegen die Genauigkeit der Arithmetik mit reellen Zahlen von der Gleitkommahardware des Computers abhängt.
Der Versuch, eine ganze Zahl und eine reelle Zahl zu addieren, führt folglich zu einer Fehlermeldung:
- 2 + 4.83;
stdIn:10.1-10.9 Error: operator and operand don't agree [literal]
operator domain: int * int
operand: int * real
in expression:
2 + 4.83
Wegen des ersten Operanden 2 interpretiert SML das Zeichen + als die Addition für ganze Zahlen. Da 4.83 keine ganze Zahl ist, wird ein Typfehler gemeldet.
SML bietet weitere häufig benötigte Typen wie z.B. "Zeichen" (wie a, b, c, usw.) und "Zeichenfolge" (wie diese Klammer) -- siehe Kapitel 6.
Ferner ermöglicht SML die Definition von Typen, die für ein praktisches Problem maßgeschneidert werden können (wie etwa eine beliebige Notenskala oder die Tage der Woche in einer beliebigen Sprache) -- siehe Kapitel 9.
Für ganze Zahlen und für reelle Zahlen bietet SML die folgenden vordefinierten überladenen Prädikate an:
| < | (echt kleiner) |
| > | (echt größer) |
| <= | (kleiner gleich) |
| >= | (größer gleich) |
Für ganze Zahlen bietet SML das vordefinierte Prädikat <> (Negation der Gleichheit) an.
Vorsicht: = und <> sind für reelle Zahen nicht zulässig. Für reelle Zahlen bietet SML die Funktion Real.compare(x, y) an:
- Real.compare(1.0,7.0);
val it = LESS : order
- Real.compare(100.0,1.0);
val it = GREATER : order
- Real.compare(1.0,1.0);
val it = EQUAL : order
Man merke, dass die Funktion Real.compare kein Prädikat ist, weil sie keine Boole'schen Werte liefert, sondern Werte aus einem bisher nicht begegneten Typ namens "order".
SML bietet auch die Gleichheitsfunktion Real.== für reelle Zahlen, die den Typ "order" nicht verwendet:
- Real.==(2.5, 2.5);
val it = true : bool
- Real.==(2.5, 3.0);
val it = false : bool
Int.abs: Betrag einer ganzen Zahl
- Int.abs(~4);
val it = 4 : int
Int.min: minimum zweier ganzen Zahlen
- Int.min(5,2);
val it = 2 : int
Int.max: maximum zweier ganzen Zahlen
- Int.max(3,5);
val it = 5 : int
Int.sign: "Vorzeichen" einer ganzen Zahl
- Int.sign(0);
val it = 0 : int
- Int.sign(~5);
val it = ~1 : int
- Int.sign(6);
val it = 1 : int
Wie bereits erwähnt, wertet SML Ausdrücke aus. Ein Ausdruck kann atomar wie 2, 4 oder false sein, oder zusammengesetzt wie 2 + 4 und not (false andalso true).
Jeder korrekt gebildete Ausdruck hat einen Typ. Ein Typ ist eine Menge von Werten, zum Beispiel die Menge der natürlichen Zahlen. Meistens hat ein Ausdruck auch einen Wert, und wenn der Ausdruck einen Wert hat, ist der Wert ein Element des Typs des Ausdrucks. Manche Ausdrücke wie 1 div 0, in denen nicht-totale Funktionen verwendet werden, haben keinen Wert.
Atomare Ausdrücke wie true und false kann man oft mit ihren Werten identifizieren. Aber in vielen, auch ziemlich einfachen, Fällen ist diese Betrachtungsweise problematisch. So lässt SML zum Beispiel bei ganzen Zahlen (Typ integer) führende Nullen zu. Also sind 02 und 2 verschiedene atomare Ausdrücke, die aber beide den selben Wert haben. Hier sind also atomare Ausdrücke und Werte nicht identisch. Ein anderes Beispiel sind atomare Ausdrücke wie div oder orelse, deren Werte selbstverständlich Funktionen sind, also nicht mit den atomaren Ausdrücken identisch. Zusammengesetzte Ausdrücke sind mit ihren Werten auf keinen Fall identisch. Aus all diesen Gründen wird üblicherweise strikt zwischen Ausdrücken und Werten unterschieden.
Jeder korrekt gebildete Ausdruck hat einen Typ (aber nicht immer einen Wert). Bisher sind wir nur Ausdrücken der Typen "ganze Zahl", "Boole'scher Wert" und "reelle Zahl" begegnet.
Auch Operationen und allgemein Funktionen haben Typen: + z.B. ist eine Funktion, die als Argumente zwei (atomare oder zusammengesetzte) Ausdrücke vom Typ "ganze Zahl" erhält, und einen Wert ebenfalls vom Typ "ganze Zahl" liefert. Die Gleichheit für ganze Zahlen ist eine Funktion, die als Argumente zwei (atomare oder zusammengesetzte) Ausdrücke vom Typ "ganze Zahl" erhält, und einen Wert vom Typ Boole'scher Wert liefert. Man schreibt:
| + | : | (int, int) | -> | int |
| = | : | (int, int) | -> | bool |
Bei der Bildung von zusammengesetzten Ausdrücken muss auf die Typen der verwendeten Operationen oder Funktionen und der eingesetzten Teilausdrücke geachtet werden.
Es gibt zwei grundlegende Ansätze, was Typen in Programmiersprachen angeht:
Eine schwach typisierte Programmiersprache würde einen Ausdruck wie 8.0 + 1 (Summe einer reellen Zahl und einer ganzen Zahl) akzeptieren und bei der Auswertung die natürliche Zahl 1 in eine reelle Zahl automatisch umwandeln -- man spricht von einer (automatischen) "Typanpassung".
Eine stark typisierte Programmiersprachen verlangt vom Programmierer, dass er für jeden Namen (oder Bezeichner) einen Typ explizit angibt und jede notwendige Typanpassung selber programmiert. In SML kann eine Typanpassung zwischen reellen und ganzen Zahlen unter Verwendung der vordefinierten Funktion "real" und "round" wie folgt programmiert werden:
- real(1);
val it = 1.0 : real
- round(8.12);
val it = 8 : int
- round(8.99);
val it = 9 : int
- round(8.0);
val it = 8 : int
Man merke, dass der Zweck von "round" nicht nur die Typanpassung ist, sondern zudem das Auf- bzw. Abrunden ist.
SML verfolgt einen Mittelweg zwischen schwach und stark typisierten Programmiersprachen, den Weg der sogenannten "polymorphen Typüberprüfung" ("polymorphic type checking"): Anstatt vom Programmierer die explizite Angabe von Typen (wie etwa in der Programmiersprache Pascal) zu verlangen, ermittelt SML wenn möglich selber, was die Typen der Bezeichner sind.
Wir haben gesehen, dass der Ausdruck 2 * 3 + 1 für (2 * 3) + 1 steht und dass der Ausdruck not not false für den (inkorrekt gebildeten) Ausdruck (not not) false steht.
Dahinter stehen zwei Begriffe: die Präzedenzen und die Assoziativitätsregeln von Operationen.
Präzedenzen zwischen Operationen legen fest, welche implizite Klammerung bei unzureichend oder gar nicht geklammerten Ausdrücken gemeint sein soll. Man sagt, dass * stärker bindet als +, was bedeutet, dass z.B. 2 * 3 + 1 für (2 * 3) + 1 steht. Obwohl diese Annahme üblich ist, könnte eine Programmiersprache genauso auf der Annahme beruhen, dass * weniger stark als + bindet.
Die Assoziativitätsregeln legen fest, ob fehlende Klammerungen von links oder rechts her einzusetzen sind, d.h. ob 2 + 3 + 4 für (2 + 3) + 4 oder für 2 + (3 + 4) steht. In SML sind übrigens + und * linksassoziativ, d.h. 2 + 3 + 4 steht für (2 + 3) + 4. Auch wenn in vielen Fällen beide Klammerungen den selben Wert liefert, ist der Wert im allgemeinen von der Assoziativitätsregel abhängig: 10 - 7 - 1 hat den Wert 2, wenn - wie in SML als linksassoziativ behandelt wird. Würde - als rechtsassoziativ behandelt, hätte der Ausdruck den Wert 4. In manchen Programmiersprachen sind die Assoziativitätsregeln auch deshalb nicht unwichtig, weil sie die Reihenfolge der Auswertung bestimmen.
Ausdrücke, die SML zur Auswertung weitergereicht werden sind linear, weil sie aus einer Folge von Zeichen bestehen. Beispiele von linearen Ausdrücke sind (2 * 3) + 1 und 2 * 3 + 1. Die Syntax solcher Ausdrücke wird von SML analysiert, bevor die Ausdrücke ausgewertet werden. Die Syntaxanalyse des linearen Ausdrucks (2 * 3) + 1 führt zur Bildung einer baumartigen Struktur in Speicher wie:
(*) +
/ \
v v
* 1
/ \
v v
2 3
Dabei stellen die gerichteten Kanten Zeiger, d.h. Speicheraddressen, dar -- siehe Informatik 3. Im (linear angeordneten) Speicher ist der obige Baum ähnlich wie folgt repräsentiert (die Ai stellen Speicheradresse dar):
(**)
Speicher
+-----+-+--------+-------+----+-+-----+-+-----+------+-+----
| |2| |+|A3|A4| |3| |*|A1|A2| |1|
+-----+-+--------+-------+----+-+-----+-+-----+------+-+--
^ ^ ^ ^
| | | |
A1 A2 A3 A4
Die Syntaxanalyse ist aus zwei Gründen notwendig:
Man merke, dass eine Baumdarstellung à la (*) genauso wie die lineare konkrete Syntax eine abstrakte Wiedergabe der abstrakten Syntax ist.
Da 2 * 3 + 1 in SML für (2 * 3) + 1 steht, führt die Syntaxanalyse von 2 * 3 + 1 zur Bildung des selben Baumes wie die Syntaxanalyse von (2 * 3) + 1.
Da Computer eine baumartige Repräsentation von Ausdrücke verwenden, kann man sich manchmal fragen, ob manche Überlegungen oder Überprüfungen, die Menschen durchführen, nicht ebenfalls auf Bäume statt (lineare) Ausdrücken beruhen, also unter Verwendung der abstrakter statt konkreter Syntax stattfinden sollten.
Die konkrete Syntax ist nur dann wünschenswert, wenn die interne Repräsentation der Ausdrücke im Speicher bei der Untersuchung eine Rolle spielt. Sonst ist die konkrete Syntax vom Vorteil, weil sie für Menschen einfacher (vor allem zu schreiben) ist. Man merke zudem, dass eine Baumdarstellung von Ausdrücke wie (**) keine geringere Abstraktion der Speicherdarstellung als die konkrete (lineare) Syntax ist.
Mit einer "Deklaration" kann ein Wert an einen "Namen" gebunden werden. Mögliche Werte, die an Namen gebunden werden können, sind unter anderem Konstanten und Funktionen. Eine Deklaration, die eine Konstante (bzw. Funktionen) an einen Namen bindet, wird Konstantendeklaration (bzw. Funktiondeklaration) genannt.
- val zwei = 2;
val zwei = 2 : int
Nach dieser Konstantendeklaration kann der Namen zwei genauso wie die Konstante 2 verwendet werden:
- zwei + zwei;
val it = 4 : int
- zwei * 8;
val it = 16 : int
Anstatt von einer Konstantendeklaration spricht man auch von einer Wertdeklaration, daher das Wort val (von englisch "value"). Alle Konstantendeklarationen sind Wertdeklarationen, aber nicht alle Wertdeklarationen sind Konstantendeklarationen - siehe unten.
- fun zweimal(x) = 2 * x;
val zweimal = fn : int -> int
Anstelle des eigentlichen Wertes der Funktion, die an den Namen zweimal gebunden wird, gibt SML "fn" (für Funktion) an. Dabei handelt es sich lediglich um eine Kurzmitteilung. Der Wert des Namens zweimal ist die Funktion, die als Eingabe eine ganze Zahl erhält und das Doppelte dieser Zahl als Ausgabe liefert.
Nachdem eine Funktion deklariert wurde, kann sie aufgerufen werden:
- zweimal(8);
val it = 16 : int
- zweimal(zweimal(8));
val it = 32 : int
Neben dem Kürzel "fn", das als Platzhalter für den Wert des (Funktions-)Namens steht, liefert SML den Typ der deklarierten Funktion, hier: int -> int. Dieser Typ wurde wie folgt ermittelt: Da 2 eine ganze Zahl ist, steht die überladene Operation * für die Multiplikation ganzer Zahlen. Folglich muss x vom Typ "ganze Zahl" sein (daher int ->). Da * die Multiplikation ganzer Zahlen ist, ist der von zweimal berechnete Wert eine ganze Zahl (daher -> int).
Die Ermittlung des Typs int -> int der Funktion zweimal ist ein Beispiel der "polymorphen Typüberprüfung" (siehe 2.2) von SML.
Anstatt von Funktiondeklaration spricht man auch von Funktionsdefinition.
Die folgenden Deklarationen sind auch korrekt:
- fun zweimal (x) = 2 * x;
- fun zweimal x = 2 * x;
Für SML ist eine Funktion ein Wert. Folglich kann auch das Deklarationskonstrukt val verwendet werden, um einen Namen an eine Funktion zu binden. Dazu wird eine besondere Notation verwendet, die die Definition von anonymen Funktionen ermöglicht.
Die Funktion zweimal kann z.B. wie folgt definiert werden:
val zweimal = fn x => 2 * x;
Diese Deklaration kann wie folgt paraphrasiert werden: An den Namen zweimal wird die anonyme Funktion gebunden, die eine Zahl x als Argument erhält und 2 * x liefert. Der Teil fn x => 2 * x definiert eine anonyme Funktion. fn wird oft "lambda" ausgesprochen.
Vorsicht: die Konstrukte fn und fun von SML nicht verwechseln!
In der Funktionsdeklaration
fun zweimal(x) = 2 * x;
wird x formaler Parameter (der Funktionsdeklaration oder Funktionsdefinition) genannt.
Im Funktionsaufruf zweimal(8) wird 8 der aktuelle Parameter (des Funktionsaufrufes) geannt.
Formale Parameter haben in Funktionsdeklarationen eine ähnliche Bedeutung wie Pronomen in natürlichen Sprachen. Die Deklaration der Funktion zweimal kann wie folgt paraphrasiert werden: Um zweimal von ETWAS zu berechnen, multipliziere ES mit 2.
Der Rumpf oder definierender Teil einer Funktionsdeklaration ist der Teil nach dem Zeichen =. Im Falle der folgenden Deklaration der Funktion zweimal
fun zweimal(x) = 2 * x;
ist der Rumpf 2 * x.
Diese drei Begriffe haben diesselbe Bedeutung.
Da x + x = 2 * x ist, hätte man die Funktion zweimal wie folgt definieren können:
- fun zweimal(x) = x + x;
Eine solche Deklaration wird nicht von allen SML-Systemen als korrekt angenommen, weil es nicht eindeutig ist, ob der formale Parameter x den Typ ganze Zahl oder den Typ reelle Zahl besitzt. Manche Systeme nehmen an, dass x den Typ ganze Zahl besitzt, weil sie im Zweifel annehmen, dass + für die Addition von ganzen Zahlen steht. Andere SML-Systemen machen keine solche Annahme und verwerfen die vorangehende Funktionsdeklaration als inkorrekt.
Typ-Constraints (auch Typsierungsausdrücke genannt) ermöglichen, die fehlende Information anzugeben, z.B. wie folgt:
- fun zweimal x: int = x + x;
womit der Typ des Ergebnis (berechneten und gelieferten Wertes) angegeben wird, oder wie folgt:
- fun zweimal(x: int) = x + x;
womit der Typ des Parameters angegeben wird, oder sogar wie folgt:
- fun zweimal(x: int): int = x + x;
womit sowohl der Typ des Ergebnis als auch der Typ des Parameters angegeben werden.
Mit einem Typ-Constraint kann die folgende Funktion für reelle Zahlen definiert werden:
- fun reell_zweimal x:real = x + x;
val reell_zweimal = fn : real -> real
- val pi = 3.1416;
val pi = 3.1416 : real
- reell_zweimal pi;
val it = 6.2832 : real
Man merke, dass vor und nach dem Zeichen : in einer Typ-Constraint ein oder mehrere Leerzeichern zulässig sind.
SML unterscheidet zwischen "alphabetischen" und "symbolischen Namen", je nach dem, wie sie gebildet sind. Diese Unterscheidung betrifft nicht die Verwendung der Namen: sowohl symbolische wie alphabetische Namen können in Konstanten- und Funktionsdeklarationen verwendet werden.
Alphabetische Namen fangen mit einem (kleinen oder großen) Buchstaben an, der gefolgt wird von endlich vielen (auch null) Buchstaben (a ... z A ... Z), Ziffern (0 1 2 ... 9), Underscore (_), Hochkommata (single quote: ').
Symbolische Namen sind (endliche) Folgen der folgenden Zeichen:
! % & $ # + - * / : < = > ? @ \ ~ ` ^ und |.
- val @#!@@@ = 12;
val @#!@@@ = 12 : int
- fun $@#? x = 5 * x;
val $@#? = fn : int -> int
Vorsicht: die folgenden symbolischen Namen haben in SML eine
vordefinierte Bedeutung:
: | = => -> # :>
Es ist empfehlenswert, Funktionsdeklarationen in einer Datei zu speichern, und dann das Laden, d.h. Einlesen, dieser Deklarationen anzuforden. Heißt die Datei meine_datei.sml, dann geschieht dies wie folgt:
- use("meine_datei.sml");
val it = () : unit
Dabei ist () (gesprochen "unity") der einzige Wert eines besonderen Datentyps namens unit, dessen Zweck es ist, einen Wert für Funktionsaufrufe zu liefern, die eigentlich keinen Wert berechnen, sondern wie die vordefinierte Funktion use einen Nebeneffekt bewirken, im Falle von use das Laden (oder Einlesen) einer Datei.
SML ermöglicht fallbasierte Funktionsdefinitionen. Eine Funktion Vorzeichen, die der vordefinierten Funktion Int.sign (siehe 2.1) entspricht, kann zum Beispiel wie folgt definiert werden:
fun Vorzeichen(x : int) = if x > 0 then 1
else if x < 0 then ~1
else 0;
Das Konstrukt if Test then E1 else E2 stellt die Anwendung auf Test einer Funktion dar, deren Definition die Folgende ist:
(fn true => E1 | false => E2)
if Test then E1 else E2 steht also für (fn true => E1 | false => E2)(Test).
Im Gegensatz zu (imperativen) Programmiersprache wie Pascal ist in SML der else-Teil von if-then-else-Ausdrücke nicht abdingbar. Der Grund ist, dass ein Ausdruck ohne else-Teil wie
if B then A
keinen Wert hätte, wenn die Bedingung B den Wert false hätte, was in der funktionallen Programmierung unmöglich wäre. In einer imperativen Programmiersprachen hat ein if-then-else-Ausdruck wie
if B then A
die Bedeutung eines bedingten Befehls.
In einem SML-Ausdruck
if B then A1 else A2
müssen A1 und A2 dasselbe Typ haben.
In der Definition der obigen anonymen Funktion sind zwei Aspekte bemerkenswert:
Mehr als zwei Fälle können vorkommen. In solchen Fällen werden die Patterns sequenziell in der Reihenfolge der Definition probiert, bis einer mit dem Wert des aktuellen Parameters "matcht". Das Pattern _ (wildcard) stellt einen Fangfall dar, d.h. matcht mit jedem möglichen Wert des aktuellen Parameters. Wildcard wird nicht im Rumpf der Funktionsdefinition verwendet. Das folgende Prädikat liefert true, wenn es auf eine ganze Zahl angewandt wird, die eine (nicht-negierte) Ziffer ist:
val Ziffer = fn 0 => true
| 1 => true
| 2 => true
| 3 => true
| 4 => true
| 5 => true
| 6 => true
| 7 => true
| 8 => true
| 9 => true
| _ => false;
Vorsicht: Pattern sind keine Tests wie etwa (x > 0), sondern mögliche Werte des Parameters.
Das Pattern Matching wird auf Deutsch auch "Angleich" oder "Musterangleich" genannt.
Sei die Funtion summe zu programmieren, die zu jeder natürlichen Zahl n die Summe aller natürlichen Zahlen von 0 bis einschließlich n liefert. summe kann unter anderem wie folgt definiert werden:
| summe(n) = | 0 | falls n = 0 |
| n + summe(n-1) | falls n > 0 |
was in SML in einer der folgenden Weise programmiert werden kann:
fun summe(n) = if n = 0 then 0 else n + summe(n-1);
oder
val rec summe = fn 0 => 0 | n => n + summe(n-1);
Man merke das Wrt rec, das dazu dient hervorzuheben, dass die Wertdefinition die Definition einer rekursiven Funktion ist. Das Hinzufügen von rec nach val ist unabdingbar, weil summe rekursiv ist.
summe kann auch wie folgt definiert werden:
summe(n) = n * (n + 1) / 2
Diese Definiton führt zu wesentlich effizienteren Berechnungen, weil sie für jedes n nur drei Grundoperationen verlangt. Diese Definition kann in SML wie folgt programmiert werden:
fun summe(n) = n * (n + 1) div 2;
Warum gilt diese Definition? Ihre Korrekthet kann wie folgt induktiv bewiesen werden.
Basisfall:
Für n = 0 gilt die Gleichung summe(n) = n * (n + 1) / 2 offenbar, weil 0 * (0 + 1) / 2 = 0.
Induktionsfall:
Induktionsannahme: Sei angenommen, dass für eine natürliche Zahl k gilt summe(k) = k * (k + 1) / 2.
Zeigen wir, dass sie auch für die Nachfolgerzahl k + 1 gilt.
summe(k + 1) = k + 1 + summe(k). Nach Induktionsanahme
summe(k) = k * (k + 1) / 2. Also
summe(k + 1) = k + 1 + summe(k) =
k + 1 + (k * (k + 1) / 2) =
[2 (k + 1) + (k * (k + 1)] / 2 =
[(k + 2) * (k + 1)] / 2.
QED
Die Technik, die in diesem Beweis angewendet wurde, heißt "vollständige Induktion". Induktionsbeweise gehören zu den unabdingbaren Techniken der Softwarentwicklung.
Sei n eine ganze Zahl.
Fall 1: n ist gerade. Die ganzen Zahlen von 1 bis n können in Paaren (n, 1), (n-1, 2), (n-3, 3), ... gruppiert werden. Das letzte solcher Paare ist ((n/2)+1, n/2) (*), weil kein weiteres solches Paar (a, b) die beiden Eigenschaften: a+b = n+1 und a >= b besitzt. Die Summe der Zahlen jedes Paares ist n+1 und es gibt n/2 solche Paare, also summe(n) = n * (n + 1) / 2.
Fall 2: n ist ungerade. Die ganzen Zahlen von 0 bis n können in Paaren (n, 0), (n-1, 1), (n-2, 2), ... gruppiert werden. Das letzte solcher Paare ist (|n/2|+1,|n/2|) (**). Die Summe der Zahlen jedes Paares ist n und es gibt (n+1)/2 solche Paare, also summe(n) = n * (n + 1) / 2.
QED
Bemerkung: Die Aussagen (*) und (**) im vorangehenden Beweis verlangen im Grunde (einfache) Induktionsbeweise, die hier der Übersichtlichkeit halber ausgelassen wurden.
Es kommt häufig vor, dass bei der Programmierung von rekursiven Funktionen ein Denk- oder Programmierungsfehler zu einer nichtterminierenden Funktion führt. Es ist z.B. der Fall mit der folgenden Funktion:
fun s(n) = n + s(n+1);
Die Terminierung einer rekursiven Funktion wie summe kann unter Anwendung der Beweistechnik der vollständigen Induktion gezeigt werden. Zeigen wir, dass für alle ganzen Zahlen n der Aufruf summe(n) terminiert.
Basisfall: summe(0) terminiert, weil nach Funktionsdeklaration der Aufruf von summe(0) den Wert 0 liefert.
Induktionsfall:
Induktionsannahme: Sei angenommen, dass für eine natürliche Zahl k der Aufruf von summe(k) terminiert.
Zeigen wir, dass der Aufruf von summe(k + 1) terminiert. Nach Funktionsdeklaration liefert der Aufruf von summe(k + 1) den Wert von k + 1 + summe(k). Nach Induktionsannahme terminiert der Aufruf von summe(k). Folglich terminiert auch der Aufruf von summe(k + 1).
Dieser Beweis stellt exemplarisch dar, wie Terminierungsbeweise sowie Beweise anderer Eigenschaften von rekursiven Funktionen unter Anwendung der Beweistechnik "vollständige Induktion" geführt werden können.
Nur in den seltensten Fällen kann man sich durch Teste von der Korrektheit eines Programms überzeugen, weil es in der Regel wie bei der rekursiven Funktion summe unendlich -- oder zu viele -- mögliche Aufrufparameter gibt. So sind Beweise unabdingbare Bestandteile der Programmentwicklung.
Betrachten wir die folgende Sitzung:
- val zwei = 2;
val zwei = 2 : int
- fun zweimal(n) = zwei * n;
val zweimal = fn : int -> int
- zweimal(9);
val it = 18 : int
- val zwei = 0;
val zwei = 0 : int
- zweimal(9);
val it = 18 : int
- fun zweimal'(n) = zwei * n;
val zweimal' = fn : int -> int
- zweimal'(9);
val it = 0 : int
Es ist zulässig, die Bindung eines Wertes, sei es eine Konstante wie im obigen Beispiel oder eine Funktion, an eine Name wiederzudeklarieren. Wird der Name in eine Deklaration verwendet, dann gilt seine letzte Bindung an einen Wert.
Die Wiederdeklaration eines Namens gilt jedoch nicht für Deklarationen, die diesen Namen vor der Wiederdeklaration verwendet haben. So steht zwei für 2 in der Deklaration der Funktion zweimal, für 0 in der Deklaration der Funktion zweimal'. Man sagt, dass die Bindung in SML eine "statische Bindung" (oder "lexikalische Bindung") ist. Würde die Wiederdeklaration eines Namens N Einfluss auf Funktionen haben, deren Rümpfe sich auf N beziehen, so würde man von einer "dynamischen Bindung" sprechen.
Die Wiederdeklaration von Namen und ihre Behandlung durch SML ist eine große Hilfe bei der Entwicklung von Programmen, die viele Namen verwenden.
Das SML-System verwaltet mit jeder Sitzung und jeder eingelesenen Datei, d.h. Programm, eine geordnete Liste von Gleichungen der Gestalt Name = Wert (dargestellt als Paare (Name, Wert)), die Umgebung heißt. Jede neue Deklaration eines Wertes W für einen Namen N führt zu einem neuen Eintrag N = W am Anfang der Umgebung. Um den Wert eines Namens zu ermitteln, wird die Umgebung von Anfang an durchlaufen. So gilt immer als Wert eines Namens N derjenige Wert, der bei der letzten Deklaration von N angegeben wurde.
Kommt ein Namen A im Wertteil W einer Deklaration val N = W oder val rec N = W oder fun N = W vor, so wird den Wert von A ermittelt und in W anstelle von A eingefügt, bevor der Eintrag für N in die Umgebung gespeichert wird. So verändert eine spätere Wiederdeklaration von A den Wert von N nicht.
Der Unterschied zwischen totalen und nichttotalen Funktionen ist für die Programmierung vom Belang. Die rekursive Funktion summe mit Typ int -> int vom Absatz 2.6
fun summe(n) = if n = 0 then 0 else n + summe(n-1);
ist über die ganzen Zahlen nicht total, weil ein Aufruf von summe mit einem nichtpositiven Eingabeparameter wie etwa summe(~25) nicht terminiert. Über den natürlichen Zahlen ist diese Funktion aber total.
Es ist wichtig zu ermitteln, über welchem Bereich eine programmierte Funktion total ist. Es ist nur bezüglich dieses Bereiches, dass Eigenschaften der Funktion wie z.B. die Terminierung überhaupt einen Sinn ergeben.
In SML sind Kommentare beliebiege Texte, die mit den Zeichen (* anfangen und mit dem Zeichen *) enden. SML läßt geschachtelte Kommentare zu. Im folgenden Beispiel ist also die ganze Funktionsdeklaration "auskommentiert":
(*
fun Vorzeichen(x : int) = if x > 0 then 1
else if x < 0 then ~1
else (* x = 0 *) 0;
*)
Klare und präzise Kommentare sind in jedem Programm unabdingbar. Es ist immer naiv anzunehmen, dass ein Programm, in welcher Programmiersprache auch, selbsterklärend sei. Programme werden zunächst für Menschen und danach für Computer geschrieben. Es ergibt keinen Sinn, Programme von Computern ausführen zu lassen, die nicht von Menschen verstanden werden.
Manche der vordefinierten Funktionen von SML wie Real.compare sind in sogenannten Modulen programmiert, d.h. in Programmen, andere wie + sind Teile des SML-Sytems. Die SML-Bezeichnung für Modulen ist "Struktur" (structure).
Eine Funktion F, die in einem Modul M definiert ist, wird außerhalb dieses Moduls als M.F bezeichnet -- und aufgerufen.
Die Standardbibliothek stellt eine Sammlung von Modulen (Strukturen) für herkömmliche Typen wie reelle Zahlen dar. Die Module der Standardbibliothek werden vom SML-System automatisch geladen. Das Laden von anderen Modulen muss aber vom Programmierer explizit angefordert werden -- siehe Kapitel 12.
Siehe "The Standard ML Basis Library" unter http://cm.bell-labs.com/cm/cs/what/smlnj/doc/basis/
Sei die folgende Funktion in SML zu programmieren:
| potenz: | Z x N | -> | Z |
| (a, b) | -> | a ** b |
Die Potenz ist übrigens keine vordefinierte Funktion in SML.
Die folgenden Gleichungen liefern die Grundlage für ein rekursives Programm:
| a ** b = 1 | falls b = 0 |
| a ** b = a * [a ** (b-1)] | andernfalls |
Daraus folgt die folgende Implementierung in SML:
fun potenz(a, b) = if b = 0 then 1 else a * potenz(a, b - 1);
Wir beweisen induktiv, dass für alle (a, b) in (Z, N) der Aufruf von potenz(a, b) terminiert.
Sei a eine beliebige ganze Zahl.
Basisfall: b = 0. Nach Funktionsdeklaration terminiert der Aufruf und liefert 1.
Induktionsfall: Sei angenommen, dass für ein gegebenes k in N der Aufruf potenz(a, b) terminiert (Induktionshypothese). Nach Definition berechnet der Aufruf von potenz(a, b + 1) den Wert von a * potenz(a, b). Er terminiert also nach Induktionsannahme.
Der Zeitbedarf wird als die Anzahl der Multipklikationen zweier ganzer Zahlen geschätzt. Diese Schätzung stellt eine Vergröberung dar, weil Multiplikationen kleiner Zahlen weniger Zeit verlangen als die Multiplikation großer Zahlen. Solche vergröbernden Annahmen sind bei Schätzungen des Zeitbedarfs üblich.
Die Berechnung von potenz(a, b + 1) bedarf einer Multiplikation mehr als die Berechnung von potenz(a, b), die Berechnung von potenz(a, 0) bedarf keiner Multiplikation. Also bedarf die Berechnung von potenz(a, b) insgesamt b Multiplikationen.
Man sagt, dass der Zeitbedarf der Funktion potenz linear im zweiten Argument ist.
Ist b gerade mit b = 2k, so gilt: a ** b = a ** 2k = (a ** k)**2. Es ist also möglich für gerade natürliche Zahlen b die b-Potenz einer ganzen Zahl a mit weniger als b Multiplikationen zu berechnen. Diese Beobachtung führt zur folgenden Funktionsdeklaration:
fun potenz'(a, b) = if b = 0
then 1
else if gerade(b)
then quadrat(potenz'(a, b div 2))
else a * potenz'(a, b - 1);
wobei die Hilfsfunktionen gerade und quadrat wie folgt deklariert werden:
fun gerade(a) = (a mod 2 = 0);
fun quadrat(a : int) = a * a;
Der Zeitbedarf der Funktion potenz' wird wie bei der Funktion potenz als die Anzahl der Multipklikationen zweier ganzer Zahlen geschätzt. Nach dieser Annahme werden die Rechenzeiten für die Aufrufe des Prädikats gerade vernachlässigt.
So geschätzt ist die Rechenzeit abhängig von b und unabhängig von a. Sei also rz(b) die Rechenzeit eines Aufrufes von potenz'(a, b) (für eine beliebige ganze Zahl a und für eine natürliche Zahl b). Es gilt:
| (*) | rz(2**b) | = | rz(2**(b-1)) + 1 |
| (**) | rz(0) | = | 0 |
Es gilt also:
(***) rz(2**b) = b
Auf die Potenzen von 2 ist also rz die Umkehrung der Funktion b -> 2**b, d.h. des Logaritmus zur Basis 2, genannt ln2. Diese Beobachtung liefert keinen präzisen Wert für Zahlen, die keine Potenzen von 2 sind.
Für große Zahlen ist der Zeitbedarf von potenz' viel geringer als der Zeitbedarf von poten). Z.B. potenz'(a, 1000) bedarf nur 14 Multiplikationen anstatt der 1000 Multiplikationen von potenz(a, 1000). Für wachsende Werte von b vergrößert sich sehr schnell der Berechnungszeitsabstand zwischen potenz' und potenz.
Die folgende Implementierung der effizienteren Potenzrechnung ist auch möglich:
fun potenz''(a, b) = if b = 0
then 1
else if gerade(b)
then potenz''(quadrat(a), b div 2)
else a * potenz''(a, b - 1);
Im Absatz 4.3.4 werden wir sehen, dass der then-Fall der Funktion potenz'' "endrekursiv" ist, d.h. dass der rekursiver Aufruf außer im if-then-else-Ausdruck in keinem weiteren zusammengesetzten Ausdruck vorkommt. Man merke, dass der else-Fall der Funktion potenz'' nicht endrekursiv ist. In diesem Absatz wird erläutert, warum Funktionen mit nur endrekursiven Aufrufe (wie im then-Fall der Funktion potenz'') gegenüber Funktionen mit nicht-endrekursiven Aufrufe (wie im else-Fall der Funktion potenz'') vorzuziehen sind.
Es ist leicht zu überprüfen, dass die Zeitbedarfsanalyse vom Absatz 2.11.5 ebenfalls auf die Funktion potenz'' zutrifft.