ALP IEinführung in Haskell
Prof. Dr. Margarita Esponda
WS 2012/2013
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Was ist Haskell?
Haskell ist eine rein Funktionale
Programmiersprache mit einer nach Bedarf
Auswertung-Strategie oder "Lazy Evaluation".
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Was bedeutet rein funktional?
- Programme werden als mathematische Funktionen dargestellt
- Haskell Funktionen haben keine Seiteneffekte.
keine Seiteneffekte ⇒ Referenzielle Transparenz
- Eine Funktion liefert immer bei gleicher Eingabe das gleiche Ergebnis.
- Der Wert eines Ausdrucks hängt nur von den Werten der aktuellen Parameter ab.
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Funktionen
e1e2..en
aFEingabewerte nur ein Ausgabewert
Das Ergebnis einer Funktion hängt nur von den Eingabewerten ab.
Prof. Dr. Margarita Esponda
Funktionale Programmierung
f ( x , y ) = x 2 + y 3
Beispiel:
1f ( 1 , 2 ) 2
Funktionen
+12
3
Arithmetische Operationen können auch als Funktionen betrachtet werden
Prof. Dr. Margarita Esponda
Funktionale Programmierung
( + ) ( x , y ) = x + y 3
1 2
Funktionen in Haskell
Einfache Funktionsdefinitionen in Haskell:
f e1 e2 en... = Funktionskörper
quadrat x = x*x
Funktionsname
Eingabeargumente ohne Klammern und Kommas
Ausdruck, dessen Wert dem Ergebnis der Funktion
entspricht
f x = x*x
Allgemeine Syntax:
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Funktionsapplikation
Die Anwendung einer Funktion mit konkreten Argumenten wird als Funktionsapplikation bezeichnet.
⇒ 1*0 + 1*2
⇒ 0 + 2⇒ 2
f x y z = x*y + x*zFunktionsdefinition:
Funktionsapplikation:
Die Variablen auf der rechten Seite der Funktionsdefinition werden durch die entsprechenden konkreten Argumente ersetzt.
Funktionsreduktion
Prof. Dr. Margarita Esponda
Funktionale Programmierung
f 1 0 2
Normalform
Kann ein Ausdruck nicht mehr weiter reduziert werden, dann befindet er sich in seiner Normalform und die Berechnung ist beendet.
Beispiele:
"text"
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Ausdruck Normalform des Ausdruck
3 + 7 10sin 0 0.0
"text"
Zahlen
"1 + 2" "1 + 2"'2' '2'
Zeichenkette
Zeichen
Auswertungsstrategie
✴ Innerhalb eines Ausdrucks kann es mehrere Funktionsapplikationen geben.
✴ Die Reihenfolge, in der unabhängige Teilausdrücke ausgewertet werden, verändert nicht den Wert des gesamtes Ausdrucks.
✴ Aber verschiedene Reihenfolgen können die Anzahl der notwendigen Berechnungen stark beeinflussen.
✴ Eine Auswertungsstrategie kann sogar entscheiden, ob eine Berechnung beendet werden kann oder nicht.
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Bottom (⊥)
✴ Wenn die Auswertung eines Ausdrucks zu einer unendlichen Folge von Reduktionen führt, wird entweder
• das Programm nicht beendet oder
• es stürzt ab, weil der Speicher voll wird.
✴ In der Theorie wird das Symbol Bottom ⊥ verwendet, um
den Wert von Ausdrücken darzustellen, die nicht vollständig ausgewertet werden können (die divergent sind).
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Bottom (⊥)
Bottom kann in Haskell wie folgt ausgedrückt
werden:
bottom = bottom
In dem Prelude-Module ist eine Funktion dafür
definiert:
undefined = error "Prelude; undefined"
Prof. Dr. Margarita Esponda
Funktionale Programmierung
AuswertungsstrategienFunktionsbeispiele: g x = 2 * x
f x = x + x
Auszuwertender Ausdruck: f (g 5)Call-by-value
Ausdrücke werden von innen nach außen und von links nach rechts ausgewertet.
f (g 5) ⇒ f (2 * 5) ⇒ f 10
⇒ 10 + 10 ⇒ 20
Call-by-nameAusdrücke werden von außen nach innen ausgewertet.f (g 5) ⇒ (g 5) + (g 5)
⇒ (2*5) + (g 5) ⇒ 10 + (g 5) ⇒ 10 + (2*5)
⇒ 10 + 10 ⇒ 20
Es wird garantiert, dass die Argumente zuerst ausgewertet werden und dann an die Funktion weitergegeben werden.
Ohne die Argumente auszuwerten, werden zuerst die äusseren Funktionen angewendet.
Prof. Dr. Margarita Esponda
Auswertungsstrategien
Auswertungsstrategie in HaskellCall-by-need oder Lazy-evaluation
Auswertung nach Bedarf
Lazy-evaluation ist eine optimierte Auswertungsvariante von
call-by-name und wird in Haskell und anderen funktionalen
Sprachen verwendet.
Beispiel:
f (g 5) ⇒ (g 5) * (g 5) where g 5 = 2*5
⇒ (g 5) * (g 5) where g 5 = 10 ⇒ 10 * 10
⇒ 100call-by-need ist eine Art call-by-name-Auswertungsstrategie mit Gedächtnis
Prof. Dr. Margarita Esponda
Auswertungsstrategien
g x = 2 * xf x = x * x
Auswertungsstrategie in Haskell
Call-by-need oder Lazy-evaluationAuswertung nach Bedarf
Definitionen:
Prof. Dr. Margarita Esponda
Auswertungsstrategien
f y x = (2 + y) + x * xdouble x = 2 * x
f 6 (double 3) ⇒ (2 + 6) + *
(double 3)
⇒ 8 + *
(double 3)
⇒ 8 + *
(2*3) ⇒ 8 + *
6 ⇒ 8 + 36
⇒ 44
f 6 (double 3)
Anwendung:
Strikte FunktionenInformell kann man sagen, dass eine Funktion f strikt nach einem ihrer Argumente a ist, wenn für die Auswertung der Funktion, die Auswertung von a notwendig ist.
Formale Definition:
f ist strikt ⇔ f ⊥ = ⊥
Beispiel: Die + Funktion ist strikt nach beiden Argumenten
(2*4) + (5*6)
oder
(+) (2*4) (5*6) ⇒ (2*4) + (5*6) ⇒ 8 + 30⇒ 38
Prof. Dr. Margarita Esponda
Auswertungsstrategien
Haskell - Auswertungsstrategieist nicht strikt
✴ Ausdrücke werden nur bei Bedarf ausgewertet ✴ im Gegensatz zu imperative Sprachen, in denen eager-evaluation
verwendet wird.
Beispiel: x = x + 1
g a = a
f a b = b
g 5 ⇒ 5
g x ⇒ g ⊥⇒ ⊥
f 2 3 ⇒ 3
f x 3 ⇒ 3
f 2 x ⇒ f 2 ⊥⇒ ⊥
weil die Auswertung von x nicht terminiert
g ist strikt nach a
f ist strikt nach b, aber nicht nach a
x ⇒ x + 1 ⇒ (x + 1) + 1 ⇒ ((x + 1) + 1) + 1 ⇒ . . .
Prof. Dr. Margarita Esponda
Auswertungsstrategien
Ein Haskell-Programm besteht aus einer Reihe von Funktionen und einem Ausdruck, der ausgewertet werden soll.
Haskell-Programm
rectArea a b = a*b
rectPerimeter a b = 2*(a+b)
Name.hs
✴ Eine Reihe von Funktionsdefinitionen werden in eine Skript-Datei geschrieben
✴ mit der Kommandozeile
:load Name.hs
wird diese vom Haskell-Interpreter gelesen.
✴ Dann können Ausdrücke damit ausgewertet werden.
Prof. Dr. Margarita Esponda
Funktionale Programmierung
(rectArea 4 5) + (rectArea 2 1)
Berechnungsmodel
• Funktionsdefinitionen werden als Ersetzungsregeln interpretiert
• Ausdrücke werden damit zu einem Wert (Normalform) reduziert
• Hat ein Ausdruck keine reduzierbaren Teilausdrücke, so ist er in Normalform
• In Haskell werden Ausdrücke nur nach Bedarf ausgewertet.
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Pseudo-Funktionen mit Seiteneffekte
Prof. Dr. Margarita Esponda
Funktionale Programmierung
e1e2..en
aF
Der Zustand einer globalen Variable wird verändert
Eingabe der Zeit abhängig ist
Eine Funktion, die während Ihrer Berechnung globale Daten in irgend ein Speichermedium manipuliert, verändert damit der Zustand der Ausführung-Umgebung und produziert damit Seiteneffekte.
keine Seiteneffekte ⇒ Referentielle Transparenz
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Vorteile der referentiellen Transparenz
- Die Korrektheit der Programme oder einfache Eigenschaften können mit klassischen mathematischen Verfahren geprüft werden.
- Die Wartung ist einfacher, weil die Auswertung von Teilausdrücken Kontext und Zeit unabhängig sind.
- Wichtige Optimierungen durch den Compiler sind möglich
- Parallele Auswertung von Teilausdrücke
- gleiche Ausdrücke werden nur ein mal ausgewertet
- usw.
Datentypen✴ Ein Datentyp entspricht dem Wertbereich, den die Argumente
oder das Ergebnis einer Funktion haben können.
✴ Jeder Ausdruck in Haskell hat einen wohldefinierten Datentyp.
✴ Funktionen werden oft nur für bestimmte Datentypen definiert.
✴ Der Datentyp von Variablen oder Ausdrücken wird durch explizite Deklaration oder durch Typ-Inferenz festgestellt.
Prof. Dr. Margarita Esponda
Funktionale Programmierung
DatentypenExplizite Deklaration des Datentyps einer Funktion
sum :: Int -> Int -> Int
sum a b = a + b
Syntax:Funktionsname :: Funktionstyp
Typ-SignaturBeispiele:
doppel :: Int -> Int
doppel a = 2*a
pi :: double
pi = 3.141598
Konstante Funktion
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Datentypen
Haskell hat ein statisches Typsystem
Der Datentyp der Funktionen wird statisch während der
Übersetzungszeit des Programms abgeleitet.
Vorteile:
• Datentyp-Fehler werden früher erkannt
• durch die Reduzierung der Typ-Überprüfung reduziert
sich die Ausführungszeit
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Grundlegende Datentypen
Int ganzzahlige Werte (-231 … 231-1)
Integer ganzzahlige Werte (unbeschränkt)
Bool Wahrheitswerte True False
Char Zeichen 'a' '1' '+'
Float Gleitkommazahlen (32 Bits)
Double Gleitkommazahlen (64 Bits)
Typ1 -> Typ2 Funktionen
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Konstanten (Literale)
Konstante Werte, die im Programm direkt geschrieben
werden, besitzen einen Typ, der sich aus der Schreibweise
ergibt.
Ganze Zahlen: 345 0
Gleitpunktzahlen 3.45 0.0
Zeichen
Zeichenketten "Zeichenkette"
'\n''A' 'a' '1' '+'
10
Beispiele: Typ
Integer
Double
Char
[Char]
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Arithmetische OperationenSymbol Operator Priorität
+ Addition 4
- Subtraktion 4
* Multiplikation 3
/ Division 3
`div` Ganzzahlige Division 3
`mod` Rest 3
** Ganzzahlige Potenz 2
^ Potenz 2
Arithmetische Operatoren mit der gleichen Priorität sind linksassoziativ
die niedrigeren Zahlen entsprechen einer höheren Priorität
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Jeder Ausdruck hat einen Wert und einen Datentyp
1 `div` 2 ⇒ 0
Wert Typ
Integer
1/2 ⇒ 0.5 Double
1 `mod` 2 ⇒ 1 Integer
-6 `mod` 4 ⇒ -2 Integer
0.0 ^ 0 ⇒ 1.0 Double
3 / 0 ⇒ Infinity Double
0 / 0 ⇒ NaN
sqrt(-5) ⇒ NaN Double
Double
(3/0)/(2/0) ⇒ NaN Double
Prof. Dr. Margarita Esponda
Funktionale Programmierung
keine Zahl
Kommentare
Blockkommentare
Zeilenkommentare
{- …….Blockkommentare …… …………………………….…. -}
-- Zeilenkommentare
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Vergleichsoperatoren
Kleiner < 5
Größer > 5
Kleiner oder gleich <= 5
Größer oder gleich >= 5
Gleichheit == 6
Ungleichheit /= 6
Priorität
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Fallunterscheidung
if <bool-Ausdruck> then <Ausdruck> else <Ausdruck>
Allgemeine Form:
Beispiel:
sign :: Int -> Intsign x = if x > 0 then 1 else if x < 0 then -1 else 0
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Case-Verteiler
german2italian :: Char -> Stringgerman2italian x = case x of
'c' → "do" 'd' → "re" 'e' → "mi" 'f' → "fa" 'g' → "sol"
'a' → "la" 'h' → "si"
Beispiele: Übersetzung der Tonnamen von Deutsch zu Italienisch
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Logische Operatoren
Logische Negation not 1
UND && 7ODER || 8
Priorität
Beispiele:
True || False ⇒ True
not ( True || undefined ) ⇒ False
not ( True && undefined ) ⇒ *** Exception: Prelude.undefined
True && False ⇒ False
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Logische Operatoren
char2Digit :: Char -> Int
char2Digit x = if (fromEnum x) >= (fromEnum '0') &&
(fromEnum x) <= (fromEnum '9')
then (fromEnum x) - (fromEnum '0')
else error "wrong argument value ..."
Beispiele: Die Funktion fromEnum gibt den ASCII-Code des Zeichens zurück.
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Schlüsselwörter sind reserviert und können nicht als
Funktionsnamen bzw. Namen für Funktionsargumente
verwendet werden.
Gibt es Funktionsnamen, die nicht erlaubt sind?
Beispiel: if where usw.then errorelse notcase undefinedof NaNlet infinity
Lokale Funktionsdefinitionen
f :: Float -> Float -> Float
f x y = (a+1)*(b+2)
where
a = (x+y)/2
b = (x+y)/3
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Guards
sign :: Int -> Intsign x | x < 0 = -1 | x == 0 = 0 | x > 0 = 1
sign :: Int -> Intsign x
| x > 0 = 1 | x == 0 = 0| otherwise = -1
Prof. Dr. Margarita Esponda
Funktionale Programmierung
otherwise :: boolotherwise = True
Guards
<Funktionsname> a1 a2 … an
| <guard1> = <expression1>| <guard2> = <expression2>
...| <guardm> = <expressionm>
Allgemeine Syntax:
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Struktur eines Haskell-Programms
Ein Haskell-Programm besteht aus einem oder
mehreren Modulen.
Ein Modul besteht aus Funktionsdefinitionen
und Typ-Deklarationen.
haelfte:: Int -> Int -- Typ-Deklaration
haelfte x = x `div` 2 -- Funktionsdefinition
Beispiel:
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Programmausführung
Drei Wege bis zur Programmausführung
Die Programme werden direkt in die Maschinensprache des jeweiligen Rechners übersetzt.
Die Programme werden nicht übersetzt, sondern direkt von einem Interpreter-Programm ausgeführt.
Das übersetzte Programm wird dann direkt von der Hardware interpretiert.
Compiler
Interpreter
Compiler + Interpreter (virtuelle Maschine)
Die Programme werden in eine Zwischensprache übersetzt und von einer so genannten virtuellen Maschine (vereinfachter Interpreter) ausgeführt.
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Programmausführung
Programm in einerhöheren
Programmiersprache
Übersetzer
Programm in Maschinensprache
Das Programm kann direkt von der Hardware
ausgeführt werden
0000011101101011
0101010111110101
0000101010111111
1111110101010110
0010101010111110
....
Compiler
Beispiele: C, C++,
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Programmausführung
Der Interpreter
wird direkt von
der Hardware
ausgeführt
Interpreter
Quellprogramm
read (a);read (b);if (a<b) then a = a*a;else a = a+b;print a;
Das Programm wird
hier interpretiert
Programm in einerhöheren
Programmiersprache
Beispiel: Skriptsprachen: JavaScript, JScript, Python, Tcl/Tk, VBA usw.
Interpreter
Prof. Dr. Margarita Esponda
Funktionale Programmierung
Programmausführung
Programm in einerhöheren
Programmiersprache
Der Interpreter
wird direkt von der
Hardware
ausgeführt.
Compiler + Interpreter
read (a);read (b);if (a<b) then a = a*a;else a = a+b;print a;
Der Zwischencode
wird hier
interpretiertBeispiele: Java
Übersetzer
Interpreter Virtuelle Maschine
LOAD #1 C LOAD #2 B MULT #1 #2 #3
LOAD #4 A ADD #3 #4 #1 STORE #1 C LOAD #4 A ADD #3 #4 #1
Programm in einer Zwischensprache
Prof. Dr. Margarita Esponda
Funktionale Programmierung