Muirauqa's Brain

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== ProMo ======
===== SMl NJ =====
Wir arbeiten mit [[http://de.wikipedia.org/wiki/Standard_ML|SML/Standard ML]]. In der New Jersey Implementierung %%[%%[[http://de.wikipedia.org/wiki/SML/NJ|Wiki]]%%]%%, %%[%%[[http://www.smlnj.org/|Projekt Seite]]%%]%%.

==== Install on Arch ====
A new up to date PKGBUILD can be found in a Arch Linux [[https://bbs.archlinux.org/viewtopic.php?pid=1064973#p1064973|Forum post]]. There is also an [[http://aur.archlinux.org/packages.php?ID=328|AUR package]] from 2010.

The installation process for the AUR package is as usual (don't do it as root).
  - Download the tarball (//Not// the PKGBUILD)
  - untar the package
  - ''cd'' into the extracted directory
  - Build the package with ''makepkg''
  - 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.

==== Tutorials and help ====
  * Nice language tutorial auf englischem [[http://en.wikipedia.org/wiki/Standard_ML|SML Wiki Eintag]].
  * [[http://www.cs.cornell.edu/courses/cs312/2003fa/handouts/cheatsheet.pdf|Cheat Sheat]].
  * [[http://www.cs.princeton.edu/courses/archive/fall08/cos441/notes/lect-SMLNJ.pdf|Language overview]] (Print!!!)

===== Identifyer =====
  * 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.
===== Typen =====
  * Typ/Datentyp: Menge von Werten + Operationen auf Weten
    * Vordefinierte Typen
    * Benutzerdefinierte Typen
 


^ Typ ^ Rechnen (''%%'a * 'a -> 'a%%'') ^^^^^^^^ Vergleichen (''%%'a * 'a -> bool%%'') ^^^^^^
^     ''int'' |   ''~''   |    ''+''  |  ''-''  |  ''*''  |  ''div''  |  ''mod''  |         |         |  ''=''        |  ''<>''       |  ''<''  |  ''>''  |  ''%%<=%%''  |  ''>=''  |
^    ''real'' |   ''~''   |    ''+''  |  ''-''  |  ''*''  |           |           |  ''/''  |         |  ''Real.==''  |  ''Real.!=''  |  ''<''  |  ''>''  |  ''%%<=%%''  |  ''>=''  |
^    ''bool'' |  ''not''  |           |         |         |           |           |         |         |  ''=''        |  ''<>''       |         |         |              |          |
^  ''string'' |           |           |         |         |           |           |         |  ''^''  |  ''=''        |  ''<>''       |  ''<''  |  ''>''  |  ''%%<=%%''  |  ''>=''  |

  * ''~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;''

=== int ===
^ Funktionen | ''Int.abs'' | ''Int.min'' | ''Int.max'' | ''Int.sign'' | ''real() : int %%->%% real'' | ''Real.fromInt() : int %%->%% real'' | ''Int.toString()'' |

Führende 0 erlaubt.

=== real ===
^ Wete | ''123.4E~4'' | ''123.4e5''  | ''000123.4e0005'' |  ''nan'' \\ Nicht schreibbar  |  ''inf'' \\ Nicht schriebbar  |

^ Funktionen | ''Real.compare(4.2, 9.9)'' | ''floor()'' | ''ceil()'' | ''trunc()'' | ''round(1.5)'' |

  * ''.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''

=== bool ===
^ Werte | ''true'' | ''false'' |

^ Operationen | ''andalso'' | ''orelse'' |

=== string ===
^ Werte | ''\n'' | ''\t'' | ''\\'' | ''\"'' | ''""'' |

^ Funktionen | ''size()'' | ''String.sub("abc", 2) = #"b"'' |

''"aaa\**<whitespace Zeichen z.B. Zeilenumbruch>**\bbb"'' also z.B. bei der Eingabe:
<code>
- "aaa\

   \bbb";
it = "aaabbb" : string
</code> 


=== char ===
^ Werte | ''#"a"'' |

^ Funktionen | ''chr()'' | ''ord()'' | ''str()'' |

  * ASCII

=== unit ===
''- fun f**()** = 42;'' \\
''val f = fn : **unit** -> int''

''- fun f(x) = **()**;'' \\
''val f = fn : 'a -> **unit**''

=== Vektor/Tupel ===
    * 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 \\ ''()''




=== Verbund/Record ===
    * 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}''.

=== List ===
  * //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];''

^ Wete | ''nil'' |

^ Funktionen | ''tl()'' | ''hd()'' | ''length()'' | ''rev()'' | ''List.last()'' | ''List.nth([...], 42)'' |  ''map fn list'' \\ Keine Klamern!  |  ''foldl fn start list'' \\ Keine Klamern!  |  ''foldr fn start list'' \\ Keine Klamern!  |  ''list @ list'' \\ infix!  |

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

Bei der Funktion ist der erste Parameter //immer// der listen Wert!
  - Wert aus der Liste
  - 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

<code>
- 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
</code>

<code>
- 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
</code>


=== Array ===
^ Vektor ^ Array ^
| Elemente fix | Elemente Veränderbar |

^ Was ^ Wie ^
| Anlegen | ''Array.array(3, 0)'' \\ ''[|0, 0, 0|] : int array'' |
| Auslesen | ''Array.sub(a, 1)'' |
| Ändern | ''Array.update(a, 1, 42)'' \\ ''() : unit'' |
| Länge | ''Array.length(a)'' |
| List -> Array | ''Array.fromList(list)'' |

  * 0 Erster Eintrag
  * //Nicht// referenzentransparent (Da Arrays pointer sind)

=== option ===
<code sml>
- NONE;
NONE : 'a option

- NONE : int option;
NONE : int option

- SOME 4.2;
SOME 4.2 : real option
</code>

=== IO ===
  * //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

^ Was           ^ Output                               ^ Input                                                                                                                  ^
| Typ           | ''.outstream''                       | ''.instream''                                                                                                          |
| Öffnen        | ''.openOut("datei")'' \\ ''.stdOut'' | ''.openIn("datei")'' \\ ''.stdIn''                                                                                     |
| Transferieren | ''.output(stream, "Text") : unit''   | ''.input1(stream) : TextIO.elem option'' \\ ''.input42(stream) : TextIO.vector'' \\ ''.input(stream) : TextIO.vector'' |
| Flush         | ''.flushOut(stream) : unit''         | --                                                                                                                     |
| Schließen     | ''.closeOut(stream) : unit''         | ''.closeIn(stream) : unit''                                                                                            |

===== Typprüfung =====
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

===== Typdefinition =====
==== Type ====
  * 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''
    * //Post//fix!
  * ''(2, 3) : foo''
  * ''(2, 3) : (int * int)''

==== Datatype ====
  * Eigener Typ
    * //Typ//konstante \\ ''datatype **Farbe** = Rot | Blau''
    * //Wert//konstruktoren (Ö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//.
==== Abstype ====
  * 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

<code sml>
(* 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;
</code>

==== Module ====
^                  ^ Struktur     ^ Signatur        ^ Funktor  ^
| SML Analogie     | Wert         | Typ             | Funktion |
| OOP Analogie     | Klasse       | Interface       | Template |
| Beinhaltet       | Definitionen | Spezifikationen | --       |
| Namenskonvention | Name         | NAME            | Name     |

  * Hierarchische Struktur
  * Named scope \\ ''Struktur.deklaration''

=== Structure ===
<code sml>
structure Name =
  
  struct
    <dec>
    <dec>
    ...
  end;
</code>

//Signature-Constraint// mit
  * ''structure Name : NAME =''
  * ''structure Name : sig <spec> <spec> ... end =''

//view// / //sicht//: Unterspezifizierte Signatur

=== Signature ===
<code sml>
signature NAME =
  
  sig
    <spec>
    <spec>
    ...
  end;
</code>

Signatur Spezifikationen:
  * ''val foo : int''
  * ''val foo : int %%->%% int''
  * ''type foo''
  * ''type foo = int''
  * ''eqtype foo''
  * ''datytype foo = value(x) | ...''
  * ''exception foo of int''

^                                       ^^  Implementierbar mit                ^^^
^ :::                                   ^^ ''type'' ^ ''datatype'' ^ ''abstype'' ^
^ Spezifikation ^ ''type bla''           |  X  |  X  |  X  |
^ :::           ^ ''type bla = int''     |  X  |     |     |
^ :::           ^ ''eqtype bla''         |  X  |  X  |     |
^ :::           ^ ''datytype bla = ...'' |     |  X  |     |


=== Funktor ===
^  Structure  ^  Funktor  ^
| ''structure Name ='' \\ | ''functor Name(param : SIGNATURE) ='' |
| ''struct'' \\ ''  <dec>'' \\ ''  <dec>'' \\ ''end'' ||

  * Nur //ein// Parameter
  * Signatur //muss// angegeben werden
  * "parametrisierte Struktur"

Erzeugen einer konkreten Struktur:
  structure NameName = Name(OtherName)


===== Polymorphie =====
  * 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;

^ Polymorphie ^ Überladen ^
| Gleicher name | Gleicher name |
| Gleicher Algorithmus | Verschiedene Algorithmen |
| Flexibler typ | Fester typ |
| Auch "parametrischer Polymorphie" | Auch "ad hoc–Polymorphie" |


Kapitel 5.4 in den Folien Lesen!!!!


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

^ Typkonstruktor                    ^^^ (Wert-)Konstruktor    ^
^ Muster ^ Schreibweise ^ Beispiel ^ :::^
| ''. list''                        | Linksassoziativ  | ''%%(('a list) list)%%''      | ''. :: .''            |
| :::                               | :::              | :::                           | ''nil''               |
| ''. * .''                         | Infix            |                               | ''( . , . )''         |
| ''{ . : . , . : . }''             |                  |                               | ''{ . = . , . = . }'' |
| ''. %%->%% .'' (Rechtsassoziativ) | Rechtsassoziativ | ''%%(int -> (int -> int))%%'' | ''fn . %%=>%% .''     |



===== Strukturelemente =====
==== Funktion / Prozedur ====
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.
  * 

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

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

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

=== Schreibart ===
== Lambda Funktion ==
  * ''val f = fn x => 42''
  * ''**val rec** f = fn x => 42''  nur mit ''fn''

== Normale Funktion ==
  fun f(x) = 42

Hat implizites ''rec''

=== Currying ===
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 ===
  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)
  
=== Komposition ===
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

=== Misc ===
''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
==== Auswahl ====
''else''-Teil muss immer angegeben werden.
<code sml>
val f = fn n => if n = 42 then true else false;
</code>

<code sml>
fun f(n) = if n = 42 then true else false;
</code>

<code sml>
val f = fn 42 => true
         | n  => false;
</code>

<code sml>
fun f(42) = true
  | f(n)  = false;
</code>

==== let / local ====
<code sml>
local
  statement;
  statement;
  ...
  statement
in
  statement
end
</code>

Let ist nötig wenn ein Funktionsparameter aus ''in ...'' in ''let ...'' verwendet werden muss.
<code sml>
let
  statement;
  statement;
  ...
  statement
in
  expression
end
</code>
==== val ... and ... ====
Mit
<code sml>
val x = 2;
</code>

<code sml>
let
  val x = 2*x
  val x = 3*x
in
  x
end;
</code>
Ergibt **12**, da jedes ''val'' alles //einzeln// Auswertet und Zuweist (mit dem ''x'' der jeweils vorherigen Deklaration).

<code sml>
let
  val x = 2*x and y = 3*x
in
  x+y
end;
</code>
Ergibt **10**, da ''val ... and ...'' alles //auf einmal// Auswertet und dann Zuweist (erst alles auswerten, dann alles auf einmal zuweisen).

<code sml>
let
  val x = 2*x and x = 3*x
in
  x
end;
</code>
stdIn:2.5-2.28 Error: duplicate variable in pattern(s): x

===== Rekursion =====
==== Wechselseitige rekursion ====
''val ... and ...'' muss sein.
<code sml>
val rec a = fn 0 => false
             | n => b(n-1)
and
        b = fn 0 => true
             | n => a(n-1);
</code>

<code sml>
fun a(0) = false
  | a(n) = b(n-1)
and
     b(0) = true
   | b(n) = a(n-1);
</code>

==== Endrekursive Funktion ====
  * //Nicht// Speicheraufwendiger
  * //Nicht// Zeitaufwendiger
  * Weniger Speicher nötig
  * Aufruf nicht Teil eines Zusamengesetzten Ausdrucks, der keine Fallunterscheidung ist
==== Endrekursive Funktion ====
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
<code sml>
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;
</code>

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

Terminieren alle Reihenfolgen, kommt das gleiche Ergebnis raus.

==== Applikative Reihenfolge ====
The SML way, bis auf sonderausdrücke.
=== Reihenfolge ===
  - Parameter
  - Funktion

=== Alternativnamen ===
  * Inside-out
  * Call-by-value
  * strikt

=== Parameterauswertung ===
n = 1
  * Parameter werden einmal Ausgewertet
  * Nicht benötigte Parameter werden ausgewertet

==== Normale Reihenfolge ====
=== Reihenfolge ===
  - Funktion
  - Parameter

=== Alternativnamen ===
  * Outside-in
  * Call-by-Name
  
=== Parameterauswertung ===
n >= 0
  * Parameter werden ggf. mehrfach Ausgewertet
  * Nicht benötigte Parameter werden nicht ausgewertet

==== Verzögerte Auswertung ====
=== Reihenfolge ===
  - Funktion
  - Parameter

=== Parameterauswertung ===
n <= 1

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

==== Sonderausdrücke ====
  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>

===== Bindung =====
  * 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

===== Misc =====
==== Funktionen ====
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)


==== Mein Spickzettel ====
  * ''%%'%%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:
  * **//In//fix** \\ __Left Child__ + Node + __Right Child__
  * **//Prä//fix** \\ Node + __Left Child + Right Child__
  * **//Post//fix** \\ __Left Child + Right Child__ + Node

Präfix collect bei Blatt mit zwei daten inkonsistent. siehe Folien 7.4, Seite 42
==== Umgebung ====
  * Ü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 ====
  * Ausdruck
      * Funktionaler Ausdruck
        * Atomar
          * Systemfunktion (+. *, ...)
        * Zusamengesetzt
      * Sonderausdruck
        * ''val'', ''fun''
        * ''if ... then ... else ...'', ''case'', ...
        * ''andalso'', ''orelse''
  
==== Variablen ====
  * 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)''


  
==== Pattern Matching ====
  * Angleichungs//regel// \\ ''<Muster> %%=>%% <Ausdruck>''
  * Angleichungs//modell// \\ ''<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 //Laufzeit//fehler.
  * 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

==== Exceptions ====
  * 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"
  
==== Referenzen ====
^ Was ^ Wie ^
| Erstellen | ''val foo = ref 42'' |
| Dereferenzieren | ''!foo'' |
| Neu zuweisen | ''foo := 21'' |

  * ''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''
  * 

==== Schleifen ====
  while <Ausdruck : bool> do <Ausdruck>
  
<code sml>
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;
</code>
users/skruppy/ext/uni/2/promo.txt · Zuletzt geändert: 2012/09/03 02:42 von 88.65.203.151