Schreibe Dein Programm - SDP
Schreibe Dein Programm - SDP
Schreibe Dein Programm - SDP
Dieses Buch wurde mit LATEX gesetzt, unter Verwendung der suftesi-Klasse von
Ivan Valbusa.
Inhaltsverzeichnis
3 Zusammengesetzte Daten 25
3.1 Computer konfigurieren 25
3.2 Record-Definitionen 29
3.3 Schablonen fr zusammengesetzte Daten 30
3.4 Grteltiere im Computer 31
4 Gemischte Daten 35
4.1 Gemischte Daten 35
4.2 Die Zucker-Ampel 39
8 Higher-Order-Programmierung 85
8.1 Higher-Order-Prozeduren auf Listen 85
8.2 Listen zusammenfalten 90
8.3 Anonyme Prozeduren 93
8.4 Prozedurfabriken 94
8.5 Der Schnfinkel-Isomorphismus 95
9 Zeitabhngige Modelle 99
9.1 Das Teachpack image2.ss 99
9.2 Zwischenergebnisse benennen 101
9.3 Modelle und Ansichten 102
9.4 Bewegung und Zustand 102
9.5 Andere Welten 103
13 Bume 149
13.1 Binrbume 149
13.2 Suchbume 152
13.3 Eigenschaften der Suchbaum-Operationen 157
Inhaltsverzeichnis 1
TBD
Schreibe Dein Programm! ist aus dem Vorgngerbuch Die Macht der
Abstraktion entstanden, das seinerseits aus dem Vorgngerbuch Vom
Problem zum Programm entstanden ist. Wir bemerkten nach der Verffent-
lichung vonDie Macht der Abstraktion, da wir das Buch einerseits einem
breiten Publikum einfach zugnglich machen wollten, andererseits kon-
tinuierlich Verbesserungen einarbeiten wollten. Beides war mit unserem
damaligen Verleger leider nicht zu machen. Entsprechend haben wir
uns entschieden, unsere Arbeit unter neuem Titel fortzufhren und
frei zugnglich zu machen. Es wird hoffentlich die letzte Titelnderung
bleiben.
Wir hatten zwar bereits viel Material aus Die Macht der Abstraktion bis
zur Unkenntlichkeit revidiert. Die TBD-Abschnitte in Schreibe Dein
Programm! kennzeichnen Stellen, deren Notwendigkeit bereits in Die
Macht der Abstraktion etabliert werde, die aber noch geschrieben werden
mssen.
Programmiersprache
http://www.deinprogramm.de/
Danksagungen
Wir, die Autoren, haben bei der Erstellung dieses Buchs immens von
der Hilfe anderer profitiert. Robert Giegerich, Ulrich Gntzer, Peter
Thiemann, Martin Plmicke, Christoph Schmitz und Volker Klaeren
machten viele Verbesserungsvorschlge zum Vorgngerbuch Vom Pro-
blem zum Programm.
Martin Gasbichler hielt einen Teil der Vorlesungen der letzten Infor-
matik I, half bei der Entwicklung der DMdA-Erweiterungen und ist
fr eine groe Anzahl von Verbesserungen verantwortlich, die sich
in diesem Buch finden. Eric Knauel, Marcus Crestani, Sabine Sperber,
Jan-Georg Smaus und Mayte Fleischer brachten viele Verbesserungs-
vorschlge ein. Andreas Schilling, Torsten Grust und Michael Hanus
hielten Vorlesungen auf Basis dieses Buches und brachten ebenfalls
viele Verbesserungen ein. Besonderer Dank gebhrt den Tutoren und
Studenten unserer Vorlesung Informatik I, die eine Flle wertvoller Kritik
und exzellenter Verbesserungsvorschlge lieferten.
Wir sind auerdem dankbar fr die Arbeit unserer Kollegen, die
Pionierarbeit in der Entwicklung von Konzepten fr die Programmier-
ausbildung geliefert haben. Eine besondere Stellung nehmen Matthias
Felleisen, Robert Bruce Findler, Matthew Flatt und Shriram Krishna-
murthi und ihr Buch How to Design Programs [?] ein, das entscheidende
didaktische Impulse fr dieses Buch gegegen hat. Felleisens Arbeit im
Rahmen des PLT-Projekts hat uns stark beeinflut; das PLT-DrRacket-
System ist eine entscheidende Grundlage fr die Arbeit mit diesem
Buch.
Herbert Klaeren
Michael Sperber
Tbingen, April 2014
1 Elemente des Programmierens
TBD
TBD
TDB
Abbildung 1.1. Das Interaktionsfenster von DrRacket
6 Kapitel 1
TBD
"z1 z2 . . . zn "
Dabei sind die zi beliebige einzelne Zeichen, auer " selbst. Beispiel:
"Mike was here!"
Mit Text kann DrRacket auch rechnen, und zwar mit der eingebauten
Prozedur string-append, die zwei Zeichenketten aneinanderhngt:
(string-append "Herbert" "Mike")
, "HerbertMike"
(string-append "Mike" " " "ist doof")
, "Mike ist doof"
Die eingebaute Prozedur string-length liefert die Anzahl der Buchsta-
ben in einer Zeichenkette:
(string-length "Herbert")
, 7
(string-length "Mike")
, 4
Die Prozeduren string->number und number->string konvertieren zwi-
schen Zahlen und den Zeichenketten, die diese darstellen:
(string->number "23")
, 23
(number->string 23)
, "23"
Programme knnen auch mit Bildern rechnen. Dazu wird eine Erwei-
terung zu DrRacket bentigt, ein sogenanntes Teachpack: Whlen Sie
dazu im Men Sprache den Punkt Teachpack hinzufgen und whlen
Sie image2.ss aus. Danach knnen Sie zum Beispiel ins Programm
schreiben:
Elemente des Programmierens 7
,
(circle 40 "solid" "green")
,
(star-polygon 20 10 3 "solid" "blue")
,
Diese Bilder sind Werte wie Zahlen und Zeichenketten auch. Insbeson-
dere knnen Sie mit Definitionen an Namen gebunden werden:
,
Bilder und Animationen mit Bildern werden ausfhrlich in Kapitel 9
behandelt.
TBD
1.6 Abstraktion
TBD
Parking-lot-cars ist eine Prozedur (das sagt der Pfeil -> zusammen
mit den Klammern);
parking-lot-cars akzeptiert zwei Argumente (vor dem Pfeil stehen
zwei Wrter);
die beiden Argumente sind natrliche Zahlen (natural);
die Prozedur liefert wieder eine natrliche Zahl (das ist das natural
hinter dem Pfeil).
(define parking-lot-cars
(lambda (vehicle-count wheel-count)
...))
; aus der Anzahl der Fahrzeuge und Rder die Anzahl der PKWs bestimmen
(: parking-lot-cars (natural natural -> natural))
(define parking-lot-cars
(lambda (vehicle-count wheel-count)
(/ (- m (* 2 n))
2)))
1.8 Testflle
Vertrauen ist gut aber Fehler passieren, auch bei sorgfltiger Program-
mierung. Angenommen, bei der Programmierung von parking-lot-cars
wre folgendes herausgekommen:
; aus der Anzahl der Fahrzeuge und Rder die Anzahl der PKWs bestimmen
(: parking-lot-cars (natural natural -> natural))
(define parking-lot-cars
(lambda (vehicle-count wheel-count)
(/ (- wheel-count (* 4 vehicle-count))
2)))
Elemente des Programmierens 11
Sehen Sie den Fehler auf den ersten Blick? Einfaches Ausprobieren ist
da vielleicht schneller:
(parking-lot-cars 1 4)
, 0
Bei der Entwicklung der Prozedur sollten also Testflle konstruiert
werden, die an ausgewhlten Beispielen berprfen, ob die gerade
programmierte Prozedur auch korrekt funktioniert. Testen ist eine un-
verzichtbare Ttigkeit des Programmierers.
Die Testflle werden am besten vor der Definition der Prozedur aufge-
stellt, denn wenn sie erst hinterher geschrieben werden, ist die Gefahr
gro, da unbewut das tatschliche Ergebnis eines Prozeduraufrufs
als das gewnschte eingegeben oder besonders kritische Beispiele weg-
gelassen werden. (In der industriellen Praxis ist sogar oft blich, da
jemand anderes als der Autor der Definitionen die Testflle schreibt.)
Es ist mhselig, bei der Programmentwicklung stndig Testflle in
die REPL einzutippen und durch einen Vergleich mit den erwarteten
Ergebnissen herauszubekommen, ob alles in Ordnung ist. In DrRacket
geht es deshalb auch einfacher. Testflle knnen zusammen mit den
erwarteten Ergebnissen wie folgt spezifiziert werden:
(check-expect (parking-lot-cars 1 4) 1)
(check-expect (parking-lot-cars 2 6) 1)
(check-expect (parking-lot-cars 10 28) 4)
Check-Fehler:
Der tatschliche Wert 0 ist nicht der erwartete Wert 1.
in Zeile 4, Spalte 0
Der tatschliche Wert -1 ist nicht der erwartete Wert 1.
in Zeile 5, Spalte 0
Der tatschliche Wert -6 ist nicht der erwartete Wert 4.
in Zeile 6, Spalte 0
Signaturverletzungen:
bekam -1 in Zeile 5, Spalte 14 , Signatur in Zeile 2, Spalte 40
verantwortlich: Prozedur in Zeile 9, Spalte 2
bekam -6 in Zeile 6, Spalte 14 , Signatur in Zeile 2, Spalte 40
verantwortlich: Prozedur in Zeile 9, Spalte 2
Wie schon in Kapitel ?? (Seite ??) bereits angedeutet, lassen sich die Da-
ten 3 und 9 nicht als Information interpretieren: Es gibt keinen Parkplatz
mit 3 Fahrzeugen und 9 Rdern zumindest nicht mit den Einschrn-
kungen der Aufgabenstellung auf vollberderte PKWs und Motorrder.
Die Prozedur parking-lot-cars strt dies allerdings wenig: Sie liefert
munter die Ausgabe 1.5. Allerdings meldet DrRacket eine Signaturver-
letzung, wenn es (parking-lot-cars 3 9) auswertet, da das Ergebnis
keine natrliche Zahl ist wie in der Signatur angegeben.
Das Programm sollte natrlich abseits der Signaturverletzung un-
sinnige Daten soweit mglich und praktikabel zurckweisen. Fr die
Eingabe (parking-lot-cars 3 16) htte es nmlich keine Signaturverlet-
zung gegeben, sondern es wre eine zunchst unschuldig aussehende
5 herausgekommen. Da htte es zuerst noch der Beobachtung bedurft,
dass unmglich 5 von 3 Fahrzeugen PKWs sein knnen. Noch feh-
len uns die Mittel, solche unsinnigen Eingaben zurckzuweisen; in
Abschnitt 2.8 werden wir dies nachholen.
TBD
TBD
Aufgaben
TBD
2 Fallunterscheidungen und
Verzweigungen
2.1 Fallunterscheidungen
nichts
Aufbauseminar
verkehrspsychologische Beratung
14 Kapitel 2
Fhrerscheinentzug
Dies ist eine Aufzhlung.
Wir fangen mit der Fragestellung an, welche Zwangsmanahme
fr eine bestimmte Punktezahl angeordnet wird. Zwangsmanahmen
gibt es nur drei: keine, Aufbauseminar und Fhrerscheinentzug, da
die verkehrspsychologische Beratung rein freiwillig ist. Entsprechend
zerfllt die Punkteskala in drei Teile: 0 13, 14 17 und ab 18. Die
Punktezahl gehrt also zu einer von drei Kategorien.
Wenn die Menge, aus der ein Wert kommt, in eine feste Anzahl von
Kategorien aufgeteilt wird und bei einem Wert nur die Kategorie zhlt,
ist diese Menge durch eine Fallunterscheidung definiert. Aufzhlungen
sind damit auch Fallunterscheidungen.
Eine Funktion, die aus einem Punktestand die Zwangsmanahme
ermittelt, sieht folgendermaen aus:
nichts
falls p 13
def
m( p) = Aufbauseminar falls p 14, p 17
Fhrerscheinentzug falls p 18
Tests gibt es auch in Scheme; sie sind dort Ausdrcke. Hier ein Beispiel:
(<= -5 0)
, #t
(<= -5 0) ist die Scheme-Schreibweise fr 5 0. Als Frage gestellt
oder Aussage aufgefat, ist 5 0 wahr. #t steht fr true oder
wahr. <= ist eine eingebaute Prozedur, welche auf kleiner gleich
testet. (Ebenso gibt es auch = fr =, < fr <, > fr > und >= fr .)
Ein Test kann auch negativ ausfallen:
(<= 5 0)
, #f
#fsteht fr false oder falsch. Wahr und falsch heien zusam-
men boolesche Werte oder auch Wahrheitswerte.1
Analog zu = fr Zahlen knnen Zeichenketten mit string=? vergli-
chen werden:
(string=? "Mike" "Mike")
, #t
(string=? "Herbert" "Mike")
, #f
#t
, #t
#f
, #f
Auch mit booleschen Werten kann DrRacket rechnen. Ein Ausdruck der
Form
(and e1 e2 . . . e n )
ergibt immer dann #t, wenn alle ei #t ergeben, sonst #f. Bei zwei
Operanden e1 und e2 ergibt (and e1 e2 ) immer dann #t, wenn e1 und e2
#t ergeben:
(and #t #t)
, #t
(and #f #t)
, #f
(and #t #f)
, #f
(and #f #f)
, #f
Entsprechend gibt es Ausdrcke der Form
(or e1 e2 . . . e n )
die immer dann #t ergeben, wenn einer der ei #t ergibt, sonst #f. Bei
zwei Operanden e1 und e2 ergibt (or e1 e2 ) immer dann #t, wenn e1
oder e2 #t ergeben:
(or #t #t)
, #t
(or #f #t)
, #t
(or #t #f)
, #t
(or #f #f)
, #f
Des weiteren gibt es noch eine eingebaute Prozedur not, die einen
booleschen Wert umdreht, sich also folgendermaen verhlt:
(not #f)
, #t
(not #t)
, #f
Die Konstruktion one-of bei Signaturen ist neu: In der obigen Signa-
tur bedeutet es, da der Aggregatzustand einer der in der one-of-
Signatur angegegebenen Werte ist, also eine der Zeichenketten "nichts",
"Aufbauseminar" und "Fhrerscheinentzug".
Hier sind zwei mgliche Testflle:
(check-expect (points-must-do 14) "Aufbauseminar")
(check-expect (points-must-do 18) "Fhrerscheinentzug")
Jetzt brauchen wir, wie bei der mathematischen Funktion m aus Ab-
schnitt 2.1, eine Verzweigung, nur eben in Scheme. Abbildung 2.1
beschreibt das dafr zustndige cond. Es ist also von vorneherein klar,
da eine cond-Form im Rumpf von points-must-do auftauchen mu:
(define points-must-do
(lambda (p)
(cond ... p ...)))
(cond
(t1 a1 )
(t2 a2 )
...
( t n 1 a n 1 )
(else an )))
Wir bentigen jetzt fr jeden cond-Zweig einen Test, der die entspre-
chende Kategorie bei den Punkten identifiziert. Dazu mssen wir nur
die entsprechenden Bedingungen aus der mathematischen Fassung
nach Scheme bersetzen. Heraus kommt folgendes:
(define points-must-do
(lambda (p)
(cond
((<= p 13) ...)
((and (>= p 14) (<= p 17)) ...)
((>= p 18) ...))))
Der letzte Schritt ist einfach wir fgen fr jeden Zweig die zum Test
passende Manahme ein:
(define points-must-do
(lambda (p)
(cond
((<= p 13) "nichts")
((and (>= p 14) (<= p 17)) "Aufbauseminar")
((>= p 18) "Fhrerscheinentzug"))))
Fertig knnte man meinen. Wenn Sie das Programm in der REPL
laufen lassen, meldet DrRacket zwei bestandene Tests. Allerdings fllt
Ihnen vielleicht auf, da das Programm im Definitionsfenster nach dem
Lauf so aussieht:
(define points-must-do
(lambda (p)
(cond
((<= p 13) "nichts" )
18 Kapitel 2
Das "nichts" ist farbig unterlegt, weil DrRacket diesen Ausdruck noch
nie ausgewertet hat. Das ist nicht gut, weil es heit, da der entspre-
chende Zweig durch die Tests noch nicht strapaziert wurde er ist
also mglicherweise fehlerhaft. Anders gesagt: Die Abdeckung des Pro-
gramms durch die Tests ist unvollstndig. Wenn wir einen Testfall fr
den ersten Zweig ergnzen, verschwindet die farbige Unterlegung:
(check-expect (points-must-do 0) "nichts")
Trotzdem ist der bestehende Satz an Tests noch suboptimal wer sagt
schlielich, da das Programm zum Beispiel bei 13 Punkten, also genau
an der Grenze zwischen dem ersten und zweiten Zweig, das richtige
tut. Wir sollten fr diese Eckflle auch Testflle bereitstellen sowie einen
Testfall, der sicherstellt, da auch bei Punktzahlen oberhalb von 18
immer noch der Fhrerschein entzogen wird:
(check-expect (points-must-do 13) "nichts")
(check-expect (points-must-do 17) "Aufbauseminar")
(check-expect (points-must-do 100) "Fhrerscheinentzug")
Bei der Konstruktion der Prozedur points-must-do haben wir ein be-
stimmtes Schema angewendet. Dieses Schema geht zunchst von fol-
gender Frage aus:
Wieviele Kategorien gibt es bei der Fallunterscheidung?
Ist die Frage beantwortet durch eine Zahl n knnen wir bereits
etwas Code in den Rumpf schreiben, nmlich eine Verzweigung mit n
Zweigen:
(define p
(lambda (...)
(cond
(... ...)
... (n Zweige)
(... ...))))
Solch ein Rumpf mit Lcken (die Ellipsen ... stehen fr noch zu
ergnzende Programmteile) ist eine Schablone. Wir, die Autoren, empfeh-
len Ihnen, die Schablone bereits hinzuschreiben, wenn Sie die Anzahl
der Kategorien bereits kennen, noch bevor Sie weiter ber die Pro-
blemstellung nachdenken. Das hilft oft, etwaige Denkblockaden zu
lsen.
Die Schablone folgt in diesem Fall aus der Struktur der Daten, also
dem Ergebnis der Datenanalyse. Es gibt noch andere Arten von Daten,
jede mit ihrer eigenen Schablone. Diese werden wir im Rest des Buchs
entwickeln. Fr alle folgenden Konstruktionsanleitungen gilt deshalb
folgendes Mantra:
Fallunterscheidungen und Verzweigungen 19
Wenn die Auswertung den Test im zweiten Zweig erreicht, steht schon
fest, da die Punktezahl 14 ist, da der Test (<= p 13) fehlgeschlagen
ist. Diese Bedingung knnten wir also weglassen. Ebenso der letzte Test,
der dadurch, da (<= p 17) #f ergeben hat, immer #t ergibt. Allerdings
sind die Zweige damit von ihrer Reihenfolge abhngig: Wenn wir
zum Beispiel die ersten beiden Zweige vertauschten, funktioniert die
Prozedur nicht mehr richtig. In Fllen wie diesen, wo vollstndige
Tests einfach zu formulieren sind, empfiehlt es sich, dies auch zu tun.
(and a b c)
7 (if a (and b c) #f)
7 (if a (if b (and c) #f) #f)
7 (if a (if b (if c (and) #f) #f) #f)
7 (if a (if b (if c #t #f) #f) #f)
Ebenso lassen sich or-Ausdrcke immer in if-Ausdrcke bersetzen,
und zwar mit folgender bersetzung:
(or) 7 #f
(or e1 e2 . . .) 7 (if e1 #t (or e2 . . .))
Beispiel:
(or a b c)
7 (if a #t (or b c))
7 (if a #t (if b #t (or c)))
7 (if a #t (if b #t (if c #t (or))))
7 (if a #t (if b #t (if c #t #f)))
2.7 Signaturdefinitionen
Der one-of-Teil der Signatur macht sich da ganz schn breit, zumal
er sich weitgehend deckt mit dem entsprechenden Teil der Signatur
von points-must-do auf Seite 16. Entsprechend sollten wir genauso wie
bei anderen Werten der Signatur fr Flensburg-Manahmen einen
Namen geben. Das geht mit einer fast ganz normalen Definition:
(define action
(signature
(one-of "nichts"
"Aufbauseminar"
"verkehrspsychologische Beratung"
"Fhrerscheinentzug")))
22 Kapitel 2
Entsprechend Mantra 3 versuchen wir, durch mehr Tests als noch bei
points-must-do bessere Abdeckung zu erzielen:
(define improve-points
(lambda (p a)
...))
(define improve-points
(lambda (p a)
(cond
(... ...)
(... ...)
(... ...)
(... ...)
(... ...))))
Wir fangen mal mit den einfachsten Fllen an unten und oben in der
Punkteskala, wo sich nichts bewegt:
(define improve-points
(lambda (p a)
(cond
((<= p 3) p)
((and (>= p 4) (<= p 8)) ...)
((and (>= p 9) (<= p 13)) ...)
((and (>= p 14) (<= p 17)) ...)
((>= p 18) p))))
Im zweiten Zweig zwischen vier und acht Punkten zhlt nur ein
Aufbauseminar, alle anderen Manahmen bringen nichts. Darum ist
hier eine binre Verzweigung angemessen:
(define improve-points
(lambda (p a)
(cond
...
((and (>= p 4) (<= p 8))
(if (string=? a "Aufbauseminar")
(- p 4)
p))
...)))
Noch einmal zurck zum Parkplatzproblem, das wir auf Seite ?? pro-
grammiert hatten. In Abschnitt 1.9 auf Seite 12 hatten wir bereits be-
merkt, da die Prozedur parking-lot-cars auch fr unsinnige Daten
frhlich ebenso unsinnige Ergebnisse ermittelt.
Auf Seite ?? wurde bereits eine Bedingung fr sinnvolle Daten formu-
liert: Wenn n die Anzahl der Fahrzeuge und m die Anzahl der Rder
ist, dann mu m gerade sein sowie 2n m 4n gelten. Wir knnen
das in einer binren Verzweigung zum Ausdruck bringen:
(define parking-lot-cars
(lambda (vehicle-count wheel-count)
(if (and (even? wheel-count)
(<= (* 2 vehicle-count) wheel-count)
(<= wheel-count (* 4 vehicle-count)))
(/ (- wheel-count (* 2 vehicle-count))
2)
...)))
Die eingebaute Prozedur even? akzeptiert eine ganze Zahl und liefert
#t, falls die Zahl gerade ist und #f, falls sie ungerade ist solche und
viele andere ntzliche Prozeduren finden Sie in der Dokumentation
im Hilfezentrum unter Sprachebenen und Material zu Die Macht der
Abstraktion im Abschnitt Primitive Operationen.
Nur was tun im Fehlerfall? Dazu gibt eine eingebaute Prozedur
violation, die eine Fehlermeldung als Zeichenkette akzeptiert und,
wenn sie aufgerufen wird, das Programm abbricht und die Fehlermel-
dung ausdruckt. Parking-lot-cars sieht dann vollstndig so aus:
(define parking-lot-cars
(lambda (vehicle-count wheel-count)
(if (and (even? wheel-count)
(<= (* 2 vehicle-count) wheel-count)
(<= wheel-count (* 4 vehicle-count)))
(/ (- wheel-count (* 2 vehicle-count))
2)
(violation "unsinnige Daten"))))
Natrlich sollten wir auch den Fehlerfall testen das geht nicht mit
check-expect, das ja erwartet, da ein Testausdruck einen ordnungs-
gemen Wert liefert. Fr Fehlerflle gibt es check-error, das Testflle
erzeugt, die dann bestanden sind, wenn die Auswertung einen Fehler
liefert:
(check-error (parking-lot-cars 10 10)) ; zu wenige Rder
(check-error (parking-lot-cars 3 9)) ; ungerade Rderzahl
(check-error (parking-lot-cars 2 10)) ; zu viele Rder
Aufgaben
TBD
3 Zusammengesetzte Daten
TBD
Mit anderen Worten: mehrere Dinge werden zu einem zusammenge-
setzt. Eine andere Betrachtungsweise ist, da ein einzelnes Ding durch
mehrere Eigenschaften charakterisiert ist.
In Scheme lassen sich solche zusammengesetzte Daten durch Records
darstellen. Ein Record ist wie ein Behlter mit mehreren Fchern, in
denen die Bestandteile der Daten untergebracht sind.
Prozessor
RAM
Festplatte
Natrlich besteht ein Computer auch noch aus anderen Teilen, aber
diese Teile sind (zumindest in diesem Beispiel) immer gleich, sie knnen
vom Kunden nicht ausgewhlt werden. In einer Bestellung mu der
26 Kapitel 3
Kunde also nur diese drei Bestandteile angeben. Wir nehmen an, da
es beim Prozessor nur auf den Namen (Athlon, Xeon, Cell, . . . )
ankommt, beim RAM nur auf die Gre in Gigabyte, und auch bei der
Festplatte nur auf die Gre in Gigabyte. Eine vereinfachte Darstellung
knnte so aussehen:
Feld Komponente
Prozessor "Cell"
Computer:
RAM 2
Festplatte 250
Sie macht also aus einer Zeichenkette und zwei Zahlen einen Wert
der eingebauten Sorte computer der Computer-Records. Die DrRacket-
REPL druckt Record-Werte mit der Schreibweise #<record:... ...> aus,
damit Sorte und Komponenten sichtbar werden.
Computer sind Werte wie andere auch und lassen sich zum Beispiel
an Variablen binden:
(define gamer (make-computer "Cell" 4 1000)) ; Cell, 4 Gbyte RAM, 1000 Gbyte Festplat
gamer
, #<record:computer "Cell" 4 1000>
Zusammengesetzte Daten 27
(define workstation (make-computer "Xeon" 2 500)) ; Xeon, 2 Gbyte RAM, 500 Gbyte Festplatte
workstation
, #<record:computer "Xeon" 2 500>
Da die Prozedur make-computer einen Computer konstruiert, heit sie
auch Konstruktor. Fr das Zerlegen von Computern sind die Prozeduren
computer-processor, computer-ram und computer-hard-drive zustndig:
(computer-processor gamer)
, "Cell"
(computer-ram gamer)
, 4
(computer-hard-drive gamer)
, 1000
Mit Hilfe des Konstruktors und der Selektoren kann der Programmierer
weitergehende Prozeduren definieren. Fr den Anfang knnte das eine
Prozedur sein, die den Gesamtspeicher eines Computers berechnet,
also Hauptspeicher und Festplattenspeicher zusammen. Eine solche
Prozedur mte Kurzbeschreibung und Signatur wie folgt haben:
; Gesamtspeicher berechnen
(: total-memory (computer -> rational))
Fertig!
Total-memory ist ein Beispiel fr eine Prozedur, die einen Record ak-
zeptiert. Umgekehrt gibt es auch Prozeduren, die Records produzieren.
Angenommen, unser Computerhndler bietet neben der Einzelkonfigu-
ration von Prozessor, Hauptspeicher und Festplatte einige Standardmo-
delle an sagen wir, ein Billigmodell, ein Modell fr Profis (was immer
ein Profi sein mag) und ein Modell fr Computerspieler. Je nach-
dem, welches der Modelle der Kunde auswhlt, mu die entsprechende
Konfiguration zusammengesetzt werden. Fr die Standardkonfigurati-
on gibt es drei feste Mglichkeiten, es handelt sich hier also um eine
Aufzhlung.
Eine Prozedur, die zu einer Standardkonfiguration den passenden
Computer fertigt, knnte folgende Kurzbeschreibung und Signatur
haben:
; Standard-Computer zusammenstellen
(: standard-computer ((one-of "cheap" "professional" "game") -> computer))
Bei den Tests der Zweige mssen wir k mit den Elementen der Aufzh-
lung vergleichen. Da es sich um Zeichenketten handelt, nehmen wir
dazu string=?:
(define standard-computer
(lambda (k)
(cond
((string=? k "cheap") ...)
((string=? k "professional") ...)
((string=? k "game") ...))))
(define standard-computer
(lambda (k)
(cond
((string=? k "cheap")
(make-computer ... ... ...))
((string=? k "professional")
(make-computer ... ... ...))
((string=? k "game")
(make-computer ... ... ...)))))
Jetzt mssen wir nur noch die Argumente fr die Aufrufe von make-computer
zur Verfgung stellen. Fr jeden Aufruf sind das, wie gehabt, der Pro-
zessor, die Gre des Hauptspeichers und die Gre der Festplatte.
Die entsprechenden Angaben knnen wir zum Beispiel den Testfllen
entnehmen, und es kommt folgendes dabei heraus:
(define standard-computer
(lambda (k)
(cond
((string=? k "cheap")
(make-computer "Sempron" 2 500))
((string=? k "professional")
(make-computer "Xeon" 4 1000))
((string=? k "game")
(make-computer "Quad" 4 750)))))
Fertig!
3.2 Record-Definitionen
; Eine kartesische Koordinate in der Ebene besteht aus einer X- und Y-Koordinate.
(define-record-procedures t
c p
(s1 . . . sn ))
1. Stellen Sie fest, von welchen Komponenten des Records das Ergebnis
der Prozeduren abhngt.
2. Fr jede dieser Komponenten, schreiben Sie (s c) in die Schablone,
wobei s der Selektor der Komponente und c der Name des Record-
Parameters ist.
3. Vervollstndigen Sie die Schablone, indem Sie einen Ausdruck kon-
struieren, in dem die Selektor-Anwendungen vorkommen.
(define-record-procedures dillo
make-dillo dillo?
(dillo-weight dillo-alive?))
Fangen wir mit dem unangenehmen Teil an, dem berfahren, das aus
einem lebenden Grteltier ein totes macht. Hier Kurzbeschreibung und
Signatur:
; Grteltier berfahren
(: run-over-dillo (dillo -> dillo))
(define run-over-dillo
(lambda (d)
(make-dillo ... ...)
... (dillo-weight d) ...
... (dillo-alive? d) ...))
Das Grteltier ist nach dem berfahren auf jeden Fall tot. Da es keine
Rolle spielt, ob das Grteltier vorher lebendig war oder nicht, knnen
wir den Selektoraufruf (dillo-alive? d) verwerfen:
(define run-over-dillo
(lambda (d)
(make-dillo (dillo-weight d)
#f)))
Fertig!
Nchste Aufgabe: Grteltier fttern. Die Standard-Futter-Portion ist
dabei 500g, und das Grteltier nimmt durch die Ftterung um das
entsprechende Gewicht zu. Hier Kurzbeschreibung und Signatur:
; Grteltier mit 500g Futter fttern
(: feed-dillo (dillo -> dillo))
Auch bei feed-dillo ist relevant, was es mit toten Grteltieren macht:
Tote Grteltiere fressen nicht, entsprechend nehmen sie auch nicht zu,
wenn man ihnen Futter anbietet:
(check-expect (feed-dillo d2) d2)
Beim zweiten Testfall haben wir gesehen, da, was feed-dillo betrifft,
die Grteltiere in zwei verschiedene Gruppen fallen: Feed-dillo verhlt
sich bei lebenden Grteltieren anders als bei toten: eine Fallunterschei-
dung. Entsprechend brauchen wir eine Verzweigung im Rumpf. Da
sich der Fall Grteltier tot dadurch definiert, da der Fall Grteltier
lebendig nicht eintritt, ist die binre Verzweigung angemessen:
(define feed-dillo
(lambda (d)
(if (dillo-alive? d)
...
...)
(make-dillo ... ...)
... (dillo-weight d) ...
(define feed-dillo
(lambda (d)
(if (dillo-alive? d)
...
d)
(make-dillo ... ...)
... (dillo-weight d) ...
(define feed-dillo
(lambda (d)
(if (dillo-alive? d)
(make-dillo (+ (dillo-weight d) 500)
#t)
d)))
Fertig!
Aufgaben
TBD
4 Gemischte Daten
In der Einleitung war die Rede von Papageien: die benutzen wir, um
gemischte Daten einzufhren. Vorher mssen wir jedoch Papageien
mit den bekannten Mitteln definieren; wir versuchen es, kurz und
schmerzlos zu machen:
Wir interessieren uns vor allem fr sprechende Papageien. Genau
wie bei Grteltieren interessiert uns das Gewicht, aber wir nehmen an,
da Papageien in der Regel nicht auf texanischen Highways berfahren
werden, da sie immer lebendig sind. Hier die Datendefinition:
(define-record-procedures parrot
make-parrot parrot?
(parrot-weight parrot-sentence))
Wir knnen einen Papagei hnlich wie ein Grteltier fttern nur
die Portion ist kleiner, wir nehmen 50 g an. Kurzbeschreibung und
Signatur:
Testflle:
Gerst:
(define feed-parrot
(lambda (p)
...))
Schablone:
(define feed-parrot
(lambda (p)
(make-parrot ... ...)
... (parrot-weight p) ...
... (parrot-sentence p) ...))
(define feed-parrot
(lambda (p)
(make-parrot (+ (parrot-weight p) 50)
(parrot-sentence p))))
ein Grteltier
ein Papagei
Die Formulierung eins der folgenden ist der klare Hinweis fr eine neue
Form der Organisation von Daten: gemischte Daten. Entsprechend ist es
durchaus sinnvoll, nach dem Gewicht eines Tiers zu fragen oder ein
Tier zu fttern, was wir im folgenden auch vorhaben.
Die Beschreibung des Begriffs Tier ist bereits als Datendefinition
geeignet, und mu fr Inklusion im Programm nur als Kommentar
umformatiert werden:
Gemischte Daten 37
Wir brauchen also eine Definition fr die Signatur animal. Diese sieht
folgendermaen aus:
(define animal
(signature
(mixed dillo parrot)))
(define animal-weight
(lambda (a)
(cond
(... ...)
(... ...))))
38 Kapitel 4
Wir brauchen als nchstes einen Test, der Grteltiere identifiziert. Jetzt
endlich kommen die auf Seite ?? eingefhrten Prdikate dillo? und
parrot? ins Spiel, die durch die Record-Definitionen definiert wurden:
(define animal-weight
(lambda (a)
(cond
((dillo? a) ...)
((parrot? a) ...))))
(define animal-weight
(lambda (a)
(cond
((dillo? a) (dillo-weight a))
((parrot? a) (parrot-weight a)))))
Fertig!
Aus diesem Beispiel ergibt sich direkt eine Konstruktionsanleitung
fr gemischte Daten. Zunchst zur Daten- und Signaturdefinition:
Gemischte Daten liegen vor, wenn Sie eine Datensorte durch eine
Formulierung der Form ein X ist eins der folgenden beschreiben
knnen: Diese Formulierung ist die Datendefinition.
Stellen Sie fest, wieviele unterschiedliche Flle die Sorte fr die ge-
mischten Daten hat.
Schreiben Sie eine Signaturdefinition der folgenden Form unter die
Datendefinition:
(define S
(signature
(mixed S1 S2 . . . Sn )))
Uns geht es nicht darum, ob solch eine Kennzeichnung sinnvoll ist oder
nicht, oder ob Zucker gesund oder ungesund ist. Auf jeden Fall sind
trotz der Bemhungen der Europischen Union die Bezeichnungen un-
einheitlich. Technisch gesehen ist die Ampel natrlich redundant, wenn
der Zuckergehalt in Gramm angegeben ist. Manchmal ist allerdings
der Zuckergehalt auch separat fr Fruktose und Glukose angegeben.
Ein Computerprogramm knnte aber den Umgang erleichtern, indem
es jede Angabe auf einer Lebensmittelpackung Zucker in Gramm
insgesamt, Fruktose und Glukose separat sowie die Ampel in die
einheitliche Ampel-Form bringt.
Zunchst die Datenanalyse:
Den Zuckergehalt in Gramm insgesamt kann eine (rationale) Zahl
reprsentieren.
Die Zuckerangabe mit Fruktose und Glukose separat ist zusammen-
gesetzt, mit zwei Komponenten. Hier Daten- und Record-Definition
dazu sowie die Signaturen fr die Record-Prozeduren:
Die Angabe ber den Zuckergehalt kann jede der drei oben genannten
Formen annehmen:
; Eins Zuckergehalt ist eins der folgenden:
; - Gewicht in Gramm (rational)
; - Zuckeranteile (sugars)
; - Ampelbezeichnung (traffic-light)
(define sugar-content
(signature
(mixed rational
sugars
traffic-light)))
Als nchstes wenden wir die Schablone fr Prozeduren an, die gemisch-
te Daten akzeptieren. Wir brauchen eine Verzweigung mit sovielen
Zweigen wie sugar-content Flle hat, also drei:
(define sugar-traffic-light
(lambda (f)
(cond
(... ...)
(... ...)
(... ...))))
Als nchstes brauchen wir Tests fr die drei Flle. Fr den zweiten
Fall ist das einfach, da es sich um sugars-Records handelt: da gibt es
das Prdikat sugars?. Beim ersten Fall handelt es sich aber um eine
rationale Zahl, beim dritten um eine Zeichenkette beides eingebaute
Datensorten. Fr diese gibt es die eingebauten Prdikate rational? und
string? Abbildung 4.1 zhlt noch mehr eingebaute Prdikate auf.
(define sugar-traffic-light
(lambda (f)
(cond
((rational? f)
(cond
(... ...)
(... ...)
(... ...)))
((sugars? f) ...)
((string? f) ...))))
Gerst:
Gemischte Daten 43
(define sugar-weight->traffic-light
(lambda (w)
...))
Den Rumpf haben wir ja schon geschrieben, wir mssen ihn nur noch
hierher bewegen und f in w umbenennen. Das DrRacket-System bie-
tet dazu nach einem Klick auf Syntaxprfung die Mglichkeit, mit
einem Rechtsklick auf den Parameter f ein Men aufzuklappen, das
unter anderem die Auswahl f umbenennen anbietet. DrRacket sorgt
dann dafr, dass alle zugehrigen Vorkommen von f in gleicher Weise
umbenannt werden.
(define sugar-weight->traffic-light
(lambda (w)
(cond
((< w 5) "grn")
((and (>= w 5) (<= w 12.5)) "gelb")
((> w 12.5) "rot"))))
(define sugar-traffic-light
(lambda (f)
(cond
((rational? f)
(sugar-weight->traffic-light f))
((sugars? f) ...)
((string? f) ...))))
(define sugar-traffic-light
(lambda (f)
(cond
((rational? f)
(sugar-weight->traffic-light f))
((sugars? f) ... (sugars-fructose f) ...
... (sugars-glucose f) ...)
((string? f) ...))))
Wir mssen Fruktose- und den Glukose-Anteil addieren und die Summe
dann ebenfalls entsprechend der Tabelle vom Anfang in eine Ampel-
farbe umwandeln. Aber halt! Genau fr das Umwandeln der Zahl
aus der Tabelle in eine Ampelfarbe haben wir ja gerade die Hilfsproze-
dur sugar-weight->traffic-light geschrieben, und diese knnen wir
erneut zum Einsatz bringen:
(define sugar-traffic-light
(lambda (f)
(cond
((rational? f)
(sugar-weight->traffic-light f))
44 Kapitel 4
((sugars? f)
(sugar-weight->traffic-light (+ (sugars-fructose f)
(sugars-glucose f))))
((string? f) ...))))
Bleibt der letzte Fall der ist zum Glck trivial, da es sich schon um
eine Farbe handelt, Die mu sugar-traffic-light nur zurckgeben:
(define sugar-traffic-light
(lambda (f)
(cond
((rational? f)
(sugar-weight->traffic-light f))
((sugars? f)
(sugar-weight->traffic-light (+ (sugars-fructose f)
(sugars-glucose f))))
((string? f) f))))
Fertig!
Aufgaben
Die bisher betrachteten Daten hatten alle immer eine feste Gre
die Anzahl der Komponenten zusammengesetzter ist fest, ebenso wie
die Anzahl der Flle bei Fallunterscheidungen oder gemischten Daten.
Das reicht nicht fr alle Anwendungen: Die Bcher im Regal, die
Wagen eines Zuges, die Fotos im Album sind allesamt in ihrer Anzahl
variabel. Fr die Reprsentation solcher Informationen wird also eine
neue Art der Datendefinition bentigt, welche die schon bekannten
zusammengesetzten und gemischten Daten ergnzt: der Selbstbezug.
Selbstbezge knnen benutzt werden, um solche Daten variabler Gre
abzubilden, insbesondere in sogenannten Listen.
; - einer Liste
(define-record-procedures pair
make-pair pair?
(first rest))
Jetzt kommt der entscheidende Punkt: Paare sind auch Listen, Listen
sind also gemischte Daten:
Die Signatur empty-list ist bereits eingebaut und pat auf die lee-
re Liste empty (und nichts sonst). (Der Name list ist in den DMdA-
Lehrsprachen bereits vergeben, darum heit die Signatur a-list.) Jetzt
ist es mglich, eine Signatur fr make-pair sowie die anderen Prozedu-
ren der Record-Definition von pair zu vergeben:
Zu einer Liste mit zwei Elementen gehren also zwei Paare. Entspre-
chend fr drei Elemente:
Programmieren mit Listen 47
Diesmal sind drei Paare im Spiel. Die Liste wird jeweils terminiert
durch die leere Liste. Abbildung 5.1 zeigt, wie die Listen aussehen, wenn
sie wie andere zusammengesetzte Daten als Tabellen dargestellt sind
das steht fr die leere Liste. Das sieht aus wie ineinandergeschachtelte
russische Puppen und entspricht damit nicht der gngigen Intuition,
wie Listen aufgebaut sind, aber es funktioniert. Fr viel mehr als drei
Elemente funktioniert die Darstellungsweise allerdings nicht: Darum
bevorzugen wir ab hier sogenannte Zeigerdiagramme, bei denen alle
Paare gleich gro dargestellt sind und ein Pfeil zeigt, da ein Paar
die rest-Komponente eines anderen Paares bildet. Abbildung 5.2 zeigt
das Pfeildiagramm, das Abbildung 5.1 entspricht; es pat besser zur
gngigen Intuition von Listen.
Als erstes Beispiel fr das Programmieren mit Listen schreiben wir eine
Prozedur, die eine Liste von Zahlen akzeptiert und deren Summe liefert.
Dazu werden erst einmal einige Beispiele solcher Listen bentigt:
; Liste mit den Zahlen 1 2 3
(define n1 (make-pair 1 (make-pair 2 (make-pair 3 empty))))
; Liste mit den Zahlen e und pi
(define n2 (make-pair 2.7183 (make-pair 3.14159 empty)))
; Liste mit den Zahlen 2 3 5 7
(define n3 (make-pair 2 (make-pair 3 (make-pair 5 (make-pair 7 empty)))))
(Es empfiehlt sich, als Bezeichner fr Listen nicht einfach nur ein l zu
verwenden, da es in vielen Schriftarten der Ziffer 1 hnlich sieht.)
Zur Erinnerung: Listen sind zunchst gemischte Daten die Definiti-
on von a-list benutzt mixed mit zwei Fllen. Entsprechend kommt die
Konstruktionsanleitung fr gemischte Daten zur Anwendung:
(define list-sum
(lambda (lis)
(cond
(... ...)
(... ...))))
Als nchstes sollten wir die Tests ergnzen, die auf die leere Liste
bzw. Paare testen. Fr empty hat dieses Buch Ihnen den Test bisher
vorenthalten: Das eingebaute Prdikat empty? liefert #t fr die leere
Liste und #f fr jeden anderen Wert. Fr Paare ist das Prdikat pair?
bereits von der Record-Definition definiert:
(define list-sum
(lambda (lis)
(cond
((empty? lis) ...)
((pair? lis) ...))))
(define list-sum
(lambda (lis)
(cond
((empty? lis) ...)
((pair? lis)
... (first lis) ... (rest lis) ...))))
Jetzt knnen wir ans Ausfllen der beiden Zweige gehen: Die erste
Ellipse mu die Frage beantworten, was die Summe der leeren Liste
sein soll. Diese Frage ist bei nahezu allen Prozeduren relevant, die Listen
akzeptieren, es empfiehlt sich darum grundstzlich, einen Testfall fr
die leere Liste zu formulieren:
Programmieren mit Listen 49
Bleibt der zweite Zweig mit den Paaren. Hier hilft es, die beiden
Selektor-Aufrufe (first lis) und (rest lis) auf die Daten zurckzu-
beziehen. (first lis) liefert fr die drei Beispiellisten folgende Werte:
(first n1)
, 1
(first n2)
, 2.7183
(first n3)
, 2
Das ist jeweils das erste Element kein Wunder, da der Selektor first
heit. Nun fr rest:
(rest n1)
, #<record:pair 2 #<record:pair 3 #<empty-list>>>
(rest n2)
, #<record:pair 3.14159 #<empty-list>>
(rest n3)
, #<record:pair 3 #<record:pair 5 #<record:pair 7 #<empty-list>>>>
Dies sind jeweils Listen mit allen Elementen auer dem ersten, also quasi
den Rest daher der Name rest fr den Selektor.
Zurck zur Schablone: Was knnen wir mit dem ersten Element der
Liste und dem Rest der Liste anfangen? Hier kommt ein besonderer
Trick zum Zug da der Rest der Liste wieder eine Liste ist, knnen wir
von der Summe des Rests sprechen. Wenn diese Summe bekannt ist
also die Summe aller Elemente auer des ersten, dann knnten wir (und
das Programm auch) die Gesamtsumme ermitteln, indem wir auf diese
Summe das noch fehlende erste Element addieren. Die Summe aller
Elemente auer des ersten knnen wir so aufschreiben:
(list-sum (rest lis))
Entsprechend die Summe des ersten Elements und der Summe des
Rests:
(+ (first lis) (list-sum (rest lis)))
(define list-sum
(lambda (lis)
(cond
((empty? lis) 0)
((pair? lis)
(+ (first lis) (list-sum (rest lis)))))))
(define proc
(lambda (lis)
(cond
((empty? lis) ...)
((pair? lis)
... (first lis)
... (proc (rest lis)) ...))))
Jetzt wo wir die Schablone haben, gehen wir noch ein weiteres Beispiel
durch, bei dem wir sie von vornherein anwenden: Gefragt ist eine
Prozedur, die eine Liste von Zahlen akzeptiert und feststellt, ob alle
Listenelemente positiv sind. Die Prozedur beantwortet eine Ja/Nein-
Frage, die damit auch die Kurzbeschreibung bildet:
; sind alle Zahlen aus einer Liste positiv?
Fr Testflle stehen die leere Liste sowie die drei Beispiellisten n1, n2
und n3 aus dem vorherigen Beispiel zur Verfgung:
(check-expect (all-positive? empty) #t)
(check-expect (all-positive? n1) #t)
(check-expect (all-positive? n2) #t)
(check-expect (all-positive? n3) #t)
Der empty-Testfall ist vielleicht etwas verwirrend: In der Tat sind alle
Elemente der leeren Liste positiv. Eine andere Art dies zu sagen wre,
da kein Element der leeren Liste nicht positiv ist.
Diese Testflle reichen sichtlich nicht aus, da alle #t ergeben sollen:
Diese wrden auch von folgender Prozedur erfllt:
Programmieren mit Listen 51
(define all-positive?
(lambda (lis)
#t))
(define all-positive?
(lambda (lis)
...))
(define all-positive?
(lambda (lis)
(cond
((empty? lis) ...)
((pair? lis)
... (first lis)
... (all-positive? (rest lis)) ...))))
Das Ergebnis im ersten Zweig wird durch den ersten Testfall diktiert: #t.
Wie schon zuvor machen wir uns die Bedeutung der Ausdrcke im pair-
Zweig klar: (first lis) ist das erste Element der Liste. (all-positive?
(rest lis)) besagt, ob alle Elemente des Rests von lis positiv sind. Es
sind nur dann alle Elemente von lis positiv, wenn (first lis) positiv
ist und (all-positive? (rest lis)) als Ergebnis #t liefert. Damit ist
klar, wie die beiden Ausdrcke kombiniert werden mssen:
(define all-positive?
(lambda (lis)
(cond
((empty? lis) #t)
((pair? lis)
(and (> (first lis) 0)
(all-positive? (rest lis)))))))
5.3 Signaturkonstruktoren
(: ml1 a-list)
(define ml1 (make-pair 5 (make-pair "Herbert" empty)))
In den meisten Fllen gehren jedoch alle Elemente einer Liste zu der-
selben Sorte beziehungsweise haben dieselbe Signatur: Schn wre es,
wenn die Signatur fr die Liste dokumentieren knne, welche Signa-
tur die Elemente haben. Wir knnten bei der Definition von pair die
Signatur der Elemente angeben, also pair zum Beispiel auf Elemente
der Signatur number fest abonnieren:
(define-record-procedures pair
make-pair pair?
(first rest))
(: make-pair (number list-of-numbers -> pair))
(: pair? (any -> boolean))
(: first (pair -> number))
(: rest (pair -> list-of-numbers))
Das funktioniert zwar, hat aber den Nachteil, da wir dann fr jede
neue Elementsorte eine neue Definition von Listen schreiben mssen:
list-of-strings, list-of-shoes etc. Das wre nicht nur mhsam, son-
dern wrde auch viel Code ohne Sinn und Verstand mehrmals kopieren.
Besser wre es natrlich, die Macht der Abstraktion zum Tragen zu brin-
gen und ber die Elementsignatur zu abstrahieren. Dazu brauchen wir
allerdings eine etwas aufgebohrte Form von define-record-procedures,
genannt define-record-procedures-parametric. Abbildung 5.3 beschreibt
die Funktionsweise.
(define-record-procedures-parametric t sc
c p
(s1 . . . sn ))
Entsprechend fr Zeichenketten:
(define list-of-strings
(signature
(mixed empty-list
(pair-of string list-of-strings))))
(define list-of
(lambda (x)
(signature
(mixed empty-list
(pair-of x (list-of x))))))
Fertig! Nun knnen wir Signaturen fr Listen von Zahlen als (list-of
number), Listen von Zeichenketten als (list-of string) und Listen von
beliebigen Werten als (list-of any) schreiben. Auerdem knnen wir
diese Definition jetzt verwenden, um bessere Signaturen fr make-pair,
first und rest anzugeben:
(list 1)
, #<list 1>
(list 1 2)
, #<list 1 2>
(list 1 2 3)
, #<list 1 2 3>
Dieser Prozedur ist egal, welche Signatur die Elemente der Liste erfllen,
weil das Konzept der Lnge einer Liste unabhngig davon ist, was die
Elemente sind. Dementsprechend steht dort nur die Signaturvariable
1 In Standard-Scheme heit der Konstruktor fr die eingebauten Paare cons, die Selektoren
car und cdr (gesprochen kar und kudder; dies waren die Namen von Anweisungen
auf einer Maschine, auf der ein Vorlufer von Scheme lief) und das Prdikat fr die leere
Liste null?.
Programmieren mit Listen 55
Die eingebaute Prozedur list erlaubt es, Listen aus ihren Elementen
ohne Verwendung von make-pair zu erzeugen. Sie akzeptiert eine belie-
bige Anzahl von Argumenten, macht daraus eine Liste und gibt diese
zurck:
(list 1 2 3)
, #<list 1 2 3>
(list "Axl" "Slash" "Izzy")
, #<list "Axl" "Slash" "Izzy">
Es ist list-length egal, was der Wert von (first lis) ist. Die Lnge
der Liste ist unabhngig davon, was fr Werte sich darin befinden:
entscheidend ist nur, wieviele es sind. (Dieser Umstand ist gerade ver-
antwortlich fr die parametrische Polymorphie.) Damit knnen wir
(first lis) aus der Schablone streichen und diese dann zum vollstn-
digen Rumpf ergnzen:
(define list-length
(lambda (lis)
(cond
((empty? lis) 0)
((pair? lis)
(+ 1
(list-length (rest lis)))))))
Prozeduren, die Listen produzieren. Das geht mit Techniken, die wir
bereits vorgestellt haben. Wir machen die Sache interessanter, indem
wir in einem ersten Beispiel Listen von zusammengesetzten Daten
betrachten und in einem zweiten Beispiel zwei Listen verarbeiten.
; Grteltiere berfahren
(: run-over-dillos ((list-of dillo) -> (list-of dillo)))
(define run-over-dillos
(lambda (dls)
...))
Die Prozedur akzeptiert eine Liste als Eingabe, wir knnen also, wie
schon so oft, die entsprechende Schablone zum Einsatz bringen:
(define run-over-dillos
(lambda (dls)
(cond
((empty? dls) ...)
((pair? dls)
... (first dls) ...
... (run-over-dillos (rest dls)) ...))))
Programmieren mit Listen 57
Im ersten Zweig ist die Sache klar: Geht eine leere Liste rein, kommt
auch eine leere Liste raus. Im zweiten Zweig knnen wir uns erst einmal
um das erste Grteltier kmmern. Wir haben ja bereits eine Prozedur,
die ein einzelnes Grteltier berfhrt; diese knnen wir auf das erste
Element der Liste anwenden:
(define run-over-dillos
(lambda (dls)
(cond
((empty? dls) empty)
((pair? dls)
... (run-over-dillo (first dls)) ...
... (run-over-dillos (rest dls)) ...))))
Lesen wir noch einmal die beiden Ausdrcke, die im zweiten Zweig
stehen:
(run-over-dillo (first dls)) ist das erste Grteltier der Liste, ber-
fahren.
(run-over-dillos (rest dls)) ist eine Liste der restlichen Grteltiere,
berfahren.
Gefragt ist eine Liste aller Grteltiere, berfahren: Wir mssen also nur
die Resultate der beiden Ausdrucke mit make-pair kombinieren:
(define run-over-dillos
(lambda (dls)
(cond
((empty? dls) empty)
((pair? dls)
(make-pair (run-over-dillo (first dls))
(run-over-dillos (rest dls)))))))
Fertig!
Dieses Beispiel zeigt, da wir fr Prozeduren, die Listen produzieren,
keine neue Technik brauchen: Wenn eine Prozedure eine leere Liste
produzieren soll, benutzen wir an der entsprechenden Stelle empty,
und bei nichtleeren Listen benutzen wir make-pair, bringen also die
Schablone fr Prozeduren zum Einsatz, die zusammengesetzte Daten
produzieren.
(define concatenate
(lambda (lis-1 lis-2)
(cond
((empty? lis-2) ...)
((pair? lis-2)
... (first lis-2)
... (concatenate lis-1 (rest lis-2)) ...))))
Der erste Zweig des cond ist noch einfach: Wenn lis-2 leer ist, mu
lis-1 herauskommen. Jedoch wre fr das obige Beispiel der Wert von
(concatenate lis-1 (rest lis-2)) die folgende Liste:
#<list 1 2 3 5 6>
Bei dieser Liste fehlt das Element 4 in der Mitte, und es ist nicht
ersichtlich, wie unsere Prozedur sie passend ergnzen knnte. Diese
Mglichkeit fhrt also in eine Sackgasse. Wir versuchen deshalb, die
Schablone auf lis-1 statt auf lis-2 anzuwenden:
(define concatenate
(lambda (lis-1 lis-2)
(cond
((empty? lis-1) ...)
((pair? lis-1)
... (first lis-1)
... (concatenate (rest lis-1) lis-2) ...))))
Die erste Ellipse ist einfach zu ersetzen: Ist die erste Liste leer, ist das
Ergebnis die zweite Liste lis-2. Fr den zweiten Fall sollten wir uns
noch einmal ins Gedchtnis rufen, was fr einen Wert (concatenate
(rest lis-1) lis-2) liefert: das Ergebnis dieses Aufrufs ist eine Li-
ste, die aus (rest lis-1) und lis-2 zusammengesetzt wurde. Auf das
obige Beispiel bertragen, mit lis-1 = #<list 1 2 3> und lis-2 =
#<list 4 5 6>, ist (rest lis-1) = #<list 2 3>. Der Wert von (concatenate
(rest lis-1) lis-2) wre also:
#<list 2 3 4 5 6>
Es fehlt das erste Element von lis-1, (first lis-1), das vorn an das
Ergebnis angehngt werden mu. Das geht mit make-pair:
(define concatenate
(lambda (lis-1 lis-2)
(cond
((empty? lis-1) lis-2)
((pair? lis-1)
(make-pair (first lis-1)
(concatenate (rest lis-1) lis-2))))))
Programmieren mit Listen 59
Anmerkungen
Listen sind, was Datenstrukturen betrifft, eine Art Alleskleber: Sie tau-
gen auch fr die Reprsentation von Tabellen, Mengen und vielen
anderen zusammengesetzten Daten. Fr Listen gibt es eine riesige
Anzahl praktischer Prozeduren, von denen die Prozeduren in diesem
Kapitel nur die Spitze des Eisberges sind. Da Listen in Scheme fest
eingebaut sind, knnen sie als universelles Kommunikationsmittel zwi-
schen Programmen dienen, weil sich Prozeduren auf Listen aus einem
Programm auch in einem anderen verwenden lassen. Dies unterscheidet
Scheme von vielen anderen Programmiersprachen, in denen Listen vom
Programmierer selbst definiert werden mssen oder nur eine unterge-
ordnete Rolle spielen.
Viele andere Programmiersprachen bauen auf Felder oder Arrays
als fundamentale Datenstrukturen fr die Reprsentation von Folgen.
Diese gibt es in Scheme auch (unter dem Namen Vektor), finden jedoch
nur selten Verwendung: Oft lt sich eine bessere Lsung mit Listen
oder anderen Reprsentationen finden.
Aufgaben
Die Mathematik beschftigt sich zentral mit Beweisen von formalen Aus-
sagen. Diese sind auch in der Informatik wichtig, um die Korrektheit
von Programmen sicherzustellen. Dabei geht es hufig um Aussagen
der Form fr alle x X, wobei X eine unendliche Menge ist zum
Beispiel die Menge der natrlichen Zahlen oder die Menge der Listen.
In der Informatik haben viele der in der Praxis vorkommenden Men-
gen insbesondere alle gemischten Daten mit Selbstbezug wie die
Listen eine besondere Eigenschaft: Sie sind induktiv definiert. Die in-
duktive Definition erlaubt, eine besondere Beweistechnik anzuwenden,
die Induktion. Um induktiv definierte Mengen, Funktionen darauf und
Beweise darber geht es in diesem Kapitel.
Wie lassen sich solche Aussagen beweisen? Gau Argument war, da,
wenn er die Summe ausschreibt:
1 + 2 + . . . + ( n 1) + n
Der Blick auf die ausgeschriebene Form hilft nicht direkt weiter:
1 + 4 + 9 + 16 + . . . + (n 1)2 + n2
Allerdings lohnt es sich, einen Blick auf die ersten paar Glieder der
Reihe zu werfen, und diese tabellarisch ber die Gausche Summen zu
62 Kapitel 6
setzen:
n 0 1 2 3 4 5 6 ...
in=0 i2 0 1 5 14 30 55 91 ...
in=0 i 0 1 3 6 10 15 21 ...
Wer die Paare der Summen der beiden Reihen lang genug anstarrt, sieht
vielleicht, da sich alle als Brche auf den Nenner 3 krzen lassen:
n 0 1 2 3 4 5 6 ...
in=0 i2 ? 3 5 7 9 11 13
...
in=0 i 3 3 3 3 3 3 3
Einzige Ausnahme ist der Bruch fr 0: dort wird durch 0 geteilt, es ist
also unklar, welcher Bruch an dieser Stelle in der Tabelle stehen sollte.
Ansonsten suggeriert die Tabelle folgende Formel:
in=0 i2 2n + 1
n =
i =0 i 3
Schne Formel aber stimmt sie auch fr alle n N? (Fr den unklaren
Fall 0 stimmt sie.) Wer mag, kann sie noch fr weitere n 7, 8, . . . aus-
probieren, und tatschlich zeigen sich zunchst keine Gegenbeispiele.
Aber das ist langweilig und wrde immer noch nicht reichen, um die
Behauptung fr alle n N zu beweisen.
Wenn die Behauptung fr alle n N stimmt, also insbesondere auch
fr ein bestimmtes n N, dann sollte sie auch fr n + 1 gelten, das
wre dann die folgende Gleichung, bei der gegenber der Gleichung
oben fr n jeweils n + 1 eingesetzt wurde:
n +1
(n + 1)((n + 1) + 1)(2(n + 1) + 1)
i2 = 6
i =0
Bei der Reihe in=+01 i2 lt sich der letze Summand ausgliedern und die
Gleichung damit folgendermaen schreiben:
n
(n + 1)(n + 2)(2n + 3)
( i 2 ) + ( n + 1)2 =
i =0
6
Damit bietet sich die Chance, die jeweiligen Seiten von Gleichung 6.1
von den Seiten von Gleichung 6.2 abzuziehen:
n n
(n + 1)(n + 2)(2n + 3) n(n + 1)(2n + 1)
( i 2 ) + ( n + 1)2 i 2 =
i =0 i =0
6 6
Induktive Beweise und Definitionen 63
Es bleibt:
(n + 1)(n + 2)(2n + 3) n(n + 1)(2n + 1)
( n + 1)2 =
6 6
Wenn diese Gleichung stimmt, dann stimmt auch Gleichung 6.2. Das
lt sich ausrechnen:
(n + 1)(n + 2)(2n + 3) n(n + 1)(2n + 1) (n + 1)(n + 2)(2n + 3) n(n + 1)(2n + 1)
=
6 6 6
(n + 1)((n + 2)(2n + 3) n(2n + 1))
=
6
(n + 1)(2n + 3n + 4n + 6 2n2 n)
2
=
6
(n + 1)(6n + 6)
=
6
6( n + 1)2
=
6
= ( n + 1)2
Tatsache! Aber was wurde jetzt eigentlich gezeigt? Es ist leicht, bei den
vielen Schritten von oben den Faden zu verlieren. Hier noch einmal die
Zusammenfassung:
Es schien so, als ob folgende Gleichung stimmen wrde:
n
n(n + 1)(2n + 1)
i2 = 6
i =0
Das ist aber die gleiche Behauptung, nur fr n + 1 statt n mit anderen
Worten folgt aus der Behauptung fr n die Behauptung fr n + 1. Da
oben durch Ausrechnen bereits gezeigt wurde, da die Behauptung
fr 1, . . . , 6 gilt, gilt sie auch fr 7. Da sie fr 7 gilt, gilt sie auch fr
8. Undsoweiter fr alle natrlichen Zahlen. Es nicht ntig, sie einzeln
auszuprobieren. Die Vermutung von oben ist also bewiesen.
Die vollstndige Induktion aus dem vorigen Abschnitt ist nur fr die
Menge der natrlichen Zahlen geeignet. Sie funktioniert aber nicht fr
alle Mengen: Fr die reellen Zahlen R z.B. erreicht die Konstruktion
bei 0 anfangen und dann immer um 1 hochzhlen einfach nicht alle
Elemente der Menge.Die natrlichen Zahlen sind also etwas besonderes.
Das liegt daran, da sich eine Art Bastelanleitung fr alle Elemente von
N angeben lt:
0 ist eine natrliche Zahl.
Fr eine bekannte natrliche Zahl n ist auch n + 1 eine natrliche
Zahl.
Diese Anleitung erreicht jede natrliche Zahl jede Zahl kann in der
Form 0 + 1 + . . . + 1 geschrieben werden. Fr diese Art Bastelanleitung
fr Mengen ist charakteristisch, da es ein oder mehrere Basiselemente
gibt (in diesem Fall die 0) und dann ein oder mehrere Regeln, die aus
beliebigeren kleineren Elementen grere Elemente konstruieren,
in diesem Fall die Regel, die besagt, da fr jede natrliche Zahl auch
ihr Nachfolger eine natrliche Zahl ist. Umgekehrt lt sich die Menge
der natrlichen Zahlen N folgendermaen definieren:
Die natrlichen Zahlen sind nicht die einzige induktiv definierte Menge.
Ein weiteres Beispiel sind die endlichen Folgen, die den Listen entspre-
chen:
Definition 6.2 Sei M eine beliebige Menge. Die Menge M der endlichen
Folgen ber M ist folgendermaen definiert:
1. Es gibt eine leere Folge2 e M .
2. Wenn f M eine Folge ist und m M, so ist m f M , also auch
eine Folge.
3. Die obigen Regeln definieren alle f M .
Eine Folge entsteht also aus einer bestehenden Folge dadurch, da
vorn noch ein Element angehngt wird. Folgen ber M = { a, b, c} sind
deshalb etwa
e, ae, be, ce, aae, abe, ace, . . . , abce, . . . cbbae, . . . (nicht alphabetisch sortiert)
Die Funktion entspricht also der Prozedur list-sum aus Abschnitt 5.2.
Da es zwei verschiedene Sorten endlicher Folgen gibt die leere Folge
und die nichtleeren Folgen liegt es nahe, die entsprechende Funkti-
on mit einer Verzweigung zu schreiben, die zwischen den beiden Sorten
unterscheidet:
(
def ? falls f = e
s( f ) =
? falls f = m f 0 , m M, f 0 M
2 Auf den ersten Blick scheint das Konzept einer leeren Folge, die keine Elemente enthlt,
merkwrdig. Die Informatik hat aber die Erfahrung gemacht, dass allzu oft Program-
me abstrzen, weil sie irgendwo nichts vorfinden, wo sie doch mindestens etwas
erwarteten. Auf den zweiten Blick ist die leere Folge aber das Analog zu der 0 bei den
natrlichen Zahlen.
68 Kapitel 6
Die Definition von s ruft sich also an der Stelle selbst auf, an der die
induktive Definition der endlichen Folgen den Selbstbezug f 0 M
eine Folge enthlt.
Mathematisch geneigte Leser werden die Definition von s mit Skep-
sis betrachten, taucht doch s sowohl auf der linken als auch auf der
rechten Seite auf es sieht so aus, als sei s durch sich selbst definiert.
Tatschlich ist dies jedoch kein Problem, da:
Induktive Beweise und Definitionen 69
6.4.2 Folgeninduktion
Das Gegenstck zur vollstndigen Induktion heit bei den Folgen Fol-
geninduktion. Der Schlu von n auf n + 1 wird bei der Folgeninduktion
zu je einem Schlu von f auf m f fr alle Folgen f und alle m M . Oft
kommt es dabei auf das Folgenelement m gar nicht an.
Zum Beweis der Behauptung, da eine bestimmte Behauptung fr
alle f M gilt, gengt es, die folgenden Beweise zu fhren:
1. Die Behauptung gilt fr f = e (Induktionsanfang)
2. Wenn die Behauptung fr eine Folge f gilt, so gilt sie auch fr alle
Folgen m f wobei m M. (Induktionsschlu).
Die Folgeninduktion funktioniert, weil sie der Struktur der Definition
der endlichen Folgen 6.2 genauso folgt wie die vollstndige Induktion
der Struktur der natrlichen Zahlen. Das Lemma lt sich auch mit
Hilfe der vollstndigen Induktion beweisen siehe Aufgabe 6.7.
Entsprechend der vollstndigen Induktion gibt es auch fr die Fol-
geninduktion eine Anleitung:
1. Formulieren Sie die zu beweisende Behauptung als Behauptung der
Form Fr alle f M gilt . . . , falls das noch nicht geschehen ist.
2. Schreiben Sie die berschrift f = e:. Schreiben Sie die Behauptung
noch einmal ab, wobei Sie das fr alle f M weglassen und fr f
das e einsetzen.
3. Beweisen Sie die abgeschriebene Behauptung. (Das ist in der Regel
sehr einfach.)
4. Schreiben Sie das Wort Induktionsvoraussetzung: Schreiben Sie
darunter die Behauptung noch einmal ab, wobei Sie das fr alle
f M weglassen lassen Sie das f da, wo es ist.
5. Schreiben Sie Induktionsschlu (zu zeigen):. Schreiben Sie darunter
die Behauptung noch einmal ab, wobei Sie fr f stattdessen m f
einsetzen. (Wieder lassen Sie das fr alle f M weg.)
6. Beweisen Sie den Induktionsschlu unter Verwendung der Indukti-
onsvoraussetzung. Denken Sie daran, die Behauptung fr alle m M
zu beweisen das ist meist aber nicht immer trivial.
Wenn die Behauptung eine Gleichung der Form A = B ist, dann lt
sich hufig die Induktionsvoraussetzung entweder direkt oder nach
einigen Umformungen in den Induktionsschlu einsetzen.
Fr ein sinnvolles Beispiel dient die Funktion cat, die Folgen aneinan-
derhngt:
(
def f2 falls f 1 = e
cat( f 1 , f 2 ) = 0
m cat( f 1 , f 2 ) falls f 1 = m f 10 , m M, f 10 M
70 Kapitel 6
2. f = e: Hier gilt
5. Wir benutzen die Definition von cat, um die linke Seite weiter auszu-
rechnen:
cat(m f , cat(v, w)) = mcat( f , cat(v, w))
Hier steht aber cat( f , cat(v, w)) und das steht auch auf der linken
Seite der Induktionsvoraussetzung. Wir knnen also einsetzen:
= mcat(cat( f , v), w)
Das ist aber das gleiche, das auch bei der linken Seite herausgekom-
men ist der Beweis ist fertig.
hNi 0 | hNi + 1
In der Grammatik steht hNi fr eine natrliche Zahl. Zu lesen ist die
Grammatik so: Eine natrliche Zahl ist entweder die 0 oder hat die Form
n + 1 wobei n wiederum eine natrliche Zahl ist. Der obligatorische
induktive Abschlu (Die obigen Regeln definieren alle n N.) wird
stillschweigend vorausgesetzt und darum weggelassen.
Das Zeichen kann also als ist oder hat die Form gelesen
werden, das Zeichen | als oder. Die Notation h X i definiert eine ent-
sprechende Menge X. Die Grammatik ist also eine Art mathematische
Schreibweise fr zusammengesetzte Daten, gemischte Daten (|) und
Selbstbezge, nur eben fr mathematische Objekte.
Fr die Menge der Folgen ber einer Menge M gengt also folgende
Notation:
h M i e | h Mi h M i
In beiden Definitionen ist jeweils der Selbstbezug klar zu sehen: Bei
den natrlichen Zahlen taucht hNi in einer Klausel auf, bei den Folgen
h M i. Alle anderen Klauseln also die ohne Selbstbezug beschreiben
Basisflle.
Das ist kein Zufall: Die rekursive Funktionsdefinition gehrt zur induk-
tiven Mengendefinition wie Pech zu Schwefel. Zwei Grundregeln legen
diese Form fest:
1. Fr jede Klausel gibt es eine Verzweigung mit einem Zweig der
induktiven Definition.
2. Bei Selbstbezgen steht im entsprechenden Zweig ein Selbstaufruf.
Auch bei den natrlichen Zahlen lassen sich viele Operationen rekursiv
aufschreiben. Zum Beispiel die Potenz:
(
n def 1 falls n = 0
b = 0
bbn falls n = n0 + 1, n0 N
hXi C1 | ...| Cn
Eine Funktion auf dieser Menge braucht dann genau wie bei gemisch-
ten Daten eine Verzweigung mit n Zweigen, eine fr jede Klausel:
R1 falls x = F1
def
F(x) = . . .
Rn falls x = Fn
x = [ a & b ], a A, b B
x = { x 0 }, x 0 X
(> ) >
> ( >)
Induktive Beweise und Definitionen 73
Die ersten beiden Flle liefern 1 und 0 respektive, fr die weiteren Flle
werden folgende Hilfsfunktionen definiert:
( (
def 1 falls t1 = 1 und t2 = 1 def 0 falls t1 = 0 und t2 = 0
a ( t1 , t2 ) = o ( t1 , t2 ) =
0 sonst 1 sonst
(
def 1 falls t = 0
n(t) =
0 falls t = 1
Die Funktion a liefert nur dann 1, wenn t1 und t2 1 sind (sonst 0).
Die Funktion o liefert dann 1, wenn t1 oder t2 1 sind (sonst 0). Die
Funktion n liefert dann 1, wenn t nicht 1 ist (sonst 0). Diese Funktionen
vervollstndigen nun die Definition von J K:
1 falls e = >
0 falls e =
def
JeK = a(Je1 K, Je1 K) falls e = e1 e2
o (Je1 K, Je1 K) falls e = e1 e2
n(Je0 K)
falls e = e0
JeK = n(JeK)
J>K = 1 JK = 0
J>K = JK JK = J>K
=0 =1
= n (1) = n (0)
Als nchstes ist der Fall e = e1 e2 an der Reihe. Da die Klausel
hEi . . . | hEi hEi
zwei Selbstbezge hat, gibt es auch eine zweiteilige Induktionsvoraus-
setzung die Behauptung kann fr e1 und e2 angenommen werden:
Je1 K = n(Je1 K), Je2 K = n(Je2 K). Der Induktionsschlu dazu sieht so aus:
Der letzte Schritt ergibt sich aus genauer Betrachtung der Definitionen
von o und a bzw. durch Einsetzen aller mglichen Werte fr t1 und t2 .
Der Fall e = e1 e2 folgt analog. Wieder gibt es zwei Selbstbezge,
also gilt wieder die zweiteilige Induktionsvoraussetzung Je1 K = n(Je1 K),
Je2 K = n(Je2 K). Induktionsschlu (zu zeigen):
Schlielich fehlt noch der Fall e = e0 . Hier gibt es nur einen Selbstbe-
zug, entsprechend lautet die Induktionsvoraussetzung: Je0 K = n(Je0 K).
Induktionsschlu (zu zeigen):
Je0 K = n(Je0 K)
J e 0 = e 0 Definition von
= n(Je0 K)
= n(n(Je0 K)) Induktionsvoraussetzung
Das Beispiel zeigt, da strukturell induktive Beweise durchaus mehr
als einen Induktionsanfang haben knnen hier die Flle > und .
Ebenso gibt es mehr als einen Induktionsschlu einen fr jede Klausel
mit Selbstbezug, hier sind das drei Flle.
Fr Beweise mit struktureller Induktion gilt also folgende Anleitung:
1. Formulieren Sie die zu beweisende Behauptung als Behauptung der
Form Fr alle x X gilt . . . (wobei X eine induktiv definierte
Menge ist), falls das noch nicht geschehen ist.
2. Fhren Sie jetzt einen Beweis fr jede einzelne Klausel Ci der induk-
tiven Definition:
3. Schreiben Sie die berschrift x = Fi , wobei Fi eine Bedingung ist,
die der Klausel entspricht. Schreiben Sie die Behauptung noch einmal
ab, wobei Sie das fr alle x X weglassen und fr x stattdessen Fi
einsetzen.
4. Wenn die Klausel keinen Selbstbezug enthlt, so beweisen Sie die
Behauptung direkt.
5. Wenn die Klausel einen oder mehrere Selbstbezge enthlt, so stehen
in der berschrift Variablen x j oder x 0 o.., die ihrerseits Element
von X sind. Schreiben Sie dann die berschrift Induktionsvorausset-
zung:. Schreiben Sie darunter fr jeden Selbstbezug die Behauptung
noch einmal ab, wobei Sie das fr alle x X weglassen und fr x
stattdessen x j bzw. x 0 einsetzen.
Schreiben Sie darunter das Wort Induktionsschlu und beweisen
die Behauptung. Denken Sie daran, die Induktionsvoraussetzung zu
benutzen.
Anmerkungen
Diese Definition ist quivalent zu Definition 6.1 von Seite 66. Wie in
Definition 6.1, lt sich N sich aus den Peano-Axiomen schrittweise
konstruieren. Aus 1. und 2. folgt, da es natrliche Zahlen
0, 00 , 000 , 0000 , 00000 , . . .
Aufgaben
1=1
1 4 = (1 + 2)
14+9 = 1+2+3
1 4 + 9 16 = (1 + 2 + 3 + 4)
Raten Sie die Gleichung, die dieser Tabelle zugrundeliegt und schreiben
Sie in mathematischer Notation auf. Beweisen Sie die Gleichung!
cat(v, w) = cat(z, w) v = z
cat(v, w) = cat(v, z) w = z
Aufgabe 6.7 Beweisen Sie die Korrektheit der Folgeninduktion aus Ab-
schnitt 6.4.2 (Seite 69) mit Hilfe der vollstndigen Induktion. Beschrei-
ben Sie dazu, wie sich eine Aussage ber alle Folgen in eine Aussage
ber die Lngen der Folgen umwandeln lt. Setzen Sie dann die Klau-
seln der vollstndigen Induktion mit den entsprechenden Klauseln der
Folgeninduktion in Beziehung.
n) die ganze Zahl ist, die am nchsten zu n / 5 liegt,
Beweise, da fib(
wobei = (1 + 5)/2.
Anleitung: Zeige, da fib ( n ) = ( n n ) / 5, wobei = (1
5)/2.
78 Kapitel 6
Aufgabe 6.11 Eine partielle Ordnung 4 auf einer Menge M heit wohl-
fundiert oder noethersch, wenn es keine unendlichen Folgen ( xi )iN gibt,
so da fr alle i N gilt
z M : (y M : y z P(y)) P(z)) x M : P( x )
Aus der induktiven Definition der natrlichen Zahlen ergibt sich direkt
eine Schablone fr die Konstruktion von Prozeduren auf den natrli-
chen Zahlen. Angenommen, es sei eine Prozedur gefragt, die fr eine
Zahl n das Produkt aller Zahlen von 1 bis n berechnet. Dieses Produkt
heit Fakultt, auf Englisch factorial. Beschreibung und Signatur sind
wie folgt:
; das Produkt aller Zahlen von 1 bis n berechnen
(: factorial (natural -> natural))
Der erste Fall ist die 0, der andere Fall deckt alle anderen Zahlen ab:
(define factorial
(lambda (n)
(cond
((= n 0) ...)
(else ...))))
Umgekehrt liee sich auch die Fallunterscheidung bei Listen mit if schreiben. Welche
Variante am besten ist, ist Geschmackssache.
80 Kapitel 7
(define factorial
(lambda (n)
(if (= n 0)
...
...)))
Der Fall 0 ist hier gar nicht so einfach zu beantworten. Was sind schlie-
lich die Zahlen von 1 bis 0? Dafr ist der andere Zweig einfacher zu
ergnzen: hier ist nmlich die Konstruktionsanleitung fr zusammen-
gesetzte Daten anwendbar. Als Selektor wird die Vorgngeroperation
angewendet, es steht also (- n 1) in der Alternative. Genau wie bei
den endlichen Folgen liegt nahe, da auf (- n 1) ein rekursiver Aufruf
erfolgt:
(define factorial
(lambda (n)
(if (= n 0)
...
... (factorial (- n 1)) ...)))
Der rekursive Aufruf (factorial (- n 1)) soll nach Signatur und Be-
schreibung der Prozedur das Produkt der Zahlen von 1 bis n 1 be-
rechnen. Gefragt ist aber das Produkt der Zahlen von 1 bis n. Es fehlt
noch n selbst, das mit dem Ergebnis multipliziert werden mu:
(define factorial
(lambda (n)
(if (= n 0)
...
(* n (factorial (- n 1))))))
Es fehlt schlielich noch der erste Zweig der if-Form. In Fllen wie die-
sem, wo die Antwort nicht offensichtlich ist, lohnt es sich, ein oder zwei
einfache Beispiele durchzurechnen, die meist die Antwort zwingend
festlegen. Das einfachste Beispiel ist wohl 1 das Produkt der Zahlen
von 1 bis 1 sollte 1 sein. Auswertung mit dem Substitutionsmodell
ergibt:
(factorial 1)
= (if (= 1 0) ... (* 1 (factorial (- 1 1))))
= (if #f ... (* 1 (factorial (- 1 1))))
= (* 1 (factorial (- 1 1)))
= (* 1 (factorial 0))
= (* 1 (if (= 0 0) ... (* 0 (factorial (- 0 1)))))
= (* 1 (if #t ... (* 0 (factorial (- 0 1)))))
= (* 1 ...)
Damit ist klar, da die unbekannte Zahl, die an Stelle der ... stehen
mu, multipliziert mit 1 wiederum 1 ergeben mu. Die einzige Zahl,
die diese Bedingung erfllt, ist 1 selbst. Die vollstndige Definition von
factorial ist also:
(define factorial
(lambda (n)
Prozeduren ber natrlichen Zahlen 81
(if (= n 0)
1
(* n (factorial (- n 1))))))
Aufgaben
Aufgabe 7.1 Schreibe eine Prozedur power2, die eine Zahl akzeptiert
und ihre Zweierpotenz zurckliefert.
Aufgabe 7.2 Schreibe eine Prozedur power, die fr eine Basis b und
einen Exponenten e N gerade be ausrechnet. Also:
(power 5 3)
, 125
Die eingebaute Prozedur odd? akzeptiert eine ganze Zahl und liefert
#t, falls diese ungerade ist und #f sonst. Schreibe mit Hilfe von odd?
eine Prozedur odds, welche fr zwei Zahlen a und b eine Liste die
ungeraden Zahlen zwischen a und b zurckgibt:
(odds 1 10)
, #<record:pair 1
#<record:pair 3
#<record:pair 5
#<record:pair 7
#<record:pair 9 #<empty-list>>>>>>
TBD
(define-record-procedures game
make-game game?
(game-matchday
game-home-team game-home-goals game-guest-team game-guest-goals))
(: make-game (natural string natural string natural -> game))
(: game? (any -> boolean))
(: game-home-team (game -> string))
(: game-home-goals (game -> natural))
(: game-guest-team (game -> string))
(: game-guest-goals (game -> natural))
1 Die kompletten Ergebnisse dieser Saison lassen sich unter dem Namen soccer.rkt von
der Webseite des Buchs deinprogramm.de herunterladen.
86 Kapitel 8
(define day1
(list g1 g2 g3 g4 g5 g6 g7 g8 g9))
Eine recht einfache Frage ist die Bestimmung der Punktzahl, welche
die Gastgebermannschaft in einem bestimmten Spiel erzielt hat. Eine
Prozedur, die das leistet, hat Beschreibung und Signatur wie folgt:
; Punktzahl in Spiel
(define points
(signature (one-of 0 1 3)))
Aber auch das Gsteteam soll die ihm zustehenden Punkte bekommen.
Das fhrt zu folgender Prozedur:
(define guest-points
(lambda (g)
(let ((g1 (game-guest-goals g))
(g2 (game-home-goals g)))
(cond
((> g1 g2) 3)
((< g1 g2) 0)
((= g1 g2) 1)))))
die Vergabe von Punkten ndern sollte, mssten hier beide Prozeduren
in gleicher Weise angepasst werden. Die Lsung fr das Problem zeigt
sich dadurch, dass der gemeinsame Code aus den beiden Prozeduren
ausfaktorisiert wird.
Musterbildung ist eine der wichtigsten Abstraktionstechniken, und
deshalb gibt es ein eigenes Mantra:
Das verdient eine kurze Betrachtung: Hier liegt eine Prozedur vor, die
zwei Prozeduren als Argument akzeptiert und eine weitere Prozedur als
Ergebnis liefert. Solche Prozeduren heien Prozeduren hherer Ordnung
oder Higher-Order-Prozeduren.
Die Definition von compute-points ergibt sich recht leicht aus den
beiden schon vorgestellten Prozeduren:
(define compute-points
(lambda (goals-1 goals-2)
(lambda (g)
(let ((g1 (goals-1 g))
(g2 (goals-2 g)))
(cond
((> g1 g2) 3)
((< g1 g2) 0)
((= g1 g2) 1))))))
Eine weitere interessante Aufgabe ist es, aus einer Liste von Spielen
die unentschieden ausgegangenen Spiele herauszusuchen. Dazu ist
zunchst eine Prozedur notwendig, die feststellt, ob ein bestimmtes
Spiel unentschieden war:
; Ist Spiel unentschieden?
(: game-draw? (game -> boolean))
(define game-draw?
(lambda (g)
(= 1 (home-points g))))
Der erste Fall ist klar: wo keine Spiele sind, sind auch keine unentschie-
denen. Der zweite Fall betrachtet das erste Element (first lis). Dabei
ist entscheidend, ob es sich dabei um ein unentschiedenes Spiel handelt
oder nicht:
(define games-draw
(lambda (lis)
(cond
((empty? lis) empty)
((pair? lis)
... (game-draw? (first lis)) ...
... (games-draw (rest lis)) ...))))
Fertig!
Eine ganz hnliche Prozedur sortiert aus einer Liste von Spielen
diejenigen aus, an denen eine bestimmte Mannschaft teilgenommen hat:
(define plays-game?
(lambda (t g)
(or (string=? t (game-home-team g))
(string=? t (game-guest-team g)))))
(define games-playing
(lambda (t lis)
(cond
((empty? lis) empty)
((pair? lis)
(let ((f (first lis))
(r (games-playing t (rest lis))))
(if (plays-game? t f)
(make-pair f r)
r))))))
(define filter-games
(lambda (p? lis)
(cond
((empty? lis) empty)
((pair? lis)
(if (p? (first lis))
(make-pair (first lis)
(filter-games p? (rest lis)))
(filter-games p? (rest lis)))))))
(define plays-nrnberg?
(lambda (g)
(plays-game? "Nrnberg" g)))
Damit diese Vorteile zur Geltung kommen, mssen die alten Ab-
straktionsvorlagen gelscht und durch Anwendungen der Abstraktion
ersetzt werden:
; aus einer Spieleliste eine Liste der Spiele einer Mannschaft t bilden
(: games-playing (string (list-of game) -> (list-of game)))
(define games-playing
(lambda (t lis)
(list-filter (lambda (g) (plays-game? t g)) lis)))
Aus Abschnitt 5.1 ist die Prozedur list-sum bekannt, welche die Summe
einer Liste von Zahlen bildet:
Higher-Order-Programmierung 91
; Liste aufsummieren
(: list-sum ((list-of number) -> number))
(define list-sum
(lambda (lis)
(cond
((empty? lis) 0)
((pair? lis)
(+ (first lis)
(list-sum (rest lis)))))))
Eine eng verwandte Prozedur wrde die Elemente einer Liste nicht
aufsummieren, sondern aufmultiplizieren. Signatur und Schablone sind
identisch zu list-sum:
; Liste aufmultiplizieren
(: list-product ((list-of number) -> number))
(define list-product
(lambda (lis)
(cond
((empty? lis) ...)
((pair? lis)
... (first lis) ...
... (list-product (rest lis)) ...))))
Die erste Ellipse mu das Produkt der leeren Liste sein, also das neu-
trale Element 1 der Multiplikation.2 Aus dem ersten Element und dem
Produkt der Restliste wird das Produkt der Gesamtliste durch Multipli-
kation gebildet.
(define list-product
(lambda (lis)
(cond
((empty? lis) 1)
((pair? lis)
(* (first lis)
(list-product (rest lis)))))))
2 0 funktioniert hier nicht es wrde dafr sorgen, da jede Liste 0 als Produkt hat.
92 Kapitel 8
Wie sich weiter unten herausstellen wird, kann diese Signatur aber
noch verallgemeinert werden. Erst kommen allerdings noch einige
Erluterungen zur Funktionsweise.
List-fold funktioniert wie folgt: Die Prozedur hat als Parameter eine
Prozedur mit zwei Parametern, einen Wert und eine Liste von Werten.
Es gilt folgende Gleichung:
(list-fold u o #<a1 . . . an >) = (o a1 (o a2 (. . . (o an u). . .)))
Die Funktionsweise von list-fold lt sich daran veranschaulichen,
da sich die ursprngliche Liste auch als
(make-pair a1 (make-pair a2 (. . . (make-pair an empty). . .)))
schreiben lt. Das heit, an die Stelle von make-pair tritt o und an die
Stelle von empty tritt u.
Eine andere, praktische Darstellung von list-fold ist, die Gleichung
mit dem Operator zwischen den Operanden zu schreiben (und nicht
davor), in Infix-Schreibweise also:
(list-fold u ( a1 . . . an )) = a1 ( a2 (. . . ( an u) . . .))
Nach dieser Sichtweise wird zwischen die Elemente der Liste einge-
fgt.
In jedem Fall wird die Liste eingefaltet daher der Name.
Die Definition von concatenate aus Abschnitt 5.5 pat ebenfalls auf
das abstrahierte Muster von list-fold:
(list-fold (list 4 5 6) make-pair (list 1 2 3))
, #<list 1 2 3 4 5 6>
Diese Applikation pat aber nicht mehr auf den obigen Signaturversuch
von list-fold, da make-pair nicht die Signatur
%a %a -> %a
sondern
%a (list-of %a) -> (list-of %a)
und deshalb
%a %b -> %b
List-fold kann auch benutzt werden, um die Lnge einer Liste auszu-
rechnen. Ganz so einfach wie bei den vorigen Beispielen ist das nicht,
da list-length aus Abschnitt 5.5 nicht direkt dem Muster entspricht:
(define list-length
(lambda (lis)
(cond
((empty? lis) 0)
((pair? lis)
(+ 1
(list-length (rest lis)))))))
(define list-filter
(lambda (p? lis)
(list-fold empty
(lambda (first result)
(if (p? first)
(make-pair first result)
result))
lis)))
Ein weiteres Beispiel die Prozedur every? findet heraus, ob ein ber-
gebenes Prdikat auf alle Elemente einer Liste zutrifft:
94 Kapitel 8
Anders als list-length lassen sich diese Definitionen nicht mit sepa-
raten Hilfsprozeduren schreiben. Fr list-filter wrde ein Versuch
zwar so aussehen:
(define list-filter-helper
(lambda (first result)
(if (p? first)
(make-pair first result)
result)))
8.4 Prozedurfabriken
def
( f g)( x ) = f ( g( x ))
(define add-5
(lambda (x)
(+ x 5)))
(define add-23
Higher-Order-Programmierung 95
(lambda (x)
(+ 23 x)))
(define add-28 (compose add-5 add-23))
(add-28 3)
, 31
((compose (lambda (x) (* x 2)) add-1) 5)
, 12
Compose ist eine Prozedurfabrik sie liefert selbst eine Prozedur zurck,
die abhngig von f und g konstruiert wird.
Compose lt sich benutzen, um eine weitere praktische Higher-Order-
Prozedur namens repeat zu definieren:
Repeat ist das Pendant zur Potenzierung von Funktionen in der Mathe-
matik, siehe Definition 1.16:
Hier ist eine Prozedurfabrik, die Prozeduren erzeugt, die auf eine Zahl
eine Konstante addieren:
((make-add 7) 15)
, 22
((make-add 13) 42)
, 55
96 Kapitel 8
Make-add ist eine andere Version von +, nmlich eine, die zwei Argumen-
te nicht auf einmal akzeptiert, sondern nacheinander. Summen von
zwei Zahlen, normalerweise geschrieben als (+ a b) lassen sich auch
als ((make-add a) b) schreiben. Diese Transformation von einer Proze-
dur mit zwei Parametern in eine Prozedur mit nur einem Parameter,
die eine Prozedur mit einem weiteren Parameter zurckgibt, die dann
schlielich den Wert liefert, lt sich auch auf andere Prozeduren
anwenden:
; Prozedur erzeugen, die mit einer Konstante multipliziert
(: make-mult (number -> (number -> number)))
(define make-mult
(lambda (a)
(lambda (b)
(* a b))))
Nun lassen sich die make-x-Prozeduren von oben mit Hilfe von curry
definieren:
(define make-add (curry +))
(define make-mult (curry *))
(define make-prepend (curry make-pair))
Aufgaben
TBD
TBD
Abbildung 9.1. Teachpack image2.ss
9 Zeitabhngige Modelle
TBD
Dabei sind die ersten beiden Argumente Breite und Hhe eines Recht-
ecks in Pixeln. Das Argument von der Sorte mode ist eine Zeichenkette,
die entweder "solid" oder "outline" sein mu. Sie bestimmt, ob das
Rechteck als durchgngiger Klotz oder nur als Umri gezeichnet wird.
Das Argument von der Sorte color ist eine Zeichenkette, die eine Farbe
(auf Englisch) bezeichnet, zum Beispiel "red", "blue", "yellow", "black",
"white" oder "gray". Als Ergebnis liefert rectangle ein Bild, das von der
DrRacket-REPL entsprechend angezeigt wird wie andere Werte auch.
Es gibt es noch weitere Prozeduren, die geometrische Figuren zeich-
nen:
Die circle-Prozedur liefert einen Kreis, wobei das erste Argument den
Radius angibt. Die mode- und color-Argumente sind wie bei rectangle.
Diese Prozedur liefert eine Ellipse, wobei das erste Argument die Breite
und das zweite die Hhe angibt.
(: line (natural natural real real real real color -> image))
Dabei sind die ersten beiden Argumente die Bilder, die aufeinanderge-
legt werden das zweite auf das erste. Die beiden anderen Argumente
geben an, wie die beiden Bilder zueinander positioniert werden. Die
Signatur von h-place, das die horizontale Positionierung festlegt, ist:
(define h-place
(signature
(mixed natural
(one-of "left"
"right"
"center"))))
Im ersten Fall, wenn es sich um eine Zahl x handelt, wird das zweite
Bild x Pixel vom linken Rand auf das erste gelegt. Die drei Flle mit
Zeichenketten sagen, da die Bilder am linken Rand bzw. am rechten
Rand bndig plaziert werden, bzw. das zweite Bild horizontal in die
Mitte des ersten gesetzt wird. Dementsprechend ist v-place, das die
vertikale Positionierung festlegt, wie folgt definiert:
(define h-place
(signature
(mixed natural
(one-of "top"
"bottom"
"center"))))
Im ersten Fall, wenn es sich um eine Zahl y handelt, wird das zweite
Bild y Pixel vom oberen Rand auf das erste gelegt. Die drei Flle mit
Zeichenketten sagen, da die Bilder am oberen Rand bzw. am unteren
Rand bndig plaziert werden, bzw. das zweite Bild vertikal in die Mitte
des ersten gesetzt wird.
Das Bild, das bei overlay herauskommt, ist gro genug, da beide
Eingabebilder genau hineinpassen.
Die folgenden Hilfsprozeduren sind Spezialflle von overlay:
Die Prozedur above ordnet zwei Bilder bereinander an, beside neben-
einenander. Dabei ist h-mode eine der Zeichenketten "left", "right"
Zeitabhngige Modelle 101
TBD
Abbildung 9.2. Eingefgte Bilder in der DrRacket-REPL
und "center", die angibt, ob die Bilder bei above an der linken oder
rechten Kante oder der Mitte ausgerichtet werden. Entsprechend ist
v-mode eine der Zeichenketten "top", "bottom" und "center", die angibt,
ob die Bilder bei beside oben, unten oder an der Mitte ausgerichtet
werden.
Die Prozeduren clip und pad beschneiden bzw. erweitern ein Bild:
Dabei mssen die vi Variablen sein und die ei und b (der Rumpf )
beliebige Ausdrcke. Bei der Auswertung eines solchen let-Ausdrucks
werden zunchst alle ei ausgewertet. Dann werden deren Werte fr die
Variablen vi im Rumpf eingesetzt; dessen Wert wird dann zum Wert
des let-Ausdrucks.
Ein let-Ausdruck hat die gleiche Bedeutung wie folgende Kombination
aus Lambda-Ausdruck und Applikation:
(let ((v1 e1 ) . . . (vn en )) b)
7 ((lambda (v1 . . . vn ) b) e1 . . . en )
Da die Variablen, die durch let und lambda gebunden werden, nur
jeweils im Rumpf des let bzw. lambda gelten, heien sie auch lokale
Variablen. Die durch define gebundenen Variablen heien dementspre-
chend da sie berall gelten globale Variablen.
Let kann auch mehrere lokale Variablen gleichzeitig einfhren, wie
im folgenden Beispiel:
(let ((a 1)
(b 2)
(c 3))
(list a b c))
, #<list 1 2 3>
Bei der Benutzung von let ist zu beachten, da die Ausdrcke, deren
Werte an die Variablen gebunden werden, allesamt auerhalb des Ein-
zugsbereich des let ausgewertet werden. Folgender Ausdruck fhrt
also bei der Auswertung zu einer Fehlermeldung:
(let ((a 1)
(b (+ a 1)))
b)
, reference to an identifier before its definition: a
TBD
In der Terminologie von universe.ss ist ein Modell eine world, auf
deutsch eine Welt: Die Idee dahinter ist, da ein Bild eine Ansicht
einer kleinen Welt ist. Damit das funktioniert, mu bei universe.ss eine
erste Welt angemeldet werden, zusammen mit Angaben, wie gro die
Ansicht wird. Dazu gibt es die Prozedur big-bang:
Dieser Aufruf erzeugt ein Fenster mit Breite und Hhe des Himmels,
startet die Uhr, die jede Sekunde zehnmal tickt, und legt als erste Welt
0, also den Anfang der Zeit fest. (Eine zehntel Sekunde reicht etwa
aus, damit die Animation dem menschlichen Auge als Bewegung
erscheint.)
Damit das Teachpack die Welt in eine Ansicht umwandeln kann, mu
eine entsprechende Ansicht angemeldet werden. Dafr ist die Prozedur
on-redraw zustndig:
Als Argument akzeptiert on-redraw also eine Prozedur, die aus einer
Welt ein Bild macht. TBD
Auch diese Prozedur mu noch beim Teachpack angemeldet werden.
Dafr die Teachpack-Prozedur on-tick-event zustndig:
(on-tick-event next-time)
Die Prozedur, die mit on-key-event angemeldet wird, wird immer auf-
gerufen, wenn der Benutzer eine Taste drckt. Welche Taste gedrckt
wurde, gibt das zweite Argument an. Wenn der Benutzer eine regulre
Zeichen-Taste drckt (also keine Cursor-Taste o..), ist dieses Argument
eine Zeichenkette bestehend aus diesem einen Zeichen.
TBD
Aufgaben
TBD
Dabei mssen die vi Variablen sein, die ci Signaturen und b (der Rumpf)
ein Ausdruck, der entweder einen booleschen Wert oder eine Eigen-
schaft liefert. Der for-all-Ausdruck hat als Wert eine Eigenschaft, die
besagt, da b gilt fr alle Werte der vi , welche die Signaturen ci erfllen.
, #<:property>
(check-property
(for-all ((a number)
(b number))
(= (+ a b) (+ b a))))
(check-property
(for-all ((a number)
(b number))
(= (- a b)
(- b a))))
Eigenschaften von Prozeduren 107
(check-property
(for-all ((a rational)
(b rational)
(c rational))
(= (+ a (+ b c))
(+ (+ a b) c))))
a C, b C, c C : a (b + c) = a b + b c
Auch dies lt sich direkt nach Scheme bersetzen, diesmal gleich mit
rational statt number:
(check-property
(for-all ((a rational)
(b rational)
(c rational))
(= (* a (+ b c))
(+ (* a b) (* a c)))))
(check-property
(for-all ((a rational)
(b rational))
(= (* a b)
(* b a))))
(define commutativity
(lambda (op)
(for-all ((a rational)
(b rational))
(= (op a b)
(op b a)))))
Mit Hilfe dieser Definition knnen wir die Kommutativitt von + und *
deutlich kompakter formulieren:
(check-property
(for-all ((a boolean)
(b boolean))
(boolean=? (and a b)
(and b a))))
(check-property
(for-all ((a boolean)
(b boolean)
(c boolean))
(boolean=? (and a (and b c))
(and (and a b) c))))
(define commutativity
(lambda (op sig =?)
(for-all ((a sig)
(b sig))
(=? (op a b)
(op b a)))))
Denken Sie an das signature, das immer notwendig ist, wenn eine
Signatur auerhalb einer Signaturdeklaration mit : sowie einem for-all
vorkommt.
Um commutativity auch auf and und or loszulassen, gibt es allerdings
noch ein weiteres Hindernis: Das Argument zu op mu eine Prozedur
sein and und or sind aber Spezialformen. Wir knnen Sie aber zu
Prozeduren machen, indem wir lambdas darumwickeln:
Bei der neuen Version von commutativity fehlt noch die Signatur. Wir
mssen dazu die ursprngliche Signatur
ziemlich radikal renovieren: Das erste Argument ist zwar immer noch
eine zweistellige Prozedur, aber nicht mehr notwendigerweise auf ratio-
nalen Zahlen. Wir skizzieren erstmal, was wir wissen:
(: commutativity ((%a %a -> %b) signature (%b %b -> boolean) -> property))
Genauso wie bei der Kommutativitt knnen wir auch bei der Assozia-
tivitt abstrahieren. Hier die Abstraktion, die dabei herauskommt:
(define associativity
(lambda (op sig =?)
(for-all ((a sig)
(b sig)
(c sig))
(=? (op a (op b c))
(op (op a b) c)))))
Eigenschaften von Prozeduren 111
Auch hier die Formulierung der Signatur nicht so einfach. Die erste
Skizze knnte so aussehen:
(: associativity ((%a %a -> %a) signature (%a %a -> boolean) -> property))
(check-property
(for-all ((a boolean)
(b boolean))
(boolean=? (not (and a b))
(or (not a) (not b)))))
(check-property
(for-all ((a rational))
(= (+ a 0) a)))
(check-property
(for-all ((a rational))
(= (+ a (- a)) 0)))
(check-property
(for-all ((a rational))
(= (+ (- a) a) 0)))
Kommutativitt a ? b = b ? a
Assoziativitt ( a ? b) ? c = a ? (b ? c)
Distributivitt a (b ? c) = ( a b) ? ( a c); (b ? c) a = (b a) ?
(c a)
neutrales Element (a ? = a; ? a = a)
inverses Element a ? a1 = ; a1 ? a =
Die Prozedur = pat nicht in das Scheme der Eigenschaften des folgen-
den Abschnitts. Sie hat folgende Signatur:
Damit akzeptiert sie zwar zwei Argumente aus derselben Menge, liefert
aber einen booleschen Wert zurck. Stattdessen handelt es sich um ein
binres Prdikat bzw. eine binre Relation. Fr binre Relationen kommt
ein anderer Satz von Eigenschaften in Frage. (Die mathematische Seite
ist in Anhang 1.5 beschrieben.) Insbesondere ist = eine quivalenzrelation
und damit reflexiv, symmetrisch und transitiv.
Die Reflexivitt besagt, da jedes Element der Grundmenge (in die-
sem Fall die Menge der Zahlen) zu sich selbst in Beziehung steht:
(check-property
(for-all ((a number))
(= a a)))
a C, b C : a = b b = a
(check-property
(for-all ((a number)
(b number))
(==> (= a b)
(= b a))))
hnlich luft es mit der Transitivitt: Wenn zwei Zahlen a und b gleich
sind sowie b und eine dritte Zahl c, dann mssen auch a und c gleich
sein:
(check-property
(for-all ((a number)
(b number)
(c number))
(==> (and (= a b) (= b c))
(= a c))))
Die Prozedur concatenate aus Abschnitt 5.6.2 hngt zwei Listen anein-
ander. Auch concatenate ist assoziativ: Wenn drei Listen mit Hilfe von
concatenate aneinandergehngt werden, spielt es keine Rolle, ob zuerst
die ersten beiden oder zuerst die letzten beiden Listen aneinanderge-
hngt werden. Nach dem Muster der Assoziativitt von + und and sieht
der Test dieser Eigenschaft folgendermaen aus:
114 Kapitel 10
(check-property
(associativity concatenate (signature (list-of number)) ...))
Beim Test ist die Signatur von lis-1, lis-2 und lis-3 jeweils (list-of
number). Die Signatur von concatenate
suggeriert allerdings, da die Signatur von lis-1, lis-2 und lis-3 je-
weils (list-of %a) lauten sollte, also allgemeiner als (list-of number).
Signaturen mit Signaturvariablen funktionieren allerdings nicht im
Zusammenhang mit Eigenschaften, wie folgendes Beispiel zeigt:
(check-property
(for-all ((x %a))
...))
(define number-list=?
(lambda (lis-1 lis-2)
(cond
((empty? lis-1)
Eigenschaften von Prozeduren 115
...)
((pair? lis-1)
... (first lis-1) ...
... (number-list=? (rest lis-1) ...) ...))))
(define number-list=?
(lambda (lis-1 lis-2)
(cond
((empty? lis-1)
(cond
((empty? lis-2) #t)
((pair? lis-2) #f)))
((pair? lis-1)
(cond
((empty? lis-2) #f)
((pair? lis-2)
(and (= (first lis-1) (first lis-2))
(number-list=? (rest lis-1) (rest lis-2)))))))))
116 Kapitel 10
(check-property
(for-all ((lis (list-of number)))
(number-list=? lis (concatenate lis empty))))
Wie der Zufall so will, hat auch die Hilfsprozedur number-list=? in-
teressante Eigenschaften: Wie = mu auch number-list=? eine qui-
valenzrelation sein schlielich testet sie wie = auf Gleichheit. Die
dazugehrigen Eigenschaften Reflexivitt, Symmetrie und Transitivi-
tt knnen ebenso wie bei = formuliert werden:
Reflexivitt:
(check-property
(for-all ((lis (list-of number)))
(number-list=? lis lis)))
Symmetrie:
(check-property
(for-all ((lis-1 (list-of number))
(lis-2 (list-of number)))
(==> (number-list=? lis-1 lis-2)
(number-list=? lis-2 lis-1))))
Transitivitt
(check-property
(for-all ((lis-1 (list-of number))
(lis-2 (list-of number))
(lis-3 (list-of number)))
(==> (and (number-list=? lis-1 lis-2)
(number-list=? lis-2 lis-3))
(number-list=? lis-1 lis-3))))
Eigenschaften von Prozeduren 117
Die Prozedur invert aus Abschnitt 12.1 dreht die Reihenfolge der
Elemente einer Liste um. Eine naheliegende Eigenschaft von invert ist,
da zweimaliges Umdrehen wieder die Ursprungsliste liefern sollte:
(check-property
(for-all ((lis (list-of number)))
(number-list=? lis (invert (invert lis)))))
(expect e1 e2 )
e1 und e2 sind Ausdrcke. Die resultierende Eigenschaft ist erfllt, wenn
e1 und e2 den gleichen Wert liefern der Vergleich wird dabei wie bei
check-expect angestellt.
(check-property
(for-all ((lis (list-of string)))
(expect lis (invert (invert lis)))))
Auf diese zwei Listen kann concatenate aber auch jeweils invert ange-
wendet werden:
(check-property
(for-all ((lis-1 (list-of number))
(lis-2 (list-of number)))
... (invert lis-1) ...
... (invert lis-2) ...
... (invert (concatenate lis-1 lis-2)) ...))
Wie lt sich die Liste (invert (concatenate lis-1 lis-2)) noch be-
schreiben? Angenommen, lis-1 ist die Liste #<list 1 2 3> und lis-2
die Liste #<list 4 5 6>. Dann gilt:
(invert (concatenate lis-1 lis-2))
=
(invert (concatenate #<list 1 2 3> #<list 4 5 6>))
= ... = (invert #<list 1 2 3 4 5 6>))| {z } | {z }
lis-1 lis-2
= ... = #<list 6 5 4
| {z } 3 2 1
| {z } >
(invert lis-2) (invert lis-1)
List-sum aus Abschnitt 5.2 ist, wie invert, eine Prozedur, die eine Liste
akzeptiert. Genau wie bei invert ist es eine gute Idee, die Interaktion
zwischen list-sum und concatenate zu untersuchen. Es mssen also
wieder zwei Listen her die zu invert analoge Vorgehensweise liefert
folgende Schablone:
(check-property
(for-all ((lis-1 (list-of number))
(lis-2 (list-of number)))
... (list-sum lis-1) ...
... (list-sum lis-2) ...
... (list-sum (concatenate lis-1 lis-2)) ...
Da list-sum die Elemente der Liste addiert und die Addition assoziativ
ist, mte folgendes gelten:
(check-property
(for-all ((lis-1 (list-of number))
Eigenschaften von Prozeduren 119
(check-property
(for-all ((lis-1 (list-of rational))
(lis-2 (list-of rational)))
(expect (+ (list-sum lis-1) (list-sum lis-2))
(list-sum (concatenate lis-1 lis-2)))))
Eine Alternative ist die Verwendung der Form expect-within, die eine
Eigenschaft analog zu check-within erzeugt. (Siehe Abbildung 10.5.)
(check-property
(for-all ((lis-1 (list-of number))
(lis-2 (list-of number)))
(expect-within (+ (list-sum lis-1) (list-sum lis-2))
(list-sum (concatenate lis-1 lis-2))
0.1)))
(check-property
(for-all ((a number)
(b number)
(c number))
(expect-within (+ a (+ b c))
(+ (+ a b) c)
0.1)))
Reihenfolge der Elemente der Liste keine Rolle spielt. Eine einfache
Mglichkeit, dies zu testen, ist wiederum mit zwei Listen zu arbeiten
und diese einmal in der einen und dann in der anderen Richtung
aneinanderzuhngen:
(check-property
(for-all ((lis-1 (list-of rational))
(lis-2 (list-of rational)))
(expect (list-sum (concatenate lis-1 lis-2))
(list-sum (concatenate lis-2 lis-1)))))
In Abschnitt 8.5 wurde bereits eine Eigenschaft von curry und uncurry
aufgefhrt:
(uncurry (curry p)) p
Mit anderen Worten: curry und uncurry sind jeweils Inverse voneinan-
der. Auch diese Eigenschaft lt sich direkt mit check-property und
for-all formulieren. Zu beachten ist wieder, obwohl curry und uncurry
polymorphe Signaturen mit Signaturvariablen haben, da fr den Test
mit check-property eine konkrete Signatur ohne Signaturvariablen
fr das Prozedur-Argument benutzt werden mu, also zum Beispiel
string:
(check-property
(for-all ((proc (string string -> string)))
(expect (curry (uncurry proc))
proc)))
Leider schlgt dieser Test fehl, und zwar mit einer mysterisen Mel-
dung:
Offenbar ist DrRacket also der Ansicht, es hat eine Prozedur gefun-
den, welche die Eigenschaft nicht erfllt, kann aber nicht genau sagen,
welche Prozedur: Das liegt daran, da es prinzipiell unmglich ist,
zwei Prozeduren auf Gleichheit zu berprfen Gleichheit zweier Pro-
zeduren heit ja, da die eine Prozedur angewendet auf einen Satz
Argumente immer das gleiche Ergebnis wie die andere Prozedur liefert.
Im obigen Beispiel akzeptiert proc zwei Zeichenketten, von denen es un-
endlich viele gibt; die Gleichheit zu berprfen, wrde also unendlich
lange dauern. Expect versucht es darum gar nicht erst, sondern sieht es
als notwendige (nicht als hinreichende) Bedingung fr die Gleichheit
zweier Prozeduren an, da sie Wert desselben lambda-Ausdrucks sind.
Expect testet also bei Prozeduren auf sogenannte intensionale Gleichheit,
was soviel heit, da expect vergleicht, auf welche Weise die beiden Pro-
zeduren entstanden sind, nicht aber, ob sich die beiden Prozeduren
gleich verhalten. Die letztere Eigenschaft heit extensionale Gleichheit
und ist, wie gesagt, nicht effektiv testbar.
Der lambda-Ausdruck der Prozedur, die von (curry (uncurry proc))
geliefert wird, ist aber der Rumpf von curry, whrend der lambda-
Ausdruck von proc i.d.R. woanders steht; damit sind die beiden Proze-
Eigenschaften von Prozeduren 121
(check-property
(for-all ((a string)
(b string)
(proc (string string -> string)))
(expect ((uncurry (curry proc)) a b)
(proc a b))))
Als erstes Beispiel fr den Beweis an einem Programm dient der Beweis
der Kommutativitt von +. Der Beweis ist nicht besonders tiefgreifend,
demonstriert aber die wichtigsten Techniken, die beim Beweisen von
Programmen zum Einsatz kommen. Zu beweisen ist:
(= (+ a b) (+ b a))
= . . . = #t
. . . und zwar fr beliebige Bindungen von a und b an Zahlen. Seien
die Zahlen, die an a bzw. b gebunden sind, x und y mit x, y C. (Die
mathematischen Namen knnten auch a und b sein, aber das birgt
ein Verwirrungsrisiko mit a und b.) Wenn nun also der obige Term fr
bestimmte Werte von x und y im Substitutionsmodell reduziert wird,
wird zuerst x fr a und y fr b eingesetzt. Fr x = 5 und y = 17 also:
(= (+ 5 17) (+ 17 5))
(= (+ a b) (+ b a))
= (= (+ d x e dye) (+ dye d x e))
Dort ist der erste Teilausdruck unterstrichen, der beim ersten Substitu-
tionsschritt ersetzt wird. Wenn die Scheme-Prozedur + tatschlich die
mathematische Operation + realisiert,1 wird der Teilausdruck (+ d x e
dye) durch x + y ersetzt beziehungsweise durch die Zahl, fr die der
mathematische Ausdruck x + y steht. Es kommt also wieder d_e zum
Einsatz:
(= (+ d x e d y e) (+ dye d x e))
= (= d x + ye (+ dye d x e))
= (= d x + ye dy + x e)
= d x + y = y + x e
= #t
Als erstes Beispiel dient die Reflexivitt. Es gilt fr die Bindung von
lis an eine beliebige Liste von Zahlen folgendes zu beweisen:
Leere Liste. Angenommen, l ist die leere Liste. Dann beginnt die
Reduktion folgendermaen:
(number-list=? d l e d l e)
= ((lambda (lis-1 lis-2) ...) d l e d l e)
= (cond ((empty? d l e) ...) ((pair? d l e) ...))
= (cond ((empty? d l e) ...) ((pair? d l e) ...))
= (cond (#t (cond ...)) ((pair? d l e) #f))
= (cond ((empty? d l e) #t) ((pair? d l e) #f))
= (cond (#t #t) ((pair? d l e) #f))
= #t
Diese knnen wir benutzen. Zunchst einmal mssen wir aber soweit
reduzieren wie mglich:
(number-list=? d l e d l e)
= ((lambda (lis-1 lis-2) ...) dl e dl e)
= (cond ((empty? dl e) ...) ((pair? dl e) ...))
= (cond (#f ...) ((pair? dl e) ...))
= (cond (#t (cond ...)))
= (cond ((empty? d l e) ...) ((pair? d l e) ...))
= (cond (#f ...) ((pair? d l e) ...))
= (cond (#t (and ...)))
= (and (= (first d l e) (first d l e)) (number-list=? ...))
(factorial d k e)
= . . . = dk!e
(factorial 0)
Longrightarrow d0!e
3. Beweis fr k = 0:
(factorial 0)
= ((lambda (n) ...) 0)
= (if (= 0 0) ...)
= (if #t 1 ...)
= 1
= d0!e
4. Induktionsvoraussetzung:
(factorial d k e)
= . . . = dk!e
(factorial d k + 1e)
= . . . = d(k + 1)!e
(define f
(lambda (n)
(if (= n 0)
0
(+ (f (- n 1))
(/ 1 (* n (+ n 1)))))))
Ein Beweis schafft Sicherheit. Wieder gehen wir nach dem bekannten
Schema vor:
1. Behauptung:
Fr alle k N gilt:
(f d k e)
= . . . = d k+k 1 e
2. k = 0:
(f d0e)
=...= d 0+0 1 e
3. Beweis:
(f d0e)
= ((lambda (n) ...) 0)
= (if (= 0 0) 0 ...)
= (if #t 0 ...)
= 0
= d 0+0 1 e
4. Induktionsvoraussetzung:
(f d k e)
= . . . = d k+k 1 e
6. Beweis:
(f d k + 1e)
= ((lambda (n) (if ...)) dk + 1e)
= (if (= dk + 1e 0) ...)
126 Kapitel 10
10.6 Invarianten
(! n)
= (! dke)
= ((lambda (n) (!-helper n 1)) dke)
= (!-helper dke 1)
= ((lambda (n acc) ...) dke 1)
= (if (= dke 0) 1 (!-helper (- dke 1) (* 1 dke)))
Hier gibt es zwar einen rekursiven Aufruf mit Argument (- dke 1),
aber der Akkumulator hat sich auch verndert. Damit ist die naheliegende
Induktionsannahme fr (!-helper (- dke 1) d ae) (falls der Wert des
Akkumulators acc a ist) wertlos. Prozeduren mit Akkumulator sind also
Eigenschaften von Prozeduren 127
(((1 4) 3) 2) 1
a 0! = a 1 = a = N!
( a k ) ( k 1) ! = a ( k ( k 1) !
= a k!
= N!
; n/(n+1) berechnen
(: f (natural -> natural))
128 Kapitel 10
(define f
(lambda (n)
(f-helper n 0)))
(define f-helper
(lambda (n acc)
(if (= n 0)
acc
(f-helper (- n 1)
(+ (/ 1 (* n (+ n 1)))
acc)))))
Aufgaben
1. DeMorgan
2. Reflexivitt
3. Symmetrie
4. Antisymmetrie
5. Transitivitt
6. linksneutrales Element
7. rechtsneutrales Element
8. inverses Element
(uncurry (curry p2 )) p2
(curry (uncurry p1 )) p1
(uncurry (curry p2 )) p2
Aufgabe 10.11 Beweisen Sie die entsprechend dem Beweis der Kom-
mutativitt von + in Abschnitt 10.4.1 die Assoziativitt von + sowie die
Distributivitt von + und * aus Abschnitt 10.1.1.
Formulieren Sie dazu auch eine Eigenschaft und berprfen Sie diese
mit check-property.
(define square-helper
(lambda (n acc)
(if (= n 0)
acc
(square-helper (- n 1)
(+ acc
(- (+ n n) 1))))))
Formulieren Sie dazu auch eine Eigenschaft und berprfen Sie diese
mit check-property.
Die Lsung des Problems soll eine Prozedur load-list sein, welche eine
Liste der Artikel zurckliefert, die in den Lastwagen geladen werden
sollen. Neben der Liste der Artikel braucht load-list auch noch die
Tragfhigkeit eines Lastwagens. Die Prozedur soll Kurzbeschreibung
und Signatur wie folgt haben:
Wenn keine Artikel da sind, kommen auch keine in den Lastwagen. Die
Liste im ersten Zweig ist also leer. Der zweite Fall ist etwas komplizierter.
Das liegt daran, da es dort eine weitere Fallunterscheidung gibt, je nach
dem ersten Artikel (first articles): die Prozedur mu entscheiden,
ob dieser erste Artikel schlielich in den Lastwagen kommen soll oder
nicht. Ein erstes Ausschlukriterium ist, wenn der Artikel schwerer ist
als die Tragfhigkeit erlaubt:
(define load-list
(lambda (articles capacity)
(cond
((empty? articles) empty)
((pair? articles)
(if (> (article-weight (first articles)) capacity)
(load-list (rest articles) capacity)
... (load-list (rest articles) capacity) ...)))))
Damit ist die Frage, ob der erste Artikel im Lastwagen landet, aber
immer noch nicht abschlieend beantwortet. Schlielich mu load-list
noch entscheiden, ob unter Verwendung dieses Artikels der Lastwagen
optimal vollgepackt werden kann. Dazu mu die Prozedur vergleichen,
wie ein Lastwagen mit dem ersten Artikel und wie er ohne diesen Artikel
am besten vollgepackt werden wrde. Die Variante ohne wird mit
folgendem Ausdruck ausgerechnet:
(load-list (rest articles) capacity)
Fortgeschrittenes Programmieren mit Rekursion 133
Die Variante mit ist etwas trickreicher sie entsteht, wenn im Last-
wagen der Platz fr den ersten Artikel reserviert wird und der Rest
der Tragfhigkeit mit den restlichen Artikeln optimal gefllt wird. Die
optimale Fllung fr den Rest wird mit folgendem Ausdruck berechnet,
der die Induktionsannahme fr load-list benutzt:
(define load-list
(lambda (articles capacity)
(cond
((empty? articles) empty)
((pair? articles)
(if (> (article-weight (first articles)) capacity)
(load-list (rest articles) capacity)
... (load-list (rest articles) capacity) ...
... (make-pair (first articles)
(load-list
(rest articles)
(- capacity
(article-weight (first articles)))))
...)))))
(define load-list
(lambda (articles capacity)
(cond
((empty? articles) empty)
((pair? articles)
(if (> (article-weight (first articles)) capacity)
(load-list (rest articles) capacity)
(let ((articles-1 (load-list (rest articles) capacity))
(articles-2
(make-pair (first articles)
(load-list
(rest articles)
(- capacity
(article-weight (first articles)))))
...))))))))
134 Kapitel 11
(define load-list
(lambda (articles capacity)
(cond
((empty? articles) empty)
((pair? articles)
(let ((first-weight (article-weight (first articles))))
(if (> first-weight capacity)
(load-list (rest articles) capacity)
(let ((articles-1 (load-list (rest articles) capacity))
(articles-2
(make-pair (first articles)
(load-list
(rest articles)
(- capacity first-weight)))
...)))))))))
(define load-list
(lambda (articles capacity)
(cond
((empty? articles) empty)
((pair? articles)
(let ((first-weight (article-weight (first articles))))
(if (> first-weight capacity)
(load-list (rest articles) capacity)
(let ((articles-1 (load-list (rest articles) capacity))
(articles-2
(make-pair (first articles)
(load-list
(rest articles)
(- capacity first-weight)))))
(if (> (articles-weight articles-1)
(articles-weight articles-2))
articles-1
articles-2))))))))
(define articles-weight
(lambda (articles)
Fortgeschrittenes Programmieren mit Rekursion 135
(cond
((empty? articles) ...)
((pair? articles)
... (first articles) ...
... (articles-weight (rest articles)) ...))))
Das Gesamtgewicht der leeren Liste ist 0 der erste Fall ist also wieder
einmal einfach. Im zweiten Fall interessiert vom ersten Artikel nur das
Gewicht:
(define articles-weight
(lambda (articles)
(cond
((empty? articles) 0)
((pair? articles)
... (article-weight (first articles)) ...
... (articles-weight (rest articles)) ...))))
Bei den rekursiven Prozeduren der vergangenen Kapitel war der Wert
eines rekursiven Aufrufs stets unabhngig vom Kontext: Die Fakultt
von 4 wute nicht, da sie spter noch mit 5 multipliziert wird, die
Summe der Zahlen von 1 bis 4 wute nicht, da spter noch 5 dazu-
addiert wird, etc. Manche Probleme sind aber so formuliert, da bei der
Berechnung ein Zwischenergebnis mitgefhrt und aktualisiert wird. Die
Konstruktionsanleitungen fr Prozeduren, die Listen oder natrliche
Zahlen verarbeiten, fhren aber bei direkter Anwendung zu Prozeduren,
die kein Zwischenergebnisses mitfhren knnen: Solche Probleme erfor-
dern deshalb eine neue Programmiertechnik, das Programmieren mit
Akkumulatoren, und entsprechend angepate Konstruktionsanleitungen.
Gefragt ist eine Prozedur, welche eine Liste invertiert, also die Reihen-
folge ihrer Elemente umdreht:
; Liste umdrehen
(: invert ((list-of %a) -> (list-of %a)))
Der Ausdruck (invert (rest lis)) liefert den Rest der Liste in umge-
kehrter Reihenfolge. Falls lis, wie im zweiten Testfall, also die Liste
#<list 1 2 3 4> ist, so ist der invertierte Rest #<list 4 3 2>. Das ge-
wnschte Ergebnis #<list 4 3 2 1> entsteht durch das Anhngen des
ersten Elements hinten an die Liste. Durch Wunschdenken wird eine
Prozedur append-element angenommen, die hinten an eine Liste ein
Element anhngt:
; Element an Liste anhngen
(: append-element ((list-of %a) %a -> (list-of %a)))
138 Kapitel 12
der Lnge 400 mehr als doppelt so lang wie das Invertieren einer Liste
der Lnge 200 bentigt. Das liegt daran, da invert bei jedem rekursiven
Aufruf append-element aufruft, und append-element selbst macht soviele
rekursive Aufrufe wie die Liste lang ist. Das wiederum heit aber, da
die Gesamtanzahl der Prozeduraufrufe fr das Invertieren einer Liste
der Lnge n so steigt wie in der Kurve in Abbildung 12.1 gezeigt, also
offenbar strker als linear: Das erklrt das berproportionale Ansteigen
der Rechenzeit. (Dafr ist auch Aufgabe 12.1 relevant.) Dies ist fr so
eine einfache Aufgabe inakzeptabel: Listen der Lnge 10000 sind nichts
ungewhnliches, und das Invertieren sollte dem Computer leichtfallen.
Tatschlich gibt es eine bessere Methode, eine Liste umzudrehen: Die
obige invert-Prozedur konstruiert die Ergebnisliste, indem stets Ele-
mente hinten angehngt werden. Das entspricht nicht der natrlichen
Konstruktion von Listen mit make-pair, das ein Element vorn anhngt.
Das Ergebnis liee sich aber durch Anhngen vorn ganz einfach konstru-
ieren, und zwar, indem in folgender Reihenfolge Zwischenergebnisse
berechnet werden, wie in folgendem Beispiel fr den Testfall (invert
(list 1 2 3 4)):
#<empty-list>
#<list 1>
#<list 2 1>
#<list 3 2 1>
#<list 4 3 2 1>
(define invert-helper
(lambda (lis acc)
...))
Die Liste lis ist nach wie vor die bestimmende Eingabe, es greifen
also die entsprechenden Konstruktionsanleitungen fr gemischte und
zusammengesetzte Daten:
(define invert-helper
140 Kapitel 12
(define invert-helper
(lambda (lis acc)
(cond
((empty? lis) acc)
((pair? lis)
... (invert-helper (rest lis)
(make-pair (first lis) acc)) ...))))
Die neue Hilfsprozedur invert-helper pat nicht auf die Signatur von
invert; invert mu also separat definiert werden und den passenden
Anfangswert fr acc bergeben:
(define invert
(lambda (lis)
(invert-helper lis empty)))
Die neue Version von invert kommt ohne append-element aus. Der
Beispielaufruf von oben fhrt zu folgender Auswertung im Substituti-
onsmodell, die sich auch im Stepper gut nachvollziehen lt:
Programmieren mit Akkumulatoren 141
Da die Prozedur invert generell ntzlich ist, ist sie unter dem Namen
reverse fest eingebaut.
Die letrec-Form bindet lokale Variablen, hnlich wie let. Ihre Syntax
ist mit der von let identisch. Whrend bei let die Variablen, die an
die Werte der Ausdrcke gebunden werden, in den Ausdrcken selbst
nicht sichtbar sind, sind bei letrec die Bindungen sichtbar.
1u 4 = 4
4 u 3 = 12
u
12 2 = 24
u
24 1 = 24
u
24
(check-expect (! 0) 1)
(check-expect (! 3) 6)
(check-expect (! 5) 120)
Wie aus der Beispielrechnung ersichtlich ist, wird aus dem alten
Zwischenergebnis das neue Zwischenergebnis, indem jeweils mit n
multipliziert wird:
(letrec
((!-helper
(lambda (n acc)
(if (= n 0)
acc
... (!-helper (- n 1) (* n acc)) ...))))
Wie schon bei invert ist es nicht notwendig, da fr die noch ver-
bleibenden Ellipsen etwas eingesetzt wird; das Programm ist bereits
fertig:
(: ! (natural -> natural))
(define !
Programmieren mit Akkumulatoren 143
(lambda (n)
(letrec
((!-helper
(lambda (n acc)
(if (= n 0)
acc
(!-helper (- n 1) (* n acc)) ...))))
(!-helper n 1))))
(define proc
(lambda (lis)
(letrec
((proc-helper
(lambda (lis acc)
(cond
((empty? lis) acc)
((pair? lis)
(proc-helper (rest lis)
(... (first lis) ... acc ...)))))))
(proc-helper lis z))))
Hier ist proc der Name der zu definierenden Prozedur und proc-helper
der Name der Hilfsprozedur mit Akkumulator. Der Anfangswert fr
den Akkumulator also das initiale Zwischenergebnis ist der Wert von
z. Der Ausdruck, der fr (... (first lis) ... acc ...) einzusetzen
ist, macht aus dem alten Zwischenergebnis acc das neue Zwischener-
gebnis.
Die Schablone fr Prozeduren mit Akkumulator, die natrliche Zah-
len akzeptieren, ist analog:
(: proc (natural -> ...))
(define proc
(lambda (n)
(letrec
((proc-helper
144 Kapitel 12
(lambda (n acc)
(if (= n 0)
acc
(proc-helper (- n 1) (... acc ...))))))
(proc-helper n z))))
= (* 4 (* 3 (* 2 (* 1 (! (- 1 1))))))
= (* 4 (* 3 (* 2 (* 1 (! 0)))))
= (* 4 (* 3 (* 2 (* 1 (if (= 0 0) 1 (* 0 (! (- 0 1))))))))
= (* 4 (* 3 (* 2 (* 1 (if #t 1 (* 0 (! (- 0 1)))))))))
= (* 4 (* 3 (* 2 (* 1 1))))
= (* 4 (* 3 (* 2 1)))
= (* 4 (* 3 2))
= (* 4 6)
= 24
auswertet:
4 (3 (2 (1 1)))
multipliziert die Variante mit Akkumulator von links:
(((1 4) 3) 2) 1
(define build-list
(lambda (n)
(if (= n 0)
empty
(make-pair n (build-list (- n 1))))))
(define build-list
(lambda (n)
(letrec
((build-list-helper
(lambda (n acc)
(if (= n 0)
acc
(build-list-helper (- n 1) (make-pair n acc))))))
(build-list-helper n empty))))
Diese Variante ist inkorrekt: Sie liefert z.B. fr (build-list 3) das Er-
gebnis #<list 1 2 3>, die Elemente der Liste sind also in umgekehrter
Reihenfolge. Da schon die Fakulttsprozedur mit Akkumulator die Mul-
tiplikationen gegenber der Variante ohne Akkumulator in umgekehrter
Reihenfolge durchgefhrt hat, war dies allerdings zu erwarten, und ist
ein generelles Phnomen bei der Berechnung von Listen-Ausgaben mit
Akkumulator. Das Problem kann durch das Umdrehen der Ergebnisliste
gelst werden:
(letrec
((build-list-helper
(lambda (n acc)
(if (= n 0)
(reverse acc)
(build-list-helper (- n 1) (make-pair n acc))))))
Programmieren mit Akkumulatoren 147
Anmerkungen
Bei der Auswertung von Programmen durch den Computer wird fr die
Verwaltung von Kontexten Speicherplatz bentigt: Bei rekursiven Pro-
zeduren ohne Akkumulator wchst dieser Speicherplatz mit der Gre
der Argumente. Entsprechend wird prinzipiell kein Speicherplatz ben-
tigt, wenn kein Kontext anfllt. In Scheme wird auch tatschlich kein
Speicherplatz fr endrekursive Aufrufe verbraucht; dies ist allerdings
bei vielen anderen Programmiersprachen nicht der Fall. Mehr dazu in
Kapitel 17.
Aufgaben
Aufgabe 12.1 Entwicklen Sie eine Formel fr die Anzahl der rekursiven
Aufrufe in der ersten Version von invert! (Hinweis: Greifen Sie auf die
Gausche Summenformel zurck.)
Aufgabe 12.3 Schreiben Sie eine Prozedur, die als Eingabe eine Liste
von Kursen einer Aktie (als Zahlen) eines Tages akzeptiert (nach Tages-
zeit aufsteigend sortiert), und als Rckgabewert den hchstmglichen
Gewinn liefert, die durch den Kauf und folgenden Verkauf der Aktie
an diesem Tag erreicht werden kann.
Hinweis: Diese Prozedur bentigt zwei Akkumulatoren.
Aufgabe 12.4 Schreibe zu der Prozedur power aus Aufgabe 7.2 eine
endrekursive Variante.
Aufgabe 12.5 Identifizieren Sie die Kontexte der Aufrufe der Prozedu-
ren namens p in folgenden Ausdrcken:
(+ (p (- n 1)) 1)
(p (- n 1) acc)
(* (p (rest lis)) b)
(+ (* 2 (p (- n 1))) 1)
(p (- n 1) (* acc n))
(f (p n))
(+ (f (p n)) 5)
(p (f (- n 1)) (* n (h n)))
(+ (f (p n)) (h n))
Aufgabe 12.8 Schreibe endrekursive Varianten von evens und odds aus
Aufgabe 7.3 auf Seite 82. Falls du Hilfsprozeduren auf Listen dafr
benutzt, gib auch dafr endrekursive Definitionen an.
Aufgabe 12.9 Schreiben Sie eine endrekursive Variante von power aus
Aufgabe 7.2 von Seite 82.
13 Bume
13.1 Binrbume
Viele Anwendungen von Bumen bauen auf einem Spezialfall auf, den
binren Bumen oder Binrbumen.
Die Binrbaume bilden eine induktiv definierte Menge. Ein Baum ist
eins der folgenden:
Der leere Binrbaum ist ein Binrbaum.
Ein Knoten, bestehend seinerseits aus zwei Binrbumen, genannt lin-
ker und rechter Teilbaum des Knotens und einer beliebigen Markierung
ist ebenfalls ein Binrbaum.
Auf den ersten Blick scheint hier ein Mibrauch vorzuliegen immerhin
handelt es sich bei leeren Bumen eindeutig nicht um zusammengesetz-
te Daten: Der Record-Typ hat kein einziges Feld. Record-Typen haben
150 Kapitel 13
aber noch die Funktion, neue Datensorten einzufhren, und sind darum
auch dann das Mittel der Wahl fr die Realisierung gemischter Daten,
wenn es sich nicht wirklich um zusammengesetzte Daten handelt. In
diesem Fall reicht es, nur einen leeren Baum zu haben, genauso wie es
nur eine leere Liste gibt:
(define node-of
(lambda (x)
(signature
(node-of* x (tree-of x) (tree-of x)))))
Damit kann ein Baum wie der in Abbildung 13.1 durch folgenden
Scheme-Ausdruck konstruiert werden:
(: t (tree-of string))
(define t
(make-node
"A"
(make-node
"B"
(make-node
"C"
the-empty-tree
(make-node "D" the-empty-tree the-empty-tree))
the-empty-tree)
(make-node
"E"
(make-node "F" the-empty-tree the-empty-tree)
the-empty-tree)))
Bume 151
(: t2 (tree-of integer))
(define t2 (make-node 17 (make-node 3 the-empty-tree t1) the-empty-tree))
Als Beispiel fr das Programmieren mit Bumen dient die Tiefe eines
Binrbaums, also die maximale Anzahl von Ebenen im Bild des Bi-
nrbaums. Hier sind Kurzbeschreibung, Signatur, Testflle und Gerst:
; Tiefe eines Baums berechnen
(: depth ((tree-of %a) -> natural))
(define depth
(lambda (tree)
...))
Der erste Fall ist einfach: Der leere Baum hat die Tiefe 0. Im zweiten
Fall geht es um Knoten, die wiederum Bume enthalten. Genau wie bei
Listen gibt es also Selbstreferenzen und damit Rekursion:
(define depth
(lambda (t)
(cond
((empty-tree? t)
0)
((node? t)
... (node-label t) ...
... (depth (node-left-branch t)) ...
... (depth (node-right-branch t)) ...))))
Die Markierung spielt keine Rolle fr die Tiefe, kann also wegfallen.
Bei den Teilbumen spielt fr die Tiefe des Knotens nur der tiefere der
152 Kapitel 13
beiden eine Rolle. Der Knoten ist um eins tiefer als das Maximum der
Tiefen der Teilbume:
(define depth
(lambda (t)
(cond
((empty-tree? t)
0)
((node? t)
(+ 1
(max (depth (node-left-branch t))
(depth (node-right-branch t))))))))
(Max ist eine eingebaute Prozedur in Scheme, die das Maximum ihrer
Argumente ermittelt.)
Auch depth folgt einer Schablone, die fr viele Prozeduren auf Bu-
men gilt; Aufgabe 13.1 beschftigt sich damit. Ihr folgt auch die Pro-
zedur node-count, welche die Anzahl der Knoten in einem Binrbaum
liefert:
; Knoten in Baum zhlen
(: node-count ((tree-of %a) -> natural))
(define node-count
(lambda (t)
(cond
((empty-tree? t)
0)
((node? t)
(+ 1
(node-count (node-left-branch t))
(node-count (node-right-branch t)))))))
13.2 Suchbume
sind als die Markierung des Knotens selbst. Diese Eigenschaft des
Baums heit auch Suchbaumeigenschaft (bezglich der gewhlten totalen
Ordnung). Abbildung 13.2 zeigt einen Suchbaum ber Buchstaben, die
alphabetisch geordnet sind.
Die Markierung eines Knotens bestimmt, in welchem Teilbaum des
Knotens eine gesuchte Markierung stecken mu, wenn diese nicht
sowieso schon die gesuchte ist: Ist die gesuchte Markierung kleiner
als die des Knotens, so mu sie (wenn berhaupt) im linken Teilbaum
stecken; wenn sie grer ist, im rechten. Insbesondere ist es nicht ntig,
im jeweils anderen Teilbaum nach der Markierung zu suchen.
Fr Suchbume wird ein neuer Record-Typ definiert. Zu einem Such-
baum gehren neben dem Baum selbst auch noch Operationen fr
Gleichheit und die Kleiner-als-Relation auf den Markierungen, beide
reprsentiert durch Prdikate (die zum Binrbaum und zueinander
passen mssen). Genau wie Bume sind auch Suchbume parametrisch:
; Ein Suchbaum besteht aus
; - einer Prozedur, die zwei Markierungen auf Gleichheit testet,
; - einer Prozedur, die vergleicht, ob eine Markierung kleiner als die andere ist
; - einem Binrbaum
(: make-search-tree ((%a %a -> boolean)
(%a %a -> boolean)
(tree-of %a)
-> (search-tree-of %a)))
(: search-tree? (any -> boolean))
(: search-tree-label-equal-proc ((search-tree-of %a) -> (%a %a -> boolean)))
(: search-tree-label-less-than-proc ((search-tree-of %a) -> (%a %a -> boolean)))
(: search-tree-tree ((search-tree-of %a) -> (tree-of %a)))
(define search-tree-of
(lambda (x)
(signature
(search-tree-of* (x x -> boolean) (x x -> boolean) (tree-of x)))))
(define s1
154 Kapitel 13
(make-search-tree
= <
(make-node 5
(make-node 3 the-empty-tree the-empty-tree)
(make-node 17
(make-node 10
the-empty-tree
(make-node 12 the-empty-tree the-empty-tree))
the-empty-tree))))
(define search-tree-member?
(lambda (l s)
(let ((label-equal? (search-tree-label-equal-proc s))
(label-less-than? (search-tree-label-less-than-proc s)))
(letrec
;; member? : tree -> bool
((member?
(lambda (t)
(cond
((empty-tree? t) #f)
((node? t)
(cond
((label-equal? (node-label t) l)
#t)
((label-less-than? l (node-label t))
(member? (node-left-branch t)))
(else
(member? (node-right-branch t)))))))))
(member? (search-tree-tree s))))))
gefunden. Ansonsten wird member? entweder auf den linken oder den
rechten Teilbaum angewendet, je nachdem, in welchem Teilbaum die
Markierung stehen mu.
Search-tree-member? kann nur richtig funktionieren, wenn das Argu-
ment s tatschlich die Suchbaumeigenschaft erfllt. Rein prinzipiell ist
es mglich, durch Mibrauch von make-search-tree einen Wert vom
Typ search-tree zu erzeugen, der nicht die Suchbaumeigenschaft er-
fllt, wie etwa s2 hier:
(define s2
(make-search-tree
= <
(make-node 5
(make-node 17 the-empty-tree the-empty-tree)
(make-node 3 the-empty-tree the-empty-tree))))
(define s3
(search-tree-insert
5
(search-tree-insert
17
(search-tree-insert
3
(make-empty-search-tree = <)))))
Die Testflle werden dann wie zuvor mit Hilfe von search-tree-member?
formuliert:
(define search-tree-insert
(lambda (l s)
(let ((label-equal? (search-tree-label-equal-proc s))
(label-less-than? (search-tree-label-less-than-proc s)))
(letrec
; (: insert (tree-of %a) -> (tree-of %a))
((insert
(lambda (t)
(cond
((empty-tree? t)
(make-node l the-empty-tree the-empty-tree))
((node? t)
(cond
((label-equal? l (node-label t))
t)
((label-less-than? l (node-label t))
(make-node (node-label t)
(insert (node-left-branch t))
(node-right-branch t)))
(else
(make-node (node-label t)
(node-left-branch t)
(insert (node-right-branch t))))))))))
(make-search-tree
label-equal? label-less-than?
(insert (search-tree-tree s)))))))
Die erste Eigenschaft ergibt ohne die zweite wenig Sinn: Sie wre auch
erfllt, wenn search-tree-member? immer #t liefern wrde.
Fr einen Test mit for-all mssen beliebige Suchbume betrachtet
werden. Allerdings funktioniert der Ansatz
Der Test ist nur sinnvoll, wenn el nicht Element der Liste els ist: Das
mu erst einmal berprft werden, und zwar durch eine Prozedur, die
testet, ob ein Wert Element einer Liste ist. Hier sind Kurzbeschreibung
und Signatur:
; ist Wert Element einer Liste?
(: member? ((%a %a -> boolean) %a (list-of %a) -> boolean))
Bume 159
(define member?
(lambda (= el lis)
(cond
((empty? lis) ...)
((pair? lis)
... (first lis)
... (member? = el (rest lis)) ...))))
Im empty?-Zweig ist die Liste leer, das Ergebnis also #f. Im anderen
Fall mu die Prozedur feststellen, ob (first lis) gerade das gesuchte
Element el ist. Vollstndig sieht die Prozedur so aus:
(define member?
(lambda (= el lis)
(cond
((empty? lis) #f)
((pair? lis)
(if (= el (first lis))
#t
(member? = el (rest lis)))))))
(check-property
(for-all ((els (list-of natural))
(el natural))
(==> (not (member? = el els))
(not (search-tree-member? el (list->search-tree = < els))))))
ist der leere Baum. Der dann zurckgegebene Baum der Form
erfllt offensichtlich die Suchbaumeigenschaft.
ist ein Knoten, dessen Markierung mit l bereinstimmt. Dann gibt
insert zurck. Da nach Voraussetzung die Suchbaumeigenschaft
erfllt, ist auch hier die Suchbaumeigenschaft erhalten.
ist ein Knoten, dessen Markierung grer ist als l, sieht also so
aus: wobei sowohl a als auch b selbst die Suchbaumeigenschaft
erfllen. In diesem Fall sieht der entstehende Baum folgendermaen
aus: Per Induktionsannahme erfllt (insert d ae) die Suchbau-
meigenschaft. Da b auch die Suchbaumeigenschaft erfllt, mu nur
noch gezeigt werden, da alle Markierungen in (insert d ae) kleiner
sind als m. Es gibt in insert drei Aufrufe von make-node, die neue
Knoten erzeugen knnen. Alle fgen hchstens l zu der Menge der
Markierungen des Baumes hinzu. Alle anderen Markierungen sind
nach Voraussetzung kleiner als m, ebenso wie l. Das Resultat erfllt
also ebenfalls die Suchbaumeigenschaft.
Im vierten Fall ist ein Knoten, dessen Markierung kleiner ist als l.
Dieser Fall geht analog zum dritten Fall.
Aufgaben
Aufgabe 13.2 Schreiben Sie eine Prozedur, die einen Binrbaum akzep-
tiert und eine Liste aller Markierungen in dem Baum zurckgibt.
Suchbaum ist.
Besser wre also, wenn beim Lschen soviel wie mglich des rest-
lichen Baums intakt bleibt: das soll fr die berlegungen erst einmal
die Maxime sein. Hypothetisch wre es mglich, da dieser Ansatz
nicht zum Ziel fhrt und diese Annahme wieder rckgngig gemacht
werden mu. Darum ist es sinnvoll, die Annahme deutlich sichtbar zu
dokumentieren:
Annahme: Es ist mglich, ein Element zu lschen, indem nur der Teilbaum verndert
wird, an dessen Wurzel das Element sitzt; der Rest soll gleichbleiben.
(make-node 17
(make-node 5 the-empty-tree the-empty-tree)
the-empty-tree))
(check-expect (search-tree-tree (search-tree-delete 5 s3))
(make-node 3
the-empty-tree
(make-node 17 the-empty-tree the-empty-tree)))
(check-expect (search-tree-tree (search-tree-delete 17 s3))
(make-node 3 the-empty-tree (make-node 5 the-empty-tree the-empty-tree)))
(define search-tree-delete
(lambda (e s)
(let ((=proc (search-tree-label-equal-proc s))
(<proc (search-tree-label-less-than-proc s)))
(letrec
; Element finden und lschen
; (: delete ((tree %a) -> (tree %a))
((delete
(lambda (t)
...))
; Element an Wurzel lschen
; (: delete-top ((node %a (tree %a) (tree %a)) -> (tree %a))
(delete-top
(lambda (n)
...)))
(make-search-tree
=proc <proc
(delete (search-tree-tree s)))))))
Die Hilfsprozedur delete folgt dabei dem gleichen Muster wie die
Hilfsprozeduren in search-tree-member? und search-tree-insert: Die
rekursiven Aufrufe folgen der Struktur des Baums gem der Such-
baumeigenschaft. Wenn des gesuchte Element gefunden ist, kann die
Hilfsprozedur delete-top den Rest der Arbeit bernehmen. Bei delete-top
sind bereits zwei Flle klar: Wenn ein Teilbaum leer ist, so kann der
Baum durch den jeweils anderen Teilbaum ersetzt werden:
(define search-tree-delete
(lambda (e s)
(let ((=proc (search-tree-label-equal-proc s))
(<proc (search-tree-label-less-than-proc s)))
(letrec
; Element finden und lschen
; (: delete ((tree %a) -> (tree %a))
((delete
(lambda (t)
166 Kapitel 14
(cond
((empty-tree? t) t)
((node? t)
(cond
((=proc e (node-label t))
(delete-top t))
((<proc e (node-label t))
(make-node (node-label t)
(delete (node-left-branch t))
(node-right-branch t)))
(else
(make-node (node-label t)
(node-left-branch t)
(delete (node-right-branch t)))))))))
; Element an Wurzel lschen
; (: delete-top ((node %a (tree %a) (tree %a)) -> (tree %a))
(delete-top
(lambda (n)
(cond
((empty-tree? (node-left-branch n))
(node-right-branch n))
((empty-tree? (node-right-branch n))
(node-left-branch n))
(else ...)))))
(make-search-tree
=proc <proc
(delete (search-tree-tree s)))))))
(define s4
(make-search-tree
= <
(make-node 17
(make-node 5 the-empty-tree the-empty-tree)
(make-node 20 the-empty-tree the-empty-tree))))
Fr die Ellipse mu nun also das maximale Element des linken Teil-
baums hochgezogen werden; der rechte Teilbaum bleibt unangetastet.
Das knnte etwa so aussehen:
Aber auch im obigen Ausdruck fehlt noch etwas, nmlich der lin-
ke Teilbaum des neu konstruierten Baums. Der soll alle Elemente
des ursprnglichen Teilbaums finden, auer dem Maximum. Wie kann
delete-top das Maximum loswerden? Am einfachsten durch die Ver-
wendung der Lsch-Prozedur, die gerade geschrieben wird. Erster
Anlauf:
(make-node (find-maximum (node-left-branch n))
(search-tree-delete
(find-maximum (node-left-branch n))
(node-left-branch n))
(node-right-branch n))
(cond
((empty-tree? t) t)
((node? t)
(cond
((=proc e (node-label t))
(delete-top t))
((<proc e (node-label t))
(make-node (node-label t)
(delete e (node-left-branch t))
(node-right-branch t)))
(else
(make-node (node-label t)
(node-left-branch t)
(delete e (node-right-branch t)))))))))
(define search-tree-delete
(lambda (e s)
(let ((=proc (search-tree-label-equal-proc s))
(<proc (search-tree-label-less-than-proc s)))
(letrec
; Element finden und lschen
; (: delete (%a (tree %a) -> (tree %a))
((delete
(lambda (e t)
(cond
((empty-tree? t) t)
((node? t)
(cond
((=proc e (node-label t))
(delete-top t))
((<proc e (node-label t))
(make-node (node-label t)
(delete e (node-left-branch t))
(node-right-branch t)))
(else
(make-node (node-label t)
(node-left-branch t)
(delete e (node-right-branch t)))))))))
; Element an der Wurzel lschen
; (: delete-top ((node %a (tree %a) (tree %a)) -> (tree %a))
(delete-top
Schrittweise Verfeinerung 169
(lambda (n)
(cond
((empty-tree? (node-left-branch n))
(node-right-branch n))
((empty-tree? (node-right-branch n))
(node-left-branch n))
(else
(let ((el (find-maximum (node-left-branch n))))
(make-node el
(delete el (node-left-branch n))
(node-right-branch n)))))))
; Maximum von Teilbaum finden
; (: find-maximum ((tree %a) -> %a))
(find-maximum
(lambda (t)
(cond
((empty-tree? t)
(violation "unerwarteter leerer Baum"))
((node? t)
(let ((right (node-right-branch t)))
(if (empty-tree? right)
(node-label t)
(find-maximum (node-right-branch t)))))))))
(make-search-tree
=proc <proc
(delete e (search-tree-tree s)))))))
Beim Testen fllt auf, da der rekursive Aufruf von find-maximum noch
nicht abgedeckt ist. (Da der Aufruf von violation nicht abgedeckt ist,
ist erwnscht es soll ja nicht passieren.) Es mu also noch ein Testfall
konstruiert werden:
(define s4
(make-search-tree
= <
(make-node 17
(make-node 5 the-empty-tree the-empty-tree)
(make-node 20 the-empty-tree the-empty-tree))))
14.2 Datenverfeinerung
(define a1
(make-apartment
"Entenhausener Strae 15"
"Sperber"
(list (make-room 30) (make-room 50) (make-room 60))))
Schrittweise Verfeinerung 171
(define a2
(make-apartment
"Froschgasse 17"
"Crestani"
(list (make-room 20) (make-room 40))))
(define apartment-area
(lambda (a)
(fold 0 +
(map room-area (apartment-rooms a)))))
make-apartment apartment?
(apartment-address apartment-resident apartment-sections))
Hier ist ein Beispiel fr solche einen untervermieteten Teil sowie ein
Apartment, das es enthlt:
(define s1
(make-sublet "Taschenbier"
(list (make-room 20)
(make-sublet "Sams"
(list (make-room 2)))
(make-room 10))))
(define a3
(make-apartment
"Flugentenschneise 17"
"Rotkohl"
(list (make-room 100)
s1
(make-room 30))))
(define apartment-rooms
(lambda (a)
(fold empty append
(map section-rooms (apartment-sections a)))))
(define section-rooms
(lambda (s)
(cond
((room? s) (list s))
((sublet? s)
(fold empty append
(map section-rooms (sublet-sections s)))))))
Der Prfix x hngt vom Wohnabschnitt ab, in dem der gesuchte Bewoh-
ner wohnt. Per Wunschdenken sei eine Prozedur vorausgesetzt, die in
den Abschnitten einer Wohnung nach dem Bewohner sucht und den
entsprechenden Prfix berechnet:
; Adre-Prfix eines Abschnitts-Bewohners berechnen
(: sections-prefix (string (list section) -> string))
Bei Untervermietungen ist die Arbeit dann erledigt, wenn der Bewohner
gerade der gesuchte ist:
(define sublet-prefix
(lambda (r s)
(if (string=? r (sublet-resident s))
r
...)))
176 Kapitel 14
Dies sieht hnlich aus wie bei apartment-prefix; auch hier funktio-
niert schon der erste Testfall. Fr die Alternative kann sections-prefix
benutzt werden:
(define sublet-prefix
(lambda (r s)
(if (string=? r (sublet-resident s))
r
(let ((prefix (sections-prefix r (sublet-sections s))))
(cond
((not-found? prefix) the-not-found)
((string? prefix)
(string-append prefix " bei " (sublet-resident s))))))))
Damit sieht das Programm fast fertig aus. Allerdings ist der nde-
rung im Vertrag von sections-prefix noch nicht berall Rechnung
getragen worden, namentlich nicht in resident-address: Einerseits
mu resident-address eine Fallunterscheidung fr den Rckgabewert
von sections-prefix einfhren; dies heit andererseits aber auch, da
resident-address selbst in die Lage kommen kann, da der gesuchte
Bewohner nicht gefunden wird. Damit werden neben der Erweiterung
des Rumpfes der Prozedur auch eine nderung des Vertrags und ein
neuer Testfall fllig:
(: resident-address (string apartment -> (mixed string not-found)))
(check-expect (resident-address "Mller" a1) the-not-found)
(define resident-address
(lambda (r a)
(if (string=? r (apartment-resident a))
r
(let ((prefix (sections-prefix r (apartment-sections a))))
(cond
((not-found? prefix)
the-not-found)
((string? prefix)
(string-append prefix
" bei "
(apartment-resident a))))))))
Aufgaben
TBD
16 Der -Kalkl
Nachdem die bisherigen Kapitel den Bogen von der praktischen Kon-
struktion einfacher Programme bis zur objektorientierten Program-
mierung geschlagen haben, beleuchtet dieses Kapitel eine wichtige
theoretische Grundlage der Programmierung.
Fr die Informatik ist der Begriff des logischen Kalkls von zentraler
Bedeutung. Ein Kalkl dient dazu, auf formale Art und Weise wahre
Aussagen abzuleiten, ohne da es dabei ntig wird, ber den Sinn
der Aussagen nachzudenken. Der -Kalkl ist ein logischer Kalkl,
der als die Basis fr eine formale Beschreibung des Verhaltens von
Computerprogrammen dient. Scheme baut direkt auf dem -Kalkl
auf: es ist kein Zufall, da das Schlsselwort fr die Abstraktion lambda
heit. Es gibt noch viele weitere Einsatzgebiete fr den -Kalkl, ins-
besondere bei der Konstruktion von besonders effizienten bersetzern
fr Programmiersprachen, in der Logik und der Linguistik, und bei
der Entwicklung und Sicherheitsberprfung von mobilem Code im
Internet.
hL i hV i
| (L L )
| ( hV i.L )
Ein -Term der Form (e0 e1 ) heit Applikation mit Operator e0 und Ope-
rand e1 . Ein Term der Form (x.e) heit Abstraktion, wobei x Parameter
der Abstraktion heit und e Rumpf. In diesem Kapitel steht e immer fr
einen -Term, v und x stehen fr Variablen.
free, bound : L P (V )
liefern die Mengen der freien bzw. der gebundenen Variablen eines -
Terms.
{v}
falls e=v
def
free(e) = free(e0 ) free(e1 ) falls e = e0 e1
free(e0 ) \ {v} falls e = v.e0
falls e = v
def
bound(e) = bound(e0 ) bound(e1 ) falls e = e0 e1
bound(e0 ) {v} falls e = v.e0
def
Auerdem ist var(e) = free(e) bound(e) die Menge der Variablen von
e. (Es lt sich leicht zeigen, da diese Menge alle vorkommenden
Variablen eines -Terms enthlt.) Ein -Term e heit abgeschlossen bzw.
Kombinator, falls free(e) = .
Einige Beispiele:
free(x.y) = {y}
bound(x.y) = {x}
free(y.y) =
bound(y.y) = {y}
free(x.y.x.x (z.a y)) = { a}
bound(x.y.x.x (z.a y)) = { x, y, z}
In einem Term kann die gleiche Variable sowohl frei als auch gebunden
vorkommen:
f
falls e = v
falls e = x und x 6= v
x
falls e = v.e0
v.e0
def
e[v 7 f ] = x.(e0 [v 7 f ]) falls e = x.e0 und x 6= v, x 6 free( f )
x 0 .(e0 [ x 7 x 0 ][v 7 f ])
falls e = x.e0
und x 6= v, x free( f ), x 0 6 free(e0 ) free( f )
(e0 [v 7 f ]) (e1 [v 7 f ])
falls e = e0 e1
Die Definition der Substitution erscheint auf den ersten Blick kom-
pliziert, folgt aber letztlich nur direkt dem Prinzip der lexikalischen
Bindung. Die erste Regel besagt, da das Vorkommen einer Variable
durch eine Substitution genau dieser Variablen ersetzt wird:
v[v 7 f ] = f
x [v 7 f ] = x x 6= v
Die dritte Regel ist auf den ersten Blick etwas berraschend:
Ein -Ausdruck, dessen Parameter gerade die Variable ist, die substi-
tutiert werden soll, bleibt unverndert. Das liegt daran, da mit dem
-Ausdruck die Zugehrigkeit aller Vorkommen von v in e0 bereits
festgelegt ist: ein Vorkommen von v in e0 gehrt entweder zu dieser
Abstraktion oder einer anderen Abstraktion mit v als Parameter, die in
e0 weiter innen steht v ist in (v.e0 ) gebunden und v bound(v.e0 ).
Da die Substitution diese Zugehrigkeiten nicht verndern darf, lt
sie das v in Ruhe.
Anders sieht es aus, wenn die Variable der Abstraktion eine andere
ist die vierte Regel:
In diesem Fall wird die Substitution auf den Rumpf der Abstraktion
angewendet. Wichtig ist dabei, da x nicht frei in f vorkommt sonst
knnte es vorkommen, da beim Einsetzen von f ein freies Vorkommen
von x pltzlich durch die umschlieende Abstraktion gebunden wird.
Damit wrde auch wieder die durch die lexikalische Bindung definierte
Zugehrigkeitsregel verletzt.
Was passiert, wenn x eben doch frei in f vorkommt, beschreibt die
fnfte Regel:
16.2 Normalformen
((x.(y.y) z) a) (x.z) a
((x.(y.y) z) a) (y.y) z
Definition 16.6 (Normalform) Sei e ein -Term. Ein -Term e0 ist eine
Normalform von e, wenn e e0 gilt und kein -Term e00 existiert mit
e0 e00 .
e1 e2
Abbildung 16.1 stellt die Aussage des Satzes von Church/Rosser gra-
fisch dar. Der Beweis des Satzes ist leider recht umfangreich und tech-
nisch. Die einschlgige Literatur ber den -Kalkl hat ihn vorrtig [?].
Die Church/Rosser-Eigenschaft ebnet den Weg fr Benutzung von
Normalformen zum Finden von Beweisen im -Kalkl:
16.3.1 Verzweigungen
Scheme (if t k a) whlt, abhngig vom Wert von t, entweder die Kon-
sequente k oder die Alternative a aus. Die Nachbildung im -Kalkl
stellt dieses Prinzip auf den Kopf: die Maschinerie fr die Auswahl
zwischen Konsequente und Alternative wird in die booleschen Werte
selbst gesteckt. true ist ein -Term, der das erste von zwei Argumen-
ten auswhlt und das zweite verwirft; false selektiert das zweite und
verwirft das erste:
def
true = xy.x
def
false = xy.y
Damit hat die Verzweigung selbst nicht mehr viel zu tun; sie wendet ein-
fach den Test, der einen booleschen Wert ergeben mu, auf Konsequente
und Alternative an:
def
if = txy.t x y
Da if tatschlich so funktioniert wie angenommen, lt sich an einem
Beispiel leicht sehen:
Die Nachbildung von Zahlen ist etwas komplizierter als die der boo-
leschen Werte. Eine Methode dafr ist die Verwendung von Church-
Numeralen. Das Church-Numeral dne einer natrlichen Zahl n ist eine
Funktion, die eine n-fache Applikation vornimmt.
def
dne = f x. f n ( x )
def
succ = n. f .x.n f ( f x )
def
pred = x.y.z.x (p.q.q ( p y)) ((x.y.x ) z) (x.x )
Der -Kalkl 189
Der Beweis dafr, da sich pred in bezug auf succ wie die Vorgnger-
funktion verhlt, ist bungsaufgabe 16.1.
In Verbindung mit den booleschen Werten lt sich eine Zahl darauf-
hin testen, ob sie 0 ist:
def
zerop = n.n (x.false) true
Nun wre es schn, einen Term zu haben, der zumindest auch die Fa-
kultt von 1 ausrechnen kann. Dazu wird fac0 in seine eigene Definition
anstelle des ? eingesetzt. Das Ergebnis sieht so aus:
Auf die gleiche Art und Weise lt sich ein Term konstruieren, der alle
Fakultten bis 2 ausrechnen kann:
def
fac2 = x.if (zerop x ) 1 ( x (fac1 (pred x )))
Dieser Term soll FAC heien. Nun lassen sich die facn -Funktionen mit
Hilfe von FAC einfacher beschreiben:
def
fac0 = x.if (zerop x ) 1 ( x (? (pred x )))
def
fac1 = FAC fac0
def
fac2 = FAC fac1
def
fac3 = FAC fac2
...
FAC ist also eine Fabrik fr Fakulttsfunktionen und teilt mit allen faci
die Eigenschaft, da ihre Definition nicht rekursiv ist.
Damit ist zwar die Notation weniger schreibintensiv geworden, aber
das fundamentale Problem ist noch nicht gelst: Eine korrekte Defini-
tion von fac mte eine unendliche Kette von Applikationen von FAC
enthalten. Da sich ein Term mit einer unendlichen Kette von Applikatio-
nen nicht aufschreiben lt, hilft im Moment nur Wunschdenken weiter.
Dafr sei angenommen, fac wre bereits gefunden. Dann gilt folgende
Gleichung:
fac FAC fac
Die eine zustzliche Applikation, die FAC vornimmt, landet auf ei-
nem ohnehin schon unendlichen Stapel, macht diesen also auch nicht
grer. Damit ist aber fac ein sogenannter Fixpunkt von FAC: Wenn fac
hineingeht, kommt es auch genauso wieder heraus. Wenn es nun eine
Mglichkeit gbe, fr einen -Term einen Fixpunkt zu finden, wre das
Problem gelst. Der folgende Satz zeigt, da dies tatschlich mglich
ist:
def
Y = f .(x. f ( x x )) (x. f ( x x )).
Der -Kalkl 191
fac 3 = Y FAC 3
(Satz 16.9) FAC (Y FAC) 3
(x.if (zerop x ) 1 ( x ((Y FAC) (pred x )))) 3
if (zerop 3) 1 ( 3 ((Y FAC) (pred 3)))
if false 1 ( 3 ((Y FAC) 2))
3 ((Y FAC) 2)
(Satz 16.9) 3 (FAC (Y FAC) 2)
3 ((x.if (zerop x ) 1 ( x ((Y FAC) (pred x )))) 2)
3 (if (zerop 2) 1 ( 2 ((Y FAC) (pred 2))))
3 (if false 1 ( 2 ((Y FAC) 1)))
3 ( 2 ((Y FAC) 1))
(Satz 16.9) 3 ( 2 (FAC (Y FAC) 1))
3 ( 2 ((x.if (zerop x ) 1 ( x ((Y FAC) (pred x )))) 1))
3 ( 2 (if (zerop 1) 1 ( 1 ((Y FAC) (pred 1)))))
3 ( 2 (if false 1 ( 1 ((Y FAC) 0))))
3 ( 2 ( 1 ((Y FAC) 0)))
(Satz 16.9) 3 ( 2 ( 1 (FAC (Y FAC) 0)))
3 ( 2 ( 1 ((x.if (zerop x ) 1 ( x ((Y FAC) (pred x )))) 0)))
3 ( 2 ( 1 (if (zerop 0) 1 ( 1 ((Y FAC) (pred 0))))))
3 ( 2 ( 1 (if true 1 ( 1 ((Y FAC) (pred 0))))))
3 ( 2 ( 1 1))
6
Dann gilt:
Der -Term Y, der Fixpunkte berechnet, heit Fixpunktkombinator. Mit
seiner Hilfe lt sich die Fakultt definieren:
def
fac = Y FAC
Abbildung 16.2 zeigt, wie die Berechnung der Fakultt von 3 mit
dieser Definition funktioniert.
16.4 Auswertungsstrategien
Leider hat die Anwendung des Satzes von Church/Rosser noch einen
Haken in der Praxis: Er besagt zwar, da sich die quivalenz von zwei
Termen dadurch beweisen lt, da ihre Normalformen verglichen wer-
den. Leider sagt er nichts darber, wie diese Normalformen gefunden
werden.
Zum systematischen Finden von Normalformen gehrt eine Aus-
wertungsstrategie. Eine solche Strategie ist dafr zustndig, von den
-Redexen innerhalb eines -Terms denjenigen auszusuchen, der tat-
schlich reduziert wird. Fr den -Kalkl gibt es mehrere populre
Auswertungsstrategien, die jeweils ihre eigenen Vor- und Nachteile
haben, was das effektive Finden von Normalformen betrifft.
Eine populre Auswertungsstrategie ist die Linksauen-Reduktion,
auch normal-order reduction oder leftmost-outermost reduction genannt:
(v.e) f o e[v 7 f ]
(v.e) f n e[v 7 f ]
i ist dabei nur anwendbar auf Subterme, die mglichst weit links
innen stehen.
zum Beispiel hat zwei Redexe, einmal den ganzen Term und dann noch
bungsaufgaben
adddmedne = dm + ne
multdmedne = dmne
expdmedne = dmn e fr m > 0
(
true falls m = n
=dmedne =
false sonst
def
add = x.y.p.q.xp(ypq)
def
mult = x.y.z.x (yz)
def
exp = x.y.yx
und gibt eine eigene Definition fr = an. Dabei lt sich die Korrektheit
von add direkt beweisen. Fr mult und exp beweise und benutze dazu
folgende Hilfslemmata:
(dne x )m y x nm y
Aufgabe 16.4 (Quelle: Ralf Hinze, Bonn) Zeige, da F mit der folgenden
Definition ebenfalls ein Fixpunktkombinator ist:
def
F = G [26]
def
G = abcde f ghijklmnopqstuvwxyzr.r (dasistein f ixpunktkombinator )
Abschnitt 16.3 zeigte bereits, da sich auch boolesche Werte und Zahlen
im -Kalkl durch -Terme darstellen lassen. Das ist zwar aus theo-
retischer Sicht gut zu wissen, auf Dauer aber etwas mhsam: Darum
ist es sinnvoll, mit einer erweiterten Version des -Kalkls zu arbeiten,
die solche primitiven Werte direkt kennt. Abschnitt 16.3 hat gezeigt,
da eine solche Erweiterung nur syntaktischer Zucker ist, also die Aus-
druckskraft des Kalkls nicht wirklich erhht. Alle Erkenntnisse aus
dem normalen -Kalkl bleiben also erhalten.
Ein solcher erweiterter -Kalkl heit auch angewandter -Kalkl:
| h Bi
| (h1 i hLA i)
| (h2 i hLA i hLA i)
...
| (hn i hLA i ... hLA i) (n-mal)
Die Grammatik ist abgekrzt notiert: Die letzen Klauseln besagen, da
es fr jede Stelligkeit i eine Klausel mit hi i gibt, bei der jeweils i
Wiederholungen von hLA i entsprechend der Stelligkeit der Primi-
tiva in i . Dabei heien Terme der Form ( F k e1 . . . ek ) auch primitive
Applikationen.
In diesem Kapitel dienen normalerweise die Zahlen als Basiswerte mit
den blichen Operationen wie +, , , / etc. Damit sind Terme wie
zum Beispiel (+ ( 5 3) 17) mglich.
Im angewandten -Kalkl kommen zu den Werten aus Definiti-
on 16.12 die Basiswerte dazu:
C = I
Ein Term aus dem angewandten -Kalkl wird mit Hilfe folgender
Funktion in Maschinencode bersetzt:
: L C
A
JK
b falls e =bB
v falls e =vV
def
JeK = Je0 K Je1 K ap falls e = ( e0 e1 )
1 K . . . Jek K prim F k falls e = ( F e1 . . . e k )
Je
(v, Je K)
0 falls e = v.e0
Das Beispiel zeigt deutlich, wie der Rumpf der innersten Abstraktion
in eine lineare Folge von Instruktionen bersetzt wird, die genau der
Call-by-Value-Reduktionsstrategie entspricht: erst f auswerten, dann
x, dann y, dann das Primitiv anwenden, dann +, und schlielich die
Applikation durchfhren.
Nun zur eigentlichen SECD-Maschine sie funktioniert hnlich wie
ein Reduktionskalkl, operiert aber auf sogenannten Maschinenzustn-
den: die Maschine berfhrt also einen Maschinenzustand durch einen
Auswertungsschritt in einen neuen Maschinenzustand. Ein Maschinen-
zustand ist dabei ein 4-Tupel aus der Menge S E C D (daher der
Name der Maschine). Die Buchstaben sind deshalb so gewhlt, weil S
der sogenannte Stack, E die sogenannte Umgebung bzw. auf englisch
das Environment, C der schon bekannte Maschinencode bzw. Code und
D der sogenannte Dump ist. Die formalen Definitionen dieser Mengen
sind wie folgt; dabei ist W die Menge der Werte:
= W
S
E = P (V W )
D = (S E C )
W = B (V C E )
Der Stack ist dabei eine Folge von Werten. In der Maschine sind dies
die Werte der zuletzt ausgewerteten Terme, wobei der zuletzt ausge-
wertete Term vorn bzw. oben steht. Die Umgebung ist eine partielle
Abbildung von Variablen auf Werte: sie ersetzt die Substitution in der
Reduktionsrelation des -Kalkls. Anstatt da Werte fr Variablen ein-
gesetzt werden, merkt sich die Umgebung einfach, an welche Werte die
Variablen gebunden sind. Erst wenn der Wert einer Variablen bentigt
wird, holt ihn die Maschine aus der Umgebung. Der Dump schlie-
lich ist eine Liste frherer Zustnde der Maschine: er entspricht dem
Kontext im Substitutionsmodell.
Die Menge W schlielich entspricht dem Wertebegriff aus Definiti-
on 17.2: Die Basiswerte gehren dazu, auerdem Tripel aus (V C E).
Ein solches Tripel, genannt Closure reprsentiert den Wert einer Ab-
straktion es besteht aus der Variable einer Abstraktion, dem Maschi-
nencode ihres Rumpfs und der Umgebung, die notwendig ist, um die
Abstraktion anzuwenden: Die Umgebung wird bentigt, damit die frei-
en Variablen der Abstraktion entsprechend der lexikalischen Bindung
ausgewertet werden knnen. Dies ist anders als im Substitutionsmodell,
wo Variablen bei der Applikation direkt ersetzt werden und damit
verschwinden. Eine Closure ist also einfach die Reprsentation einer
Funktion.
Im Verlauf der Auswertung werden Umgebungen hufig um neue
Bindungen von einer Variable an einen Wert erweitert. Dazu ist die
Notation e[v 7 w] ntzlich. e[v 7 w] konstruiert aus einer Umgebung
e eine neue Umgebung, in der die Variable v an den Wert w gebunden
ist. Hier ist die Definition:
def
e[v 7 w] = (e \ {(v, w0 )|(v, w0 ) e}) {(v, w)}
, P ((S E C D ) (S E C D ))
(s, e, bc, d) , (bs, e, c, d) (17.1)
(s, e, vc, d) , (e(v)s, e, c, d) (17.2)
(bk . . . b1 s, e, primFk c, d) , (bs, e, c, d) (17.3)
wobei F k k und FBk (b1 , . . . , bk ) = b
0
(s, e, (v, c )c, d) , ((v, c0 , e)s, e, c, d) (17.4)
0
(w(v, c , e0 )s, e, ap c, d) , (e, e0 [v 7 w], c0 , (s, e, c)d) (17.5)
(w, e, e, (s0 , e0 , c0 )d) , (ws0 , e0 , c0 , d) (17.6)
Regel 17.1 (die Literalregel) schiebt einen Basiswert direkt auf den
Stack.
Regel 17.2 (die Variablenregel) ermittelt den Wert einer Variable aus
der Umgebung und schiebt diesen auf den Stack.
Regel 17.3 ist die Primitivregel. Bei einer primitiven Applikation ms-
sen soviele Basiswerte oben auf dem Stack liegen wie die Stelligkeit
des Primitivs. Dann ermittelt die Primitivregel das Ergebnis der
primitiven Applikation und schiebt es oben auf den Stack.
Regel 17.4 ist die Abstraktionsregel: Das Tupel (v, c0 ) ist bei der ber-
setzung aus einer Abstraktion entstanden. Die Regel ergnzt v und c0
mit e zu einer Closure, die auf den Stack geschoben wird.
Regel 17.5 ist die Applikationsregel: Bei einer Applikation mssen oben
auf dem Stack ein Wert sowie eine Closure liegen. (Zur Erinnerung:
Eine Applikation kann nur ausgewertet werden, wenn eine Abstrak-
tion vorliegt. Abstraktionen werden zu Closures ausgewertet.) In
einem solchen Fall sichert die Applikation den aktuellen Zustand
auf den Dump, und die Auswertung fhrt mit einem leeren Stack,
der Umgebung aus der Closure erweitert um eine Bindung fr die
Variable und dem Code aus der Closure fort.
Regel 17.6 ist die Rckkehrregel: Sie ist anwendbar, wenn das Ende
des Codes erreicht ist. Das heit, da gerade die Auswertung einer
Applikation fertig ist. Auf dem Dump liegt aber noch ein gesicherter
Zustand, der jetzt zurckgeholt wird.
evalSECD LA B
:
evalSECD (e) = x wenn (e, , JeK, e) , ( x, e, e, e)
evalSECD L Z
(A
b falls (e, , JeK, e) , (b, e, e, e)
evalSECD (e) =
function falls (e, , JeK, e ) , ((v, c, e0 ), e, e, e )
5
, 5
"Mike ist doof"
, "Mike ist doof"
#t
, #t
(list 1 2 3 4 5 6)
, (1 2 3 4 5 6)
Die REPL druckt also eine Liste aus, indem sie zuerst eine ffnen-
de Klammer ausdruckt, dann die Listenelemente (durch Leerzeichen
getrennt) und dann eine schlieende Klammer.
Das funktioniert auch fr die leere Liste:
empty
, ()
(1 2 3 4 5 6)
, (1 2 3 4 5 6)
(1 #t "Mike" (2 3) "doof" 4 #f 17)
, (1 #t "Mike" (2 3) "doof" 4 #f 17)
()
, ()
5
, 5
"Mike ist doof"
, "Mike ist doof"
#t
, #t
204 Kapitel 17
Mit der Einfhrung von Quote kommt noch eine vllig neue Sorte Wer-
te hinzu: die Symbole. Symbole sind Werte hnlich wie Zeichenketten
und bestehen aus Text. Sie unterscheiden sich allerdings dadurch, da
sie als Literal mit Quote geschrieben und in der REPL ohne Anfh-
rungszeichen ausgedruckt werden:
mike
, mike
doof
, doof
Symbole lassen sich mit dem Prdikat symbol? von anderen Werten
unterscheiden:
(symbol? mike)
, #t
(symbol? 5)
, #f
(symbol? "Mike")
, #f
Vergleichen lassen sich Symbole mit equal? (siehe Abbildung ??):
duftmarke
, duftmarke
lambda
, lambda
+
, +
*
, *
(+ 1 2)
, (+ 1 2)
(lambda (n) (+ n 1))
, (lambda (n) (+ n 1))
Auch wenn diese Werte wie Ausdrcke so aussehen, sind sie doch
ganz normale Listen: der Wert von (+ 1 2) ist eine Liste mit drei
Elementen: das Symbol +, die Zahl 1 und die Zahl 2. Der Wert von
(lambda (n) (+ n 1)) ist ebenfalls eine Liste mit drei Elementen: das
Symbol lambda, eine Liste mit einem einzelnen Element, nmlich dem
Symbol n, und einer weiteren Liste mit drei Elementen: dem Symbol +,
dem Symbol n und der Zahl 1.
Quote hat noch eine weitere verwirrende Eigenheit:
()
, ()
Dieses Literal bezeichnet nicht die leere Liste (dann wrde nur ()
ausgedruckt, ohne Quote), sondern etwas anderes:
(pair? ())
, #t
(first ())
, quote
(rest ())
, (())
Der Wert des Ausdrucks () ist also eine Liste mit zwei Elementen:
das erste Element ist das Symbol quote und das zweite Element ist die
leere Liste. t ist selbst also nur syntaktischer Zucker, und zwar fr
(quote t):
Quote erlaubt die Konstruktion von Literalen fr viele Werte, aber nicht
fr alle. Ein Wert, fr den Quote ein Literal konstruieren kann, heit
reprsentierbarer Wert. Die folgende induktive Definition spezifiziert, was
ein reprsentierbarer Wert ist:
17.4.1 Datenanalyse
Die erste Aufgabe ist dabei zunchst, wie immer, die Datenanalyse: Am
Anfang stehen die Terme des angewandten -Kalkls. Eine geeignete
Reprsentation mit Listen und Symbolen lt dabei die Terme in der
fortgeschrittenen Sprachebene genau wie entsprechenden Scheme-
Terme aussehen:
(+ 1 2) steht fr (+ 1 2)
(lambda (x) x) steht fr x.x
((lambda (x) (x x)) (lambda (x) (x x))) steht fr (x.( x x )) (x.( x x ))
etc.
Die Datendefinition dafr orientiert sich direkt an Definition 17.1:
(define term
(signature
(mixed symbol
application
abstraction
base
primitive-application)))
; Prdikat fr Abstraktionen
(: abstraction? (%a -> boolean))
(define abstraction?
(lambda (t)
(and (pair? t)
(equal? lambda (first t)))))
Die Definition lt noch offen, was genau ein Basiswert und was
ein Primitiv ist. Auch hierfr werden noch Datendefinitionen ben-
tigt, zuerst fr Basiswerte. Der Einfachheit halber beschrnkt sich die
Implementierung erst einmal auf boolesche Werte und Zahlen:
; Prdikat fr Basiswerte
(: base? (%a -> boolean))
(define base?
(lambda (v)
(or (boolean? v) (number? v))))
Da die Primitive genau wie die Variablen Symbole sind, stehen die
Primitive als Variablen nicht mehr zur Verfgung: Alle Symbole, die
keine Primitive sind, sind also Variablen. Das dazugehrige Prdikat
ist das folgende:
; Prdikat fr Primitive
(: primitive? (%a -> boolean))
(define primitive?
(lambda (s)
(or (equal? + s)
(equal? - s)
(equal? * s)
(equal? / s)
(equal? = s))))
Da die Stelligkeit eines Primitivs dem Primitiv fest zugeordnet ist, ist
eine Hilfsprozedur ntzlich, die bei der Erzeugung eines Werts der
Sorte prim die Stelligkeit ergnzt. Glcklicherweise haben alle oben
eingefhrten Primitive die gleiche Stelligkeit:
; Primitiv erzeugen
(: make-prim (symbol -> prim))
(define make-prim
(lambda (s)
(real-make-prim s 2)))
(define term->machine-code
(lambda (e)
(cond
((symbol? e) (list e))
((base? e) (list e))
...)))
(define term->machine-code
(lambda (e)
(cond
...
((application? e)
(append (term->machine-code (first e))
(append (term->machine-code (first (rest e)))
(list (make-ap)))))
...)))
(define term->machine-code
(lambda (e)
(cond
...
((primitive-application? e)
(append
(append-lists
(map term->machine-code (rest e)))
(list (make-prim (first e)))))
...)))
(define term->machine-code
(lambda (e)
(cond
...
((abstraction? e)
(list
(make-abs (first (first (rest e)))
(term->machine-code
(first (rest (rest e))))))))))
(define-record-procedures binding
make-binding binding?
(binding-variable binding-value))
(: make-binding (symbol value -> binding))
Die leere Umgebung wird fter bentigt und wird darum schon vorde-
finiert:
(lambda (e v w)
(make-pair (make-binding v w)
(remove-environment-binding e v))))
Mit Hilfe dieser Definitionen ist es mglich, eine Daten- und eine
Record-Definition fr die Zustnde der SECD-Maschine anzugeben,
also die Tupel aus S E C D:
; Ein SECD-Zustand ist ein Wert
; (make-secd s e c d)
; wobei s ein Stack, e eine Umgebung, c Maschinencode
; und d ein Dump ist
(define-record-procedures secd
make-secd secd?
(secd-stack secd-environment secd-code secd-dump))
(: make-secd (stack environment machine-code dump -> secd))
In diesem Gerst werden nun die Regeln direkt abgebildet. Hier zur
Erinnerung noch einmal die erste Regel fr Basiswerte:
...
(cond
...
((prim? (first code))
(make-secd (make-pair
(apply-primitive
(prim-operator (first code))
(take-reverse (prim-arity (first code)) stack))
(drop (prim-arity (first code)) stack))
environment
(rest code)
dump))
...)
...))
Aus einem Primitiv und einer Liste von Argumenten berechnet apply-primitive
das Resultat der primitiven Applikation. Dabei handelt es sich bei
primitive um eine Fallunterscheidung, der Rumpf der Prozedur ist also
eine entsprechende Verzweigung:
; Delta-Transition berechnen
(: apply-primitive (primitive (list-of value) -> value))
(define apply-primitive
(lambda (p args)
(cond
((equal? p +)
(+ (first args) (first (rest args))))
((equal? p -)
(- (first args) (first (rest args))))
((equal? p =)
(= (first args) (first (rest args))))
((equal? p *)
216 Kapitel 17
Schlielich bleibt noch der Code fr die Rckgabe eines Wertes von
einer Prozedur. Hier ist die Regel:
(w, e, e, (s0 , e0 , c0 )d) , (ws0 , e0 , c0 , d)
Hier ist der Code dazu:
Die SECD-Maschine 217
(define secd-step
(lambda (state)
...
(cond
...
((empty? code)
(let ((f (first dump)))
(make-secd
(make-pair (first stack)
(frame-stack f))
(frame-environment f)
(frame-code f)
(rest dump)))))
...))
(define eval-secd
(lambda (e)
(let ((val (first
(secd-stack
(secd-step*
(inject-secd e))))))
(if (base? val)
val
proc))))
I = ...
{tailap}
: L C
A
JK
b falls e =bB
v falls e =vV
def
JeK = Je0 K Je1 K ap falls e = ( e0 e1 )
Je1 K . . . Jek K primFk falls e = ( F e1 . . . e k )
(v, Je K0 )
falls e = v.e0
0
J K0 : LA C
b falls e =bB
v falls e =vV
def
JeK0 = Je0 K Je1 K tailap falls e = ( e0 e1 )
1 K . . . Jek K primFk falls e = ( F e1 . . . e k )
Je
(v, Je K0 )
falls e = v.e0
0
Da die erste Regel ein neues Dump-Frame erzeugt und die zweite ein
Dump-Frame vernichtet, entfllt diese Arbeit in der Regel fr tailap:
Damit luft das Beispiel zwar immer noch endlos, aber immerhin, ohne
immer mehr Platz zu verbrauchen:
, (e, , ( x, x x tailap) ( x, x x tailap) ap, e)
, (( x, x x tailap, ), , ( x, x x tailap) ap, e)
, (( x, x x tailap, ) ( x, x x tailap, ), , ap, e)
, (e, {( x, ( x, x x tailap, ))}, x x tailap, (e, , e))
, (( x, x x tailap, ), {( x, ( x, x x tailap, ))}, x tailap, (e, , e))
, (( x, x x tailap, ) ( x, x x tailap, ), {( x, ( x, x x tailap, ))}, tailap, (e, , e))
, (e, {( x, ( x, x x tailap, ))}, x x tailap, (e, , e))
, (( x, x x tailap, ), {( x, ( x, x x tailap, ))}, x tailap, (e, , e))
, (( x, x x tailap, ) ( x, x x tailap, ), {( x, ( x, x x tailap, ))}, tailap, (e, , e))
, (e, {( x, ( x, x x tailap, ))}, x x tailap, (e, , e))
, (( x, x x tailap, ), {( x, ( x, x x tailap, ))}, x tailap, (e, , e))
, (( x, x x tailap, ) ( x, x x tailap, ), {( x, ( x, x x tailap, ))}, tailap, (e, , e))
, (e, {( x, ( x, x x tailap, ))}, x x tailap, (e, , e))
, (( x, x x tailap, ), {( x, ( x, x x tailap, ))}, x tailap, (e, , e))
hLS i hV i
| (hLS i hLS i)
| (hV i.hLS i)
| h Bi
| (h1 i hLS i)
| (h2 i hLS i hLS i)
...
| (h n i hLS i ... hLS i) (n-mal)
| (set! hVi hLS i)
M = P ( A X)
X = B {v.e|v.e LS }
hLS i ...
| hAi
| (set! hAi hLS i)
Adressen tauchen dabei nur als Zwischenschritte bei der Reduktion
auf; sie sind nicht dafr gedacht, da sie der Programmierer in ein
Programm schreibt.
Da das bisherige Substitutionsprinzip bei Zuweisungen nicht mehr
funktioniert, reicht es nicht, die Reduktionsregeln fr den -Kalkl
mit Zustand einfach nur auf Termen auszudrcken: Ein Term, der ja
Adressen enthalten kann, ergibt nur Sinn, wenn er mit einem Speicher
kombiniert wird. Die Reduktionsregeln berfhren somit immer ein
Paar, bestehend aus einem Term und einem Speicher in ein ebensol-
ches Paar. Hierbei wird der Einfachheit halber kein Unterschied mehr
zwischen den verschiedenen Arten der Reduktion gemacht:
b, m a, m[ a 7 b] wobei a frisch
v.e, m a, m[ a 7 v.e] wobei a frisch
( a0 a1 ), m e[v 7 a], m[ a 7 m( a1 )] wobei m( a0 ) = v.e und a frisch
(set! a0 a1 ), m void, m[ a0 7 m( a1 )]
k
( F a1 . . . ak ), m a, m[ a 7 FB (b1 , . . . , bk )] wobei bi = m( ai ) B, a frisch
Die Formulierung a frisch bedeutet dabei, da a eine Adresse sein
sollte, die in m bisher noch nicht benutzt wurde. Die Operation m[ a 7
x ] ist hnlich wie bei Umgebungen definiert: der alte Speicherinhalt bei
a wird zunchst entfernt, und dann eine neue Zuordnung fr a nach x
hinzugefgt:
def
m[ a 7 x ] = (e \ {( a, x 0 )|( a, x 0 ) m) {( a, x )}
Die SECD-Maschine ist nicht mchtig genug, um den -Kalkl mit Zu-
stand zu modellieren: Es fehlt ein Speicher. Darum mu das Maschinen-
Pendant zum -Kalkl mit Zustand um eine Speicher-Komponente
erweitert werden: Heraus kommt die SECDH-Maschine, um die es in
diesem Abschnitt geht.
Der Maschinencode fr die SECDH-Maschine ist dabei genau wie
bei der SECD-Maschine, nur da eine spezielle Zuweisungsoperation
hinzukommt:
hIi ...
| :=
Der Begriff der Adresse aus der Menge A wird direkt aus dem Kalkl
bernommen. hnlich wie im Kalkl landen Zwischenergebnisse nicht
mehr direkt auf dem Stack, sondern stattdessen landen ihre Adressen
im Speicher. Dementsprechend bilden nun Umgebungen Variablen auf
Adressen ab. Die neue Komponente H ist gerade der Speicher, auch
genannt Heap, der die Adressen auf Werte abbildet:
S = A
E = P (V A )
D = (S E C )
H = P (A W)
W = B (V C E )
Der Heap aus H gehrt nun zum Zustand dazu. Anders als die
Umgebung wird er nicht bei der Bildung von Closures eingepackt:
Stattdessen wird der Heap stets linear von links nach rechts durch
Regeln durchgefdelt.
Zwischenergebnisse nehmen stets den Umweg ber den Heap: Immer,
wenn ein neues Zwischenergebnis entsteht, wird es bei einer neuen
Adresse im Heap abgelegt. Auf dem Stack landen die Adressen der
Zwischenergebnisse.
Die SECD-Maschine 223
, P ((S E C D H ) (S E C D H ))
(s, e, bc, d, h) , ( as, e, c, d, h[ a 7 b])
wobei a frisch
(s, e, vc, d, h) , (e(v)s, e, c, d, h)
( ak . . . a1 s, e, primFk c, d, h) , ( as, e, c, d, h[ a 7 b])
wobei a frisch, bi = h( ai ) und F k k und FBk (b1 , . . . , bk ) = b
( a1 a0 s, e, :=c, d, h) , ( as, e, c, d, h[ a0 7 h( a1 )][ a 7 void])
wobei a frisch
(s, e, (v, c )c, d, h) , ( as, e, c, d, h[ a 7 (v, c0 , e)])
0
wobei a frisch
( a1 a0 s, e, apc, d, h) , (e, e0 [v 7 a], c0 , (s, e, c)d, h[ a 7 h( a1 )])
wobei a frisch und h( a0 ) = (v, c0 , e0 )
( a, e, e, (s0 , e0 , c0 )d, h) , ( as0 , e0 , c0 , d, h)
evalSECD L Z
(S
h( a) falls (e, , JeK, e, ) , ( a, e, e, e, h), h( a) B
evalSECD (e) =
proc falls (e, , JeK, e, ) , ( a, e, e, e, h ), h ( a ) = ( v, c, e0 )
Mit Hilfe dieser Definition kann die Signaturdefinition von term erwei-
tert werden:
(define term
(signature
(mixed symbol
224 Kapitel 17
application
abstraction
base
primitive-application
assignment)))
Die Ellipse steht fr die nchste frische Adresse: Wenn die bisherige
frische Adresse in heap-store belegt wird, so mu eine neue frische
Adresse gewhlt werden:
226 Kapitel 17
(define heap-store
(lambda (h a w)
(make-heap (make-pair (make-cell a w)
(remove-cell a (heap-cells h)))
(let ((next (heap-next h)))
(if (= a next)
(+ next 1)
next)))))
Als nchstes ist die Operation an der Reihe, die den Wert, der an einer
Adresse im Heap gespeichert ist. Die Prozedur heap-lookup benutzt
eine Hilfsprozedur cells-lookup, um in der Liste von Zellen nach der
richtigen zu suchen:
; den Wert an einer Adresse im Heap nachschauen
(: heap-lookup (heap address -> value))
(define heap-lookup
(lambda (h a)
(cells-lookup (heap-cells h) a)))
Auch hier wird nur ein void-Wert bentigt, der vorfabriziert wird:
Die SECD-Maschine 227
Der Zustand fr die SECDH-Maschine wird genau wie bei der SECD-
Maschine reprsentiert, ergnzt um die Komponente fr den Heap:
dump
(heap-store heap a
(apply-primitive
(prim-operator (first code))
(map (lambda (address)
(heap-lookup heap address))
(take-reverse (prim-arity (first code)) stack)))))))
((:=? (first code))
(let ((a (heap-next heap)))
(make-secdh
(make-pair a (rest (rest stack)))
environment
(rest code)
dump
(heap-store
(heap-store heap
(first (rest stack))
(heap-lookup heap (first stack)))
a the-void))))
((abs? (first code))
(let ((a (heap-next heap)))
(make-secdh
(make-pair a stack)
environment
(rest code)
dump
(heap-store heap a
(make-closure (abs-variable (first code))
(abs-code (first code))
environment)))))
((ap? (first code))
(let ((closure (heap-lookup heap (first (rest stack))))
(a (heap-next heap)))
(make-secdh empty
(extend-environment
(closure-environment closure)
(closure-variable closure)
a)
(closure-code closure)
(make-pair
(make-frame (rest (rest stack)) environment (rest code))
dump)
(heap-store heap a (heap-lookup heap (first stack))))))
((tailap? (first code))
(let ((closure (heap-lookup heap (first (rest stack))))
(a (heap-next heap)))
(make-secdh (rest (rest stack))
(extend-environment
(closure-environment closure)
(closure-variable closure)
a)
(closure-code closure)
Die SECD-Maschine 229
dump
(heap-store heap a
(heap-lookup heap (first stack))))))))
((empty? code)
(let ((f (first dump)))
(make-secdh
(make-pair (first stack)
(frame-stack f))
(frame-environment f)
(frame-code f)
(rest dump)
heap)))))))
bungsaufgaben
1. (xy.(+ x y)) ( 5 6) 23
230 Kapitel 17
Dabei steht ! fr das boolesche not und && fr das boolesche and.
(define lookup-environment
(lambda (e v)
(e v)))
Aufgabe 17.13 Auf den ersten Blick erscheint es etwas aufwendig, je-
desmal bei der Auswertung einer Abstraktion die gesamte Umgebung
in die Closure einzupacken. Was wrde sich ndern, wenn dieser Schritt
weggelassen wrde, Closures also nur Variable und Maschinencode
fr den Rumpf enthalten wrden? Formulieren Sie die entsprechenden
Regeln fr die SECD-Maschine und ndern Sie die Implementierung
entsprechend. Funktioniert die SECD-Maschine nach der nderung
noch korrekt?
A Mathematische Grundlagen
1.1 Aussagenlogik
Eine Aussage ist ein Satz, der prinzipiell einen Wahrheitswert W (fr
wahr) oder F (fr falsch) besitzt.
Aus primitiven (elementaren) Aussagen werden mit Hilfe sogenannter
aussagenlogischer Junktoren zusammengesetzte Aussagen aufgebaut.
Es gibt zwei vordefinierte primitive Aussagen > und mit den Wahr-
heitswerten W bzw. F. Die wichtigsten Junktoren sind:
und (): a b hat den Wahrheitswert W genau dann, wenn a und b
beide den Wert W haben.
oder (): a b hat den Wahrheitswert W genau dann, wenn von a
und b mindestens eins den Wert W hat.
nicht (): a hat den Wahrheitswert W genau dann, wenn a den Wert
F hat.
In der Aussagenlogik gilt demnach das Prinzip, da der Wahrheits-
wert einer zusammengesetzten Aussage durch die Wahrheitswerte sei-
ner Bestandteile bestimmt ist.
Statt a wird gelegentlich auch a geschrieben.
Meistens werden logische Junktoren durch sogenannte Wahrheitstafeln
definiert:
W F W F
W W F W W W W F
F F F F W F F W
Andere Junktoren, die ebenfalls hufig verwendet werden, sind:
W F
impliziert (): W W F
F W W
a b spricht sich als wenn a, dann b oder aus a folgt b. F
W besitzt ebenso wie F F den Wahrheitswert W! In der formalen
Aussagenlogik folgt aus einer falschen Voraussetzung jede Folgerung.
W F
genau-dann-wenn (): W W F
F F W
234 Anhang A
1.2 Mengen
Die leere Menge ist die Menge, die keine Elemente besitzt und wird
durch bezeichnet.
A heit Teilmenge von B, in Zeichen A B, wenn jedes Element von
A auch Element von B ist:
def
A B a A a B.
Zwei Mengen sind gleich, wenn sie die gleichen Elemente besitzen; dies
lt sich mit Hilfe der Teilmengenbeziehung auch so ausdrcken:
def
A = B A B und B A.
{11, 13, 17, 19} = {11, 13, 11, 17, 17, 11, 13, 19},
d.h. es spielt keine Rolle, wie oft ein bestimmtes Element erwhnt wird;
es ist trotzdem nur einmal in der Menge enthalten.
Die Notation A 6 B bedeutet, da A B nicht gilt, A 6= B, da
A = B nicht gilt. A heit echte Teilmenge von B, wenn A B, aber
A 6= B. Die Notation dafr ist A B. Es bedeutet B A, da A B
gilt, ebenso fr B A.
Die Vereinigung A B zweier Mengen A und B ist definiert durch
def
AB = { a | a A a B }.
def
AB = { a | a A a B }.
def
A\B = { a | a A a 6 B }.
def
A1 A n = {( a1 , . . . , an ) | ai Ai }.
236 Anhang A
def
P ( A) = { T | T A}
AB = AB
T : A {0, 1}
def 1 falls x T
T (x) =
0 falls x 6 T
def
T f = { x A | f ( x ) = 1}.
1.3 Prdikatenlogik
Viele Aussagen haben die Form es gibt (mindestens) ein Objekt (In-
dividuum) mit der Eigenschaft. . . oder fr alle Objekte aus einem
bestimmten Bereich gilt. . . . Solche Aussagen heien Prdikate und
fr ihre mathematische Behandlung werden sogenannte Quantoren
eingefhrt, und zwar der Allquantor (Universalquantor) und der Exi-
stenzquantor . Im folgenden werden Grobuchstaben zur Bezeichnung
von Prdikaten und Kleinbuchstaben fr Individuen verwendet. Die
Stelligkeit eines Prdikats ist die Anzahl der Individuen, ber die hier
eine Aussage gemacht wird.
Ist Q ein nstelliges Prdikat und sind x1 , . . . , xn Individuen eines
Individuenbereichs, so ist die Behauptung, da Q auf x1 , . . . , xn zutrifft
(abgekrzt Qx1 . . . xn ) eine prdikatenlogische Aussage. Mathematische
Ausdrcke wie x M oder n < m oder aussagenlogische Aussagen sind
ebenfalls prdikatenlogische Aussagen, nur in anderer Schreibweise.
Statt der Individuen selbst kommen in den Quantorenausdrcken
Individuenvariablen vor; diese sind Platzhalter fr die Individuen selbst.
Die prdikatenlogische Aussage x : Qx bedeutet: Fr alle Indivi-
duen a gilt die Aussage (das Prdikat) Q, wobei fr die Variable x
das Individuum a eingesetzt wird. Dementsprechend heit x : Qx:
Es gibt mindestens ein Individuum a, so da die Aussage Qa wahr
ist. Die Variable x heit in beiden Fllen eine gebundene Variable des
Prdikatsausdrucks. Variablen, die nicht gebunden sind, heien freie
Variablen.
Eine wichtige Eigenschaft der Quantoren beschreibt der folgende
Satz:
x : ( x M y N : Pxy)
x : ( x M y : (y N Pxy)) .
1.4 Multimengen
def
PQ = {( x, m) | x P x Q, m = max(M( P, x ), M( Q, x ))}
def
PQ = {( x, m) | ( x, p) P, ( x, q) Q, m = min( p, q), m > 0}
def
P\Q = {( x, m) | ( x, p) P, m = p M( Q, x ), m > 0}
def
reflexiv-transitiver Abschlu von 0 ist die kleinste reflexive und
transitive Relation mit 0 .
Dabei heit kleinste Relation jeweils, da fr jede andere Relation 00 ,
welche die jeweilige Eigenschaft erfllt, gilt 0 00 .
+
Die transitive Abschlu von wird geschrieben, der reflexiv-
transitive Abschlu .
def
Definition 1.11 Fr eine Menge A ist die Identittsabbildung durch id A =
def
( A, id A , A) mit id A = {( a, a) | a A} definiert.
f
Definition 1.12 Eine Abbildung (auch: Funktion) A B heit
def
surjektiv fr alle b B gibt es ein a A, so da f ( a) = b,
def
injektiv aus f ( a1 ) = f ( a2 ) folgt a1 = a2 fr beliebige a1 , a2 A,
def f
bijektiv A B ist injektiv und surjektiv.
f
Ist A B bijektiv, so heien A und B isomorph, in Zeichen A
= B.
f g
Definition 1.13 Fr zwei Abbildungen A B und B C definiere
durch
def
g f = ( A, g f , C )
die Komposition von g und f mit
def
g f = {( a, c) | b B : ( a, b) f (b, c) g }.
Lemma 1.14 Die Komposition von Abbildungen ist assoziativ, das heit
f g h
fr A B, B C und C D gilt
(h g) f = h ( g f ) .
1.6 Ordnungen
Definition 1.18 Eine totale Ordnung auf einer Menge M ist eine partielle
Ordnung , bei der zustzlich gilt
x, y M : xy yx .
i N : a i 1 a i +1 .
Aufgaben
f g
Aufgabe 1.1 A B C sei injektiv (surjektiv). Welche Aussagen ber
f g
A B bzw. B C gelten dann mit Bestimmtheit?
f 1
Aufgabe 1.2 Zeige, da die Umkehrfunktion B A einer bijektiven
f
Funktion A B stets injektiv ist.
|P ( A)| = 2| A|
( A B) = A B
( A B) = A B
A ( B C ) = ( A B) ( A C )
Die Kontraposition:
( A B) ( B A)
( A ( B C )) (( A B) ( A C ))
Gib eine partielle Ordnung an, fr welche die Aussage nicht gilt!