═══ 1. Eine kleine Referenz fБr Standard ML ═══ Es folgt eine kurze Darstellung der Grundlagen von SML in Anlehnung an "Functional Programming Using Standard ML" von П. WikstrФm und "ML Primer" vin Ryan Stansifer. Der Text ist dennoch selbst formuliert, Garantien fБr die Richtigkeit kФnnen nicht Бbernommen werden. Sollte jemand Fehler finden, wБrde ich mich freuen, wenn er mir diese mitteilt, damit ich sie in einer zukБnftigen Version beseitigen kann. ═══ 1.1. Die Sprache ═══ Standard ML (im folgenden: SML oder ML) ist eine funktionale Sprache (wie Lisp, Haskell), strongly typed (wie C++, nicht wie Smalltalk) und ohne lazy evaluation (nicht wie Miranda, Haskell). ML hat keine echten objektorientierten Elemente (wie - glaube ich - Haskell von sich behauptet). ML ist keine reine funktionale Sprache (wie FP), da Seiteneffekte mФglich sind, und Referenzen gebildet werden kФnnen. ML hat viele moderne Sprachelemente, wie 1. Pattern matching 2. Exception handlling 3. Polymorphismus 4. Rekursive Datenstrukturen ═══ 1.2. Basistypen ═══ Dieser Abschnitt beschreibt die grundlegenden Datentypen int, real und string. ═══ 1.2.1. unit ═══ Der Datentyp unit ist der einfachste in SML. Es gibt genau ein Element nДmlich (). ═══ 1.2.2. bool ═══ Boolesche Werte werden mit dem Datentyp bool ausgedrБckt. Es gibt (natБrlich) genau zwei Werte, nДmlich true und false. SДmtliche Vergleichsoperatoren <,>,>=,=,... liefern bool. Logische VerknБpfungen gestatten die operetoren andalso, sowie orelse. ═══ 1.2.3. int ═══ Integer sind 32-Bit breite ganze Zahlen. Beispiel: 2:int. Negative Zahlen werden mit ~ dargestellt. Beispiel: ~3. Standardfunktionen: ┌───────────────┬──────────────────────────────┐ │div │ganzzahlige Division │ ├───────────────┼──────────────────────────────┤ │mod │Rest der Division │ ├───────────────┼──────────────────────────────┤ │abs │Absolutbetrag der Zahl │ └───────────────┴──────────────────────────────┘ ═══ 1.2.4. real ═══ Real stellt Gleitkommazahlen dar. Beipiel: ~3.14:real. ~ bezeichnet das negative Vorzeichen. Standardfunktionen: ┌───────────────┬──────────────────────────────┐ │floor │abrunden (real->int) │ ├───────────────┼──────────────────────────────┤ │sqrt │Quadratwurzel │ ├───────────────┼──────────────────────────────┤ │abs │Absolutbetrag der Zahl │ └───────────────┴──────────────────────────────┘ ═══ 1.2.5. string ═══ Strings werden in doppelten AnfБhrungszeichen eingeschlossen. Bsp.: "hello, world":string. Einzelne Zeichen werden als String der LДnge 1 dargestellt. Es kФnnen C-Escape-Sequenzen angegeben werden. z.B. "\n"; Standardfunktionen: ┌───────────────┬────────────────────────────────────────────────────────────┐ │ord │Umwandeln des ersten Zeichens in ASCII Wert (string->int) │ ├───────────────┼────────────────────────────────────────────────────────────┤ │chr │Umwandeln einer Zahl in ASCII-Zeichen (int->string) │ ├───────────────┼────────────────────────────────────────────────────────────┤ │size │LДnge des Strings │ ├───────────────┼────────────────────────────────────────────────────────────┤ │^ │Verkettung zweier Strings (s1^s2;) │ ├───────────────┼────────────────────────────────────────────────────────────┤ │<,>,=,... │ Vergleich zweier Strings │ ├───────────────┼────────────────────────────────────────────────────────────┤ │makestring │Erzeugt String des Ausdrucks (makestring(2+3);) │ ├───────────────┼────────────────────────────────────────────────────────────┤ │explode │Erzeugt eine Liste mit Strings ("hi" > ["h","i"]) │ ├───────────────┼────────────────────────────────────────────────────────────┤ │implode │Gegenteil von explode (["he","llo"] > "hello") │ └───────────────┴────────────────────────────────────────────────────────────┘ ═══ 1.3. Paare und n-Tupel ═══ n-Tupel werden dargestellt runde Klammern, in denen die Elemente durch Kommata voneinander getrennt sind. Bsp.: (5,true,false). Strengenommen wird auf diese Weise ein Konstruktor (pair constructor) bezeichnet, der ein Tripel mit den Datenelementen 5, true und false erzeugt. Der Datentyp des Tripels wird in diesem Fall mit int*bool*bool beschrieben. Auf diese Weise wird ein neuer Datentyp der Form int*bool*bool erzeugt, weshalb der *-operator auch type constructor genannt wird. Den neuen Datentypen kann man als das Kartesisches Produkt int x bool x bool auffassen. Standardfunktionen: ┌───────────────┬────────────────────────────────────────┐ │#n │liefert das n. Element des Tuples (z.B. │ │ │#2 (1,2,3);) │ └───────────────┴────────────────────────────────────────┘ Weitere Operationen mit Tupeln unter Pattern Matching ═══ 1.4. Records ═══ Records sind den Tupeln Дhnlich, jedoch sind die Elemente benannt. Records werden mit geschweiften Klammen geschrieben. Z.B. {name=hugo, groesse=186, gewicht=80}; Eine Funktion kann dann die folgende Gestalt haben: fun uebergewicht {name,groesse,gewicht}=gewicht+100>groesse; ═══ 1.5. Listen ═══ Eine Liste ist eine geordnete Sequenz von Elementen gleichen Typs. Dargestellt wird eine Liste mithilfe eckiger Klammern. [2,4,6] bezeichet eine Liste des Typs int list. [] bzw. nil bezeichnen die leere Liste. Standardfunktionen: ┌───────────────┬─────────────────────────────────────────────┐ │ :: │ Verketten einer eines Elements mit einer │ │ │Liste. (1::[2,3];) │ ├───────────────┼─────────────────────────────────────────────┤ │ hd │ gibt das erste Element der Liste zurБck ('a │ │ │list->a) │ ├───────────────┼─────────────────────────────────────────────┤ │ tl │ gibt alle Element auсer dem ersten zurБck │ │ │('a list->'a list). │ ├───────────────┼─────────────────────────────────────────────┤ │ @ │ verketten zweier Listen │ ├───────────────┼─────────────────────────────────────────────┤ │ rev │ "Spiegeln" einer Liste │ ├───────────────┼─────────────────────────────────────────────┤ │ len │ gibt die Zahl der Elemente einer Liste │ │ │zurБck │ ├───────────────┼─────────────────────────────────────────────┤ │ map │ Berechnet die Funktion f fБr jedes Element │ │ │einer Liste. map f [1,2]; │ └───────────────┴─────────────────────────────────────────────┘ ═══ 1.6. Deklarationen ═══ In diesem Abschnitt wird beschrieben, wie Variablen, Funktionen, ... definiert und implizit deklariert werden. ═══ 1.6.1. Variablen ═══ Eine Variable wird durch val x=5; deklariert/definiert. ═══ 1.6.2. Funktionen ═══ Funktionen werden mit fun f x = x*4; deklariert. Der Typ dieser speziellen Funktion wird dann mit fn:int->int bezeichnet. Eine Funktion ohne Parameter (fn:unit->int) kann durch fun f () = 5; deklariert werden. Andererseits kann eine Funktion Parameter benБtzen ohne eine Ausgabe zu haben. (fun f x=() ergibt fn:int->unit). Achtung: Diese Funktionen sind nur sinnvoll, wenn sie Seiteneffekte haben, die in einer funktionalen Sprache vermieden werden mБssen. Rekursion ist mit dieser Form der Definition mФglich. Funktionen kФnnen auch durch val f = fn x=>x*4; deklariert werden. Somit kommt zu Ausdruck, daс auch Variablen letztendlich 0-stellige Funktionen sind. Bei dieser zweiten Form der Definition ist kein RБckbezug auf den eigenen Namen (und damit keine Rekursion) mФglich. Rekursive Funktionen mБssen daher mit "rec" explizit als rekursiv definiert werden: val rec fac=(fn=>if n=0 then 1 else n*fac(n-1));. ═══ 1.6.3. Neue Datenobjekte (Enumeration) ═══ mit datatype kФnnen neue Datenobjekte kreiiert werden. Die Deklaration lautet: datatype tag=mo|di|mi|do|fr|sa|so; Ein einzelnes Element (z.B. do) ist dann vom Typ tag. Also gilt do:tag. ═══ 1.7. lokale Deklarationen ═══ Dieser Abschnitt beschreibt Deklarationen lokal zu AusdrБcken und anderen Deklarationen. ═══ 1.7.1. AusdrБcke ═══ mit let ... in ... end kann eine Deklaration lokal in einem Ausdruck erfolgen. Bsp.: let val pi=3.14 in pi*d end; ═══ 1.7.2. Deklarationen ═══ mit local ... in ... end kann eine Deklaration in einer anderen Deklaration erfolgen. Bsp.: local fun flaeche=... in fun vol=... end; ═══ 1.8. Pattern Matching ═══ Das Pattern Matching gestattet die Benutzung von Mustern und Wildcards. Pattern Matching wird schon bei der einfachen Zuweisung benutzt. Z.B. val x=4; oder val (x,y)=(2,false); Als Wildcard kann das Zeichen "_" eingesetzt werden. Es steht fБr einen beliebigen Wert. So gibt die Funktion fun fst (x,_) = x; den ersten Wert eines Tupels zurБck. HДufiger ist die Anwendung bei Funktionen im Sinne einer Fallunterscheidung. So z.B. in fun f 0=0 | f _=1;. Insbesondere gilt dies bei Enumerationen. Muster lassen sich mit dem SchlБsselwort as benennen. Die Funktion fun mirror (p as (x,y))=(p,(y,x)); fБhrt bei Eingabe von mirror (1,2) zu ((1,2),(2,1)). Muster werden sequentiell getestet. Redundante Muster fБhren ebenso wie unvollstДndige Muster zu Warnungen. Eine Дhnliche Form des Pattern Matchings lДсt sich mit dem case-Konstrukt erreichen. Die Funktion fun f x=case x of 0=>0 | _=>1; hat die gleiche Semantik wie die Funktion oben. ═══ 1.9. Operatoren ═══ Operatoren kФnnen wie einfache Funktionen definiert werden. Z.B. fun != (x,y) = x<>y; fБr einen C-Дhnlichen "ungleich"-Operator. Mit infix != wird != zum Infix-Operator. nonfix macht Selbiges wieder rБckgДngig. infixr steht fБr rechtsassoziative Operatoren. Mit z.B. infixr 8 != kann zusДtzlich die PrДzidenz angegeben werden. Standard-Operatoren mit PrДzidenz ┌───────────────┬───────────────┬────────────────────────────────────────┐ │PrДzidenz │ Operator │ Bedeutung │ ├───────────────┼───────────────┼────────────────────────────────────────┤ │7 │ / │Division │ │ │div │ganzzahlige Division │ │ │mod │Rest │ │ │* │ │ ├───────────────┼───────────────┼────────────────────────────────────────┤ │6 │ + │Addition │ │ │- │Subtraktion │ │ │^ │Verkettung von Strings │ ├───────────────┼───────────────┼────────────────────────────────────────┤ │5 │ │Verkettung Element und Liste │ │ │:: │Verkettung zweier Listen │ │ │@ │ │ ├───────────────┼───────────────┼────────────────────────────────────────┤ │4 │ │gleich │ │ │= │ungleich │ │ │<> │kleiner │ │ │< │grФсer │ │ │> │kleiner gleich │ │ │<= │grФсer gleich │ │ │>= │ │ ├───────────────┼───────────────┼────────────────────────────────────────┤ │3 │ o │Funktionenverkettung │ │ │ │? │ └───────────────┴───────────────┴────────────────────────────────────────┘ ═══ 1.10. Ausnahmen ═══ SML stellt ein Exception-handling zur VerfБgung. Eine Ausnahme wird deklariert mit exception ex1 and ex2; Ein Ausnahme wird durch raise ex2 ausgeworfen. Ausnahmen sind natБrlich nur sinnvoll, wenn sie auch aufgefangen werden kФnnen. Das geschieht mit handle. Bsp: fun divide a b:real=(a/b) handle Quot=>9e999; Dadurch ergibt die Division durch Null "unendlich"; Viele Ausnahmen sind schon vordefiniert. Anm.: Die Verwandschaft des C++-Exception handlings mit dem von ML ist nicht zu Бbersehen. ═══ 1.11. High-order Funktionen ═══ Eine Funktion kann Argument oder Ergebis einer anderen Funktion sein. Letztere wird dann high-order-function genannt. Bsp.: - fun add x y:int = x+y; > val add = fn : int -> (int -> int) - val succ = add 1; > val succ = fn : int -> int - val x=succ 11; > val x = 12 : int Wichtig sind in diesem Zusammenhang das currying (Eine Funktion mit mehreren Argumenten mit einem Argumentstupel brechnen) und das uncurrying (Eine Funktion, die ein Argumentstupel benФtigt mit mehreren Argumenten aufrufen.) Def. der Funktionen: - fun curry f = fn x => fn y => f(x,y); (* s. Fkt.Dekl. *) > val curry = fn : (('a * 'b) -> 'c) -> ('a -> ('b -> 'c)) - fun uncurry f = fn (x,y) => f x y; > val uncurry = fn : ('a -> ('b -> 'c)) -> (('a * 'b) -> 'c) - uncurry add (2,3); > 5 : int ═══ 1.12. Rekursion ═══ Die Rekursion spielt bei SML eine sehr bedeutende Rolle. Folgende Grundtypen werden unterschieden: o lineare Rekursion: Jeder Aufruf fБhrt zu hФchstens einem weiteren rekursiven Aufruf. Bsp.: FakultДt o repepetive Rekursion (tail recursion): Der rekursive Aufruf ist die Дuсerste Aktion. Diese Form der Rekursion wird in Iteration umgewandelt und ist daher sehr effizient. Bsp. FakultДt o kaskadenartige (nichtlineare) Rekursion: Ein Aufruf kann zu zwei oder mehr weiteren Rekursiven Aufrufen fБhren. Bsp. Fibonacci-Zahlen o vernestete Rekursion (nested recursion): Ein Parameter des rek. Aufrufs stellt wieder einen rekursiven Aufruf dar. Bsp. Ackermannfunktion o verschrДnkte Rekursion: Zwei oder mehr Funktionen rufen sich gegenseitig rekursiv auf. ═══ 1.13. Datentypen ═══ Neue Datentypen kФnnen auf vielfДltige Weise definiert werden. o Enumeration: datatype TAG=Mo|Di|Mi|Do|Fr|Sa|So; o Konstruktor: datatype COMPLEX=Complex of real*real; o Union Types: datatype NUMBER=Int of int | Real of real; o Rekursive Typen: datatype NAT=Zero | Succ of NAT; Auf diese Weise werden komplett neue Datentypen mit den dazugehФrigen Konstruktoren geschaffen. D.h. Int(4) erzeugt den Typen NUMBER. Eine "AbkБrzung" fБr Typen kann durch type COMPLEX=real*real; geschaffen werden. In diesem Fall wird kein grundsДtzlich neuer Typ erzeugt. Es kann also nicht zwischen COMPLEX und real*real unterschieden werden. ═══ 1.14. Abstrakte Datentypen ═══ Abstrakte Datentypen werden Дhnlich wie einfache Datentypen definiert. ZusДtzlich wird noch ein Satz von Variablen und Funktionen deklariert. Beispiel: abstype 'a QUEUE = Queue of 'a list with exception Empty val Empty = Queue nil fun Enter e (Queue es) = Queue (e::es) ... end; ═══ 1.15. Streams ═══ SML unterstБtzt mittels Streams die Dateiein- und ausgabe. Dateien werden geФffnet mittels: val outfile=open_out "datei.out"; val infile=open_in "datei.in"; Die Streams std_in und std_out sind vordefiniert. Mit den Standardfunktionen input und output kann man leicht eine Funktion echo definieren: fun echo()=if lookahead std_in="." then () else (output(std_out,input(std_in,1));echo()); ═══ 2. reservierte WФrter ═══ 1. abstype 2. and 3. andalso 4. as 5. case 6. do 7. datatype 8. else 9. end 10. exception 11. fn 12. fun 13. handle 14. if 15. in 16. infox 17. infixr 18. let 19. local 20. nonfix 21. of 22. op 23. orelse 24. raise 25. rec 26. then 27. type 28. val 29. while 30. ( ) 31. [ ] 32. { } 33. , 34. : 35. ; 36. ... 37. | 38. = 39. => 40. -> 41. _ 42. #