1
Grundlagen der Programmierung 2
Prof. Dr. Manfred Schmidt-Schauÿ
Künstliche Intelligenz und Softwaretechnologie
15. April 2009
Grundlagen der Programmierung 2:Geplanter Inhalt der zweiten Halfte
Grundlagen der Programmierung 2 (1.A) - 2 -
• rekursives Programmieren in Haskell• Auswertung in Haskell• Programmieren mit Listen• Strome als unendliche Listen in Haskell• Polymorphe Typen und Typklassen• Compilerbau; Einfuhrung• Semantik; parallele Auswertung
Bucher, Literatur, URLs
Grundlagen der Programmierung 2 (1.A) - 3 -
• http://www.cs.uni-frankfurt.de/˜prg2
• www.haskell.org Haskell-Web-Seite
• http://haskell.org/onlinereport/ Haskell-Doku
• Manuel Chakravarty und Gabriele Keller, Einfuhrung in die
Programmierung mit Haskell• Richard Bird, Introduction to Functional Programming Using
Haskell• Simon Thompson, Haskell: The Craft of Functional Program-
ming• Graham Hutton, Programming in Haskell (2007)
Haskell
Grundlagen der Programmierung 2 (1.A) - 4 -
rekursive Programmierung
mit einer stark typisierten
funktionalen Programmiersprache
mit parametrischem Polymorphismus
Haskell
Haskell
Grundlagen der Programmierung 2 (1.A) - 5 -
Haskell ist eine moderne Programmiersprache;
sehr weitgehende Konzepte werden erprobt und kombiniert
strenge und statische TypisierungNicht-strikte Auswertung
=⇒ viele korrekte Programmtransformationen=⇒ korrekte automatische Parallelisierung
Haskell
Grundlagen der Programmierung 2 (1.A) - 6 -
Wichtige Eigenschaften funktionaler Programmiersprachen
Referentielle TransparenzGleiche Funktion, gleiche Argumente =⇒ gleicher (Ruckgabe-)WertKeine Seiteneffekte! D.h. keine Anderung von Objekten
Verzogerte AuswertungNur die fur das Resultat notwendigen Unterausdrucke werden(so spat wie moglich) ausgewertet.
Parametrisch Polymorphes TypsystemNur Ausdrucke mit Typ sind erlaubt — es gibt Typvariablen.Das Typsystem garantiert: keine dynamischen Typfehler.
Automatische SpeicherverwaltungAnforderung und Freigabe von Speicher
Public Relations fur Funktionale Programmier-sprachen
Grundlagen der Programmierung 2 (1.A) - 7 -
OCaml: Variante von ML, analog zu Haskell
Artikel von Yaron Minsky und Stephen Weeks: (JFP 2008)
Einige Zitate:
”Most importantly, using OCaml helps us find, hire, and retain great
programmers. . . .
The density of bright people in the OCaml community is impressive
and it shows up in hiring “
Public Relations fur Funktionale Programmier-sprachen
Grundlagen der Programmierung 2 (1.A) - 8 -
”OCaml . . . . It has allowed us to develop code to very high standards
of safety and correctness while rapidly adapting to changing markets.
“
”Immutability OCaml is not a pure language, but the default in
OCaml is for immutability.”
”Pattern Matching A great deal of what happens in many programs
is case analysis. . . . a convenient syntax for data-directed case analy-
sis, and a proof guaranteed by the compiler that the case analysis is
exhaustive“
Public Relations fur Funktionale Programmier-sprachen
Grundlagen der Programmierung 2 (1.A) - 9 -
”The current standard library is implemented well and provides
reasonable coverage, but it is missing a lot of useful functionality and
has a number of well-known pitfalls (perhaps the most commented
upon is the fact that a number of the functions in the list module are
not tail-recursive). “
(d.h. nicht endrekursions-optimiert: dazu kommen wir noch)
Programmierung in Haskell
Grundlagen der Programmierung 2 (1.A) - 10 -
Grundprinzipien: des funktionalen Programmierens
• Definition von Funktionen quadrat x = x*x
• Aufbau von Ausdrucken:Anwendung der Funktion auf Argumente,die wieder Ausdrucke sein konnen. 3*(quadrat 5)
• programminterne Kommunikation:Nur der Wert von Ausdrucken wird bei derAuswertung zuruckgegeben. 75
• Funktionen konnen Datenobjekte sein
Interpreter / Compiler fur Haskell
Grundlagen der Programmierung 2 (1.A) - 11 -
Wir verwenden den Interpreter GHCi
Im RBI verfugbar
Einfacher Download und Installation
Umgang mit dem Interpreter
Grundlagen der Programmierung 2 (1.A) - 12 -
Online-Report http://www.haskell.org/onlinereport
Aufruf: ghci (im richtigen Fenster)>:h Hilfe>:t Ausdruck druckt den Typ des Ausdrucks>:set +t ... Optionen andern
Module im Interpreter verwenden:
:m +Char +Numeric ...
Einfache Daten und Operatoren
Grundlagen der Programmierung 2 (1.A) - 13 -
• ganze Zahlen Typ Int
n mit |n| ≤ 231 − 1 = 2147483647• beliebig lange ganze Zahlen (vom Typ Integer),• rationale Zahlen 3%7 Typ: Ratio• Gleitkommazahlen 3.456e+10 Typ: Floating)• Zeichen ’a’ Typ Char
• Datenkonstruktoren True, False; Typ Bool
Diese nennen wir auch Basiswerte (bis auf Floating)
Einfache Daten und Operatoren
Grundlagen der Programmierung 2 (1.A) - 14 -
• Arithmetische Operatoren: +,−, ∗, /,(ein) Typ: Int → Int → Int
• Arithmetische Vergleiche: ==, <=, < . . .(ein) Typ: Int → Int → Bool
• Logische Operatoren: &&, ||, not(ein) Typ: Bool → Bool → Bool
Beispiel
Grundlagen der Programmierung 2 (1.A) - 15 -
Definition eines Polynoms x2 + y2:
quadratsumme x y = quadrat x + quadrat y
Auswertung:
...
Main> quadratsumme 3 4
25
Typen in Haskell
Grundlagen der Programmierung 2 (1.A) - 16 -
Int 1,2,3,4,. . .Integer 1,2,3,4,. . .
Float 1.23e45Double 1.23e45
Integer -> Integer -> Integer (+)Integer -> Integer quadrat
Integer -> Integer -> Integer quadratsumme
Typ Konstanten,(Typ von Argument 1) -> (Typ von Argument 2) -> Ergebnistyp Funktionen
Typen in Haskell
Grundlagen der Programmierung 2 (1.A) - 17 -
Beispiel
Die Ausgabe des Interpreters fur die Addition (+) ist komplizierter:
(+) :: (Num a) => a -> a -> a
D.h.: Fur alle Typen a, die man als numerisch klassifiziert hat,
d.h. die in der Typklasse Num sind,
hat (+) den Typ a -> a -> a
Z.B. gilt:
(+)::Integer -> Integer -> Integer
(+)::Double -> Double -> Double
(vereinfachte) Haskell-Syntax
Grundlagen der Programmierung 2 (1.A) - 18 -
〈FunktionsDefinition〉 ::= 〈Funktionsname〉〈Parameter〉∗ = 〈Ausdruck〉〈Ausdruck〉 ::= 〈Bezeichner〉 | 〈Zahl〉
| (〈Ausdruck〉 〈Ausdruck〉)| (〈Ausdruck〉)| (〈Ausdruck〉〈BinInfixOp〉 〈Ausdruck〉)
〈Bezeichner〉 ::= 〈Funktionsname〉 | 〈Datenkonstruktorname〉| 〈Parameter〉 | 〈BinInfixOp〉
〈BinInfixOp〉 ::= ∗ | + | − | /
Argumente einer Funktion: formale Parameter.Anzahl der Argumente: Stelligkeit der Funktion: (ar(f))
Beispiel zur Grammatik
Grundlagen der Programmierung 2 (1.A) - 19 -
quadratsumme x y = (quadrat x) + (quadrat y)
Zeichenfolge im Programm Name in der Grammatik (sog. Nichtterminal)quadratsumme Funktionsnamex,y formale Parameter= = gleiches Zeichen wie in Grammatik(quadrat x) + (quadrat y) 〈Ausdruck〉 der Form 〈Ausdruck〉+ 〈Ausdruck〉+ binarer Infix-Operatorquadrat x Anwendung: quadrat ist ein Ausdruck
und x ist ein Ausdruck
Programm
Grundlagen der Programmierung 2 (1.A) - 20 -
Ein Haskell-Programm ist definiert als
• Eine Menge von Funktionsdefinitionen
• Eine davon ist die Definition der Konstanten main.
Haskell: Verschiedenes . . .
Grundlagen der Programmierung 2 (1.A) - 21 -
Prelude: vordefinierte Funktionen, Typen und Datenkonstruktoren
Prafix, Infix, Prioritaten: ist moglich fur Operatoren
Konventionen zur Klammerung: s1 s2 . . . sn ≡ ((. . . (s1 s2) s3 . . .) sn)
Funktionsdefinitionen:
• formale Parameter mussen verschiedenen sein;
• keine undefinierten Variablen im Rumpf!
Weitere Trennzeichen: “{“,“}“ Semikolon “; “
Layout-sensibel: bewirkt Klammerung mit {, }.
Fallunterscheidung
Grundlagen der Programmierung 2 (1.A) - 22 -
Syntax: if 〈Ausdruck〉 then 〈Ausdruck〉 else 〈Ausdruck〉
”if“,
”then“,
”else“ sind reservierte Schlusselworte
Der erste Ausdruck ist eine Bedingung (Typ Bool)
Typisierung: if Bool . . . then typ else typ
(if 1 then 1 else 2) ergibt einen Fehler
Bedingungen, Arithmetische Vergleiche
Grundlagen der Programmierung 2 (1.A) - 23 -
Die Infixoperatoren ==, <, >, <=, >=, /= haben den Typ:
Integer -> Integer -> Bool
Achtung: = ist reserviert fur Funktionsdefinitionen und let
Boolesche Ausdrucke
sind kombinierbar mit not, ||, && (nicht, oder, und)
Konstanten sind True, False.
Beispiel: 3.0 <= x && x < 5.0
Darstellungen eines Programms
Grundlagen der Programmierung 2 (1.A) - 24 -
sichtbare Syntax: vom Programmierer benutzt
Interne Syntax: “Linearisierung“; entzuckerte Version;
voll geklammert; alle Operatoren sind Prafix; kein Layout
Ableitungsbaum (Herleitungsbaum): Interne Darstellung;
Vom Kompiler erzeugt
Darstellungen eines Programms
Grundlagen der Programmierung 2 (1.A) - 25 -
Syntaxbaum:
Eindeutige Darstellung des Programms als markierter Baum.
ermoglicht die eindeutige Definition
der Ausfuhrung des Programms.
entspricht der Schachtelung des Programms.
Syntaxbaum: Beispiele
Grundlagen der Programmierung 2 (1.A) - 26 -
if x <= 0 then 1 else x*(quadrat (x-1))
ifThenElse
tthhhhhhhhhhhhhhhhhhhh
��++WWWWWWWWWWWWWWWWWWWWWWWWWW
<=
{{xxxxxxxxx
##FFFFFFFFF 1 ∗
xxqqqqqqqqqqqqqq
''PPPPPPPPPPPPPP
x 0 x app
wwooooooooooo
##FFFFFFFFF
quadrat −{{xxxxxxxxxx
��@@@
@@@@
@
x 1
Syntaxbaum: Beispiele
Grundlagen der Programmierung 2 (1.A) - 27 -
Zwei Syntaxbaume zu 1-2-3:
−����
����
��
AAA
AAAA
1 −~~}}
}}}}
}}
��@@@
@@@@
2 3
(1− (2− 3))
−~~}}
}}}}
}
��???
????
?
−��~~
~~~~
~
AAA
AAAA
A 3
1 2
((1− 2)− 3)