ProMo

Wir arbeiten mit SML/Standard ML. In der New Jersey Implementierung [Wiki], [Projekt Seite].

A new up to date PKGBUILD can be found in a Arch Linux Forum post. There is also an AUR package from 2010.

The installation process for the AUR package is as usual (don't do it as root).

1. Download the tarball (Not the PKGBUILD)
2. untar the package
3. cd into the extracted directory
4. Build the package with makepkg
5. Install the package with sudo pacman -U *pkg.tar.xz

The installation process of the forum package is the same expect for the steps 1 and 2, it can be omitted.

• Nice language tutorial auf englischem SML Wiki Eintag.
• Cheat Sheat.
• Language overview (Print!!!)

• Alphabetische namen
  • a-z (Anfang)
  • A-Z (Anfang)
  • 0-9
  • _
  • '
• Symbolische Namen
  • ! % & $ # + - * / : < = > ? @ \ ~ ` ^ und |

Beide immer verwendbar, aber nicht mischbar.

ACHTUNG: o nicht verwenden. Ist bereits Infix Operation der Komposition.

• Typ/Datentyp: Menge von Werten + Operationen auf Weten
  • Vordefinierte Typen
  • Benutzerdefinierte Typen

• ~42; OK
• ~~42; Fehler: „unbound variable or constructor: ~~“
• ~ ~42; OK
• ~ ~ 42; Fehler: „operator and operand don't agree [overload]“
• ~(~42); OK
• ~(~ 42); OK
• ~ (~42); OK
• ~ (~ 42); OK

+ ist Links assiziativ: 1 + 2 + 3 = (1 + 2) + 3

Implizites int wenn nicht allgemein genug für 'a aber zu unspezifisch für einen Typ. Z.B. ist fun f(x) = x + x vom Typ int * int -> int und nicht vom Typ 'a * 'a -> 'a. Alternativen sind:

• fun f(x : real) = x + x;
• fun f(x) : real = x + x;
• fun f(x : real) : real = x + x;

Führende 0 erlaubt.

• .42 nicht erlaubt
• trunc() entspricht floor() für positive Zahlen
• trunc() entspricht ceil() für negative Zahlen
• Real.compare : real * real -> order
• order = LESS/EQUAL/GREATER

„aaa\<whitespace Zeichen z.B. Zeilenumbruch>\bbb“ also z.B. bei der Eingabe:

- "aaa\

   \bbb";
it = "aaabbb" : string

• ASCII

- fun f() = 42;
val f = fn : unit → int

- fun f(x) = ();
val f = fn : 'a → unit

• Verschiedene Element-Typen
  (1, „a“)
• Typ
  int * real
• Einstellige Tupel werden reduziert
  (((3))) → 3
• Vergleich
  (eins, zwei) = (1, 2)
• Vergleich + Reduzierung
  (((3))) = 3
• Zuweisung/Pattern Matching (so wie bei Funktionen)
  val (a:int, b) = someTupel
• Zugriff auf Element
  val a = #2 someTupel
• Null-Stelliges Tupel = unit
  ()

• Verschiedene Element-Typen
  { b = 1.0, a = „foo“ } : {a:real, b:string }
• Verschiedene Verbund-Typen
  {a = 1.0, b = 2.0} <> {aaa = 1.0, bbb = 2.0}
• Typ
  {a:int, b:real}
• Vergleich: Reihenfolge Egal
  {a = 1.0, b = 2.0} = {b = 2.0, a = 1.0}
• Zugriff auf Element
  #a {a = 1.0}
• Zuweisung von Record (Variablen Name = Komponenten Name)
  val {a, b} = {a = 1.0, b = 2.0}
• Zuweisung von Record + Maping
  val {c=a, d=b} = {c=„a“, d=„b“}
• Zuweisung von Tuper + Maping
  val {1=a, 2=b} = („a“, „b“)
• ABER: Zuweisung von Tupel zu Tupel + Maping
  val (1=a, 2=b) = („a“, „b“) FEHLER
• Reduzierung zu Tupel (n >= 2)
  {2=„b“, 1=„a“} → („a“, „b“)
• Reduzierung zu unit (n = 0)
  {2=„b“, 1=„a“} → ()
• ABER: Keine Reduzierung (n = 1)
  {2=„b“} → {2=„b“}
• Vergleich + Reduzierung (n >= 2)
  {2=„b“, 1=„a“} = („a“, „b“)
• ABER: Vergleich + Reduzierung FUNKTIONIERT AUCH (n = 1)
  {1=„a“} = {1=„a“}

#asd ist eine Funktion, läst sich also auch so schreiben (Math.sqrt o #y) {x = 1.2, y = 3,4}.

• Gleiche Element-Typen
  [1, 2, 3] : int list
• Typ
  int list
• Leere Liste ist Polymorph (es wird nur ein nil benötigt)
  nil : 'a list
• Listen Konstruktor „cons“ (Rechtsassoziativ)
  a :: b :: c :: [d, e] = a :: (b :: (c :: [d,e]))
• Zuweisung
  val [a, b, c] = [3, 2, 1];

fold[l/r] hatt 3 Parameter! Startwert nicht vergessen! Liste erst am schluss (macht mit unvolständigen Parametern und currying sinn)!

1. Funktion
2. Start Wert
3. Liste

Bei der Funktion ist der erste Parameter immer der listen Wert!

1. Wert aus der Liste
2. Agregiertert Wert

• foldl geht von links durch die Liste (fängt links an)
• foldr geht von rechts durch die Liste (fängt von rechts an)

Achtung currying: Richtig Klammern

- foldl (fn (a, b) => let val t = print("l = "^a^"\tr = "^b^"\n") in a^b end) "#" (["1", "2", "3"]);
l = 1	r = #
l = 2	r = 1#
l = 3	r = 21#
val it = "321#" : string

- foldr (fn (a, b) => let val t = print("l = "^a^"\tr = "^b^"\n") in a^b end) "#" (["1", "2", "3"]);
l = 3	r = #
l = 2	r = 3#
l = 1	r = 23#
val it = "123#" : string

• 0 Erster Eintrag
• Nicht referenzentransparent (Da Arrays pointer sind)

- NONE;
NONE : 'a option
 
- NONE : int option;
NONE : int option
 
- SOME 4.2;
SOME 4.2 : real option

• Nicht referenzentransparent
• print() ist synonym für TextIO.print()
• TextIO.vector verhält sich wie string
• TextIO.elem verhält sich wie char

• TextIO: char option / string
• BinIO: 8 Bit

Aufgaben:

• Ermittlung des Typs eines Ausdrucks aus Typ-Constraints (Bei der deklaration)
• Überprüfung von Typ-Constraints (Bei der anwendung)

Arten:

• Dynamisch: Zur Laufzeit
• Statisch: Bei der Übersetzung

Statisch typisierte Sprache = Ausschließlich statische Typprüfung = SML

Vorteile:

• Fehlererkännung während der Programmierung
• Schneller zur Laufzeit
• Einfachere Übersetzung
• Keine Typbedingen Laufzeitfehler

• Kein eigener Typ
• Synonym für Typen
  • Typprüfung: Type-Constrains mit aufgelösten Typen ⇒ Kein eigener Typ (nur lesbarer)
  • Typermittlung: Synonym wird verwendet (lesbarer)
• Typabkürzung: type foo = int * int
• Polymorphe Typabkürzung
  • type 'a bar = 'a list
  • Instanziierung: int bar
  • Postfix!
• (2, 3) : foo
• (2, 3) : (int * int)

• Eigener Typ
  • Typkonstante
    datatype Farbe = Rot | Blau
  • Wertkonstruktoren (Öffentlich, kein Zugriff über z.B. Farbe.Rot)
    • 0-Stellig (angeblich Atomarer Wert)
      datatype Farbe = Rot | Blau
    • n-Stellig (angeblich Zusamengesetzter Wert)
      datatype Koordinate = Polar of real * real | Kart of real * real
Polar(1.0, 2.0) (Kein currying!)
      • Wertkonstruktor ist keine Funktion!
      • Polymorphe Datentypen
        datatype 'a dt = Foo of 'a list | Null
Foo([1, 2]) : int list dt
• Gleichheits Test wenn
  • 0-Stelliger Wert konstruktor
  • n-Stelliger Wert Konstruktor + typen Gleichheitstest Unterstützen
• induktive/rekursive Typdefinition (implizites rec)
  datatype Baum = Blatt | Knoten of Baum * Baum
  • Es Entsteht ein rekursiver Typ.

• Eigener Typ
• Gebündelt mit Deklarationen (val, exception, fun, …)
• Wertkonstruktor nur innerhalb des abstypes verwendbar.
• Innere Gestalt eines Wertes nicht sichtbar
  val Red = - : color
• Namen im „globalen space“
  • Unabhängigkeit des Klienten
  • Keine unbeabsichtige Verarbeitung interna

(* Vergleiche mit type Deklaraton:
type    color = rgb of int * int * int
*)
abstype color = rgb of int * int * int
with
  val red  = rgb(255, 0,   0);
  val blue = rgb(  0, 0, 255);
 
  exception fail;
 
  fun makeGreen(x) = rgb(0, x, 0);     (* Wertkonstruktor nur hier innerhalb verwendbar *)
end;
 
(* Zugriffüber globalen name space *)
makeGreen(20);
red;

• Hierarchische Struktur
• Named scope
  Struktur.deklaration

structure Name =
 
  struct
    <dec>
    <dec>
    ...
  end;

Signature-Constraint mit

• structure Name : NAME =
• structure Name : sig <spec> <spec> … end =

view / sicht: Unterspezifizierte Signatur

signature NAME =
 
  sig
    <spec>
    <spec>
    ...
  end;

Signatur Spezifikationen:

• val foo : int
• val foo : int -> int
• type foo
• type foo = int
• eqtype foo
• datytype foo = value(x) | …
• exception foo of int

• Nur ein Parameter
• Signatur muss angegeben werden
• „parametrisierte Struktur“

Erzeugen einer konkreten Struktur:

structure NameName = Name(OtherName)

• Verkleinert programme
• Macht übersichtlicher Programme
• Verkleinert wartungsaufwand

Polymorphe Typen (Polytyp): 'a oder 'a list gegenteil: Monotyp

Das gibt einen Fehler da der Typ des ausdrucks bei der Anwendung nicht festgestelt werden kann.

nil@nil;

Kapitel 5.4 in den Folien Lesen!!!!

• Typinferenz = Typprüfung, also:
  • Ermittlung des Typs eines Ausdrucks aus Typ-Constraints (Bei der deklaration)
  • Überprüfung von Typ-Constraints (Bei der anwendung)
• Typausdruck
  • atomar
    • Typkonstante: int, real
    • Typvariable
      • 'a (alpha)
      • ''a: Typ mit = definiert (also z.B. keine Funktion)
      • Wird an Typausdruck gebunden (atomar oder zusamengesetzt)
  • zusamengesetzt: int list (warum ist das keine typ konstante?)
    • Typkonstruktoren: (Bindet stärker) *, ->, …. (Bindet Schwächer) meist postfix oder infix
• Typconstraints
  • Ausdruck : Typausdruck
  • Auch: Typisierungsausdrück
  • Syntaktisch gleich zu Funktionen

Funktion $\subseteq$ Prozedur (D.h. nicht jede Prozedur ist auch eine Funktion, aber jede Funktion ist eine Prozedur)

Funktion:

• Liefert Ergebniss
• Kein Nebeneffekt
• Referenztransparent (Referenz-transparent): Gleiche Parameter ⇒ Gleiches Ergebniss (Gleicher Deklarationsbereich + Gleicher Ausdruck = Gleicher Wert)
  Verursacht durch:
  • Funktionale Variablen
  • Überschatten
  • Statische/Lexikalische Bindung

• Formaler Parameter: fun f(x) = x
• aktueller Parameter: f(8)

Prozeduren:

• SML hat auch Prozeduren z.B. use().
• Hat Nebenefekte z.B. werden neue Definitioen geladen.
• Sie liefern unit () zurück.

• 0: Konstante
• 1: Nur Konstanten als Parameter und Rückgabewert
• n: max(ord(Paramer) + ord(Wert)) + 1 (Funktionen höherer Ordnung)

fun f(a, b) = a+b;
f(1, 2);

fun f{a, b} = a+b;
f{a=1, b=2};

• val f = fn x ⇒ 42
• val rec f = fn x ⇒ 42 nur mit fn

fun f(x) = 42

Hat implizites rec

Currying ⇒ curried Funktion:

fun f x y = ...
val f = fn x => fn y => ...

ACHTUNG: val f = fn x y ⇒ … ist nicht möglich!

ACHTUNG: Einzelne Parameter richtig Klamern

infix io
fun x io y = ...
val (op io) = fn (x, y) => ...

• infix foo; fun p1 foo p2 = p1 + p2;
• infix 3 foo. Präzedenz = 3 (default: 0; bereich: 0 - 9)
• infix = liksassoziativ; infixr = rechtsassoziativ
• infix op1 op2 op3

infix 0 before
infix 3 o :=
infix 4 = <> > < >= <=
infixr 5 :: @
infix 6 + - ^
infix 7 * / div mod quot rem

op wandelt Infix in Präfix Funktion.

ACHTUNG bei * operator: Fehler (op *) da *) Einde eines Komentars ist. Korrekt: (op * ) (mit Leerzeichen)

Infix Operator o. Variablen/Funktionen dürfen nicht o heißen.

• Anwendungsreihenfolge
  • (f o g)(x) = f(g(x))
  • gleiche Reihenfolge
  • Erstes außen
  • SML
• Diagrammreihenfolge
  • (f o g)(x) = g(f(x))
  • Umgekehrte Reihenfolge
  • Erstes innen
  • Mathe

f(a, b, c) ist Ein-Stellige Funktion. Mit dem einen Parameter, dem Tupel (a, b, c). Denn es kann auch wie follgt Aufgerufen werden:

val params = (1, 2, 3);
f params;

http://www.mpi-sws.org/~rossberg/sml.html

else-Teil muss immer angegeben werden.

val f = fn n => if n = 42 then true else false;

fun f(n) = if n = 42 then true else false;

val f = fn 42 => true
         | n  => false;

fun f(42) = true
  | f(n)  = false;

local
  statement;
  statement;
  ...
  statement
in
  statement
end

Let ist nötig wenn ein Funktionsparameter aus in … in let … verwendet werden muss.

let
  statement;
  statement;
  ...
  statement
in
  expression
end

Mit

val x = 2;

let
  val x = 2*x
  val x = 3*x
in
  x
end;

Ergibt 12, da jedes val alles einzeln Auswertet und Zuweist (mit dem x der jeweils vorherigen Deklaration).

let
  val x = 2*x and y = 3*x
in
  x+y
end;

Ergibt 10, da val … and … alles auf einmal Auswertet und dann Zuweist (erst alles auswerten, dann alles auf einmal zuweisen).

let
  val x = 2*x and x = 3*x
in
  x
end;

stdIn:2.5-2.28 Error: duplicate variable in pattern(s): x

val … and … muss sein.

val rec a = fn 0 => false
             | n => b(n-1)
and
        b = fn 0 => true
             | n => a(n-1);

fun a(0) = false
  | a(n) = b(n-1)
and
     b(0) = true
   | b(n) = a(n-1);

• Nicht Speicheraufwendiger
• Nicht Zeitaufwendiger
• Weniger Speicher nötig
• Aufruf nicht Teil eines Zusamengesetzten Ausdrucks, der keine Fallunterscheidung ist

Kein rekursiver Aufruf in einem zusammengesetzten Ausdruck (ausgenommen Fallunterscheidungen wie if .. then .. else oder case).

Die Werte die für den nächsten Iterationsschritt benötigt werden, werden als Parameter übergeben und sind kein Rückgabewert (einer rekursiven Funktion).

Verhindert Speicherverschwendung durch unvolendete Rechnungen (Um die berechnung ab zu schließen muss nicht nochmal die rekursive funktion aufgerufen werden).

Beispiel

local
  fun qAux(sum, 0) = sum
    | qAux(sum, n) = qAux(sum + (n mod 10), n div 10)
in
  fun q(n) = qAux(0, n)
end;

Substitutionsmodel: Alles wird ersetzt, Reihenfolge bleibt offen (Nur für Referenzentransparente Sprachen sinvoll).

Terminieren alle Reihenfolgen, kommt das gleiche Ergebnis raus.

The SML way, bis auf sonderausdrücke.

1. Parameter
2. Funktion

• Inside-out
• Call-by-value
• strikt

n = 1

• Parameter werden einmal Ausgewertet
• Nicht benötigte Parameter werden ausgewertet

1. Funktion
2. Parameter

• Outside-in
• Call-by-Name

n >= 0

• Parameter werden ggf. mehrfach Ausgewertet
• Nicht benötigte Parameter werden nicht ausgewertet

1. Funktion
2. Parameter

n ⇐ 1

Parametervorkommen werden, bis auf eins, durch Zeiger, auf das eine, ersetzt. ⇒ Parameter werden maximal einmal Ausgewertet.

if <1> then <2a> else <2b>

case <1> of <a> => <2a>
          | <b> => <2b>
          | <c> => <2c>
          | <d> => <2d>
          | <e> => <2e>

<1> orelse <2>

<1> andalso <2>

• Statische/Lexikalisch Bindung: Wiederdeklaration nur für neue Deklarationen (SML)
• Dynamische Bindung: Wiederdeklaration auch für alte Deklarationen

…. Was hat statische/dynamische bindung mit dem vorhandensein von scopes (und überschatten zu tun? Zu sehen am follgenden beispiel:

val n = 2;
fun foo() = n;
val n = 3;
fun bar(n) = n + foo();
bar(4);

statisch ist eigentlich semi-statisch, da parameter dynamisch bleiben müssen. statisch ohen scope mölich?

• Mit statischer bindung und scopes wäre das ergebniss 2+4=6
• Mit statischer bindung und ohne scopes wäre das ergebniss 2+4=6 ← vermulich SML

• Mit dynamischer bindung und scopes wäre das ergebniss 3+4=7
• Mit dynamischer bindung und ohne scopes wäre das ergebniss 4+4=8

• Blocksprache: Lokale Deklarationen + Statische Bindung
• Blockstruktur
• SML

Bislang verwendete Funktionen

• it ist eine art default Vairable (wörtlich zu nehmen „es“)
• use(„file.sml“)
• (hd = head?; nicht aus VL)
• (tl = tail?; nicht aus VL)

• 'a ist ein Polymorpher typ parameter (d.h. er wird wenn der typ ausgegeben wird werden abhängige type a, b, c, … genannt)
• tl; it myList; funktioniert!
• immer else bie if
• _ default bei prädikaten immer am Ende.
• prädikate müssen alle fälle abdecken
• prädikate müssen gleiche ein und ausgabe typen haben
• val xxx = ( yyy ) Implizite klammerung nach dem ersten “=„ oder dem nach „val“ (prüfen) und besondere bedeutung (zuweisung).
• Kein überlaen möglich (also kein fun a(p1); fun b(p2);
• handle ist infix operator, ist wie andalso, rechts wird nur ausgewertet je nach linkem wert
• ; nicht nötig, wenn danach ein Schlüsselwort (val, fun) kommt.

• Kommentar (* … *)
• Komentar schachtelbar

Baumdurchläufe:

• Infix
  Left Child + Node + Right Child
• Präfix
  Node + Left Child + Right Child
• Postfix
  Left Child + Right Child + Node

Präfix collect bei Blatt mit zwei daten inkonsistent. siehe Folien 7.4, Seite 42

• Überschatten: val a = 1; val a = 2;
• Deklarationen werden in Umgebung gesammelt
  • N: Name
  • W: Wert
  • T: Ab wo gesucht werden soll (pos = 1, 2, …)
    • val: pos - 1
    • fun und val rec: pos
• Lokale Umgebungen
  • Für
    • Aktuelle Parameter
    • let
    • local
  • Wird zwischen T und T + 1 temporär eingefügt.
• val … ; val … ; (lokale) Umgebung wird nacheinander erweitert.
• val .. and … (lokale) Umgebung wird gleichzeitig erweitert. (Es wird gesamelt, nötig für Wechselseitige rekursion).

• Ausdruck
  • Funktionaler Ausdruck
    • Atomar
      • Systemfunktion (+. *, …)
    • Zusamengesetzt
  • Sonderausdruck
    • val, fun
    • if … then … else …, case, …
    • andalso, orelse

• Funktionale „Variable“ (Für funktionale Sprachen)
  • Konstante/Funktion/Systemfunktion/Sonderalgorithmus
  • Ein Wert pro Deklarationsbereich
• Zustandsvarible (Für imperative sprachen)
  • Meistens nur Variable
  • Mehrere Werte pro Deklarationsbereich

(if a > 42 then abs else quadrat)(b)

• Angleichungsregel
  <Muster> => <Ausdruck>
• Angleichungsmodell
  <Angleichungsregel> | <Angleichungsregel> | <Angleichungsregel>
  • Alle Muster vom selben Typ
  • Alle Ausdrücke vom selben Typ
  • <Ausdruck> an <Muster> angleichen erfolgreich ⇒ Variablen von <Muster> and Werte von <Ausdruck> binden

• case <Ausdruck> of <Angleichungsmodell>
  • val (a, b) = (1, 2)
• fn <Angleichungsmodell>
  • fun …

• Warning: match nonexhaustive ⇒ mögliche Laufzeitfehler.
• Wildcards sollten verwendet werden wenn Wert uninteresant
• Angleich an Teilausdrücke (auch mit Wildcards) möglich
• Muster muss linear sein: Keine doppelten Variablen

• Wildcard-Muster _
  • angleich an alle Werte
  • bindet keinen Wert
• Verbund-Wildcard-Muster …
  • val {1=a, 3=b, …} = (11, 22, 33, 44)
  • Die Typen aller Record Elemente (auch derer die unter den Wildcard fallen) müssen zur Übersetzungszeit bekannt sein, sonst Fehler!
• gestuftes Muster / layered pattern L1 as L2
  • D as (N, V)
  • Erst das „grobe“ dann das „feine“

Beweise:

• Per Induktion
• einige fälle sind „offensichtlich“
• Korrektheit
  • Namen in Muster ersetzen durch Ergebniss des Pattern Matching Algorithmuses = Wert
  • order Scheitern ⇒ Es existieren keine Bindungen

• Typ: exn
• Wert: Ausmahmewerte
  • Neue Ausnamekonstruktoren zu existierendem Typ hinzufügen
    exception foo
exception bar of string * int
• Ausnahme werfen
  raise foo
raise bar(„You failed“, 1337)
• Ausnahme behandeln (mit Pattern matching)
  handle <Muster 1> => <Ausdruck 1> | <Muster 2> => <Ausdruck 2>
• Ausnahmen nur wenn sie nicht den Normalfann behanden!

Ausnahmepaket im Substitutionsmodel

((raise foo(42)) + 3) handle foo(x) => "Failed"
($[foo(42)] + 3) handle foo(x) => "Failed"
$[foo(42)] handle foo(x) => "Failed"
"Failed"

• ref ist eine Funktion
  • Nie ohne Initialwert
  • Nur Monotypen, keine Polytypen (FEHLER: ref nil OK: ref (nil : string list))
  • Nicht referenzentransparent (da ref 42 <> ref 42)
• explizite dereferenzierung (keine implizite)
• := ist ein Infix Operator
  • Rückgabewert: ()
  • Typ: 'a ref * 'a -> unit
• Referenzenvergleich gleich wie in C: pointer1 = pointer2 ⇒ !pointer1 = !pointer2

while <Ausdruck : bool> do <Ausdruck>

fun sum(n) =
  let
    val sum = ref 0;
    val cnt = ref n;
  in
    while !cnt <> 0 do (
      sum := !sum + !cnt;
      cnt := !cnt -1   (* Hier KEIN ";" *)
    );
    !sum   (* Hier KEIN ";" *)
  end;