close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Handzettel - Informatik - FB3 - Uni Bremen - Universität Bremen

EinbettenHerunterladen
Personal
Vorlesung:
Christoph Lüth cxl@informatik.uni-bremen.de
MZH 3110, Tel. 59830
Praktische Informatik 3: Funktionale Programmierung
Vorlesung 1 vom 13.10.2014: Einführung
Tutoren:
Jan Radtke
Sandor Herms
Daniel Müller
Felix Thielke
Sören Schulze
Henrik Reichmann
Christoph Lüth
Universität Bremen
Wintersemester 2014/15
Fragestunde:
Berthold Hoffmann
jradtke@informatik.uni-bremen.de
sanherms@informatik.uni-bremen.de
dmueller@informatik.uni-bremen.de
fthielke@informatik.uni-bremen.de
sschulze@informatik.uni-bremen.de
henrikr@informatik.uni-bremen.de
hof@informatik.uni-bremen.de
Webseite: www.informatik.uni-bremen.de/~cxl/lehre/pi3.ws14
Rev. 2721
1 [24]
Termine
2 [24]
Übungsbetrieb
Vorlesung:
Di 12 – 14, MZH 1380/1400
Tutorien:
Mi
Mi
Mi
Mi
Do
Do
08
10
12
14
08
10
–
–
–
–
–
–
10
12
14
16
10
12
MZH
MZH
MZH
SFG
MZH
MZH
1110
1470
1110
1020
1110
1090
Ausgabe der Übungsblätter über die Webseite Dienstag abend
Sören Schulze
Sandor Herms
Henrik Reichmann
Felix Thielke
Jan Radtke
Daniel Müller
Besprechung der Übungsblätter in den Tutorien
Bearbeitungszeit: eine Woche
Abgabe: elektronisch bis Freitag nächste Woche 12:00
Fragestunde : Di 10 – 12 Berthold Hoffmann (Cartesium 2.048)
Elf Übungsblätter (voraussichtlich) plus 0. Übungsblatt
Anmeldung zu den Übungsgruppen über stud.ip
Übungsgruppen: max. drei Teilnehmer (nur in Ausnahmefällen vier)
3 [24]
Scheinkriterien
4 [24]
Spielregeln
Quellen angeben bei
Von n Übungsblättern werden n − 1 bewertet (geplant n = 11)
Gruppenübergreifender Zusammenarbeit;
Insgesamt mind. 50% aller Punkte
Internetrecherche, Literatur, etc.
Notenspiegel (in Prozent aller Punkte):
Pkt.%
Note
≥ 95
94.5-90
1.0
1.3
Pkt.%
89.5-85
84.5-80
79.5-75
Note
1.7
2.0
2.3
Pkt.%
74.5-70
69.5-65
64.5-60
Erster Täuschungsversuch: Null Punkte
Note
2.7
3.0
3.3
Pkt.%
59.5-55
54.5-50
49.5-0
Note
3.7
4.0
n/b
Zweiter Täuschungsversuch: Kein Schein.
Deadline verpaßt?
Triftiger Grund (z.B. Krankheit mehrerer Gruppenmitglieder)
Fachgespräch (Individualität der Leistung) am Ende
Vorher ankündigen, sonst null Punkte.
5 [24]
Fahrplan
6 [24]
Warum funktionale Programmierung lernen?
Teil I: Funktionale Programmierung im Kleinen
Denken in Algorithmen, nicht in Programmiersprachen
Einführung
Funktionen und Datentypen
Abstraktion: Konzentration auf das Wesentliche
Rekursive Datentypen
Wesentliche Elemente moderner Programmierung:
Typvariablen und Polymorphie
Funktionen höherer Ordnung I
Datenabstraktion und Funktionale Abstraktion
Funktionen höherer Ordnung II
Modularisierung
Typinferenz
Teil II: Funktionale Programmierung im Großen
Typisierung und Spezifikation
Teil III: Funktionale Programmierung im richtigen Leben
7 [24]
8 [24]
The Future is Bright — The Future is Functional
Warum Haskell?
Blick über den Tellerrand — Blick in die Zukunft
Moderne Sprache
Studium = Programmierkurs — was kommt in 10 Jahren?
Standardisiert, mehrere Implementationen
Funktionale Programmierung ist bereit für die Herausforderungen der
Zukunft:
Interpreter: ghci, hugs
Compiler: ghc, nhc98
Nebenläufige Systeme (Mehrkernarchitekturen)
Rein funktional
Vielfach vernetzte Rechner („Internet der Dinge“)
Essenz der funktionalen Programmierung
Große Datenmengen („Big Data“)
10 [24]
9 [24]
Geschichtliches
Programme als Funktionen
Grundlagen 1920/30
Kombinatorlogik und λ-Kalkül (Schönfinkel, Curry, Church)
Programme als Funktionen
Erste funktionale Programmiersprachen 1960
P : Eingabe → Ausgabe
LISP (McCarthy), ISWIM (Landin)
Keine veränderlichen Variablen — kein versteckter Zustand
Weitere Programmiersprachen 1970– 80
FP (Backus); ML (Milner, Gordon); Hope (Burstall); Miranda (Turner)
Rückgabewert hängt ausschließlich von Werten der Argumente ab,
nicht vom Aufrufkontext (referentielle Transparenz)
Konsolidierung 1990
CAML, Formale Semantik für Standard ML
Haskell als Standardsprache
Alle Abhängigkeiten explizit
Kommerzialisierung 2010
Scala, Clojure, F#
12 [24]
11 [24]
Beispiel: Programmieren mit Funktionen
Beispiel: Nichtnumerische Werte
Programme werden durch Gleichungen definiert:
Rechnen mit Zeichenketten
fac n = i f n == 0 then 1
else n∗ fac (n−1)
repeat n s = i f n == 0 then ""
else s +
+ repeat (n−1) s
Auswertung durch Reduktion von Ausdrücken:
fac 2 → if 2 == 0 then 1 else 2* fac (2-1)
→ if False then 1 else 2* fac 1
→ 2* fac 1
→ 2* if 1 == 0 then 1 else 1* fac (1-1)
→ 2* if False then 1 else 1* fac 0
→ 2* 1* fac 0
→ 2* 1* if 0 == 0 then 1 else 0* fac (0-1)
→ 2* 1* if True then 1 else 0* fac (-1)
→ 2* 1* 1 → 2
Auswertung:
repeat 2 "hallo "
→ if 2 == 0 then "" else "hallo " ++ repeat (2-1) "hallo "
→ "hallo "++ repeat 1 "hallo "
→ "hallo "++ if 1 == 0 then ""
else "hallo "++ repeat (1-1) "hallo "
→ "hallo "++ ("hallo "++ repeat 0 "hallo ")
→ "hallo "++ ("hallo "++ if 0 == 0 then ""
else repeat (0-1) "hallo ")
→ "hallo "++ ("hallo " ++ "")
→ "hallo hallo "
13 [24]
Auswertung als Ausführungsbegriff
14 [24]
Ausdrücke und Werte
Programme werden durch Gleichungen definiert:
Nichtreduzierbare Ausdrücke sind Werte
f (x ) = E
Vorgebenene Basiswerte: Zahlen, Zeichen
Auswertung durch Anwenden der Gleichungen:
Durch Implementation gegeben
Suchen nach Vorkommen von f , e.g. f (t)
f (t) wird durch E
t
x
Definierte Datentypen: Wahrheitswerte, Listen, . . .
ersetzt
Modellierung von Daten
Auswertung kann divergieren!
15 [24]
16 [24]
Typisierung
Signaturen
Typen unterscheiden Arten von Ausdrücken und Werten:
Jede Funktion hat eine Signatur
repeat n s = . . .
n
s
Zahl
Zeichenkette
fac
:: Integer→ Integer
repeat :: Int→ String→ String
Verschiedene Typen:
Basistypen (Zahlen, Zeichen)
Typüberprüfung
strukturierte Typen (Listen, Tupel, etc)
fac nur auf Int anwendbar, Resultat ist Int
Wozu Typen?
repeat nur auf Int und String anwendbar, Resultat ist String
Typüberprüfung während Übersetzung erspart Laufzeitfehler
Programmsicherheit
17 [24]
Übersicht: Typen in Haskell
18 [24]
Das Rechnen mit Zahlen
Typ
Bezeichner
Beispiel
Ganze Zahlen
Int
0
94
Fließkomma
Double
3.0
3.141592
Zeichen
Char
’a’ ’x’
’\034’
Zeichenketten
String
"yuck"
"hi\nho\"\n"
Int - ganze Zahlen als Maschinenworte (≥ 31 Bit)
Wahrheitswerte
Bool
True
False
Integer - beliebig große ganze Zahlen
Funktionen
a -> b
-45
Beschränkte Genauigkeit,
beliebige Genauigkeit,
←→
konstanter Aufwand
wachsender Aufwand
Haskell bietet die Auswahl:
’\n’
Rational - beliebig genaue rationale Zahlen
Später mehr. Viel mehr.
Float, Double - Fließkommazahlen (reelle Zahlen)
19 [24]
Ganze Zahlen: Int und Integer
Fließkommazahlen: Double
Doppeltgenaue Fließkommazahlen (IEEE 754 und 854)
Nützliche Funktionen (überladen, auch für Integer ):
+, ∗ , ^, −
abs
div , quot
mod, rem
::
::
::
::
Int→
Int→
Int→
Int→
20 [24]
Logarithmen, Wurzel, Exponentation, π und e, trigonometrische
Funktionen
Int→ Int
Int −− Betrag
Int→ Int
Int→ Int
Konversion in ganze Zahlen:
fromIntegral :: Int , Integer → Double
Es gilt (div x y)∗y + mod x y ==x
fromInteger :: Integer → Double
Vergleich durch ==, =, ≤, <, . . .
round, truncate :: Double→ Int , Integer
Achtung: Unäres Minus
Überladungen mit Typannotation auflösen:
round ( fromInt 10) :: Int
Unterschied zum Infix-Operator −
Im Zweifelsfall klammern: abs (−34)
Rundungsfehler!
21 [24]
Alphanumerische Basisdatentypen: Char
22 [24]
Zusammenfassung
Programme sind Funktionen, definiert durch Gleichungen
Notation für einzelne Zeichen: ’a’,. . .
Nützliche Funktionen:
Referentielle Transparenz
ord :: Char → Int
chr :: Int → Char
kein impliziter Zustand, keine veränderlichen Variablen
Ausführung durch Reduktion von Ausdrücken
toLower
toUpper
isDigit
isAlpha
::
::
::
::
Char→
Char→
Char→
Char→
Char
Char
Bool
Bool
Typisierung:
Basistypen: Zahlen, Zeichen(ketten), Wahrheitswerte
Strukturierte Typen: Listen, Tupel
Zeichenketten: String
Jede Funktion f hat eine Signatur f :: a → b
23 [24]
24 [24]
Document
Kategorie
Technik
Seitenansichten
19
Dateigröße
180 KB
Tags
1/--Seiten
melden