Embed Size (px)
Citation preview
Funktionale Programmierung
Frank Huch
Sommersemester 2008
Dieses Skript entsteht auf der Basis eines Skript, welches von MihhailAizatul in und Klaas Ole Kürtz (www.kuertz.name) im Sommersemes-ter 2005 zu der ersten Version dieser Vorlesung erstel lt wurde.
Inhaltsverzeichnis0 Einführung 1
1 Einführung in Haskell 31.1 Funktions- und Typdefinit ionen . . . . . . . . . . . . . . 3
1.1.1 Funktionsdef init ionen . . . . . . . . . . . . . . . . . 31.1.2 Basisdatentypen . . . . . . . . . . . . . . . . . . . . 61.1.3 Typannotationen . . . . . . . . . . . . . . . . . . . 71.1.4 Algebraische Datentypen . . . . . . . . . . . . . . . 7
1.2 Polymorphismus . . . . . . . . . . . . . . . . . . . . . . . 91.3 Pattern-Matching . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.1 Case-Ausdrücke . . . . . . . . . . . . . . . . . . . . 141.3.2 Guards . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Funktionen höherer Ordnung . . . . . . . . . . . . . . . . 151.4.1 Anonyme Funktionen (Lambda-Abstraktion) . . . 161.4.2 Generische Programmierung . . . . . . . . . . . . . 171.4.3 Kontrol lstrukturen (Programmschemata) . . . . . 201.4.4 Funktionen als Datenstrukturen . . . . . . . . . . . 211.4.5 Wichtige Funktionen höherer Ordnung . . . . . . . 22
1.5 Typklassen und Überladung . . . . . . . . . . . . . . . . . 231.5.1 Die Klasse Read . . . . . . . . . . . . . . . . . . . . . 25
1.6 Lazy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 261.7 Simulation in Stirkten Sprachen . . . . . . . . . . . . . . 29
2 Monaden 312.1 Die IO-Monade . . . . . . . . . . . . . . . . . . . . . . . . 322.2 List Comprehensions . . . . . . . . . . . . . . . . . . . . . 36
3 Theoretische Grundlagen: Der Lambda-Kalkül 383.1 Syntax des Lambda-Kalküls . . . . . . . . . . . . . . . . . 393.2 Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . 393.3 Reduktionsregeln . . . . . . . . . . . . . . . . . . . . . . . 403.4 Datenobjekte im reinen Lambda-Kalkül . . . . . . . . . . 433.5 Mächtigkeit des Kalküls . . . . . . . . . . . . . . . . . . . 443.6 Angereicherter Lambda-Kalkül . . . . . . . . . . . . . . . 44
4 Monaden 464.1 Die Maybe-Monade . . . . . . . . . . . . . . . . . . . . . . 474.2 Die Listenmonade . . . . . . . . . . . . . . . . . . . . . . . 484.3 Implementierung der IO-Monade . . . . . . . . . . . . . . 50
i
4.4 Erweiterung der IO-Monade um Zustände . . . . . . . . . 524.5 Zustandsmonaden . . . . . . . . . . . . . . . . . . . . . . . 53
5 Debugging 555.1 Debuggen mit Observations (Hood) . . . . . . . . . . . . 565.2 Implementierung von Observations für Daten . . . . . . 575.3 Observieren von Funktionen . . . . . . . . . . . . . . . . 615.4 Andere Ansätze . . . . . . . . . . . . . . . . . . . . . . . . 63
6 Parserkombinatoren 666.1 Kombinatorbibl iothek für Parser . . . . . . . . . . . . . . 666.2 Monadische Parserkombinatoren . . . . . . . . . . . . . . 706.3 Anmerkung zum Parsen . . . . . . . . . . . . . . . . . . . 72
7 Rekursion 747.1 Attributierte Grammatiken . . . . . . . . . . . . . . . . . 747.2 Continuation Passing Style . . . . . . . . . . . . . . . . . 82
8 Algorithmen und Datenstrukturen 858.1 Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858.2 Stacks (LIFO) . . . . . . . . . . . . . . . . . . . . . . . . . 878.3 Queues (FIFO) . . . . . . . . . . . . . . . . . . . . . . . . 888.4 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898.5 Braunbäume . . . . . . . . . . . . . . . . . . . . . . . . . . 898.6 Höhenbalancierte Suchbäume . . . . . . . . . . . . . . . . 918.7 Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
8.7.1 Nested Datatypes . . . . . . . . . . . . . . . . . . . 97
9 Graphen 99
i i
0 EinführungVorteile von funktionalen Sprachen sind:
• hohes Abstraktionsniveau, keine Manipulation von Speicherzel-len
• keine Seiteneffekte, dies führt zu höherer Verständlichkeit undbesseren Möglichkeiten zur Code-Optimierung
• Programmierung über Eigenschaften, nicht über den zeit l ichenAblauf
• implizite Speicherverwaltung (u.a. Garbage Collection)
• einfachere Korrektheitsbeweise
• kompakterer Source-Code (kürzere Entwicklungszeiten, lesbare-re Programme, bessere Wartbarkeit)
• modularer Programmaufbau, Polymorphismus, Funktionen hö-herer Ordnung, damit auch eine hohe Wiederverwertbarkeit desCodes
Strukturen in Funktionalen Programmen sind
• Variablen entsprechen unbekannten Werten (nicht Speicherzel-len!)
• Programme entsprechen Mengen von Funktions- und Typdefini-t ionen
• Speicher ist nicht explizit verwendbar, sondern wird automatischal loziert und freigegeben (Garbage Collection)
• Programmablauf entspricht einer Reduktion von Ausdrücken(nicht einer Sequenz von Anweisungen)
Historie der funktionalen Sprachen:
• Grundlage ist die mathematische Theorie des λ-Kalküls (Church1941)
• LISP (McCarthy 1960): Datenstruktur ist vor al lem Listen, Ver-wendung heute in der KI und in Emacs
1
• Scheme: LISP-Dialekt mit statischer Bindung
• SASL (Turner 1979): Lesbares LISP für die Lehrer
• ML (Milner 1978): polymorphes Typsystem
• KRC (Turner 1980): Guards, Pattern-Matching, Laziness
• Miranda (Turner 1985): Erweiterung von KRC um ein polymorphesTypsystem, Modulkonzept, aber: geschützte Sprache, damit ge-ringe Verbreitung
• Haskell: Entwicklung als public-domain-Variante von Miranda, Fest-setzung als Standard Haskell 98, seitdem jedoch viele Weiterent-wicklungen (Typsystem, Nebenläufigkeit , vertei lte Programmie-rung, explizite Speichermanipulation, ForeignFunction-Interace
• StandardML (1997): Standardisierung, seitdem aber auch vieleWeiterentwicklungen
• Erlang: entwickelt von der Firma Ericsson zur Implementierungvon Telekommunikationsanwendungen; Aufbau auf PROLOG, spe-ziel les Konzept zur nebenläufigen bzw. vertei lten Programmie-rung
In der Vorlesung wird zunächst Haskell 98 behandelt .
2
1 Einführung in Haskell
1.1 Funktions- und Typdefinitionen• In der Mathematik stehen Variablen für unbekannte Werte, bei-
spielsweise ist x2 − 4x + 4 = 0 eine Aussage, aus der sich x = 2ableiten lässt. Aber in imperativen Programmiersprachen stehenAnweisungen wie x = x + 1, was im Widerspruch zur mathema-tischen Notation steht! Idee der funktionalen Programmierung:Variablen werden wie in der Mathematik verwendet!
• In der Mathematik verwendet man Funktionen für Berechnungen,in der imperativen Welt werden diese jedoch (mit einer ande-ren Bedeutung: Seiteneffekte!) zur Modularis ierung eingesetzt(Prozeduren, Methoden), Lösung aus der funktionalen Welt: Pro-grammierung ohne Seiteneffekte!
1.1.1 Funktionsdefinitionen
Ein Programm besteht aus Funtionsdef init ionen, welche wie folgtaufgebaut sind:
f x1 . . . xn = e
Dabei ist f der Funktionsname, die xi sind formale Parameter (zu-nächst nur Variablen) und e ist der Funktionsrumpf, ein Ausdruck.Funktionsbezeichner und Variablen beginnen mit einem Kleinbuch-staben, gefolgt von Buchstaben und Zahlen. Ausdrücke sind wie folgtaufgebaut:
• Zahlen (3, 3.1415. . .)
• Basisoperationen (3+4, 6*7)
• formale Parameter (Variablen)
• Funktionsanwendung ((f e1 ... en)) mit einer Funktion f undAusdrücken ei. In vielen Fällen kann die Klammerung weggelas-sen werden. Z.B. beim äußersten Ausdruck oder in Kombinationmit Basisoperationen.
• bedingte Ausdrücke (if b then e1 else e2) , wobei b ein Ausdruckvom booleschen Typ ist und e1 und e2 ausdrücke des gleichenTyps sind (z.B. beide Zahlen l iefern). Die genaue Bedeutung vonTypen wird später in diesem Kapitel erklärt.
3
Beispiele für Funktionen:
• Quadratfunktion:
square x = x ∗ x
• Minimum:
min x y = i f x <= y then x else y
• Fakultätsfunktion: Mathematisch ist die Funktion definiert als :
n! =
{1 , falls n = 0
n · (n− 1)! , sonst
In Haskell:
f a c n = i f n == 0 then 1 else n ∗ f a c (n−1)
Betrachte zur Auswertung die Funktionsdef init ion als orientierteGleichung (Reduktionssemantik): Binde die formalen Parameter andie aktuel len Parameter und ersetze den Funktionsaufruf durch dierechte Seite. Beispiel für die Auswertung von square (3 + 1):
square (3 + 1)
square 4
(3 + 1) * (3 + 1)4 * 4 16(3 + 1) * 4
4 * (3 + 1)
Weiteres Beispiel : Fibonacci-Funktion
f i b 1 n = i f n == 0then 0else i f n == 1
then 1else f i b 1 (n − 1 ) + f i b 1 (n − 2 )
Dies entspricht der mathematischen Definit ion, ist aber sehr inef-f iz ient (O(2n)) . Verbesserung: Berechnung der Fibonacci-Folge „vonunten“, bis der n-te Wert berechnet ist -- diese Programmiertech-nik heißt Akkumulatortechnik : Zur Berechnung von fib n werden dieErgebnisse von fib(n - 1) und fib(n - 2) benötigt, behalte diese alsAkkumulator-Parameter.
4
f i b 2 ’ f i b n f i bnp1 n =i f n == 0 then f i b n
else f i b 2 ’ f i bnp1( f i b n + f ibnp1 )(n − 1 )
f i b 2 n = f i b 2 ’ 0 1 n
Aus softwaretechnischer Sicht ist dies unschön: fib2’ kann auch(falsch) verwendet werden, besser ist eine lokale Definition:
f i b 2 n = f i b 2 ’ 0 1 nwhere f i b 2 ’ f i b n f i bnp1 n = . . .
Hierbei ist where immer gültig für die letzte Gleichung! Weitere Mög-l ichkeit :
f i b 2 n = l et f i b 2 ’ f i b n f i bnp1 n = . . .in f i b 2 ’ 0 1 n
Das Konstrukt let ... in ist auch in bel iebigen Ausdrücken möglich,z.B:
( l et x = 3y = 1
in x + y) + 2
Zur Vermeidung von Klammern und Trennzeichen wird die Off-Side-Rule benutzt: Das nächste Symbol, das kein Whitespace ist hinterwhere und let, def iniert einen Block:
f x = ewhere g y = {Rumpf von g}
{Rumpf von g geht we i t e r }{Rumpf von g geht we i t e r }
h z = {Rumpf von h}{Rumpf von h geht we i t e r }{Rumpf von h geht we i t e r }
k x y = . . .
Sobald ein Zeichen auf der gleichen Höhe wie g erscheint, wird es alsAnfang einer neuen Definit ion in where betrachtet, hier also h. Daserste Zeichen links von g ( in diesem Fall k) wird dem übergeordne-ten Block, hier der Top-Level-Deklaration zugeordnet. Aber auchgeschachtelte let- und where-Deklarationen sind möglich.
5
In verschiedenen Blöcken im obigen Beispiel s ind folgende Variablenund Funktionen sichtbar:
• Im Rumpf von g: Variablen x, y, Funktionen f, g, h, k
• Im Rumpf von h: Variablen x, z, Funktionen f, g, h, k
• Im Rumpf von k: Variablen x, y, Funktionen f, k
Vorteile von lokalen Deklarationen sind:
• Vermeidung von Namenskonfl ikten und falscher Verwendungvon Hilfsfunktionen
• bessere Lesbarkeit wegen des kleineren Interfaces
• Vermeidung von Mehrfachberechnung, betrachte beispielsweisedie Funktion f(x, y) = y(1 − y) + (1 + xy)(1 − y) + xy , diese kannumgesetzt werden als
f x y = l et a = 1 − yb = x ∗ y
in y ∗ a + (1 + b)∗a + b
• Einsparung von Parametern der Hil fsfunktion, beispielsweisebeim Test auf Primzahleigenschaft
i sPr ime n = n /= 1 &&checkDiv (div n 2 )
where checkDiv m =m == 1 | | mod n m /= 0
&& checkDiv (m − 1 )−− && bindet stärker a l s | |
Der Operator && ist ein nicht striktes „und“ , z .B. gi lt False &&⊥=False (wobei ⊥ eine nicht-terminierende Berechnung bezeichnet).Genauso ist || ein nicht striktes „oder“ . Die Funktion div ist dieganzzahlige Divis ion. Kommentare fangen mit -- an.
1.1.2 Basisdatentypen
Bereits verwendet:
• Ganze Zahlen:
6
– Int, Werte von −216 + 1 bis 216 − 1
– Integer, bel iebig klein/groß (nur durch Speicher beschränkt)
Operationen: +, -, *, div, mod; Vergleiche: <=, >=, <, >, /=,==.
• Boolesche Werte: Bool; Werte: True, False; Operationen: &&, ||,==, /=, not
• Fließkommazahlen: Float, geschrieben 0.3, -1.5e-2; Operationenwie auf Int/Integer, mit / statt div und ohne mod
• Zeichen (ASCII): Char, Werte: ’a’, ’\n’, ’\NUL’, ’\214’. Opera-tionen: chr, ord
1.1.3 Typannotationen
Alle Werte bzw. Ausdrücke in Haskell haben einen Typ, welcher auchmittels :: annotiert werden kann:
3 : : Int3 : : Integer( 3 == 4) | | True : : Boolsquare : : Int −> Intsquare x = (x : : Int ) ∗ ( x : : Int ) : : Int
Aber: was ist der Typ von min? In ML (Java) wäre der Typ min ::(Int, Int)-> Int, die Schreibweise in Haskell ist jedoch curryfiziert :
min :: Int -> Int -> Int.
1.1.4 Algebraische Datentypen
Eigene Datentypen können als neue Datentypen definiert werden. Wer-te werden mittels Konstruktoren (frei interpretierte Funktionen) aufge-baut. Die Definit ion sieht al lgemein wie folgt aus:
data τ = c1 τ11 . . . τ1n1 | . . . | ck τk1 . . . τknk
wobei
• τ der neu definierte Typ ist,
• c1, . . . , ck definierte Konstruktoren sind
• τi1 bis τinidie Argumenttypen des Kontruktors ci sind, also ci::
τi1 →. . .→τini→ τ .
7
Beachte: Sowohl Typen, als auch Konstruktoren müssen mit Groß-buchstaben beginnen.Beispiele:
• Aufzahlungstyp (nur 0-stel l ige Konstruktoren)
data Color = Red | Blue | Yel lowRed : : Color
• Verbundtyp (nur ein Konstruktor)
data Complex = Complex Float FloatComplex 3 . 0 4 . 7 : : Complex
Namen für Typen und Konstruktoren sind in getrennten Namens-räumen, deshalb gleiche Namen erlaubt.
Wie ist die Selektion von Komponenten möglich? In Haskell: Pattern-Matching statt expliziter Selektionsfunktionen.
Beispiel:
addC : : Complex −> Complex −> ComplexaddC (Complex r 1 i 1 )
(Complex r 2 i 2 ) =(Complex ( r 1 + r2 ) ( i 1 + i 2 ) )
• Listen kann man wie folgt def inieren:
data List = Ni l | Cons Int List
append : : List −> List −> Listappend N i l ys = ysappend (Cons x xs ) ys = Cons x (append xs ys )
Nil stel lt die leere Liste dar, Cons erzeugt eine neue Liste durchHnzufürgen eines neues Elements an den Anfang einer Liste. DieFunktion append, zum Zusammenfügen zweier Listen, kann mitHil fe mehrerer Gleichungen definiert werden, wobei die erstepassende gewählt wird.
In Haskell sind Listen vordef iniert:
data [ Int ] = [ ] | Int : [ Int ] −− Pseudocode
8
Der Operator : ist rechts-assoziativ, also 1:(2:(3:[]))= 1:2:3:[].Abkürzende Schreibweise: Aufzählung der Elemente, z.B. [1, 2,3]. Außerdem: Operator ++ statt append:
[ ] ++ ys = ys(x : xs ) ++ ys = x : ( xs ++ ys )
Bemerkung: Operatoren sind zweistel l ige Funktionen, die in-f ix geschrieben werden und mit einem Sonderzeichen beginnen.Durch Klammerung werden sie zu normalen Funktionen, z.B. [1]++ [2] ist äquivalent zu (++) [1] [2]. Umgekehrt können zwei-stel l ige Funktionen in ‘...‘ inf ix verwendet werden: div 4 2 istdas Gleiche wie 4 ‘div‘ 2.
Beispiel: Berechnung der Länge einer Liste:
length [ ] = 0length ( x : xs ) = 1 + length xs
Bemerkung: Für selbstdef inierte Datentypen besteht nicht au-tomatisch die Möglichkeit , diese vergleichen bzw. ausgeben zukönnen. Hierzu:
data MyType = . . .deriving (Eq, Show)
Eq stel lt == und /= für den Typ zur Verfügung, Show bietet dieMöglichkeit zur Ausgabe.
1.2 PolymorphismusBetrachtet man die Definit ionen von length und (++), so fäl lt auf,dass beide zwar auf Listen arbeiten, aber der Typ der Listenelementenicht relevant ist . Möglich wäre sowohl
length : : [ Int ] −> Int
als auch
length : : [ [ Int ] ] −> Int
Allgemein könnte man sagen:
length : : ∀ Typen τ . [ τ ] −> Int
was in Haskell durch Typvariablen ausgedrückt wird:
9
length : : [ a ] −> Int
was für al le Typen a bedeutet. Der Name einer Typvariablen mussmit einem kleinen Buchstaben anfangen. Der Typ von (++) ist somit
(++) : : [ a ] −> [ a ] −> [ a ]
Es können nur Listen über gleichen Elementtypen zusammengehängtwerden.Für Definitionen von polymorphen Datenstrukturen verwendet manTypkonstruktoren zum Aufbauen von Typen:
data K a1 . . . an = c1 τ11 . . . τ1n1 | . . . | ck τk1 . . . τknk
Dies ist ein Datentypkonstruktor wie zuvor ein Typ, mit
• K ein Typkonstruktor
• a1, . . . , an Typvariablen
• τik Typen, auch polymorphe über den Typvariablen a1, . . . , an
Funktionen und Konstruktoren werden auf Werte (Ausdrücke) ange-wendet. Analog werden Typkonstruktoren auf Typen bzw. Typvaria-blen angewendet.Beispiel: Partiel le Werte
data Maybe a = Nothing | Just a
Dann lassen sich z.B. folgende Typen benutzen:
Maybe IntMaybe (Maybe Int )
Zugehörige Werte sind Nothing, Just 42 bzw. Just Nothing oder Just (Just 42). Bei der Applikation von Typkonstruktoren auf Typvariablenerhalten wir polymorphe Typen :
isNothing : : Maybe a −> BoolisNothing Nothing = TrueisNothing (Just _) = False
Das Pattern _ steht für einen bel iebigen Wert.Beispiele:
• Binärbäume
10
data Tree a = Node (Tree a ) a (Tree a ) | Empty
he i gh t : : Tree a −> Inthe i gh t Empty = 0he i gh t (Node t l _ t r ) = 1 + (max ( h e i gh t t l )
( h e i gh t t r ) )
• In Haskell vordefiniert: Listen.
data [ a ] = [ ] | a : [ a ] −− Pseudocode
Dies ist Pseudocode, eine eigene Definit ion ist so nicht erlaubt.Die erste und die dritte Verwendung von [] sind Typkonstruk-toren, die zweite dagegen ein Listenkonstruktor. Damit sind[Int], [Char], [[Int]] Applikationen des Typkonstruktors []auf Typen und [a] der polymorphe Typ, der alle Listentypenrepräsentiert.
Einige Funktionen auf Listen:
head : : [ a ] −> ahead ( x :_) = x
t a i l : : [ a ] −> [ a ]t a i l (_: xs ) = xs
last : : [ a ] −> alast [ x ] = xlast (_: xs ) = last xs
concat : : [ [ a ] ] −> [ a ]concat [ ] = [ ]concat ( l : l s ) = l ++ concat l s
( ! ! ) : : [ a ] −> Int −> a(x : xs ) ! ! n = i f n == 0
then xelse xs ! ! (n − 1 )
• Strings sind in Haskell als Typsynonym für Listen von Zeichendefiniert:
11
type String = [Char ]
Schreibweise: "Hallo"= ’H’:’a’:’l’:’l’:’o’:[]. Vortei l gegenüberspeziel len vordef inierten Typ: al le Listenfunktionen für Stringauch verwendbar, z.B. length ("Hallo"++ "Leute").
• Vereinigung zweier Typen:
data Either a b = Left a | Right b
Damit können z.B. Werte „unterschiedl icher“ Typen in einerListe zusammengefasst werden:
[ Left 42 , Right "Hallo" ] : : [Either Int String ]
• Tupel (mit Mixfixnotation):
data ( , ) a b = ( , ) a b −− oder (a , b)data ( , , ) a b c = ( , , ) a b c−− usw
Das linke Vorkommen von (,) ist ein Typkonstruktor; (,) rechtsist ein Wertkonstruktor. Einige Funktionen:
f s t : : ( a , b ) −> af s t ( x ,_) = x
snd : : ( a , b ) −> bsnd (_, y ) = y
zip : : [ a ] −> [ b ] −> [ ( a , b ) ]zip [ ] _ = [ ]zip _ [ ] = [ ]zip ( x : xs ) ( y : y s ) = (x , y ) : zip xs ys
unzip : : [ ( a , b ) ] −> ( [ a ] , [ b ] )unzip [ ] = ( [ ] , [ ] )unzip ( ( x , y ) : xys ) = l et ( xs , y s ) = unzip xys
in ( x : xs , y : y s )
Bemerkung: Es gilt nicht immer unzip (zip l1 l2)= (l1, l2).
12
1.3 Pattern-MatchingPattern-Matching ist ein komfortabler Programmiersti l , alternativzur Verwendung von Selektoren. Dabei entspricht die l inke Seiteeiner Funktionsdef init ion einem „Prototyp“ des Funktionsaufrufs.Die Funktionen werden durch mehrere Gleichungen definiert:
f pat11 . . . pat1n = e1. . .
f patk1 . . . patkn = ek
Semantik: Wähle die erste Regel mit passender l inken Seite und wendediese an. Dabei sol lte man überlappende Regeln vermeiden!
Aufbau der Pattern:
• x (Variable): passt immer, x wird an aktuel len Ausdruck gebun-den
• _ (Wildcard): passt immer, keine Bindung
• c pat1 . . .patk mit c k-stel l iger Konstruktor und pat1, . . . ,patk Pat-tern: passt, fal ls aktuel ler Wert (c e1 . . . ek) ist und pat1 auf al leei passt. Zahlen und Zeichen (Char) können als 0-stel l ige Kon-struktoren verwendet werden; (:) kann auch infix angegebenwerden, Tupel auch mixfix.
• x@pat („as pattern“): Passt, fal ls pat passt, zusätzl ich Bindungvon x an aktuel len Ausdruck. Benutzer zum einen zum Benen-nen gröberer Strukturen, zum anderen zur Verfeinerung vonVariablen.
• n + k: Passt auf al le Zahlen größer gleich k , wobei n an aktuel lenWert minus k gebunden wird.
Beispiel:
f a c 0 = 1f a c m@(n + 1) = m ∗ f a c n
Nicht erlaubt ist mehrfaches Auftreten einer Variable in einem Pat-tern, mehrere Wildcards können jedoch auftreten:
eq : : a −> a −> Booleq x x = True −− verboteneq _ _ = False −− er laubt
13
Pattern können auch an anderen Stel len verwendet werden, und zwarals Konstantendefinit ionen, z.B. in der Definit ion von unzip:
unzip : : [ ( a , b ) ] −> ( [ a ] , [ b ] )unzip ( ( x , y ) : xys ) =
l et ( xs , y s ) = unzip xysin ( x : xs , y : y s )
Hier wird im let Pattern-Matching benutzt. Genauso ist Pattern-Matching im where möglich oder auch auf Toplevel :
(dimX, dimY) = ev a l F i e l d S i z e t e s t F i e l d−− wird nur einmal berechnet
1.3.1 Case-Ausdrücke
Manchmal ist Pattern-Matching mit Verzweigung auch in Ausdrückenpraktisch -- die Definit ion einer Hil fsfunktionen zum Verzweigen wäreumständlich. Dann werden case-Ausdrücke verwendet:
case e ofpat1 −> e1. . .
patn −> en
Beachte dabei die Einrückungen gemäß Offside-Rule! Obiges def inierteinen Ausdruck mit dem Typ von e1 (der gleich dem Typ von e2, . . . , ensein muß). Außerdem muss der Typ von e, pat1, patn ebenfal ls gleichsein.
Beispiel: Extraktion der Zei len eines Strings:
l ines : : String −> [ String ] −− vo rde f i n i e r tl ines "" = [ ]l ines ( ’ \ n ’ : c s ) = "" : l ines c sl ines ( c : c s ) = case l ines c s of
( s t r : s t r s ) −> ( c : s t r ) : s t r s[ ] −> [ [ c ] ]
1.3.2 Guards
Programmieren mit mehreren Regeln ist oft schöner als mit Bedin-gungen im Ausdruck. Guards erlauben es, bel iebige Bedingungen aufdie l inke Seite zu schieben.
14
Beispiel:
f a c n | n == 0 = 1| otherwise = n ∗ f a c (n − 1 )
Semantik: Guards werden der Reihe nach ausgewertet. Die rechteSeite des ersten erfül lten Guards wird gewählt, dabei ist otherwise= True vordefiniert. Fal ls kein Guard erfül lt ist , wird die nächsteRegel gewählt.
Beispiel: die ersten n Elemente einer Liste:
take : : Int −> [ a ] −> [ a ]take n _ | n <= 0 = [ ] −− tota le Funktiontake _ [ ] = [ ]take (n + 1) (x : xs ) = x : take n xs
Guards sind bei jedem Pattern Matching erlaubt, also auch bei case- ,let- und where-Ausdrücken.
1.4 Funktionen höherer OrdnungIdee: Funktionen sind in funktionalen Programmiersprachen „Bürgererster Klasse“ , d.h. können wie al le anderen Werte überal l verwendetwerden. Anwendungen sind unter anderem generische Programmie-rung und Programmschemata (Kontrol lstrukturen).
Vorteile: Höhere Wiederverwendbarkeit und große Modularität.
Beispiel: Die Ableitung ist eine Funktion, die eine Funktion nimmtund eine Funktion berechnet:
ab l e i t ung : : (Float −> Float ) −> (Float −> Float )
Numerische Berechnung:
f ′(x) = limdx→0
f(x+ dx)− f(x)
dx
Implementierung: Wähle kleines dx
dx = 0 .0001ab l e i t ung f = f ’
where f ’ x = ( f ( x + dx) − f x ) / dx
( ab l e i t ung sin ) 0 . 0 1 . 0( ab l e i t ung square ) 1 . 0 2 .0003
15
1.4.1 Anonyme Funktionen (Lambda-Abstraktion)
„Kleine“ Funktionen müssen nicht global def iniert werden. Stattdes-sen kann man schreiben
ab l e i t ung (\x −> x ∗ x )
Allgemein:
\pat1 . . . patn −> e
wobei pat1, . . . ,patn Pattern und e ein Ausdruck sind. Nun können wirschreiben:
ab l e i t ung f = \x −> ( f ( x + dx) − f x ) / dx
Die Funktion ableitung ist nicht die erste Funktion, die ein funktio-nales Ergebnis hat. Betrachte z.B. die folgende Funktion:
add : : Int −> Int −> Intadd x y = x + y
Eine andere mögliche Definit ion:
add = \x y −> x + y
Also kann add auch als Konstante mit funktionalem Wert gesehenwerden! Noch eine weitere Definit ion:
add x = \y −> x + y
Nun ist add eine einstel l ige Funktion mit funktionalem Ergebnis.
Mit der dritten Definit ion von add sol lte auch ableitung (add 2),\x-> 1.0 möglich sein. Dies ist bei al len Implementierungen von Haskellmöglich.
Bei der ersten Implementierung bezeichnet man add 2 als partielleApplikation (man übergibt bei der Applikation weniger Argumente, alsdie Stel l igkeit der Funktion es fordert). Ferner sol lte gelten: add x y,(add x)y. In Haskell sind beide Ausdrücke sogar semantisch gleich:Die Funktionsapplikation ist linksassoziativ.
Entsprechend verhalten sich auch die Typen:
a→ b→ c == a→ (b→ c)
Der Typkonstruktor → ist also rechtsassoziativ. Beachte:
a→ b→ c 6= (a→ b)→ c
16
Die partiel le Applikation ist möglich wegen der curryfizierten1 Schreib-weise. Wegen der Möglichkeit der partiel len Applikation ist die cur-ryf izierte Definit ion von Funktionen der über Tupeln vorzuziehen!Beispiele für partiel le Applikation:
• take 42 :: [a] -> [a] gibt die ersten 42 Elemente jeder Listezurück
• (+) 1 :: Int -> Int ist die Inkrement- oder Nachfolgerfunktion
Für Operatoren sind zusätzl iche partiel le Applikationen möglich:
• (2-) :: Int -> Int ist die Funktion \x -> 2 - x
• (-2) :: Int -> Int ist die Funktion \x -> x - 2
• (/b) a = (a/) b = a/b
Neben der partiel len Applikation auf ihr erstes Argument könnenOperatoren also auch partiel l auf ihr zweites Argument appliziertwerden.
1.4.2 Generische Programmierung
Wir betrachten folgende Haskell-Funktionen:
i n c L i s t : : [ Int ] −> [ Int ]i n c L i s t [ ] = [ ]i n c L i s t ( x : xs ) = (x+1) : i n c L i s t xs
code : : Char −> Charcode c | c == ’Z ’ = ’A’
| c == ’ z ’ = ’ a ’| otherwise = chr (ord c + 1)
codeSt r : : String −> StringcodeSt r "" = ""codeSt r ( c : c s ) = ( code c ) : codeSt r c s
1Currying geht zurück auf die Mathematiker Curry und Schönfinkel, die gleichzeitig, aberunabhängig voneinander in den 1940ern folgende Isosmorphie feststellten: [A×B → C] ' [A→[B → C]]
17
Beide Funktionen haben eine „ähnliche“ Struktur. Beide appliziereneine Funktion (code bzw. inc) auf al le Listenelemente. Dieses Schemakann man veral lgemeinern und code und inc als Parameter an dieveral lgemeinerte Funktion übergeben:
map : : ( a −> b) −> [ a ] −> [ b ]map f [ ] = [ ]map f ( x : x s ) = f x : map f x s
Nun lassen sich obige Funktionen ganz einfach definieren:
i n c L i s t = map (1+)codeSt r = map code
Wir betrachten ein weiteres Beispiel :
sum : : [ Int ] −> Intsum [ ] = [ ]sum ( x : xs ) = x + sum xs
checksum : : String −> Intchecksum [ ] = 1checksum ( c : c s ) = ord c + checksum c s
Auch hier ist eine ähnliche Struktur erkennbar, die man veral lgemei-nern kann:
foldr : : ( a −> b −> b) −> b −> [ a ] −> bfoldr f e [ ] = efoldr f e ( x : xs ) = f x ( foldr f e xs )
Nun lassen sich obige Funktionen wieder einfacher def inieren als:
sum = foldr + 0checksum = foldr ( \ c sum −> ord c + sum) 1
Weitere Anwendung wären zum Beispiel Konjunktion und Disjunktionauf Listen von Booleschen Werten:
and = foldr (&&) Trueor = foldr ( | | ) False
Entsprechend: concat = foldr (++)[].
Allgemeines Vorgehen: Suche ein al lgemeines Schema und real is ierees durch eine Funktion höhere Ordnung.
18
Weiteres Schema: Bewertung von Listenelementen gemäß eines Prä-dikats. Nur die Elemente, die das Prädikat erfül len werden in dieERgebnisl iste übernommen.
f i l t e r : : ( a −> Bool ) −> [ a ] −> [ a ]f i l t e r p [ ] = [ ]f i l t e r p (x : xs ) | p x = x : f i l t e r p xs
| otherwise = f i l t e r p xs
Die Umwandlung einer Liste in eine Menge (d.h. Entfernen doppelterEinträge) kann dann definiert werden durch:
nub : : [ Int ] −> [ Int ]nub [ ] = [ ]nub ( x : xs ) = x : nub ( f i l t e r (/= x) xs )
Sortieren von Listen mittels QuickSort :
q s o r t : : [ Int ] −> [ Int ]q s o r t [ ] = [ ]q s o r t ( x : xs ) = ( q s o r t ( f i l t e r (<=x) xs))++[x]++
( q s o r t ( f i l t e r (> x ) xs )
Diese Implementierung kann verbessert werden, indem man statt derdoppelten Anwendung eines Filters auf auf die Argumentl iste dieFunktion split verwendet -> Übung.
Auch filter ist mittels foldr definierbar!
f i l t e r = foldr ( \x ys −> i f p x then x : yselse ys ) [ ]
Beachte: foldr ist ein sehr al lgemeines Skelett (Programmiermuster),es entspricht einem Katamorphismus der Kategorientheorie. Dabeientspricht foldr f e (x1:x2:. . .:[]) der Auswertung
(f x1 (f x2 . . . (f xn e)))
es wird also jeder (:) durch f und die leere Liste durch e ersetzt.Die Verwendung von foldr hat aber manchmal auch Nachtei le . Dasäußerste f kann oft erst berechnet werden, wenn die ganze Struk-tur durchlaufen wurde, zum Beispiel wird bei foldr (+)~0 [1,2,3]zunächst 1 + (2 + (3 + 0)) auf den Stack gelegt und kann erst ausgerech-net werden, wenn die leere Liste erreicht wird.
Eine bessere Lösung kann mit Hil fe der Akkumulatortechnik definiertwerden:
19
sum : : [ Int ] −> Intsum = sum’ 0
where sum’ : : Int −> [ Int ] −> Intsum’ s [ ] = ssum’ s ( x : xs ) = sum’ ( s+x ) xs
Hier wird nun (mit konstantem Stack Verbrauch) ((0 + 1) + 2) + 3berechnet statt 1 + (2 + (3 + 0)) berechnet. Auch diese Lösung kann zueinem allgemeinen Programmierschema veral lgemeinert werden:
fo ld l : : ( a −> b −> a ) −> a −> [ b ] −> afo ld l f e [ ] = efo ld l f e ( x : xs ) = fo ld l f ( f e x ) xs
Dabei entspricht foldl f e (x1:x2:. . .:[]) der Auswertung
f . . . (f(f e x1) x2) . . . xn
.
1.4.3 Kontrollstrukturen (Programmschemata)
Schlei fenkonstrukte sind in imperativen Programmiersprachen dasMittel der Wahl, um Wiederholungen auszudrücken. Als Beispielbetrachten wir folgende while-Schlei fe in C:
x = 1 ;while ( x < 100)
x = x ∗ 2 ;
Analysiert man diese Schlei fe , so erkennt man, dass sie aus drei Tei lenbesteht:
• einem Anfangswert (x=1) ,
• einer Bedingung (x<100) und
• einem Rumpf, welcher den Zustand verändet (x=2*x) .
In Haskell können wir dies Kontrol lstruktur als ein Schema umsetzen.Die drei Tei le werden durch (z.T. funktionale) Parameter real is iert :
wh i l e : : ( a −> Bool ) −> (a −> a ) −> a −> awh i l e p f x | p x = wh i l e p f ( f x )
| otherwise = x
20
Obiges C-Porgramm entspricht dann dem Aufruf while (<100)(2*)1,welcher zu 128 ausgewertet wird.
Aus Sicht der funktionalen Programmierung, entspricht die imperati-ve Programmierung also einer Programmierung mit einem begrenztenSatz an Funktionen höherer Ordnung, den Kontrol lstrukturen.
1.4.4 Funktionen als Datenstrukturen
Definition: Eine abstrakte Datenstruktur ist ein Objekt mit:
• Konstruktoren (z.B. [], (:) bei Liste)
• Selektoren (z.B. head, tail)
• Testfunktionen (z.B. null)
• Verknüpfungen (z.B. (++))
Wichtig hierbei ist die Funktionalität der Schnittstel le und nicht dieImplementierung. Somit entspricht eine Datenstruktur einem Satzvon Funktionen. Die einfachste Implementierung kann also häufigmittels Funktionen erfolgen.
Beispiel: Arrays (Felder mit bel iebigen Elementen).
• Konstruktoren:
emptyArray : : Fe ld a
−− fügt Wert in Feld an Indexpos i t ion einputIndex : : Fe ld a −> Int −> a −> Feld a
• Selektoren
−− l i e f e r t Wert an Indexpos it ionget Index : : Fe ld a −> Int −> a
Implementierung:
type Feld a = Int −> a
emptyArray i = error ("Zugriff auf nicht" ++"initialisierte Arraykomponente" ++ show i )
ge t Index a i = a i
21
putIndex a i v = a ’where a ’ j | i == j = v
| otherwise = a j
Vorteil ist die konzeptuel le Klarheit (Implementierung entspricht derSpezif ikation), dies ist ideal für Rapid Prototyping. Nachteil: DieZugrif fszeit ist abhängig von der Anzahl der putIndex-Operationen.Durch einen abstrakten Datentyp ist später aber eine Optimierungmöglich.
1.4.5 Wichtige Funktionen höherer Ordnung
• Hintereinanderausführung von Funktionen mittels (.):
( . ) : : ( a −> b) −> ( c −> a ) −> c −> b( f . g ) x = f ( g x )
Beispiel: Die folgende Funktion l iefert die Anzahl der Elementeeiner Liste von Listen
length . concat : : [ [ a ] ] −> Int
• Vertauschung der Reihenfolge von Argumenten durch flip:
f l i p : : ( a −> b −> c ) −> b −> a −> cf l i p f x y = f y x
Beispiel: flip (:)[1] 2 [2, 1]
• curry und uncurry:
curry : : ( ( a , b ) −> c ) −> a −> b −> ccurry f x y = f ( x , y )
uncurry : : ( a −> b −> c ) −> (a , b) −> cuncurry f ( x , y ) = f x y
Beispiel:
map (uncurry (+)) ( zip [ 1 , 2 , 3 ] [ 4 , 5 , 6 ] ) [ 5 , 7 , 9 ]
• Konstante Funktion const:
22
const : : a −> b −> aconst x _ = x
1.5 Typklassen und ÜberladungBetrachte folgende Funktionsdef init ion:
elem x [ ] = Falseelem x (y : ys ) = x == y | | elem x ys
Was sol l der Typ von elem sein? Möglichkeiten wären z.B.:
elem : : Int −> [ Int ] −> Boolelem : : Bool −> [Bool ] −> Boolelem : : Char −> String −> Bool
Leider sind diese Typen nicht al lgemein genug. Eine Möglichkeit wärenoch
elem : : a −> [ a ] −> Bool
Dies ist zu allgemein, da a zum Beispiel Funktionen repräsentierenkann, für die die Gleichheit nicht entschieden werden kann. Deswegenmachen wir Einschränkung auf Typen, für die die Gleichheit def iniertist :
elem : : Eq a => a −> [ a ] −> Bool
Dabei ist Eq a ein Klassenconstraint, der a einschränkt. 2 Die Klasse Eqist wie folgt def iniert:
class Eq a where(==), (/=) : : a −> a −> Bool
In einer Klasse werden mehrere Typen zusammengefasst, für die dieFunktionen der Klasse def iniert sind (hier (==) und (/=)) . Typenwerden zu Instanzen einer Klasse wie folgt:
data Tree = Empty | Node Tree Int Tree
instance Eq Tree whereEmpty == Empty = True(Node t l 1 n1 t r 1 ) == (Node t l 2 n2 t r 2 ) =
2Bei mehreren Constraints muss man klammern: (Eq a, Ord a).
23
t l 1 == t l 2 && n1 == n2 && t r 1 == t r 2t1 /= t2 = not ( t 1 == t2 )
Die Gleichheit auf polymorphen Datentypen kann nur definiert wer-den, fal ls Gleichheit für Subtypen definiert ist :
data Tree a = Empty | Node (Tree a ) a (Tree a )
instance Eq a => Eq (Tree a ) where. . .
Beachte: Auf diese Weise werden unendlich viele Typen jeweils In-stanz der Klasse Eq.
Es gibt die Möglichkeit , vordef inierte Funktionen einer Klasse anzu-geben: Die Definit ion von (/=) wird in fast jeder Instanzdefinit iongleich aussehen. Deshalb verschieben wir sie in die Klassendefinit ion.Die eigentl iche Definit ion von Eq ist wie folgt:
class Eq a where(==), (/=) : : a −> a −> Boolx1 == x2 = not ( x1 /= x2 )x1 /= x2 = not ( x1 == x2 )
Dabei kann jeweils eine oder auch beide der vordef inierten Funktionenüberschrieben werden.
Es gibt die Möglichkeit , Klassen zu erweitern.Beispiel: Die Klasse, die die totale Ordnung definiert, ist eine Erwei-terung der Klasse Eq:
class Eq a => Ord a wherecompare : : a −> a −> Ording(<) , (<=), (>=), (>) : : a −> a −> Boolmax, min : : a −> a −> a
data Ording = (LT | EQ | GT)
Eine minimale Instanzi ierung dieser Klasse implementiert entwedercompare oder <=, es ist aber auch möglich, weitere Funktionen zuüberschreiben.
Weitere vordefinierten Klassen sind:
• Num zum Rechnen mit Zahlen (definiert (+), (-), (*), abs etc.)
Beispiel: (+) :: Num a =>a -> a -> a
24
• Show zum Umwandeln in Strings:
show : : Show a => a −> String
• Read zum Konstruieren aus Strings
Vordefinierte Klassen (außer Num) werden automatisch instanzi iertmittels deriving (K1, . . . ,Kn) hinter der Datentypdefinit ion3 , Beispiel :
data Tree = Node Tree Int Tree | Emptyderiving Show
1.5.1 Die Klasse Read
Die Funktion read hat den Typ Read a =>~String -> a, d.h. der Aufrufread "(3, a)" wird ausgewertet zu (3, ’a’). Der Aufruf setzt sichzusammen aus drei unterschiedl ichen read-Funktionen:
read : : String −> Intread : : String −> Charread : : (Read a , Read b) => String −> (a , b)
Idee: die Eingabe wird zeichenweise abgearbeitet, das Ergebnis ent-hält den Reststring. Die Reihenfolge der Aufrufe ist z.B.:
readTuple "(3, ’a’)"readInt "3, ’a’)" ( 3 , ", ’a’)" )readChar "’a’)" ( ’ a ’ , ")" )
( ( 3 , ’ a ’ ) , "" )
Auch Fehler müssen berücksichtigt werden. Eine Möglichkeit wäre:
read : : Read a => String −> Maybe ( a , String )
In Haskell wird es anders gemacht:
type ReadS a = String −> [ ( a , String ) ]class Read a wherereadsPrec : : Int −> ReadS areadList : : ReadS [ a ] −− vo rde f i n i e r t
Der erste Parameter von readsPrec ist die Ausdruckstiefe (Anzahl derzu erwartenden Klammern). In der Prelude sind definiert:
3Die Klammern können bei einer einzelnen abgeleiteten Klasse weggelassen werden.
25
reads : : Read a => ReadS areads = readsPrec 0read : : Read a => String −> aread xs = case reads xs of
[ ( x , "" ) ] −> x_ −> error "no parse"
Beispiel:
reads "(3, ’a’)" : : [ ( ( Int , Char) , String ) ] [ ( ( 3 , ’ a ’ ) , "" ) ]
reads "3, ’a’)" : : [ ( Int , String ) ] [ ( 3 , ", ’a’)" ) ]
1.6 Lazy EvaluationBetrachte folgendes Haskell-Programm:
f x = 1h = h
mit der Anfrage:
f h
Nicht jeder Berechnungspfad dieser Anfrage terminiert. Es gibt aberzwei ausgezeichnete Reduktionen:
• Leftmost-Innermost (LI, strikte Funktionen) : Alle Argumente einesFunktionsaufrufs müssen ausgewertet sein, bevor die Funkti-on angewendet werden kann.
• Leftmost-Outermost (LO, nicht-strikte Funktionen) : Die Funktionen wer-den jeweils vor Argumenten ausgewertet.
Vorteil von Leftmost-Outermost ist die Berechnungsvollständigkeit : Alles,was mit irgendeiner Reduktion berechenbar ist , wird auch mit LOberechnet. Dies ist praxisrelevant u.a. für:
• Vermeidung überflüssiger Berechnungen.
Beispiel:
head ( [ 1 , 2 ] ++ [ 3 , 4 ] )
26
head ([1,2] ++ [3,4])
head (1:([2] ++ [3,4]))
LO, LI
1
LO
head (1:2:([]++[3,4]))
LI
head (1:2:[3,4])
LI
1
LI
Abbildung 1: Auswertung von head ([1,2] ++ [3,4])
Die Auswertung mit beiden Strategien ist in der Abb. 1 darge-stel lt .
• Rechnen mit unendlichen Datenstrukturen.
Beispiel: Die Funktion
from : : Num a => a −> [ a ]from n = n : from (n + 1)
definiert eine unendliche Liste al ler Zahlen ab n. Betrachte nun
take : : Int −> [ a ] −> [ a ]take n _ | n <= 0 = [ ]take n [ ] = [ ]take n (x : xs ) = x : take (n − 1 ) xs
Jetzt können wir schreiben
take 3 ( from 1) take 3 ( 1 : from(1+1)) 1 : take (3−1) ( from(1+1)). . . 1 : 2 : 3 : take 0 ( from 4) 1 : 2 : 3 : [ ]
27
Vorteil: Trennung von Kontrol le (take 3) und Daten (from 1) .
• Ein weiteres
Beispiel: Primzahlberechnung mittels Sieb des Eratosthenes. Idee:
1. Erstel le Liste al ler Zahlen größer gleich 2.
2 . Streiche Viel fache der ersten (Prim-)Zahl aus der Liste.
3. Das 1. Listenelement ist Primzahl, weiter bei (2) mit Rest-l iste.
In Haskell:
s i e v e : : [ Int ] −> [ Int ]s i e v e (p : xs ) = p : s i e v e
( f i l t e r ( \x −> x ‘mod‘ p > 0) xs )
pr imes = s i e v e ( from 2)take 10 pr imes [ 2 , 3 , 5 , 7 , 1 1 , 1 3 , 1 7 , 1 9 , 2 3 , 2 9 ]
• Die Programmierung mit unendlichen Datenstrukturen kannauch als Alternative zur Akkumulatortechnik verwendet werden.
Beispiel: Liste al ler Fibonacci-Zahlen.
f i b g en : : Int −> Int −> [ Int ]f i b g e n n1 n2 = n1 : f i b g en n2 (n1 + n2)
f i b s : : [ Int ]f i b s = f i b g en 0 1f i b : : Int −> Intf i b n = f i b s ! ! n
f i b 10 34f i b 9 25
Bei der zweiten Auswertung ist die neue Generierung der Listenicht nötig, da Konstanten nur einmal berechnet werden. DieseTechnik zum Merken von aufwändigen Berechnungen (Memorizati-on ) führt al lerdings gegebenenfal ls zur Speicherverschwendung.
28
Nachteil der LO-Strategie: Berechnungen können dupliziert werden,z.B. in double x = x + x. Aus Eff iz ienzgründen verwendet daher keineProgrammiersprache die reine LO-Strategie.
Eine Optimierung ist die sogenannte Lazy-Auswertung : Statt Termenwerden Graphen reduziert, die Variablen des Programms entsprechenZeigern auf Ausdrücke. Die Auswertung eines Ausdrucks gi lt für al leVariablen, die an diesen gebunden sind (sharing ) . Der Mechanismusder Normalisierung führt Variablen für jeden Teilausdruck ein.
Die Formalis ierung ist die sogenannte Launchbury-Semantik. Die Lazy-Auswertung ist optimal bezüglich der Länge der Ableitung, al lerdingsbenötigt sie oft viel Speicher. Deswegen benutzen Sprachen wie ML,Erlang, Scheme oder Lisp die LI-Reduktion.
1.7 Simulation in Stirkten SprachenLaziness ist auch in strikten Sprachen möglich! Idee: Verwendungvon Funktionen zur Verzögerung (Lazy-Datenstrukturen). Wir verwendendabei den Unit-Typ, der nur () als einzigen Wert enthält und alsDummy-Argument verwendet wird.Beispiel: Wir betrachten Lazy Listen. Die lazy Listenkonstruktorenwerden dann durch folgende Funktionen repräsentiert:
• x : xs entspr. \()-> x : xs
• [] entspr. \()-> []
Funktionen sind auch in strikten Sprachen Werte, welche nicht weiterausgewertet werden. Eine Reduktion unterhalb des Lambdas ist nichtsinnvoll , da sie oft nicht möglich ist (wegen der ungebundenen freienVariablen) und die Funktion ja nicht unbedingt appliziert werdenmuss und somit die Reduktion überf lüssig wäre.
type List a = ( ) −> ListD adata ListD a = N i l | Cons a (List a )
n i l = \ ( ) −> Ni l
cons x xs = \ ( ) −> Cons x xs
−− head : : [ a ] −> aheadL : : List a −> a
29
headL xs = l et (Cons y _) = xs ( ) in y
−− t a i l : : [ a ] −> [a ]t a i l L : : List a −> List at a i l L xs = l et (Cons _ ys ) = xs ( ) in ys
−− nu l l : : [ a ] −> Booli s N i l : : List a −> Booli s N i l x s = case xs ( ) of
Ni l −> True_ −> False
−− (++) : : [ a ] −> [a ] −> [a ]app : : List a −> List a −> List aapp xs ys = i f i s N i l x s
then yselse \ ( ) −> Cons (headL xs )
(app ( t a i l L xs ) ys )
−− enumFromfrom n = \ ( ) −> Cons n ( from (n + 1 ) )
−− take : : Int −> [a ] −> [a ]takeL n xs =
i f i s N i l x s | | n==0then n i lelse \ ( ) −> Cons (headL xs ) ( takeL (n−1) ( t a i l L xs ) )
showL : : Show a => List a −> StringshowL xs =
i f i s N i l x sthen "[]"else show (headL xs ) ++ ":" ++ showL ( t a i l L xs )
Dies kann man dann beispielsweise wie folgt anwenden:
head ( from 1) l et (Cons x _) = from 1 ( ) in x l et (Cons x _) = cons 1 ( from (1 + 1 ) ) ( ) in x l et (Cons x _) = cons 1 ( from 2) ( ) in x l et (Cons x _) = Cons 1 ( from 2) in x 1
30
Beachte, dass folgende Abkürzende Definit ion für \()-> Cons x xsnicht möglich ist:
cons x xs = \x −> Cons x xs
from n = cons n ( from (n+1))
i s N i l ( from 1) i s N i l ( cons 1 ( from (1+1)) i s N i l ( cons 1 ( from 2 ) ) i s N i l ( cons 1 ( cons 2 ( from (2+1))) . . .
Es ist also möglich Laziness in strikten Sprachen zu simulieren, al-lerdings ist der Programmiersti l weniger komfortable und auch feh-leranfäl l ig (kein Pattern Matching, Konstruktoren müssen überal ldurch \()-> Cons geschützt werden). Außerdem steht Laziness nur fürbestimmte Konstruktoren zur Verfügung. In obiger Implementierungsind nur die Listenkonstruktoren lazy. Die Listenelemente sind nichtvor strikten Auswertungen geschützt.
2 MonadenMonaden sind eine Technik zur (lazy) Sequential iz ierung in funk-tionalen Sprachen. Zunächst beschränken wir uns auf Ein-/Ausgabe.Wann sol l in Lazy-Sprachen Ein- und Ausgabe stattf inden?Beispiel:
main = l et s t r = getLine inputStr s t r
Was ist der Wert von main? Es ist der Wert von putStr str, e ineMöglichkeit wäre (). Dann wäre aber eigentl ich keine Ein/Ausgabenötig, um das Ergebnis () zu berechnen. Deshalb in ML: Ausgabeals Seiteneffekt von Funktionen, ausgeführt, wenn getLine/putStrausgewertet wird. Aber was passiert dann bei folgendem Programm?
man = getLine ++ getLine
Hier passiert nur eine Eingabe, da getLine eine Konstante ist . Besserwäre:
31
main = getLine ( ) ++ getLine ( )
was aber nicht äquivalent zum folgender Definit ion ist , da x natürl ichnur einmal ausgewertet wird:
main = l et x = getLine ( ) inx ++ x
Ein weiteres Problem:
main = l et s t r = getLine ( ) ++ getLine ( ) inhead s t r
In einer Lazy-Sprache entstünde aber folgendes Problem: fal ls dieerste Eingabe mindestens ein Zeichen enthält ist keine weitere Ein-gabe notwendig, sonst muss eine zweite Eingabe gemacht wird. Wirddann aber später (z.B. in weiterem Code hinter head str) auf weite-re Elemente von str zugegri f fen, so muss nachträgl ich eine weitereEingabe verlangt werden.Spielt man diese Idee weiter, so ergibt sich folgendes Problem infolgendem häufig verwendeten Szenario:
main = l et database = readDBFromUserr e qu e s t = readRequestFromUser
in lookupDB reque s t database
Wegen Laziness wird database erst eingelesen, nachdem request einge-lesen wurde und auch nur soweit, wie nötig um lookup durchzuführen;später wird die Datenbank dann ggf. weiter eingelesen für weitereRequests. Dies ist natürl ich unpraktikabel .
2.1 Die IO-MonadeWichtig für Ein- und Ausgabe sind weniger die Werte, als vielmehrdie Aktionen und ihre Reihenfolge. Die Aktionen müssen sequential is iertwerden. In Haskell gibt es dafür den abstrakten Datentyp IO (), z .B.
putChar : : Char −> IO ( )
IO-Werte sind First-Order-Werte, werden aber nur ausgeführt, wenn siein die IO-Aktion von main (bzw. interaktive Anfrage bei Hugs/ghci)eingebaut sind.
Das Zusammensetzen von IO-Aktionen geschieht mittels des Sequenz-Operators:
32
(>>) : : IO ( ) −> IO ( ) −> IO ( )
Beispiele:
• Die Funktion
main : : IO ( )main = putChar ’ a ’ >> putChar ’ a ’
verhält sich genauso wie
main = l et p = putChar ’ a ’ in p >> p
oder wie
main = l et l = repeat (putChar ’ a ’ )in l ! ! 1 >> l ! ! 2
Die Aktionen werden nur in der main-IO-Aktion ausgeführt.
• Ausgabe von Zeilen:
putStr : : String −> IO ( )putStr "" = return ( )putStr ( c : c s ) = putChar c >> putStr c s
Dabei ist return () eine IO-Aktion, die nichts tut. Andere Defi-nit ionsmöglichkeit :
putStr = foldr ( \ c−>(putChar c >>)) ( return ( ) )
Für die Eingabe hat der Typkonstruktor IO zusätzl ich einen Typ-parameter für die Übergabe von Werten an nachfolgende Aktionen,z.B:
getChar : : IO Charreturn : : a −> IO a
Sequenzierung mit Weitergabe erfolgt mittels des Bind-Operators :
(>>=) : : IO a −> (a −> IO b) −> IO b
Beispiele:
(getChar >>= putChar) : : IO ( )
33
getLine : : IO StringgetLine = getcha r >>= \ c −>
i f c == ’ \n ’then return ""else getLine >>= \ c s −> return ( c : c s )
main = getLine >>= putStr
Die do-Notation ist eine vereinfachte Schreibweise, die statt der Ope-ratoren (>>=), (>>) nur Sequenzen verwendet. Eingeleitet wird sie mitdem Schlüsselwort do, die Länge des Blockes bestimmt die Off-Side-Rule (alternativ ist auch eine Blocknotation mit {. . .} und ; möglich.Ausdrücke in der do-Notation sind:
pat ← el et pat = e −− ohne ine
Beispiel:
main = doc ← getCharputChar c
Dies entspricht
main = getChar >>= \c −> putChar c
Die Variablen sind ab ihrer Einführung gültig. Die Pattern l inks von← müssen fehlerfrei matchen, sonst wird ein Laufzeitfehler erzeugt --deswegen verwendet man meist Variablen.
Beispiele:
• getLine in do-Notation
getLine = doc ← getChari f c == ’ \n ’ then return ""else do c s ← getLine
return ( c : c s )
• Ausgabe al ler Zwischenergebnisse von fac:
34
f a c : : Int −> IO Int
f a c 0 = do putStr "1"return 1
f a c (n + 1) = dofacN ← f a c nl et facNp1 = (n + 1) ∗ facNputStr ( ’ ’ : show facNp1 )return facNp1
do x ← f a c 7 ; print x
Beachte: Bei manchen interaktiven Haskel l -Systemen werden nirAusdrücke vom Typ IO () ausgeführt. Deswegen wird bei derAuswertung von fac 7 nur <<IO Action>> ausgegeben.
Die eben verwendete Funktion print ist def iniert als
print : : Show a => a −> IO ( )print = putStrLn . show
Allgemeiner Programmierstil sol lte es sein, möglichst wenig IO-Ope-rationen zu benutzen:
1. Einlesen in IO-Monade.
2. Berechnung auf Basis der Eingabewerte rein funktional , außer-halb der IO-Monade.
3. Ergebnis der Berechnung ausgeben.
Dies ist alternativ zum Einlesen/Ausgeben über Standardein/-ausgabeauch über das Dateisystem möglich. Hierzu stehen folgende die Funk-tionen zu Verfügung:
readFile : : String −> IO StringwriteFile : : String −> String −> IO ( )
Als Beispiel betrachten wir folgendes kurzes Programm: Falls eineDatei mit Namen in existiert , wird diese eingelesen, eine Funktionparse :: String -> String auf den Datei inhalt angewendet und dasErgebnis in eine Datei out geschrieben:
35
main = dos t r ← readFile "in"writeFile "out" ( pa r s e s t r )
main = readFile "in" >>= writeFile "out" . pa r s e
Wegen der einfachen Möglichkeiten des Dateizugri f fs und der ein-fachen Listenprogrammierung für Strings, eignet sich Haskel l auchhervorragend als Skriptsprache.
2.2 List ComprehensionsWir haben bereits syntaktischen Zucker für Aufzählungen kennenge-lernt:
[ 1 . . 4 ] enumFromTo 1 4 [ 1 , 2 , 3 , 4 ][ 4 , 2 . . ] [ 4 , 2 , 0 ,−2 ,−4 , . . .
Noch komfortabler sind List Comprehensions: Mengen schreibt man inder Mathematik gerne wie folgt:
{(i, j) | i ∈ {1, . . . , 3}, j ∈ {2, 3, 4}, i 6= j}
In Haskell ist eine ähnliche Schreibweise für Listen möglich. Eine Liste,die obiger Menge entspricht, erhält man mit:
[ ( i , j ) | i ← [ 1 . . 3 ] , j ← [ 2 , 3 , 4 ] , i /= j ] [ ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 2 ) , ( 3 , 4 ) ]
Die al lgemeine Form der List Comprehensions ist :
[ e | l c e 1 , l c e 2 , . . . , l c e n ]
Dabei ist e ein bel iebiger Ausdruck über die in lcei definierten Varia-blen, und die Ausdrücke lcei sind von der folgenden Form:
• Generatoren: pat ← e, wobei e ein Ausdruck vom Listentyp ist
• Tests: e vom Typ Bool
• lokale Definit ionen: let pat = e (ohne das in e’)
In einem Ausdruck lcei können alle Variablen benutzt werden, die inlcej mit j < i definiert wurden.
Beispiele:
36
• Anfangsstücke natürl icher Zahlen
[ [ 0 . . n ] | n ← [−1 . . ] ] [ [ ] , [ 0 ] , [ 0 , 1 ] , [ 0 , 1 , 2 ] , . . .
• Konkatenation von Listen:
concat : : [ [ a ] ] −> [ a ]concat x s s = [ x | xs ← xxs , x ← xs ]
Beachte, dass die Generatoren geschachtelten Schlei fen (Rekur-sionen) entsprechen! Das führt ggf. zu Problemen bei unendli-chen Listen:
[ ( i , j ) | i ← [ 1 . . 3 ] , j ← [ 1 . . ] ] [ ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) , . . .
Hier sol lte man die Generatoren vertauschen:
[ ( i , j ) | j ← [ 1 . . ] , i ← [ 1 . . 3 ] ] [ ( 1 , 1 ) , ( 2 , 1 ) , ( 3 , 1 ) , ( 1 , 2 ) , . . .
• Transponieren einer Matrix (gegeben als Liste von Listen):
transpose : : [ [ a ] ] −> [ [ a ] ]transpose [ ] = [ ]transpose ( [ ] : x s s ) = transpose x s stranspose ( ( x : x s ) : x s s ) =
(x : [ h | (h : t ) ← x s s ] ): transpose ( xs : [ t | (h : t ) ← x s s ] )
• Acht-Damen-Problem: Acht Damen sol len auf einem Schachfeldso platziert werden, dass keine eine andere schlagen kann. Ko-diert werden die Lösungen hier durch einen Posit ionsvektor,Beispiel :
[ 0, 1, 2, 3, 4, 5, 6, 7 ]? − − − − − − −− ? − − − − − −− − ? − − − − −− − − ? − − − −− − − − ? − − −− − − − − ? − −− − − − − − ? −− − − − − − − ?
37
Zunächst werden mit Hil fe der Funktion queens’ al le Permutatio-nen der Liste [0..7] bestimmt. Diese stel len al le möglichkeitendar, in denen man acht Türme auf einem Schachbrett vertei lenkann.
queens ’ : : Int −> [ [ Int ] ]queens ’ 0 = [ [ ] ]queens ’ (n+1) = [ q : b | b ← queens ’ n ,
q ← [ 0 . . 7 ] ,not (elem q b) ]
−− korrekt b i s auf Diagonalen
Nun muss nur noch überprüft werden, ob zwei sich zwei Damenauf einer Diagonalen befinden.
diagsOK : : [ [ Int ] ] −> [ [ Int ] ]diagsOK = f i l t e r ( \b −> and
[ not ( j − i == abs (b ! ! i − b ! ! j ) )| i ← [ 0 . . 7 ] , j ← [ i + 1 . . 7 ] ] )−− Diagonalen kor r i g i e ren
queens : : [ [ Int ] ]queens = diagsOK ( queens ’ 8 )
head queens [ 3 , 1 , 6 , 2 , 5 , 7 , 4 , 0 ]
3 Theoretische Grundlagen: Der λ-KalkülGrundlage funktionaler Sprachen ist der λ-Kalkül, der 1941 von Churchentwickelt wurde. Motivation war, eine Grundlage der Mathematikund mathematischen Logik zu schaffen; in diesem Zusammenhangentstand der Begrif f der „Berechenbarkeit“ . Es zeigte sich eine Äquiva-lenz zur Turing-Maschine, aus der die Church’sche These hervorging.
Wichtige Aspekte:
• Funktionen als Objekte
• gebundene und freie Variablen
• Auswertungsstrategien
38
3.1 Syntax des λ-KalkülsVar sei eine abzählbare Menge von Variablen, Exp die Menge derAusdrücke des reinen λ-Kalküls, die def iniert werden durch (e ∈ Exp) :
e ::= v (mit v ∈ Var) Variable| (e e′) (mit e, e′ ∈ Exp) Applikation| λv.e (mit v ∈ Var, e ∈ Exp) Abstraktion
Wir verwenden folgende Konvention zur Klammervermeidung:
• Applikation ist l inksassoziativ -- d.h. xyz statt ((xy)z)
• Wirkungsbereich von λ so weit wie möglich -- d.h. λx.xy stattλx.(xy) und nicht ((λx.x)y)
• Listen von Parametern: λxy.e statt λx.λy.e
Beachte: Es gibt keine Konstanten (vordef inierte Funktionen) oderIf-Then-Else-Strukturen, diese sind später im reinen λ-Kalkül def i -nierbar. Der reine λ-Kalkül ist damit minimal, aber universel l !
3.2 SubstitutionDie Semantik des reinen λ-Kalküls erfolgt wie in funktionalen Spra-chen: λx.e entspricht den anonymen Funktion \x -> e. Somit gi lt(λx.x)z z , wobei im Rumpf der Funktion (x) die Variable x durch zsubstituiert wurde. Damit können aber Namenskonfl ikte auftreten:
(λf.λx.fx)x 6 λx.xx Konfl ikt(λf.λx.fx)x λy.xy kein Konfl ikt
Definiere dafür zunächst freie bzw. gebundene Variablen durch:
free(v) = {v} bound(v) = ∅free((e e′)) = free(e) ∪ free(e′) bound((e e′)) = bound(e) ∪ bound(e′)free(λv.e) = free(e) \ {v} bound(λv.e) = bound(e) ∪ {v}
Ein Ausdruck e heißt geschlossen (Kombinator), wenn free(e) = ∅ ist .
Wichtig: Bei der Applikation nur Ersetzung der freien Vorkommender Parameter, wobei Namenskonfl ikte vermieden werden müssen.Präzis iert wird dies durch die Definit ion der Substitution :
39
Seien e, f ∈ Exp, v ∈ Var. Dann ist die Substitution e[v/f ] („ersetze v durchf in e“) def iniert durch:
v[v/f ] = fx[v/f ] = x für x 6= v
(e e′)[v/f ] = (e[v/f ] e′[v/f ])λv.e[v/f ] = λv.eλx.e[v/f ] = λx.(e[v/f ]) für x 6= v, x /∈ free(f)λx.e[v/f ] = λy.(e[x/y][v/f ]) für x 6= v, x ∈ free(f),
y /∈ free(e) ∪ free(f)
Somit gi lt : Fal ls v /∈ free(e), so ist e[v/f ] = e.
Damit ist eine Präzisierung des Ausrechnens der Applikation als Re-duktionsrelation erreicht.
3.3 ReduktionsregelnDefiniere die Beta-Reduktion (β-Reduktion) durch folgende Relation:
→β ⊆ Exp× Exp mit (λv.e)f →β e[v/f ]
Beispiel: Nun gilt(λf.λx.fx)x→β λy.xy
aber auch(λf.λx.fx)x→β λz.xz
Somit ist →β nicht konfluent4!
Aber: Die Namen der Parameter spielen keine Rolle bezüglich derBedeutung einer Funktion, d.h. die syntaktisch verschiedenen Termeλx.x und λy.y sind semantisch gleich (die Identitätsfunktion)
Lösung: Die Alpha-Reduktion (α-Reduktion) ist eine Relation
→α ⊆ Exp× Exp mit λx.e →α λy.(e[x/y]) (fal ls y /∈ free(e))
Beispiele:
λx.x→α λy.y, λy.xy →α λz.xz, λy.xy 6→α λx.xx
Somit gi lt e ↔∗α e′ („e und e′ sind α-äquivalent“) genau dann, wennsich e und e′ nur durch Namen der Parameter unterscheiden.
4Eine Relation →∗ ist konfluent, falls für alle u, v, w mit u →∗ v und u →∗ w auch ein zexistiert mit v →∗ z und w →∗ z.
40
Konvention im Folgenden: Bertrachte α-äquivalente Ausdrücke alsgleich, d.h. rechne auf α-Äquivalenzklassen statt auf Ausdrücken.
Die β -Reduktion kann bisher Ausdrücke ausrechnen, al lerdings nuraußen -- deswegen setzen wir die β -Reduktion auf bel iebige Stel lenin Ausdrücken fort (analog für α-Reduktion):
e→β e′ =⇒ ef →β e
′f∧ fe →β fe
′
∧ λx.e →β λx.e′
Eigenschaften der β -Reduktion:
• Die Relation →β ist konfluent.
• Jeder Ausdruck besitzt höchstens eine Normalform bezüglich →β
(bis auf α-Äquivalenzklassen).
Es gibt al lerdings auch Ausdrücke ohne Normalform, dies ist wichtigfür die Äquivalenz zu Turing-Maschinen! Betrachte:
(λx.xx)(λx.xx)→β (λx.xx)(λx.xx)
Die darin enthaltene Selbstapplikation (λx.xx) würde in Programmier-sprachen zu Typfehlern führen.
Frage: Wie f indet man die Normalform, fal ls s ie exist iert?
Ein β-Redex sei ein Teilausdruck der Form (λx.e)f . Dann ist eine Reduk-tionsstrategie eine Funktion von der Menge der Ausdrücke in die Mengeder Redexe: Sie gibt an, welcher Redex als nächster reduziert wird.Wichtige Reduktionsstrategien sind:
• Leftmost-Outermost-Strategie (LO, nicht strikt, normal-order-reduction) :wähle l inkesten, äußersten Redex
• Leftmost-Innermost-Strategie (LI, strikt, applicative-order-reduction) : wählel inkesten, innersten Redex
(λx.z)((λx.xx)(λx.xx)) →LI (λx.z)((λx.xx)(λx.xx))(λx.z)((λx.xx)(λx.xx)) →LO z
Satz: Ist e′ eine Normalform von e, d.h. e→∗β e′ 6→β e′′ , dann existiert
eine LO-Ableitung von e nach e′ .
Damit berechnet LO jede Normalform, LI manche nicht! LO ist somitberechnungsstärker als LI.
41
Ein wichtiger Aspekt (für Optimierungen, Transformation, Verif ika-tion) ist die Äquivalenz von Ausdrücken5 . Intuit iv sind e und e′ genaudann äquivalent, wenn e überal l für e′ eingesetzt werden kann, ohnedas Ergebnis zu verändern.Beispiele:
• λx.x ist äquivalent zu λy.y
• λf.λx.((λy.y)f)((λz.z)x) ist äquivalent zu λf.λx.fx
Wünschenswert wäre es, die Äquivalenz durch syntaktische Transfor-mationen nachweisen zu können. α- und β -Äquivalenz sind dafür abernicht ausreichend, betrachte folgendes Beispiel ( in Haskell-Notation):(+1) ist äquivalent zu λx.(+)1x, denn bei der Anwendung auf ein Ar-gument z gi lt :
(+1)z(+)1z und (λx.(+)1x)z →β (+)1z
Doch beide Terme sind weder α- noch β -äquivalent. Daher def inierenwir noch die Eta-Reduktion (η-Reduktion) als Relation:
→η ⊆ Exp× Exp mit λx.ex →η e (fal ls x /∈ free(e))
Weitere Sichtweisen der η-Reduktion:
• Die η-Reduktion ist eine vorweggenommene β -Reduktion:(λx.ex)f →β ef , fal ls x /∈ free(e) ist .
• Extensional ität: Funktionen sind äquivalent, fal ls s ie gleicheFunktionsgraphen (Menge der Argument-Wert-Paare) haben. Beach-te: Falls fx↔∗β gx6 gi lt , dann ist f ↔∗β,η g (mit x ∈ free(f) ∩ free(g)) ,da gi lt :
f ←η λx.fx↔∗β λx.gx→η g
Es gibt auch noch eine weitere Reduktion, die Delta-Reduktion (δ-Reduktion),die das Rechnen mit vordef inierten Funktionen ermöglicht, wie zumBeispiel (+) 1 2 →δ 3. Diese vordef inierten Funktionen sind nichtnotwendig, da sie im reinen λ-Kalkül darstel lbar sind.
Zusammenfassung der Reduktionen im λ-Kalkül:
• α-Reduktion: Umbenennung von Parametern5Wobei wir im Folgenden nur Äquivalenz auf terminierenden Ausdrücken betrachten, sonst ist
nicht klar, was man unter „Ergebnis“ versteht.6Unter u↔∗β v verstehen wir: es gibt ein w, so dass u→∗β w und v →∗β w.
42
• β -Reduktion: Funktionsanwendung
• η-Reduktion: Elimination redundanter λ-Abstraktionen
• δ-Reduktion: Rechen mit vordef inierten Funktionen
3.4 Datenobjekte im reinen λ-KalkülDatentypen sind Objekte mit Operationen darauf, Idee hier: Stel le dieObjekte durch geschlossene λ-Ausdrücke dar und definiere passendeOperationen.
Betrachte den Datentyp der Wahrheitswerte: Objekte sind True undFalse, die wichtigste Operation ist die If-Then-Else-Funktion:
if_then_else(b, e1, e2) =
{e1 , falls b = Truee2 , falls b = False
Daher sind Wahrheitswerte nur Projektionsfunktionen:
True ≡ λx.λy.x erstes Argument nehmenFalse ≡ λx.λy.y zweites Argument nehmen
Nun lässt sich eine If-Then-Else-Funktion definieren durch
Cond ≡ λb.λx.λy.bxy
Beispiel:
Cond True e1e2 ≡ (λbxy.bxy)(λxy.x)e1e2 →3β (λxy.xe1e2) →2
β e1Cond False e1e2 ≡ (λbxy.bxy)(λxy.y)e1e2 →3
β (λxy.ye1e2) →2β e2
Nun kodieren wir die natürlichen Zahlen: Betrachte die Church-Numerals,die jede Zahl n ∈ N als Funktional darstel len, das eine Funktion fgenau n mal auf ein Argument anwendet:
0 ≡ λf.λx.x
1 ≡ λf.λx.fx
2 ≡ λf.λx.f(fx)
3 ≡ λf.λx.f(f(fx))
n ≡ λf.λx.fnx
Nun definieren wir Operationen:
43
• Die wichtigste Operation ist die Nachfolgefunktion succ:
succ ≡ λn.λf.λx.nf(fx)
Beispiel: Nachfolger von Eins:
succ 1 ≡ (λn.λf.λx.nf(fx))(λf.λx.fx)
→β λf.λx.(λf.λx.fx)f(fx)
→β λf.λx.(λx.fx)(fx)
→β λf.λx.f(fx) ≡ 2
• Test auf Null :is_Null ≡ λn.n(λx.False)True
Beispiel: Teste Null auf Null :
is_Null 0 = (λn.n(λx.False)True)(λf.λx.x)
→β (λf.λx.x)(λx.False)True→β (λx.x)True→β True
3.5 Mächtigkeit des KalkülsIst der reine λ-Kalkül also berechnungsuniversel l? Ja, denn auchRekursion ist darstel lbar, beachte den Fixpunktsatz:
Satz: Zu jedem F ∈ Exp gibt es einen Ausdruck X mit FX ↔∗β X .
Beweis: Wähle zum Beispiel X = Y F mit Fixpunktkombinator Y :
Y ≡ λf.(λx.f(xx))(λx.f(xx))
Es bleibt zu zeigen, dass Y F ↔β F (Y F ) gi lt , s iehe Übung.
Der reine λ-Kalkül ist minimal, aber berechnungsuniversel l - - erbesitzt aber eher theoretische Relevanz (Barendregt 1984).
3.6 Angereicherter λ-KalkülFür funktionale Programmiung ist aber eher ein angereicherter λ-Kalkül relevant, bei dem Konstanten (vordef inierte Objekte undFunktionen), let, if-then-else und ein Fixpunktkombinator hinzuge-nommen werden.
44
Die Syntax des angereicherten λ-Kalküls:
e ::= v Variable| k Konstantensymbol| (e e′) Applikation| let v = e in e′ lokale Definit ionen| if e then e1 else e2 Alternative
(manchmal auch case)| µv.e Fixpunktkombinator
Als operationale Semantik benutzen wir zusätzl ich zur α- , β - undη-Reduktion noch folgende Regeln:
• δ-Reduktion für Konstanten, z.B. (+) 21 21→δ 42
• let v = e in e′ → e′[v/e]
• if True then e1 else e2 → e1if False then e1 else e2 → e2
• µv.e→ e[v/µv.e]
Beispiel: Fakultätsfunktion:
fac ≡ µf.λx. if ((==) x 0) then 1 else ((∗) x (f ((−) x 1)))
Der angereicherte λ-Kalkül bi ldet die Basis der Implementierung funk-tionaler Sprachen (Peyton, Jones 1987):
1. Übersetze Programme in diesen Kalkül (Core-Haskell im ghc) :
• Pattern-Matching wird in if-then-else (oder case) übersetzt,
• f x1 . . . xn = e wird übersetzt zu f = λx1 . . . xn.e,
• für rekursive Funktionen führt man Fixpunktkombinatorenein,
• ein Programm entspricht einer Folge von let-Deklarationenund einem auszuwertenden Ausdruck.
2. Implementiere den Kalkül durch eine speziel le abstrakte Maschi-ne, z.B. durch die SECD-Maschine von Landin in ghc oder durcheine Graphreduktionsmaschine.
Weitere Anwendungen des erweiterten λ-Kalküls sind die denotatio-nel le Semantik und die Typisierung (getypte λ-Kalküle).
45
4 MonadenUntersucht man die IO-Monade und ihre Verknüpfungen genauer,erkennt man die Gültigkeit folgender Gesetze:
return ( ) >> m = mm >> return ( ) = mm >> (n >> o ) = (m >> n) >> o
Hierbei fäl lt auf, dass (>>) assoziativ ist und return () ein neutralesElement ist , d.h. beide ergeben zusammen ein Monoid.Entsprechend gelten für return und >>= folgende Gesetze:
return v >>= \x −> m = m[ x/v ]m >>= \x −> return x = mm >>= \x −> (n >>= \y −> o ) =
(m >>= \x −> n) >>= \y −> o −− f a l l s x /∈ free(o)
Diese Struktur heißt Monade. Der Monaden-Begrif f stammt aus derKategorientheorie, wo er al lgemeiner von einem Funktor und zweinatürl ichen Transformationen spricht und wo die Monadengesetzemathematisch formuliert sind7 . Das Wort Monade wurde von Leibniz’entlehnt8 .In Haskel l ist eine Monade also ein einstel l iger Typkonstruktor m mitden Operationen return, (>>=) (und fail) , welche die obigen Eigen-schaften erfül len und in der Klasse Monad zusammengefasst werden:
class Monad m where(>>=) : : m a −> (a −> m b) −> m b
return : : a −> m a
f a i l : : String −> m af a i l s = error s
(>>) : : m a −> m b −> m bp >> q = p >>= \_ −> q
7http://en.wikipedia.org/wiki/Monad_(category_theory)8Das Wort Monade kommt aus dem Griechischen und bedeutet Eines. Zu Leibniz’ Idee der
Monade: „Eine Monade – der zentrale Begriff der Leibnizschen Welterklärung – ist eine einfa-che, nicht ausgedehnte und daher unteilbare Substanz, die äußeren mechanischen Einwirkungenunzugänglich ist. Das gesamte Universum bildet sich in den von den Monaden spontan gebilde-ten Wahrnehmungen (Perzeptionen) ab. Sie sind eine Art spirituelle Atome, ewig, unzerlegbar,einzigartig.“ – nach http://de.wikipedia.org/wiki/Leibniz
46
Die do-Notation ist in Haskell syntaktischer Zucker für al le Monaden,IO ist Instanz der Klasse Monad.
4.1 Die Maybe-MonadeEine weitere Haskel l Monade ist der Typkonstruktor Maybe.
data Maybe a = Nothing | Just a
Beispiel: Auswertung arithmetischer Ausdrücke9 :
data Expr = Expr :+ : Expr| Expr : / : Expr| Num Float
Problem ist hier die Vermeidung von Laufzeitfehlern (hier beim Teilendurch Null) , Ziel ist eine Funktion eval mit folgenden Eigenschaften:
e v a l (Num 3 :+ : Num 4 ) Just 7 . 0e v a l (Num 3 : / : (Num (−1) :+ : Num 1 ) ) Nothing
Dazu definieren wir nun die Funktion eval:
e v a l : : Expr −> Maybe Floate v a l (Num n) = Just neva l ( e1 :+ : e2 ) = case e v a l e1 ofNothing −> NothingJust n1 −> case e v a l e2 of
Nothing −> NothingJust n2 −> Just (n1 + n2)
e v a l ( e1 : / : e2 ) = case e v a l e1 ofNothing −> NothingJust n1 −> case e v a l e2 of
Nothing −> NothingJust 0 −> NothingJust n2 −> Just (n1 / n2 )
Dies geht einfacher und schöner mit Maybe als Monade, wobei einFehler „durchschlägt“ :
instance Monad Maybe whereNothing >>= k = NothingJust x >>= k = k x
9Operatoren als Konstruktoren sind möglich, müssen aber mit einem Doppelpunkt beginnen!
47
return = Justf a i l _ = Nothing
Nun kann man den Auswerter einfacher def inieren:
e v a l (Num n) = return neva l ( e1 :+ : e2 ) = do
n1 ← e v a l e1n2 ← e v a l e2return (n1 + n2)
e v a l ( e1 : / : e2 ) = don1 ← e v a l e1n2 ← e v a l e2i f (n2 == 0)
then Nothingelse return (n1 / n2 )
Die Monadengesetze können für Maybe einfach nachgewiesen werden(Übung).
4.2 Die ListenmonadeEine andere Sicht auf den Datentyp Maybe ist , dass Maybe eine Struktur(ein Container) ist , die null oder ein Element aufnehmen kann. Wennman dies auf Listen als Container veral lgemeinert, kann man auchfür den Listentyp eine Monadeninstanz definieren:
instance Monad [ ] wherereturn x = [ x ]
( x : xs ) >>= f = f x ++ ( xs >>= f )[ ] >>= f = [ ]
f a i l _ = [ ]
Dann ist
[ 1 , 2 , 3 ] >>= \x −> [ 4 , 5 ] >>= \y −> return ( x , y ) [ ( 1 , 4 ) , ( 1 , 5 ) , ( 2 , 4 ) , ( 2 , 5 ) , ( 3 , 4 ) , ( 3 , 5 ) ]
Dies ist übersetzt in die do-Notation:
do x ← [ 1 , 2 , 3 ]y ← [ 4 , 5 ]return ( x , y )
48
Diese darstel lung erinnert stark an die List Comprehensions, welchetatsächlich nur syntaktischen Zucker für die Listenmonade darstel len:
[ ( x , y ) | x ← [ 1 , 2 , 3 ] , y ← [ 4 , 5 ] ]
Weitere Eigenschaft der Listenmonade ist , dass die leere Liste die Nullder Struktur ist , da gi lt :
m >>= \x −> [ ] = [ ][ ] >>= \x −> m = [ ]
Desweiteren gibt es eine ausgezeichnete, assoziative Funktion (++)mit
(m ++ n) ++ o = m ++ (n ++ o )
Zusammengefasst ergibt sich die Klasse MonadPlus:
class Monad m => MonadPlus m wherezero : : m amplus : : m a −> m a −> m a
Für Listen ergibt sich dann:
instance MonadPlus [ ] wherezero = [ ][ ] ‘mplus ‘ y s = ys(x : xs ) ‘mplus ‘ y s = x : ( xs ‘mplus ‘ y s )
Viele Funktionen sind auf Monad oder MonadPlus definiert, die für kon-krete Instanzen verwendbar sind. Wir stel len hier nur die wichtigstenFunktionen vor.
sequence : : Monad m => [m a ] −> m [ a ]sequence = foldr mcons ( return [ ] )
where mcons p q = p >>= \x −>q >>= \ys −>return ( x : ys )
sequence_ : : Monad m => [m a ] −> m ( )sequence_ = foldr (>>) ( return ( ) )
Nun kann man beispielsweise benutzen:
sequence [ getLine , getLine ] >>= printsequence [ [ 1 , 2 ] , [ 3 , 4 ] ] [ [ 1 , 3 ] , [ 1 , 4 ] , [ 2 , 3 ] , [ 2 , 4 ] ]
49
Wir können nun map auf Monaden definieren:
mapM : : Monad m => ( a −> m b) −> [ a ] −> m [ b ]mapM f a s = sequence (map f a s )
mapM_ : : Monad m => ( a −> m b) −> [ a ] −> m ( )mapM_ f a = sequence_ (map f a s )
Nun verwenden wir:
mapM_ putStr [ "Hallo " , "Leute" ] ) Hal l o Leute
mapM ( \ s t r −> putStr ( s t r ++ ": " ) >>getLine )
[ "Vorname" , "Name" ] >>= print Vorname : Frank
Name: Huch[ "Frank" , "Huch" ]
Außerdem ist es für Monaden möglich ein ‘ ‘ i f -then’’ ohne ‘ ‘e lse’ ’ zudefinieren:
when : : Monad m => Bool −> m ( ) −> m ( )when b a = i f b then a else return ( )
main = dos t r ← getLinewhen ( s t r == "Frank" )
(putStrLn "Hi Frank, nice to meet you" )\ l d o t s
Eine weitere wichtige Funktion um z.B. auch die booleschen Bedin-gungen in den List Comprehensions zu übersetzen ist die monadischeBedingung:
guard : : MonadPlus m => Bool −> m ( )guard b = i f b then return ( ) else Zero
4.3 Implementierung der IO-MonadeFrage: Kann auch die IO-Monade in Haskell implementiert werden? DieAntwort ist ja! Die IO-Aktionen nehmen „die Welt“ und liefern dieveränderte Welt in Kombination mit dem Ergebnis zurück. Wenn wir
50
dies al lerdings selbst implementieren, reicht es aus, eine „Dummy-Welt“ zu verwenden, um die Arbeit der IO-Monade zu simulieren:
type IO a = World −> (a , World)type World = ( )
Wichtig ist aber, dass die Welt immer weitergereicht wird und zwi-schen durch keine neue Welt ‘ ‘erfunden’’ wird. Damit können wir dieMonaden-Funktionen definieren als:
return : : a −> IO areturn x w = (x , w)
(>>=) : : IO a −> (a −> IO b) −> IO b( a >>= k) w = case a w of
( r , w’ ) −> k r w’
„Die Welt“ wird also durchgeschl i f fen, so dass a ausgeführt werdenmuß, bevor k ausgeführt werden kann! Beachte bei diesem Ansatz:Die Welt darf nicht dupliziert werden!
Anderer Ansatz: Die Sprache Clean stel lt über das Uniqueness -Typsystemsicher, dass die Welt unique bleibt, also nicht dupliziert werden kannund gewährleistet so die Sequential is ierung. So ist es in Clean zwarmöglich die WElt in Teile zu zertei len, die dann unabhängig verwen-det werden können. Diese Teile können aber nicht wieder zusammen-gefügt werden.
Bei unserem Ansatz muß in den primitiven Funktionen die Umwand-lung in und von C-Datenstrukturen durchgeführt werden, bevor dieWelt zurückgegeben wird. Das Starten unserer IO-Monade geschiehtdurch Applikation auf ():
runIO : : IO( ) −> IntrunIO a = case a ( ) of
( ( ) , ( ) ) −> 42
Dabei ist der Rückgabetyp von runIO eigentl ich egal , er ist im Lauf-zeitsystem verborgen.
Beachte: Für unsere eigene IO-Monade können wir auch folgendeOperation definieren:
unsafePerformIO : : IO a −> aunsafePerformIO a = case a ( ) of
( r , _) −> r
51
Wir erf inden einfach eine neue Welt und verwenden diese zum Starteiner neuer IO-Aktionen an einer bel iebigen Programmstel le . DieseFunktion ist aber unsicher, da sie nicht referentiell transparent ist :
const : : Stringconst = unsafePerformIO getLine
Diese Konstante c kann bei jeder Programmausführung einen anderenWert haben! Auch Haskel l stel lt diese Funktion zur Verfügung. EineVerwendung in normalen Anwendungen ist aber wegen des Verlustesder referentiel len Transparenz unschön.
4.4 Erweiterung der IO-Monade um ZuständeDie hier vorgestel lten Erweiterungen gehen über den Haskell 98-Standardhinaus, s ind aber in den meisten Haskell-Implementierungen vorhanden.Im Modul IOExts/Data.IORef ist der abstrakter Datentyp data IORef adefiniert, der polymorphe Speicherzellen bietet. Sein Interface siehtwie folgt aus. :
−− gener ie r t neue IORefnewIORef : : a −> IO ( IORef a )−− l i e s t aktue l len WertreadIORef : : IORef a −> IO a−− schre ibt WertwriteIORef : : IORef a −> a −> IO ( )
Beachte: Die Aktionen werden in der IO-Monade sequential is iert, aberdie Werte in IORefs werden lazy berechnet!
Beispiel: Wir implementieren Graphen als Zeigerstrukturen. Zunächstdie Datenstruktur:
data Node = Node ColorRef [ NodeRef ]type NodeRef = IORef Nodetype ColorRef = IORef Bool
Nun schreiben wir eine Funktion, die den Graphen ausgehend voneinem Knoten färbt:
pa in t (Node co l o rRe f succRe f s ) = doc o l o r ← readIORef c o l o rRe fi f c o l o r then return ( )
else dowriteIORef c o l o rRe f True
52
mapM_ ( \nodeRef −> donode ← readIORef nodeRefpa in t node )
succRe f s
Beachte: Die Farbe wird destruktiv verändert, und jede Kante desGraphen wird nur einmal besucht. Dies ist ein Beispiel für eine direkteeff iz iente Implementietung von sequentiel len Algorithmen in einerfunktionalen Sprache!
Nachteil ist hier, dass das sequentiel le Programm in der funktionalenSchreibweise durch Seiteneffekte schwer verständlich wird. Oft istes besser, den Graphen als Datenstruktur zu kodieren und eine funk-tionale Implementierung des Algorithmus’ zu wählen (gi lt auch fürimperative Sprachen). Mit einer eleganten, funktionalen Repräsenta-tion von Graphen werden wir uns später nocheinmal beschäftigen.
4.5 ZustandsmonadenFrage: Sind globale Zustände nur in der IO-Monade möglich?
Beispiel: Nummeriere al le Blätter eines Baumes! Mit IORefs ist diesüber einen globalen Zustand möglich, rein funktional ist dies auchmöglich.
data Tree a = Node (Tree a ) (Tree a )| Lea f a
number : : Tree a −> Tree ( Int , a )number t r e e = f s t (number ’ t r e e 1 )
where number ’ : : Tree a −> Int −> (Tree ( Int , a ) , Int )number ’ ( Lea f x ) c = ( Lea f ( c , x ) , c+1)number ’ (Node t l t r ) c = (Node t l ’ t r ’ , c2 )
where ( t l ’ , c1 ) = number ’ t l c1( t r ’ , c2 ) = number ’ t r c2
Dieses Durchreichen des Zählers kann aber unübersichtl ich werden.Schöner ist es, diesen Zustand in einer Monade zu verstecken, die ihndurchschlei ft .
data Sta t e s a = ST ( s −> (a , s ) )
Dabei ist s der Typ des Zustands und a das Monadenergebnis, s -> (a, s) ist die Zustandstransformation. Nun können wir die Monaden-funktionen definieren:
53
instance Monad ( S ta t e s ) wherereturn : : a −> Sta t e s areturn r = ST (\ s −> ( r , s ) )
(>>=) : : S ta t e s a −> (a −> Sta t e s b) −> Sta t e s bm >>= f = ST (\ s1 −>
l et (ST s t r an s 1 ) = m( r1 , s 2 ) = s t r an s 1 s1(ST s t r an s 2 ) = f r1( r2 , s 3 ) = s t r an s 2 s2
in ( r2 , s 3 ) )
Außerdem:
runState : : s −> Sta t e s a −> arunState s t a r t (ST t r an s ) = f s t ( t r an s s t a r t )
update : : ( s −> s ) −> Sta t e s supdate f = ST (\ s −> ( s , f s ) )
g e t : : S t a t e s sg e t = update id
s e t : : s −> Sta t e s ss e t newState = update ( const newState )
Anwendung:
number : : Tree a −> Tree ( Int , a )number t r e e = runState 1 (number ’ t r e e )
where number ’ : : Tree a −> Sta t e Int (Tree ( Int , a ) )number ’ ( Lea f x ) = do
c ← update (+1)return ( Lea f ( c , x ) )
number ’ (Node t l t r ) = dot l ’ ← number ’ t lt r ’ ← number ’ t rreturn (Node t l ’ t r ’ )
Beachte aber: Die Reihenfolge ist hier (im Gegensatz zu oben!) wich-tig, da der Zustand durchgereicht wird (implizites (>>=)) .
54
5 DebuggingHaskell hat viele Vortei le (z.B. Laziness), die aber das Finden von Feh-lern erschweren. In imperativen Sprachen ist ein einfaches Debuggingmöglich mittels printf-Anweisungen; in Haskell ist dies möglich mitder unsicheren Funktion10
import IOExtst r a c e : : String −> a −> at r a c e s t r x = unsafePerformIO $ do
putStr s t rreturn x
Semantik ist die Identität, aber sobald die Berechnung von traceangestossen wird, wird der String als Seiteneffekt ausgegeben!
Beispiel:
> t r a c e "Hallo" (3+4)Ha l l o 7
> take 4 (map ( t r a c e "*" ) [ 1 . . ] )[∗1 ,∗2 ,∗3 ,∗4 ]
Oft ist man auch an Werten interessiert:
traceAndShow : : Show a => a −> atraceAndShow x = t r a c e (show x ) x
> take 4 (map traceAndShow [ 1 . . ] )[ 1 1 , 2 2 , 3 3 , 4 4 ]
Probleme dabei sind die Vermischung der Debug-Ausgabe mit derErgebnisausgabe (Lösung: Trace-Datei) und die Abhängigkeit derAusgabe von der Auswertungsreihenfolge (beachte Laziness!)
Beispiel:
x = l et l = map traceAndShow[ 1 . . ] in sum ( take 4 l )
y = l et l = map traceAndShow[ 1 . . ] in sum ( reverse ( take 4 l ) )
> x
10Dabei ist $ ein Operator, der die niedrigste Präzedenz hat und somit die Präzedenz derFunktionsanwendung umkehrt: f $ g x = f (g x)
55
1 2 3 4 10> y4 3 2 1 10
Weitere Probleme:
• Die Funktion traceAndShow zerstört zum Teil die Laziness:traceAndShow [1..] terminiert nicht, sobald es angestossen wird!Durch die dann strikte Auswertung entsteht zum einen ein Eff iz i -enzverlust, zum anderen setzen z.B. einige Parserkombinatorendie Laziness voraus.
• Man erhält keine Informationen über den Fortschritt der Aus-wertung.
• Es ist nur die Beobachtung von Werten der Klasse Show möglich,z.B. keine Funktionen!
5.1 Debuggen mit Observations (Hood)Idee ist hier, Werte wie mit traceAndShow zu beobachten, aber „_“ fürnicht benötigte (d.h. auch noch nicht ausgewertete) Teilstrukturenanzuzeigen. Dazu wird die Ausgabe bis zum Programmende (auchStrg-C) verzögert, ein zusätzl icher String-Parameter wird benutztzur Unterscheidung der Beobachtung.
Beispiel:
> : l Observe> take 2 ( obse rve "List" [ 1 . . ] )[ 1 , 2 ]>>>>>>> Observat ions <<<<<<List ( 1 : 2 : _)
> obse rve "List" [ 1 , 2 , 3 , 4 , 5 ] ! ! 34>>>>>>> Observat ions <<<<<<List (_ : _ : _ : 4 : _ : [ ] )
Verwendung: In einem Programm kann man mittels import Observedas Modul importieren und dann (Observe name e) wie traceAndShowbenutzen.
Alle Datentypen können observiert werden. Funktionen werden durchden „benutzten Teil“ des Funktionsgraphen dargestel lt .
56
Beispiel:
> map ( obse rve "inc" (+1)) [ 1 . . 3 ][ 2 , 3 , 4 ]>>> Observat ions <<<in c
{\ 3 −> 4 ,\ 2 −> 3 ,\ 1 −> 2}
Observations von Funktionen sind meist wichtiger als die der Daten-strukturen, da sie die Funktional ität wiederspiegeln. Wir betrachteneine Funktionsdefinit ion
f p11 . . p1n = e1...
f pm1 . . pmn = em
Um alle Aufrufe von f zu observieren, kann man f einfach wie folgtumdefinieren:
f = obse rve "f" f ’f ’ p11 . . p1n = e1
...f ’ pm1 . . pmn = em
So werden auch alle, also auch die rekursiven Aufrufe observiert.Besser ist daher oft :
f = obse rve "f" f ’f ’ p11 . . p1n = e1 [ f / f ’ ]
...f ’ pm1 . . pmn = em [ f / f ’ ]
Außerdem möglich sind:
• Observations von IO-/Zustandsmonaden
• Definit ion von zusammenhängenden Observations.
5.2 Implementierung von Observations für DatenZunächst: Definit ion einer Datenstruktur zur Repräsentation (tei l -)ausgewerteter Daten.
57
data EvalTree = Cons String [ EvalRef ]| Uneval −− entspr icht ’_’| Demand −− entspr icht ’ ! ’ ,
−− abgebrochene Berechnung
type EvalRef = IORef EvalTree
Beispiel für abgebrochene Berechnung:
> obse rve "List" [ 1 , f a c (−1 ) ][ 1 ,<< Ctr l−C >>>>> Observat ions <<<List ( 1 : ! :_)
Der Wert _:1:! wird repräsentiert durch
Cons ”(:)”
Cons ”(:)”
Uneval
Cons ”1” [] Demand
Zuerst implementieren wir die nötigen Funktionen für eine Daten-struktur:
data Tree = Empty | Node Tree Tree
oTree : : EvalRef −> Tree −> TreeoTree r e f Empty = unsavePerformIO $ do
mkEvalTreeCons "Empty" r e f 0return Empty
oTree r e f (Node t l t r ) = unsafePerformIO $ do[ t lR e f , t rRe f ] ← mkEvalTreeCons "Node" r e f 2return (Node ( oTree t lR e f t l )
( oTree t rRe f t r ) )
mkEvalTreeCons : : String −> IORef −> Int −> IO [ EvalRef ]mkEvalTreeCons consName r e f n = do
r e f s ← mapM ( const (newIORef Uneval ) ) [ 1 . . n ]wr i teIORef r e f (Cons consName r e f s )return r e f s
58
Es sol l nun wie folgt ausgewertet werden:
i sNode (Node _ _) = Truei sNode _ = False
> isNode ( obse rve "tree" (Node Empty Empty) ) i sNode ( oTree r e f (Node Empty Empty) )−− wobei re f auf folgendes ze igt :−− Cons "Node" [ ref1 Uneval , re f2 Uneval ]
Verallgemeinerung auf bel iebige Datentypen:
class Observe a whereobs : : a −> EvalRef −> a
instance Observe Tree whereobs = oTree
ob s e rv e r : : Observe a => a −> EvalRef −> aobs e rv e r x r e f = unsafePerformIO $ do
writeIORef r e f Demandreturn ( obs x r e f )
Zusätzl ich muss oTree in (*) oben durch observer ersetzt werden. Eswird Demand geschrieben, bevor die Berechnung gestartet wird. DieReihenfolge ist insgesamt wie folgt:
Uneval Anfrage des Werts−−−−−−−−−−→ Demand Kopfnormalform−−−−−−−−−→ Cons
Das Speichern al ler Observations geschieht in einer globalen Varia-blen:
g l o b a l : : IORef [ IO ( ) ]g l o b a l = unsafePerformIO (newIORef [ ] )
obse rve : : Observe a => String −> a −> aobse rve l a b e l x = unsafePerformIO $ do
r e f ← newIORef UnevalmodifyIORef g l o b a l
( pu tS t r l n ( l a b e l ++ "\n"++ ( replicate ( length l a b e l ’_’ ) )
>> showEvalTreeRef r e f >>= putStrLn ) : )return ( ob s e rv e r x r e f )
59
run : : IO ( ) −> IO ( )run i o = do
writeIORef g l o b a l [ ]i o −− a l t e rna t i v catch io (\_ −> printObs )
−− aus Modul Control . ExceptionprintObs
pr intObs = doputStrLn ">>> Observations <<<"obs ← readIORef g l o b a lsequence obs
Es fehlt nun nur noch die Definit ion der Funktion showEvalTreeRef,die eine benutzerfreundliche Ausgabe des EvalTrees ermöglicht:
showEvalTreeRef : : EvalTreeRef −> IO StringshowEvalTreeRef r = do
va l ← readIORef rshowEvalTRee va l
showEvalTree : : EvalTree −> IO StringshowEvalTree Uneval = return "_"showEvalTree Demand = return "!"showEvalTree (Cons cons [ ] ) = return consshowEvalTree (Cons cons r s ) = do
a r g s ← mapM showEvalTreeRef r sreturn ("(" ++ concat ( intersperse " " ( cons : a r g s ) )
++ ")" )
Speziel le Darstel lungen für Tupel oder Infix-Konstruktoren sind mög-l ich (Übung).Wie definiert man nun komfortabel Instanzen der Klasse Observe?Beispiel:
instance Observe a => Observe [ a ] whereobs (x : xs ) = o2 ( : ) "(:)" x xsobs [ ] = o0 [ ] "()"
Hierbei s ind folgende Funktionen definiert:
o0 : : a −> String −> EvalRef −> ao0 cons consName r e f = unsafePerformIO $ do
mkEvalTreeCons consName r e f 0
60
return cons
o2 : : (Observe a , Observe b) => ( a −> b −> c )−> String −> a −> b −> EvalRef −> c
o2 cons consName vA vB r e f = unsafePerformIO $ do[ aRef , bRef ] ← mkEvalTreeCons consName r e f 2return ( cons ( ob s e rv e r vA aRef )
( ob s e rv e r vB bRef ) )
5.3 Observieren von FunktionenEs wäre natürl ich auch schön, wenn man Funktionen oberservierenkönnen würde. Ähnlich wie bei ( lazy) Datenstrukturen kann einenFunktion durch ihren verwendeten Teil dargestel lt werden. Hierzuwird der Teil des Funktionsgraphen dargestel lt , der während desProgrammablaufs verwendet wurde:
> map ( obse rve "inc" (+1)) [ 3 , 4 , 5 ][ 4 , 5 , 6 ]>>> Observat ions <<<in c
{\3 −> 4, \4 −> 5, \5 −> 6}
Beachte: f ist hier eine Konstante, der zugehörige Observer wird nureinmal berechnet. Eine Umsetzung wie bei Konstruktoren würde zumÜberschreiben der letzten Funktionsanwendung führen!
Lösung: Behandle „->“ als dreistel l igen Konstruktor im EvalTree:
data EvalTree = Cons String [ EvalTreeRef ]| Uneval| Demand| Fun [ ( EvalTreeRef , EvalTreeRef ) ]
In obigem Beispiel ergibt sich also die Repräsentation11 :
Fun [ ( Cons "3" [ ] , Cons "4" [ ] ) ,(Cons "4" [ ] , Cons "5" [ ] ) ,(Cons "5" [ ] , Cons "6" [ ] ) ]
11Die Referenzen wurden hier zum besseren Verständnis weggelassen.
61
Diese Repräsentation ist nich ganz richtig, da wir am Ende der Listeimmer noch eine freie Posit ion, für mögliche weitere Anwendungenoffen lassen müssen.
instance (Observe a , Observe b) =>Observe ( a −> b) where
obs f r e f x = unsafePerformIO $ doapp lRe f s ← readIOFunRef r e fargRef ← newIORef Unevalr e sRe f ← newIORef Unevalwr iteIORef r (Fun ( ( argRef , r e sRe f ) : app lRe f s ) )return ( ob s e rv e r ( f ( ob s e rv e r x argRef ) ) r e sRe f )
wherereadIOFunRef : : EvalTreeRef
−> [ ( EvalTreeRef , EvalTreeRef ) ]readIOFunRef r e f = do
v ← readIORef r e fcase v of
Fun app lRe f s −> return app lRe f s_ −> do
writeIORef r e f (Fun [ ] )return [ ]
showEvalTree : : EvalTree −> IO StringshowEvalTree . . .showEvalTree (Fun app l s ) = do
r e sDSt r s ← mapM showApp ( reverse app l s )return ( concat ( intersperse "\n" r e s S t r s )where
showApp ( rArg , rRes ) = doarg ← showEvalTReeRef rArgsr e s ← showEvalTreeRef rResreturn ("{" ++ arg ++ "->" ++ r e s ++ "}" )
Die Ausgabe ist zunächst sehr einfach gehalten:
> obse rve "(+)" (+) 3 47>>> Observat ions <<<(+)−−−{3−>{4−>7}}
62
Sie kann aber mittels Pretty-Printing einfach optimiert werden.Statt der Verwendung einer Datenstruktur ist auch eine Observation-Datei möglich. Die ist le ider weniger dynamisch, und die Anzeigemuss aus einer Datei generiert werden, dies ist aber auch spätermöglich. Vortei l ist aber, dass der zeit l iche Ablauf erkennbar ist(was aufgrund der Laziness jedoch nicht unbedingt hi l freich ist) .
Der vorgestel lte Ansatz geht zurück auf Hood -- er ist in Hugs festeingebaut(, aber zum Teil fehlerhaft). Vorteile des Ansatzes von Hoodsind, dass er einfach zu benutzen ist, und sowohl die Laziness von Pro-grammen erhält als auch bei Spracherweiterungen (keine Programm-transformation) funktioniert. Ein Nachteil des Ansatzes ist aber, dasses nicht möglich ist , unabhängige Beobachtungen in Verbindungzusetzen, was mit komplexerten Ansätzen versucht wurde.
5.4 Andere AnsätzeAndere Ansätze arbeiten meist Trace-basiert, d.h. die Berechnungwird aufgezeichnet. Ein Trace wird später mit speziel len „Viewers“analysiert. Wichtigstes Tool ist Hat.
Beispiel: Fehlerhaftes Insertionsort:
sort : : Ord a => [ a ] −> [ a ]sort [ ] = [ ]sort ( x : xs ) = insert x ( sort xs )
insert : : Ord a => a −> [ a ] −> [ a ]insert x [ ] = [ x ]insert x (y : ys ) | x <= y = x : ys
| otherwise = x : insert x y s
main = putStrLn ( sort "program" )
> main"agop"
Eine Möglichkeit ist nun hat-observe zur Beobachtung von Top-level-Funktionen:
> hat−obse rve sortsort "program" = "agop"
...
63
sort "am" = "a"sort "m" = "m"sort "" = ""
> hat−obse rve insertinsert ’ a ’ "m" = "a" −− Fehler
Vorteile: Es sind hier keine Observe-Annotationen notwendig! Zusätz-l ich ist ein Pattern-Matching auf Argumente/Ergebnisse möglich!
Einige weitere Views sind:
• hat-trail mit einer Bottom-up-Sicht der Berechnung: Man kannerfragen, wo die Werte (insbesondere auch Fehler) herkommen:
agop \n← putStrLn "agop"← insert "p" "agor" | False −− Fehler
• hat-detect (deklaratives Debugging wie Freja, Budda)
sort [ 3 , 2 , 1 ]sort ( 3 : 2 : 1 : [ ] ) = 3 : 3 : 3 : [ ] ? ninsert 1 [ ] = 1 : [ ] ? yinsert 2 ( 1 : [ ] ) = 2 : 2 : [ ] ? ninsert 2 [ ] = 2 : [ ] ? y
Error l o c a t ed !Bug found : "insert 2 (1:[]) = 2:2:[]"
Nachteil: man verl iert oft den Überblick, und falsche Antworten(bei großen Datenstrukturen) führen zu falschen Fehlerposit io-nen. Manchmal ist dies wenig Zielgerichtet, oft kann man bessermit seiner Intuition arbeieten.
• hat-stack erlaubt die Anzeige des Laufzeitkel lers für eine strikteBerechnung zu einem Laufzeitfehler/Ctrl-C -- dies entsprichtder Java-Exception-Sicht.
• hat-explore (neu) ist ein Standarddebugger, der Innermost-Abstiegin bel iebigen Argumenten ermöglicht (zumindest so weit, wie dieBerechnung ausgeführt wurde). Zusätzl ich ist eine Verkleinerungdes möglichen Fehlercodes durch Slicing möglich.
64
In hat können alle Views paral le l verwendet werden.12
Vorteil dieses Ansatzes gegenüber Hood sind neben der Möglichkeitder Analyse der Beziehungen zwischen unterschiedl ichen Berechnun-gen auch die besseren Tools (gute Browser, die aber Übung benöti-gen).
Nachteile:
• Langsamere Programmausführung, manchmal langsamer View.
• Programmtransformationen auf Haskell 98 beschränkt.
• Aufwändigere Instal lation/Benutzung.
12Neue Views sind potentielle Themen für Diplomarbeiten!
65
6 ParserkombinatorenSei eine kontextfreie Grammatik G = (N,Σ, P, S) gegeben. Ein Programm,welches für al le w ∈ Σ∗ entscheidet, ob w ∈ L(G) ist , heißt Parser für G.Zusätzl ich sol lte ein Parser noch eine Ausgabe l iefern, die abstrakteInformationen über die Eingabe enthält (z.B. Linksableitung desWortes, einen abstrakten Syntaxbaum (AST) etc.) .
Zum Implementieren von Parsern gibt es unterschiedl iche Ansätze:
• Tools wie YACC (oder Happy für Haskell) generieren einen Parseraus einer Grammatik.
• rekursive Abstiegsparser wurden für PASCAL von Wirth umgesetzt,auch der XML-Parser im Projekt zur Vorlesung war ein solcherParser
• Parserkombinatoren erlauben es, den Parser gleichzeit ig mit derGrammatik aufzustel len
6.1 Kombinatorbibliothek für ParserAbstrakte Idee der Kombinatoren:
type Parse r s a = [ s ] −> [ ( a , [ s ] ) ]
Dabei ist [s] l inks die Eingabetokenfolge, a rechts das Ergebnis und[s] die Resttokenfolge.
Wir def inieren jetzt zunächst einige elementare Parser:
• pSucceed: Liefert einen Parser, der immer matcht, Eingabe wirdnicht verbraucht, v ist Ergebnis.
pSucceed : : a −> Parse r s apSucceed v t s = [ ( v , t s ) ]
• pFail: Ein Parser, der immer fehlschlägt:
pFa i l : : Par s e r s apFa i l t s = [ ]
• pPred: Liefert einen Parser, der aktuel les Token testet und es alsErgebnis l iefert:
66
pPred : : ( s −> Bool ) −> Parse r s spPred pred ( t : t s ) | pred t = [ ( t , t s ) ]
| otherwise = [ ]pPred pred [ ] = [ ]
• pSym: Test auf Symbol:
pSym : : Eq s => s −> Parse r s spSym t = pPred ( t ==)
Nun können wir Operatoren zum Kombinieren von (u.a. obigen) Par-sern definieren. Zunächst legen wir die Präzedenz der Operatorenfest (dies muß am Modulanfang geschehen!):
i n f i x l 3 <|>i n f i x l 4 <∗>
Nun definieren wir unsere ersten Kombinatoren :
• Der Operator (<|>) testet zuerst mit Parser p, wenn dieser fehl-schlägt, dann mit Parser q auf der gleichen Eingabe (das Parsengeschieht also lazy).
(<|>) : : Par se r s a −> Parse r s a −> Parse r s ap <|> q t s = p t s ++ q t s
• Der Operator (<*>) führt die Parser p und q hintereinander ausund wendet Ergebnis von p auf Ergebnis von q an.
(<∗>) : : Par se r s (b −> a ) −> Parse r s b−> Parse r s a
(p <∗> q) t s = [ (pv qv , t s 2 ) |(pv , t s 1 ) ← p t s ,( qv , t s 2 ) ← q t s 1 ]
Beispiel: Parser für die Sprache: {anbn | n ∈ N} mit Grammatik S →aSb | ε:
anbn : : Par se r Char Intanbn = pSucceed (\_ n _ −> n + 1)
<∗> pSym ’ a ’ <∗> anbn <∗> pSym ’b ’<|> pSucceed 0
67
Dieser Parser wertet dann folgendermaßen aus:
anbn "aabb" [ ( 2 , "" ) , ( 0 , "aabb" ) ]anbn "abb" [ ( 1 , "b" ) , ( 0 , "abb" ) ]anbn "aab" [ ( 0 , "aab" ) ]
Das korrekte Ergebnis ist dasjenige, wo die Eingabe vollständig ver-braucht ist . Beachte dabei: Kombinatoren liefern immer den längst-möglichen Parse zuerst.
Vorteile dieser Technik:
• Die Grammatik wird direkt als Programm geschrieben.
• Es ist eine sehr große Sprachklasse erkennbar -- LL(∞), d.h. dieSprachen, die mit bel iebig großem Look-Ahead entscheidbar sind.13
• Die Grammatik kann mit Hil fe von Haskell-Funktionen aufgebautwerden (z.B. foldr auf Parsern etc.) .
• Die Grammatik kann dynamisch (z.B. in Abhängigkeit vomParse-Ergebnis) aufgebaut werden.
• Es können neue (speziel le) Kombinatoren definiert werden.
Weitere Kombinatoren:
i n f i x l 4 <$>, <∗, ∗>i n f i x l 2 ‘ opt ‘
(<$>) : : (b −> a ) −> Parse r s b −> Parse r s af <$> p = pSucceed f <∗> p
(<∗) : : Par s e r s a −> Parse r s b −> Parse r s ap <∗ q = (\ x _ −> x) <$> p <∗> q
(∗>) : : Par se r s a −> Parse r s b −> Parse r s bp ∗> q = (\ _ x −> x) <$> p <∗> q
(<∗∗>) : : Par se r s a −> Parse r s ( a −> b) −> Parse r s bp <∗∗> q = (\ x f −> f x ) <$> p <∗> q
13Dabei gilt⋃K∈N LL(K) ( LL(∞).
68
pFoldr : : ( a −> b −> b) −> b −> Parse r s a−> Parse r s b
pFoldr op e p = op <$> p <∗> (pFoldr op e p) ‘ opt ‘ e
‘ opt ‘ : : Par se r s a −> a −> Parse r s ap ‘ opt ‘ v = p <|> pSucceed v
pL i s t : : Par s e r s a −> Parse r s [ a ]pL i s t p = pFoldr ( : ) [ ]
Jetzt lässt sich unser Beispiel wie folgt schreiben:
anbn = (+1) <$>(pSym ’ a ’ ∗> anbn <∗ pSym ’ b ’ )<|> pSucceed 0
Zusätzl ich ist es wünschenswert, kontext-sensitive Eigenschaften tes-ten zu können.Beispiel: Parsen von zwei gleichen Zeichen: L = {xx | x ∈ Σ}. Das Auf-zählen al ler Möglichkeiten ist hier nicht praktikabel , besser ist dieHinzunahme eines Tests:
check : : ( a −> Bool ) −> Parse r s a −> Parse r s acheck pred p t s = f i l t e r (pred . f s t ) (p t s )
doubleChar : : Par se r Char ChardoubleChar = f s t <$>
check (uncurry (==))( ( , ) <$> pAnySym <∗> pAnySym)
pAnySym : : Par se r Char CharpAnySym = pPred ( const True)
Alternativer Ansatz: Wir verwenden nun das Ergebnis eines Parsersals Parameter für den nächsten Parser:
(<->>) : : Par se r s a −> (a −> Parse r s b)−> Parse r s b
(p <->> q f ) t s = [ r e s | (pv , t s 1 ) ← p t sr e s ← q f pv t s 1 ]
doubleChar = pAnySym <->> pSym
Beispiel: Wir entwerfen wieder einen Parser für XML:
69
data XML = Tag String [XML]| Text String
pXMLs = ( : ) <$> pXML <∗> pXMLs<|> pSucceed [ ]
pOTag = pSym ’< ’ ∗> pIdent <∗ pSym ’> ’pOCTag = pSym ’< ’ ∗> pIdent <∗ pSym ’ / ’ <∗ pSym ’> ’pCTag tag = const ( ) <$> (pSym ’< ’ ∗>
pSym ’ / ’ ∗> pCheckIdent tag <∗ pSym ’> ’ )
Die Funktion pCTag sol l wie folgt verwendet werden können:
> pCTag "a" "</a>bc"[ ( ( ) , "bc" ) ]> pCTag "a" "</b>bc"[ ]
Dazu definieren wir:
pIdent = ( : ) <$> pPred (/= ’> ’ ) <∗> pIdent<|> pSucceed ""
pCheckIdent : : String −> Parse r Char ( )pCheckIdent "" = pSucceed ( )pCheckIdent ( c : c s ) = pSym c ∗> pCheckIdent c s
pText = ( : ) <$> pPred ( ’< ’ /=) <∗> pText<|> ( : [ ] ) <$> pPred ( ’< ’ /=)
pXML = f l i p Tag [ ] <$> pOCTag<|> pOTag
<->> \ tag −> (\ xmls −> Tag tag xmls )<$> pXMLs <∗ pCTag tag
<|> Text <$> pText
6.2 Monadische ParserkombinatorenBetrachtet man den Typ des Kombinators <-» , so fäl lt auf, dass ereinen ähnlichen Typ wie der monadische Bind-Operator hat.Frage: Lassen sich Parser als Monaden darstel len? Ja! Bisher war
70
Parser s a jedoch ein Typsynonym, für eine Instanz der Klasse Monadbenötigen wir einen Typkonstruktor:
data Parse r s a = Parse r ( [ s ] −> [ ( a , [ s ] ) ] )
instance Monad ( Par se r s ) where( Par se r p) >>= q f =
Parse r ( \ t s −> [ r e s | (pv , t s 1 ) ← p t s ,l et ( Par se r q ) = q f pv ,r e s ← q t s 1 ] )
return v = Parse r ( \ t s −> [ ( v , t s ) ] )
Nun definieren wir pPred für die neue Parser-Definit ion:
pPred : : ( s −> Bool ) −> Parse r s spPred pred = Parse r ( \ t s −>
case t s of t : t s ’ −> i f pred tthen [ ( t , t s ’ ) ]else [ ] )
Parser lassen sich aber sogar der Klasse MonadPlus zuordnen:
instance MonadPlus ( Par se r s ) where( Par se r p) ‘mplus ‘ ( Par se r q ) =
Parse r ( \ t s −> p t s ++ q t s )zero = Parse r ( \ t s −> [ ] )
runParser : : Par se r a −> [ s ] −> [ ( a , [ s ] ) ]runParser ( Par se r p) t s = p t s
Nun läßt sich beispielsweise der Parser für die Sprache anbn folgen-dermaßen definieren:
anbn = dopSym ’ a ’x ← anbnpSym ’b ’return ( x+1)
‘mplus ‘return 0
71
Diese Implementierung von Parsern ist in der Parsec-Bibl iothek14 vor-handen.Entsprechend einfach kann auch ein monadischer Parser für XMLdefiniert werden:
pXMLs : : Par se r Char [XML]pXMLs = do
xml ← pXMLxmls ← pXMLsreturn (xml : xmls )
<|> return [ ]
pXML : : Par se r Char XMLpXML = do
ocTag ← pOCTagreturn (Tag ocTag [ ] )
<|> dooTag ← pOTagxmls ← pXMLspCTag oTag−−cTag ← pCTag1 −− a l te rnat i ve Lösung−−guard (oTag==cTag) −− ohne Parametr is ierten Parserreturn (Tag oTag xmls )
<|> dot ← pTextreturn (Text t )
Hierbei verwenden wir wieder einen parametriesierten Parser, welchergezielt das passende schl ießende Tag parst.
6.3 Anmerkung zum ParsenEin Problem beim Top-Down-Parsen ist die Linksrekursion in Gramma-tiken wie zum Beispiel
S → S a | ε
Die folgende Lösung mit Parserkombinatoren würde nicht terminie-ren:
14 auf www.haskell.org unter „Libraries and Tools for Haskell“ ist Parsec zu finden, oderdirekt auf www.cs.uu.nl/ daan/parsec.html – Parsec ist standardmässig in den ghc-Librariesenthalten
72
s = (+1) <$> s <∗ pSym ’ a ’<|> pSucceed 0
Lösung: Übersetze die Linkrekursion in eine Rechtsrekursion:
S → aS | ε
Das allgemeine Vorgehen wird in der Compilerbau-Vorlesung behandelt !
Zur Optimierung bei Parsern der Operator <|> ist oft ineff iz ient, dadie Alternativen jeweils Speicher benötigen. Wir def inieren dahereine deterministische Variante <||>:
<||> : : Par se r s a −> Parse r s a −> Parse r s a(p <||> q ) t s = case p t s of [ ] −> q t s
r s −> r s
Analoges kann man für monadische Parserkombinatoren definieren.
Weitere Features der Parserkombinatoren in Kurzform:
• Exceptions zur Fehlerbehandlung
• Zustandsmonaden („globaler“ Zustand während des Parsens, Par-sec)
• Zeileninformationen zur Fehlergenerierung
• Korrektur der Eingabe (Swierstra, 1999)
73
7 RekursionIn Programmen haben wir unterschiedl iche Formen von Rekursionkennengelernt. Hierbei werden meist Datenstrukturen (Bäume) durch-laufen.
Beispiel: Selbst Rekursion über Int kann als Baumdurchlauf gesehenwerden -- man definiere etwa data Nat = 0 | Succ Nat.
7.1 Attributierte GrammatikenIdee: Wir notieren nicht-kontextfreie Eigenschaften als Attributierungeiner kontextfreien Grammatik.Definition: Sei G = (N,Σ, P, S) eine kontextfreie Grammatik (CFG).Dann kann G um eine Attributierung erweitert werden:
• ordne jedem Symbol X ∈ N ∪ Σ eine Menge von synthetisiertenAttributen Syn(X) und eine Menge von vererbten (inheriten) AttributenInh(X) zu (wobei Inh(a) = ∅ für al le a ∈ Σ gi lt)
• ordne jeder Regel X0 → X1 . . . Xn ∈ P eine Menge von semantischenRegeln (Attributgleichungen) der Form a.i = f(a1.j1, . . . , ak.jk) zu mitfolgenden Eigenschaften:
– a ∈ Syn(Xi) fal ls i = 0
– a ∈ Inh(Xi) fal ls i > 0
– für al le 1 ≤ i ≤ k gi lt :
∗ ai ∈ Syn(Xji) fal ls ji > 0
∗ ai ∈ Inh(Xji) fal ls ji = 0
Die Attributierung einer Regel enthält eine Attributgleichung für al lesynthetischen Attribute von X0 und für al le inheriten Attribute vonX1, . . . , Xn .
Idee: Synthetische Attribute werden hochgereicht, inherite Attributewerden runtergereicht, und f wird interpretiert, z .B. durch ein Haskell-Programm.
Beispiel: Sei eine Regel A→ B C ∈ P gegeben, Attribute seien Syn(A) =Syn(B) = Syn(C) = {s} und Inh(A) = Inh(B) = Inh(C) = {i}.Der Ableitungsbaum und die Attributte lassen sich dann folgender-maßen darstel len (wobei wir synthetische Attribute rechts, inheriteAttribute l inks neben die Knoten schreiben):
74
A
C B
i s
i s i s
Mögliche Regeln sind jetzt:
s.0 = f(s.1, s.2, i.0)
i.1 = g(s.1, s.2, i.0)
Beachte: Es ist kein Zykel innerhalb einer Regel def inierbar!
Beispiel: Beschreibe Binärzahlen in folgender Form (Knuth 1968):
G : N → L | L.LL→ B | LBB → 0 | 1
Zu der Zahl 1101.01 ∈ L(G) erhält man dann den Ableitungsbaum ausAbbildung 2.
1
0
•
N
L
B L
B
L
B
1
L
B
0
L
B
1
L
B
1
Abbildung 2: Ableitungsbaum für 1101.01 ∈ L(G)
75
Die Attributierung eines Ableitungsbaumes ist nun die Zuordnung vonAttributen zu den Knoten gemäß der Attributabhängigkeiten derRegeln; hier im Beispiel wollen wir den Dezimalwert einer Binärzahlzunächst rein synthetisch ermitteln. Dazu sei
Syn(N) = Syn(B) = {v}Syn(L) = {v, l}
Syn(0) = Syn(1) = Syn(.) = ∅
Nun können wir unsere Regeln attributieren:
B → 0 : v.0 = 0B → 1 : v.0 = 1L→ B : v.0 = v.1, l.0 = 1L→ LB : v.0 = v.2 + 2 · v.1, l.0 = l.1 + 1N → L : v.0 = v.1N → L.L : v.0 = v.1 + v.3
2l.3
Damit erigbt sich der attributierte Baum aus Abbildung 3.
1
0
•
N
L
B v = 1 L
B
v = 0 l = 1
v = 0
L
B
1
v = 13 l = 4
v = 1 L
B
0
v = 6 l = 3
v = 0 L
B
1
v = 3 l = 2
v = 1
L
B
1
v = 1 l = 1
v = 1
v = 0 l = 2
v = 13¼
Abbildung 3: attributierter Ableitungsbaum (1) für 1101.01 ∈ L(G)
ErweitertesBeispiel: Wir fügen zusätzl ich ein inherites Attribut für die Stel le des
76
Bits hinzu (d.h. Inh(L) = Inh(B) = {n}) :
B → 0 : v.0 = 0B → 1 : v.0 = 2n.0
L→ B : v.0 = v.1, l.0 = 1n.1 = n.0
L→ LB : v.0 = v.1 + v.2, l.0 = l.1 + 1n.1 = n.0 + 1, n.2 = n.0
N → L : v.0 = v.1, n.1 = 0N → L.L : v.0 = v.1 + v.3
n.1 = 0, n.3 = −l.3
Nun gibt es praktisch drei Durchläufe durch den Baum: Zunächstwird die Länge (l) von unten synthetisch berechnet, dann werden dieStel len (n) von oben nach unten weitergegeben, und schließl ich wirdder Wert (v) von unten nach oben berechnet.
1
0
•
N
L
B v = ¼ n = -2
L
B
v = 0 l = 1 n = -1
v = 0 n = -1
L
B
1
v = 13 l = 4 n = 0
v = 1 n = 0
L
B
0
v = 12 l = 3 n = 1
v = 0 n = 1
L
B
1
v = 12 l = 2 n = 2
v = 4 n = 2
L
B
1
v = 8 n = 3
v = ¼ l = 2 n = -2
v = 13¼
v = 8 l = 1 n = 3
Abbildung 4: attributierter Ableitungsbaum (2) für 1101.01 ∈ L(G)
Damit ergibt sich der Baum aus Abbildung 4.
Spezialfälle von Attributierungen sind:
• Bei einer reinen S-Attributierung benutzen wir nur synthetischeAttribute.
77
• Bei einer L-Attributierung gi lt für al le Attributgleichungen derForm a.i = f(a1.i1, . . . , ak.jn) mit i > 0, dass i > jk ist . D.h. zurDefinit ion eines inheriten Attributs dürfen nur synthetischeAttribute von weiter l inks und inherite Attribute der l inkenSeite verwendet werden:
A
C B
i s
i s i s
Dann ist die Attributauswertung mittels eines Links-Rechts-Durchlaufs (L-Durchlauf) möglich:
A
G
K H
I
B
E C
D
F
J
Damit wird jeder Knoten maximal zweimal besucht (währenddes Abstiegs und während der Rückgabe eines Wertes).
• Zyklische Attributierungen sind unerwünscht -- es ist dabei entscheid-bar, ob eine gegebene attributierte Grammatik zykelfrei ist . Wirgehen im Folgenden davon aus, dass eine zykelfreie attributierteGrammatik vorl iegt.
Beispiel: Betrachte wieder Binärzahlen, diesmal ohne Nachkomma-Antei l ; und berechne den Wert als Summe der Zweier-Potenzen --dafür sei Inh(L) = {p} ein Attribut für die jeweil ige Zweier-Potenz.
B → 0 : v.0 = 0B → 1 : v.0 = 1L→ B : v.0 = p.0 · v.1L→ LB : v.0 = v.1 + v.2 · p.0, p.1 = 2 · p.0N → L : v.0 = v.1, p.1 = 1
Als Beispielzahl betrachten wir 1101:
78
N
L
B
1
v = 13 p = 1
v = 1
L
B
0
v = 12 p = 2
v = 0
L
B
1
v = 12 p = 4
v = 1
L
B
1
v = 1
v = 13
v = 8 p = 8
Frage: Wie kann die Attributierung eines Baumes berechnet werden?Dazu wird der Ableitungsbaum als Haskell-Datenstruktur repräsentiert.Jedes Nichtterminalsymbol ist ein Datentyp, und die Regeln zu einemNichtterminalsymbol werden durch unterschiedl iche Konstruktorenunterschieden.
Um die Grammatik für Dezimalzahlen (mit Nachkomma-Antei l) um-zusetzen, benutze folgende Datenstruktur:
data N = N1 L | N2 L L −− Terminal ’ . ’ e n t f ä l l tdata L = L1 B | L2 L Bdata B = O | I
t e s tB ina ry = N2 (L2 (L2 (L2 (L1 I ) I ) O) I )(L2 (L1 O) I )
Der Übergang von Wort zur Datenstruktur kann mittels eines Par-ser erfolgen (z.B. mit Parserkombinatoren). Danach kann die S-Attributierung wie folgt als Haskell-Programm implementiert werden(wobei die Attribute jeweils die Ergebnisse des Baumdurchlaufs sind,ggf . als Tupel bei mehreren Attributen). Wir implementieren folgendeS-attributierte Grammatik von oben:
B → 0 : v.0 = 0B → 1 : v.0 = 1L→ B : v.0 = v.1, l.0 = 1L→ LB : v.0 = v.2 + 2 · v.1, l.0 = l.1 + 1N → L : v.0 = v.1N → L.L : v.0 = v.1 + v.3
2l.3
Diese wird umgesetzt in drei Funktionen:
79
be : : B −> Floatbe O = 0be I = 1
l e : : L −> (Float , Int )l e (L1 b) = l et v1 = be b
in ( v1 , 1 )l e (L2 l b) = l et ( v1 , l 1 ) = l e l
v2 = be bin ( 2∗v1+v2 , l 1+1)
ne : : N −> Floatne (N1 l ) = l et ( v1 , _) = l e l
in v1ne (N2 l l l r ) = l et ( v1 , _) = l e l l
( v3 , l 3 ) = l e l rin v1 + v3/2 ∗∗ l 3
Dann ist ne testBinary gleich 13.25.
Nun betrachten wir zusätzl ich auch inherite Attribute -- diese kön-nen als Parameter an die Funktionen für den Baumdurchlauf überge-ben werden! Betrachte dazu folgende L-attributierte Grammatik vonoben:
B → 0 : v.0 = 0B → 1 : v.0 = 1L→ B : v.0 = p.0 · v.1L→ LB : v.0 = v.1 + v.2 · p.0, p.1 = 2 · p.0N → L : v.0 = v.1, p.1 = 1
Diese wird wieder umgesetzt in drei Funktionen:
be : : B −> Intbe O = 0be I = 1
l e : : L −> Int −> Int −− p , vl e (L1 b) p0 = l et v1 = be b
in p0 ∗ v1l e (L2 l b) p0 = l et v1 = l e l ( 2 ∗ p0)
v2 = be bin v1+p0∗v2
80
ne : : N −> Intne (N1 l ) = l e l 1
Nun ergibt sich: ne (N1 (L2 (L2 (L2 (L1 I)O)I)I)) ergibt 11.
Betrachte als letztes folgende nicht L-attributierte Grammatik vonoben:
B → 0 : v.0 = 0B → 1 : v.0 = 2n.0
L→ B : v.0 = v.1, l.0 = 1n.1 = n.0
L→ LB : v.0 = v.1 + v.2, l.0 = l.1 + 1n.1 = n.0 + 1, n.2 = n.0
N → L : v.0 = v.1, n.1 = 0N → L.L : v.0 = v.1 + v.3
n.1 = 0, n.3 = −l.3Da diese nicht L-attributiert ist , ist zunächst die Auswertungsstrate-gie nicht klar. Wir schreiben dennoch nach obigem Schema folgendesProgramm:
be : : B −> Int −> Float −− n , vbe O n0 = 0be I n0 = 2∗∗n0
l e : : L −> Int −> (Float , Int ) −− n , (v , l )l e (L1 b) n0 = l et v1 = be b n0
in ( v1 , 1 )l e (L2 l b) n0 = l et ( v1 , l 1 ) = l e l (n0+1)
v2 = be n0in ( v1+v2 , l 1+1)
ne : : N −> Floatne (N1 l ) = l et ( v1 , _) = l e l 0
in v1ne (N2 l l x ) = l et ( v1 , l 1 ) = l e l 0
( v3 , l 3 ) = l e l x (− l 3 )in v1+v3
Beachte dabei le ider, dass in der vorletzten Zei le l3 auf beiden Sei-ten der Gleichung vorkommt: (v3, l3)= le lx (-l3). Dies wird alsovermutl ich nicht terminieren.
81
Überraschung ( !) : Es terminiert doch und funktioniert sogar sehr gut:Haskells Lazy Evaluation zerlegt die Rekursion über Tupel (die inle vorkommt) in mehrere Baumdurchläufe (jedoch ohne mehrfachesPattern Matching). Betrachte als entsprechendes Beispiel :
l oop = loop −− nicht−terminierend !snd ( l e (L2 (L1 I ) O) l oop ) 2
Dies funktioniert, da das zweite Argument von le für die Berechnungder Länge als Ergebnis nicht benötigt wird!
Allgemein gi lt : Für jede zykelfreie attributierte Grammatik stel lt obi-ge Implementierung einen eff iz ienten Attributauswerter dar. Für S-und L-Attributierung stel lt diese Technik auch eine Implementierungin strikten oder imperativen Sprachen dar.
7.2 Continuation Passing StyleIm folgenden wollen wir uns nocheinmal mit Abbrüchen währendeines Baumdurchlaufs beschäftigen. Betrachte hierzu wiederum:
data Expr = Expr :+ : Expr| Expr : / : Expr| Num Float
e v a l : : Expr −> Maybe Float −− mit Maybe−Monade
Hier wird nach Auftreten des Fehles (Nothing) der Baumdurchlaufnicht völl ig abgebrochen, sondern nur der Wert Nothing hochgereicht,
82
d.h. dies wird an jedem Knoten oberhalb der Fehlerstel le erneutgetestet (per Pattern Matching gegen Nothing) .
Idee: Wir möchten den Abbruch direkt an der Fehlerstel le durchfüh-ren. Stel le dazu die Berechnung (den Baumdurchlauf) als sogenanntenContinuation (Fortsetzung) dar. Dann kann im Fehlerfal l die Continuationverworfen werden und der Fehler direkt zurückgegeben werden.
Dieser Programmiersti l wird mit Continuation Passing Style (CPS) be-zeichnet.
Im Beispiel :
e v a l : : Expr −> (Float −> Maybe Float ) −> Maybe Floate v a l (Num x ) c = c xeva l ( e1 :+ : e2 ) c =
eva l e1 (\v1 −> eva l e2 (\v2 −> c (v1+v2 ) ) )e v a l ( e1 : / : e2 ) c =
eva l e1 (\v1 −> eva l e2 (\v2 −>i f v2 == 0 then Nothing
else c ( v1/v2 ) ) )
e v a l (Num 1 : / : (Num 1 :+ : Num (−1)) Just Nothing
Möglich wäre es auch, zuerst den Divisor zu berechnen:
e v a l ( e1 : / : e2 ) c =eva l e2 (\v2 −> i f v2 == 0
then Nothingelse e v a l e1 (\v1 −> c (v1/v2 ) ) )
Die Vorteile, die weitere Berechnung als Argument zu übergeben,sind:
• Die weitere Berechnung kann „modif iz iert“ werden, man kannalso den Kontext der Auswertung im Baum sehen und benutzen.
• Die Aufrufe beispielsweise von eval sind endrekursiv, dies ver-braucht keinen Platz auf dem Stack!
• Für Exceptions ist diese Berechnungsart vortei lhaft , da mehrfa-che Baumdurchläufe gespart werden (Coroutining).
Beispiel: S-Attributierung im CPS:
83
be : : B −> (Float −> a ) −> abe I c = c 1be O c = c 0
l e : : L −> (Float −> Float −> a ) −> al e (L1 b) c = be b (\v1 −> c v1 1 )l e (L2 l b) c = l e l ( \v1 l 1 −>
be b (\v2 −>c ( 2∗v1∗v2 ) ( l 1 +1)))
ne : : N −> (Float −> a ) −> ane (N1 l ) c = l e l ( \v1 −> c v1 )ne (N2 l 1 l 2 ) c = l e l 1 ( \v1 _ −>
l e l 2 ( \v3 l 3 −> c (v1 + v3/2∗∗ l 3 )
Dann wird ne testBinary id ausgewertet zu 13.25.Auch L-Attributierungen können einfach im CPS implementiert wer-den (Übung).
84
8 Algorithmen und DatenstrukturenBisher haben wir Listen und (unbalancierte) Suchbäume benutzt.Was sind geeignete Algorithmen und Datenstrukturen für häufigeFragestel lungen?
8.1 ListenListen eignen sich gut, wenn Daten gesammelt werden und anschlie-ßend jedes Element verwendet wird.
Beispiel: fac n = foldr (*)1 [0..n]
Problem: Konkatenation von Listen ist l inear im ersten Argument,deshalb ist es teuer, ein Element hinten anzuhängen: xs++[x].
Aber manchmal läßt sich dies nur schwer vermeiden (z.B. bei Rekur-sion):
data Tree = Node Tree Tree| Lea f Int
t r e eToL i s t : : Tree −> [ Int ]t r e eToL i s t ( Lea f n) = [ n ]t r e eToL i s t (Node t l t r ) =
t r e eToL i s t t l ++ t r e eToL i s t t r
Hier ist der Aufwand für treeToList t nicht l inear in der Anzahlder Blätter von t, da das erste Argument von ++ wächst. Bei einementarteten Baum ergibt sich eine quadratische Laufzeit in der Anzahlder Knoten bzw. Blätter.
Durch CPS läßt sich dies verbessern:
t r e eToL i s t : : Tree −> ( Int −> [ Int ] ) −> [ Int ]t r e eToL i s t ( Lea f n) c = c nt r e eToL i s t (Node t l t r ) c =
t r e eToL i s t t l ( : ( t r e eToL i s t t r c ) )
Dann kann man treeToList (:[]) auf einen Baum anwenden, dies istl inear in Anzahl der Knoten bzw. Blätter.
Dies ist aber schwer zu komponieren, wie das Beispiel Show zeigt:
show : : Show a => a −> String −− [ Char ]
85
Bei geschachtelten Typen müssen also unterschiedl iche Implementie-rungen von show (für die einzelnen Typen) komponiert werden, fürshow [Tree] also etwa showList, showInt und showTree.
Die Continuation müßte dann durch alle Listen gereicht werden:
class ShowC a where −− so nicht in Haskel l implementiertshowC : : a −> (String −> String ) −> String
instance showC Tree whereshowC ( Lea f n) c =
showC n (\ nStr −> c ("Leaf " ++ nStr ) )showC (Node t l t r ) c =
showC t l (++ (showC t r c ) )
Wir verwenden zwar (++), aber dies wird nur auf kurze Listen, wie"Leaf 42" angewendet.
instance ShowC a => showC [ a ] whereshowC [ ] c = c "[]"showC (x : xs ) c =
showC x (++ ’ : ’ : showC xs c )
Dann kann die Umwandlung der Datenstruktur in einen String inl inearer Zeit erfolgen.
Als bessere Alternative nutzen wir die Akkumulatortechnik:
t r e eToL i s t : : Tree −> [ Int ] −> [ Int ]t r e eToL i s t ( Lea f n) ns = n : nst r e eToL i s t (Node t l t r ) ns =
t r e eToL i s t t l ( TreeToList t r ns )
Dies ist scheinbar ähnlich wenig komposit ionel l wie mit CPS. Wirkönnen dies aber noch anders def inieren:
t r e eToL i s t ( Lea f n) = (n : )t r e eToL i s t (Node t l t r ) =
t r e eToL i s t t l . t r e eToL i s t t r
Dann entspricht die Funktionskomposit ion dem (++). Solche Listennennt man funktionale Listen. Um die Typsignatur anzupassen kannman definieren:
type I n tL i s tF = [ Int ] −> [ Int ]t r e eToL i s t : : Tree −> IntL i s tF
86
Wie funktioniert dies für Show?
type ShowS = String −> String
class Show a whereshows : : a −> ShowSshow : : a −> Stringshow x = shows x ""
instance Show Tree whereshows ( Lea f n) =
showString "Leaf" . shows n . showChar ’ , ’shows (Node t l t r ) =
showString "Node (" . shows t l .showString ") (" . shows t r . showChar ’ ) ’
Dabei s ind folgende Funktionen definiert:
showChar : : Char −> ShowSshowChar = ( : )
showString : : String −> ShowSshowString = (++)
Nun können wir ein al lgemeines shows auf Listen definieren:
instance Show a => Show [ a ] whereshows [ ] = showString "[]"shows ( x : xs ) = shows x . showChar ’ : ’ . shows xs
In Haskell ist diese Implementierung noch um einen zusätzl ichen Prä-zendenzparameter erweitert (z.B. um Klammern zu sparen), der abermeist 0 ist :
showsPrec : : Int −> a −> ShowSshows = showsPrec 0
Zudem ist showsPrec mittels show vordefiniert, es ist zudem auchshowList vordefiniert (z.B. als [1,2,3]) , kann aber überschrieben wer-den (z.B. für String).
8.2 Stacks (LIFO)Zur Implementierung von Stacks eignen sich Listen ausgezeichnet:
87
push = ( : )pop = t a i ltop = head
8.3 Queues (FIFO)Zunächst implementieren wir Queues mittels Listen:
type Queue a = [ a ]
emptyQueue : Queue aemptyQueue = [ ]
e n t e r : : a −> Queue a −> Queue aen t e r x q = q++[x ]
remove : : Queue a −> (Maybe a , Queue a )remove [ ] = (Nothing , [ ] )remove (x : xs ) = (Just x , xs )
Für kleine Queues ist dies gut. Für große Queues ergibt sich dasProblem, dass enter l inear in Queuegröße ist . Wie kann das verbessertwerden? Wir verwenden zwei Listen:
data Queue a = Queue [ a ] [ a ]
emptyQueue : Queue aemptyQueue = Queue [ ] [ ]
e n t e r : : a −> Queue a −> Queue aen t e r x (Queue out in ) = Queue out (x : in )
remove : : Queue a −> Maybe aremove (Queue [ ] [ ] ) = (Nothing , emptyQueue)remove (Queue (x : xs ) i ) = (Just x ,Queue xs i )remove (Queue [ ] i ) = l et out=reverse i in
(Just (head i ) , t a i l i )
Die Laufzeit ist nun in den meisten Fällen konstant, nur wenn dieout-Liste leer ist , dann ist die Operation l inear in Queuegröße. Aber:je größer die Queue ist , desto seltener muß reverse ausgeführt werden.Die amortiesierte Laufzeit ist konstant!
88
8.4 ArraysHaskell stel lt Arrays im Modul Array zur Verfügung, wobei als Array-Index jeder Typ dienen kann, der auf Int abgebildet werden kann(mittels der Typklasse Ix) . Das Interface sieht wie folgt aus:
data Array a b −− abstrakter Typarray : : Ix a => ( a , a ) −> [ ( a , b ) ] −> Array a blistArray : : Ix a => ( a , a ) −> [ b ] −> Array a b( ! ) : : Ix a => Array a b −> a −> b(// ) : : Ix a => Array a b −> [ ( a , b ) ] −> Array a b
Dies kann man dann wie folgt benutzen:
array ( 1 , 5 ) [ ( i , i +1) | i ← [ 1 . . 5 ] ] array ( 1 , 5 ) [ ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 4 ) , ( 4 , 5 ) , ( 5 , 6 ) ]
( listArray ( 1 , 5 ) [ 2 . . ] ) ! 2 3( listArray ( 1 , 5 ) [ 2 . . ] // [ ( 2 , 4 ) ] ) ! 2 4
Laufzeiten:
• array und listArray sind l inear in Arraygröße,
• (!) ist konstant,
• aber (//) ist l inear in Arraygröße, denn beim Ändern wird dasgesamte Array kopiert.
Dies ist gut für Datenstrukturen zum Nachschlagen, z.B. bei eineminitialen Konstruktionsalgorithmus mit späterem Lesen des Arraysohne Veränderung. Bei häufigen kleineren Änderungen ist diese Im-plementierung jedoch schlecht!
Beachte: Destruktive Updates sind in funktionalen Sprachen nichtmöglich, da das alte Array an anderer Stel le auch noch verwendetwerden kann (referentiel le Transparenz).
Es gibt aber auch alternative, referentiel l Transparente Implemen-tierungen, die eff iz iente punktweise Änderungen ermöglichen.
8.5 BraunbäumeEine alternative Implementierung für Arrays nutzt Braunbäume (hiernur mit Ints als Indizes, kann auch auf die Klasse Ix erweitert wer-den). Als Idee werden dabei die Indizes auf gerade und ungerade
89
aufgetei lt und beim Abstieg durch zwei dividiert (und eins abgezogenbei geraden Indizes). Die Null ist dabei die Wurzel .
data ArrayB b = Entry b (ArrayB b) (ArrayB b)
Folgende Graphik zeigt ein Anfangsstücke des Baumes beschri ftetmit den entsprechenden Indizes:
0
1 2
3 5
7 11 9 13
4 6
8 12 10 14
Die Selektion eines Wertes in diesem Baum können wir nun wie folgtdef inieren:
( ! ) : : ArrayB b −> Int −> b(Entry v a l a r ) ! n
| n == 0 = v| even n = ar ! (n ‘div ‘ 2 − 1 )| otherwise = a l ! (n ‘div ‘ 2 )
update : : ArrayB b −> Int −> b −> ArrayB bupdate (Entry v ’ a l a r ) n v
| n == 0 = Entry v a l a r| even n = Entry v ’ a l
( update a r (n ‘div ‘ 2 − 1 ) v )| otherwise = Entry v ’
( update a l (n ‘div ‘ 2 ) v ) a r
Dann sind sowohl (!) als auch update logarithmisch im Index.
Beachte: Bei update wird nicht die gesamte Datenstruktur kopiert,sondern nur der Pfad zum veränderten Knoten.
emptyArrayB : : ArrayB aemptyArrayB =
Entry ( error "access to non-instantiated index" )emptyArrayB emptyArrayB
90
ArrayBs können bel iebig groß sein, es gibt keine Dimensionsbeschrän-kung -- aber mit größeren Indizes wird die Datenstruktur auch ineff i -z ienter, beachte al lerdings log2 1.000.000 ≈ 20.
Bei vol lständiger Verwendung des Indexbereichs [0..n] ergibt sichein ausgegl ichener binärer Baum.
Ein Vorteil gegenüber destruktiven Updates ist , dass alte und neueVariante des Arrays verfügbar sind (mit logarithmischem Zeit- undPlatzverbrauch!), während man in imperativen Sprachen oft eineKopie eines Array anlegt (l inearer Zeit- und Platzverbrauch).
Das Füllen eines Arrays mit Werten aus einer Liste ist mit updatemöglich in O(n · log n) (fal ls n die Länge der Liste ist) , jedoch miteinem großen konstanten Antei l . Besser ist folgende Lösung:
sp l i t : : [ a ] −> ( [ a ] , [ a ] )sp l i t [ ] = ( [ ] , [ ] )sp l i t [ x ] = ( [ x ] , [ ] )sp l i t ( x : y : xys ) =
l et ( xs , y s ) = sp l i t xys in ( x : xs , y : y s )
l i s tToArrayB : : [ b ] −> ArrayB bl i stToArrayB [ ] = emptyArrayBl i stToArrayB (x : xs ) =
l et ( l s , r s ) = sp l i t xsin Entry x ( l i s tToArrayB l s ) ( l i s tToArrayB r s )
Die Laufzeit ist zwar noch in O(n · log n), aber sie hat bessere Kon-stanten. Eine l ineare Implementierung ist möglich, s iehe Okasaki1997.
8.6 Höhenbalancierte SuchbäumeNachteil von Arrays: Indizes müssen auf „kleine“ Ints abgebildet wer-den können. Was macht man aber bei komplizierten Schlüsseln? Oftist Hashing auf möglichst kleine Int-Werte relativ schwer (nicht al leWerte werden genutzt, Koll is ionen bei zu kleiner Hashtable).
Lösung sind Suchbäume. Dabei muß der Schlüssel aus der KlasseOrd sein (was meist „derived“ werden kann), dies gibt Probleme beiFunktionen oder Suchbäumen als Schlüssel (da Suchbäume schlechtvergleichbar sind, offene Frage: wie implementiert man am eff iz ien-testen Mengen von Mengen?).
91
Effizient ist dies für zufäl l ige Schlüsselvertei lung beim Einfügen (dieOperationen insert, delete und lookup in O(log n) mit n als Anzahl derEinträge), ineff iz ient im Worst-Case: O(n).
Verbesserung sind hier höhenbalancierte Bäume (z.B. Spreizbäume, Rot-Schwarz-Bäume oder AVL-Bäume), die beinahe balancierte Suchbäu-me durch Umbalancierungen gewährleisten -- die genauere gewährleis-tete Eigenschaft ist beispielsweise, dass die Höhe zweier benachbarterTeilbäume sich um maximal eins unterscheidet. Somit ist die Tiefedes Baumes maximal 2·blog(n+ 1)c und insert, delete und lookup laufenin O(log n).
Zur Implementierung siehe Informatik 2, in funktionalen Programmier-sprachen ist die Implementierung jedoch eleganter.
Vergleich mit Braunbäumen:
• insert, lookup und delete:
– höhenbalancierte Bäume: O(log n) mit n als Anzahl Einträge
– Braunbäume: O(logm) mit m Index
• Schlüssel :
– höhenbalancierte Bäume: Instanz der Klasse Ord
– Braunbäume: Int
• Baumtiefe:
– höhenbalancierte Bäume: 2 · blog2(n+ 1)c– Braunbäume: blog2(n+ 1)c mit n größtem Index
• Laziness:
– höhenbalancierte Bäume: wenig, da für Umbalancieren al-le Werte eingetragen sein müssen. In ghc sogar zusätzl icheStriktheitsannotation um Speicher für suspendierte Berech-nungen zu sparen.
– Braunbäume: nur benötigte Einträge werden gemacht
• unendliche Strukturen:
– höhenbalancierte Bäume: wegen Balancierung nicht möglich
– Braunbäume: möglich, z.B. emptyArrayB
92
8.7 TriesEin alternativer Ansatz zu höhenbalancierten Bäumen sind Tries, de-ren Idee von Thue (1912) zur Repräsentation von Strings stammt. InHaskell kann dies für bel iebige Datentypen als Schlüssel veral lgemei-nert werden.Beispiel: Sei die folgende String-Schlüssel-Menge gegeben:
[ "hat" , "hare" , "home" , "fun" , "funk" ]
Dann kann man dies in folgendem Baum repräsentieren:
Das Nachschlagen ist nun linear in Größe des Schlüssels (bei kon-stanter Alphabet-Größe). Als Datenstruktur für String-Tries nutzenwir:
type String = [Char ]data MapStr v = Tr i e (Maybe v ) (MapChar (MapStr v ) )type MapChar v = [ (Char , v ) ]
Für MapChar v verwenden wir eine Assoziationsl iste, es ginge aucheff iz ienter mit einem ArrayB über die ASCII-Werte der Zeichen.
lookupChar : : Char −> MapChar v −> Maybe vlookupChar = lookup
l ookupStr : : String −> MapStr v −> Maybe vlookupStr "" ( T r i eS t r tn t c ) = tnlookupStr ( c : c s ) ( T r i eS t r tn t c ) = do
t c s ← lookupChar c t clookupStr c s t c s
i n s e r tChar : : Char −> a −> MapChar a −> MapChar ain s e r tChar c v [ ] = [ ( c , v ) ]
93
i n s e r tChar c v ( ( c ’ , v ’ ) : cv s )| c == c ’ = ( c , v ) : cv s| otherwise = ( c ’ , v ’ ) : i n s e r tChar c v cvs
emptyTrieStr : : MapStr aemptyTrieStr = Tr i eS t r Nothing [ ]
Beachte: In MapChar werden keine Werte für v eingetragen, sondernkomplette Tries!
Laufzeit: lookup und insert sind l inear in Schlüsselgröße, delete istetwas schwieriger, da der Baum aufgeräumt werden muß, um keineleeren Äste zu hinterlassen.
d e l e t e S t r : : String −> MapStr a −> MapStr ad e l e t e S t r "" ( T r i eS t r _ t c ) = Tr i eS t r Nothing t cd e l e t e S t r ( c : c s ) ( T r i eS t r tn t c ) =
case lookup c t c ofNothing −> Tr i eS t r tn t cJust t c s −>
case d e l e t e S t r c s t c s ofTr i eS t r Nothing [ ] −>
Tr i eS t r tn ( f i l t e r ((/=c ) . f s t ) t c )t c s ’ −> Tr i eS t r tn ( in s e r tChar c t c s ’ t c )
i n s e r t S t r : : String −> a −> MapStr a −> MapStr ai n s e r t S t r "" v ( Tr i eS t r _ t c ) =
Tr i eS t r (Just v ) t ci n s e r t S t r ( c : c s ) v ( Tr i eS t r tn t c ) = Tr i eS t r tn
( case lookup c t c ofNothing −> ( c , i n s e r t S t r c s v emptyTrieStr ) : t cJust t c s −> inse r tChar c ( i n s e r t S t r c s v t c s ) t c
Beachte: Wenn filter die leere Liste l iefert und tn gleich Nothing,dann wird der Knoten im übergeordneten deleteStr gelöscht.
Beachte: Bei der Trie-Implementierung für String-Schlüssel habenwir eine Trie-Implementierung für Char-Schlüssel verwendet. MapCharist als Assoziationsl iste dargestel lt , also [(Char, a)]. Im Fall , dasskeine Verlängerung eines Wortes im Trie ist , haben wir hier [], wasanalog zu Nothing in dem ersten Argument von TrieStr ist .15
15Dieser Teil ist – wie auch vorher schon einige Teile – aus einer Mitschrift von Björn Duderstadt,vielen Dank!
94
Erweiterung: Im nächsten Schritt verwenden wir Binärzahlen alsSchlüssel :
data No = Empty | I No | O No
Nun können wir zunächst Zahlen in unsere Binärdarstel lung umwan-deln:
intToNo : : Int −> NointToNo 0 = EmptyintToNo n =
( i f even n then O else I ) ( intToNo (n ‘div ‘ 2 ) )
map intToNo [ 0 . . 4 ] [Empty, I Empty, O ( I Empty) ,
I ( I Empty) , O(O( I Empty) ) ]
Wie kann nun der zugehörige Trie aussehen?
Empty I O
Empty EmptyI O I O
Als Datenstruktur für einen Trie verwenden wir nun:
data MapNo a = TrieNo (Maybe a ) −− fo r Empty(Maybe (MapNo a ) ) −− fo r I(Maybe (MapNo a ) ) −− fo r O
emptyTrieNo : : MapNo aemptyTrieNo = TrieNo Nothing Nothing Nothing
Nun können wir einfügen, auslesen und löschen:
lookupNo : : No −> MapNo a −> Maybe alookupNo Empty (TrieNo t e t i t o ) = t elookupNo ( I n) (TrieNo t e t i t o ) =
case t i ofNothing −> NothingJust t i ’ −> lookupNo n t i ’
95
i n s e r tNo : : No −> a −> MapNo a −> MapNo ain s e r tNo Empty v (TrieNo _ t i t o ) =
TrieNo (Just v ) t i t oin s e r tNo ( I n) v (TrieNo t e Nothing t o ) =
TrieNo t e (Just ( i n s e r tNo n v emptyTrieNo ) )in s e r tNo ( I n) v (TrieNo t e Nothing t o ) =
TrieNo t e (Just ( i n s e r tNo n v t i ) ) t o
de le teNo : : No −> MapNo a −> MapNo ade le teNo Empty (TrieNo _ t i t o ) =
TrieNo Nothing t i t ode le teNo ( I n) t@( Tr i e t e Nothing t o ) = tde le teNo ( I n) (TrieNo t e (Just t i ) t o ) =
case de le teNo n t i ofTrieNo Nothing Nothing Nothing −>
TrieNo t e Nothing t ot1 ’ −> TrieNo t e (Just t i ’ ) t o
de le teNo (O n) −− analog
Beachte: deleteNo räumt den Baum auf, so dass ein leerer TrieNo immergleich EmptyTrieNo ist .
Allgemein: Die Auftei lung des Tries hat starke Ähnlichkeit mit Braun-bäumen. Unter Berücksichtigung von Empty und Vernachlässigungredundanter Binärzahlen (z.B. 001 statt 1) sind die Zahlen gleicheinsortiert. Damit können Tries auch als Veral lgemeinerung vonBrauntrees gesehen werden.
Als weitere Veral lgemeinerung können wir nun binäre Bäume alsSchlüssel zulassen:
data Bin = Lea f String| Node Bin Bin
data MapBin a =TrieBin (Maybe (MapStr a ) ) −− für "Leaf"
(Maybe (MapBin (MapBin a ) ) ) −− für "Node" ,−− MapBin für Unterscheidung−− l i n k s /rechts in "Bin Bin"
emptyTrieBin : : MapBin aemptyTrieBin = TrieBin Nothing Nothing
96
Allgemein: Ein Trie für einen monomorphen Typen τ hat einen Kon-struktor Trieτ und für jeden Konstruktor c von τ hat Trieτ ein Argu-ment, welches sukzessive über den Argumenten von c entsprechendeTries verzweigt. Da zu einem Schlüssel möglicherweise auch keinEintrag im Trie steht, wird jedes Argument von Trieτ mit Maybegekapselt .
8.7.1 Nested Datatypes
Beachte: MapBin wird auf (MapBin a) „appliziert“ . Dies ist ein sogenann-ter Nested Datatype : Ein Typkonstruktor wird auf der rechten Seite aufeinen „neuen“ Typen angewandt:
data T a = . . . T (X a )
Die Implementierung sieht nun folgendermaßen aus:
lookupBin : : Bin −> MapBin a −> Maybe alookupBin ( Lea f s ) ( Tr ieBin Nothing _) = NothinglookupBin ( Lea f s ) ( Tr ieBin (Just t l ) _ ) =
lookupStr s t llookupBin (Node l r ) ( Tr ieBin _ Nothing ) = NothinglookupBin (Node l r ) ( Tr ieBin _ (Just tn ) ) = do
tn ’← lookupBin l tnlookupBin r tn ’
i n s e r tB i n : : Bin −> a −> MapBin a −> MapBin ai n s e r tB i n ( Lea f s ) v (Tr ieBin Nothing tn ) =
TrieBin (Just ( i n s e r t S t r s emptyTrieStr ) ) tni n s e r tB i n ( Lea f s ) v (Tr ieBin (Just t l ) tn ) =
TrieBin (Just ( i n s e r t S t r s t l ) ) tni n s e r tB i n (Node l r ) v (Tr ieBin t l Nothing ) =
TrieBin t l (Just ( i n s e r tB i n l( i n s e r tB i n r v emptyTrieBin )emptyTrieBin ) )
i n s e r tB i n (Node l r ) v (Tr ieBin t l (Just tn ) ) =TrieBin t l (Just $
case lookupBin l tn ofNothing −>
in s e r tB i n l( i n s e r tB i n r v emptyTrieBin ) tn
Just tn ’ −>in s e r tB i n l ( i n s e r tB i n r v tn ’ ) tn )
97
de l e t eB in : : Bin −> MapBin a −> MapBin ade l e t eB in ( Lea f s ) t@(TrieBin Nothing tn ) = tde l e t eB in ( Lea f s ) ( Tr ieBin (Just t l ) tn ) =
case d e l e t e S t r s t l ofTr i eS t r Nothing [ ] −> TrieBin Nothing tnt t ’ −> TrieBin (Just t l ’ ) tn
de l e t eB in (Node _ _) t@(TrieBin t l Nothing ) = tde l e t eB in (Node l r ) ( Tr ieBin t l (Just tn ) ) =
TrieBin t l $case lookupBin l tn ofNothing −> Just tnJust tn1 −>
case de l e t eB in r tn1 ofTreeBin Nothing Nothing −>
case de l e t eB in l tn ofTrieBin Nothing Nothing −> Nothingtn2 −> Just tn2
tn2 −> Just ( i n s e r tB i n l tn2 tn )
Beachte: deleteBin schneidet al le leeren Teile aus dem Trie heraus,so dass diese Garbage werden können. Der leere Trie wird immer alsTrieBin Nothing Nothing dargestel lt , und nicht z.B. als
Tr ieBin Nothing (Just ( Tr ieBin Nothing Nothing ) )
Laufzeiten: lookup, insert, delete erfolgen l inear in der Schlüsselgrö-ße. Besser geht es aus Komplexitätstheoretischer Sicht nicht. Triesverhalten sich auch aus Laziness-Sicht gutmütig, da nur benötigteTeile berechnet werden müssen.
Bei der Programmierung mit Nested Datatypes wird meist polymorpheRekursion benötigt, d.h. eine Funktion ruft (ggf . indirekt) sich selbstfür einen anderen Typen auf: In lookupBin für MapBin a wird lookupBinzuerst auf MapBin a angewendet.
Problem: Bei polymorpher Rekursion ist Typinferenz im allgemeinenunentscheidbar. Deshalb erlaubt Haskell 98 polymorphe Rekursion nurbei gegebener Typsignatur der Funktion. Es wird also nur eine Typ-prüfung durchgeführt -- diese ist entscheidbar. Der ghc versucht einenTyp zu inferieren, was meist gel ingt, aber nach einigen Iterationenauch fehlschlagen kann.
98
9 GraphenMathematisch sind Graphen definiert als :
G =< V,E > mit V Menge von KnotenE ⊆ V × V Menge von Kanten
Zusätzl ich fügt man häufig noch Beschriftungen zu Knoten und Kan-ten hinzu.
Wie können Graphen in Haskel l implementiert werden:
type Graph a b = (Nodes a , Edges b)type NodeId = Inttype Nodes a = [ ( NodeId , a ) ]type Edges b = [ ( NodeId , b , NodeId ) ]
Zunächst Überlegungen zur Schnittstel le , Eff iz ienzbetrachtungen derImplementierung später.
Viele (imperative) Graphalgorithmen arbeiten mit Markierungen.Ähnliches wäre auch in unserem Framework über Beschri ftungenmöglich, z.B. durch Erweiterung um eine boolesche Komponente.
Allerdings entspricht dies nicht dem üblichen induktiven Program-mieren in funktionalen Sprachen. Schöner wäre eine induktive Dar-stel lung der Graphen, wie:
• leerer Graph (Konstruktor EmptyGraph)
• Graph, der aus einem Knoten (mit seinem Kontext, den ein- undausgehenden Kanten) und einem Restgraph besteht (Konstruktor&v , wobei v die zugehörige Knotennummer ist)
type Context a b = ( [ ( NodeId , b ) ] , a , [ ( NodeId , b ) ] )
d f s : : [ NodeId ] −> Graph a b −> [NodeId ]d f s [ ] _ = [ ]d f s ( v : vs ) ( c &v g ) = v : d f s ( s u c c s c ++ vs ) gd f s (_: vs ) g = d f s vs g
Problematisch ist natürl ich das doppelte Vorkommen von v in denPattern (Nicht-Linearität) und der parametris ierte Konstruktor &.
Als Lösung kann dieses Matching mit Hil fe einer Funktion umgesetztwerden:
99
match : : NodeId −> Graph a b−> Maybe (Context a b , −− Kontext
Graph a b) −− Restgraph
Dann:
d f s : : [ NodeId ] −> Graph a b −> [NodeId ]d f s [ ] _ = [ ]d f s ( v : vs ) g =
case match v g ofNothing −> d f s vs gJust ( (_,_, su c c s ) , g ’ ) −>
v : d f s (map fst s u c c s ++ vs ) g ’
Wie kann match definiert werden? Suchen des Knotens und Aufsam-meln der Vorgänger- und Nachfolgerknoten.
match n ( nodes , edges ) = doa ← lookup n nodesreturn ( ( [ (m, b) | (m, b , n ’ ) ← edges , n’==n ] ,
a ,[ (m, b) | (n ’ , b ,m) ← edges , n’==n ] ) ,
( f i l t e r ((/=n) . f s t ) nodes ,[ (m, b ,m’ ) | (m, b ,m’ ) ← edges , m/=n ,m’/=n ] ) )
Konstruktion von Graphen:
addNode : : NodeId −> a −> Graph a b −> Graph a baddNode n a ( nodes , edges ) =maybe ( ( n , a ) : nodes , edges )
( error ("Node " ++ show n ++ "already in graph" ) )( lookup n nodes )
addEdge : : NodeId −> b −> NodeId −> Graph a b−> Graph a b
addEdge n b m (nodes , edges ) =maybe ( errNode n)
(maybe ( errNode n)( const ( nodes , ( n , b ,m) : edges ) )( lookup m nodes ) )
( lookup m nodes )whereerrNode n = error ("Node " ++ show n ++ " not in graph" )
100
addNodeWithSuccs : : NodeId −> a −> [ ( NodeId , b ) ]−> Graph a b −> Graph a b
addNodeWithSuccs . . .
Beachte: Knoten / Kanten können mittels match in anderer Reihenfolgeentnommen werden als sie hinzugefügt wurden.
Bem.: Hier sol l es mehr auf die Idee der Schnittstel le ankommen.Repräsentation des Graphen so ineff iz ient.
Eff iz ientere Darstel lung: Braunbäume der höhenbalancierten Such-bäume, die NodeIds auf Vorgänger-/Nachfolgerknoten abbilden. Hier-durch Impementierung von match komplizierter, aber eff iz ient möglich.Dann Knoten/Kanten hinzufügen und matchen logarithmisch in derGraphgröße.
Weitere Verbesserungsmöglichkeit : Die NodeIds sind nicht abstrakt,s ie müssen durch die Anwendung generiert werden. Verbesserungdurch monadische Erweiterung der Graphen um NodeId-Zustand, dann:
. . . = don ← addNode "a"m ← addNode "b"addEdge n 42 m
101
