Date post: | 06-Apr-2015 |
Category: |
Documents |
Upload: | liutbert-zahler |
View: | 111 times |
Download: | 1 times |
Funktionale Programmierung Funktionale Programmierung mit Camlmit Caml
Klaus Becker2004
2
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Programmieren mit FunktionenProgrammieren mit Funktionen
1
g u
00
1
0 0 0 1 1 0 1 1
Ok!
akzeptor
3
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Teil 1 Teil 1
Funktionen als Programme
4
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Die Welt der AutomatenDie Welt der Automaten
Mit Hilfe endlicher Automaten kann man formale Sprachen erkennen. Der dargestellte endliche Automat erkennt die Sprache der 0-1-Worte mit gerader Parität (gerader Anzahl von 1en).
1
g u
00
1
5
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Eine AutomatenbeschreibungEine Automatenbeschreibung
Zustandsmenge: Z = {g, u}
Anfangszustand: za = g
Endzustände: zE = {g}
Eingabemenge: E = {0, 1}
Überführungsfunktion: : (g, 0) g : (g, 1) u
: (u, 0) u : (u, 1) g
1
g u
00
1
6
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ModellierungFunktionale Modellierung
Zustandsmenge: Z = {g, u}
Eingabemenge: E = {0, 1}
Anfangszustand: za = g
Endzustände: zE = {g}
Überführungsfunktion: : (g, 0) g : (g, 1) u : (u, 0) u: (u, 1) g
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
7
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ModellierungFunktionale Modellierung
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
deltaP: (g, e1) u
endzustandP: g true
anfangszustandP
zustand
eingabe
zustand
boolzustand
g u g u g u e0 e1truefalse
8
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ModellierungskonzeptModellierungskonzept
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
Typdeklaration
Konstantendeklaration
Funktionsdeklaration
Objektbereiche werden mit Hilfe von Typen beschrieben.
Eigenschaften von Objekten und Zusammenhänge zwischen Objekten mit Hilfe von Funktionen (und Konstanten).
Objektbereiche werden mit Hilfe von Typen beschrieben.
Eigenschaften von Objekten und Zusammenhänge zwischen Objekten mit Hilfe von Funktionen (und Konstanten).
9
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Auswertung von DeklarationenAuswertung von Deklarationen
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
#Type zustandP defined.
#Type eingabeP defined.
#anfangszustandP : zustandP = g
#endzustandP : zustandP -> bool = <fun>
#deltaP : zustandP * eingabeP -> zustandP = <fun>
#Type zustandP defined.
#Type eingabeP defined.
#anfangszustandP : zustandP = g
#endzustandP : zustandP -> bool = <fun>
#deltaP : zustandP * eingabeP -> zustandP = <fun>
Auswertung durch Caml
Benutzereingabe
10
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
SignaturanalyseSignaturanalyse
Benutzereingabe:
type zustandP = g | u;;
type eingabeP = e0 | e1;;
...
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
Benutzereingabe:
type zustandP = g | u;;
type eingabeP = e0 | e1;;
...
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
Auswertung:
#deltaP : zustandP * eingabeP -> zustandP = <fun>
Auswertung:
#deltaP : zustandP * eingabeP -> zustandP = <fun>
Die Funktion deltaP ordnet einem Paar bestehend aus einem Objekt vom Typ zustandP und einem Objekt vom Typ eingabeP ein Objekt vom Typ zustandP zu.
Funktionsdeklaration
Signatur der Funktion
11
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
FunktionsanwendungFunktionsanwendung
Vorherige Benutzereingaben:
type zustandP = g | u;;
type eingabeP = e0 | e1;;
...
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
Vorherige Benutzereingaben:
type zustandP = g | u;;
type eingabeP = e0 | e1;;
...
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
Auswertung:
...
#deltaP : zustandP * eingabeP -> zustandP = <fun>
#deltaP(u, e0);;
- : zustandP = u
Auswertung:
...
#deltaP : zustandP * eingabeP -> zustandP = <fun>
#deltaP(u, e0);;
- : zustandP = u
Die Auswertung des funktionalen Ausdrucks delta(e0, g) liefert das Objekt u vom Typ zustand.
Aktuelle Benutzereingabe:
deltaP(u, e0);;
Aktuelle Benutzereingabe:
deltaP(u, e0);;
12
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
FunktionsanwendungFunktionsanwendung
Auswertung:
#endzustandP(deltaP(deltaP(anfangszustandP, e1), e1));;
- : bool = true
Auswertung:
#endzustandP(deltaP(deltaP(anfangszustandP, e1), e1));;
- : bool = true
Die Auswertung des funktionalen Ausdrucks
deltaP(deltaP(anfangszustandP, e1), e1)
liefert das Objekt u vom Typ zustandP.
Benutzereingabe:
endzustandP(deltaP(deltaP(anfangszustandP, e1), e1));;
Benutzereingabe:
endzustandP(deltaP(deltaP(anfangszustandP, e1), e1));;
13
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ProgrammeFunktionale Programme
Benutzereingabe:
type zustandP = g | u;;
type eingabeP = e0 | e1;;
...
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
Benutzereingabe:
type zustandP = g | u;;
type eingabeP = e0 | e1;;
...
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
Benutzereingabe:
deltaP(u, e0);;
Benutzereingabe:
deltaP(u, e0);;
Ein funktionales Programm besteht aus einer Menge von Funktionsdeklarationen (und evtl. benötigten Typdeklarationen) und einem funktionalen Ausdruck (Berechnungsausdruck).
Ein funktionales Programm besteht aus einer Menge von Funktionsdeklarationen (und evtl. benötigten Typdeklarationen) und einem funktionalen Ausdruck (Berechnungsausdruck).
Funktionaler Ausdruck Funktionsdeklarationen
14
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ProgrammierkonzeptProgrammierkonzept
type zustandP = g | u;;
type eingabeP = e0 | e1;;
...
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
deltaP(u, e0);;
Mit Funktionen kann man programmieren. Die Programme bestehen aus Funktionsdeklarationen und einem funktionalen Berechnungsausdruck.
Mit Funktionen kann man programmieren. Die Programme bestehen aus Funktionsdeklarationen und einem funktionalen Berechnungsausdruck.
15
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Übung Übung
Entwickeln Sie ein funktionales Programm zur Simulation einer Ampelschaltung mit Tag-Nacht-Betrieb. Testen Sie das Programm.
16
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
LösungsvorschlagLösungsvorschlag
type zustandA = ro | rg | ge | gr | aa;;
type eingabeA = t | n;;
type ausgabeA = Ooo | OOo | ooO | oOo | ooo;;
let anfangszustandA = ge;;
let deltaA = function (ro, t) -> rg | (rg, t) -> gr | (gr, t) -> ge | (ge, t) -> ro | (aa, t) -> ge | (ro, n) -> aa | (rg, n) -> aa | (gr, n) -> aa | (ge, n) -> aa | (aa, n) -> ge ;;
let lambdaA = function (ro, t) -> OOo | (rg, t) -> ooO | (gr, t) -> oOo | ...
17
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Teil 2 Teil 2
Kontrollstrukturen
18
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ZielsetzungZielsetzung
Es soll ein Akzeptor-System entwickelt werden, mit dem eine Folge von Eingaben verarbeiten werden kann und rückgemeldet wird, ob diese Folge in einen Endzustand überführt.
1
g u
00
1
0 0 0 1 1 0 1 1 Ok!
19
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ListenListen
Eine Liste in Caml besteht aus einer beliebigen, aber endlichen Anzahl von Elementen, die alle den gleichen Typ haben.
1
g u
00
1
[0; 0; 0; 1; 1; 0; 1; 1]
true
20
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ListenkonstruktorenListenkonstruktoren
Leere Liste:
Die leere Liste wird mit [] dargestellt.
Hinzufügen eines Elementes:
Mit Hilfe des Hinzufügoperators :: kann ein Element vorne in eine Liste eingefügt werden.
Bsp.: 1 :: [2; 3] [1; 2; 3]
21
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Spezifikation des AutomatensimulatorsSpezifikation des Automatensimulators
simulatorP
Bsp.: simulatorP(g, [e0; e1; e1; e1]) u
Eingabeliste
Zustand nach der Verarbeitung der Eingaben
Zustand
Spezifikation:
akzeptorP
Bsp.: akzeptorP([e0; e1; e1; e1]) false
Eingabeliste true / false
Spezifikation:
22
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Rekursive ProblemreduktionRekursive Problemreduktion
Fall 1: Verarbeite eine leere Eingabenliste
simulartorP(g, []) g
simulatorP(g, [e1; e0; e1]) simulatorP(u, [e0; e1])]
g g
Fall 2: Verarbeite eine nicht-leere Eingabenliste
Rekursive Problemreduktion: Reduktion des Problems auf ein entsprechendes, aber „verkleinertes“ Problem Rekursive Problemreduktion: Reduktion des Problems auf ein entsprechendes, aber „verkleinertes“ Problem
23
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ReduktionsregelnReduktionsregeln
Fall 1: Verarbeite eine leere Eingabenliste
simulartorP(g, []) g
simulatorP(g, [e1; e0; e1]) simulatorP(u, [e0; e1])]
g g
Fall 2: Verarbeite eine nicht-leere Eingabenliste
let rec simulatorP = function (z, []) -> z | (z, e::r) -> simulatorP(deltaP(e,z), r);;
let rec simulatorP = function (z, []) -> z | (z, e::r) -> simulatorP(deltaP(e,z), r);;
24
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ReduktionskettenReduktionsketten
let rec simulatorP = function (z, []) -> z | (z, e::r) -> simulatorP(deltaP(e,z), r);;
let rec simulatorP = function (z, []) -> z | (z, e::r) -> simulatorP(deltaP(e,z), r);;
simulatorP(g, [e1; e0; e1])
simulatorP(deltaP(g, e1), [e0; e1])
simulatorP(delta(deltaP(g, e1), e0), [e1])
simulatorP(delta(delta(deltaP(g, e1), e0), e1), [])
delta(delta(deltaP(g, e1), e0), e1)
delta(delta(u, e0), e1)
delta(u, e1)
g
Caml berechnet mit Hilfe solcher Reduktionsketten den Wert des Ausgangsterms.Caml berechnet mit Hilfe solcher Reduktionsketten den Wert des Ausgangsterms.
25
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Paritäts-AkzeptorParitäts-Akzeptor
let rec simulatorP = function (z, []) -> z | (z, e::r) -> simulatorP(deltaP(z,e), r);;
let akzeptorP = function w -> endzustandP(simulatorP(anfangszustandP,w));;
let rec simulatorP = function (z, []) -> z | (z, e::r) -> simulatorP(deltaP(z,e), r);;
let akzeptorP = function w -> endzustandP(simulatorP(anfangszustandP,w));;
#simulatorP : zustandP * eingabeP list -> zustandP = <fun>
#akzeptorP : eingabeP list -> bool = <fun>
#simulatorP : zustandP * eingabeP list -> zustandP = <fun>
#akzeptorP : eingabeP list -> bool = <fun>
26
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Test des AkzeptorsTest des Akzeptors
akzeptorP([e1;e0;e1]);;akzeptorP([e1;e0;e1]);;
#akzeptorP([e1;e0;e1]);;
- : bool = true
#akzeptorP([e1;e0;e1]);;
- : bool = true
27
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
KontrollstrukturenKontrollstrukturen
let rec simulatorP = function (z, []) -> z | (z, e::r) -> simulatorP(deltaP(e,z), r);;
let akzeptorP = function w -> endzustandP(simulatorP(anfangszustandP,w));;
Funktionsdeklarationen werden mit Hilfe von - Funktionskomposition,- Fallunterscheidungen und- Rekursion aufgebaut.
Funktionsdeklarationen werden mit Hilfe von - Funktionskomposition,- Fallunterscheidungen und- Rekursion aufgebaut.
Fallunterscheidung
Rekursion
Funktionskomposition
28
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ÜbungÜbung
Entwickeln Sie eine Funktionsdeklaration zur Implementierung eines Ampelsimulators.
Liste mit den erzeugten Ausgaben
simulatorA
Bsp.: simulatorA(ro, [t; t; t; t]) [OOo; ooO; oOo; Ooo]
Eingabeliste
Zustand
Spezifikation:
29
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
LösungsvorschlagLösungsvorschlag
...
(* Deklaration der Ampel *)
...
let rec simulatorA = function (z, []) -> [] | (z, e::r) -> lambdaA(z,e) :: simulatorA(deltaA(z,e), r);;
simulatorA(anfangszustandA, [t;t;t;t;n;n]);;
...
(* Deklaration der Ampel *)
...
let rec simulatorA = function (z, []) -> [] | (z, e::r) -> lambdaA(z,e) :: simulatorA(deltaA(z,e), r);;
simulatorA(anfangszustandA, [t;t;t;t;n;n]);;
#simulatorA : zustandA * eingabeA list -> ausgabeA list = <fun>
#- : ausgabeA list = [Ooo; OOo; ooO; ooO; ooo; oOo]
#simulatorA : zustandA * eingabeA list -> ausgabeA list = <fun>
#- : ausgabeA list = [Ooo; OOo; ooO; ooO; ooo; oOo]
30
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Teil 3 Teil 3
Datenstrukturen
31
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ZielsetzungZielsetzung
Es soll ein universelles Akzeptor-System entwickelt werden, mit dem eine Folge von Eingaben mit einem beliebig vorgegebenen Automaten verarbeiten werden kann.
0 0 0 1 1 0 1 1
Ok!
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g, e0) -> g | (g, e1) -> u | (u, e0) -> u | (u, e1) -> g ;;
32
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Zustand nach der Verarbeitung der Eingaben
Spezifikation des AutomatensimulatorsSpezifikation des Automatensimulators
simulator
Bsp.: simulator((g, (g true, u false), ...), g, [e0; e1; e1; e1]) u
Eingabeliste
Zustand
Spezifikation:
Bsp.: akzeptor((g, (g true, u false), ...), [e0; e1; e1; e1]) false
Eingabeliste
Spezifikation:
Automatenbeschreibung
akzeptorAutomatenbeschreibung true / false
33
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Zustand nach der Verarbeitung der Eingaben
AutomatenbeschreibungAutomatenbeschreibung
simulator
Bsp.: simulator((g, (g true, u false), ...), g, [e0; e1; e1; e1]) u
Eingabeliste
Zustand
Spezifikation:
Automatenbeschreibung
Eine Automatenbeschreibung ist ein Tripel (az, ez, de) mit:
- az ist eine Konstante eines Zustandstyps 'a („Anfangszustand“).
- ez ist eine Funktion 'a 'b, die jedem Zustand aus 'a einen Wert aus 'b zuordnet („Endzustand“).
- de ist eine Funktion 'a * 'c 'a, die jedem Zustand aus 'a und jeder Eingabe aus einem Eingabetyp 'c einen neuen Zustand aus 'a zuordnet („Delta“).
34
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ReduktionsregelnReduktionsregeln
let rec simulator = function ((az,ez,de), z, []) -> z | ((az,ez,de), z, e::r) -> simulator((az,ez,de), de(z,e), r);;
let akzeptor = function ((az,ez,de), w) -> ez(simulator((az,ez,de), az, w));;
let rec simulator = function ((az,ez,de), z, []) -> z | ((az,ez,de), z, e::r) -> simulator((az,ez,de), de(z,e), r);;
let akzeptor = function ((az,ez,de), w) -> ez(simulator((az,ez,de), az, w));;
#simulator : ('a * 'b * ('c * 'd -> 'd)) * 'd * 'c list -> 'd = <fun>
#akzeptor : ('a * ('a -> 'b) * ('c * 'a -> 'a)) * 'c list -> 'b = <fun>
#simulator : ('a * 'b * ('c * 'd -> 'd)) * 'd * 'c list -> 'd = <fun>
#akzeptor : ('a * ('a -> 'b) * ('c * 'a -> 'a)) * 'c list -> 'b = <fun>
35
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
TestTest
let rec simulator = function ...
let akzeptor = function ...
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g,e0)->g| (g,e1)->u| (u,e0)->u| (u,e1)->g;;
let automatP = (anfangszustandP, endzustandP, deltaP);;
let wortP = [e0; e1; e1; e1];;
akzeptor(automatP, wortP);;
let rec simulator = function ...
let akzeptor = function ...
type zustandP = g | u;;
type eingabeP = e0 | e1;;
let anfangszustandP = g;;
let endzustandP = function g -> true | u -> false;;
let deltaP = function (g,e0)->g| (g,e1)->u| (u,e0)->u| (u,e1)->g;;
let automatP = (anfangszustandP, endzustandP, deltaP);;
let wortP = [e0; e1; e1; e1];;
akzeptor(automatP, wortP);;
#akzeptor(automatP, wortP);;
- : bool = false
#akzeptor(automatP, wortP);;
- : bool = false
36
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
DatenstrukturenDatenstrukturen
let rec simulator = function ((az,ez,de), z, []) -> z | ((az,ez,de), z, e::r) -> simulator(...);;
Objekte können mit Hilfe von Tupelbildung und Listen zu neuen Einheiten zusammen-gefasst werden.
Funktionen können als Eingabeobjekte für weitere Funktionen benutzt werden.
Objekte können mit Hilfe von Tupelbildung und Listen zu neuen Einheiten zusammen-gefasst werden.
Funktionen können als Eingabeobjekte für weitere Funktionen benutzt werden.
Funktion ListeTupel
37
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ÜbungÜbung
Entwickeln Sie eine Funktionsdeklaration zur Implementierung eines Automatensimulators. Testen Sie den Simulator.
Liste mit den erzeugten Ausgaben
simulator
Bsp.: simulator((...), ro, [t; t; t; t]) [OOo; ooO; oOo; Ooo]
Eingabeliste
Zustand
Spezifikation:
Automatenbeschreibung
38
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
LösungsvorschlagLösungsvorschlag
... (* Deklaration der Ampel *) ...
let rec simulator = function ((az, de, la), z, []) -> [] | ((az, de, la), z, e::r) -> la(z,e) :: simulator((az, de, la), de(z,e), r);;
let transduktor = function ((az, de, la), w) -> simulator((az, de, la), az, w);;
let ampel = (anfangszustandA, deltaA, lambdaA);;
transduktor(ampel, [t;t;t;t;n;n]);;
... (* Deklaration der Ampel *) ...
let rec simulator = function ((az, de, la), z, []) -> [] | ((az, de, la), z, e::r) -> la(z,e) :: simulator((az, de, la), de(z,e), r);;
let transduktor = function ((az, de, la), w) -> simulator((az, de, la), az, w);;
let ampel = (anfangszustandA, deltaA, lambdaA);;
transduktor(ampel, [t;t;t;t;n;n]);;
#simulator : ('a * ('b * 'c -> 'b) * ('b * 'c -> 'd)) * 'b * 'c list -> 'd list = <fun>
#transduktor : ('a * ('a * 'b -> 'a) * ('a * 'b -> 'c)) * 'b list -> 'c list = <fun>
#ampel : zustandA * (zustandA * eingabeA -> zustandA) * (zustandA * eingabeA -> ausgabeA) = ge, <fun>, <fun>
#- : ausgabeA list = [Ooo; OOo; ooO; oOo; ooo; oOo]
#simulator : ('a * ('b * 'c -> 'b) * ('b * 'c -> 'd)) * 'b * 'c list -> 'd list = <fun>
#transduktor : ('a * ('a * 'b -> 'a) * ('a * 'b -> 'c)) * 'b list -> 'c list = <fun>
#ampel : zustandA * (zustandA * eingabeA -> zustandA) * (zustandA * eingabeA -> ausgabeA) = ge, <fun>, <fun>
#- : ausgabeA list = [Ooo; OOo; ooO; oOo; ooo; oOo]
39
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Teil 4 Teil 4
Deklarative Programmierung
40
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ProgrammierstileProgrammierstile
let rec simulator = function ((az, de, la), z, []) -> [] | ((az, de, la), z, e::r) -> la(z,e) :: simulator((az, de, la), de(z,e), r);;
let transduktor = function ((az, de, la), w) -> simulator((az, de, la), az, w);;
let ampel = (anfangszustandA, deltaA, lambdaA);;
transduktor(ampel, [t;t;t;t;n;n]);;
let rec simulator = function ((az, de, la), z, []) -> [] | ((az, de, la), z, e::r) -> la(z,e) :: simulator((az, de, la), de(z,e), r);;
let transduktor = function ((az, de, la), w) -> simulator((az, de, la), az, w);;
let ampel = (anfangszustandA, deltaA, lambdaA);;
transduktor(ampel, [t;t;t;t;n;n]);;
beginautomat.anfangszustand;for i := 0 to eingaben.Count-1 do begin e := eingaben[i]; a := automat.ausgabe(e); automat.neuerZustand(e); ausgaben.Add(a); end;end;
beginautomat.anfangszustand;for i := 0 to eingaben.Count-1 do begin e := eingaben[i]; a := automat.ausgabe(e); automat.neuerZustand(e); ausgaben.Add(a); end;end;
Programmierung mit
Wertzuweisungen
Programmierung mit
Funktionsdeklarationen
41
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Imperative ProgrammierungImperative Programmierung
beginz := anfangszustand;for i := 0 to n-1 do begin e := eingaben[i]; a := ausgabe(e); z := neuerZustand(e); ausgaben[i] := a; end;end;
beginz := anfangszustand;for i := 0 to n-1 do begin e := eingaben[i]; a := ausgabe(e); z := neuerZustand(e); ausgaben[i] := a; end;end; Programmierung
mit Wertzuweisungen
Wertzuweisungen sind die zentralen elementaren Bausteine imperativer Programme. Die Wertzuweisungen verändern (i. a.) den momentanen Variablenzustand (Speicherzustand).
42
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Imperative ProgrammierungImperative Programmierung
Beschreiben, wie die Ergebnisse berechnet werden sollen.Beschreiben, wie die Ergebnisse berechnet werden sollen.
E.-Zustand
Register-maschine
A.-Zustand
Anweisungen
z := anfangszustand;for i := 0 to n-1 do begin e := eingaben[i]; a := ausgabe(e); z := neuerZustand(e); ausgaben[i] := a; end;
{eingaben: [t][t][t][t]}
{ausgaben: [Ooo][OOo][ooO][oOo]}
Imperative Programmierung besteht darin, eine mehr oder weniger abstrakte Registermaschine (Maschine mit Speicherzellen) mit Hilfe von Anweisungen zu steuern.
Imperative Programmierung besteht darin, eine mehr oder weniger abstrakte Registermaschine (Maschine mit Speicherzellen) mit Hilfe von Anweisungen zu steuern.
43
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Vorsicht: SeiteneffekteVorsicht: Seiteneffekte
PROGRAM Demo;
VAR d: boolean; w1, w2: integer;
function f(n: int.): int.; BEGIN if d THEN f := 2*n ELSE f := n; d := not d; END;
BEGINd := true;w1 := f(1)+f(2);w2 := f(2)+f(1);END.
PROGRAM Demo;
VAR d: boolean; w1, w2: integer;
function f(n: int.): int.; BEGIN if d THEN f := 2*n ELSE f := n; d := not d; END;
BEGINd := true;w1 := f(1)+f(2);w2 := f(2)+f(1);END.
{d: ; w1: ; w2: }
d := true;
{d: true; w1: ; w2: }
w1 := f(1) + f(2) ;
{d: true; w1: 4; w2: }
w1 := f(2) + f(1) ;
{d: true; w1: 4; w2: 5}
{d: ; w1: ; w2: }
d := true;
{d: true; w1: ; w2: }
w1 := f(1) + f(2) ;
{d: true; w1: 4; w2: }
w1 := f(2) + f(1) ;
{d: true; w1: 4; w2: 5}
2 2
4 1
Seiteneffekt: Veränderung einer globalen Variablen
Imperative Programmierung ist wegen der Möglichkeit, Seiteneffekte zu produzieren, recht fehleranfällig. Imperative Programmierung ist wegen der Möglichkeit, Seiteneffekte zu produzieren, recht fehleranfällig.
44
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
let rec simulator = function ((az, de, la), z, []) -> [] | ((az, de, la), z, e::r) -> la(z,e) :: simulator((az, de, la), de(z,e), r);;
let transduktor = function ((az, de, la), w) -> simulator((az, de, la), az, w);;
let ampel = (anfangszustandA, deltaA, lambdaA);;
transduktor(ampel, [t;t;t;t;n;n]);;
let rec simulator = function ((az, de, la), z, []) -> [] | ((az, de, la), z, e::r) -> la(z,e) :: simulator((az, de, la), de(z,e), r);;
let transduktor = function ((az, de, la), w) -> simulator((az, de, la), az, w);;
let ampel = (anfangszustandA, deltaA, lambdaA);;
transduktor(ampel, [t;t;t;t;n;n]);;
Funktionale ProgrammierungFunktionale Programmierung
Programmierung mit
Funkionsdeklarationen
Die funktionale Programmierung arbeitet ohne Speichervariablen. Variablen kommen hier nur als Funktionsvariablen zur Übergabe von Funktionsargumenten vor. Seiteneffekte sind demnach in der funktionalen Programmierung nicht möglich. Das Verhalten einer Funktion wird vollständig durch die Funktionsdeklarationen festgelegt.
45
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ProgrammierungFunktionale Programmierung
Beschreiben, was (welche funkt. Zusammenhänge) gelten soll.Beschreiben, was (welche funkt. Zusammenhänge) gelten soll.
E.-Term
Reduktions-maschine
A.-Term
Deklarationen
...
let rec simulator = function ((az,de,la),z,[]) ->[]|((az,de,la),z,e::r)->...
...
transduktor(ampel,[t;t;t]);;
#- : ausgabeA list = [Ooo; OOo; ooO]
Funktionale Programmierung besteht darin, die strukturellen Zusammenhänge der Miniwelt mit Hilfe von Funktionen zu beschreiben.
Funktionale Programmierung besteht darin, die strukturellen Zusammenhänge der Miniwelt mit Hilfe von Funktionen zu beschreiben.
46
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
FazitFazit
Prototyp eines Automatensimulationsprogramms:Prototyp eines Automatensimulationsprogramms:
Funktionale Programmierung erfolgt auf einem höheren Abstraktionsniveau: keine Anweisungen an eine Maschine, sondern Beschreibung funktionaler Zusammenhänge.
Funktionale Programmierung erfolgt auf einem höheren Abstraktionsniveau: keine Anweisungen an eine Maschine, sondern Beschreibung funktionaler Zusammenhänge.
Konsequenzen:- Funktionale Programme sind kurz.- Funktionale Programme sind leicht zu verstehen.- Funktionale Programmierung ist wenig fehleranfällig.- Funktionale Programmierung eignet sich zum „Prototyping“.
let rec simulator = function ((az, de, la), z, []) -> [] | ((az, de, la), z, e::r) -> la(z,e) :: simulator((az, de, la), de(z,e), r);;
let transduktor = function ((az, de, la), w) -> simulator((az, de, la), az, w);;
let rec simulator = function ((az, de, la), z, []) -> [] | ((az, de, la), z, e::r) -> la(z,e) :: simulator((az, de, la), de(z,e), r);;
let transduktor = function ((az, de, la), w) -> simulator((az, de, la), az, w);;
47
KB
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
LiteraturhinweiseLiteraturhinweise[Becker 99] K. Becker: Funktionale Programmierung. Materialien zum Lehrplan Informatik. LMZ 1999. (http://informatikag.bildung-rp.de/html/funktprog.html)
[Becker 00] K. Becker: Problemlösen mit dem Computeralgebrasystem Derive - informatisch betrachtet. (http://informatikag.bildung-rp.de/html/derive.html)
[Fischbacher 97] T. Fischbacher: Funktionale Programmierung. In: LOG IN 17 (1997) Heft 3 / 4, S. 24-26.
[ISB 97] Staatliches Institut für Schulpädagogik und Bildungsforschung München (Hrsg.): Funktionales Programmieren in Gofer. Baustein zur Didaktik der Informatik. München, 1997.
[Puhlmann 98] H. Puhlmann: Funktionales Programmieren - Eine organische Verbindung von Informatikunterricht und Mathematik. In: LOG IN 18 (1998) Heft 2, S. 46-50.
[Schwill 93] A. Schwill: Funktionale Programmierung mit Caml. In: LOG IN 13 (1993) Heft 4, S. 20-30.
[MacLennan ??] B.J. MacLennan: Functional Programming: Addison-Wesley ??.
[Wagenknecht 94] Christian Wagenknecht: Rekursion. Ein didaktischer Zugang mit Funktionen. Bonn: Dümmlers Verlag 1994.
[Wolff von Gudenberg 96] J. Wolff. von Gudenberg: Algorithmen, Datenstrukturen, Funktionale Programmierung. Eine praktische Einführung mit Caml Light. Bonn: Addison-Wesley 1996.