Post on 06-Apr-2015
transcript
Funktionale Funktionale ProgrammierungProgrammierung
IFB 1/2002
Klaus Becker
2
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Teil 1Teil 1
Programmieren mit Funktionen
3
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
an Mosel, Saar und Ruweran Mosel, Saar und Ruwer
4
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
KirchtürmeKirchtürme
5
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
KirchtürmeKirchtürme
6
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
DachberechnungenDachberechnungenEs soll ein Programm erstellt werden, mit dem man für verschieden dimensionierte Kirchturmdächer den Gesamtflächeninhalt berechnen kann.
Es soll ein Programm erstellt werden, mit dem man für verschieden dimensionierte Kirchturmdächer den Gesamtflächeninhalt berechnen kann.
7
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
DachstrukturDachstruktur
Pyramiden-dreieck
Übergangstrapez
Übergangs-dreieck
ADach =
4 * AÜbergangsTrapez
+ 4 * AÜbergangsDreieck
+ 8 * APyramidenDreieck
ADach =
4 * AÜbergangsTrapez
+ 4 * AÜbergangsDreieck
+ 8 * APyramidenDreieck
8
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
DachparameterDachparameter
bQ
bA
hP
hÜ
Pyramiden-dreieck
Übergangstrapez
Übergangs-dreieck
9
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ModellierungFunktionale Modellierung
bQ
bA
hP
hÜ
bQbAhÜhP
ADach
4.02.03.0
10.0
...
10
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ModellierungFunktionale ModellierungADach =
4 * AÜbergangsTrapez
+ 4 * AÜbergangsDreieck
+ 8 * APyramidenDreieck
ADach =
4 * AÜbergangsTrapez
+ 4 * AÜbergangsDreieck
+ 8 * APyramidenDreieck
gh
ADreieck
ac
ATrapez
h
ADreieck(g,h) = 0.5*g*h ADreieck(g,h) = 0.5*g*h
ATrapez(a,c,h) = 0.5*(a+c)*h ATrapez(a,c,h) = 0.5*(a+c)*h
11
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ModellierungFunktionale Modellierung
bQ
bA
hP
hÜ
hPD
sA
hÜDhÜT
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA,hÜT)
+ 4 * ADreieck(sA,hÜD)
+ 8 * ADreieck(sA,hPD)
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA,hÜT)
+ 4 * ADreieck(sA,hÜD)
+ 8 * ADreieck(sA,hPD)
12
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ModellierungFunktionale Modellierung
bQ
bA
hP
hÜ
hPD
sA
hÜDhÜT
bA
sA
bAhP
hPD
bQbA
hÜD
hÜ
bQbA
hÜT
hÜ
13
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ModellierungFunktionale Modellierung
bA
sA
bAhP
hPD
bQbA
hÜD
hÜ
bQbA
hÜT
hÜ
ADach(bQ,bA,hÜ,hP) =
4*ATrapez(bQ,sA,hÜT) +
4*ADreieck(sA,hÜD) +
8*ADreieck(sA,hPD)
ADach(bQ,bA,hÜ,hP) =
4*ATrapez(bQ,sA,hÜT) +
4*ADreieck(sA,hÜD) +
8*ADreieck(sA,hPD)
ADach(bQ,bA,hÜ,hP) =
4*ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4*ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8*ADreieck(sA(bA),hPD(bA,hP))
ADach(bQ,bA,hÜ,hP) =
4*ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4*ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8*ADreieck(sA(bA),hPD(bA,hP))
14
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale ModellierungFunktionale Modellierung
bA
sA
bAhP
hPD
bQbA
hÜD
hÜ
bQbA
hÜT
hÜ
sA(bA) = bA * tan(/8)sA(bA) = bA * tan(/8)
hPD(bA,hP) = ((bA/2)2 + hP2)hPD(bA,hP) = ((bA/2)2 + hP2)
hÜD(bQ,bA,hÜ) =
(((2 * bQ - bA)/2)2 + hÜ2)
hÜD(bQ,bA,hÜ) =
(((2 * bQ - bA)/2)2 + hÜ2)
hÜT(bQ,bA,hÜ) =
(((bQ - bA)/2)2 + hÜ2)
hÜT(bQ,bA,hÜ) =
(((bQ - bA)/2)2 + hÜ2)
15
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionales ProgrammFunktionales ProgrammADreieck(g,h) = 0.5*g*h
ATrapez(a,c,h) = 0.5*(a+c)*h
sA(bA) = bA * tan(/8)
hPD(bA,hP) = ((bA/2)2 + hP2)
hÜD(bQ,bA,hÜ) = (((2 * bQ - bA)/2)2 + hÜ2)
hÜT(bQ,bA,hÜ) = (((bQ - bA)/2)2 + hÜ2)
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
ADreieck(g,h) = 0.5*g*h
ATrapez(a,c,h) = 0.5*(a+c)*h
sA(bA) = bA * tan(/8)
hPD(bA,hP) = ((bA/2)2 + hP2)
hÜD(bQ,bA,hÜ) = (((2 * bQ - bA)/2)2 + hÜ2)
hÜT(bQ,bA,hÜ) = (((bQ - bA)/2)2 + hÜ2)
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
Funk. Progr. bestehen aus Funktionsdeklarationen.Funk. Progr. bestehen aus Funktionsdeklarationen.
16
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
AuswertungAuswertungADach(10,5,4,20)
4 * ATrapez(10,sA(5),hÜT(10,5,4)) +
4 * ADreieck(sA(10),hÜD(10,5,4)) +
8 * ADreieck(sA(10),hPD(5,20))
4 * ATrapez(10,5 * tan(/8),hÜT(10,5,4)) +
4 * ADreieck(sA(10),hÜD(10,5,4)) +
8 * ADreieck(sA(10),hPD(5,20))
...
...
306.012
ADach(10,5,4,20)
4 * ATrapez(10,sA(5),hÜT(10,5,4)) +
4 * ADreieck(sA(10),hÜD(10,5,4)) +
8 * ADreieck(sA(10),hPD(5,20))
4 * ATrapez(10,5 * tan(/8),hÜT(10,5,4)) +
4 * ADreieck(sA(10),hÜD(10,5,4)) +
8 * ADreieck(sA(10),hPD(5,20))
...
...
306.012
Die Auswertung erfolgt durch Termersetzung.Die Auswertung erfolgt durch Termersetzung.
// Funktionsaufruf
// Funktionswert
17
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ZusammenfassungZusammenfassung
Mit Funktionen kann man programmieren.
Die Programme bestehen aus
Funktionsdeklarationen. Die Programmauswertung
erfolgt durch Funktionsanwendung
(Termersetzung).
18
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Methodik: ArbeitsschritteMethodik: Arbeitsschritte
Beschreiben - Vereinfachen - Deuten
Beschreiben - Vereinfachen - Deuten
Derive
Funktions-deklarationenFunktionsaufruf
Verein-fachen
Problem-kontext
Lösung
Beschreiben
Benutzer
FunktionswertDeuten
Benutzer
19
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Derive als Derive als ProgrammiersystemProgrammiersystem
Beschreiben: ADreieck(g,h) := 0.5*g*h
ATrapez(a,c,h) := 0.5*(a+c)*h
...
ADach(10,5,4,20)
Vereinfachen:
Deuten: Der Flächeninhalt des Dachs ...
(31675 - 21950· 2) +...
306.012
20
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Übungen - Aufgabe 1Übungen - Aufgabe 1Es soll ein Programm zur Kalkulation der Herstellungskosten eines Buches entwickelt werden. Folgende Informationen sollen dabei modelliert werden:
Die Buchkosten setzen sich aus den Papierkosten, Setzkosten, Druckkosten und Bindekosten zusammen.
Das Papier wird in Bögen zum Preis von 0,43 E geliefert. Aus jedem Bogen lassen sich 16 Seiten schneiden. Der Druck kostet 0,27 E pro Bogen, der Satz 17,5 E pro Seite. Für das Binden eines Buches werden 1,83 E benötigt.
Das zu erstellende Programm soll bei gegebener Seitenzahl (z.B. 366) und der Auflage (z.B. 10000) die Gesamtherstellungskosten errechnen.
21
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Hinweise zu Aufgabe 1Hinweise zu Aufgabe 1
Modellieren Sie zunächst geeignete (Hilfs-) Funktionen. (Black-Box-Darstellung)
Entwickeln Sie anschließend die zugehörigen Funktionsdeklarationen.
Zur Berechnung der Anzahl der Bögen benötigt man eine Operation zur Durchführung der ganzzahligen Division. Benutzen Sie hierzu die folgende (in Derive vordefinierte) Operation:
23
FLOOR
54
Implementieren Sie abschließend die Funktionen mit DERIVE.
22
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Übungen - Aufgabe 2Übungen - Aufgabe 2Zur Berechnung von Flächeninhalten / Integralen wird ein Programm benötigt, das Rechtecksummen berechnen kann.
Modellieren Sie zunächst geeignete (Hilfs-) Funktionen. (Black-Box-Darstellung)
Erstellen Sie anschließend die Funktionsdeklarationen.
Implementieren Sie abschließend die Funktionen mit DERIVE.
23
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Lösung zu Aufgabe 1Lösung zu Aufgabe 1Bogen := 0.43Druck := 0.27Satz := 17.5Binden := 1.83
BogenAnzahl(Seiten) := FLOOR(Seiten - 1, 16) + 1
PapierKosten(Seiten, Auflage) := BogenAnzahl(Seiten)·Bogen·Auflage
SetzKosten(Seiten) := Seiten·Satz
DruckKosten(Seiten, Auflage) := BogenAnzahl(Seiten)·Druck·Auflage
BindeKosten(Auflage) := Auflage·Binden
Kosten(Seiten, Auflage) := PapierKosten(Seiten, Auflage) + SetzKosten(Seiten) +
DruckKosten(Seiten, Auflage) + BindeKosten(Auflage)
Bogen := 0.43Druck := 0.27Satz := 17.5Binden := 1.83
BogenAnzahl(Seiten) := FLOOR(Seiten - 1, 16) + 1
PapierKosten(Seiten, Auflage) := BogenAnzahl(Seiten)·Bogen·Auflage
SetzKosten(Seiten) := Seiten·Satz
DruckKosten(Seiten, Auflage) := BogenAnzahl(Seiten)·Druck·Auflage
BindeKosten(Auflage) := Auflage·Binden
Kosten(Seiten, Auflage) := PapierKosten(Seiten, Auflage) + SetzKosten(Seiten) +
DruckKosten(Seiten, Auflage) + BindeKosten(Auflage)
24
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Lösung zu Aufgabe 2Lösung zu Aufgabe 2Funktiondeklaration ohne Spezifikation des Funktionstermsf(x) :=
Streifenbreite:d(a, b, n) := (b - a) / n
Unterteilungsstelle:s(a, b, n, i) := a + i·d(a, b, n)
Rechtecksumme: RS(a, b, n) := (d(a, b, n) ·f(s(a, b, n, i)), i, 0, n - 1)
Funktiondeklaration ohne Spezifikation des Funktionstermsf(x) :=
Streifenbreite:d(a, b, n) := (b - a) / n
Unterteilungsstelle:s(a, b, n, i) := a + i·d(a, b, n)
Rechtecksumme: RS(a, b, n) := (d(a, b, n) ·f(s(a, b, n, i)), i, 0, n - 1)
25
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Teil 2Teil 2
Datentypen / Datenstrukturen
26
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
RechteckfigurenRechteckfiguren
Es soll ein Programm erstellt werden, mit dem man Rechteckfiguren zu einer vorgegeben Funktion veranschaulichen kann. Es soll dabei möglich sein, das Intervall und die Streifenbreite vorzugeben.
Es soll ein Programm erstellt werden, mit dem man Rechteckfiguren zu einer vorgegeben Funktion veranschaulichen kann. Es soll dabei möglich sein, das Intervall und die Streifenbreite vorzugeben.
27
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Datenmodellierung mit Datenmodellierung mit ListenListen
Punkt als Koordinatenpaar: [0, 0]
Rechteck als Streckenzug: [[0, 0], [2, 0], [2, 4], [0, 4], [0, 0]]
Rechteckfigur als Folge von Rechtecken: [
[[0, 0], [2, 0], [2, 4], [0, 4], [0, 0]],
[[2, 0], [4, 0], [4, 16], [2, 16], [2, 0]],
[[4, 0], [6, 0], [6, 36], [4, 36], [4, 0]]
]
28
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Listen in DERIVEListen in DERIVEListe: Folge von Objekten (Zahlen, Terme, Listen) [0, 1, 2, 3]
[1, x, x2, x3]
[[], [0], [[0]]]
Liste: Folge von Objekten (Zahlen, Terme, Listen) [0, 1, 2, 3]
[1, x, x2, x3]
[[], [0], [[0]]]
Erzeugung von Listen: - Aufzählung der Listenelemente - Generierung mit dem VECTOR-Operator
[1, x, x2, x3] VECTOR(xn, n, 0, 3, 1)
Erzeugung von Listen: - Aufzählung der Listenelemente - Generierung mit dem VECTOR-Operator
[1, x, x2, x3] VECTOR(xn, n, 0, 3, 1)
Term
VECTOR
nat. Zahlnat. Zahlnat. Zahlnat. Zahl
xn
Laufvariable:
0
3
1
[1, x, x2, x3]
n
Anfangswert:
Endwert:
Schrittweite:
Term:
29
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Spezifikation der Spezifikation der FunktionenFunktionen
Rechteckpunkte: nat. Zahl
LU
nat. Zahlnat. Zahlnat. Zahl
aIntervallgrenze:
n
i
Koordinaten der linken unteren Ecke von Rechteck Nummer i
bUnterteilungen: Nummer:
Intervallgrenze:
Rechteck: nat. Zahl
Rechteck
nat. Zahlnat. Zahlnat. Zahl
aIntervallgrenze:
n
i
Koordinaten der Punkte des Streckenzugs zum Rechteck Nummer i
bUnterteilungen: Nummer:
Intervallgrenze:
Rechteckfigur: nat. Zahl
RF
nat. Zahlnat. Zahl
aIntervallgrenze:
n
Koordinaten der Punkte des Streckenzugs zur Rechteckfigur
bUnterteilungen:
Intervallgrenze:
30
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ProgrammProgramm
Rechteck als Streckenzug:
Rechteck(a,b,n,i) := [LU(a,b,n,i), RU(a,b,n,i), RO(a,b,n,i), LO(a,b,n,i), LU(a,b,n,i)]
Rechteckfigur als Folge von Rechtecken:
RF(a,b,n) := VECTOR(Rechteck(a,b,n,i), i, 1, n)
Rechteckpunkte:
LU(a,b,n,i) := [s(a,b,n,i-1), 0]
RU(a,b,n,i) := [s(a,b,n,i), 0]
LO(a,b,n,i) := [s(a,b,n,i-1), f(s(a,b,n,i-1))]
RO(a,b,n,i) := [s(a,b,n,i), f(s(a,b,n,i-1))]
Unterteilungsstellen:
d(a, b, n) := (b - a) / n
s(a, b, n, i) := a + i·d(a, b, n)
31
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktion als Funktion als EingabeobjektEingabeobjekt
Spezifikation: RF
nat. Zahlnat. Zahlnat. Zahl
Intervallgrenze:
b
n
Koordinaten der Punkte des Streckenzugs zur Rechteckfigur
aIntervallgrenze: Unterteilungen:
R RfRandfunktion:
„Trick“: Term
A(pply)
TermT
Einsetzungsterm:
Neuer Term, bei dem x jeweils durch u ersetzt ist
Funktionsterm:
u
Beispiele: A(x2, 4) 16; A(x2, y-1) (y-1)2
A(T, u) := LIM(T, x, u)A(T, u) := LIM(T, x, u)
Implementierung in Derive:
32
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Derive-ImplementierungDerive-ImplementierungFunktionsdeklarationen:
A(T, u) := LIM(T, x, u)
d(a, b, n) := (b - a) / n
s(a, b, n, i) := a + i·d(a, b, n)
LU(a,b,n,i) := [s(a,b,n,i-1), 0]
RU(a,b,n,i) := [s(a,b,n,i), 0]
LO(f,a,b,n,i) := [s(a,b,n,i-1), A(f, s(a,b,n,i-1))]
RO(f,a,b,n,i) := [s(a,b,n,i), A(f, s(a,b,n,i-1))]
Rechteck(f,a,b,n,i) := [LU(a,b,n,i), RU(a,b,n,i), RO(f,a,b,n,i), LO(f,a,b,n,i), LU(a,b,n,i)]
RF(f,a,b,n) := VECTOR(Rechteck(f,a,b,n,i), i, 1, n)
Funktionsaufruf:
RF(-x2 + 4, 0, 2, 10)
Funktionsdeklarationen:
A(T, u) := LIM(T, x, u)
d(a, b, n) := (b - a) / n
s(a, b, n, i) := a + i·d(a, b, n)
LU(a,b,n,i) := [s(a,b,n,i-1), 0]
RU(a,b,n,i) := [s(a,b,n,i), 0]
LO(f,a,b,n,i) := [s(a,b,n,i-1), A(f, s(a,b,n,i-1))]
RO(f,a,b,n,i) := [s(a,b,n,i), A(f, s(a,b,n,i-1))]
Rechteck(f,a,b,n,i) := [LU(a,b,n,i), RU(a,b,n,i), RO(f,a,b,n,i), LO(f,a,b,n,i), LU(a,b,n,i)]
RF(f,a,b,n) := VECTOR(Rechteck(f,a,b,n,i), i, 1, n)
Funktionsaufruf:
RF(-x2 + 4, 0, 2, 10)
33
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Datentypen / Datentypen / DatenstrukturenDatenstrukturen
Elementare Datentypen: Zahlen: 3; 5.1; ... (Wahrheitswerte, Zeichen, Zeichenketten)
Funktionen: Terme: x2 - 1 (Zuordnungen: x x2 - 1)
Listen: inhomogen: [x2 - 1, 0, [ ] ] (homogen: [[0], [0, 1], [0, 1, 2], [0, 1, 2, 3]])
Elementare Datentypen: Zahlen: 3; 5.1; ... (Wahrheitswerte, Zeichen, Zeichenketten)
Funktionen: Terme: x2 - 1 (Zuordnungen: x x2 - 1)
Listen: inhomogen: [x2 - 1, 0, [ ] ] (homogen: [[0], [0, 1], [0, 1, 2], [0, 1, 2, 3]])
34
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
WarteschlangeWarteschlange
Es soll ein Programm erstellt werden, mit dem man Druckaufträge zwischenspeichern kann. Der Zwischenspeicher soll nach dem FIFO-Prinzip (first in, first out) arbeiten.
Es soll ein Programm erstellt werden, mit dem man Druckaufträge zwischenspeichern kann. Der Zwischenspeicher soll nach dem FIFO-Prinzip (first in, first out) arbeiten.
35
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
DatenmodellierungDatenmodellierung
Druckauftrag: [4, [31,62,75,92]]
Adresse, Daten
Druckauftrag
Zahl Daten
Zahl
..
Verbund
Sequenz
Struktur Implementieru
ng
Liste
Liste
Warteschlange: [[4, [31,62,75,92]], [3, []], [7, [102,101,77]]]
Warteschlange
Druckauftrag
..Sequenz
Struktur Implementieru
ng
Liste
Vereinfachte Warteschlange: [4, 3, 7]
36
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Warteschlangen-Warteschlangen-OperationenOperationen
Spezifikation:
Liste
ER
L erstes ElementSchlange:
Liste
OE
LSchlange ohne das erste ElementSchlange:
Liste
ML
ElementL
Auftrag:
Schlange, mit a als neuem letztem Elementa
Schlange:
37
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Listenoperatoren von Listenoperatoren von DERIVEDERIVE
Vordefinierte Operatoren
Liste
ELEMENT
nat. ZahlL
Nummer: Listenelement an der Stelle ii
Liste:
Bsp.: ELEMENT([3,5,7,2,9,4], 2) 5
Kurzschreibweise: [3,5,7,2,9,4] 2
Liste
DIMENSION
LAnzahl der ListenelementeListe:
Bsp.: DIMENSION([3,5,7,2,9,4]) 6
38
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ImplementierungImplementierung
ER(L) := ELEMENT(L,1)
OE(L) := VECTOR(ELEMENT(L,i), i, 2, DIMENSION(L))
ML(L,a) := VECTOR( IF(iDIMENSION(L), ELEMENT(L,i), a), i, 1, DIMENSION(L)+1)
ER(L) := ELEMENT(L,1)
OE(L) := VECTOR(ELEMENT(L,i), i, 2, DIMENSION(L))
ML(L,a) := VECTOR( IF(iDIMENSION(L), ELEMENT(L,i), a), i, 1, DIMENSION(L)+1)
IF-Operator Syntax: IF( Bedingung, then-Ausdruck, else-Ausdruck )
Bsp.:
IF( x = y, 1, 0)
IF( x > 0, x2, -x2 )
39
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ZusammenfassungZusammenfassung
elementare Datentypen
Liste als zentrale Datenstruktur;
zur Verarbeitung von Listen benötigt man
elementare Listenoperationen
Funktionen als Datenobjekte
40
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Methodik: ProgrammierenMethodik: Programmieren
Schritt 1:
Spezifikation der Funktion
a) Signatur (Typen der Parameter; Ergebnistyp)
b) Verhalten (informelle Beschreibung; Beispiele)
Spezifikation der Funktion
a) Signatur (Typen der Parameter; Ergebnistyp)
b) Verhalten (informelle Beschreibung; Beispiele)
Schritt 2:
Deklaration der FunktionDeklaration der Funktion
Schritt 3:
Implementierung der FunktionImplementierung der Funktion
41
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Übung: Aufgabe 3 Übung: Aufgabe 3 Implementieren und testen Sie die folgenden Operationen zur Listenverarbeitung:
Liste
LE
L letztes Element
Liste
OL
LListe ohne das letzte Element
Element
ME
Listea Liste, mit a als neuem
erstem ElementL
42
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Übung: Aufgabe 4 Übung: Aufgabe 4 Eine Liste enthält die Ergebnisse einer Würfelwurfserie.Z.B.: [3, 2, 2, 6, 4, 5, 3, 6, 1, 5]Entwickeln Sie ein Programm, das zählt, wie oft eine bestimmte Augenzahl in der Würfelwurfserie vorgekommt.
Hinweise:Entwickeln Sie zunächst eine Funktion, mit der man die interessierende Augenzahl (z. B. 6) herausfiltern kann.[3, 2, 2, 6, 4, 5, 3, 6, 1, 5] [0, 0, 0, 1, 0, 0, 0, 1, 0, 0]Mit Hilfe des vordefinierten SUM-Operators kann dann die gewünschte Anzahl bestimmt werden.
43
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Lösung zu Aufgabe 3 Lösung zu Aufgabe 3 L := [3, 5, 2, 8, 6, 5, 1]
LE(L) := ELEMENT(L, DIMENSION(L))
LE(L)
1
OL(L) := VECTOR(ELEMENT(L, i), i, 1, DIMENSION(L) - 1)
OL(L)
[3, 5, 2, 8, 6, 5]
ME(L, a) := VECTOR(IF(i = 0, a, ELEMENT(L, i)), i, 0, DIMENSION(L))
ME(L, 0)
[0, 3, 5, 2, 8, 6, 5, 1]
L := [3, 5, 2, 8, 6, 5, 1]
LE(L) := ELEMENT(L, DIMENSION(L))
LE(L)
1
OL(L) := VECTOR(ELEMENT(L, i), i, 1, DIMENSION(L) - 1)
OL(L)
[3, 5, 2, 8, 6, 5]
ME(L, a) := VECTOR(IF(i = 0, a, ELEMENT(L, i)), i, 0, DIMENSION(L))
ME(L, 0)
[0, 3, 5, 2, 8, 6, 5, 1]
44
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Lösung zu Aufgabe 4 Lösung zu Aufgabe 4 Filter(w, L) := VECTOR(IF(ELEMENT(L, i) = w, 1, 0), i, 1, DIMENSION(L))
Filter(6, [3, 4, 6, 2, 1, 6, 4])
[0, 0, 1, 0, 0, 1, 0]
Zaehlen(w, L) := SUM(Filter(w, L))
Zaehlen(6, [3, 4, 6, 2, 1, 6, 4])
2
Filter(w, L) := VECTOR(IF(ELEMENT(L, i) = w, 1, 0), i, 1, DIMENSION(L))
Filter(6, [3, 4, 6, 2, 1, 6, 4])
[0, 0, 1, 0, 0, 1, 0]
Zaehlen(w, L) := SUM(Filter(w, L))
Zaehlen(6, [3, 4, 6, 2, 1, 6, 4])
2
45
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Teil 3Teil 3
Kontrollstrukturen
46
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Bearbeitung von AnfragenBearbeitung von Anfragen
Das Programm zur Verwaltung von Druckaufträgen soll auch Anfragen von Benutzern bearbeiten können.Z.B.: An welcher Stelle befindet sich „mein Auftrag“ in der Warteschlange?
Das Programm zur Verwaltung von Druckaufträgen soll auch Anfragen von Benutzern bearbeiten können.Z.B.: An welcher Stelle befindet sich „mein Auftrag“ in der Warteschlange?
47
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Spezifikation zur AnfrageSpezifikation zur Anfrage
An welcher Stelle befindet sich der erste Auftrag von Rechner x?
Problem:
Listenel.
Stelle
Listex
Schlange:
Stelle, an der sich der erste Auftrag von x befindet L
Adresse:
Bsp.: Stelle(2, [3,5,2,7,2,9,4]) 3
Spezifikation:
48
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Rekursive Rekursive ProblemreduktionProblemreduktion
Reduktionsschritte:
Stelle(3, []) 0
Stelle(3, [1, 2, 1, 3, 8, 3]) 1 + Stelle(3, [2, 1, 3, 8, 3])
Stelle(3, [3, 8, 3]) 1
4 3
4
Rekursive Problemreduktion:
Reduktion des Problems auf ein entsprechendes, aber „verkleinertes“ Problem
Rekursive Problemreduktion:
Reduktion des Problems auf ein entsprechendes, aber „verkleinertes“ Problem
49
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ReduktionsregelnReduktionsregeln
Reduktionsschritte:
Reduktionsregeln:
Stelle(x, []) 0
Stelle(x, [e|R]) IF(x=e, 1, 1+Stelle(x,R))
Stelle(x, []) 0
Stelle(x, [e|R]) IF(x=e, 1, 1+Stelle(x,R))
Stelle(3, []) 0
Stelle(3, [1, 2, 1, 3, 8, 3]) 1 + Stelle(3, [2, 1, 3, 8, 3])
Stelle(3, [3, 8, 3]) 1
Reduktionsregeln sind Problemreduktionsschemata.Reduktionsregeln sind Problemreduktionsschemata.
50
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
DERIVE-ImplementierungDERIVE-Implementierung
Reduktionsregeln:
Stelle(x, []) 0
Stelle(x, [e|R]) IF(x=e, 1, 1+Stelle(x,R))
Stelle(x, []) 0
Stelle(x, [e|R]) IF(x=e, 1, 1+Stelle(x,R))
Implementierung:
Stelle(x, L) :=
IF(DIMENSION(L)=0,0,
IF(x=ER(L), 1, 1+Stelle(x,OE(L))))
Stelle(x, L) :=
IF(DIMENSION(L)=0,0,
IF(x=ER(L), 1, 1+Stelle(x,OE(L))))
51
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
eine Löschanfrageeine Löschanfrage
Lösche den ersten Auftrag von Rechner x.
Problem:
Listenel.
LöscheErstes
Listex
Schlange:
Liste ohne den ersten vorkommenden Auftrag von x L
Adresse:
Bsp.: LöscheErstes(2, [3,5,2,7,2,9,4]) [3,5,7,2,9,4]
Spezifikation:
52
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Rekursive Rekursive ProblemreduktionProblemreduktion
Reduktionsschritte:
DelEr(3, []) []
DelEr(3, [1, 2, 1, 3, 8, 3]) [1 | DelEr(3, [2, 1, 3, 8, 3])]
DelEr (3, [3, 8, 3]) [8, 3]
[1, 2, 1, 8, 3] [2, 1, 8, 3]
[1, 2, 1, 8, 3]
Reduktionsregeln:
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, ME(e, DelEr(x,R)))
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, ME(e, DelEr(x,R)))
53
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
DERIVE-ImplementierungDERIVE-Implementierung
Implementierung: DelEr(x, L) :=
IF(DIMENSION(L)=0, [],
IF(x=ER(L), OE(L), ME(ER(L), DelEr(x, OE(L)))))
DelEr(x, L) :=
IF(DIMENSION(L)=0, [],
IF(x=ER(L), OE(L), ME(ER(L), DelEr(x, OE(L)))))
Reduktionsregeln:
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, ME(e, DelEr(x,R)))
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, ME(e, DelEr(x,R)))
54
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ReduktionskonzeptReduktionskonzept
Reduktionskette: Anwendung der Reduktionsregeln Reduktionskette: Anwendung der Reduktionsregeln
DelEr(3, [1, 2, 1, 3, 8, 3])
ME(1, DelEr(3, [2, 1, 3, 8, 3]))
ME(1, ME(2, DelEr(3, [1, 3, 8, 3])))
ME(1, ME(2, ME(1, DelEr(3, [3, 8, 3]))))
ME(1, ME(2, ME(1, [8, 3])))
[1, 2, 1, 8, 3]
DelEr(3, [1, 2, 1, 3, 8, 3])
ME(1, DelEr(3, [2, 1, 3, 8, 3]))
ME(1, ME(2, DelEr(3, [1, 3, 8, 3])))
ME(1, ME(2, ME(1, DelEr(3, [3, 8, 3]))))
ME(1, ME(2, ME(1, [8, 3])))
[1, 2, 1, 8, 3]
Reduktionsregeln: ProblemreduktionsschemataReduktionsregeln: Problemreduktionsschemata
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, ME(e, DelEr(x,R)))
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, ME(e, DelEr(x,R)))
Funktionsaufruf
Funktionswert
55
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ZusammenfassungZusammenfassung
KontrollstrukturenDelEr(x, L) := IF(DIMENSION(L)=0, [], IF(x=ER(L), OE(L), ME(ER(L), DelEr(x, OE(L)))))
RekursionKomposition
Fallunterscheidung
56
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Methodik: RekursionMethodik: Rekursion
Schritt 1: Entwurf typischer, exemplarischer Reduktionsschritte
(Korrektheitsbetrachtungen, Terminationsbetrachtungen)
Entwurf typischer, exemplarischer Reduktionsschritte
(Korrektheitsbetrachtungen, Terminationsbetrachtungen)
Schritt 2:
Verallgemeinerung zu ReduktionsregelnVerallgemeinerung zu Reduktionsregeln
Schritt 3:
Beschreibung mit einer rekursiven FunktionBeschreibung mit einer rekursiven Funktion
57
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Übung - Aufgabe 5Übung - Aufgabe 5Entwickeln Sie funktionale Programme zur Bearbeitung der folgenden Anfragen:
- Wie viele Aufträge hat Rechner x in der Schlange?
- Lösche alle Aufträge von Rechner x in der Schlange.
- Welche Rechner haben einen Auftrag in der Schlange?
Gehen Sie dabei nach der oben beschriebenen Methode (exemplarische Reduktionsschritte; Reduktionsregeln; Implementierung in Derive) vor.
58
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Übung - Aufgabe 6Übung - Aufgabe 6Miniprojekt: Wir betrachten die folgende Erweiterung des Warteschlangen-Programms:
Die Druckaufträge sollen jetzt zusätzlich mit Prioritätsangaben versehen werden (dringend, eilt nicht, brennt, ...). Diese Prioritätsangaben werden hier mit Zahlen kodiert (je kleiner die Zahl, desto höher ist die Priorität). Ein Druckauftrag wird im folgenden durch ein Zahlenpaar [Adresse, Prioritätsangabe] beschrieben.
Welche Änderungen ergeben sich durch diese Erweiterung?
Mit Hilfe einer Funktion „Umschalten“ soll man vom normalen „FIFO-Betrieb“ in den „Prioritätsbetrieb“ umschalten können. Die Druckaufträge sollen dann in der Warteschlange umsortiert werden.
59
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Lösung zu Aufgabe 5Lösung zu Aufgabe 5
Wie viele Aufträge hat Rechner x in der Schlange?
Reduktionsregeln: Anzahl(x, []) 0
Anzahl(x, [e|R]) IF(x=e, 1+Anzahl(x,R), Anzahl(x,R))
Anzahl(x, []) 0
Anzahl(x, [e|R]) IF(x=e, 1+Anzahl(x,R), Anzahl(x,R))
Implementierung: Anzahl(x, L) :=
IF(DIMENSION(L)=0,0,
IF(x=ER(L), 1+Anzahl(x,OE(L)),Anzahl(x,OE(L))))
Anzahl(x, L) :=
IF(DIMENSION(L)=0,0,
IF(x=ER(L), 1+Anzahl(x,OE(L)),Anzahl(x,OE(L))))
Anfrage:
60
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Lösung zu Aufgabe 5Lösung zu Aufgabe 5
Lösche alle Aufträge von Rechner x in der Schlange.
Reduktionsregeln:
Implementierung:
Anfrage:
DelAlle(x, []) []
DelAlle(x, [e|R]) IF(x=e, DelAlle(x,R), ME(e, DelAlle(x,R)))
DelAlle(x, []) []
DelAlle(x, [e|R]) IF(x=e, DelAlle(x,R), ME(e, DelAlle(x,R)))
DelAlle(x, L) :=
IF(DIMENSION(L)=0, [],
IF(x=ER(L), DelAlle(x,OE(L)), ME(ER(L), DelAlle(x, OE(L)))))
DelAlle(x, L) :=
IF(DIMENSION(L)=0, [],
IF(x=ER(L), DelAlle(x,OE(L)), ME(ER(L), DelAlle(x, OE(L)))))
61
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Lösung zu Aufgabe 5Lösung zu Aufgabe 5
Welche Rechner haben einen Auftrag in der Schlange?
Reduktionsregeln:
Implementierung:
Anfrage:
Benutzer([]) []
Benutzer([e|R]) ME(e, Benutzer(DelAlle(e,R))
Benutzer([]) []
Benutzer([e|R]) ME(e, Benutzer(DelAlle(e,R))
Benutzer(L) :=
IF(DIMENSION(L)=0, [], ME(ER(L), Benutzer(DelAlle(ER(L), OE(L)))))
Benutzer(L) :=
IF(DIMENSION(L)=0, [], ME(ER(L), Benutzer(DelAlle(ER(L), OE(L)))))
62
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Teil 4Teil 4
Funktionale Programmierung
63
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ein Problem - drei ein Problem - drei LösungenLösungen
Tauschen(x, y)
z := x x := y y := z
Tauschen(x, y)
z := x x := y y := z
imperative Lösung
Tauschen([x, y]) = [y, x]Tauschen([x, y]) = [y, x]
funktionale Lösung
Tauschen([x, y], [a, b])
x = b, y = a
Tauschen([x, y], [a, b])
x = b, y = a
Logik-basierte Lösung
64
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ProgrammierstileProgrammierstile
Registerbelegung
Register-maschine
Registerbelegung
Programm:z := xx := yy := z
Imperative Programmierung
Das Programm besteht aus Anweisungen.
Die Registermaschine verändert die Register-belegung gemäß den Anweisungen.
Imperative Programmierung
Das Programm besteht aus Anweisungen.
Die Registermaschine verändert die Register-belegung gemäß den Anweisungen.
Algorithmisches Denken
Erfassen u. Beschreiben von (zeitlichen) Abläufen
Algorithmisches Denken
Erfassen u. Beschreiben von (zeitlichen) Abläufen
65
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ProgrammierstileProgrammierstile
Ergebnis
Inferenz-maschine
Anfrage
Programm:T([x, y], [a, b])
x = b, y = a
Logik-basierte Programmierung
Das Programm besteht aus Fakten und Regeln.
Die Inferenzmaschine sucht eine auf den Fakten und Regeln basierende logische Folgerungskette zur Klärung der Anfrage.
Logik-basierte Programmierung
Das Programm besteht aus Fakten und Regeln.
Die Inferenzmaschine sucht eine auf den Fakten und Regeln basierende logische Folgerungskette zur Klärung der Anfrage.
Logisches Denken
Erfassen u. Beschreiben von Sachverhalten
Logisches Denken
Erfassen u. Beschreiben von Sachverhalten
66
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
ProgrammierstileProgrammierstile
Ergebnisterm
Reduktions-maschine
Ausgangsterm
Programm:Tauschen([x, y]) = [y, x]
Funktionale Programmierung
Das Programm besteht a. Funktionsdeklarationen.
Die Reduktionsmaschine vereinfacht den Aus-gangsterm mit Hilfe der Funktionsdeklarationen.
Funktionale Programmierung
Das Programm besteht a. Funktionsdeklarationen.
Die Reduktionsmaschine vereinfacht den Aus-gangsterm mit Hilfe der Funktionsdeklarationen.
Funktionales Denken
Erfassen u. Beschreiben von Zuordnungen
Funktionales Denken
Erfassen u. Beschreiben von Zuordnungen
67
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionales DenkenFunktionales Denken
Funktionale Ausdrücke
/Terme beschreiben
Problemwerte
Funktionsterme beinhalten
Berechnungsregeln
Funktionen beschreiben Ein-/Ausgabe-Sit. bzw. Berechnungssituationen
Funktionale Ausdrücke / Terme sind referentiell transparent
68
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Referentielle TransparenzReferentielle TransparenzJeder (Teil-)Term beschreibt einen bestimmten Wert, der nicht durch die Auswertung anderer (Teil-)Terme verändert werden kann. Die Auswertung eines (Teil-)Term verändert seine Form, aber nicht seinen Wert.
Jeder (Teil-)Term beschreibt einen bestimmten Wert, der nicht durch die Auswertung anderer (Teil-)Terme verändert werden kann. Die Auswertung eines (Teil-)Term verändert seine Form, aber nicht seinen Wert.
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
- Term muss nur einmal dargestellt / ausgewertet werden
- Reihenfolge der Auswertung irrelevant
- parallele Auswertung ist möglich
- keine Seiteneffekte, die das Verhalten komplizieren
69
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Referentielle TransparenzReferentielle TransparenzFunktionale Programme sind i. a. referentiell transparent.Funktionale Programme sind i. a. referentiell transparent.
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
Imperative Programme sind i. a. referentiell undurchsichtig.Imperative Programme sind i. a. referentiell undurchsichtig.
s := 0;x := x + 1s := s + x;x := x + 1;s := s + 1;
s := 0;x := x + 1s := s + x;x := x + 1;s := s + 1;
70
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Auswertung von Auswertung von WürfelserienWürfelserien
Mit Hilfe eines Programms sollen Würfelserien erzeugt und ausgewertet werden. Das Programm soll insbesondere eine Häufigkeitsverteilung erstellen.
Mit Hilfe eines Programms sollen Würfelserien erzeugt und ausgewertet werden. Das Programm soll insbesondere eine Häufigkeitsverteilung erstellen.
...
71
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Programm - Version 1Programm - Version 1
Wuerfeln := RANDOM(6) + 1WuerfelSerie(n) := VECTOR(Wuerfeln, m, 1, n)WuerfelSerie(10)[4, 4, 5, 5, 5, 5, 2, 3, 4, 5]Häufigkeit(i, n) :=
DIMENSION(SELECT(x = i, x, WuerfelSerie(n)))Häufigkeit(4, 100)20Häufigkeit(3, 100)16Verteilung(n) := VECTOR([i, Häufigkeit(i, n)], i, 1, 6)[[ 1, 16], [2, 16], [3, 13], [4, 20], [5, 16], [6, 16]]
Wuerfeln := RANDOM(6) + 1WuerfelSerie(n) := VECTOR(Wuerfeln, m, 1, n)WuerfelSerie(10)[4, 4, 5, 5, 5, 5, 2, 3, 4, 5]Häufigkeit(i, n) :=
DIMENSION(SELECT(x = i, x, WuerfelSerie(n)))Häufigkeit(4, 100)20Häufigkeit(3, 100)16Verteilung(n) := VECTOR([i, Häufigkeit(i, n)], i, 1, 6)[[ 1, 16], [2, 16], [3, 13], [4, 20], [5, 16], [6, 16]]
Nicht korrekt!
72
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Programm - Version 2Programm - Version 2
Wuerfeln := RANDOM(6) + 1WuerfelSerie(n) := VECTOR(Wuerfeln, m, 1, n)WuerfelSerie(10)[4, 4, 5, 5, 5, 5, 2, 3, 4, 5]Häufigkeit(i, L) := DIMENSION(SELECT(x = i, x, L))Häufigkeit(5, [4, 4, 5, 5, 5, 5, 2, 3, 4, 5])5Verteilung(L) := VECTOR([i, Häufigkeit(i, L)], i, 1, 6)Verteilung([4, 4, 5, 5, 5, 5, 2, 3, 4, 5])[[ 1, 0], [2, 1], [3, 1], [4, 3], [5, 5], [6, 0]]Verteilung(WuerfelSerie(100))[[ 1, 12], [2, 14], [3, 22], [4, 19], [5, 14], [6, 19]]
Wuerfeln := RANDOM(6) + 1WuerfelSerie(n) := VECTOR(Wuerfeln, m, 1, n)WuerfelSerie(10)[4, 4, 5, 5, 5, 5, 2, 3, 4, 5]Häufigkeit(i, L) := DIMENSION(SELECT(x = i, x, L))Häufigkeit(5, [4, 4, 5, 5, 5, 5, 2, 3, 4, 5])5Verteilung(L) := VECTOR([i, Häufigkeit(i, L)], i, 1, 6)Verteilung([4, 4, 5, 5, 5, 5, 2, 3, 4, 5])[[ 1, 0], [2, 1], [3, 1], [4, 3], [5, 5], [6, 0]]Verteilung(WuerfelSerie(100))[[ 1, 12], [2, 14], [3, 22], [4, 19], [5, 14], [6, 19]]
Korrekt!
73
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Der RANDOM-OperatorDer RANDOM-Operator
Versuch 1:
VECTOR(RANDOM(2), i, 1, 3)[0, 0, 1]VECTOR(RANDOM(2), i, 1, 3)[1, 0, 1]
VECTOR(RANDOM(2), i, 1, 3)[0, 0, 1]VECTOR(RANDOM(2), i, 1, 3)[1, 0, 1]
Versuch 2:
h(x) := VECTOR(x, i, 1, 3)h(RANDOM(2))[1, 1, 1]h(RANDOM(2))[0, 0, 0]
h(x) := VECTOR(x, i, 1, 3)h(RANDOM(2))[1, 1, 1]h(RANDOM(2))[0, 0, 0]
Keine referentielle Transparenz!
74
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
AuswertungsstrategienAuswertungsstrategienVersuch 1 - Auswertung: erst außen, dann innnen
VECTOR(RANDOM(2), i, 1, 3) [RANDOM(2), RANDOM(2), RANDOM(2)] [0, 0, 1]
VECTOR(RANDOM(2), i, 1, 3) [RANDOM(2), RANDOM(2), RANDOM(2)] [0, 0, 1]
Versuch 2 - Auswertung: erst innen, dann außen h(RANDOM(2)) // h(x) := VECTOR(x, i, 1, 3) h(1) VECTOR(1, i, 1, 3) [1, 1, 1]
h(RANDOM(2)) // h(x) := VECTOR(x, i, 1, 3) h(1) VECTOR(1, i, 1, 3) [1, 1, 1]
Wenn keine referentielle Transparenz vorhanden ist, muss man detailliertes Wissen über die Arbeitsweise der ausführenden Maschine haben, um korrekte Programme zu erstellen.
75
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Warum funktional?Warum funktional?Grund 1: (nach B. J. MacLennan, Functional Programming) Programmieren erfolgt ohne Wertzuweisungen.
Vorteile:
- Programme sind einfacher zu verstehen.
- Programme können systematischer erzeugt werden.
- Es ist einfacher, Programme zu beurteilen.
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
Beispiel:
76
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Warum funktional?Warum funktional?Grund 2: (nach B. J. MacLennan, Functional Programming) Funktionale Programmierung unterstützt parallele
Verarbeitung.
Grund: referentielle Transparenz
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
ADach(bQ,bA,hÜ,hP) =
4 * ATrapez(bQ,sA(bA),hÜT(bQ,bA,hÜ)) +
4 * ADreieck(sA(bA),hÜD(bQ,bA,hÜ)) +
8 * ADreieck(sA(bA),hPD(bA,hP))
Beispiel:
77
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Warum funktional?Warum funktional?Grund 3: (nach B. J. MacLennan, Functional Programming)
Funktionales Programmieren erfolgt auf einem höheren Abstraktionsniveau.
Beispiel: Sortieren
ins(x, []) [x]
ins(x, [e|R]) IF(x < e, [x|[e| R]], [e|ins(x, R)])
ins(x, []) [x]
ins(x, [e|R]) IF(x < e, [x|[e| R]], [e|ins(x, R)])
sort([]) [ ]
sort([e|R]) ins(e, sort(R))
sort([]) [ ]
sort([e|R]) ins(e, sort(R))
78
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Warum funktional?Warum funktional?Grund 4: (nach B. J. MacLennan, Functional Programming)
Funktionale Programmierung wird sehr viel in der KI (künstliche Intelligenz) verwendet.
Grund 5: (nach B. J. MacLennan, Functional Programming)
Funktionale Programmierung erlaubt es, schnell Prototypen zu entwickeln (Programme als ausführbare Spezifikationen).
Grund 6: (nach B. J. MacLennan, Functional Programming) Funktionale Programmierung ist eng verknüpft mit der
theoretischen Informatik: liefert ein Programmiermodell, das sich gut eignet, allgemeine Fragestellungen zu untersuchen.
79
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale SprachenFunktionale Sprachen
-Kalkül (Church und Kleene; 30er Jahre)
LISP (McCarthy; um 1960)
LOGO (Papert; 80er Jahre)
ML (Milner 1984; Caml)
Miranda (Turner 1985)
Haskell (Hudak u. a. 1992)
80
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale SprachenFunktionale Sprachen
Reduktionsregeln:
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, [e | DelEr(x,R)] )
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, [e | DelEr(x,R)] )
Implementierung mit Derive:
DelEr(x, L) :=
IF(DIMENSION(L)=0, [], IF(x=ER(L), OE(L), ME(ER(L), DelEr(x, OE(L)))))
DelEr(x, L) :=
IF(DIMENSION(L)=0, [], IF(x=ER(L), OE(L), ME(ER(L), DelEr(x, OE(L)))))
81
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale SprachenFunktionale Sprachen
Reduktionsregeln:
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, [e | DelEr(x,R)] )
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, [e | DelEr(x,R)] )
Implementierung in LOGO:
PR DelEr :x :L
PRÜFE :L = [ ]WW RG []WF PRÜFE :x = ER :LWW RG OE(L) WF RG ME ER :L DelEr :x OE :L
PR DelEr :x :L
PRÜFE :L = [ ]WW RG []WF PRÜFE :x = ER :LWW RG OE(L) WF RG ME ER :L DelEr :x OE :L
82
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
Funktionale SprachenFunktionale Sprachen
Reduktionsregeln:
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, [e | DelEr(x,R)] )
DelEr(x, []) []
DelEr(x, [e|R]) IF(x=e, R, [e | DelEr(x,R)] )
Implementierung in CAML:
let rec DelEr = function
(x, []) -> [] |
(x, e::r) -> if x = e then r else e::DelEr(x,r);;
DelEr : `a * `a list -> `a list = <fun>
let rec DelEr = function
(x, []) -> [] |
(x, e::r) -> if x = e then r else e::DelEr(x,r);;
DelEr : `a * `a list -> `a list = <fun>
83
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
... und in der Schule?... und in der Schule?
„andere“ Form
des Programmierens
Klarer Programmierstil
Einfache, kurze, durchschaubare Programme Funktionale
Programmierung
Funktionales Denken
Fazit: Funktionale Programmierung ist gut / bestens geeignet für die Schule.
84
© KB 2002
Fun
kti
on
ale
Pro
gra
mm
ieru
ng
LiteraturLiteratur[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.