3.2 Einführung in ML

Literatur: R. Harper: Introduction to Standard ML, Carnegie Mellon University 1986–1993; siehe WWW-Seite L.C. Paulson: ML for the Working Programmer, Cambridge University Press 1991.

3.2.1 Sprachübersicht

• Funktionen sind Daten erster Klasse. Insbesondere können sie Argumente und Ergebnisse von Funktionsaufrufen sein oder in Variablen gespeichert werden. Die Anwendung (rekursiver) Funktionen auf ein Argument ist der hauptsächliche Kontrollmechanismus der ML-Programmierung.

• Interaktivität

• starke Typisierung: Typinferenz durch den Übersetzer, garantiert kein Typfehler zur Laufzeit

• polymorphes Typsystem mit automatisch inferierbaren allgemeinsten Typen

• parametrisierte, abstrakte Datentypen

• statische Bindung von Variablen

• typsichere Ausnahmebehandlung

Geschichte: Erste Versionen um 1975 von Gordon, Milner, Wadsworth im Zusammenhang mit Semantik und Verifikation von Programmiersprachen (LCF). Standard ML, welches in dieser Vorlesung behandelt wird, beinhaltet Ideen von HOPE und von Cardellis ML-Dialekt. Das Modulsystem stammt von MacQueen, vgl. Literaturangaben in Harpers Buch.

3.2.2 Primitive Ausdrücke, Werte und Typen

Interaktion

hg@mpii02039(88)% sml
Standard ML of New Jersey, Version 0.93, February 15, 1993
val it = () : unit
- 3+2;
val it = 5 : int
- 3+it;
val it = 8 : int
- it+cos(3.0);
std_in:4.1-4.11 Error: operator and operand don't agree (tycon mismatch)
  operator domain: int * int
  operand:         int * real
  in expression:
    + : overloaded (it,cos (3.0))
- real(it)+cos(3.0);
val it = 7.01000750339955 : real
-

Einheitstyp Der Type unit hat den einzigen Wert (). Wird gebraucht, wenn Wert uninteressant oder für parameterlose Funktionen.

Booleans

- if not true then true andalso false else true;
val it = true : bool

• then-Typ = else-Type

• else zwingend notwendig

• vordefinierte Funktionen not, andalso, orelse

Ganze Zahlen

- 75;
val it = 75 : int
- ~13;
val it = ~13 : int

• vordefinierte Funktionen +, -, *, div, mod

• vordefinierte Relationen <, <=, >, >=, =, <>,

Zeichenreihen

- "Programmiersprachen WS94/95";
val it = "Programmiersprachen WS94/95" : string
- "Programmiersprachen " ^"WS94/95";
val it = "Programmiersprachen WS94/95" : string
- size it;
val it = 27 : int
- "\"Programmiersprachen\" WS94/95";
val it = "\"Programmiersprachen\" WS94/95" : string
- size it;
val it = 29 : int

Reelle Zahlen

- 3.14
= ;
val it = 3.14 : real
- 3.14;
val it = 3.14 : real
- 3E2;
val it = 300.0 : real
- 3.14E3;
val it = 3140.0 : real

• vordefinierte Funktionen +, -, , *, /, sin, sqrt, exp, usw.

• vordefinierte Relationen <, <=, >, >=, =, <>,

• keine implizite Anpassung zwischen int und real; keine gemischten Operandentypen in binären Funktionen und Relationen; explizite Anpassung durch real bzw.

     floor.

Tupel

- (true, ());
val it = (true,()) : bool * unit
- (1,false,"WS94/95",(true,12));
val it = (1,false,"WS94/95",(true,12)) : int * bool * string * (bool * int)
- (14 mod 3, not false) = (1+1, not (not true));
val it = true : bool
- (true, 7) = (true, 8);
val it = false : bool
- (true, 7) = (true, ());
std_in:0.0-0.0 Error: operator and operand don't agree (tycon mismatch)
  operator domain: (bool * int) * (bool * int)
  operand:         (bool * int) * (bool * unit)
  in expression:
    = ((true,7),(true,()))

• geordnete Tupel beliebiger Länge n ≥ 2

• Gleichheit komponentenweise

• Typausdrücke von der Form τ_{1} ∗ τ_{2} ∗ … ∗ τ_{n}

Listen

- nil;
val it = [] : 'a list
- 3 :: 4 :: nil;
val it = [3,4] : int list
- [3,4];
val it = [3,4] : int list
- (3 :: nil) :: (3 :: 4 :: nil) :: nil;
val it = [[3],[3,4]] : int list list
- ["Das", "ist", "eine", "Liste"];
val it = ["Das","ist","eine","Liste"] : string list

Listen werden konstruiert über nil (leere Liste) und :: (ausgesprochen ”cons“), womit ein neues Element an eine bestehende Liste vorne angehängt wird. Man spricht von einem rekursiven Datentyp.

Listen mit Elementen e_{1}, …, e_{n}, n ≥ 0, haben die Form e_{1} :: ... :: e_{n} :: nil, wofür auch [e_{1} :: ... :: e_{n}] geschrieben werden darf.

Die Elemente einer Liste müssen alle vom selben Typ τ sein, in welchem Fall dann τ list der Typ der Liste ist.

Der Typ von nil enthält die Typvariable 'a, da nil Element eines jeden Listentyps ist. nil ist ein polymorphes Objekt, welches aber nur in Listentypen enthalten ist. Ein Typ, der eine Typvariable enthält, heißt ein polymorpher Typ. Instanzen eines polymophen Typs erhält man, indem man Typvariablen durch Typen substituiert. Monomorphe Typen (Monotypen) sind Typen, die keine Typvariablen enthalten.

Man beachte den Unterschied zwischen (parametrischem) Polymorphismus und Überladung von Bezeichnern, auch ad hoc Polymorphismus genannt, wie er z.B. bei + oder >= auftritt.

Verbunde Verbundtypen sind ähnlich then ”Pascal records“ und ”C structures“.

- {Name="Ganzinger", Alter=44};
val it = {Alter=44,Name="Ganzinger"} : {Alter:int, Name:string}
- {a=1,b=2} = {b=1+1, a=1};
val it = true : bool
- {a=1,b=2} = {b=1+1, c=1};
std_in:30.1-30.24 Error: operator and operand don't agree (tycon mismatch)
  operator domain: {a:int, b:int} * {a:int, b:int}
  operand:         {a:int, b:int} * {b:int, c:int}
  in expression:
    = ({a=1,b=2},{b=+ : overloaded (1,1),c=1})

Verbundtypen sind endliche Mengen von benamten Feldern der Form {l_{1}=v_{1},…,l_{n}=v_{n}}, n ≥ 1.^{1}. Namen müssen eindeutig sein. Die zugehörigen Typausdrücke haben die Form {l_{1}:τ_{1},…,l_{n}:τ_{n}}, wenn τ_{i} der Typ von v_{i} ist. Die Namen der Felder zählen also zur Typinformation. Die Reihenfolge der Felder ist irrelevant.

Tupeltypen τ_{1} ∗ τ_{2} ∗ … τ_{n} sind Kurzschreibweisen für Verbundtypen der Form {1:τ_{1},…,n:τ_{n}}. D.h. die Ausdrücke (2,true) und {1=2,2=true} haben dieselbe Bedeutung. Als Feldnamen sind also Identifikatoren und ganze Zahlen zugelassen.

Bemerkungen Man beachte die Uniformität der Art und Weise, wie in ML Werte der verschiedenen Typen mit Konstruktoren aus Konstanten gebildet werden. Jeder Wert ist also ein Term, an dessen Blättern Konstante atomarer Typen (Zahlen) oder (nullstellige) Konstruktoren (z.B. nil, true) stehen und an deren inneren Knoten (mehrstellige) Konstruktoren (z.B. ::, ( , ), {name= , alter= }) angewendet sind. Obwohl Konstruktoren Daten in eindeutiger Weise konstruieren, sind sie aber keine Funktionen im technischen Sinne von ML.

3.2.3 Funktionsdefinitionen

Funktionsdefinitionen sind spezielle Formen von bindungserzeugenden Konstrukten, die wir in ihrer ganzen Schönheit noch später kennenlernen werden.

Funktionen werden verwendet, indem sie auf Argumente angewendet werden. Funktionen in ML sind allesamt einstellig. Mehrstellige Funktionen können entweder durch tupelwertige Argumente oder durch Funktionen höherer Ordnung realisiert werden. Applikationen haben die Form e1 e2. Eine Applikation ist typmäßig korrekt, wenn e1 einen Typ von der Form σ → τ und e2 dann den Typ σ hat. Ergebnis der Anwendung ist in diesem Fall ein Wert vom Typ τ. Diese Typbedingung garantiert, daß e1 bei seiner Auswertung^{2} eine Funktion liefern wird, die Argumente vom Typ von e2 akzeptiert. σ bzw. τ heißen die Typen des Definitions- bzw. Wertebereichs der Funktion.

1Der leere Verbund {} ist eine andere Notation für () und hat den Typ unit

- size;
val it = fn : string -> int
- not;
val it = fn : bool -> bool
- not 3 ;
std_in:4.1-4.5 Error: operator and operand don't agree (tycon mismatch)
  operator domain: bool
  operand:         int
  in expression:
    not 3
- size "abc";
val it = 3 : int

Es folgen einfache Beispiele für Funktionsdefinitionen.

- fun twice x = 2*x;
val twice = fn : int -> int
- twice 4;
val it = 8 : int
- fun fact x = if x=0 then 1 else x*fact(x-1);
val fact = fn : int -> int
- fact 5;
val it = 120 : int
- fun plus(x,y) = x+y;
std_in:10.18 Error: overloaded variable cannot be resolved: +
- fun plus(x,y):int = x+y;
val plus = fn : int * int -> int
- plus (3,6);
val it = 9 : int

Folgendes sind die Bestandteile solcher Definitionen:

• Name der zu definierenden Funktion, z.B. plus,

• Parametermuster, z.B. (x,y),

• optionale Ergebnistypbeschränkung, z.B. :int, die vornehmlich zur Auflösung von Typmehrdeutigkeiten, die aus Überladung entstehen, verwendet werden,

• Ausdruck, der das Funktionsergebnis zum jeweiligen Parametermuster spezifiziert, z.B. x+y.

Die Parametermuster liefern Bindungen an die in ihnen enthaltenen Variablen, wenn das Muster auf den jeweiligen aktuellen Parameterwert gelegt wird. Wesentlich ist, daß mehr als eine Regel (oder Klausel) der Form

2Terminierung wird bei Aussagen dieser Form immer unterstellt. Natürlich kann kein statisches Typkonzept Terminierung garantieren.

        <Funktionsname> <Muster> = <Ergebnisausdruck>

angegeben werden darf. Im allgemeinen sind es soviele, daß die Vereinigung der Muster alle möglichen Parameterwerte überdeckt. Die Klauseln werden durch | getrennt. Paßt mehr als eine Regel, wird die erste passende verwendet. Dafür jetzt ein Beispiel.^{3}

- fun isNil   nil  = true
=   | isNil (_::_) = false;
val isNil = fn : 'a list -> bool
- isNil nil;
val it = true : bool
- isNil [2,3];
val it = false : bool
- isNil ["aa","ab"];
val it = false : bool
- fun append (nil,l) = l
=   | append (hd::tl,l) = hd :: append(tl,l);
val append = fn : 'a list * 'a list -> 'a list
- append([],[1,2,3]);
val it = [1,2,3] : int list
- append(["auch", "eine"],["Liste"]);
val it = ["auch","eine","Liste"] : string list

Bemerkungen:

• Beide Funktionen sind polymorph. Man bemerke aber bei append, daß diese Funktion zwar Listen von beliebigem Elementyp akzeptiert, daß aber die Elementtypen beider Argumentlisten gleich sein müssen (Typ αlist ∗ αlist → αlist). Der ML-Übersetzer findet den allgemeinsten Typ selbst heraus.

• append ist rekursiv. Auf der rechten Seite der Regeln sind also alle links eingeführten Bindungen, einschließlich der zu definierenden Funktion, sichtbar.

• Ist eine Teilstruktur eines Wertes irrelevant beim Mustertest, so verwendet man den Joker , siehe zweite Regel für isNil.

• Die Verwendung von Mustern und Mustertest ist die einzige Möglichkeit, um auf Komponenten von Konstruktortermen zuzugreifen. Es gibt in ML keine expliziten Destruktoren.

Bevor wir zu interessanteren Beispielen kommen, wollen wir in Abschnitt ?? allgemeiner auf Identifikatoren, Bindungen und Deklarationen sowie Muster und Mustertest eingehen.

Funktionen müssen in SML nicht notwendig einen Namen haben. Sogennante λ-Ausdrücke der Form

    fn <Muster> => <Ausdruck>

3Die =-Zeichen am Anfang von (Folge-)Zeilen ist Ausgabe des Interpreters wenn Eingaben über eine Zeile hinausgehen, nicht Eingabesyntax!

definieren namenlose Funktionen, die Argumentmuster Muster auf Ergebnisse Ausdruck abbilden. Diese kann man direkt in Applikationen verwenden oder in Deklarationsausdrücken. Dann sind auch (nichtrekursive) Funktionsdefinitionen spezielle Form von Wertedefinitionen.

fn x => x;
- val it = fn : 'a -> 'a
- it(1);
val it = 1 : int
- val id = fn x => x;
val id = fn : 'a -> 'a
- val plus = fn (x,y):int*int => x+y;
val plus = fn : int * int -> int
- plus(1,3);
val it = 4 : int

Diesen Aspekt werden wir in Abschnitt ?? vertiefen.

3.2.4 Deklarationen

Alle Identifikatoren müssen vor ihrer Verwendung deklariert werden. Bei ihrer Deklaration werden sie zu einem Wert gebunden. Wesentlich ist, daß im Gültigkeitsbereich einer Deklaration dieser Wert fest ist und nicht,, wie etwa in imperativen Sprachen, durch eine Wertzuweisung verändert werden kann. Die ML-Variablen sind also eher vergleichbar den Konstanten (vgl. const-Deklarationen in Pascal) imperativer Sprachen.

- val x = 4*5;
val x = 20 : int
- val s = "abc"^"def";
val s = "abcdef" : string
- val p = ( x, s );
val p = (20,"abcdef") : int * string

Phrasen der Form

        val <Identifikator> = <Ausdruck>

heißen Wertedefinitionen. Ihr Effekt ist die Bindung des Identifikators an den Wert der rechten Seite.

Die Redefinition eines Identifikators verdeckt die bereits bestehende Bindung in demselben Sinne, wie in einer inneren Prozedurdefinition in Pascal durch Redeklaration eine äußere Bindung verdeckt wird. Was der Unterschied zwischen einer Redefinition und einer Pascal-Wertzuweisung ist, werden wir später noch sehen,

- val x = 17;
val x = 17 : int
- val y = x;
val y = 17 : int
- val x = true;
val x = true : bool
- val z = x;

val z = true : bool
- val x = 17;
val x = 17 : int
- val x = true and y = x;
val x = true : bool
val y = 17 : int

Folgene Regeln und Terminologie definieren die Semantik dieser Konstrukte:

• Deklarationen erzeugen Bindungen und Mengen von Bindungen bilden eine Umgebung. Es gibt verschiedene Arten von Deklarationen, z.B. für Werte val oder Funktionen fun; später sehen wir noch andere Arten.

• Die Auswertung eines jeden Ausdrucks erfolgt in einer bestimmten Umgebung, die dann die Werte für die Variablen des Ausdrucks festlegt.

• Die rechte Seite einer Wertdeklaration wird in der alten, bisherigen Umgebung ausgewertet (der Wert des letzten y ist 17 und nicht true). Bei Funktionsdefinitionen

            fun f m_{1} = e_{1} | ... | f m_{n} = e_{n}

ist dies anders. Hier können die Definitionen rekursiv sein und die neuen Bindungen für f und für die Variablen in den Mustern m_{i} sind bereits in e_{i} sichtbar. Letztere sind nur lokal in den e_{i} sichtbar.

• Deklarationen können durch bestimmte Kombinatoren zusammengesetzt werden. So bedeutet d1 ; d2 die sequentielle Komposition^{4} von Deklarationen d1 und d2. d1 wird in der gegebenen Umgebung E ausgewertet. Der Effekt ist, daß die neuen Bindungen gemäß d1 zu E hinzugefügt werden und alte Bindungen in E für redefinierte Identifikatoren verdeckt werden. In dieser neuen Umgebung erfolgt die Auswertung von d2, die dann in gleicher Weise die Umgebung modifiziert. Auf Interpreter-Eingabeebene sind also nacheinanderfolgende, durch ”;“ getrennte Deklarationen als in diesem Sinn sequentiell zusammengesetzt zu betrachten.

• and trennt parallele Deklarationen von mehreren verschiedenen Identifikatoren. Die Definitionsrümpfe werden alle in der alten Umgebung ausgewertet.

Der Gültigkeitsbereich von Deklarationen kann lokal beschränkt werden.

- local val x = 10
= in
=       val u = x*x + x*x
=       val v = 2*x + (x div 5)
= end;
val u = 200 : int
val v = 22 : int

local erzeugt lokale Deklarationen für eine (zusammengesetzte) Deklaration zwischen

in und end.

4Das Semikolon ist optional. Man kann auch einfach d1 und d2 hintereinanderschreiben.

- let val x = 10
= in
=     x*x + 2*x +1
= end;
val it = 121 : int

let erzeugt lokale Deklarationen für die Auswertung eines Ausdrucks zwischen in und

end.

3.2.5 Muster

Wir haben schon bei den Funktionsdefinitionen gesehen, daß die Verwendung von Mustern die einzige Möglichkeit ist, um auf Substrukturen von Konstruktortermen zuzugreifen. Muster sind Konstruktorterme, die Variablen enthalten. Es ist nur natürlich, Muster auch in Wertdeklarationen zuzulassen. D.h. Wertdeklarationen haben die allgemeinere Form

        val <Muster> = <Ausdruck>,

bei der der Asudruck in der gegebenen Umgebung ausgewertet wird, das Muster des entstehenden Wertes gestestet wird und im Erfolgsfall die Variablen des Musters an die entsprechenden Subterme gebunden werden.

- val x = (17,true);
val x = (17,true) : int * bool
- val (left,right) = x;
val left = 17 : int
val right = true : bool
- val (left,false) = x;
std_in:48.1-48.20 Warning: binding not exhaustive
          (left,false) = ...
uncaught Bind exception std_in:48.1-48.20

• Warnung, wenn Muster nicht alle Möglichkeiten (diese sind nach der Typinferenz bekannt) abdeckt;

• Ausnahmebehandlung wird angestoßen, wenn Muster nicht paßt.

• Alle Muster müssen linear sein, d.h. Mehrfachvorkommen von Variablen sind nicht erlaubt.

Weitere Beispiele:

- val l = [1,2,3];
val l = [1,2,3] : int list
- val [x,y,z] = l;
std_in:49.1-49.15 Warning: binding not exhaustive
          x :: y :: z :: nil = ...
val x = 1 : int
val y = 2 : int

val z = 3 : int
- val r = {name="hugo", used = true};
val r = {name="hugo",used=true} : {name:string, used:bool}
- val {used=u, name=n} = r;
val n = "hugo" : string
val u = true : bool
- val {used=u, ...}=r;
val u = true : bool
- val u = #used r;
val u = true : bool
- fun uu {used = u, ...} = u;
std_in:55.1-55.26 Error: unresolved flex record in let pattern
  type: {used:'Y, '...Z}

• ... ist der Joker, der auf eine beliebige Anzahl von Verbundfeldern paßt.

• Bei Verbundtypen müssen alle Felder und deren Typen aus dem Kontext hervorgehen, eventuell müssen Typeinschränkungen verwendet werden. Den Polymorphismus, der in der objektorientierten Programmierung durch Verbunderweiterung erfolgt (Vererbung von Instanzvariablen), hat man in SML leider nicht. In einer ML-Variante von Cardelli gab es ihn einmal.

• #name r ist eine abkürzende Schreibweise für den Zugriff auf das Feld name eines Verbundes r.

Muster brauchen nicht flach zu sein, sondern können beliebig geschachtelte Terme sein.

- val l = [(1,["H","G"]),(2,["U","W"])];
val l = [(1,["H","G"]),(2,["U","W"])] : (int * string list) list
- val _::(key,_::second)::tl = l;
val key = 2 : int
val second = ["W"] : string list
val tl = [] : (int * string list) list