HaskellHaskell

Eine rein funktionale SpracheEine rein funktionale Sprache

Ein Rat vorwegEin Rat vorweg

An die anwesenden C-Programmierer:

Vergesst am besten alles, was Ihr bisher über Programmierung und Programmiersprachen gelernt habt !!!

We now proudly We now proudly present:present:

ÜbersichtÜbersicht EinführungEinführung

Einordnen von Haskell in das Sprachen-SpektrumEinordnen von Haskell in das Sprachen-Spektrum imperativ vs. deklarativimperativ vs. deklarativ

Beispiel eines imperativen Programms und eines deklarativen Beispiel eines imperativen Programms und eines deklarativen ProgrammsProgramms

Entwicklung der deklarativen Sprachen, insb. HaskellEntwicklung der deklarativen Sprachen, insb. Haskell -Kalkül, Grundlage von Haskell-Kalkül, Grundlage von Haskell

Einführung, Auswertung, Erweiterung, Beispiele, …Einführung, Auswertung, Erweiterung, Beispiele, … Evolution der ProgrammiersprachenEvolution der Programmiersprachen

Grundkonzepte funktionaler Sprachen, insb. HaskellGrundkonzepte funktionaler Sprachen, insb. Haskell TypenTypen

Beispielprogramm: KryptographieBeispielprogramm: Kryptographie AuswertungAuswertung

Beispielauswertung (Tafel)Beispielauswertung (Tafel) Lazy EvaluationLazy Evaluation

Rekursive Funktionen (mit einfachen Datenstrukturen)Rekursive Funktionen (mit einfachen Datenstrukturen)

Das Sprachen-SpektrumDas Sprachen-SpektrumProgrammiersprachen

imperative Programmiersprachen

deklarative Programmiersprachen

konventionelle Sprachen

objekt-orientierteSprachen

funktionale Sprachen

LogikSprachen

funktional-logischeSprachen

Fortran

Pascal

Modula

C

…

SmallTalk

Eifel

C++

Java

…

Haskell

LISP

…

Prolog

…

Ideal

Babel

Curry

…

imperativ vs. deklarativimperativ vs. deklarativ

Merkmale Merkmale imperativer imperativer SprachenSprachen

1.1. Die Grundidee ist die des Die Grundidee ist die des „„von Neumannvon Neumann“ bzw. des “ bzw. des „„stored programstored program“ Rechners.“ Rechners.Hier werden Programme als Hier werden Programme als festefeste Folge von Befehlen Folge von Befehlen nacheinander abgearbeitet.nacheinander abgearbeitet.

2.2. Ein Programm beschreibt, Ein Programm beschreibt, wie etwas berechnet wird. wie etwas berechnet wird. Dies geschieht als Dies geschieht als Abfolge Abfolge lokaler lokaler SpeichertransformationenSpeichertransformationen (Wertzuweisungen).(Wertzuweisungen).

3.3. Die Kontrollstruktur ist die Die Kontrollstruktur ist die IterationIteration (Schleife). (Schleife).

Merkmaler Merkmaler deklarativer deklarativer

SprachenSprachen

1.1. Die Grundidee ist das Die Grundidee ist das --Kalkül von Kalkül von ChurchChurch, eine , eine mathematische Theorie.mathematische Theorie.

2.2. Jede Berechnung ist das Jede Berechnung ist das Ergebnis einer Funktion Ergebnis einer Funktion und wird durch einfache und wird durch einfache Ersetzung von Ausdrücken Ersetzung von Ausdrücken errechnet (Reduktion).errechnet (Reduktion). vgl. Auswertung vgl. Auswertung

3.3. Die Hauptkontrollstruktur Die Hauptkontrollstruktur ist die ist die Rekursion.Rekursion.

WAS WAS anstelle anstelle vonvon WIE WIE

Somit lässt sich der Hauptunterschied zusammenfassen

als Motto:

Der Programmierer soll nur noch angeben, was er programmieren möchte, er soll nicht mehr damit belastet werden, wie etwas genau programmiert wird.

(Aber trotzdem muss er in der Lage sein dem Computer mitzuteilen, was er haben möchte.)

Der QuicksortalgorithmusDer QuicksortalgorithmusVergleich zwischen imperativer und funktionaler Vergleich zwischen imperativer und funktionaler

ProgrammierungProgrammierung

{ public void sort(Object [] rgo) { sort(rgo, 0, rgo.length - 1); }

private void sort(Object [] rgo, int nLow0, int nHigh0) { int nLow = nLow0; int nHigh = nHigh0; Object oMid; if (nHigh0 > nLow0) { oMid = rgo[ (nLow0 + nHigh0) / 2 ]; while(nLow <= nHigh) { while((nLow < nHigh0) && lessThan(rgo[nLow], oMid)) ++nLow;

while((nLow0 < nHigh) && lessThan(oMid, rgo[nHigh])) --nHigh;

if(nLow <= nHigh) { swap(rgo, nLow++, nHigh--); }} }} if(nLow0 < nHigh) sort(rgo, nLow0, nHigh); if(nLow < nHigh0) sort(rgo, nLow, nHigh0); } }

private void swap(Object [] rgo, int i, int j) { Object o; o = rgo[i]; rgo[i] = rgo[j]; rgo[j] = o; }

protected boolean lessThan(Object oFirst, Object oSecond) { return oFirst.hashCode() < oSecond.hashCode(); }}

Implementierung in Java:

Implementierung in Haskell:

quicksort :: Ord a => [a] -> [a]quicksort [] = []quicksort (pivot:xs) = quicksort [y | y <- xs, y<=pivot] ++ [pivot] ++ quicksort [y | y <- xs, y>pivot]

JahreszaJahreszahlhl

TheorieTheorie / / SpracheSprache EntwicklerEntwickler

19321932 -Kalkül (siehe weiter hinten)-Kalkül (siehe weiter hinten)

Ursprung und gemeinsamer Kern aller funktionalen Ursprung und gemeinsamer Kern aller funktionalen Sprachen. Churchs Intention bei der Entwicklung des Sprachen. Churchs Intention bei der Entwicklung des --Kalküls war eine „Kalküls war eine „Formalisierung des Formalisierung des Berechenbarkeitsbegriffs auf der Basis von FunktionenBerechenbarkeitsbegriffs auf der Basis von Funktionen“ “ „„Churchsche TheseChurchsche These“.“.Diese These wurde durch die äquivalente Turing-Diese These wurde durch die äquivalente Turing-Berechenbarkeit untermauert.Berechenbarkeit untermauert.

Church, KleeneChurch, Kleene

19601960 LISPLISP (List Prozessing) (List Prozessing)

Lisp war die erste funktionale Sprache, die von den Lisp war die erste funktionale Sprache, die von den Prinzipien der damaligen durch Fortran geprägten Prinzipien der damaligen durch Fortran geprägten Programmierung abwich. Wesentliche Neuheiten von LISP Programmierung abwich. Wesentliche Neuheiten von LISP waren: waren: bedingte Ausdrückebedingte Ausdrücke, Verwendung von , Verwendung von Listen als Listen als BasisstrukturBasisstruktur, Heapverwaltung mit , Heapverwaltung mit Garbage CollectionGarbage Collection

John McCarthyJohn McCarthy

19751975 MLML (Meta Language) (Meta Language)

Das Bedeutendste in ML ist das mächtige Das Bedeutendste in ML ist das mächtige polymorphe polymorphe TypenkonzeptTypenkonzept, das von den meisten modernen funktionalen , das von den meisten modernen funktionalen Sprachen adaptiert wurde. Sprachen adaptiert wurde. (vgl Abschnitt Typen)(vgl Abschnitt Typen)

Milner, Gordon, Milner, Gordon, University of University of EdinburghEdinburgh

19801980 HopeHope

In Hope wurden zum ersten Mal In Hope wurden zum ersten Mal benutzerdefinierte benutzerdefinierte Datenstrukturen Datenstrukturen undund Pattern Matching Pattern Matching bei der Definition von bei der Definition von Funktionen über solchen Strukturen zugelassen.Funktionen über solchen Strukturen zugelassen.

R. Burstall, R. Burstall, D. MacQueen, D. MacQueen, D. Sannella, D. Sannella, Uni. of Uni. of EdinburghEdinburgh

JahreszJahreszahlahl

Theorie / SpracheTheorie / Sprache EntwicklerEntwickler

19851985 MirandaMiranda

Eine der wenigen kommerziell vertriebenen funktionalen Eine der wenigen kommerziell vertriebenen funktionalen Sprachen. Besonders ist hier der Einsatz von Sprachen. Besonders ist hier der Einsatz von FunktionalenFunktionalen (Funktionen höherer Ordnung), sowie die (Funktionen höherer Ordnung), sowie die bedarfsgesteuerte Auswertungsstrategie „bedarfsgesteuerte Auswertungsstrategie „lazy evaluationlazy evaluation““

D. Turner, D. Turner, University of University of KentKent

~1988~1988 HaskellHaskell ( Vorname des Logikers Haskell Brooks Curry )( Vorname des Logikers Haskell Brooks Curry )Haskell ist nach dem amerikanischen Logiker Haskell Brooks Curry benannt (weil Haskell [die Sprache] curryfizierte Funktionen liebt, wie Haskell [der Logiker]

Haskell wurde von einem Komitee von Forschern entwickelt, Haskell wurde von einem Komitee von Forschern entwickelt, die das Ziel verfolgten eine die das Ziel verfolgten eine rein funktionale rein funktionale ProgrammierspracheProgrammiersprache einzuführen. einzuführen.

Haskell unterstützt eine enrome Vielfalt von (auch oben Haskell unterstützt eine enrome Vielfalt von (auch oben aufgeführten) Konzepten und zeichnet sich insbesondere aufgeführten) Konzepten und zeichnet sich insbesondere durch ein mächtiges Typsystem und eine saubere durch ein mächtiges Typsystem und eine saubere Modellierung von interaktiven Ein-/Ausgaben aus.Modellierung von interaktiven Ein-/Ausgaben aus.

Bemerkenswert ist, dass eine Bemerkenswert ist, dass eine vollständige formale vollständige formale SemantikdefinitionSemantikdefinition ( (http://haskell.org/report/index.htmlhttp://haskell.org/report/index.html) ) existiert.existiert.

Ziele beim Entwurf von Haskell waren:Ziele beim Entwurf von Haskell waren: Für Lehre, Forschung und Anwendungen, insbesondere für Für Lehre, Forschung und Anwendungen, insbesondere für Programmierung großer SystemeProgrammierung großer SystemeVollständige Beschreibung von Syntax und SemantikVollständige Beschreibung von Syntax und SemantikFrei erhältlichFrei erhältlichBasiert auf allgemein akzeptierten IdeenBasiert auf allgemein akzeptierten Ideen

Komitee unter Komitee unter Leitung von Leitung von P.Hudak (Yale P.Hudak (Yale University),University), Ph. Wadler Ph. Wadler (Glasgow (Glasgow University)University)

Logiker H. B. Logiker H. B. CurryCurry

EntwicklungEntwicklung

Zur Geschichte:1988 Gründung des Haskell-Komitees (auf der FPCA), dem u.a. Paul Hudak, Simon Peyton Jones und Philip Wadler angehören.1990 Haskell 1.0 Sprachdefinition1992 Haskell 1.2 Sprachdefinition1996 Haskell 1.3 Sprachdefinition1997 Haskell 1.4 Sprachdefinition1999 Haskell 98 Sprachdefinition

Das Lambda-KalkülDas Lambda-Kalkül

Das Lambda-Kalkül besteht aus zwei Das Lambda-Kalkül besteht aus zwei BausteinenBausteinen

FunktionsabstraktionFunktionsabstraktionx.A x.A definiert eine definiert eine (anonyme) Funktion(anonyme) Funktion, die , die ein x bekommt, und einen Ausdruck A als ein x bekommt, und einen Ausdruck A als FunktionskörperFunktionskörper hat (in dem in der Regel x hat (in dem in der Regel x vorkommt, aber nicht vorkommen muß)vorkommt, aber nicht vorkommen muß)

FunktionsapplikationFunktionsapplikationFA bedeutet, daß die Funktion F auf dem FA bedeutet, daß die Funktion F auf dem Ausdruck A angewandt wirdAusdruck A angewandt wird

Die Groß- u. Kleinschreibung dient nur der Übersicht, es gibt keinen Grund Funktionen und Variablen zu unterscheiden, denn es kommt auf den Kontext an.

Beispiele für Funktionen Beispiele für Funktionen (1)(1)

Die Identität:Die Identität:x.xx.x

Eine Funktion, die jedes Argument Eine Funktion, die jedes Argument auf die Identitätsfunktion abbildet:auf die Identitätsfunktion abbildet:y.(y.(x.x)x.x)

Die Identität, angewandt auf sich Die Identität, angewandt auf sich selbst:selbst:((x.x)(x.x)(y.y)y.y) ((y.y)y.y)

Beispiele für Funktionen Beispiele für Funktionen (2)(2)

Nicht alle Variablennamen müssen Nicht alle Variablennamen müssen definiert sein, auch die folgenden definiert sein, auch die folgenden sind korrekte sind korrekte -Terme-Terme

x.Fxx.Fx((y.y)(z)y.y)(z) ? ?uvuvk.Jmk.Jm

Beispiele für Funktionen Beispiele für Funktionen (3)(3)

Ein komplexerer AusdruckEin komplexerer Ausdruck

((f.(f.(x.f(fx)))uvx.f(fx)))uv

((x.u(ux))vx.u(ux))v

u(uv)u(uv)

Diese Funktion wendet also Diese Funktion wendet also eine Funktion zweimal auf ein eine Funktion zweimal auf ein Argument an.Argument an.

Eigenschaften des Eigenschaften des --KalkülsKalküls

Als Bausteine gibt es nur Als Bausteine gibt es nur Funktionsabstraktionen und -applikationen.Funktionsabstraktionen und -applikationen.Das ist alles!Das ist alles!Es gibt keine Zahlen, Funktionsnamen, Es gibt keine Zahlen, Funktionsnamen, arithmetische Funktionen, Wahrheitswertearithmetische Funktionen, Wahrheitswerte

Die Funktionen werden nicht benannt, sie Die Funktionen werden nicht benannt, sie sind anonym.sind anonym.(Alle heißen (Alle heißen ))

Das Lambda-Kalkül ist ungetyptDas Lambda-Kalkül ist ungetypt

KalkülKalkül

DefinitionDefinitionEin Ein Kalkül Kalkül besteht aus zwei wesentlichen besteht aus zwei wesentlichen

Teilen:Teilen: Der Der KalkülspracheKalkülsprache, d.h., d.h.

einem zugrunde liegenden einem zugrunde liegenden Alphabet Alphabet von Zeichenvon Zeichen einer Definition der einer Definition der wohlgeformten wohlgeformten AusdrückeAusdrücke

Dem Dem DeduktionsgerüstDeduktionsgerüst, d.h., d.h. Axiomen Axiomen aus der Menge der wohlgeformten aus der Menge der wohlgeformten

Ausdrücke (Terme)Ausdrücke (Terme) AbleitungsregelnAbleitungsregeln, mit denen Ausdrücke , mit denen Ausdrücke

umgeformt/ausgewertet werdenumgeformt/ausgewertet werdennach K.Schröter(1941)nach K.Schröter(1941)

kurzer weiterer Ausblickkurzer weiterer Ausblick

Auf den ersten Blick bietet das Auf den ersten Blick bietet das --Kalkül nur sehr primitive Kalkül nur sehr primitive Funktionen, die nicht von Funktionen, die nicht von praktischem Nutzen sind.praktischem Nutzen sind.

Man kann allerdings mit dem Man kann allerdings mit dem --Kalkül Fallunterscheidungen, Zahlen Kalkül Fallunterscheidungen, Zahlen und arithmetische Funktionen und arithmetische Funktionen herleitenherleiten

kurz notiert(1)kurz notiert(1)

Um Zahlen zu erhalten, werden wir Um Zahlen zu erhalten, werden wir jetzt ganz bestimmte Funktionen mit jetzt ganz bestimmte Funktionen mit den natürlichen Zahlen identifizieren:den natürlichen Zahlen identifizieren:FFnnAA (n-malige Anwendung von F auf A) (n-malige Anwendung von F auf A) entspricht der induktiven Definitionentspricht der induktiven Definition FF00A:=A A:=A FFn+1n+1A:=A:= F( F(FFnnA)A)

Die Zahlen zDie Zahlen z00,z,z11,… werden dann ,… werden dann definiert durch:definiert durch:zznn:=:=fx.ffx.fnn(x)(x)

kurz notiert(2)kurz notiert(2)

Definition von Plus:Definition von Plus:für zwei Zahlen z und z‘für zwei Zahlen z und z‘

zz‘fx.zf(z‘fx)zz‘fx.zf(z‘fx) Definition von MalDefinition von Mal

zz‘fx.z(z‘f)xzz‘fx.z(z‘f)x

Beispiel zur Addition Beispiel zur Addition (verkürzt)(verkürzt)

Beispiel: Plus zBeispiel: Plus z22 z z33 z z55

zz22==(λ f x . f (f (x)))

z3 = (λ f x . f (f (f (x))))

PlusPlus zz22 zz33

(λ z z’ f x . z f (z’ f x)) z2 z3

→ (λ z’ f x . z2 f (z’ f x)) z3

→ (λ z’ f x . f ( f (z’ f x))) z3

→ (λ f x . f ( f (z3 f x)))→ (λ f x . f ( f ( f ( f ( f (x)))))) ( = z5 )

Beispiel zur Addition Beispiel zur Addition (ausgeschrieben)(ausgeschrieben)

Am Beispiel: Plus z2 z3 (→ z5 )

Plus z2 z3

(λ z z’ f x . z f (z’ f x)) (λ g y . g (g (y))) (λ g y . g ( g ( g (y))))

→ (λ z’ f x . (λ g y . g (g (y))) f (z’ f x)) (λ g y . g ( g ( g (y))))

→ (λ z’ f x . (λ y . f ( f (y)) (z’ f x)) (λ g y . g ( g ( g (y))))→ (λ z’ f x . f ( f (z’ f x))) (λ g y . g ( g ( g (y))))→ (λ z’ f x . f ( f (λ g y . g ( g ( g (y))) f x)))→ (λ f x . f ( f (λ y . f ( f ( f (y))) x)))→ (λ f x . f ( f ( f ( f ( f (x)))))) ( = z5 )

kurz notiert(3)kurz notiert(3) Es ist außerdem möglich If-Anweisungen Es ist außerdem möglich If-Anweisungen

mit dem mit dem -Kalkül auszudrücken.-Kalkül auszudrücken.

Sei True := Sei True := xy.xxy.x (Projektion auf das erste (Projektion auf das erste Argument)Argument)

Sei False := Sei False := xy.yxy.y (Projektion auf das zweite (Projektion auf das zweite Argument)Argument)

Damit können wir ein If definieren:Damit können wir ein If definieren:If .. then .. else .. entspricht hier: If .. then .. else .. entspricht hier: bxy.bxybxy.bxywobei b entweder True oder False ist.wobei b entweder True oder False ist.

Resultat aus der Resultat aus der Theoretischen InformatikTheoretischen Informatik

Das Das -Kalkül ist -Kalkül ist logisch äquivalent logisch äquivalent zu der zu der Turing-Maschine.Turing-Maschine.

Somit kann man mit dem Somit kann man mit dem -Kalkül -Kalkül (zumindest theoretisch) genau die (zumindest theoretisch) genau die Probleme lösen (ausrechnen), die die Probleme lösen (ausrechnen), die die heutigen Computer auch lösen können.heutigen Computer auch lösen können.

Jede von einem Computer berechenbare Funktion ist auch im Lambda-Kalkül berechenbar.

Evolution der Evolution der ProgrammiersprachenProgrammiersprachen„„high levelhigh level“ PS“ PS

Assembler Assembler MaschinenspracMaschinensprac

hehe

ProblemspezifikationProblemspezifikation

ProgrammProgramm

RechnerRechner

vertical migration

Grundkonzepte Grundkonzepte funktionaler Sprachen, funktionaler Sprachen,

insb. Haskellinsb. Haskell Die meisten Anwendungsprobleme sind auf Die meisten Anwendungsprobleme sind auf

natürliche Weise als Funktionen definiert, natürliche Weise als Funktionen definiert, Bsp.:Bsp.: sin x, sin x,

exp, …exp, … LATEX:LATEX: Datenbanksysteme (SQL):Datenbanksysteme (SQL): EVA-PrinzipEVA-Prinzip

ff11

EingabenEingaben Ausgabe Ausgabe ffnn

xn2

1n2n 1 xn

Funktion

xn0

xn

n

Text dvi Datei

SQL Anfrage Tabellenausgabe

Grundkonzept HaskellGrundkonzept HaskellAuch Haskell arbeitet so:Auch Haskell arbeitet so:

Ein funktionales Programm ist eine Ein funktionales Programm ist eine Menge von FunktionsdefinitionenMenge von Funktionsdefinitionen

ff11 X X11 .. X .. Xnn = e= e11

……

ffrr X X1,r1,r .. X .. Xn,rn,r = e= err

Funktionsbezeichner Parametervariablen Funktionsbezeichner Parametervariablen RumpfausdruckRumpfausdruck

Eine Eine Funktion transformiert Eingabe Funktion transformiert Eingabe in Ausgabein Ausgabe

Beispiele in HaskellBeispiele in Haskell-- hier stehen Kommentare-- hier stehen Kommentare-- einfache arithmetische Funktionen-- einfache arithmetische Funktionenadd x1 x2 = x1 + x2add x1 x2 = x1 + x2square x = x * xsquare x = x * xnegate x = -xnegate x = -x

-- Konstantendefinitionen-- Konstantendefinitionene = 2.71828e = 2.71828newline = '\n'newline = '\n'

-- Test auf Identität: Vergleichoperatoren-- Test auf Identität: VergleichoperatorenallEqual n m p = (n==m) && (m==p)allEqual n m p = (n==m) && (m==p)

-- Maximumsfunktion: Bsp. für Fallunterscheidung-- Maximumsfunktion: Bsp. für Fallunterscheidung

max a b | a>b = amax a b | a>b = a

| a==b = a| a==b = a

| otherwise = b| otherwise = b

TypenTypenIn Haskell haben In Haskell haben alle Datenobjekte einen wohldefinierten Typalle Datenobjekte einen wohldefinierten Typ..Ein Ein Typ ist eine Menge von ObjektenTyp ist eine Menge von Objekten gleicher Art, z.B. existieren Basistypen wie gleicher Art, z.B. existieren Basistypen wieIntInt = Menge aller ganzen Zahlen (32 Bit) = Menge aller ganzen Zahlen (32 Bit)Integer = Menge beliebiger ganzer Zahlen, insb. nur durch den Speicher beschränkte Integer = Menge beliebiger ganzer Zahlen, insb. nur durch den Speicher beschränkte

große Zahlengroße ZahlenBoolBool = {True, False} = {True, False}CharChar = Menge aller Zeichen = Menge aller ZeichenString = Eine Liste von CharString = Eine Liste von Char

Neben diesen Basistypen gibt es auch Funktionstypen, wie z.B.:Neben diesen Basistypen gibt es auch Funktionstypen, wie z.B.:Int Int Int = Menge aller einstelligen Funktionen über den ganzen Zahlen (wie z.B.: Int = Menge aller einstelligen Funktionen über den ganzen Zahlen (wie z.B.:

Quadrieren):Quadrieren):

Int Int Int Int Int = Menge aller zweistelligen Funktionen über den ganzen Zahlen (wie Int = Menge aller zweistelligen Funktionen über den ganzen Zahlen (wie z.B.: Addieren): z.B.: Addieren):

In Haskell- Programmen In Haskell- Programmen könnenkönnen optional optional TypdeklarationenTypdeklarationen der Form der Form name :: type name :: type zu zu Definitionen angegeben werden. Bei der Compilation von Programmen erfolgt eine Definitionen angegeben werden. Bei der Compilation von Programmen erfolgt eine automatische Typinferenz und Typüberprüfung (type checker). Nur korrekt automatische Typinferenz und Typüberprüfung (type checker). Nur korrekt typisierbare Programme können somit compiliert werden. Hierdurch werden viele typisierbare Programme können somit compiliert werden. Hierdurch werden viele Programmfehler frühzeitig erkannt.Programmfehler frühzeitig erkannt.Ist keine konkrete Typisierung vorgenommen, so bestimmt der Compiler Ist keine konkrete Typisierung vorgenommen, so bestimmt der Compiler automatisch den allgemeinsten Typ für jedes Datenobjekt.automatisch den allgemeinsten Typ für jedes Datenobjekt.

Int Int Int

Int Int

Beispiele in HaskellBeispiele in Haskell-- hier stehen Kommentare-- hier stehen Kommentare-- einfache arithmetische Funktionen-- einfache arithmetische Funktionenadd :: Int -> Int -> Intadd :: Int -> Int -> Intadd x1 x2 = x1 + x2add x1 x2 = x1 + x2

square :: Int -> Intsquare :: Int -> Intsquare x = x * xsquare x = x * x

negate :: Int -> Intnegate :: Int -> Intnegate x = -xnegate x = -x

-- Konstantendefinitionen-- Konstantendefinitionene :: Doublee :: Doublee = 2.71828e = 2.71828

newline :: Charnewline :: Charnewline = '\n'newline = '\n'

-- Test auf Identität-- Test auf IdentitätallEqual :: Int -> Int -> Int -> BoolallEqual :: Int -> Int -> Int -> BoolallEqual n m p = (n==m) && (m==p)allEqual n m p = (n==m) && (m==p)

-- Maximumsfunktion? Fallunterscheidung-- Maximumsfunktion? Fallunterscheidungmax :: Double -> Double -> Doublemax :: Double -> Double -> Doublemax a b | a>b = amax a b | a>b = a | a==b = a| a==b = a -- bedingte Auswertungen, funktioniert wie-- bedingte Auswertungen, funktioniert wie | otherwise = b| otherwise = b -- eine if/case-Struktur, das erste passende wird-- eine if/case-Struktur, das erste passende wird

-- ausgewertet.-- ausgewertet.

TypenTypen Bei der Compilation von Programmen erfolgt eine Bei der Compilation von Programmen erfolgt eine

automatische Typinferenz und Typüberprüfung (type automatische Typinferenz und Typüberprüfung (type checker). Nicht typisierte Programme werden checker). Nicht typisierte Programme werden automatisch möglichst allgemein typisiert.automatisch möglichst allgemein typisiert.

Ist ein Programm im Hugs-System geladen, Ist ein Programm im Hugs-System geladen, kann man mit kann man mit ::t <Funktionsbezeichnung>t <Funktionsbezeichnung>ddie Typdeklaration ie Typdeklaration eines Objekts eines Objekts erfahren.erfahren.z.B.:z.B.:

Beispielprogramm Beispielprogramm Kryptographie (1)Kryptographie (1)

Als Beispielprogramm betrachten wir das Als Beispielprogramm betrachten wir das Caesar-Verschlüsselungsverfahren.Caesar-Verschlüsselungsverfahren.

Hierzu stellt man sich das Alphabet (im Hierzu stellt man sich das Alphabet (im einfachen Fall nur die kleinen Buchstaben) einfachen Fall nur die kleinen Buchstaben) im Kreis angeordnet vor. im Kreis angeordnet vor.

Ordnet man den Zeichen von a bis z die Ordnet man den Zeichen von a bis z die Nummern 0 bis 25 zu, so ist das Verschieben Nummern 0 bis 25 zu, so ist das Verschieben innerhalb des Kreises eine Addition modulo innerhalb des Kreises eine Addition modulo 26.26.

Die Verschlüsselung besteht darin, anstelle Die Verschlüsselung besteht darin, anstelle jedes Klartextbuchstabens das Zeichen jedes Klartextbuchstabens das Zeichen auszugeben, das im Kreis um eine festgelegte auszugeben, das im Kreis um eine festgelegte Anzahl von Positionen später kommt.Anzahl von Positionen später kommt.

Beispielprogramm Beispielprogramm Kryptographie (2)Kryptographie (2)

Somit ergibt sich die Funktion Somit ergibt sich die Funktion schiebeschiebe::

Als nächstes müssen wir zwei Als nächstes müssen wir zwei Übergangsfunktionen zwischen den Übergangsfunktionen zwischen den Zahlen und den Zeichen definierenZahlen und den Zeichen definieren

schiebe :: Int -> Int -> Intschiebe schluessel zahl = mod (zahl + schluessel) 26

position :: Char -> Intposition zeichen = (ord zeichen) - 97

buchstabe :: Int -> Charbuchstabe zahl = chr (zahl + 97)

Beispielprogramm Beispielprogramm Kryptographie (3)Kryptographie (3)

Als nächstes definieren wir eine Als nächstes definieren wir eine Funktion Funktion caesar:: Int -> Char -> caesar:: Int -> Char -> CharChardie mit einem Schlüssel ein Zeichen die mit einem Schlüssel ein Zeichen verschlüsselt.verschlüsselt.Dazu verwenden wir die vorigen Dazu verwenden wir die vorigen Funktionen.Funktionen.caesar :: Int -> Char -> Charcaesar schluessel zeichen = buchstabe (schiebe schluessel (position zeichen))

Die Verschlüsselung eines ganzen Wortes Die Verschlüsselung eines ganzen Wortes erfordert die zeichenweise Anwendung dieser erfordert die zeichenweise Anwendung dieser Funktion auf die Buchstaben des Wortes. Hierzu Funktion auf die Buchstaben des Wortes. Hierzu lässt sich die Funktion lässt sich die Funktion mapmap verwenden, mit der verwenden, mit der eine Funktion elementweise auf eine eine Funktion elementweise auf eine Zeichenkette angewendet werden kann.Zeichenkette angewendet werden kann.

Eckige Klammern um den Typ Char signalisieren, Eckige Klammern um den Typ Char signalisieren, dass es sich um eine Liste von Char handelt (also dass es sich um eine Liste von Char handelt (also um einen String).um einen String).

Beispielprogramm Beispielprogramm Kryptographie (4)Kryptographie (4)

caesar_wort :: Int -> [Char] -> [Char]caesar_wort schluessel wort = map (caesar schluessel) wort

Bemerkenswert ist hier die Tatsache das caesar schluessel als eine einstellige Funktion betrachtet wird (Da der Erste von den beiden Parametervariablen bereits fest dasteht).

Beisp

ielp

rog

ram

m

Beisp

ielp

rog

ram

m

Kryp

tog

rap

hie

(5)

Kryp

tog

rap

hie

(5)

AuswertungAuswertung Bei der Auswertung von Ausdrücken Bei der Auswertung von Ausdrücken

werden die Funktionsdefinitionen als werden die Funktionsdefinitionen als Ersetzungsregeln interpretiert.Ersetzungsregeln interpretiert.

In einem In einem ReduktionsschrittReduktionsschritt wird eine wird eine Funktionsapplikation durch den Rumpf Funktionsapplikation durch den Rumpf der entsprechenden Funktionsdefinitionen der entsprechenden Funktionsdefinitionen ersetzt.ersetzt.Dabei wird eine Substitution der Dabei wird eine Substitution der Parameter vorgenommen.Parameter vorgenommen.

Ein Ausdruck ohne reduzierbare Ein Ausdruck ohne reduzierbare Teilausdrücke heißt Normalform. Teilausdrücke heißt Normalform. Die Normalform eines Ausdrucks ist somit Die Normalform eines Ausdrucks ist somit das Resultat seiner Auswertung.das Resultat seiner Auswertung.

Verschiedene Verschiedene AuswertungsstrategienAuswertungsstrategien

Haskell verwendet eine Form der Haskell verwendet eine Form der Left-most outermost StrategieLeft-most outermost Strategie

Auf dieser Strategie baut die Auf dieser Strategie baut die bedarfsgesteuerte bedarfsgesteuerte Auswertungsstrategie auf Auswertungsstrategie auf (engl. (engl. lazy evaluation, call by needlazy evaluation, call by need))

Das Motto von Lazy Evaluation Das Motto von Lazy Evaluation lautet:lautet:Berechne einen Ausdruck bzw. einen Teilausdruck nur, wenn es unbedingt nötig ist und dann auch nur einmal.

Rekursive FunktionenRekursive Funktionen

Rekursion ist eine selbst-referenzierende Art Rekursion ist eine selbst-referenzierende Art der Definition.der Definition.

Von Rekursion spricht man, wenn in der Von Rekursion spricht man, wenn in der Definition einer Funktion auf die Funktion Definition einer Funktion auf die Funktion selbst Bezug genommen wird.selbst Bezug genommen wird.

Grundidee: Meistens „Grundidee: Meistens „Divide and Conquer“ Divide and Conquer“ PrinzipPrinzip Wir zerlegen das Problem in zwei Fälle:Wir zerlegen das Problem in zwei Fälle: Einen leichten Fall, den wir lösenEinen leichten Fall, den wir lösen Und einen schweren Fall, den wir auf das leichte Und einen schweren Fall, den wir auf das leichte

Problem zurückführenProblem zurückführen

Beispiele zur RekursionBeispiele zur Rekursion Rekursion kommt häufig in der Mathematik Rekursion kommt häufig in der Mathematik

und in der Informatik vor, z.B.:und in der Informatik vor, z.B.: Die Fakultätsfunktion: Die Fakultätsfunktion:

n!n! Fibonacci-Zahlen: Fibonacci-Zahlen: fibfib00=0=0fibfib11=1=1fibfibnn=fib=fibn-1n-1+fib+fibn-2n-2

Übung: Übung: Programmieren Sie diese beiden Funktionen Programmieren Sie diese beiden Funktionen mit ihrem Tischnachbarn auf Papier und mit ihrem Tischnachbarn auf Papier und werten Sie einen nichttrivialen werten Sie einen nichttrivialen Beispielausdruck dazu aus.Beispielausdruck dazu aus.

weiterführende Beispiele weiterführende Beispiele für Rekursion in Haskellfür Rekursion in Haskell

Durch das Grundprinzip der deklarativen Durch das Grundprinzip der deklarativen Sprachen in Kombination mit der Rekursion Sprachen in Kombination mit der Rekursion lassen sich somit leicht mathematische lassen sich somit leicht mathematische Strukturen auf den Computer übertragen.Strukturen auf den Computer übertragen.

Als Beispiel kann man einen Baum nennen. Als Beispiel kann man einen Baum nennen. Dieser lässt sich in Haskell rel. einfach als Dieser lässt sich in Haskell rel. einfach als neue Datenstruktur anlegen und man kann neue Datenstruktur anlegen und man kann sehr einfach auf ihm operieren.sehr einfach auf ihm operieren.

Einfache Beispiele sind z.B. folgende Einfache Beispiele sind z.B. folgende Geometrische FormenGeometrische Formen

BeispieleBeispiele

Hugs verfügt auch über eine grafische Ausgabe. Mit ihr kann man relativ leicht solche Strukturen erzeugen.

Etwas komplexere fraktale Etwas komplexere fraktale StrukturenStrukturen

Mit etwas Mit etwas mehr mehr Rechen-Rechen-power und power und MathematMathematik ist es ik ist es dann auch dann auch möglich möglich beliebige beliebige komplexe komplexe StruktureStrukturen zu n zu erzeugen.erzeugen.

Weiteres Material (Tutorials, Papers, …) sowie den Compiler findet man unter www.haskell.org © by Christian

Heil