Was ist der unterschied zwischen dem prozeduraufruf und der prozeduranwendung

Inhaltsverzeichnis 1 Abstraktion mit Prozeduren 1.1 Programmelemente . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Ausdr¨ ucke . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Abstraktion durch Benennung von Objekten . . . 1.1.3 Auswertung von Termen und Kombinationen . . . 1.1.4 Abstraktion durch Benennung von Prozeduren . . 1.1.5 Substitutionsmodell f¨ ur Prozeduranwendungen . . 1.1.6 Programmierstil und Pragmatik . . . . . . . . . . 1.1.7 Bedingte Ausdr¨ ucke, Fallunterscheidungen . . . . . 1.1.8 Zusammengesetzte Pr¨ adikate . . . . . . . . . . . . 1.1.9 Quadratwurzelberechnung nach Newton . . . . . . 1.1.10 Allgemeine Vorgehensweisen beim Programmieren 1.2 Prozeduren und Prozesse . . . . . . . . . . . . . . . . . . 1.2.1 Lineare Rekursion und Iteration . . . . . . . . . . 1.2.2 Baumrekursion . . . . . . . . . . . . . . . . . . . . 1.2.3 Gr¨ oßenordnungen . . . . . . . . . . . . . . . . . . . 1.2.4 Fermat’scher Primzahltest . . . . . . . . . . . . . . 1.2.5 Berechnung und Auswertung . . . . . . . . . . . . 2 Abstraktion mit Daten 2.1 Einf¨ uhrung . . . . . . . . . . . . . . . . . . . 2.1.1 Abstrakte Daten . . . . . . . . . . . . 2.1.2 Abstrakte Datentypen . . . . . . . . . 2.2 Hierarchische Datenstrukturen . . . . . . . . 2.2.1 Listen . . . . . . . . . . . . . . . . . . 2.2.2 Quotieren . . . . . . . . . . . . . . . . 2.2.3 Implementierung von Mengen . . . . . 2.2.4 Huffmann-B¨ aume . . . . . . . . . . . . 2.3 Abstraktion mit Prozeduren h¨ oherer Ordnung 2.3.1 Prozeduren h¨ oherer Ordnung . . . . . 2.3.2 Lokale Definitionen . . . . . . . . . . . 2.3.3 Lexikalische (statische) Bindung . . . 2.3.4 Prozeduren als Ergebnis . . . . . . . . 2.3.5 Komplexe Typdeklaration . . . . . . . 2.4 Systeme mit generischen Operatoren . . . . . 2.5 Exkurs . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

7 7 7 8 9 10 11 11 12 13 13 15 16 16 17 19 22 24

. . . . . . . . . . . . . . . .

29 29 29 31 33 33 35 39 42 45 45 47 47 50 55 58 59

Inhaltsverzeichnis 2.5.1

Beweistechniken f¨ ur Programme mit Datenstrukturen . . . . . . . 59

3 Modularit¨ at, Objekte, Zust¨ ande 3.1 Zuweisungen und lokale Zust¨ande . . . . . . . . . . . . . . . . . . . 3.1.1 Probleme der Zuweisungen . . . . . . . . . . . . . . . . . . 3.2 Das Umgebungsmodell . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Ver¨ anderbare Datenstrukturen . . . . . . . . . . . . . . . . . . . . 3.3.1 Structure Sharing und Identit¨at . . . . . . . . . . . . . . . . 3.3.2 Simulation digitaler Schaltkreise . . . . . . . . . . . . . . . 3.3.3 Modelle mit Beschr¨ankung . . . . . . . . . . . . . . . . . . 3.4 Zust¨ ande in mehrl¨ aufigen Systemen . . . . . . . . . . . . . . . . . . 3.5 Datenstr¨ ome (Streams) . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Datenflussorientierte Programmstruktur mit Datenstr¨omen 3.5.2 Implementierung von Datenstr¨omen . . . . . . . . . . . . . 3.5.3 Implementierung der verz¨ogerten Auswertung . . . . . . . . 3.5.4 Datenstr¨ ome unendlicher L¨ange . . . . . . . . . . . . . . . . 3.5.5 Datenstr¨ ome ⇔ Lokale Zust¨ande . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

63 63 65 67 69 70 74 81 87 89 90 93 95 96 98

4 Einf¨ uhrung in JAVA 4.1 Allgemeines . . . . . . . . . . 4.2 Ausdr¨ ucke und Anweisungen 4.2.1 Grundtypen in JAVA 4.3 Typisierung . . . . . . . . . . 4.3.1 Felder . . . . . . . . . 4.4 Klassen und Objekte . . . . . 4.5 Vererbung . . . . . . . . . . . 4.6 Schnittstellen und Pakete . . 4.7 Weitere Aspekte von JAVA .

. . . . . . . . .

103 103 104 104 105 106 107 110 111 111

5 Zusammenfassung

. . . . . . . . .

113

1 Abstraktion mit Prozeduren 1.1 Programmelemente 1.1.1 Ausdr¨ ucke Die Programmiersprache SCHEME erlaubt die Erstellung von Programmen mithilfe der funktionalen, sowie unter anderem der imperativen Programmierung. SCHEME ist insofern eine recht einfache Programmiersprache, als dass sie aus nur wenigen Schl¨ usselw¨ortern, beziehungsweise so genannten Sonderformen, besteht und recht einfach nach Belieben erweitert werden kann. Die zentralen Elemente von SCHEME sind Ausdr¨ ucke sowie Bedingungen. Der Rest, wie zum Beispiel Schleifen, wird auf andere Weise realisiert. Dazu jedoch sp¨ater mehr. Generell hat jedes Objekt unter SCHEME einen Wert. Bei Zahlen ist der Wert zum Beispiel die Zahl selbst, wie man anhand der folgenden Eingabe unter SCHEME sehen kann. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > 42 42 > Kombinationen hingegen sind Verkn¨ upfungen mit elementaren Prozeduren1 . Zu beachten ist die zun¨ achst etwas ungewohnt anmutende Pr¨afixnotation, die SCHEME im Gegensatz zur Infixnotation wie zum Beispiel in JAVA oder C verwendet. Dazu wird der Operator nach vorne gezogen und der jeweils ein Ausdruck wird in Klammern gesetzt. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (+ 10 31) 1 (* 5 42) 10 Die so genannte Pr¨ afixnotation in SCHEME bedeutet, dass zun¨achst der Operator und anschließend die dazu geh¨ orenden Operanden geschrieben werden2 . Einige Vorteile dieser Pr¨ afixnotation sind: 1 2

Wie zum Beispiel die arithmetischen Operatoren +,-,/,*. Das Gegenteil davon ist, wie bereits erw¨ ahnt, die Infixnotation, wo der Operator zwischen zwei Operanden geschrieben wird.

1 Abstraktion mit Prozeduren • Obwohl nur ein Operator verwendet wird, kann man unbegrenzt viele Operanden darauf anwenden: (+ 1 2 3 4) • Ausdr¨ ucke k¨ onnen nach Belieben verschachtelt werden: (+ (* 3 5)(- 10 6)) • Die Leseweise ist bedingt durch die Klammern eindeutig, sodass man sich um Regeln wie Punkt vor Strich keine Sorgen mehr machen muss. Damit auch l¨ angere und vor allem verschachteltere Ausdr¨ ucke in SCHEME noch lesbar bleiben, gibt es eine bestimmte Konvention, wie die Operanden vertikal untereinander geschrieben werden sollten. Einfache Ausdr¨ ucke(z.B. (+ 1 2)) werden hintereinander geschrieben, aber komplexere, zusammengesetzte Ausdr¨ ucke werden so untereinander. geschrieben, das klar ist, welche Operanden zu welchem Operator geh¨oren. 1 2 3 4 5

(+ ( ∗ 3 (+ ( ∗ 2 4 ) (+ 3 5 ) ) ) (+ (− 10 7 ) 6)) F¨ ur den Computer sind die Leerzeichen v¨ollig unwichtig, doch f¨ ur jemanden, der die Prozedur, beziehungsweise die Ausdr¨ ucke sp¨ater noch lesen und unter Umst¨anden warten soll, ist eine u ¨bersichtliche Schreibweise sehr wichtig. Wichtig ist letztendlich jedoch nur, dass man sich einen guten Schreibstil aussucht und diesen auch beibeh¨alt.

1.1.2 Abstraktion durch Benennung von Objekten Ein Name (Identifikator) benennt eine Variable, deren Wert ein Objekt ist. Der Operator zur Namensgebung nennt sich define. Der erste Operand ist der zuk¨ unftige Name der Variable, w¨ ahrend der zweite Operand der Wert ist, welcher der Variable zugeordnet wird. Auch dieser Name dient nur der Abstraktion, also dem Verst¨andnis f¨ ur den Programmierer. F¨ ur den Computer spielt der Name keine Rolle. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (define groesse 2) > groesse 2 > (* groesse 10) 20 > (define qu-groesse (* groesse groesse)) > qu-groesse 4 > Der Operator define stellt unter SCHEME das einfachste Abstraktionsmittel dar, indem komplexe Ausdr¨ ucke zu einem Namen abstrahiert werden. Da die Variable groesse nun

1.1 Programmelemente in der aktuellen Umgebung bekannt ist, bedeutet das, dass der Operator define in der Lage ist, die Umgebung zu ver¨ andern. Es gibt im SCHEME-System einen so genannten Namensspeicher, in dem die Zuordnung von einem Namen zu einem Objekt verankert ist. Dies ist define entsprechend in der Lage zu a¨ndern.

1.1.3 Auswertung von Termen und Kombinationen • Werte alle Teile aus (die Reihenfolge ist hier egal) • Wende den Wert des linken Element auf die Werte der restlichen Elemente an. Es handelt sich zwar um einen rekursiven Aufruf, der jedoch wohl definiert und somit auch endlich ist, da die einzelnen Teile des Terms immer kleiner werden. Das linke Element ist in der Regel eine Prozedur, beziehungsweise ein Prozedurname, es kann jedoch auch eine komplexere Kombination sein, wie wir sp¨ater noch sehen werden. Der Wert von elementaren Prozeduren wird im Endeffekt in Maschinencode umgewandelt, damit dieser ausgef¨ uhrt werden kann. Nehmen wir dazu als Beispiel den folgenden Code. 1 2 3

( ∗ (+ 2 (∗ 4 6)) (+ 3 5 7 ) ) (∗ (+ 2 (∗ 4 6)) (+ 3 5 7)) | {z } | {z } 15 | {z24 } 26 | {z } 390

Die Auswertung geschieht von innen nach außen, jedoch w¨are eine Auswertung teilweise parallel m¨oglich. So h¨ atten die beiden Zweige (die beiden Operanden der ¨außersten Multiplikation) auf einem Zweikern-Prozessor gleichzeitig durchlaufen werden k¨onnen, was insgesamt nat¨ urlich ein schnelleres Ergebnis geliefert h¨atte. Wie bereits erw¨ ahnt gibt es in SCHEME eine Handvoll von Befehlen, welche anders als regul¨are Prozeduren funktionieren. Diese so genannten Sonderformen sind Befehle, die auf andere Weise ausgewertet werden. Einen davon haben wir bereits kennen gelernt: define. Die Art und Weise, wie dieser ausgewertet wird, ist Folgende: • Werte zun¨ achst das letzte Element aus • Ordne dann das zweite Element dem ersten Wert zu Diese und a¨hnliche Sonderformen sind fest in der Syntax SCHEME verankert und nicht wie andere Prozeduren in der Umgebung definiert. Wie bereits erw¨ahnt hat SCHEME nur wenige dieser Sonderformen und ist entsprechend einfacher als andere Programmiersprachen. Die Syntax, die man lernen muss, um Programme zu schreiben, hat einen relativ kleinen Sprachumfang.

1 Abstraktion mit Prozeduren

1.1.4 Abstraktion durch Benennung von Prozeduren W¨ unschenswert w¨ are es nun, nachdem wir wissen, dass es m¨oglich ist, Objekte zu abstrahieren, auch ein Verfahren zur Wertberechnung zu abstrahieren. So soll zum Beispiel die Fl¨ ache eines Quadrats berechnet werden. Man schaue sich die Berechnung der Fl¨ achen von Quadraten unterschiedlicher Kantenl¨ange an. • Kantenl¨ ange 2 ⇒ (* 2 2) • Kantenl¨ ange 3 ⇒ (* 3 3) • Kantenl¨ ange 4 ⇒ (* 4 4) Es handelt sich hierbei, wie man recht schnell erkennen kann, u ¨berall um das gleiche Schema. Ist x die Kantenl¨ ange, so berechnet sich die Fl¨ache zu (* x x). Zur allgemeinen Berechnung der Quadratfl¨ache wird dieses Schema zu einem Namen mit Parameter abstrahiert. 1

( d e f i n e ( quadrat x ) ( ∗ x x ) ) Wie man sehen kann, enth¨ alt die Prozedur formale Parameter. Das bedeutet, dass die Auswertung des Terms erst geschieht, wenn die aktuellen Parameter bekannt sind und das Problem so konkret wird. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (quadrat 21) 441 > (quadrat (quadrat 3)) 81 > Zusammengesetzte Prozeduren sind u ¨brigens nicht von elementaren Prozeduren unterscheidbar. Tats¨ achlich sind sie sogar Bausteine f¨ ur weitaus komplexere Prozeduren. Zum Beispiel:

1 2 3 4 5 6 7 8

( d e f i n e ( quadrat x ) (∗ x x ) ) ( d e f i n e ( quadratsumme x y ) (+ ( quadrat x ) ( quadrat y ) ) ) ( define ( f a) ( quadratsumme (+ a 1 ) (∗ a 2 ) ) )

1.1 Programmelemente

1.1.5 Substitutionsmodell f¨ ur Prozeduranwendungen Werte den Rumpf aus, nachdem jeder formale Parameter durch das entsprechende Argument ersetzt (substituiert) wurde. Dies wird nun am Beispiel der Auswertung von (f 5) gezeigt: (f 5) ⇒ (quadratsumme (+ 5 1) (* 5 2)) ⇒ (quadratsumme 6 (* 5 2)) ⇒ (quadratsumme 6 10) ⇒ (+ (quadrat 6) (quadrat 10)) ⇒ (+ (* 6 6) (* 10 10)) ⇒ (+ 36 100) ⇒ 136 Es handelt sich bei dem Substitutionsmodell u ¨brigens lediglich um ein rein theoretisches Modell; in der Praxis gibt es keine textuelle Ersetzungen, sondern es gibt einen Zugriff u utzlich, ¨ber die lokale Umgebung. Das Substitutionsmodell scheint zun¨achst n¨ versagt jedoch sp¨ ater, wenn es dann um ver¨anderbare Datenstrukturen geht. Die Auswertung ist Ziel einer jeden Berechnung. Das bedeutet, dass die Ausdr¨ ucke soweit ausgewertet werden, dass sie ausgerechnet werden k¨onnen. Zusammengefasst kann man zur Auswertung verschiedener Ausdr¨ ucke sagen: • Zahl: Das Ergebnis ist die Zahl selbst • Name: Schaue in der Umgebung die Definition nach. Das Ergebnis ist der zugeordnete Wert • Kombination: Elementare Prozeduren, oder nach Substitutionsmodell aufl¨osbar

1.1.6 Programmierstil und Pragmatik Falls die Abstraktionen komplexer werden, sollten der Zweck der Abstraktionen kommentiert werden. Kommentare beginnen in SCHEME mit dem Semikolon und reichen bis zum Zeilenende. Der Inhalt wird dabei vom System ignoriert. Vor jeder nicht trivialen Abstraktion sollte ein Kommentar beschreiben, was3 die Abstraktion definiert. 3

nicht wie!

1 Abstraktion mit Prozeduren ¨ Ein sogenannter Vertrag ist im Ubrigen eine Beschreibung, was eine Prozedur leisten soll. 1 2 3 4

; Bestimme aus Anzahl von PKW und Mopeds d i e Anzahl d e r R¨ a der ( d e f i n e ( raeder−von pkws mopeds ) (+ ( ∗ pkws 4 ) ( ∗ mopeds 2 ) ) ) Grunds¨ atzlich sollte jede Abstraktion getestet werden. Unabh¨angig davon, wie trivial sie ist. Da die meisten Abstraktionen auf unendlich viele Parameter zutreffen, kann man durch Testen lediglich das Vorhandensein von Fehlern nachweisen, jedoch nicht, dass die Abstraktion f¨ ur alle4 Parameter richtig rechnet. Das bedeutet, dass man sich vor Realisierung der Abstraktion anhand des Vertrages/Kommentares die Testf¨ alle u ¨berlegen sollte, mit der die Implementierung zu testen ist. Im speziellen sollte man sowohl gew¨ohnliche als auch extremale F¨alle austesten. • (raeder-von 0 0): Wert 0 • (raeder-von 2 0): Wert 8 • (raeder-von 0 3): Wert 6 • (raeder-von 4 2): Wert 22 Hier kann man sehen, dass zun¨achst der extremale Fall ausgetestet wird, wenn sowohl pkws als auch mopeds Null ist. Dann wird jeweils einer von beiden Parametern gleich Null gesetzt, anschließend wird ein trivialer Fall getestet.

1.1.7 Bedingte Ausdr¨ ucke, Fallunterscheidungen Mit den bisherigen Anweisungen lassen sich zwar schon einfache Programme schreiben, aber irgendwann m¨ ochte man in der Lage sein, auch Fallunterscheidungen zu treffen und das Programm f¨ ur verschiedene M¨oglichkeiten unterschiedliche Berechnungen anstellen zu lassen. Als Beispiel sei hier der Absolutbetrag einer Zahl genannt.   f alls x > 0 x abs(x) = 0 f alls x = 0   −x f alls x < 0 Um dieses Beispiel also unter SCHEME Prozedur verwirklichen zu k¨onnen, ben¨ otigt man die M¨ oglichkeit einer Fallunterscheidung. Die Sonderform cond l¨asst sich daf¨ ur benutzen. ( cond ( ) ( ) ... ( ))

1 2 3 4 4

Unter Umst¨ anden auch unendlich viele

1.1 Programmelemente Die ersten Operanden (p1 . . . pn ) sind jeweils Bedingungen, die zweiten Operanden (a1 . . . an ) sind die dazugeh¨ origen Ausdr¨ ucke. cond wird abgearbeitet, indem zun¨achst p1 ausgewertet wird. Ist dieser Wert wahr, so wird die Bedingung a1 abgearbeitet. Ist der Wert falsch, so wird p2 ausgewertet usw. Falls keiner der Werte wahr ist, gibt es eine Fehlermeldung. Man sieht also, dass pro Durchlauf nur ein Fall abgearbeitet wird, anders als in JAVA oder C, wo mehrere Bedingungen zutreffen k¨onnen. 1 2 3

( d e f i n e ( abs x ) ( cond ((> x 0 ) x ) ((= x 0 ) 0 ) ((< x 0 (− x ) ) ) ) Diese Prozedur kann man jedoch noch vereinfachen, indem wir den Spezialfall pn = else einf¨ uhren. Ist keiner der vorherigen Werte wahr, so wird der else-Zweig ausgef¨ uhrt. Damit wird eine Fehlermeldung wie vorhin genannt, umgangen.

1 2

( d e f i n e ( abs x ) ( cond ((> x 0 ) x ) ( e l s e (− x ) ) ) ) Eine weitere Sonderform ist die Art von cond, welche lediglich aus einem Pr¨adikat (einer Bedingung) und einem else-Zweig besteht. Da diese sehr h¨aufig ist, wird daf¨ ur if verwendet.

( i f ) Damit l¨asst sich nun unser obiges Beispiel noch ein weiteres Mal vereinfachen.

1 2 3

( d e f i n e ( abs x ) ( i f (> x 0 ) x (− x ) ) )

1.1.8 Zusammengesetzte Pr¨ adikate Um verschachtelte Bedingungen (Pr¨ adikate) zu erzeugen, gibt es unter anderem die drei Wahrheitsoperatoren and, or und not. And ergibt wahr, falls alle Operanden den Wert wahr haben haben. Oder ergibt nur dann falsch, wenn alle Operanden den Wert falsch haben. Not ergibt wahr, falls der Operand den Wert falsch hat und umgekehrt.

1 2 3

( d e f i n e (>= x y ) ( or (> x y ) (= x y ) ) )

1.1.9 Quadratwurzelberechnung nach Newton √ Die mathematische Wurzelfunktion sagt aus, dass x = y, sodass y >= 0 und y 2 = x. Dies ist pr¨azise, aber nicht effektiv. Dies ist ein definitiver Unterschied zwischen der

1 Abstraktion mit Prozeduren Mathematik und der Informatik. Die Wurzelfunktion ist zwar ¨außerst korrekt, sagt jedoch nicht aus, wie genau die Wurzel von x nun gefunden wird. Zu diesem Zweck gibt es das Newton’sche Bestimmungsverfahren. Dieses sagt aus, dass es bei einer gegebenen Sch¨ atzung y eine bessere Sch¨atzung gibt, n¨amlich der Mittelwert von y und xy .

Sch¨atzung 1 1.5 1,4167...

Mittelwert 1.5 1.4167... 1.4142... √ Tabelle 1.1: Bestimmung von 2 nach Newton ( define ( wurzel−iter y x) ( i f ( gut−genug ? y x ) y ( wurzel−iter ( verbessern y x) x )))

1 2 3 4 5

( define ( verbessern y x) ( mittelwert y (/ x y ) ) )

6 7 8

( define ( mittelwert y x) ( / (+ x y ) 2 ) )

9 10 11

( d e f i n e ( gut−genug ? y x ) (< ( abs (− ( quadrat y ) x ) ) 0 . 0 0 1 ) )

12 13 14

( d e f i n e ( wurzel x ) ( wurzel−iter 1 x ))

Wie man sehen kann, wurde das Abbruchkriterium hier stark vereinfacht. So funktioniert die Prozedur zum Beispiel nicht f¨ ur sehr kleine Zahlen, da das Abbruchkriterium anscheinend sofort erreicht wird. Nun noch eine Beispielausgabe des Programms. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (wurzel 9) 3.0000915541313801785305561... > Anhand des Programms kann man also Folgendes sehen: • Die numerische Anwendung ist m¨oglich • Es sind nur Prozeduren und Fallunterscheidungen notwendig

1.1 Programmelemente • Es sind keine iterativen Konstrukte (wie z.B. Schleifen) notwendig • Die Schleife entspricht in SCHEME einem rekursiven Aufruf

1.1.10 Allgemeine Vorgehensweisen beim Programmieren • Problem in Teilprobleme zerlegen5 • Teilproblem ≈ Prozedur • Bei Prozeduren ist nur wichtig, dass sie bestimmte Aufgaben erf¨ ullen • Bei Prozeduren ist nicht wichtig, wie sie bestimmte Aufgaben erf¨ ullen ⇒ prozedurale Abstraktionen Prozedurale Abstraktionen sind im Grunde so etwas wie eine ”Black Box”. F¨ ur denjenigen, der sie benutzt, ist nicht wichtig, was genau darin ist. Sie wird lediglich im Notfall ge¨offnet. Und so verh¨ alt es sich auch beim Programmieren im Team. Wird zum Beispiel eine Prozedur angefordert, so interessiert denjenigen, der sie sp¨ater benutzt, nur, was diese Prozedur macht, nicht wie sie etwas macht.

Abbildung 1.1: top-down-Entwurf Dies nennt man einen top-down-Entwurf, da bei der Entwicklung von oben nach unten gegangen wurde. Das Gegenteil ist der so genannte bottom-up-Entwurf, bei der zun¨achst grundlegende Prozeduren entwickelt werden, auf denen dann die komplexeren Dinge aufbauen. In der Praxis wird meistens eher eine Mischung aus beiden Entwurfsarten angewandt. 5

In logische Einheiten; nicht in Teilprobleme ≈ max. 10 Zeilen o.¨ a.

1 Abstraktion mit Prozeduren • Prozedurnamen spielen insofern eine wichtige Rolle beim Programmieren, als dass sie dem Benutzer der Prozeduren eine m¨oglichst gute Abstraktion erm¨oglichen sollen. F¨ ur den Computer macht ein anderer Prozedurname kein Unterschied, f¨ ur den Benutzer schon. • Namen von Parametern sind nur lokal relevant. Dies ist auch wichtig, damit Prozeduren unabh¨ angig voneinander entwickelt werden k¨onnen. Meistens einigt man sich lediglich auf die Prozedurnamen. Die Namen der Parameter sind jedem Entwickler freigestellt. • Formale Parameter sind durch Prozedurdefinitionen gebundene Variablen • Das Gegenteil davon sind freie Variablen.

1.2 Prozeduren und Prozesse 1.2.1 Lineare Rekursion und Iteration Fakult¨ at n! = n · (n − 1) · (n − 2) · · · · · 2 · 1 1 2 3 4 5

( define ( fak n) ( i f (= n 1 ) 1 (∗ n ( f a k (− n 1 ) ) ) ) ) Der Berechnungsprozess f¨ ur die Fakult¨at von 3 w¨are nun nach dem Substitutionsmodell6 folgende: (fak 3) ⇒ (* 3 (fak 2)) ⇒ (* 3 (* 2 (fak 1))) ⇒ (* 3 (* 2 1)) ⇒ (* 3 2) ⇒ 6 Man kann sehen, dass der Speicherbedarf bei dieser Prozedur teilweise stark w¨achst. Daher w¨ ahlen wir nun eine andere M¨oglichkeit, diese Prozedur zu implementieren. Multipliziert man 1 mit 2, so ist das Ergebnis 2. Multipliziert man dieses mit 3, so ergibt sich 6. ⇒ Parameter f¨ ur jeden Schritt sind der Z¨ahler (1 bis n), das Produkt (1 bis n!) und n (Abbruch).

1 2

( define ( fak n) ( fak−iter 1 1 n))

3 6

Zur Vereinfachung ohne if-Auswertung

1.2 Prozeduren und Prozesse 4 5 6 7 8

( define ( fak−iter z p n) ( i f (> z n ) p ( f a k − i t e r (+ z 1 ) (∗ p z ) n ) ) ) Diese Implementierung erzeugt nach dem Substitutionsmodell folgenden Berechnungsprozess: (fak 3) ⇒ (fak-iter 1 1 1) ⇒ (fak-iter 2 1 3) ⇒ (fak-iter 3 2 3) ⇒ (fak-iter 4 6 3) ⇒ 6

Beobachtung: • Beide Prozesse haben die gleiche L¨ ange (linearer Prozess) • 1. Version ”verz¨ ogert”die Multiplikation vor dem rekursiven Aufruf (linearer rekursiver Prozess) • 2. Version multipliziert schrittweise mit p,z,n7 und stellt einen linearen iterativen Prozes dar. Der Platzbedarf des Speichers ist bei dieser Version konstant. Merke: Rekursive Prozedur 6= Rekursiver Prozess

1.2.2 Baumrekursion Im Folgenden wird die Baumrekursion anhand der Fibonacci-Zahlen erkl¨art. Die FibonacciZahlen sind eine Folge von Zahlen, mit dem Bildungsgesetz: Jede Zahl in der Folge in die Summe der beiden vorhergehenden Zahlen. Dabei sind die ersten beiden FibonacciZahlen mit 0 und 1 festgelegt8 . Damit ergibt sich f¨ ur die ersten Fibonacci-Zahlen: 0,1,1,2,3,5,8,13,21,34,55,89 usw.   0 f alls n = 0  Fib(n) = 1 f alls n = 1   F ib(n − 1) + F ib(n − 2) f alls n > 1 7 8

Zustandsvariablen Gelegentlich auch mit 1 und 1

1 Abstraktion mit Prozeduren

1 2 3 4 5

( define ( fib n) ( cond ((= n 0 ) 0 ) ((= n 1 ) 1 ) ( e l s e (+ ( f i b (− n 1 ) ) ( f i b (− n 2 ) ) ) ) ) ) Stellt man nun den Aufruf von (fib 4) als Substitutionsmodell da, ergibt sich folgender Berechnungsprozess:

Abbildung 1.2: Baumrekursiver Berechnungsprozess Das gewaltige Problem, welches sich bei dem Berechnungsprozess ergibt, ist, dass Redundanzen auftreten. So wird (fib 2) etwa zweimal aufgerufen, (fib 1) sogar ganze dreimal. Die Berechnung einer Fibonacci-Zahl wird hier immer auf die ersten beiden Fibonacci-Zahlen herunter gebrochen. Das Programm besitzt eine hohe Laufzeit, genau genommen sogar eine exponentielle Laufzeit, hda eine Formel zur schnellen Berechnung i n φ von Fibonacci-Zahlen aussagt, dass f ib(n) = √5 . Um diesen Verfahren nun zu beschleunigen, werden die Fibonacci-Zahlen im Folgenden durch einen iterativen Prozess durch aufsummieren berechnet. Als Parameter bekommt das Programm die letzten beiden Fibonacci-Zahlen sowie einen Z¨ahler, der u uft, ¨berpr¨ ab wann das Aufsummieren stoppen muss. Seien a und b die beiden letzten FibonacciZahlen, wobei b die vorletzte ist, dann gilt bei jedem Schritt, dass a = a + b und b = a wird, wobei diese beiden Schritte gleichzeitig ausgef¨ uhrt werden m¨ ussen.

1 2

( define ( fib n) ( fib−iter 1 0 n))

3 4 5 6 7

( define ( fib−iter a b z) ( i f (= z 0 ) b ( f i b − i t e r (+ a b )

1.2 Prozeduren und Prozesse a (− z 1 ) ) ) )

8 9

Aus dem rechenaufwendigen baumrekursiven Verfahren wurde nunmehr ein linear iterativer Prozess gemacht mit einer linearen Laufzeit und einem konstanten Speicherverbrauch.

Baumrekursion: • Erlaubt eine zumeist nat¨ urliche Formulieren • Ist h¨aufig geeignet (z.B. f¨ ur hierarchische Datenstrukturen) • H¨aufige Gefahr von Ineffizienz. Iteration: • Effizient ¨ • Ben¨otigt etwas mehr Uberlegungen zu den Zustandsvariablen

1.2.3 Gr¨ oßenordnungen • Wichtig zum Vergleich des Ressourcen-Verbrauchs • Gemessen in Abh¨ angigkeit eines Parameters n

• R(n) ist der Betrag an Ressourcen des Prozesses, der ein Problem der Gr¨oße n berechnet 10 • Ist exakt nur schwer zu messen

• R(n) hat Gr¨ oßenordnung O(f (n)) falls es Konstanten c und n0 12 gibt mit R(n) ≤ c · f (n) f¨ ur alle n ≥ n0 . Somit ist O(n) = O(2u) = O( h2 )

Prozess Linear rekursiver Fakult¨ atsprozess Iterative Variante des Fakult¨atsprozesses Baumrekursion bei Fibonacci

Laufzeit O(n) O(n) O(φn )

Speicher O(n) O(1) O(n)

z.B. n bei den Fibonacci-Zahlen; Genauigkeit bei der Wurzelberechnung; Gr¨ oße der Matrix etc. z.B. Laufzeit, Speicherzellen, Prozeduraufrufe etc. 11 Da die Faktoren meist stark von der Implementierung abh¨ angen 12 unabh¨ angig von n 10

1 Abstraktion mit Prozeduren Man kann also sehen, dass es sich bei Speicherverbrauch und Laufzeit um ein grobes Maß der Effizienz verschiedener Algorithmen handelt. Prozesse mit exponentieller Laufzeit (O(cn )) sind praktisch unbrauchbar und sollten so h¨aufig wie m¨oglich vermieden werden - auch wenn es durchaus Probleme gibt, bei denen es keine andere L¨osung als einen solchen Algorithmus gibt. Ein weiteres Problem, anhand dessen nun die Optimierung des Algorithmus klar gemacht wird, ist die Potenzrechnung. Nehmen wir eine Prozedur, die als Eingabe zwei Zahlen b und n, erh¨ alt und als R¨ uckgabewert bn hat. Einfachkeitshalber wird davon ausgegangen, dass es sich bei b um eine nat¨ urliche und bei n um eine ganze Zahl handelt. Die rekursive L¨ osung zu diesem Problem w¨are relativ einfach: bn = |b · b · b{z· · · · · }b = n−mal

b · bn−1 und b0 = 1. Damit w¨ urde sich folgende Prozedur ergeben: ( d e f i n e ( potenz b n) ( i f (= n 0 ) 1 (∗ b ( p o t e n z b (− n 1 ) ) ) ) )

1 2 3 4 5

Dies ist ein linear rekursiver Prozess. Speicher und Laufzeit sind linear. Eine bessere Variante w¨ are die Implementierung einer iterativen Berechnung: ( d e f i n e ( potenz b n) ( pot−iter n b 1))

1 2 3

( define ( pot−iter b z p) ( i f (= z 0 ) p ( p o t − i t e r b (− z 1 ) ( ∗ b p ) ) ) )

4 5 6 7

Bei der iterativen Variante ist die Laufzeit zwar weiterhin linear, der Speicherverbrauch ist jedoch nun konstant. Es gibt jedoch die M¨oglichkeit, die Berechnung schon schneller zu machen. Statt zum Beispiel b8 = b · b · b · b · b · b · b · b wird b2 = b · b, b4 = b2 · b2 , b8 = b4 · b4 berechnet. Allgemein kann man damit sagen:   b n2 2 f alls n gerade n b = b · bn−1 f alls n ungerade ( define ( schnell−pot b n) ( cond ((= n 0 ) 1 ) (( gerade ? n) ( quadrat ( s c h n e l l − p o t b ( / n 2 ) ) ) ) ( e l s e ( ∗ b ( s c h n e l l − p o t b (− n 1 ) ) ) ) ) )

1 2 3 4 5 6

( d e f i n e ( gerade ? n)

1.2 Prozeduren und Prozesse 8

(= ( r e m a i n d e r n 2 ) 0 ) ) Die von SCHEME bereitgestellte Prozedur remainder entspricht dem Rest des Dividierens, also Modulo. ¨ Interessant ist nun eine Uberpr¨ ufung der Prozedur. Zwischen dem Berechnen von bn und b2n liegt lediglich ein einziger Aufruf. Die Anzahl der Multiplikationen entsprechen dem Logarithmus (Zur Basis 2) von n. Die Laufzeit der obigen Prozedur liegt also bei O(log n), was einen riesigen Unterschied zu O(n) ausmacht. Betr¨agt n etwa 1000, so sind lediglich 14 Multiplikationen notwendig. Ein Algorithmus mit logarithmischer Laufzeit geh¨ort so ziemlich zur schnellsten Klasse von Algorithmen. Ein weiteres Beispiel ist die Berechnung des gr¨oßten gemeinsamen Teilers zweier Zahlen a und b. Zur Berechnung des ggTs sind mehrere Verfahren bekannt: • Probiere alle Zahlen als Teiler • Zerlege a und b in Primfaktoren und finde gleiche Primfaktoren • Euklidischer Algorithmus An dieser Stelle interessiert uns nat¨ urlich der euklidische Algorithmus. Dieser berechnet den ggT durch: ggT (a, b) = ggT (b, a mod b). Dies machen wir nun anhand eines Beispiels. Wir w¨ ahlen die beiden Zahlen a = 206 und b = 40. ggT (206, 40) = ggT (40, 6)

(1.1)

= ggT (6, 4)

(1.2)

= ggT (4, 2)

(1.3)

= ggT (2, 0)

(1.4)

= 2

(1.5)

Die Implementierung des Algorithmus w¨are nun: 1 2 3 4

( d e f i n e ( ggt a b) ( i f (= b 0 ) a ( g g t b ( r e m a i n d er a b ) ) ) ) Es handelt sich hierbei um einen iterativen Prozess mit konstantem Speicherverbrauch. Wie sieht es nun mit der Laufzeit aus? Auf die Spur bringt uns hierbei der Satz von Lam´e (1845): Der Euklidische Algorithmus ben¨otigt k Schritte zur Berechnung des ggTs zweier Zahlen a und b mit min(a, b) ≥ F ib(k). Sei n = min(a, b) ⇒ Allgemein werden k Schritte ben¨ otigt mit n ≥ F ib(k) ≈ φk ⇒ Schrittzahl ist kleiner als logφ n ⇒ O(log n)

1 Abstraktion mit Prozeduren

1.2.4 Fermat’scher Primzahltest Der Primzahltest ist, wie der Name schon sagt, ein Verfahren um zu u ufen, ob eine ¨berpr¨ Zahl eine Primzahl ist. Primzahlen werden h¨aufig in der Kryptographie eingesetzt, daher ist der Nutzen von Primzahlen noch immer vorhanden. Die klassische Art und Weise ist die Suche nach Teilern. Man teilt die zu u ufende Zahl durch ganze Zahlen von 2 ¨berpr¨ √ bis n: ( define ( k l e i n s t e r − t e i l e r n) ( finde−teiler 2 n))

1 2

( define ( finde−teiler test n) ( cond ((> ( quadrat t e s t ) n ) n ) (( t e i l t ? test n) test ) ( e l s e ( f i n d e − t e i l e r (+ t e s t 1 ) n ) ) ) )

3 4 5 6 7

( define ( t e i l t ? a b) (= ( r e m a i n d e r b a ) 0 ) )

8 9 10

( d e f i n e ( p r i m z a h l ? n ) (= ( k l e i n s t e r − t e i l e r n ) n ) )

√ Dies hier ist ein linearer iterativer Prozess mit einer recht guten Laufzeit von O( n). Er ist allerdings noch immer langsam f¨ ur große Zahlen. W¨ unschenswert w¨are ein Algorithmus mit einer Laufzeit O(log n). Zu diesem Zwecke bedient man sich des kleinen fermatischen Satzes. Dieser sagt aus, dass wenn n eine Primzahl ist, f¨ ur eine beliebige ganze Zahl a mit 0 < a < n gilt, dass n a mod n = a. Daraus l¨ asst sich folgern, dass wenn n keine Primzahl ist, es wahrscheinlich viele Zahlen 0 < a < n mit der Eigenschaft an mod n 6= a gibt. Testet man die Bedingung an mod n = a nun f¨ ur zuf¨ allige Zahlen a, so kann man mit hoher Wahrscheinlichkeit davon ausgehen, dass die Primzahleigenschaft erf¨ ullt ist. Je mehr Tests man macht, umso geringer ist die Wahrscheinlichkeit eines Fehlers. Der Fermat-Test f¨ ur Primzahlen funktioniert also folgendermaßen: • W¨ ahle eine Zufallszahl 0 ≤ a < n • Teste an mod n = a Zum Ausw¨ ahlen der Zufallszahl unter SCHEME gibt es die Prozedur (random x), die eine ganze Zufallszahl z zwischen 0 ≤ z < x zur¨ uckliefert. Da jedoch die Ausf¨ uhrung des Tests bei den Werten 0 und 1 f¨ ur die Zufallszahl keinen Sinn macht, wird der R¨ uckgabewert der Prozedur geringf¨ ugig ge¨ andert, sodass die Zufallszahl eine Zahl 2 ≤ a < n ist. ( d e f i n e ( potmod b e n ) ( cond ((= e 0 ) 1 ) ( ( g e r a d e ? e ) ( r e m a i n d e r ( quadrat ( potmod b (/ e 2)

1 2 3 4 5

1.2 Prozeduren und Prozesse n))

n)) ( e l s e ( remainder (∗ b ( potmod b (− e 1 ) n)) n))))

7 8 9 10 11 12 13

( d e f i n e ( fermat−test n) ( fermat−test−mit−zufallszahl n (+ 2 (random (− n 2 ) ) ) ) )

14 15 16 17 18

( define ( fermat−test−mit−zufallszahl n a ) (= ( potmod a n n ) a ) )

19 20 21

( d e f i n e ( fast−prim ? n x ) ( cond ((= x 0 ) t r u e ) ( ( fermat−test n) ( fast−prime ? n (− x 1 ) ) ) ( else false )))

22 23 24 25 26

Bei dieser Prozedur zur Bestimmung, ob eine Zahl eine Primzahl ist oder nicht, kann es mit sehr geringer Wahrscheinlichkeit zu einem falschen Ergebnis kommen. Man nennt diese Art von Methoden Probalistische Methoden. Der Fermat-Test f¨ ur Primzahlen hat so zum Beispiel folgende Eigenschaften: • Falls das Ergebnis false ist, so handelt es sich sicher um keine Primzahl • Falls das Ergebnis true ist, so handelt es sich wahrscheinlich aber nicht absolut sicher um eine Primzahl • Je mehr Durchl¨ aufe/Tests gemacht werden, umso sicherer ist das Ergebnis Einige der Argumente f¨ ur solche Algorithmen, die m¨oglicherweise falsche Ergebnisse liefern, sind, dass sie meistens schneller als ein Algorithmus f¨ ur das gleiche Problem ¨ sind, der jedoch ein sicheres Ergebnis liefert oder dass auch ein ”korrekterAlgorithmus 13 unter Umst¨anden falsche Ergebnisse liefern kann . Bei Primzahlen speziell gibt es sogenannte Carmichael-Zahlen, die sehr selten sind und, obwohl sie keine Primzahlen sind, den Fermatschen Test bestehen14 . 13 14

zum Beispiel durch Hardwarefehler Ein Beispiel daf¨ ur ist die Zahl 172081

1 Abstraktion mit Prozeduren

1.2.5 Berechnung und Auswertung Um sowohl einfachere als auch komplexere Ausdr¨ ucke auszuwerten haben wir bereits das sogenannte Substitutionsmodell kennengelernt. Dieses ist jedoch rein informell. F¨ ur Programmierer und auch Implementierer ist es jedoch notwendig, ein formales mathematisches Modellieren zu haben. Um Berechnungen zu formalisieren sind Terme und Ausdr¨ ucke notwendig. Wie diese genau definiert sind, wird nun im Folgenden genauer betrachtet.

P Definition der Signatur: Menge von Paaren der Form Pf /n, wobei f Prozeduren und n ganze Zahlen sind mit der Eigenschaft f /m, f /n ∈ dann ist m = n. Um das zu u ¨bersetzen: f sind Prozeduren und n die Anzahl der dazugeh¨origen Argumente/Parameter. Unter SCHEME k¨ onnen keine Methoden gleichen Namens existieren, die eine unterschiedliche Anzahl von Parametern besitzen. P c ist eine Konstante falls c/0 ∈ gilt, denn dann liefert ein Aufruf von c stets P einen festen Wert zur¨ uck. Zahlen sind nat¨ urlich ebenfalls Konstanten, d.h. es gilt n/0 ∈ f¨ ur alle Zahlen n. Terme enthalten nur Signatursymbole und Variablen15 .

Beispiel:

= {+/2, −/2, ∗/2, quadrat/1, quadratsumme/2, true/0, f alse/0 . . . }

Tats¨ achlich k¨ onnen die arithmetischen Operatoren mehr als zwei Argument aufnehmen, jedoch sehen wir die Definitionen jetzt als etwas strenger an und erlauben lediglich zwei Argumente.

P Definition der Menge der Terme: Sei Signatur und X Menge von Variablen16 . P P Dann ist die Menge der Terme T (X) u und X wie folgt definiert: ¨ber 1. F¨ ur alle Konstanten c/0 ∈

gilt c ∈ TP (X)

2. F¨ ur alle Variablen x ∈ X gilt x ∈ TP (X) 3. F¨ ur alle n-stelligen Funktionen f /m ∈ TP (X) Beispiel: Sei TP 15 16

und t1 . . . tn ∈ TP (X) ist (f t1 . . . tn ) ∈

P , X = {x, y, z} dann gilt (+ 1 2) ∈ TP (X); (quadratsumme (+ y 1) (∗ z 2)) ∈

Hier: Parameter P welche disjunkt zu sind

1.2 Prozeduren und Prozesse P Definition Programm: Ein Programm ist ein Tripel ( , X, R) mit •

ist Signatur

• X ist Variablenmenge disjunkt zu

• R ist eine Menge von Regeln der Form (f x1 . . . xn ) → r, wobei f /n ∈ x1 . . . xn ∈ X, r ∈ TP ({x1 . . . xn })

P ,

• reele Regelseiten d¨ urfen nur formale Parameter enthalten • manchmal ist erlaubt, dass die linke Regelseite ein beliebiger Term ist (⇒ Termersetzungssystem, pattern matching) • SCHEME-Definition: (def ine (f x1 . . . xn )r) ≈ obige Regel Definition Substitution: Substitution σ ist Funktion σ : x → TP (X), die jeder Variablen einen Term zuordnet.

Anwendung einer Substitution: σ auf x ∈ TP (X), geschrieben tσ, ist wie folgt definiert17 : • Falls t ∈ X, dann tσ = σ(t) (Also falls t eine Variable ist) • Falls t/0 ∈

P , dann tσ = t (Also falls t eine Konstante ist)

• Falls (f t1 . . . tn ), dann ist tσ = (f t1 σ . . . tn σ) Somit ersetzt die Substitution nur Variablen - alles andere bleibt unver¨andert.

Beispiel: Sei σ eine Substitution mit σ(x) = 2, σ(y) = (+ z 1), σ(z) = z, dann ist (* x (+ y z))σ = (* 2 (+ (+ z 1) z)) .

Definition Position: Zum Ausrechnen eines Terms werden bestimmte Ersetzungen an bestimmten Positionen im Term vorgenommen. Die Position identifiziert eindeutig eine ¨ Stelle im Term . Damit sind die Positionen im Term t Pos(t). Ublicherweise werden die Positionen als Folgen nat¨ urlicher Zahlen angegeben, wobei die leere Folge () als die Position der Wurzel definiert ist, also als der Einstiegspunkt des Terms. 17

induktiv

1 Abstraktion mit Prozeduren Beispiel: Sei t = (* x (+ y z)) und Pos(t) = {, < 1 >, < 2 >, < 2, 1 >, < 2, 2 >}, dann entspr¨ ache dem Einstiegspunkt des Terms. < 1 > entspr¨ache dem ersten Element, also dem x. < 2 > entspricht dem Teilterm (+ y z) und < 2, 1 > wiederum dem y innerhalb des Teilterms. Das z innerhalb des Teilterms ist mit < 2, 2 > indiziert. Ist p ∈ P os(t), dann heißt t|p Teilterm von t an der Position p. • p = → t| = t • Wenn p = dann t = (f t1 . . . tn ) mit tp1 ...pn = tp1 | Beispiel: Sei t = (* x (+ y z)) und sei t| gesucht. t| w¨are (+ y z) und t| entsprechend dann nur noch z.

Definition Ersetzung: Ist p ∈ P os(t), t0 ein Term, dann heißt t[t0 ]p Ersetzung von t|p durch t0 an der Stelle p. • p = → t[t0 ] = t0 • Wenn p =< p1 , p2 . . . pn > und t = (f t1 . . . tn ) dann ist t[t0 ]p = (f t1 . . . tp1−1 tp1 [t0 ] tp+1 Beispiel: Sei t = (* x (+ y z)) und t0 = (+zy), dann ist t[t0 ] = (* x (+ z y)).

P Definition Berechnungsschritt: Sei P = ( , X, R), dann ist der Berechnungsschritt t1 ⇒ t2 definiert falls p ∈ P os(t1 ), l → r ∈ R und eine Substitution existiert mit der Eigenschaft • σ(l) = t1 |p (σ ersetzt formale Parameter durch die aktuellen) • t2 = t1 [rσ]p (Ersetze Teilterm durch rechte Regelseite nach Substitution der formalen Parameter) Die Berechnung t1 ⇒ ∗t2 ist eine18 Folge von Schritten t1 ⇒ s1 ⇒ s2 ⇒ · · · ⇒ sn ⇒.

Beispiel 1: (quadrat x) → (* x x) ∈ R. (quadrat (+ 1 2)), p =, σ(x) = (+ 1 2)

Beispiel 2: (* 3 (quadrat 4)), p =< 2 >, σ(x) =4 ⇒ (* 3 (* 4 4)) 18

unter Umst¨ anden auch eventuell leere

1.2 Prozeduren und Prozesse Auswertung vordefinierter Funktionen Die Auswertung vordefinierter Funktionen 19 funktioniert konzeptiell durch implizite20 Menge von Regeln. Formal ist das kein Programm, aber zur Vereinfachung sind das f¨ ur uns nur weitere Termersetzungsregeln. (+ 0 0) ⇒ 0 (+ 0 1) ⇒ 1 ... Somit wird (quadrat (+ 1 2)) auf folgende Weise ausgewertet: (quadrat (+ 1 2)) ⇒ (* (+ 1 2) (+ 1 2)) ⇒ (* 3 (+ 1 2)) ⇒ (* 3 3) ⇒ 9 Es ist jedoch auch m¨ oglich, den Term auf folgende Weise auszuwerten: (quadrat (+ 1 2)) ⇒ (quadrat 3) ⇒ (* 3 3) ⇒ 9 Bei ersterem handelt es sich um die Normalordnung, bei letzterem um die applikative Ordnung. Worum genau es sich dabei handelt, wird sp¨ater noch behandelt. Definition Normalform: Term t heißt in Normalform, falls es kein Term t0 gibt mit t ⇒ t0 . Das heißt es ist kein weiterer Schritt m¨oglich. Normalform ≈ Endergebnis ≈ Werte Auswertung in applikativer Ordnung Informell:

Werte Argumente vor der Prozeduranwendung aus.

Formell: Falls t1 ⇒ t2 mit t2 = t1 [rσ]p , dann ist t1 |p = (f s1 . . . sn ) und jedes si ist in Normalform. 19 20

z.B. +, - . . . und damit unendliche viele

1 Abstraktion mit Prozeduren Auswertung in Normalordnung Informell: Ersetze alle Prozeduraufrufe, bis nur elementare vorhanden sind und werte diese dann aus. Formell: Falls t1 ⇒ t2 mit t2 = t1 [rσ]p , dann ist t1 |p ¨außerster Teilterm, an dem ein Schritt m¨ oglich ist, das heißt falls p =< p1 . . . pn >, dann ist ein Schritt an < p1 . . . pi > mit i < n nicht m¨ oglich. Beispiel: ( f 5) (f 5) ⇒0 (quadratsumme (+ 5 1) (* 5 2)) ⇒0 (+ (quadrat (+ 5 1)) (quadrat (* 5 2))) ⇒0 (+ (* (+ 5 1) (+ 5 1))(* (* 5 2) (* 5 2))) ⇒0 (+ (* 6 6)(* 10 10)) ⇒0 (+ 36 100) ⇒0 136 Hier merkt man, dass zwar eine Doppelauswertung von (+ 5 1) und (* 5 2) vorliegt, das Endergebnis jedoch identisch zu dem der applikativen Ordnung ist. Die Normalordnung kann jedoch ein Ergebnis liefern, wo die applikative Ordnung nicht terminiert. Die Normalordnung liefert immer eine Normalform zur¨ uck, sofern eine existiert. Daf¨ ur ist die applikative Ordnung h¨aufig effizienter implementiert. In diesem Zusammenhang sei noch erw¨ ahnt, dass SCHEME die applikative Ordnung besitzt. Es gibt nur wenige Ausnahmen, zum Beispiel if, wo zuerst die Bedingung ausgewertet wird.

2 Abstraktion mit Daten 2.1 Einf¨ uhrung 2.1.1 Abstrakte Daten Anwender: Kennt nicht die interne Struktur; benutzt nur festgelegte Operationen Implementierer: W¨ ahlt eine passende Struktur; stellt Operationen bereit Beides zusammengefasst bedeutet das, dass sich Implementierer und Anwender u ¨ber eine sogenannte Schnittstelle einig sein m¨ ussen. Wenn das geschehen ist, k¨onnen sowohl Implementierer als auch Anwender weiterarbeiten. Vorteile dieses Systems sind: • Interne Implementierung ist leicht austauschbar • Mehr Modularit¨ at • Bessere Verst¨ andlichkeit großer Programme Schnittstelle: Eine sogenannte Schnittstelle besteht aus Selektoren, Konstruktoren und Operatoren. Selektoren sorgen f¨ ur das Extrahieren von Teilinformationen. Konstruktoren erzeugen komplexere Daten, w¨ ahrend die Operatoren zur Verkn¨ upfung dieser Daten sorgen. Rationale Zahlen nz bestehen aus einem Z¨ahler und einem Nenner, wobei es sich bei beidem um ganze Zahlen handelt. Nun m¨ochten wir folgende Schnittstellen haben: • Konstruktor: (konstr-rat z n): liefert rationale Zahl • Selektoren: (zaehler r): liefert den Z¨ ahler der rationalen Zahl (nenner r): liefert den Nenner der rationalen Zahl • Operatoren: (define (+rat x y) (konstr-rat (+ (* (zaehler x) (nenner y)) (* (zaehler y) (nenner x))) (* (nenner x (nenner y)))

2 Abstraktion mit Daten Schnittstellendefinition: Eine sogenannte Struktur ist die Kombination mehrerer Daten zu einer Einheit. Eine neue Sonderform zu diesem Zweck ist (jedoch nur innerhalb der Dr. SCHEME-Umgebung): (define-struct sname (k1...kn)). sname ist hierbei der Name der Struktur. k1 . . . kn sind die Komponentennamen. Durch die Definition werden sogleich mehrere neue Operationen zur Verf¨ ugung gestellt: • (make-sname x1...xn): Erzeuge neue Struktur mit Komponenten x1 . . . xn • (sname-ki s): liefert Komponente ki der Struktur s(i = 1 . . . n) • (sname? x): Ist x eine sname-Struktur? Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (make-rat 1 3) (make-rat 1 3) > (rat-nenner (make-rat 1 3)) 3 Intuitiv handelt es sich bei der Struktur um eine Box mit Schubladen, die Namen haben.

Gesetze: Wichtig ist nicht die Implementierung, sondern die Eigenschaften (Gesetze). Es gilt immer: Sei s ein Wert von (make-sname (x1...xn)), dann gilt (sname-ki s) = x mit i = 1 . . . n und außerdem (sname? s) = true. Oder in Kurzschreibweise: (sname-ki (make-sname (x1...xn)) = x. Konkret auf unser obiges Beispiel ergeben sich folgende beiden Gesetze: • (rat-zaehler (make-rat z n)) = z • (rat-nenner (make-rat z n)) = n Dies mag trivial erscheinen, ist jedoch eine grundlegende und sehr wichtige Eigenschaft. Erweiterung des Substitutionsmodells um obige Gesetze: Das bedeutet auf unser Beispiel von eben bezogen: (define r (make-rat 2 5)) ⇒ (+ (rat-zaehler r) 3) ⇒ (+ 2 3) ⇒ 5 Um jetzt die gew¨ unschten Schnittstellen zu implementieren, m¨ ussen diese nun auch noch definiert werden:

2.1 Einf¨ uhrung

1 2 3 4 5 6

( d e f i n e ( konstr−rat z n) ( make−rat z n ) ) ( define ( zaehler r ) ( rat−zaehler r )) ( d e f i n e ( nenner r ) ( rat−nenner r ) ) Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. (define eindrittel (Konstr-rat 1 3)) > (+rat eindrittel eindrittel) (make-rat 6 9) Hier ergibt sich ein Problem. Wie man sehen kann, wird die Zahl 31 mit sich selbst addiert. Heraus kommt jedoch statt 23 das ungek¨ urzte Ergebnis 69 . Um Abhilfe zu schaffen, k¨onnen wir die ggT-Division verwenden. Eine M¨ oglichkeit w¨are es, diese nach jeder Berechnung anzuwenden. Da dies aber recht unsch¨ on ist, verwenden wir sie stattdessen direkt bei der Konstruktion von Zahlen:

1 2 3

( d e f i n e ( konstr−rat z n) ( make−rat ( / z ( g g t z n ) ) (/ n ( ggt z n ) ) ) ) Somit liefern die Berechnungsprozeduren jetzt die richtigen Ergebnisse, wobei lediglich eine Prozedur ge¨ andert werden musste. Schichtenentwurf von Programmen: Wenn in der Realit¨at große Programme erarbeitet werden, so werden diese meist auf mehrere Schichten u ¨bertragen. Die unterste Schicht enth¨alt so zum Beispiel lediglich elementare Objekte der Programmiersprache, w¨ahrend die oberste Schicht die Anwendungsobjekte enth¨alt. Wichtig dabei ist, dass es kein Durchgreifen durch diese Schichten geben sollte. Es sollten immer die Schnittstellen benutzt werden.

2.1.2 Abstrakte Datentypen Wir haben bereits ein Beispiel von abstrakten Daten gezeigt. Wie u uft man nun ¨berpr¨ aber die Korrektheit einer Implementierung? Vor allem dadurch, dass sie bestimmte Gesetze erf¨ ullt. Das machen wir uns an unserem vorherigen Beispiel klar. Dort wurden unter anderem durch konstr-rat, zaehler, nenner rationale Zahlen realisiert. Diese Implementierung ist genau dann korrekt, falls immer1 gilt: (zaehler (konstr − rat z n)) z = (nenner (konstr − rat z n)) n 1

d.h. f¨ ur beliebige Werte f¨ ur z und n

2 Abstraktion mit Daten . W¨ urden wir lediglich aussagen, dass der Z¨ahler gleich dem Z¨ahler und dem Nenner gleich dem Nenner w¨ are, h¨ atten wir einen Widerspruch f¨ ur den Fall des K¨ urzens mit dem ggT. Wir m¨ ussen also schon die Verh¨altnisse vergleichen. Daten sind also hier fest definiert mit Operationen und Gesetzen. Die Abstraktion dabei ist, dass die konkrete Implementierung nicht festgelegt und damit f¨ ur den Benutzer nicht wichtig ist. Definition Abstrakter Datentyp: Ein abstrakter Datentyp2 (Σ, X, E) besteht aus: • Σ: Signatur • X: Variablennennung3 • E: Menge von Gleichungen der Form t = t04 Wichtig: Die Gleichungen sind eventuell5 nicht ausf¨ uhrbar. Sie sind keine Regeln, wie das bei Programmen der Fall w¨are. Definition Implementierung eines ADT Ein Programm (Σ, E, R) ist eine m¨ogliche Implementierung eines ADT (Σ, X, E), falls dieses Programm alle Gleichungen erf¨ ullt, das heißt falls f¨ ur jede Gleichung t = t0 ∈ E und alle Substitutionen σx → TΣ ({}) gilt σ(t) = t1 ⇔ t2 ⇔ · · · ⇔ tn = σ(t0 ), wobei n ≥ 0 und s ⇔ s0 , falls s ⇒ s0 oder s ⇐ s0 . Anders ausgedr¨ uckt: Die linke und die rechte Gleichung m¨ ussen durch beliebige Berechnungsschritte ineinander u uhrbar sein. ¨berf¨ Die erste Implementierung rationaler Zahlen6 erf¨ ullt das ADT-Gesetz.

⇒ ⇒ ⇒ ⇒ ⇒ 2

auch: ADT Disjunkt zu Σ 4 Wobei t, t0 ∈ TΣ (X) 5 Genau genommen meistens 6 Ohne ggT-K¨ urzen 3

(zaehler (konstr − rat z n)) (nenner (konstr − rat z n) (rat − zaehler (konstr − rat z n)) (nenner (konstr − rat z n) (rat − zaehler (konstr − rat z n)) (rat − nenner (konstr − rat z n) (rat − zaehler (make − rat z n)) (rat − nenner (make − rat z n) ... z n

(2.1) (2.2) (2.3) (2.4) (2.5) (2.6)

2.2 Hierarchische Datenstrukturen Da die beiden Terme ineinander u uhrbar sind7 , gilt die Implementierung. Analog ist ¨berf¨ auch die Begr¨ undung, warum die zweite Implementierung korrekt ist.

2.2 Hierarchische Datenstrukturen 2.2.1 Listen Eine Liste, auch Sequenz genannt, ist eine geordnete Menge von Objekten. Das geordnet ist hierbei ein Hinweis auf eine Reihenfolge und das Menge ein Hinweis auf eine beliebige Gr¨oße. Tats¨ achlich geschieht die Modellierung in SCHEME durch Fallunterscheidung. Der erste Fall w¨ are, dass die Liste leer ist und damit kein Element enth¨alt. Dies wird mit dem Schl¨ usselwort empty gezeigt. Der zweite Fall w¨are analog, dass die Liste nicht leer ist und damit ein erstes Element sowie eine Liste mit weiteren Elementen enth¨alt. Die Notation ist in diesem Fall (const 1.Element Restliste) (cons 1 empty) → eine Liste mit dem Element 1 (cons 1 (cons 2 empty)) → eine Liste mit den Elementen 1 und 2 (cons 1 (cons 2 (cons 3 empty))) → eine Liste mit den Elementen 1, 2, 3

empty 1

Abbildung 2.1: Kasten-Zeiger-Darstellung Um nun mit Listen in SCHEME arbeiten zu k¨onnen, m¨ ussen wir wissen, wie der Zugriff darauf geschieht. Mit dem Befehl first kommt man an das erste Element heran, mit dem Befehl rest erh¨ alt man Zugriff auf den Rest der Liste. Die Implementierung interessiert uns nicht weiter, wichtig ist nur, dass wir die dazugeh¨origen Gesetze kennen: (first (cons e l)) = e (rest (cons e l)) = l Achtung: cons erzeugt eine Liste und kein Paar8 . Zur Vereinfachung gibt es die spezielle Sonderform list. Damit gilt (list < a1 >< a2 > · · · < an >) = (cons < a1 > (cons < a2 > (... (cons < an >)...))) Operationen auf Listen Um Operationen auf Listen durchzuf¨ uhren, geht man typischerweise rekursiv vor. Um zum Beispiel das n-te Element einer Liste l zu erhalten schreibt man folgende Prozedur: 7 8

Die P¨ unktchen stehen hier f¨ ur die vorherigen Gesetze f¨ ur die Rat-Struktur d.h. der Befehl (cons 1 2) w¨ urde zum Beispiel unweigerlich zu einer Fehlermeldung f¨ uhren

2 Abstraktion mit Daten

1 2 3 4

( d e f i n e ( n−tes n l ) ( i f (= n 0 ) ( first l ) ( n−tes (− n 1 ) ( r es t l ) ) ) ) Damit ergibt sich auch schon ein recht h¨aufig angewandtes Schema f¨ ur Operationen auf Listen:

1 2 3 4

( define ( if ( ( (

( listop . . . l ) ) . . . ( first l ) . . . ) . . . ( r es t l ) . . . ) ) )

Es gibt auch h¨ aufig eine Fallunterscheidung zwischen leeren und nicht-leeren Mengen. Dazu gibt es das Pr¨ adikat empty?. Ist die mitgelieferte Liste leer, so gibt dieses Pr¨adikat true zur¨ uck, andernfalls false. Analog gibt es dazu passend das Pr¨adikat cons?, welches u uft, ob eine Liste mindestens ein Element enth¨alt. Damit ergibt sich ein weiteres, ¨berpr¨ h¨ aufiges Schema unter SCHEME f¨ ur Operationen auf Listen: 1 2 3 4

( define ( listop . . . l ) ( i f ( empty ? l ) ( ... ) ( . . . ( f i r s t l ) . . . ( r es t l ) . . . ) ) ) Das zeigen wir nun am Beispiel einer Prozedur, welche die L¨ange einer Liste berechnet:

1 2 3 4

( define ( laenge l ) ( i f ( empty ? l ) 0 (+ 1 ( l a e n g e ( r es t l ) ) ) ) ) Eine weitere Technik, die wir uns hier ansehen m¨ochten, ist das Durchlaufen einer Liste um eine Ergebnisliste zu konstruieren. Nehmen wir an, wir m¨ochten eine Liste mit allen Elementen aus der Liste l1 und allen Elementen aus der Liste l2 konstruieren. Das machen wir mit folgender Prozedur:

1 2 3 4

( d e f i n e (append l 1 l 2 ) ( i f ( empty ? l 1 ) l2 ( cons ( f i r s t l 1 ) (append ( r es t l 1 ) l 2 ) ) ) )

Baumstrukturen Wie bereits erw¨ ahnt sind Baumstrukturen relativ langsam, jedoch h¨aufig notwendig, wenn es um hierarchische statt um sequentielle Anordnungen von Daten geht. Da dies bei Listen der Fall ist, ben¨ otigen wir hierbei h¨aufiger Baumstrukturen. Stellen wir uns die

2.2 Hierarchische Datenstrukturen Datenstrukturen als Baum mit einer Wurzel, mehreren Knoten und mit Sohnknoten (Mit Wurzeln von Teilb¨ aumen), sowie mit Bl¨ attern vor. Die Bl¨atter sind hierbei schlussendlich die Daten.

Abbildung 2.2: Modellierung der Baumstruktur Zur Modellierung gibt es wieder eine Fallunterscheidung. Im ersten Fall ist der Baum ein Blatt, also eine Zahl. Im zweiten Fall ist der Baum ein innerer Knoten, das heißt eine Liste der S¨ohne. In diesem Fall w¨ are der Baum (list 1 (list 2 3) 4). Zur Fallunterscheidung, ob es sich um ein Blatt handelt oder nicht9 wird der Befehl number? verwendet, der true zur¨ uckliefert, falls es sich um eine Zahl handelt, ansonsten false. Damit ergibt sich folgender Code, um die Anzahl der Bl¨ atter eines solchen Baumes zu erhalten: 1 2 3 4 5

( define ( blaetterzahl b) ( cond ( ( l e a f ? b ) 1 ) ( ( empty ? b ) 0 ) ( e l s e (+ ( b l a e t t e r z a h l ( f i r s t b ) ) ( b l a e t t e r z a h l ( r es t b ) ) ) ) ) )

2.2.2 Quotieren Das sogenannte Quotieren in SCHEME bedeutet, dass nicht nur Zahlen, sondern auch Symbole als Rechenobjekte erlaubt werden. Nehmen wir zum Beispiel eine Liste von Symbolen: Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (list a b c) reference to undefined identifier: a > Wie man sehen kann, versucht SCHEME a auszuwerten und erzeugt dabei einen Fehler, da a noch unbekannt ist. Um SCHEME zu zwingen, das Symbol a nicht auszuwerten, quotieren wir. Wir schreiben ein Apostroph davor. 9

Beziehungsweise ob es sich um eine Zahl oder nicht handelt

2 Abstraktion mit Daten

Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (list ’a ’b) (cons ’a (cons ’b empty)) > Um zwei Symbole auf Gleichheit zu u ufen, gibt es den Befehl eq?. ¨berpr¨ Extrahiere Restliste einer gegebenen Liste, die mit einem bestimmten Symbol beginnt: 1 2 3 4 5

( d e f i n e (menmq e l ) ( cond ( ( empty ? l ) f a l s e ) ( ( empty ? l ) f a l s e ) ( ( eq? e ( f i r s t l ) ) l ) ( e l s e (memq e ( r es t l ) ) ) ) ) Aufgerufen wird diese Prozedur dann wie folgt: Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (memq ’b (list ’a ’b ’c)) (list ’b ’c) Nun m¨ ochten wir eine Prozedur schreiben, mit der das Ableiten einer Funktion m¨oglich wird. Nicht nummerisch, sondern vielmehr symbolisch. Dazu u ¨berlegen wir uns, woraus eine Funktion aufgebaut sein kann: • Zahlkonsten • Variablen • Summen, Produkte (erweiterbar: Logarithmus, Sinus...) Die Darstellung einer Funktion kann ebenfalls auf verschiedene Arten geschehen: 1. Stringdarstellung, d.h. Funktion ≈ Liste der Symbole (z.B. ax+b“) ” ¨ 2. Ubliche Pr¨ afixschreibweise → g¨ unstiger, weil Priorit¨aten klar sind (z.B. ax+b“ ≈ ” (list ’+ (list ’* ’a ’x) ’b)) Wir entwickeln nun zwei Konstruktoren, um sp¨ater die abgeleitete Funktion einfacher zusammensetzen zu k¨ onnen.

1 2

( d e f i n e ( konstr−summe a1 a2 ) ( l i s t ’+ a1 a2 ) )

3 4 5

( d e f i n e ( konstr−produkt a1 a2 ) ( l i s t ’ ∗ a1 a2 ) )

2.2 Hierarchische Datenstrukturen Damit wir sp¨ ater die einzelnen Teile des Funktionsterm analysieren k¨onnen, brauchen wir auch einige geeignete Pr¨ adikate. 1 2

( define ( konstante ? a ) ( number ? a ) )

3 4 5

( define ( variable ? a) ( symbol ? a ) )

6 7 8 9 10

( d e f i n e (summe? a ) ( i f ( cons ? a ) ( eq? ( f i r s t a ) ’+) false ))

11 12 13 14 15

( d e f i n e ( produkt ? a ) ( i f ( cons ? a ) ( eq? ( f i r s t a ) ’ ∗ ) false ))

16 17 18 19 20

( d e f i n e ( g l e i c h e − v a r i a b l e ? v1 v2 ) (and ( v a r i a b l e ? v1 ) ( v a r i a b l e ? v2 ) ( eq? v1 v2 ) ) ) Um auf die einzelnen Teile des Terms zuzugreifen zu k¨onnen, benutzen wir die schon vorher entwickelte Prozedur, mit der ein bestimmtes Element aus der Liste herausgeholt werden kann.

1 2

( d e f i n e ( operand1 a ) ( n−tes 1 a ) )

3 4 5

( d e f i n e ( operand2 a ) ( n−tes 2 a ) ) Nun beginnt das eigentliche Differenzieren, wo wir lediglich die mathematischen Regeln umsetzen.

1 2 3 4 5 6 7 8 9

( define ( ableitung a v) ( cond ( ( konst ? a ) 0) (( variable ? a) ( i f ( gleiche−variable ? a v) 1 0)) ( ( summe? a ) ( konstr−summe ( a b l e i t u n g ( operand1 a ) v ) ( a b l e i t u n g ( operand2 a ) v ) ) ) ( ( produkt ? a ) ( konstr−summe

2 Abstraktion mit Daten ( konstr−produkt ( operand1 ( a b l e i t u n g ( operand2 a ) ( konstr−produkt ( operand2 ( a b l e i t u n g ( operand1 a )

10 11 12 13

a) v)) a) v))))))

Schlussendlich merken wir, dass das Ergebnis nicht immer zufriedenstellend ist. Es ist richtig, aber oftmals nicht vereinfacht. Wir u ¨berlegen uns diverse Vereinfachungsregeln und setzen diese in den Konstruktoren ein. x·0=0 0·x=0 1·x=x x·1=x x+0=1 0+x=x .. . 1 2 3 4 5 6 7 8 9 10 11

( d e f i n e ( konstr−summe a1 a2 ) ( cond ( ( and ( number ? a1 ) ( number ? a2 ) ) (+ a1 a2 ) ) ( ( number ? a1 ) ( i f (= a1 0 ) a2 ) ( l i s t ’+ a1 a2 ) ) ( ( number ? a2 ) ( i f (= a2 0 ) a1 ) ( l i s t ’+ a1 a2 ) ) ( e l s e ( l i s t ’ a a1 a2 ) ) ) )

12 13 14 15 16 17 18 19 20 21 22 23 24 25

( d e f i n e ( konstr−produkt a1 a2 ) ( cond ( ( and ( number ? a1 ) ( number ? a2 ) ) ( ∗ a1 a2 ) ) ( ( number ? a1 ) ( cond ((= a1 0 ) 0 ) ((= a1 1 ) a2 ) ( e l s e ( l i s t ’ ∗ a1 a2 ) ) ) ) ( ( number ? a2 ) ( cond ((= a2 0 ) 0 ) ((= a2 1 ) a1 ) ( e l s e ( l i s t ’ ∗ a1 a2 ) ) ) ) ( e l s e ( l i s t ’ ∗ a1 a2 ) ) ) )

2.2 Hierarchische Datenstrukturen

2.2.3 Implementierung von Mengen Mengen sind Sammlungen von Objekten, ohne Reihenfolge und es gibt keine doppelten Elemente. ADT-Mengenoperationen w¨ aren Σ ={leer/0, vereinigung/2,schnitt/2,hinzufuegen/2,element?/2} Gesetze g¨abe es dann folgende: (element? x (leer)) = false (element? x (hinzufuegen x s)) = true (vereinigung s1 s2) = (or (element? x s1) (element? x s2)) (schnitt s1 s2) = (and (element? x s1) (element? x s2)) (hinzufuegen x (hinzufuegen x s)) = (hinzufuegen x s) (hinzufuegen x (hinzufuegen y s)) =(hinzufuegen y (hinzufuegen x s))

Implementierung von Mengen als ungeordnete Liste: Die Idee, die hinter dieser Implementierung steckt ist die, dass die Menge einer Liste der Elemente entspricht, jedoch ohne Duplikate. 1 2 3 4

( d e f i n e ( element ? x s ) ( cond ( ( empty ? s ) f a l s e ) ( equal ? x ( f i r s t s ) ) t r u e ) ( e l s e ( e l e m e n t ? x ( r es t s ) ) ) )

5 6

( d e f i n e l e e r empty )

7 8 9 10 11

( define ( hinzufuegen x s ) ( i f ( element ? x s ) s ( cons x s ) ) )

12 13 14 15 16 17 18

( d e f i n e ( s c h n i t t s1 s2 ) ( cond ( ( empty ? s 1 l e e r ) ( ( element ? ( f i r s t ? s1 ) s2 ) ( cons ( f i r s t s 1 ) ( s c h n i t t ( r es t s 1 ) s 2 ) ) ) ( e l s e ( s c h n i t t ( r es t s 1 ) s 2 ) ) ) ) ) Die Vereinigung geschieht analog. Wir wollen uns nun Gedanken zur Effizienz dieser Implementierung machen. Nehmen wir n als die M¨ achtigkeit der Menge an. Dann gilt f¨ ur die Laufzeit: • element? O(n) • hinzufuegen? O(n) • schnitt O(n2 )

2 Abstraktion mit Daten Das ist schon ganz gut, allerdings m¨ ussen die Konstruktoren und die Selektoren die ungeordnete Liste im schlimmsten Fall komplett durchgehen. Bessere w¨are also die Implementierung mit einer Sortierung.

Implementierung von Mengen als aufsteigend sortierte Liste: Es muss also eine totale Ordnung der Elemente herrschen, sodass nur noch eine Darstellung der Mengen m¨ oglich ist. Um das zu realisieren brauchen wir lediglich die Prozeduren leicht abzu¨andern. Das wichtigste ist dabei nat¨ urlich das Hinzuf¨ ugen neuer Elemente. 1 2 3 4 5

( define ( hinzufuegen x s ) ( cond ( ( empty ? s ) ( cons x s ) ) ((= x ( f i r s t s ) ) s ) ((< x ( f i r s t s ) ) ( cons x s ) ) ( e l s e ( cons ( f i r s t s ) ( h i n z u f u e g e n x ( r es t

s ))))))

Die Komplexit¨ at ist im Durchschnitt nun O( n2 ) = O(n), da die Konstanten wegfallen. Also keine Verbesserung. Analog dazu ist die Laufzeit von element? auch O(n). Allerdings k¨onnen wir die Implementierung der Prozedur schnitt wesentlich verbessern, indem wir beide Listen gleichzeitig verarbeiten. Da die Listen sortiert sind, vergleichen wir immer die ersten Elemente. Sind sie gleich, werden sie dem Schnitt hinzugef¨ ugt und falls sie ungleich sind, wir das kleinere Element gestrichen. 1 2 3 4 5 6 7 8 9

( d e f i n e ( s c h n i t t s1 s2 ) ( i f ( or ( empty ? s 1 ) ( empty ? s 2 ) ) leer ( cond ((= ( f i r s t s 1 ) ( f i r s t s 2 ) ) ( cons ( f i r s t s 1 ) ( s c h n i t t ( r es t s 1 ) ( r es t s 2 ) ) ) ) ((< ( f i r s t s 1 ) ( f i r s t s 2 ) ) ( s c h n i t t ( r es t s 1 ) s 2 ) ) ( e l s e ( s c h n i t t s 1 ( r es t s 2 ) ) ) ) ) ) Da bei jedem Schritt nun mindestens ein Element wegf¨allt, betr¨agt die Komplexit¨at nun |s1 | + |s2 | ⇒ O(n) statt wie zuvor O(n2 ). Das stellt also eine wesentliche Verbesserung dar. Die Schnelligkeit l¨ asst sich jedoch durch eine weitere Implementierung nochmals beschleunigen.

Implementierung von Mengen als geordnete Bin¨ arb¨ aume: Die Idee zur Implementierung besteht darin, die Mengen als B¨aume anzusehen, wobei jeder Baum allerdings ¨ maximal zwei Aste haben kann. Der linke Teilbaum enth¨alt dabei nur kleinere Elemente, der rechte nur gr¨ oßere Elemente als das Element an der Wurzel. Dabei ist die Darstellung jedoch nicht eindeutig.

2.2 Hierarchische Datenstrukturen

4 5

2 1

Der Vorteil bei dieser Ordnung w¨ urde sich zum Beispiel stark bei der Prozedur element? bemerkbar machen. Da bei jedem Schritt die Anzahl der m¨oglichen Elemente halbiert wird, h¨ atte die Prozedur eine Laufzeit von O(log n) statt O(n)10 . 1

( d e f i n e − s t r u c t baum ( e i n t r a g l i n k s r e c h t s ) )

2 3

( d e f i n e l e e r empty )

4 5 6 7 8 9 10

( d e f i n e ( element ? x s ) ( cond ( ( empty ? s ) f a l s e ) ((= x ( baum−eintrag s ) ) t r u e ) ((< x ( baum−eintrag s ) ) ( e l e m e n t ? x ( baum−links s ) ) ) ( e l s e ( e l e m e n t ? x ( baum−rechts s ) ) ) ) )

11 12 13 14 15 16 17 18 19 20 21 22

( define ( hinzufuegen x s ) ( cond ( ( empty ? s ) (make−baum x empty empty ) ) ((= x ( baum−eintrag s ) ) s ) ((< x ( baum−eintrag s ) ) (make−baum ( baum−eintrag s ) ( h i n z u f u e g e n x ( baum−links s ) ) ( baum−rechts s ) ) ) ( e l s e (make−baum ( baum−eintrag s ) ( baum−links s ) ( h i n z u f u e g e n x ( baum−rechts s ) ) ) ) ) ) Bei ausgeglichenen B¨ aumen ist die Laufzeit der Prozedur zum Hinzuf¨ ugen von Elementen ebenfalls O(log n). F¨ ur die Prozeduren zur Schnittmenge und Vereinigungsmenge gibt es keine effizientere Methode als den Baum zu durchlaufen und eine Elementpr¨ ufung zu machen. Die Laufzeit betr¨ agt dabei O(n · log n). Damit die Prozeduren allerdings halbwegs schnell laufen, wird angenommen, dass die Elemente zuf¨allig eingef¨ ugt werden. W¨ urde man etwa {1, 2, 3, 4, 5, 6} nacheinander einf¨ ugen h¨atte man einen sehr einseitigen Baum, der einer Liste entspricht. Eine bessere L¨osung w¨are also ein ADT, der daf¨ ur 10

Allerdings nur bei einem ausgeglichenen Baum

2 Abstraktion mit Daten sorgen w¨ urde, dass die B¨ aume stets ausgeglichen bleiben. Darauf wird aber an dieser Stelle nicht weiter eingegangen. Mengen werden oftmals in Datenbanksystemen eingesetzt, wobei die einzelnen Elemente dann h¨ aufig aus Paaren (Schl¨ ussel, Inhalt) bestehen, da man die Schl¨ ussel wesentlich schneller miteinander vergleichen kann. Diese Systeme werden oftmals ebenfalls als B¨ aume realisiert, da hierbei ein schneller Zugriff essentiell ist.

2.2.4 Huffmann-B¨ aume Huffmann-B¨ aume Die Idee, die sich hinter den Huffmann-B¨aumen versteckt ist die, dass die Darstellung von Daten anhand von 0/1-Folgen geschieht11 . So ist der ASCII-Code zum Beispiel derart codiert, dass ein Zeichen einer Folge von 7 Bits entspricht12 . Eine Nachricht von 10 Zeichen ist somit in 70 Bits codiert. Bei einem Code f¨ ur n verschiedene Zeichen sind log2 (n) Bits pro Symbol n¨ otig. Nehmen wir also zum Beispiel eine Nachricht, die aus nur 8 Zeichen besteht (A,B,C,D,E,F,G,H). Da log2 (8) = 3 brauchen wir bei einem Code fester L¨ ange genau 18 Bits: A = 000 B = 001 C = 010 D = 011 E = 100 F = 101 G = 110 H = 111 ⇒ ABAFBA ⇒ 000 001 000 101 001 000 Der Nachteil bei dieser Darstellung ist, dass jedes Zeichen gleich viel Bits ben¨otigt, unabh¨ angig davon, wie h¨ aufig es vorkommt. Eine k¨ urzere Darstellung g¨abe es also, wenn jedes Zeichen unterschiedlich viel Bits ben¨otigt. Ein Code variabler L¨ange also. Dann k¨onnten wir auf 13 Bits reduzieren: A=0 B = 100 C = 1010 D = 1011 E = 1100 F = 1101 G = 1110 H = 1111

11 12

Also durch Bitfolgen Damit ergeben sich 128 verschiedene Zeichen im ASCII-Standardzeichensatz

2.2 Hierarchische Datenstrukturen ⇒ ABAFBA ⇒ 0 100 0 1101 100 0 Die Frage, die man sich nat¨ urlich stellt ist die, woher man weiß, wo das n¨achste Zeichen anf¨angt. Zu diesem Zweck gibt es den sogenannten Pr¨afixcode: Kein Code f¨ ur ein Symbol ist Pr¨ afix eines anderen Codes. Die Konstruktion eines solchen Codes entspricht dann der sogenannten Huffmann-Codierung. Idee: • Code als Bin¨ arbaum • Bl¨atter einzelner Zeichen mit Gewichtung13 • Innerer Knoten: Zeichenmengen (Vereinigung der Sohnknoten) + Gewichtung Codierung: • Beide S¨ ohne mit 0/1 beschriften • Code f¨ ur ein Zeichen: Folge der Beschreibung von Wurzel bis zum Blatt Decodierung: • Folge den Bits von der Wurzel hinunter • Wenn das Blatt erreicht wurde ist das Zeichen gefunden Konstruktion: • Anfangs: Nur Bl¨ atter mit Gewichtungen • Schritt: Suche zwei Teilb¨ aume mit den geringsten Gewichtungen und vereinige diese dann • Ende: Nur noch ein Baum vorhanden Im Endeffekt sieht der Code folgendermaßen aus: 1

; D a r s t e l l u n g von B l a e t t e r n

2 3

( d e f i n e − s t r u c t b l a t t ( symbol wichtung ) )

4 5

; D a r s t e l l u n g von Knoten

6 7

( d e f i n e − s t r u c t baum ( symbole wichtung l i n k s r e c h t s ) )

8 9 10 11

( d e f i n e ( konstr−code−baum l i n k s r e c h t s ) (make−baum ( append ( symbole l i n k s ) ( symbole r e c h t s ) ) (+ ( wichtung l i n k s ) ( wichtung r e c h t s ) ) 13

H¨ aufigkeit

2 Abstraktion mit Daten links rechts ))

12 13 14 15 16 17

( d e f i n e ( symbole baum) ( i f ( b l a t t ? baum) ( l i s t ( blatt−symbol baum ) ) ( baum−symbole baum ) ) )

18 19 20 21 22

( d e f i n e ( wichtung baum) ( i f ( b l a t t ? baum) ( b l a t t − w i c h t u n g baum) ( baum−wichtung baum ) ) )

23 24

; De codi ere n von N a c h r i c h t e n

25 26 27

( d e f i n e ( d e c o d i e r e b i t s baum) ( d e c o d i e r e − 1 b i t s baum baum ) )

28 29 30 31 32 33 34 35

( d e f i n e ( d e c o d i e r e − 1 b i t s baum a k t u e l l e r − a s t ) ( i f ( empty ? b i t s ) empty ( d e c o d i e r e − n a e c h s t e n − a s t ( r es t b i t s ) baum ( waehle−ast ( f i r s t b i t s ) aktueller−ast ))))

36 37 38 39 40 41

( d e f i n e ( d e c o d i e r e − n a e c h s t e n − a s t r e s t b i t s baum n a e c h s t e r − a s t ) ( i f ( blatt ? naechster−ast ) ( cons ( blatt−symbol n a e c h s t e r − a s t ) ( d e c o d i e r e − 1 r e s t b i t s baum baum ) ) ( d e c o d i e r e − 1 r e s t b i t s baum n a e c h s t e r − a s t ) ) )

42 43 44 45 46

( d e f i n e ( waehle−ast bit a s t ) ( cond ((= bit 0 ) ( baum−links a s t ) ) ((= bit 1 ) ( baum−rechts a s t ) ) ( e l s e ( error ’ waehle−ast ” f a l s c h e s B i t ” ) ) ) )

47 48

; Generierung von Huffman−Baeumen

49 50

; E i n f u e g e n i n g e o r d n e t e Menge von g e w i c h t e t e n Elementen

51 52 53 54 55

( d e f i n e ( hinzufuegen−menge x menge ) ( cond ( ( empty ? menge ) ( l i s t x ) ) ((< ( wichtung x ) ( wichtung ( f i r s t menge ) ) ) ( cons x menge ) )

2.3 Abstraktion mit Prozeduren h¨oherer Ordnung 56 57

( e l s e ( cons ( f i r s t menge ) ( hinzufuegen−menge x ( r es t menge ) ) ) ) ) )

58 59

; D a r s t e l l u n g von Symbol−Haeufigkeit−Paaren

60 61

( d e f i n e − s t r u c t sh ( symbol h a e u f i g k e i t ) )

62 63 64

; T r a n s f o r m i e r e e i n e L i s t e von Symbol−Haeufigkeit−Paaren ; i n e i n e g e w i c h t e t e Menge von B l a e t t e r n

65 66 67 68 69 70 71 72

( d e f i n e ( konstr−blatt−menge sh−paare ) ( i f ( empty ? sh−paare ) empty ( hinzufuegen−menge ( make−blatt ( sh−symbol ( f i r s t sh−paare ) ) ( s h − h a e u f i g k e i t ( f i r s t sh−paare ) ) ) ( konstr−blatt−menge ( r es t sh−paare ) ) ) ) )

2.3 Abstraktion mit Prozeduren h¨ oherer Ordnung 2.3.1 Prozeduren h¨ oherer Ordnung Bisher haben wir als Prozedurparameter unter SCHEME lediglich Zahlen, Symbole und Strukturen zugelassen. Nun werden wir im Folgenden kennenlernen, dass wir auch Prozeduren als Parameter u onnen. Die Motivation dabei ist, dass man h¨aufig auf ¨bergeben k¨ Prozeduren mit ¨ ahnlichem Schema st¨ oßt. Bei der Wartung des Programmes ist es daher unn¨otig kompliziert, wenn man jede Prozedur einzeln bearbeiten muss. Nehmen wir als Beispiel, dass wir alle ganzen Zahlen zwischen a und b zusammenrechnen wollen. 1 2 3 4

( d e f i n e ( ganz−summe a b ) ( i f (> a b ) 0 (+ a ( ganz−summe (+ a 1 ) b ) ) ) ) Nun m¨ochten wir eine Prozedur implementieren, welche die Quadratzahlen zwischen a und b zusammenrechnet.

1 2 3 4

( d e f i n e (qu−summe a b ) ( i f (> a b ) 0 (+ ( quadrat a ) (qu−summe (+ a 1 ) b ) ) ) )

2 Abstraktion mit Daten Nun m¨ ochten wir eine Reihe zusammenrechnen, welche eine N¨aherung f¨ ur π darstellt. Dazu betrachtet man die Reihe: π 1 1 1 = + + + ... 8 1 · 3 5 · 7 9 · 11 1 2 3 4

( d e f i n e ( pi−summe a b ) ( i f (> a b ) 0 (+ ( / 1 ( ∗ a (+ a 2 ) ) ) ( pi−summe (+ a 4 ) b ) ) ) ) Das allgemeine Schema der drei Prozeduren ist das Gleiche:

1 2 3 4

( d e f i n e (summe fun n a e c h s t a b ) ( i f (> a b ) 0 (+ ( fun a ) (summe fun n a e c h s t ( n a e c h s t a ) b ) ) ) ) Wir u ¨bergeben hier also die Berechnungsvorschriften, die Prozeduren, als Parameter. Vereinfacht sieht das dann folgendermaßen aus:

1 2

( d e f i n e ( i n c x ) (+ x 1 ) ) ( d e f i n e (qu−summe a b ) (summe quadrat i n c a b ) )

3 4 5 6

( d e f i n e ( pi−fun x ) ( / 1 ( ∗ x (+ x 2 ) ) ) ) ( d e f i n e ( p l u s 4 x ) (+ x 4 ) ) ( d e f i n e ( pi−summe a b ) (summe pi−fun p l u s 4 a b ) ) Der Nachteil ist, dass die Anwendung etwas umst¨andlich ist. So mussten etwa f¨ ur die Berechnungsvorschriften extra noch Prozeduren erstellt werden, die so sonst nicht mehr im Programm genutzt werden. Besser w¨are es also anonyome14 Funktionen zu verwenden. Dazu f¨ uhren wir die neue Sonderform lambda ein. Diese wird dann wie folgt eingesetzt:

1 2 3 4 5

( d e f i n e ( pi−summe a b ) (summe ( lambda ( x ) ( / 1 ( ∗ x (+ x 2 ) ) ) ) ( lambda ( x ) (+ x 4 ) ) a b)) Ein Lambda-Ausdruck ist einfach gesagt ein Ausdruck mit dem Wert Prozedur, allerdings ohne einen Namen. Tats¨achlich ist der Ausdruck (define (plus4 x) (+ x 4)) identisch zu (define plus4 (lambda (x) (+ x 4))). Lambda kann immer dort verwendet werden, wo Prozeduren erwartet werden. Pragmatisch kann Lambda dann benutzt werden, wenn die Prozedur nicht rekursiv und wirklich nur an einer Stelle ben¨otigt wird. Geschichtlich gesehen ist der Befehl verwurzelt im λ-Kalk¨ ul15 . 14 15

Namenlose Church, 1941

2.3 Abstraktion mit Prozeduren h¨oherer Ordnung

2.3.2 Lokale Definitionen Gelegentlich kommt man in die Situation, dass man bestimmte Prozeduren o.¨a. nicht global sichtbar haben m¨ ochte, sondern einfach nur lokal. Zum Beispiel in einer anderen Prozedur, die so komplex ist, dass man sie in einige Teilprobleme zerlegen m¨ochte. Zu diesem Zweck gibt es die Sonderform local: (local (Def1 Def2 ... Defn) Ausdruck) Die Definitionen sind lediglich innerhalb dieser local-Struktur sichtbar. Sehen wir uns den folgenden Code an, so wird klar, dass die beiden Prozeduren g und f außerhalb der local-Umgebung faktisch nicht sichtbar sind. 1 2 3

( l o c a l ( ( d e f i n e ( f x ) (+ x 2 ) ) ( d e f i n e ( g y ) (∗ ( f y ) 4 ) ) ) (g 3)) Der Bereich, in dem die Prozedur bzw. allgemein ein Name genutzt werden kann, nennt man G¨ ultigkeitsbereich, Geltungsbereich oder auch Ausdrucksmenge. Der Geltungsbereich von y beschr¨ ankt sich im folgenden Code einzig und alleine auf den Rumpf der Prozedur g.

1 2 3

( define ( f x) ( l o c a l ( ( d e f i n e ( g y ) ) ) ...)) Der Geltungsbereich von g und x ist der gesamte Rumpf von f, der einzig und alleine aus der local-Umgebung besteht.

2.3.3 Lexikalische (statische) Bindung Die lexikalische Bindung, wie sie in den meisten modernen (h¨oheren) Programmiersprachen eingesetzt wird, bedeutet nichts anderes, als dass sich Namen stets auf den n¨achsten umfassenden Block beziehen, in dem sie deklariert sind. Das bedeutet, man kann gleiche Namen anwenden, die sich jedoch auf unterschiedliche Objekte beziehen. Dabei gilt dass lokale Definitionen die globalen Definitionen u ¨berschatten beziehungsweise u ¨berdecken. 1 2 3 4 5

( define ( f x) ( local (( define (g x) x)) ; ; x)) ; ;

Das x i n sich auf Dieses x x von ( f

dieser Zeile bezieht das x von ( g x ) b e z i e h t s i c h a u f das x)

Hier sieht man, dass es sich bei den beiden x um unterschiedliche Objekte handelt, die jedoch beide den gleichen Namen haben k¨onnen. Wozu braucht man diese M¨oglichkeit nun aber eigentlich? Sie ist n¨ utzlich zur Vermeidung des Durchreichens von globalen Parametern16 . Nehmen wir als Beispiel die Prozedur zur Berechnung der Summe 16

Dies hatten wir zum Beispiel auch bei der Berechnung der Wurzel nach Newton, bei der auch der unver¨ anderte Wert stets an die Funktion selbst wieder u ¨bergeben wurde

2 Abstraktion mit Daten in einem Intervall. Die Prozedur hatten wir bereits insoweit verbessert, als dass wir lediglich noch eine Prozedur hatten, der die notwendigen Prozeduren zur Berechnung als Parameter u ¨bergeben wurden. Das Problem mit dem Durchreichen besteht auch hier. Die Berechnungsvorschriften werden der Prozedur jedesmal wieder selbst u ¨bergeben, ob17 wohl sich diese gar nicht ¨ andern . Das wollen wir nun mithilfe von lokalen Definitionen abstellen. 1 2 3 4 5 6

( d e f i n e (summe fun n a e c h s t a b ) ( l o c a l ( ( d e f i n e ( summiere x ) ( i f (> x b ) 0 (+ ( fun x ) ( summiere ( n a e c h s t x ) ) ) ) ) ) ( summiere a ) ) ) Pragmatisch wird local eigentlich immer dann benutzt, wenn Hilfsfunktionen notwendig sind, die zwar f¨ ur das spezifische Problem relevant sind, jedoch nicht f¨ ur das globale. Prozeduren h¨ oherer Ordnung sind meist dann n¨ utzlich, wenn eine universelle Verarbeitung von Datenstrukturen notwendig ist. Schauen wir uns als Beispiel die Transformation einer Liste durch Anwendung einer Funktion auf alle Elemente an.

Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (map-list quadrat (list 1 2 3 4)) (list 1 4 9 16) Die Implementierung dieser Prozedur ist mit unserem Wissen relativ simpel: 1 2 3 4

( d e f i n e ( map−list f l ) ( i f ( empty ? l ) empty ( cons ( f ( f i r s t l ) ) ( map−list f ( r es t l ) ) ) ) ) Universelle Berechnungsverfahren werden auch oft f¨ ur die Mathematik ben¨otigt. Nehme man zum Beispiel die Nullstellenbestimmung oder das Differenzieren f¨ ur beliebige Funktionen. Nun wollen wir die Nullstellenbestimmung durch Intervallhalbierung implementieren. Gegeben sei eine Funktion f , die Punkte a, b mit f (a) < 0 < f (b). Gesucht sei die Nullstelle von f , d.h. x mit f (x) = 0 und a < x < b. Die Idee dazu ist, dass x der Mittelwert von a und b ist. Wir nehmen also an, dass sich im Intervall ]a, b[ eine Nullstelle befindet. 17

Genaugenommen werden fun, naechst und b immer unver¨ andert u ¨bernommen.

2.3 Abstraktion mit Prozeduren h¨oherer Ordnung Falls f (x) > 0 gilt, befindet sich die Nullstelle zwischen a und x. Falls f (x) < 0 gilt, befindet sich die Nullstelle zwischen b und x. Falls f (x) = 0 gilt, befindet sich die Nullstelle bei x. Generell wird also das Suchintervall in jedem Schritt bis zu einer gegebenen Grenze halbiert (es sei denn, das Ziel wird vorher erreicht). Nehmen wir an, dass das Intervall ]a, b[ verdoppelt wird. Dann ben¨ otigen wir genau einen Schritt mehr, da nach einem Schritt bereits das Intervall wieder halbiert ist. Wir ]a, b[ vervierfacht, so ben¨otigen wir genau zwei Schritte mehr. Wir haben es also mit einer logarithmischen Laufzeit zu tun. |b−a| Genau genommen ist die Laufzeit O(log T mit T als Toleranz18 . 1 2 3 4 5 6 7 8 9 10

( d e f i n e ( suche f a b) ( local (( define x ( mittelwert a b ))) ( i f ( nah−genug ? a b ) x ( l o c a l (( define fx ( f x )) ) ( cond ( ( p o s i t i v e ? f x ) ( suche f a x ) ) (( negative ? fx ) ( suche f x b ) ) ( else x))))))

11 12 13

( define ( mittelwert a b) ( / (+ a b ) 2 ) )

14 15 16 17

( d e f i n e ( nah−genug ? x y ) (< ( abs (− x y ) ) 0.001))

18 19

; Benutzerschnittstelle

20 21 22 23 24 25 26 27 28 29

( define ( intervall−halbierung f a b) ( local (( define fa ( f a )) ( define fb ( f b ) ) ) ( cond ( ( and ( n e g a t i v e ? f a ) ( p o s i t i v e ? f b ) ) ( suche f a b ) ) ( ( and ( n e g a t i v e ? f b ) ( p o s i t i v e ? f a ) ) ( suche f b a ) ) ( e l s e ( error ’ i n t e r v a l l − h a l b i e r u n g ” Werte haben g l e i c h e s V o r z e i c h e n ” ) ) ) ) )

Genauigkeit

2 Abstraktion mit Daten

2.3.4 Prozeduren als Ergebnis Unter Umst¨ anden m¨ ochte man auch einmal Prozeduren nicht nur als Argumente zulassen, sondern auch Prozeduren als Ergebnis zur¨ uck liefern. Nehmen wir zum Beispiel das Differenzieren von Funktionen19 . Das Argument ist dabei eine Funktion (f (x)), ebenso das Ergebnis (f 0 (x)). Nummerisch berechnet sich die Ableitung folgendermaßen: (x) (x) df (x) = f (x+∆x)−f = f (x+dx)−f , wobei dx m¨oglichst klein sein sollte. ∆x dx 1 2 3 4

( d e f i n e ( a b l e i t u n g f dx ) ( lambda ( x ) ( / (− ( f (+ x dx ) ) ( f x)) dx ) ) ) Wie man sehen kann, nutzen wir hier wieder das bereits bekannte Λ, um eine Prozedur als Ergebnis zur¨ uckzuliefern. Anzumerken sei, dass der Ergebnistyp tats¨achlich als Wert eine Prozedur ist. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > ((ableitung quadrat 0.0001) 4) 8.001 Funktionskomposition (f ◦ g)(x) = f (g(x))

1 2

( d e f i n e ( komp f g ) ( lambda ( x ) ( f ( g x ) ) ) ) Auch diese Prozedur liefert nun eine Prozedur zur¨ uck. In diesem Fall eine Funktion, die eine Komposition aus zwei Funktionen bildet. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > ((komp quadrat quadrat) 4) 256 > ((ableitung (komp quadrat quadrat) 0.001) 3) 108.054 Dadurch, dass wir Prozeduren als Ergebnisse zur¨ uckliefern k¨onnen, stehen uns sogar noch ganz andere Tore offen. Mit Λ ist es tats¨achlich m¨oglich, beinahe alles zu implementieren. W¨ are es nicht sch¨on, wenn wir unsere eigene Listenimplementierung h¨atten? Auch das ist m¨ oglich. 19

Hier beziehen wir uns auf das nummerische Differenzieren. Nicht auf das symbolische, welches wir bereits behandelt hatten

2.3 Abstraktion mit Prozeduren h¨oherer Ordnung

1 2 3 4

( d e f i n e ( cons x y ) ( lambda (m) ( cond ((= m 0 ) x ) ((= m 1 ) y ) ( e l s e error ’ cons ” F a l s c h e r Wert” ) ) ) )

5 6 7

( define ( first l ) ( l 0)) ( d e f i n e ( res t l ) ( l 1 ) ) ¨ Eine n¨ahere Uberpr¨ ufung dieser Prozeduren zeigt, dass unsere Listenimplementierung s¨amtliche ADT-Gesetze erf¨ ullt. Und sie steht der urspr¨ unglichen Implementierung in Nichts nach. Wir wissen bereits, dass wir Datenabstraktionen zum einen dazu nutzen, um die Implementierung zu sch¨ utzen und außerdem um die Implementierung austauschbar zu halten. So wird oftmals zun¨ achst ein Prototyp einer Implementierung genutzt, der dann sp¨ater durch eine effizientere Implementierung ersetzt wird. Allerdings haben wir auch bereits kennengelernt, dass die Effizient stark von den konkreten Daten und den Operatoren abh¨angt20 . Nun m¨ ochten wir im Folgenden die M¨oglichkeit vorstellen, dass wir mehrere Implementierungen gleichzeitig nutzen. Dazu ziehen wir als Beispiel die komplexen Zahlen heran. Wie wir wissen, bestehen sie aus einem Real- und einem Imagin¨ arteil. Tats¨achlich lassen sich komplexe Zahlen aber auch anders darstellen und zwar in Polarkoordinaten. Dabei bestehen sie aus dem Betrag21 und einem Winkel22 . • Rechteckkoordinaten: (x, y)23 Addition mit Rechteckkoordinaten: (x1 , y1 ) + (x2 , y2 ) = (x1 + x2 , y1 + y2 ) • Polarkoordinaten: (a, φ)24 Multplikation mit Polarkoordinaten: (a1 , φ1 ) + (a2 , φ2 ) = (a1 · a2 , φ1 + φ2 ) Zur Implementierung sei jetzt angenommen, dass wir bereits konstr-rechteck, konstrpolar, real-teil, im-teil, abs-wert, winkel zur Verf¨ ugung haben.

1 2 3 4 5

( d e f i n e ( ∗ c z1 z2 ) ( k o n s t r − p o l a r ( ∗ ( abs−wert z1 ) z1 ) (+ ( w i n k e l z1 ) ( w i n k e l z2 ) ) ) ) 20

Vergleiche hier auch die Implementierung der Mengen Die Entfernung zum Mittelpunkt 22 Womit sie dann eindeutig definiert sind 23 Gut f¨ ur +, − 24 Gut f¨ ur ∗, / 21

2 Abstraktion mit Daten 6 7 8 9 10 11

( d e f i n e (+c z1 z2 ) ( k o n s t r − r e c h t e c k (+ ( r e a l − t e i l z1 ) ( r e a l − t e i l z2 ) ) (+ ( i m − t e i l z1 ) ( i m − t e i l z2 ) ) ) ) Die Zusammenh¨ ange bei der Darstellung (x, y)=(a, ˆ φ) sind u ¨brigens folgende: x = a · cos φ y = a · sin φ p a = x2 + y 2 y φ = arctan + richtiger Quadrant x Nun wollen wir uns daran machen, die beiden Darstellungen tats¨achlich zu implementieren, indem wir uns die Zusammenh¨ange zu Nutze machen. Dabei verwenden wir im ¨ Ubrigen eine Tangensfunktion, welche zwei Parameter mitbekommt und anhand dessen entscheidet, welcher Quadrant der Richtige ist.

1 2

; I m p l e m e n t i e r u n g mit R e c h t e c k d a r s t e l l u n g ( d e f i n e − s t r u c t r e c h t ( r e a l im ) )

3 4 5

( define ( konstr−rechteck x y) ( make−recht x y ) )

6 7 8

( define ( real−teil−recht z ) ( recht−real z ))

9 10 11

( d e f i n e ( im−teil−recht z ) ( recht−im z ) )

12 13 14 15

( d e f i n e ( abs−wert−recht z ) ( w u r z e l (+ ( quadrat ( r e c h t − r e a l z ) ) ( quadrat ( recht−im z ) ) ) ) )

16 17 18 19

( d e f i n e ( winkel−recht z ) ( atan ( recht−im z ) ( recht−real z )))

20 21 22 23

( d e f i n e ( k o n s t r − p o l a r − r e c h t a w) ( make−recht ( ∗ a ( cos w) ) ( ∗ a ( sin w ) ) ) )

2.3 Abstraktion mit Prozeduren h¨oherer Ordnung 25 26

; I m p l e m e n t i e r u n g mit P o l a r d a r s t e l l u n g ( d e f i n e − s t r u c t p o l ( abs p h i ) )

27 28 29

( d e f i n e ( k o s t r − p o l a r a w) ( make−pol a w) )

30 31 32

( d e f i n e ( abs−wert−pol z ) ( pol−abs z ) )

33 34 35

( d e f i n e ( winkel−pol z ) ( pol−phi z ) )

36 37 38 39

( define ( real−teil−pol z ) ( ∗ ( pol−abs z ) ( cos ( pol−phi z ) ) ) )

40 41 42 43

( d e f i n e ( im−teil−pol z ) ( ∗ ( pol−abs z ) ( sin ( pol−phi z ) ) ) )

44 45 46 47 48

( d e f i n e ( konstr−rechteck−pol x y ) ( make−pol ( w u r z e l (+ ( quadrat x ) ( quadrat y ) ) ) ( atan y x ) ) ) Jetzt k¨onnen die vier Rechenoperationen problemlos unabh¨angig von der internen Darstellung ausgef¨ uhrt werden. Es kann nun mit beiden Darstellungen gleichzeitig gearbeitet werden. Das Problem ist, dass die Selektoren nun wissen m¨ ussen, welche von beiden Darstellungen vorliegt. Die sogenannten Datenobjekte mit manifestem Typ, mit denen wir arbeiten, enthalten jedoch schon Informationen u ¨ber den Typ der Repr¨asentation. Aufgrund der Struktur, die wir benutzen, verf¨ ugen wir ja schon u ¨ber die notwendigen Pr¨adikate (recht?, polar?). Nun m¨ ussen wir die Selektoren nun nur noch mit einem generischen Verhalten ausstatten25 .

1 2 3

( define ( real−teil z) ( cond ( ( r e c h t ? z ) ( r e a l − t e i l − r e c h t z ) ) (( pol ? z ) ( real−teil−pol z ) ) ) ) Diese Prozedur ist nun also in der Lage als Selektor zu fungieren und trotzdem gleichzeitig das richtige Objekt je nach ADT zur¨ uckzuliefern. Die Fallunterscheidungen werden analog in den anderen Selektoren eingebaut. Das ist eine ganz praktische L¨ osung, hat aber einen entscheidenden Nachteil. Wenn nun 25

Das bedeutet nichts anderes, als dass die Selektoren in der Lage sind, mit verschiedenen Typen umzugehen.

2 Abstraktion mit Daten zum Beispiel eine neue Darstellung hinzugef¨ ugt werden soll, m¨ ussen s¨amtliche generischen Operatoren ge¨ andert werden. Eine L¨osung w¨are es, wenn nicht die Prozeduren entscheiden, wie die Daten bearbeitet werden, sondern wenn die Daten dies selbst entscheiden - dies nennt man eine Datengesteuerte Programmierung. Notwendig w¨are dazu eine Zuordnung (Darstellungstypen → Bearbeitungsprozeduren). Typ/Operator real-teil ...

Rechteck real-teil-recht ...

Polar real-teil-pol ...

Hierzu werden die Typinformationen in ein Symbol umgewandelt und in eine Tabelle eingetragen26 . 1 2 3 4

( d e f i n e ( typ z ) ( cond ( ( r e c h t ? z ) ’ r e c h t ) (( polar ? z ) ’ polar ) ( e l s e ( error ’ typ ” Unbekannte D a r s t e l l u n g ” ) ) ) ) Wollen wir weitere Typen hinzuf¨ ugen, m¨ ussen wir diese in die Prozedur typ einf¨ ugen. F¨ ur den Aufbau von Tabellen verwenden wir den Befehl (put typ op eintrag) und zum Durchsuchen verwenden wir (get typ op). Letztere Prozedur liefert den Eintrag oder, falls der Eintrag nicht gefunden werden konnte, empty zur¨ uck. Um die Tabelle nun konkret aufzubauen nutzen wir die Befehle (put ’recht ’real-teil real-teil-recht) und (put ’pol ’realteil real-teil-pol). Die restlichen Eintr¨age entstehen nat¨ urlich analog. Wichtig hierbei ist, dass die eigentlichen Tabelleneintr¨age keine Namen sondern tats¨achlich Prozeduren sind. Das Hinzuf¨ ugen einer neuen Darstellung gestaltet sich nun relativ einfach. Das Modul wird implementiert, die typ-Prozedur erweitert und die put-operationen f¨ ur die neue Spalte werden geschrieben. Nun stellt sich nat¨ urlich die Frage, wie die eigentlichen Operationen ausgef¨ uhrt werden. Dazu schreiben wir eine weitere Prozedur:

1 2 3 4 5 6 7 8

( d e f i n e ( op−ausfuehren op o b j ) ( l o c a l ( ( d e f i n e proz ( get ( t y p o b j ) op ) ) ) ( i f ( not ( empty ? p r o z ) ) ( proz obj ) ( error ’ op−ausfuehren ” Operator i s t f u ¨ r den Typ u n d e f i n i e r t ” ) ) ) )

9 10 11

( d e f i n e ( r e a l − t e i l obj ) ( op−ausfuehren ’ r e a l − t e i l o b j ) ) Die weiteren generischen Operatoren (die nun im u ¨brigen typunabh¨angig arbeiten) werden wie u ¨blich analog implementiert. 26

Wie sich dies bewerkstelligen l¨ asst wird sp¨ ater noch gezeigt. F¨ ur den Moment muss es reichen, dass wir die Prozeduren daf¨ ur einfach verwenden.

2.3 Abstraktion mit Prozeduren h¨oherer Ordnung Das allgemeine Prinzip hierbei ist, dass zun¨achst eine Typpr¨ ufung gemacht wird und anschließend die dazu passende Prozedur aufgerufen wird. Dies nennt man auch dispatching on type. Hier: Intelligente Operatoren → Eine Zeile in der Tabelle Alternativ: Intelligente Datenobjekte → Eine Spalte in der Tabelle ⇒ Technik: Nachrichtenweitergabe. Dies bedeutet, dass das Datenobjekt selbst die Zuordnung von Operator zur Implementierung enth¨alt. Dies machen wir nun am Beispiel von Rechteckobjekten:

1 2 3 4 5 6 7 8 9 10 11 12

( define ( konstr−rechteck x y) ( l o ca l (( define ( zuteilen n) ( cond ( ( eq? n ’ r e a l − t e i l ) x ) ( ( eq? n ’ i m − t e i l ) y ) ( ( eq? n ’ abs−wert ) ( w u r z e l (+ ( quadrat x ) ( quadrat y ) ) ) ) ( ( eq? n ’ w i n k e l ) ( atan y x ) ) ( e l s e ( error ’ k o n s t r − r e c h t e c k ” Unbekannte O p e r a t i o n ” ) ) ) ) ) zuteilen ))

13 14 15

; Zum Ausf¨ u hren e i n e r O p e r a t i o n : ( d e f i n e ( op−ausfuehren op o b j ) ( o b j op ) )

Diese Programmiertechnik der Nachrichtenweitergabe, auch message passing genannt hat die Vorteile der Modularit¨ at. Dass die Datenobjekte selbst Implementierungsinformationen enthalten ist die Basis der objektorientierten Programmierung.

2.3.5 Komplexe Typdeklaration Wir wollen nun im Folgenden ein generisches Arithmetikmodul erstellen, also Operatoren f¨ ur Zahlen aller Art bereitstellen27 . Unsere gew¨ unschte Zielstruktur sieht etwa folgendermaßen aus:

Reelle Zahlen, rationale Zahlen, komplexe Zahlen. . .

2 Abstraktion mit Daten

Die Realisierung des Moduls geschieht ¨ahnlich wie bei der Mehrfachdarstellung mit Tabellen, indem die Unterscheidung u ¨ber die Datentypen gemacht wird. Zun¨achst wird aber das Zahl-Modul implementiert: 1

( d e f i n e − s t r u c t z a h l ( wert ) )

2 3 4

( d e f i n e ( konstr−zahl z ) ( make−zahl z ) )

5 6 7

( d e f i n e ( zwert z ) ( zahl−wert z ) )

8 9 10 11

( d e f i n e (+ z a h l z1 z2 ) ( k o n s t r − z a h l (+ ( z w e r t z1 ) ( z w e r t z2 ) ) ) ) Die weiteren Operatoren werden - nat¨ urlich - analog implementiert. Man sieht, dass es eigentlich unn¨ otig aufw¨ andig ist, eine Zahl ebenfalls als ADT zu implementieren, dies ist jedoch notwendig, um die Typ-Prozedur um den Typ zu erweitern:

1 2 3 4 5

( d e f i n e ( typ z ) ( cond ( ( r e c h t ? z ) ’ r e c h t ) (( polar ? z ) ’ polar ) (( zahl ? z ) ’ zahl ) ( e l s e ( error ’ typ ” Unbekannte D a r s t e l l u n g ” ) ) ) ) Die Befehle (put ’zahl ’add +zahl) etc. m¨ ussen nat¨ urlich ebenfalls wieder genutzt werden. Allgemein ergibt sich damit f¨ ur die Operatoren folgende Struktur:

( d e f i n e ( add x y )

2.3 Abstraktion mit Prozeduren h¨oherer Ordnung 2

( op−ausfuehren2 ’ add x y ) )

3 4 5 6 7 8 9 10

( d e f i n e ( op−ausfuehren2 op a1 a2 ) ( i f ( eq? ( typ a1 ) ( typ a2 ) ) ( l o c a l ( ( d e f i n e ( p r o z ( get ( typ a1 ) op ) ) ) ( i f ( not ( empty ? p r o z ) ) ( p r o z a1 a2 ) ( error ’ op−ausfuehren2 ” U n d e f i n i e r t e O p e r a t i o n ” ) ) ) ) ( error ’ op−ausfuehren2 ” U n g l e i c h e Typen” ) ) ) Um das Modul f¨ ur die komplexen Zahlen nun zum generischen Arithmetikmodul hinzuzuf¨ ugen, werden die komplexen Zahlen in eine neue Struktur gepackt.

( d e f i n e − s t r u c t komplex ( wert ) )

2 3

( d e f i n e ( konstr−komplex z ) ( make−komplex z ) )

4 5

( d e f i n e ( kwert z ) ( komplex−wert z ) )

6 7 8 9

( d e f i n e (+komplex z1 z2 ) ( konstr−komplex (+C ( kwert z1 ) ( kwert z2 ) ) ) ) Analog werden die anderen Operationen implementiert. Nun muss erneut der putBefehl genutzt werden, um die einzelnen Operationen der Tabelle hinzuzuf¨ ugen. Außerdem muss die Typ-Prozedur um den neuen Komplex-Typ erweitert werden. Auff¨alliges ist, dass wir jetzt ein 2-stufiges Typsystem hier haben. Wenn wir eine komplexe Zahl in Rechteckkoordinaten erstellen m¨ochten, nutzen wir den Befehl (konstrkomplex (konstr-rechteck 3 4)). Auf dem Weg nach unten zur Implementierung werden die Strukturen sozusagen abgestreift. Nun m¨ochten wir Operanden mit unterschiedlichem Typ bei den Operationen zulassen. Bisher erzeugte das Addieren einer Zahl und einer komplexen Zahl einen Fehler, obwohl das nicht sinnvoll ist, da sehr wohl eine Beziehung zwischen den Datentypen herrscht. Eine m¨ ogliche L¨ osung w¨ are mit Sicherheit, dass wir Operatoren f¨ ur die gemischten Operanden erstellen, also eine dreidimensionale Tabelle erzeugen, sodass wir eine Abbildung T yp×T yp×Operator → P rozedur haben. Der Nachteil dabei w¨are, dass wir bei n verschiedenen Typen im Extremfall genau n2 Versionen einer jeden Operation implementieren m¨ ussten. Eine bessere L¨ osung w¨are wohl eine Typanpassung, sodass erst versucht wird, einen Typ in einen anderen umzuwandeln. Nehmen wir als Beispiel eine Typumwandlung von Zahlen in komplexe Zahlen.

1 2

( d e f i n e ( zahl−>komplex x ) ( konstr−komplex ( k o n s t r − r e c h t e c k ( z w e r t x ) 0 ) ) )

3 4

( put−typanpassung ’ z a h l ’ komplex zahl−>komplex )

2 Abstraktion mit Daten 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

( d e f i n e ( op−ausfuehren2 op a1 a2 ) ( l o c a l ( ( d e f i n e t 1 ( typ a1 ) ( d e f i n e t 2 ( typ a2 ) ) ) ( i f ( eq? t 1 t 2 ) ( l o c a l ( ( d e f i n e p r o z ( get t 1 op ) ) ) ( i f ( not ( empty ? p r o z ) ) ( p r o z a1 a2 ) ( error ’ op−ausfuehren2 ” U n g u ¨ l t i g e Prozedur ” ) ) ) ( l o c a l ( ( d e f i n e t1−>t 2 ( get−typanpassung t 1 t 2 ) ) ( d e f i n e t2−>t 1 ( get−typanpassung t 2 t 1 ) ) ) ( cond ( ( not ( empty ? ( t1−>t 2 ) ) ) ( op−ausfuehrn2 op t1−>t 2 a1 ) a2 ) ( ( not ( empty ? ( t2−>t 1 ) ) ) ( op−ausfuehren op a1 ( t2−>t 1 a2 ) ) ) ( e l s e ( error ’ op−ausfuehren2 ” U n g u ¨ l t i g e Typen” ) ) )))))) Der Vorteil bei dieser Implementierung ist, dass wir bei n Typen nur n Versionen jedes Operators ben¨ otigen. Allerdings ben¨otigen wir bis zu n2 Anpassungsprozeduren. Vorstellbar w¨ are auch, dass wir Objekte mit Typen t1 und t2 haben, wobei aber weder t1→t2 noch t2→t1 existiert, aber ein gemeinsamer Typ mit t1-¿t3 und t2-¿t3. Bei der sogenannten Typhierarchie gibt es zum Beispiel zwei Typen t1 und t2, wobei t1 ein Untertyp von t2 ist,was bedeutet, dass jedes t1-Objekt auch ein t2-Objekt ist. Außerdem ist jede auf t2-Objekte anwendbare Operation auch auf t1-Objekte anwendbar. Das t1-Konzept ist somit ein Spezialfall vom t2-Konzept. Diese Typhierarchie haben wir eigentlich schon bei unseren Zahlen. ganze Zahlen → rationale Zahlen → reelle Zahlen → komplexe Zahlen. W¨ urden wir nun eine Typanpassung von ganzen Zahlen zu komplexen Zahlen vornehmen wollen, br¨auchten wir uns eigentlich nur schrittweise entlang hangeln und f¨ ur jeden Typ eine Prozedur zur Umwandlung in den Obertypen vornehmen. Die ¨ Anderung in op-ausfuehren2 w¨are dann, dass wir schrittweise den niedrigen Typ erh¨ ohen bis beide Typgleich sind. Ein weiterer Vorteil w¨are dabei, dass wir eine Vererbung von Operationen h¨ atten.

2.4 Systeme mit generischen Operatoren Komplexe Typdeklaration Um ein Beispiel von komplexer Typdeklaration zu haben, also eine Struktur, bei der Objekte auch von mehreren Objekten erben, betrachten wir geometrische Objekte:

2.5 Exkurs Polygon Dreieck gleichschenkliges Dreieck gleichseitiges Dreieck

rechtwinkliges Dreieck gleichschenkliges, rechtwinkliges Dreieck

Viereck Drachen Parallelogramm

Rhombus

Rechteck Quadrat

Das Problem hierbei ist, dass wir keine eindeutige Typerh¨ohung vornehmen k¨onnten, da mehrere Objekte von mehreren anderen Objekten erben. Auch ist keine eindeutige Erniedrigung des Typ m¨ oglich. Bei Objektorientierten Sprachen ist es daher notwendig, dass man, wenn m¨ oglich, die Operanden auf einen kleinsten gemeinsamen Obertypen erh¨oht. Dazu ist es notwendig m¨ oglichst effizient und schnell im Typgraph danach zu suchen.

2.5 Exkurs 2.5.1 Beweistechniken f¨ ur Programme mit Datenstrukturen F¨ ur einen ADT existieren Gleichungen zwischen den Termen. Wenn diese Gleichungen korrekt sind, ist auch die Implementierung korrekt. Aber wie erbringt man diesen Nachweis? Haben wir Gleichungen mit Variablen, so weisen wir die Gleichungen f¨ ur alle Terme anstelle der Variablen nach. Bei unendlich vielen Termen mit regelm¨aßiger Struktur k¨onnen wir uns der vollst¨ andiger Induktion bedienen. So zum Beispiel bei Listen: empty ist eine Liste. l ist eine Liste und e ein Element, dann ist (cons e l) eine Liste. Bei nat¨ urlichen Zahlen erfolgt ein Beweis durch vollst¨andige Induktion durch mehrere Schritte. Sei p ein Pr¨ adikat (Aussage) u urliche Zahlen. Falls P(0) wahr ist (In¨ber nat¨ duktionsbasis) und falls aus P(n) wahr auch (Pn+1) wahr folgt (Induktionssschritt), dann ist P(n) f¨ ur alle nat¨ urlichen Zahlen n wahr. Analog erfolgt das Beweisprinzip f¨ ur Terme und Datenstrukturen. ur jedes n-stellige Funktionssymbol f /n ∈ PBei der strukturellen Induktion gilt falls f¨ (n ≥ σ) gilt: Falls P(t1 )...P(tn ) wahr, dann ist auch P(f (t1 ...tn )) wahr, dann gilt f¨ ur alle Terme t ∈ TΣ (φ): P(t). Wir zeigen dies nun einmal an einem Beispiel. Nehmen wir an, wir m¨ochten die Korrektheit der folgenden SCHEME-Prozedur zur L¨angenberechnung einer Liste beweisen. 1 2

( d e f i n e ( length l ) ( i f ( empty ? l )

2 Abstraktion mit Daten 0 (+ 1 ( length ( r es t l ) ) ) ) )

3 4

Die Behauptung ist, dass falls l eine Liste mit n Elementen ist (n ≥ 0), dann ergibt (length l)⇒∗ n. F¨ ur die strukturelle Induktion ist wichtig, dass wir die Konstruktoren f¨ ur Listen kennen: empty und cons. F¨ ur den Induktionsanfang setzen wir n =. (length empty) ⇒ (if (empty? empty) 0 (+ 1 (length (rest empty)))) ⇒ (if true 0 (+ 1 (length (rest empty)))) ⇒ 0 Der Induktionsanfang stimmt also. Nun nehmen wir an, dass l = (cons e l’) gilt mit l’ als Liste mit n Elementen (n ≥ 0), d.h. l enth¨alt n+1 Elemente. Die Annahme ist also, dass (length l’) ⇒∗ n. Zu zeigen ist, dass (length l) ⇒∗ n+1. (length l) ⇒ (if (empty? l) 0 (+ 1 (length (rest l))))) ⇒ (if (empty? l) 0 (+ 1 (length (rest (cons e l’))))) ⇒ (if false 0 (+ 1 (length l’))) ⇒ (+ 1 (length l’)) ⇒∗ (+ 1 n) ⇒ n+1 Wir machen ein weiteres Beispiel. Wir wollen die Korrekheit der append-Prozedur zeigen. 1 2 3 4 5 6

( d e f i n e (append l 1 l 2 ) ( i f ( empty ? l 1 ) l2 ( cons ( f i r s t l 1 ) (append ( r es t l 1 ) l2 )))) Die Behauptung ist, falls xs = (list x1...xn) und ys = (list y1...yn), dann gilt (append xs ys) ⇒ ∗ (list x1...xn,y1...yn). Unsere Behauptung bezeichnen wir u ¨brigens als P(xs). F¨ ur den Induktionsanfang setzen wir wieder (n = 0). (append empty ys) ⇒ (if (empty? empty) ys (cons (first empty) (append (rest empty) ys))) ⇒ (if true ys (cons (first empty) (append (rest empty) ys))) ⇒ ys = (list y1...yn) Nun setzen wir xs = (cons x1 xs’), xs’ = (list x2...xn) und ys = (list y1...yn). Unsere Annahme ist (append xs’ ys) ⇒∗ (list x2...xn,y1...yn). Zu zeigen ist (append xs ys) ⇒ ∗ (list x1...xn, y1...yn). (append xs ys) = (append (cons x1 xs’) ys) ⇒ (if (empty? (cons x1 xs’)) ys (cons (first (cons x1 xs’)) (append (rest (cons x1 xs’)) ys))) ⇒ (if false ys (cons (first (cons x1 xs’)) (append (rest (cons x1 xs’)) ys))) ⇒ (cons (first (cons x1 xs’)) (append (rest (cons x1 xs’)) ys)) ⇒ (cons x1 (append xs’ ys)) ⇒∗ (cons x1 (list x2...xn,y1...yn)) ⇒

2.5 Exkurs (list x1...xn,y1...yn) Damit ist auch diese Behauptung f¨ ur alle Listen richtig.

2 Abstraktion mit Daten

3 Modularit¨ at, Objekte, Zust¨ ande 3.1 Zuweisungen und lokale Zust¨ ande Nehmen wir an, wir m¨ ochten eine Software zur Bankkontoverwaltung realisieren. Wir m¨ochten 1000 Euro vom Bankkonto abheben. Nun stellt sich die Frage: Ist dies m¨oglich? Je nachdem wie die Vorgeschichte eben dieses Bankkontos ist, kann dies m¨oglich sein oder auch nicht. Das bedeutet, wir haben zwar denselben Funktionsaufruf haben jedoch unterschiedliche Ausgaben. Dies ist mit unseren bisherigen Mitteln nicht m¨oglich, da wir Namen bisher immer einen festen, unver¨anderbaren Wert zugewiesen haben. Die Sonderform (set! Name NeuerWert) erm¨ oglicht uns, den Wert eines Namens zu ¨andern. Bei der Auswertung von set! wird folgendermaßen vorgegangen: 1. Werte den Ausdruck NeuerWert aus 2. Ver¨anderte den Wert von Name zum ausgerechneten Wert 3. ¡Name¿ muss bereits durch define bekannt sein. 4. Das Ergebnis der Operation selbst ist undefiniert Damit l¨asst sich unser Bankkonto nun realisieren. 1

( d e f i n e kontostand 130)

2 3 4 5 6 7 8

( d e f i n e ( abheben b e t r a g ) ( i f (>= k o n t o s t a n d b e t r a g ) ( begin ( set ! k o n t o s t a n d (− k o n t o s t a n d b e t r a g ) ) kontostand ) ” Deckung u n z u r e i c h e n d ” ) ) Die Sonderform (begin a1 ... an) hatten wir bereits im Rahmen des Programmierpraktikum kennen gelernt. F¨ ur diese Sonderform gilt: 1. Werte nacheinander die Ausdr¨ ucke aus 2. Wert dieser Sonderform ist der Wert von an . Der Nachteil bei dieser L¨ osung ist allerdings, dass der Kontostand global bekannt und somit u anderbar ist. Dazu u ¨berall ver¨ ¨berlegen wir uns folgende L¨osung:

3 Modularit¨at, Objekte, Zust¨ande

1 2 3 4 5 6 7 8

( d e f i n e neu−abheben ( l o c a l ( ( d e f i n e kontostand 130)) ( lambda ( b e t r a g ) ( i f (>= k o n t o s t a n d b e t r a g ) ( begin ( set ! k o n t o s t a n d (− k o n t o s t a n d b e t r a g ) ) kontostand ) ” Deckung u n z u r e i c h e n d ” ) ) ) ) Diese L¨ osung ist besser, aber noch immer nicht ideal. Wir haben einen fixen Anfangskontostand und außerdem nur ein einziges Konto. Eine Verbesserung w¨are mit Sicherheit das Benutzen von Konstruktoren, sowie Abhebungsprozessen f¨ ur beliebige Konten und f¨ ur beliebige Anfangsbetr¨ age.

1 2 3 4 5 6 7 8

( d e f i n e ( konstr−abheben wert ) ( l o c a l ( ( d e f i n e k o n t o s t a n d wert ) ) ( lambda ( b e t r a g ) ( i f (>= k o n t o s t a n d b e t r a g ) ( begin ( set ! k o n t o s t a n d (− k o n t o s t a n d b e t r a g ) ) kontostand ) ” Deckung u n z u r e i c h e n d ” ) ) ) )

Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (define A1 (konstr-abheben 100)) > (define A2 (konstr-abheben 120)) > (A1 50) 50 > (A2 50) 70 Wir haben mit den oberen beiden Befehlen unterschiedliche Objekte mit jeweils eigenem Kontostand erstellt. Allerdings ist das Abheben alleine nicht sinnvoll, da auch das Einzahlen in der Regel m¨ oglich sein soll. Wir brauchen also mehrere Prozeduren, die auf einem Konto arbeiten. Der Kontostand muss nach wie vor lokal bleiben und auch die Prozeduren zum Abheben und Einzahlen werden zu lokalen Prozeduren gemacht. Die Realisierung geschieht durch Nachrichtenweitergabe. 1 2 3 4

( d e f i n e ( konstr−konto wert ) ( l o c a l ( ( d e f i n e k o n t o s t a n d wert ) ( d e f i n e ( abheben b e t r a g ) ( i f (>= k o n t o s t a n d b e t r a g )

3.1 Zuweisungen und lokale Zust¨ande 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

( begin ( set ! k o n t o s t a n d (− k o n t o s t a n d b e t r a g ) ) kontostand ) ” Deckung u n z u r e i c h e n d ” ) ) ( define ( einzahlen betrag ) ( begin ( set ! k o n t o s t a n d (+ k o n t o s t a n d b e t r a g ) ) kontostand ) ) ( d e f i n e ( z u t e i l e n m) ( cond ( ( eq? m ’ abheben ) abheben ) ( ( eq? m ’ e i n z a h l e n ) e i n z a h l e n ) ( else ( error ’ konstr−konto ” Unbekannte Forderung ” ) )))) zuteilen ))

3.1.1 Probleme der Zuweisungen Laut unserem bisherigen Substitutionsmodell waren wir in der Lage, Gleiches durch Gleiches und gleiche Ausdr¨ ucke durch die gleichen Werte zu ersetzen. Durch den Einsatz von set! wird dieses Prinzip zerst¨ ort, da wir beim Aufruf von ein und derselben Prozedur mit den gleichen Parametern unter Umst¨ anden trotzdem unterschiedliche Werte erhalten. Somit: Bei set!-Benutzung sind Variablen nicht mehr Namen f¨ ur Werte, sondern Namen f¨ ur orte, wo Werte gespeichert werden. Die Konsequenz daraus ist: • Auswertungsreihenfolge ist relevant. Der Befehl (+ (abheben 110) kontostand) wird zum Beispiel bei der Auswertung von links nach recht zu (+ 20 20) = 40 ausgewertet, bei der Auswertung von rechts nach links jedoch zu (+ 20 130)= 150. • Es ist unzul¨ assig Ausdr¨ ucke im Programm durch ihre Werte zu ersetzen. • Optimierung + Verifikation ist damit wesentlich schwieriger • Referentielle Transparenz. Das Prinzip, das wir Ausdr¨ ucke durch Werte ersetzen k¨onnen, ohne dass sich Ergebnisse ver¨andern, wird durch den Einsatz von set! zerst¨ort. Dadurch wird auch das Programmverst¨andnis wesentlich schwieriger. • Der Gleichheitsbegriff wird schwieriger. Durch den Einsatz von set! gibt es nunmehr zwei Begriffe von Gleichheit. Zum einen die Wertgleichheit und zum anderen die Objektgleichheit. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (define peter-konto (konstr-konto 100)) > (define paul-konto (konstr-konto 100))

3 Modularit¨at, Objekte, Zust¨ande Hierbei werden zwei verschiedene Konten erstellt. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Anf¨ anger. > (define peter-konto (konstr-konto 100)) > (define paul-konto peter-konto) Hierbei wird nur ein Konto erstellt, welches jedoch zwei Namen besitzt. Die Verwendung von Zuweisungen hat jedoch nicht nur Nachteile. Durch den Einsatz wird die Modularit¨ at durch Objekte mit lokalem Zustand erh¨oht. Als Beispiel betrachten wir dazu einen Zufallsgenerator. Dazu unsere Annahme: Die Funktion zufall-aktuell erzeugt die n¨achste Zufallszahl aus der vorherigen. Dazu wird zum Beispiel die Formel (ax + bmodm) verwendet. a ist die vorherige Zufallszahl, w¨ ahrend b und m entsprechend gew¨ahlt sind. 1 2 3 4 5 6

( define zufall ( local (( define x zufall−init )) ( lambda ( ) ( begin ( set ! x ( z u f a l l − a k t u e l l x ) ) x)))) Die Funktion zufall liefert nun jedes Mal eine andere Zufallszahl. Der Vorteil gegen¨ uber zufall-aktuell ist, dass wird nicht die jeweilige Zufallszahl durch reichen m¨ ussen. Schauen wir uns als weiteres Beispiel die Monte-Carlo-Simulation an. Die Grundidee der Monte-Carlo-Simulation ist, dass eine große Menge von Experimenten gemacht werden und die Ergebnisse tabelliert werden. Die Wahrscheinlichkeiten erlauben dann Schlussfolgerungen. Wir machen dies im Folgenden an einem konkreten Beispiel. Die Wahrscheinlichkeit, dass zwei zuf¨ allige Zahlen teilerfremd sind, ist π62 . Eine N¨aherung von pi w¨are dann q durch die Monte-Carlo-Simulation m¨oglich. π = P6 .

1 2

( d e f i n e ( schaetzwert−pi versuche ) ( sqrt ( / 6 ( monte−carlose v e r s u c h e c e s a r o − t e s t ) ) ) )

3 4 5

( define ( cesaro−test ) (= ( ggT ( z u f a l l ) ( z u f a l l ) ) 1 ) )

6 7 8 9 10 11 12

( d e f i n e ( monte−carlo v e r s u c h e e x p e r i m e n t ) ( l o c a l ( ( d e f i n e i t e r versuche−uebrig versuche−erfolgreich ) ( cond ((= v e r s u c h e − u e b r i g 0 ) (/ v e r s u c h e − e r f o l g r e i c h versuche ) ) ( ( experiment ) ( i t e r (− v e r s u c h e − u e b r i g 1 )

3.2 Das Umgebungsmodell 13 14 15 16 17

(+ v e r s u c h e − e r f o l g r e i c h 1 ) ) ) ( else ( i t e r (− v e r s u c h e − u e b r i g 1 ) versuche−erfolgreich ))))) ( i t e r versuche 0))

3.2 Das Umgebungsmodell Bei dem Umgebungsmodell werden Umgebungen als Folge von Rahmen (mit Bindungen) dargestellt. Ausdr¨ ucke werden in den Umgebungen ausgewertet. Bei den Rahmen handelt es sich um eine Tabelle von Bindungen mitsamt der Zeiger auf die zugeh¨orige Umgebung (außer bei dem globalen Rahmen, der s¨amtliche vordefinierten Symbole enth¨alt). Bindungen wiederum sind Zuordnungen von Variablen zu Werten. Der Wert einer Variable bez¨ uglich einer Umgebung ist der Wert derjenigen Bindung der Variable, die sich im ersten Rahmen der Umgebung befindet, der eine Bindung f¨ ur die Variable enth¨alt. Das mag zun¨achst kompliziert klingen, ist jedoch relativ simpel.

x: 3 y: 5 z: 6 x: 7 A

m: 1 y: 2 B

Der Wert von y ist bei diesem Beispiel bez¨ uglich der Umgebung A 5. Bez¨ uglich der Umgebung B ist der Wert jedoch 2. So wie das Substitutionsmodell seine Regeln hat, so hat auch das Umgebungsmodell seine Auswertungsregeln. Die Auswertung einer Kombination bez¨ uglich einer Umgebung geschieht folgendermaßen: 1. Werte die Teilausdr¨ ucke bez¨ uglich dieser Umgebung aus (Die Reihenfolge ist dabei beliebig). 2. Wende den Operatorwert auf die Operandenwerte an. Das Anwenden einer Prozedur auf Argumente geschieht folgendermaßen:

3 Modularit¨at, Objekte, Zust¨ande 1. Konstruiere neuen Rahmen mit Umgebungsteil der Prozedur als zugeh¨orige Umgebung 2. Trage dort die Bindungen formale Parameter (aktuelle Argumente) ein 3. Werte den Rumpf der Prozedur bez¨ uglich dieser neuen Umgebung aus. Die Auswertung eines Lambda-Ausdrucks bez¨ uglich einer Umgebung U: 1. Parameter und Rumpf der Prozedur aus dem Lambda-Ausdruck 2. Umgebungszeiger wird auf die jeweilige Umgebung U eingetragen Die Auswertung eines Define-Ausdrucks bez¨ uglich einer Umgebung U: 1. Erzeuge eine Bindung von der Variablen zum Wert im ersten Rahmen von U 2. Falls dort die Bindung f¨ ur die Variable schon existiert, wird eine Fehlermeldung ausgegeben. Die Auswertung eines Set!-Ausdrucks bez¨ uglich einer Umgebung U: 1. Suche in U (ausgehend vom ersten Rahmen) die Bindung der Variable (falls diese nicht existiert, so wird eine Fehlermeldung ausgegeben). ¨ 2. Andere in dieser Bindung den Wert. Die Auswertung eines Local-Ausdrucks bez¨ uglich einer Umgebung U: 1. Konstruiere einen neuen Rahmen mit Z als zugeh¨origer Umgebung. 2. Werte die Definition und den Ausdruck bez¨ uglich der neuen Umgebung aus. 3. Trage also die Definition im neuen Rahmen ein. Der Effekt lokaler Deklarationen durch das Umgebungsmodell: ¨ 1. Keine Uberschneidung lokaler Namen mit globalen Namen: Lokale Namen sind in der lokalen Aufrufsumgebung gebunden und so global unsichtbar. 2. Innerhalb lokaler Prozeduren: Parameter der globalen Prozedur sichtbar, da die Rahmen verkettet sind. 3. Keine Namenskonflikte bei Argumentnamen von Prozeduren auf gleicher Ebene.

3.3 Ver¨anderbare Datenstrukturen

3.3 Ver¨ anderbare Datenstrukturen Objekte bestehen, wie wir bereits wissen, auf mehreren Teildaten (Konstruktoren, Selektoren). Eine Ver¨ anderung u ¨ber sogenannte Mutatoren w¨are mit Sicherheit sehr sinnvoll. Ver¨anderbare Datenobjekte (mutable data objects): Sind Daten-Objekte, f¨ ur die Mutatoren definiert sind. Mutator f¨ ur die Struktur w¨are eine Prozedur, welche die Komponenten ¨andert. Dies geschieht u ur Listen gibrt es die Mutatoren set-first! ¨ber set!. F¨ und set-rest!, die jeweils das erste Element und die Restliste in der Liste durch das mitgelieferte ersetzen. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Fortgeschritten. > (define l (list 1 2)) > (set-first! l 3) > l (list 3 2) > (set-rest! l (list 4 5)) > l (list 3 4 5) Weiterhin gibt es auch den Mutator append!, welcher eine Liste an die andere dauerhaft anf¨ ugt. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Fortgeschritten. > (define l1 (list 1 2 3)) > (define l2 (list 4 5 6)) > (append! l1 l2) (list 1 2 3 4 5 6) > l1 (list 1 2 3 4 5 6) > l2 (list 4 5 6) > append! ist jedoch nicht uneingeschr¨ ankt nutzbar, wie wir gleich sehen werden. Dort erzeugen wir mithilfe einer Liste eine zyklische Struktur und so eine Endlosschleife. Willkommen bei DrScheme, Version 371 [3m]. Sprache: Fortgeschritten. > (define l1 (list 1 2)) > (define l2 (list 3 4)) > (append! l1 l2) (list 1 2 3 4)

3 Modularit¨at, Objekte, Zust¨ande > l1 (list 1 2 3 4) > (append! l2 l2) (list 3 4 3 4 3 4 3 4...)

Mutatoren f¨ ur beliebige Strukturen werden automatisch durch define-struct definiert. Wir kennen bereits make-sname, s-name-ki und sname?. Nun gibt es auch set-sname-ki!, um die einzelnen Komponenten der Struktur zu ver¨andern.

3.3.1 Structure Sharing und Identit¨ at Willkommen bei DrScheme, Version 371 [3m]. Sprache: Fortgeschritten. > (define l (list 1 2)) > (define l1 (cons l l)) > l1 (shared ((-1- (list 1 2))) (cons -1- -1-)) > (define l2 (cons (list 1 2) (list 1 2))) > l2 (list (list 1 2) 1 2) >

Wie man sehen kann, verweist (first l1) genauso wie (rest l1) auf die selbe Liste und erzeugt so einen zyklischen Aufruf. (first l2) hingegen zeigt auf die gleiche Liste wie (rest l2), jedoch nicht auf die selbe und erzeugt so keinen zyklischen Aufruf.

Abbildung 3.1: Darstellung der zyklischen Liste

3.3 Ver¨anderbare Datenstrukturen

Abbildung 3.2: Darstellung der zweiten Liste Wirklich wichtig wird dieses Structure Sharing jedoch erst bei der Benutzung von Mutatoren. > (set-first! (shared ((-1> (set-first! (list (list 9 >

(first l1) 9) (list 9 2))) (cons -1- -1-)) (first l2) 9) 2) 1 2)

Eine sorgf¨altige Planung mit Mutatoren ist also esentiell. Sharing kann jedoch mithilfe von eq? entdeckt werden. eq? liefert n¨ amlich wahr zur¨ uck, wenn beide Objekte identisch sind. Im Folgenden schauen wir uns an, wie set-first! und set-rest! mithilfe von set! implementiert werden k¨ onnen. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

( d e f i n e ( cons x y ) ( l o c a l ( ( d e f i n e ( set−x ! u ) ( set ! x u ) ) ( d e f i n e ( set−y ! u ) ( set ! y u ) ) ( define ( zuteilen n) ( cond ( ( eq? n ’ f i r s t ) x) ( ( eq? n ’ r est ) y) ( ( eq? n ’ s e t − f i r s t ! ) set−x ! ) ( ( eq? n ’ s e t − r e s t ! ) set−y ! ) ( e l s e ( error ’ cons ” O p e r a t i o n unbekannt ” ) ) ) ) ) zuteilen ))

18 19 20

( define ( first z) (z ’ first ))

3 Modularit¨at, Objekte, Zust¨ande 21 22 23

( d e f i n e ( r es t z ) ( z ’ r es t ) )

24 25 26

( define ( set−first ! z u) (( z ’ set−first !) u))

27 28 29

( define ( set−rest ! z u) (( z ’ set−rest ! ) u)) Nun wollen wir uns u ¨berlegen, wie wir eine Warteschlange implementieren k¨onnen. Es soll m¨ oglich sein, Objekte hinzuzuf¨ ugen, sowie zu entfernen. Das Entfernen wird nat¨ urlich in O(1) funktionieren, da lediglich das letzte Element entfernt werden muss. Das Hinzuf¨ ugen wird lediglich in O(n) geschehen, da die gesamte Warteschlange durchlaufen werden muss. Um das Hinzuf¨ ugen effizienter zu gestalten, kann ein zus¨atzlicher Zeiger auf das letzte Element angebracht werden, um so von O(n) auf O(1) zu gelangen.

( d e f i n e − s t r u c t ws ( anfang ende ) )

2 3 4 5

; Konstruktor fu ¨ r e i n e neue , l e e r e W a r t e s c h l a n g e ( d e f i n e ( konstr−warteschlange ) ( make−ws empty empty ) )

6 7 8 9

; Selektoren ( define ( leere−warteschlange ? q) ( empty ? ( ws−anfang q ) ) )

10 11 12 13 14

( d e f i n e ( anfang q ) ( i f ( leere−warteschlange ? q) ( error ’ anfang ” L e e r e Warteschlange ” ) ( f i r s t ( ws−anfang q ) ) ) )

15 16 17 18 19 20 21 22 23 24 25 26

; Mutatoren ( d e f i n e ( hinzufuegen−warteschlange ! q e ) ( l o c a l ( ( d e f i n e neues−cons ( cons e empty ) ) ) ( i f ( leere−warteschlange ? q) ( b e g i n ( set−ws−anfang ! q neues−cons ) ( set−ws−ende ! q neues−cons ) q) ( b e g i n ( s e t − r e s t ! ( ws−ende q ) neues−cons ) ( set−ws−ende ! q neues−cons ) q))))

27 28

( define ( entfernen−warteschlange ! q)

3.3 Ver¨anderbare Datenstrukturen 29 30 31 32 33 34

( i f ( leere−warteschlange ? q) ( error ’ e n t f e r n e n − w a r t e s c h l a n g e ” L e e r e Warteschlange ” ) ( b e g i n ( set−ws−anfang q ( res t ( ws−anfang q ) ) ) q))) Eine weitere wichtige Datenstruktur sind Tabellen. Wir haben sie bereits verwendet, ohne die genaue Implementierung zu kennen. Wir wollen nun zun¨achst eine eindimensionale Tabelle implementieren.

( d e f i n e − s t r u c t e i n t r a g ( key wert ) )

2 3

( d e f i n e − s t r u c t tab ( e i n t r a e g e ) )

4 5 6 7

; Konstruktor ( define ( konstr−tabelle ) ( make−tab empty ) )

8 9 10 11 12 13 14 15 16 17

; Selektoren ( d e f i n e ( suche−wert key t ) ( local (( define satz ( ass−eq key ( tab−eintraege t ) ) ) ) ( i f ( empty ? s a t z ) ( error ’ suche−wert ” Element n i c h t vorhanden ” ) ( eintrag−wert satz ) ) ) )

18 19 20 21 22 23 24 25 26

( d e f i n e ( ass−eq key a l ) ( cond ( ( empty ? a l ) empty ) ( ( eq? key ( eintrag−key ( f i r s t a l ) ) ) ( first al )) ( else ( ass−eq key ( r es t a l ) ) ) ) )

27 28 29 30 31 32 33 34

( d e f i n e ( e i n t r a g e n ! key wert t ) ( local (( define eintraege ( tab−eintraege t )) ( define satz ( ass−eq key e i n t r a e g e ) ) ) ( i f ( empty ? s a t z ) ( set−tab−eintraege !

3 Modularit¨at, Objekte, Zust¨ande t ( cons ( make−eintrag key wert ) eintraege )) ( s e t − e i n t r a g − w e r t ! s a t z wert ) ) ) )

35 36 37 38

3.3.2 Simulation digitaler Schaltkreise Als n¨ achstes wollen wir eine Simulation von digitalen Schaltkreisen durchf¨ uhren, also eine Menge von Gattern, verbunden mit Dr¨ahten, welche den Wert 0 oder 1 annehmen k¨onnen. Das Ausgabesignal wird dabei mit Verz¨ogerung aus dem Eingabesignal erzeugt. Die Dr¨ ahte verbinden somit die einzelnen Gatter und haben Werte (0 oder 1). Sie ver¨ anlassen bei einer Anderung ihres Wertes eine Aktion. Die Gatter selbst leiten Werte zwischen den angeschlossenen Dr¨ahten weiter. 1 2

; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Aufgabe : S i m u l a t i o n d i g i t a l e r S c h a l t k r e i s e

3 4 5 6

; H i l f s f u n k t i o n e n : I m p l e m e n t i e r u n g von Warteschlangen ; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; I m p l e m e n t i e r u n g von Warteschlangen

7 8 9

; S t r u k t u r f u e r Warteschlangen : ws mit Anfangs− und E n d z e i g e r ( d e f i n e − s t r u c t ws ( anfang ende ) )

10 11 12

; Konstruiere l e e r e Warteschlange ( d e f i n e ( k o n s t r − w a r t e s c h l a n g e ) ( make−ws empty empty ) )

13 14 15 16

; Selektoren : ( define ( leere−warteschlange ? q) ( empty ? ( ws−anfang q ) ) )

17 18 19 20 21

( d e f i n e ( anfang q ) ( i f ( leere−warteschlange ? q) ( error ’ anfang ” Wartschlange i s t l e e r ” ) ( f i r s t ( ws−anfang q ) ) ) )

22 23 24 25 26 27 28 29 30

; Mutatoren ( d e f i n e ( hinzufuegen−warteschlange ! q e ) ( l o c a l ( ( d e f i n e neues−paar ( cons e empty ) ) ) ( i f ( leere−warteschlange ? q) ( b e g i n ( set−ws−anfang ! q neues−paar ) ( set−ws−ende ! q neues−paar ) q) ( b e g i n ( s e t − r e s t ! ( ws−ende q ) neues−paar ) ; anhanegen

3.3 Ver¨anderbare Datenstrukturen 31

( set−ws−ende ! q neues−paar )

32 33

; Endzeiger ; umsetzen

q))))

34 35 36 37 38 39

( define ( entfernen−warteschlange ! q) ( i f ( leere−warteschlange ? q) ( error ’ e n t f e r n e n − w a r t s c h l a n g e ” Warteschlange i s t l e e r ” ) ( b e g i n ( set−ws−anfang ! q ( r es t ( ws−anfang q ) ) ) q)))

40 41 42 43

; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; Der S c h a l t k r e i s s i m u l a t o r :

44 45 46 47 48 49 50 51 52 53

( d e f i n e ( i n v e r t e r e i n g a b e ausgabe ) ( local (( define ( invert−eingabe ) ( verzoegert inverter−verzoegerung ( lambda ( ) ( s e t − s i g n a l ! ausgabe ( l o g i s c h e s − n i c h t ( get−signal eingabe ) ) ) ) ) ) ) ( add−vorgang ! e i n g a b e i n v e r t − e i n g a b e ) ) )

54 55 56 57 58

( define ( logisches−nicht s ) ( cond ((= s 0 ) 1 ) ((= s 1 ) 0 ) ( e l s e ( error ’ l o g i s c h e s − n i c h t ” U n g u e l t i g e s S i g n a l ” ) ) ) )

59 60 61 62 63 64 65 66 67 68 69 70 71

( d e f i n e ( und−gatter a1 a2 ausgabe ) ( local ( ( d e f i n e ( und−vorgang−prozedur ) ( l o c a l ( ( d e f i n e neuer−wert ( l o g i s c h e s − u n d ( g e t − s i g n a l a1 ) ( g e t − s i g n a l a2 ) ) ) ) ( v e r z o e g e r t und−gatter−verzoegerung ( lambda ( ) ( s e t − s i g n a l ! ausgabe neuer−wert ) ) ) ) ) ) ( begin ( add−vorgang ! a1 und−vorgang−prozedur ) ( add−vorgang ! a2 und−vorgang−prozedur ) ) ) )

72 73 74

( d e f i n e ( logisches−und s1 s2 ) ( i f (and (= s 1 1 ) (= s 2 1 ) )

3 Modularit¨at, Objekte, Zust¨ande 1 0))

75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

( d e f i n e ( o d e r − g a t t e r a1 a2 ausgabe ) ( local ( ( d e f i n e ( oder−vorgang−prozedur ) ( l o c a l ( ( d e f i n e neuer−wert ( l o g i s c h e s − o d e r ( g e t − s i g n a l a1 ) ( g e t − s i g n a l a2 ) ) ) ) ( v e r z o e g e r t oder−gatter−verzoegerung ( lambda ( ) ( s e t − s i g n a l ! ausgabe neuer−wert ) ) ) ) ) ) ( begin ( add−vorgang ! a1 oder−vorgang−prozedur ) ( add−vorgang ! a2 oder−vorgang−prozedur ) ) ) )

90 91 92 93 94

( d e f i n e ( logisches−oder s1 s2 ) ( i f ( or (= s 1 1 ) (= s 2 1 ) ) 1 0))

95 96 97 98 99 100 101 102 103 104

( define ( halbaddierer a b s c ) ( l o c a l ( ( d e f i n e d ( konstr−draht ) ) ( d e f i n e e ( konstr−draht ) ) ) ( begin ( oder−gatter a b d) ( und−gatter a b c ) ( inverter c e) ( und−gatter d e s ) ’ fertig )))

105 106 107 108 109 110

( d e f i n e ( konstr−draht ) ( local ( ( d e f i n e signal−wert 0) ( d e f i n e vorgang−prozeduren empty )

111

( d e f i n e ( s e t −m e i n −s i g n a l ! neuer−wert ) ( i f ( not (= s i g n a l − w e r t neuer−wert ) ) ( b e g i n ( set ! s i g n a l − w e r t neuer−wert ) ( j e d e − a u f r u f e n vorgang−prozeduren ) ) ’ f e r t i g ))

112 113 114 115 116 117

( d e f i n e ( add−vorgang−prozedur p r o z )

118

3.3 Ver¨anderbare Datenstrukturen 119 120 121 122

( begin ( set ! vorgang−prozeduren ( cons p r o z vorgang−prozeduren ) ) ( proz ) ) )

123 124 125 126 127 128 129

( define ( cond ( ( eq? ( ( eq? ( ( eq? ( else

( z u t e i l e n m) m ’ get−signal ) signal−wert ) m ’ s e t − s i g n a l ! ) s e t−m e i n −s i g n a l ! ) m ’ add−vorgang ! ) add−vorgang−prozedur ) ( error ’ konstr−draht ” Unbekannte O p e r a t i o n ” ) ) ) ) )

130 131

zuteilen ))

132 133 134 135 136 137 138 139

( d e f i n e ( jede−aufrufen prozeduren ) ( i f ( empty ? p r o z e d u r e n ) ’ fertig ( begin ( ( f i r s t prozeduren ) ) ( j e d e − a u f r u f e n ( r es t p r o z e d u r e n ) ) ) ) )

140 141 142 143 144

( d e f i n e ( get−signal draht ) ( draht ’ get−signal ) )

145 146 147 148

( d e f i n e ( s e t − s i g n a l ! d r a h t neuer−wert ) ( ( d r a h t ’ s e t − s i g n a l ! ) neuer−wert ) )

149 150 151 152

( d e f i n e ( add−vorgang ! d r a h t vorgang−prozedur ) ( ( d r a h t ’ add−vorgang ! ) vorgang−prozedur ) )

153 154 155

; ; ; R e a l i s i e r u n g d e r V er zo e ge ru ng

156 157 158 159 160

( d e f i n e ( v e r z o e g e r t v e r z o e g e r u n g vorgang ) ( h i n z u f u e g e n − p l a n ! (+ v e r z o e g e r u n g ( a k t u e l l e − z e i t der−plan ) ) vorgang der−plan ) )

161 162

3 Modularit¨at, Objekte, Zust¨ande 163

; ; ; O b e r s t e Ebene d e r S i m u l a t i o n

164 165 166 167 168 169 170 171

( define ( fortfuehren ) ( i f ( l e e r e r − p l a n ? der−plan ) ’ fertig ( begin ( ( e r s t e r − p l a n − e i n t r a g der−plan ) ) ( e n t f e r n e − e r s t e n − p l a n − e i n t r a g ! der−plan ) ( fortfuehren ))))

172 173 174 175

; ; ; S t r u k t u r f u e r Z e i t s e g m e n t e b e s t e h e n d aus e i n e r Z e i t und ; ; ; e i n e r W a r t e s c h l a n g e mit V o r g a n g s p r o z e d u r e n ( d e f i n e − s t r u c t segment ( z e i t w a r t e s c h l a n g e ) )

176 177 178 179 180

; ; ; S t r u k t u r f u e r Z e i t p l a e n e b e s t e h e n d aus d e r a k t u e l l e n Z e i t ; ; ; und e i n e r L i s t e von Z e i t s e g m e n t e n : ( d e f i n e − s t r u c t p l a n ( z e i t segmente ) )

181 182 183

; ; ; K o n s t r u k t o r f u e r e i n e n l e e r e n Plan : ( d e f i n e ( konstr−plan ) ( make−plan 0 empty ) )

184 185

( d e f i n e ( a k t u e l l e − z e i t plan ) ( plan−zeit plan ) )

186 187 188

( d e f i n e ( s e t − a k t u e l l e − z e i t ! plan z e i t ) ( set−plan−zeit ! plan z e i t ) )

189 190

( d e f i n e ( segmente p l a n ) ( plan−segmente p l a n ) )

191 192 193

( d e f i n e ( set−segmente ! p l a n segmente ) ( set−plan−segmente ! p l a n segmente ) )

194 195

( d e f i n e ( e r s t e s − s e g m e n t p l a n ) ( f i r s t ( segmente p l a n ) ) )

196 197

( d e f i n e ( r e s t−s e g me n t e p l a n ) ( r es t ( segmente p l a n ) ) )

198 199 200

( d e f i n e ( leerer−plan ? plan ) ( empty ? ( segmente p l a n ) ) )

201 202 203 204 205 206

( d e f i n e ( h i n z u f u e g e n − p l a n ! z e i t vorgang p l a n ) ( local ( ( d e f i n e ( gehoert−vor ? segmente ) ( or ( empty ? segmente ) (< z e i t ( s e g m e n t − z e i t ( f i r s t segmente ) ) ) ) )

3.3 Ver¨anderbare Datenstrukturen 207 208 209 210 211 212

( d e f i n e ( konstr−neues−zeit−segment z e i t vorgang ) ( l o c a l (( d e f i n e q ( konstr−warteschlange ) ) ) ( begin ( h i n z u f u e g e n − w a r t e s c h l a n g e ! q vorgang ) ( make−segment z e i t q ) ) ) )

213 214 215 216 217 218 219 220 221 222 223

( d e f i n e ( hinzufuegen−segmente ! segmente ) ( cond ((= ( s e g m e n t − z e i t ( f i r s t segmente ) ) z e i t ) ( hinzufuegen−warteschlange ! ( segment−warteschlange ( f i r s t segmente ) ) vorgang ) ) ( ( gehoert−vor ? ( r es t segmente ) ) ( s e t − r e s t ! segmente ( cons ( konstr−neues−zeit−segment z e i t vorgang ) ( r es t segmente ) ) ) ) ( e l s e ( hinzufuegen−segmente ! ( r es t segmente ) ) ) ) )

224 225

( d e f i n e psegmente ( segmente p l a n ) ) )

226 227 228 229 230 231 232

( i f ( gehoert−vor ? psegmente ) ( set−segmente ! plan ( cons ( konstr−neues−zeit−segment z e i t vorgang ) psegmente ) ) ( hinzufuegen−segmente ! psegmente ) ) ) )

233 234 235 236 237 238 239 240 241 242

( d e f i n e ( entferne−ersten−plan−eintrag ! plan ) ( l o c a l ( ( d e f i n e q ( segment−warteschlange ( e r s t e s − s e g m e n t plan ) ) ) ) ( begin ( entfernen−warteschlange ! q) ( i f ( leere−warteschlange ? q) ( set−segmente ! p l a n ( r e st −s e g me n t e p l a n ) ) ’ fertig ))))

243 244 245 246 247 248 249 250

( d e f i n e ( erster−plan−eintrag plan ) ( i f ( leerer−plan ? plan ) ( error ’ e r s t e r − p l a n − e i n t r a g ” Plan i s t l e e r ” ) ( l o c a l ( ( d e f i n e erstes−seg ( erstes−segment plan ) ) ) ( begin ( s e t − a k t u e l l e − z e i t ! plan ( segment−zeit erstes−seg ) )

3 Modularit¨at, Objekte, Zust¨ande ( anfang ( segment−warteschlange e r s t e s − s e g ) ) ) ) ) )

251 252 253 254

; ; ; Anbringen von Sonden am Draht

255 256 257 258 259 260 261 262 263 264

( d e f i n e ( sonde name d r a h t ) ( add−vorgang ! d r a h t ( lambda ( ) ( begin ( d i s p l a y name ) ( d i s p l a y ( a k t u e l l e − z e i t der−plan ) ) ( d i s p l a y ” neuer−wert = ” ) ( d i s p l a y ( get−signal draht ) ) ( newline ) ) ) ) )

265 266 267 268

; ; Beispiellauf :

269 270

( d e f i n e der−plan ( konstr−plan ) )

271 272 273 274

( d e f i n e inverter−verzoegerung 2) ( d e f i n e und−gatter−verzoegerung 3 ) ( d e f i n e oder−gatter−verzoegerung 5)

275 276 277 278 279 280

( define ( define ( define ( define

a1 ( konstr−draht ) ) a2 ( konstr−draht ) ) s ( konstr−draht ) ) c ( konstr−draht ) )

281 282 283 284 285

( sonde ( sonde ( sonde ( sonde

” Draht ” Draht ” Draht ” Draht

a1 : ” a1 ) a2 : ” a2 ) s: ” s) c : ” c)

286 287

( h a l b a d d i e r e r a1 a2 s c )

288 289 290 291 292

( s e t − s i g n a l ! a1 1 ) ( fortfuehren ) ( s e t − s i g n a l ! a2 1 ) ( fortfuehren )

3.3 Ver¨anderbare Datenstrukturen

3.3.3 Modelle mit Beschr¨ ankung In der traditionellen Programmierung haben wir die Wertberechnung aus Eingaben durchgef¨ uhrt. D.h. wir haben nur in genau eine Richtung die Berechnung durchgef¨ uhrt. Nun wollen wir auch Modelle mit unbekannter Richtung implementieren, also Berechnungsmodelle, bei denen die Werte erst zur Compilerzeit bekannt werden. Wir nutzen dazu Relationen in verschiedene Richtungen aus, sobald einzelne Werte u ¨berhaupt erst bekannt sind. Als Beispiel nehmen wir die Temperaturumrechnung Celsius ⇔ Fahrenheit, f¨ ur welche die Relation 9·C = 5(F −32) gilt. Dieses System, bei dem man in verschiedene Richtungen die Berechnung durchf¨ uhren kann, nennt man Rechnen mit Beschr¨ankungen. Anwendung finden diese Systeme vor allem in der k¨ unstlichen Intelligenz, beim Operation Research, bei der Containerverteilung, bei Produktionsabl¨aufen, bei Terminalvergaben am Flughafen etc. Die Werte werden also bez¨ uglich der Beschr¨ankungen propagiert. Wir arbeiten dazu mit Beschr¨ ankungsnetzen. Ein elementares Netz w¨are zum Beispiel eine Prozedur (addierer x y z), welche die Relation x + y = z ausnutzt. Je nachdem, welche Werte bekannt sind, liefert diese Relation entsprechend den noch fehlenden Wert zur¨ uck. Um die Relationen zu verkn¨ upfen benutzen wir sogenannte Konnektoren. Das Netzwerk f¨ ur die Temperaturumrechnung w¨ urde zum Beispiel folgendermaßen aussehen:

Abbildung 3.3: Netzwerk f¨ ur 9C = 5(F − 32) Die Berechnung im Netzwerk geschieht folendermaßen. Falls ein Konnektor einen Wert erh¨alt so weckt er alle Beschr¨ ankungen, mit denen er verbunden ist - mit Ausnahme derjenigen, von der der Wert kommt - und informiert diese u ¨ber den neuen Wert. Falls eine Beschr¨ankung geweckt wird, pr¨ uft sie, ob die angeschlossenen Konnektoren genug Werte liefern, um weitere Werte zu berechnen. Wenn das der Fall ist, so werden die Werte an die Konnektoren weitergeleitet. 1 2

; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Aufgabe : P r o p a g i e r u n g von Beschraenkungen

3 4 5

; ; ; P r i m i t i v e Beschraenkungen :

6 7 8 9 10

( d e f i n e ( a d d i e r e r a1 a2 summe) ( local ( ( d e f i n e ( verarbeite−neuen−wert ) ( cond ( ( and ( hat−wert ? a1 ) ( hat−wert ? a2 ) )

3 Modularit¨at, Objekte, Zust¨ande ( set−wert ! summe (+ ( get−wert a1 ) ( get−wert a2 ) ) ich )) ( ( and ( hat−wert ? a1 ) ( hat−wert ? summe ) ) ( set−wert ! a2 (− ( get−wert summe) ( get−wert a1 ) ) ich )) ( ( and ( hat−wert ? a2 ) ( hat−wert ? summe ) ) ( set−wert ! a1 (− ( get−wert summe) ( get−wert a2 ) ) ich )) ( else ’ fertig )))

11 12 13 14 15 16 17 18 19 20 21 22 23

( define ( verarbeite−vergiss−wert ) ( b e g i n ( v e r g i s s − w e r t ! summe i c h ) ( v e r g i s s − w e r t ! a1 i c h ) ( v e r g i s s − w e r t ! a2 i c h ) ( verarbeite−neuen−wert ) ) ) ; wegen m o e g l i c h e r a n d e r e r ; Werte

24 25 26 27 28 29 30

( define ( ich aufforderung ) ( cond ( ( eq? a u f f o r d e r u n g ’ ich−habe−einen−wert ) verarbeite−neuen−wert ) ( ( eq? a u f f o r d e r u n g ’ ich−verlor−meinen−wert ) verarbeite−vergiss−wert ) ( e l s e ( error ’ a d d i e r e r ” Unbekannte A u f f o r d e r u n g ” ) ) ) ) )

31 32 33 34 35 36 37

( b e g i n ( v e r b i n d e a1 i c h ) ( v e r b i n d e a2 i c h ) ( v e r b i n d e summe i c h ) ) ) )

38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

( d e f i n e ( m u l t i p l i k a t o r m1 m2 produkt ) ( local ( ( d e f i n e ( verarbeite−neuen−wert ) ( cond ( ( or ( i f ( hat−wert ? m1) (= ( get−wert m1) 0 ) f a l s e ) ( i f ( hat−wert ? m2) (= ( get−wert m2) 0 ) f a l s e ) ) ( set−wert ! produkt 0 i c h ) ) ( ( and ( hat−wert ? m1) ( hat−wert ? m2) ) ( set−wert ! produkt ( ∗ ( get−wert m1) ( get−wert m2) ) ich )) ( ( and ( hat−wert ? produkt ) ( hat−wert ? m1) ) ( set−wert ! m2 ( / ( get−wert produkt ) ( get−wert m1) )

3.3 Ver¨anderbare Datenstrukturen 55 56 57 58 59 60

ich )) ( ( and ( hat−wert ? produkt ) ( hat−wert ? m2) ) ( set−wert ! m1 ( / ( get−wert produkt ) ( get−wert m2) ) ich )) ( else ’ fertig )))

61 62 63 64 65 66

( define ( verarbeite−vergiss−wert ) ( b e g i n ( v e r g i s s − w e r t ! produkt i c h ) ( v e r g i s s − w e r t ! m1 i c h ) ( v e r g i s s − w e r t ! m2 i c h ) ( verarbeite−neuen−wert ) ) )

67 68 69 70 71 72 73 74

( define ( ich aufforderung ) ( cond ( ( eq? a u f f o r d e r u n g ’ ich−habe−einen−wert ) verarbeite−neuen−wert ) ( ( eq? a u f f o r d e r u n g ’ ich−verlor−meinen−wert ) verarbeite−vergiss−wert ) ( else ( error ’ m u l t i p l i k a t o r ” Unbekannte A u f f o r d e r u n g ” ) ) ) ) )

75 76 77 78

( b e g i n ( v e r b i n d e m1 i c h ) ( v e r b i n d e m2 i c h ) ( v e r b i n d e produkt i c h ) ) ) )

79 80 81 82 83 84 85 86

( d e f i n e ( k o n s t a n t e wert k o n n e k t o r ) ( local (( define ( ich aufforderung ) ( error ’ k o n s t a n t e ” Unbekannte A u f f o r d e r u n g ” ) ) ) ( begin ( verbinde konnektor i ch ) ( set−wert ! k o n n e k t o r wert i c h ) ) ) )

87 88 89 90 91 92 93 94 95 96

( d e f i n e ( sonde name k o n n e k t o r ) ( local ( ( d e f i n e ( verarbeite−neuen−wert ) ( begin ( newline ) ( d i s p l a y ” Sonde : ” ) ( d i s p l a y name ) ( display ” = ”) ( d i s p l a y ( get−wert k o n n e k t o r ) ) ) )

97 98

( define ( verarbeite−vergiss−wert )

3 Modularit¨at, Objekte, Zust¨ande ( begin ( newline ) ( d i s p l a y ” Sonde : ” ) ( d i s p l a y name ) ( display ” = ”) ( display ”?” ) ) )

99 100 101 102 103 104 105

106 107 108 109 110 111 112

( verbinde konnektor ic h ) ) )

113 114 115 116 117 118

; S c h n i t t s t e l l e f u e r Beschraenkungen : ( d e f i n e ( i n f o r m i e r e − u e b e r − w e r t beschraenkung ) ( ( beschraenkung ’ ich−habe−einen−wert ) ) )

119 120 121

( d e f i n e ( i n f o r m i e r e −u e b e r −k e i n−w e r t beschraenkung ) ( ( beschraenkung ’ ich−verlor−meinen−wert ) ) )

122 123

; ; ; Konnektoren

124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139

( d e f i n e ( konstr−konnektor ) ( local ( ( d e f i n e wert empty ) ( d e f i n e i n f o r m a n t empty ) ( d e f i n e beschraenkungen empty ) ( d e f i n e ( set−mein−wert neuwert s e t z e n d e r ) ( cond ( ( not ( hat−wert ? i c h ) ) ( b e g i n ( set ! wert neuwert ) ( set ! i n f o r m a n t s e t z e n d e r ) ( fuer−jeden−ausser setzender informiere−ueber−wert beschraenkungen ) ) ) ( ( not (= wert neuwert ) ) ( error ’ k o n n e k t o r ” Widerspruch ” ) ) ( else ’ fertig )))

140

( d e f i n e ( vergiss−mein−wert r u e c k z i e h e n d e r ) ( i f ( eq? r u e c k z i e h e n d e r i n f o r m a n t )

141 142

3.3 Ver¨anderbare Datenstrukturen 143 144 145 146 147

( b e g i n ( set ! i n f o r m a n t empty ) ( fuer−jeden−ausser rueckziehender i n f o r m i e r e−u e b e r −k e i n−w e r t beschraenkungen ) ) ’ f e r t i g ))

148 149 150 151 152 153 154 155 156 157

( d e f i n e ( v e r b i n d e neue−beschraenkung ) ( begin ( i f ( not (memq neue−beschraenkung beschraenkungen ) ) ( set ! beschraenkungen ( cons neue−beschraenkung beschraenkungen ) ) ’ fertig ) ( i f ( hat−wert ? i c h ) ( i n f o r m i e r e − u e b e r − w e r t neue−beschraenkung ) ’ fertig )))

158 159 160 161 162 163 164 165 166 167

( define ( ich aufforderung ) ( cond ( ( eq? a u f f o r d e r u n g ’ hat−wert ? ) ( not ( empty ? informant ) ) ) ( ( eq? a u f f o r d e r u n g ’ wert ) wert ) ( ( eq? a u f f o r d e r u n g ’ set−wert ! ) set−mein−wert ) ( ( eq? a u f f o r d e r u n g ’ v e r g i s s ) vergiss−mein−wert ) ( ( eq? a u f f o r d e r u n g ’ v e r b i n d e ) v e r b i n d e ) ( e l s e ( error ’ k o n n e k t o r ” Unbekannte O p e r a t i o n ” ) ) ) ) ) ich ))

168 169 170 171 172 173 174 175 176 177

( d e f i n e ( f u e r − j e d e n − a u s s e r ausnahme p r o z e d u r l i s t e ) ( local ( ( d e f i n e ( s c h l e i f e elemente ) ( cond ( ( empty ? e l e m e n t e ) ’ f e r t i g ) ( ( eq? ( f i r s t e l e m e n t e ) ausnahme ) ( s c h l e i f e ( r es t e l e m e n t e ) ) ) ( e l s e ( begin ( prozedur ( f i r s t elemente ) ) ( s c h l e i f e ( r es t e l e m e n t e ) ) ) ) ) ) ) ( schleife liste )))

178 179

; ; ; S c h n i t t s t e l l e zu Konnektoren

180 181 182

( d e f i n e ( hat−wert ? k o n n e k t o r ) ( k o n n e kt o r ’ hat−wert ? ) )

183 184 185

( d e f i n e ( get−wert k o n n e k t o r ) ( k o n n e kt o r ’ wert ) )

186

3 Modularit¨at, Objekte, Zust¨ande 187 188

( d e f i n e ( vergiss−wert ! konnektor rueckziehender ) ( ( konnektor ’ v e r g i s s ) rueckziehender ) )

189 190 191

( d e f i n e ( set−wert ! k o n n e k t o r neuer−wert i n f o r m a n t ) ( ( k o n n e k t o r ’ set−wert ! ) neuer−wert i n f o r m a n t ) )

192 193 194

( d e f i n e ( v e r b i n d e k o n n e k t o r neue−beschraenkung ) ( ( k o n n e k t o r ’ v e r b i n d e ) neue−beschraenkung ) )

195 196 197

; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

198 199

; B e i s p i e l : Celsius−Fahrenheit−Konverter :

200 201 202 203 204 205 206 207 208 209 210 211 212

( define ( celsius−fahrenheit−konverter c f ) ( l o c a l ( ( d e f i n e u ( konstr−konnektor ) ) ( d e f i n e v ( konstr−konnektor ) ) ( d e f i n e w ( konstr−konnektor ) ) ( d e f i n e x ( konstr−konnektor ) ) ( d e f i n e y ( konstr−konnektor ) ) ) ( begin ( m u l t i p l i k a t o r c w u) ( multiplikator v x u) ( addierer v y f ) ( k o n s t a n t e 9 w) ( konstante 5 x) ( k o n s t a n t e 32 y ) ) ) )

213 214 215 216 217

; D e f i n i e r e Konverter : ( d e f i n e C ( konstr−konnektor ) ) ( d e f i n e F ( konstr−konnektor ) ) ( c e l s i u s − f a h r e n h e i t − k o n v e r t e r C F)

218 219 220 221

; Sonden a n b r i n g e n : ( sonde ” C e l s i u s ” C) ( sonde ” F a h r e n h e i t ” F)

222 223 224 225 226

; ; ; ;

( s e t − w e r t ! C 25 ’ b e n u t z e r ) ( s e t − w e r t ! F 212 ’ b e n u t z e r ) ( vergiss−wert ! C ’ benutzer ) ( s e t − w e r t ! F 212 ’ b e n u t z e r )

Willkommen bei DrScheme, Version 4.1.3 [3m]. Sprache: Fortgeschritten angepasst; memory limit: 128 megabytes.

3.4 Zust¨ande in mehrl¨aufigen Systemen ’fertig ’fertig ’fertig This program should be tested. > (set-wert! C 25 ’benutzer) Sonde: Celsius = 25 Sonde: Fahrenheit = 77’fertig > (set-wert! F 25 ’benutzer) konnektor: Widerspruch > (vergiss-wert! C ’benutzer) Sonde: Celsius = ? Sonde: Fahrenheit = ?’fertig > (set-wert! F 25 ’benutzer) Sonde: Fahrenheit = 25 Sonde: Celsius = -35/9’fertig

3.4 Zust¨ ande in mehrl¨ aufigen Systemen Wir haben in den vorigen Kapiteln bereits Ausdr¨ ucke zeitlos benutzt, als wir keine Zust¨ande hatten und auch zeitabh¨ angig, als wir lokale Zust¨ande erlaubt hatten. Das Ergebnis der gleichen Prozedur konnte also trotz gleicher Parameter unterschiedlich ausfallen, da das Ergebnis abh¨ angig von der Vorgeschichte war. In der realen Welt gibt es jedoch eine Art von Nebenl¨ aufigkeit, welche daf¨ ur sorgt, dass die Auswertungen noch schwieriger zu u ¨berschauen sind. In der Realit¨at existieren unabh¨angige Objekte (Prozesse), die alleine agieren und sich synchronisieren. Auch auf dem Computer gibt es viele nebenl¨aufig angelegte Programme. Die Nebenl¨aufigkeit erzeugt nun aber Probleme bei Zust¨anden, die von mehreren Prozessen ver¨andert werden k¨ onnen. Dazu betrachten wir als Beispiel unsere alte Implementierung des Bankkontos. 1 2 3 4 5 6

( d e f i n e ( abheben b e t r a g ) ( i f (>= k o n t o s t a n d b e t r a g ) ( b e g i n ( set ! k o n t o s t a n d (− k o n t o s t a n d b e t r a g ) ) kontostand ) ” Deckung n i c h t a u s r e i c h e n d ” ) ) Nehmen wir nun an, Peter und Paul haben ein gemeinsames Konto. Auf diesem befinden sich 130 Euro und beide heben an unterschiedlichen Geldautomaten jeweils 100 Euro ab. Was kann nun geschehen? Im ersten Fall, wenn beide gleichzeitig abheben, k¨onnte es ¨ passieren, dass beide abheben d¨ urfen, also beide durch die Uberpr¨ ufung (¿= kontostand

3 Modularit¨at, Objekte, Zust¨ande betrag) kommen. Nun hebt zun¨achst Peter sein Geld ab, sodass der Kontostand bei 30 liegt. Danach hebt Paul ab, sodass der Kontostand anschließend auf -70 gestellt wird, obwohl wir es nicht erm¨ oglichen wollten, dass das Konto u ¨berzogen wird. Wesentlich schlimmer ist jedoch der zweite Fall. Nehmen wir an, Peter hebt 100 Euro ab. Bevor der Kontostand jedoch gesetzt wird, hebt auch Paul 100 Euro ab. Peter setzt den Kontostand auf 30 und kurz danach setzt auch Paul den Kontostand auf 30. Abgehoben wurde also 200 Euro, abgebucht jedoch nur 100 Euro. Ein fataler Fehler. Es ist also eine Kontrolle der kritischen Bereiche notwendig. Um diese kritischen Bereiche zu kontrollieren, gibt es sogenannte Semaphore. Das sind Signale, die z.B. einen Wert Null oder Eins annehmen k¨onnen und Operationen P und V haben (”passeren”/ ”vrijeven”). (P s) sorgt daf¨ ur, dass wenn s=1 gilt, s auf 0 gesetzt wird. Ansonsten wird die Ausf¨ uhrung gestoppt und der Prozess wird auf die Warteschlange gesetzt. Erst wenn s wieder auf 1 wechselt, wird der Prozess weiter ausgef¨ uhrt. (V s) setzt s auf 1. Wenn Prozesse auf s=1 warten, so aktiviert die Prozedur sogleich den n¨ achsten. Wichtig dabei ist, dass sowohl P als auch V unteilbare Operationen sind. Das heißt, dass das Betriebssystem garantieren muss, dass nur ein prozess Gleichzeitig P oder V ausf¨ uhrt. Wir ver¨ andern unseren Code also folgendermaßen: 1 2 3 4

( d e f i n e ( konstr−abheben b e t r a g ) ( b e g i n (P s ) ( abheben b e t r a g ) (V s ) ) ) So kann nur ein Prozess gleichzeitig abheben. Ein Problem besteht aber nochi immer. An verschiedenen Konten kann nicht gleichzeitig abgehoben werden. Eine L¨osung w¨ are also f¨ ur jedes Konto ein eigenes, lokales Semaphor.

1 2 3

( d e f i n e ( konstr−konto a n f a n g s b e t r a g ) ( l o c a l ( ( d e f i n e s ( konstr−semaphor ) ) ( d e f i n e ( abheben b e t r a g ) . . . Diese Art von Nebenl¨ aufigkeitskontrolle sorgt jedoch unter Umst¨anden f¨ ur neue Proble¨ me. nehmen wir an, wir m¨ ochten eine Uberweisung zwischen den Konten K1 und K2 durchf¨ uhren. Dazu schreiben wir folgende Prozedur:

1 2 3 4 5 6

( d e f i n e ( u e b e r w e i s e n k1 k2 s 1 s 2 ) ( b e g i n (P s 1 ) (P s 2 ) (P s 2 ) (P s 1 ) ) ) Nun haben Peter und Paul verschiedene Konten und wollen sich ”gleichzeitig”gegenseitig ¨ Geld u (P s1) ¨berweisen. Nun stellen wir uns vor, dass die eine Uberweisungsprozedur ausf¨ uhrt, die andere zeitgleich (P s2). Dann kommt es zu einer Verklemmung1 , da beide 1

Ein sogenannter Deadlock.

3.5 Datenstr¨ome (Streams) Prozeduren gegenseitig auf sich warten und so festh¨angen. Um solche Dinge zu vermeiden, erfordert es eine sorgf¨ altige Planung von Verklemmungsvermeidungsstrategien. Als Konsequenz daraus sollten wir also, wann immer es m¨oglich ist, zustandsfrei arbeiten, ¨ Zust¨ande lokal halten und Anderungen kontrollieren. Außerdem sollten wir Verklem¨ mungen ausschließen, indem wir Anderungsoperationen synchronisieren.

3.5 Datenstr¨ ome (Streams) Wir haben bereits Prozeduren h¨ oherer Ordnung benutzt, um Gesetzm¨aßigkeiten bez¨ uglich der Ablaufstruktur herauszuziehen. Hier wollen wir es ¨ahnlich f¨ ur Datenverarbeitung machen. Nehmen wir dazu an, wir wollen in einem Bin¨arbaum aus ganzen Zahlen alle ungeraden Bl¨atter quadrieren und aufsummieren. Dazu schreiben wie folgende Prozedur: 1 2 3 4 5 6 7

( d e f i n e (summe−uq b ) ( i f ( blatt ? b) ( i f ( ungerade ? b ) ( quadrat b ) 0) (+ (summe−uq ( l i n k t e r − a s t b ) ) (summe−uq ( r e c h t e r − a s t b ) ) ) ) ) Nun wollen wir alle ungeraden Fibonaccizahlen Fib(h) mit 1 ≤ h ≤ n auflisten.

1 2 3 4 5 6 7 8 9

( d e f i n e ( ungerade−fibs n) ( l o c a l (( define ( naechstes k) ( i f (> k 1 ) empty ( l o c a l (( define fh ( f i b h )) ( i f ( ungerade ? f h ) ( cons f h ( n a e c h s t e s (+ h 1 ) ) ) ( n a e c h s t e s (+ h 1 ) ) ) ) ) ) ) ) ( naechstes 1))) Oberfl¨achlich scheinen beide Prozeduren nicht viel gemeinsam haben. bei genauerer Betrachtung f¨allt jedoch schon eine Gemeinsamkeit auf. F¨ ur summe-uq gilt: 1. Aufz¨ahlung der Bl¨ atter 2. Filtern der ungeraden Zahlen 3. Quadrieren 4. Akkumulieren in Summe F¨ ur ungerade-fibs gilt: 1. Aufz¨ahlung ganzer Zahlen

3 Modularit¨at, Objekte, Zust¨ande 2. Fibonacci-Berechnung 3. Filtern der ungeraden Zahlen 4. Akkumuliere in Liste Im ersten Schritt wird also bei beiden Prozeduren etwas erzeugt. Im zweiten und dritten Schritt wird ein Abbild erstellt und gefiltert. Im letzten Schritt wird das Ergebnis gesammelt. Jedoch ist diese Struktur im Programm nicht explizit sichtbar. Unser Ziel ist nun ein modularer Aufbau bez¨ uglich des Datenflusses. Uns interessiert also nicht die Berechnungsfolge, sondern vielmehr der Datenfluss selbst.

3.5.1 Datenflussorientierte Programmstruktur mit Datenstr¨ omen Datenstr¨ ome sind generell einfach nur Folgen von Elementen. Die u ¨blichen Operationen auf solche Datenstr¨ ome sind: • cons-strom: Konstruiere neuen Strom • kopf: 1.Element • rest-strom: Restlicher Strom • der-leere-strom: Leerer Strom ohne Elemente • leerer-strom?: Ist der Strom leer? Die Gesetze w¨ aren entsprechend: • (kopf (cons-strom a b)) = a • (rest-strom (cons-strom a b)) = b • (leerer-strom? (cons-strom a b)) = false • (leerer-strom? (der-leere-strom) = true Die Implementierung geschieht zun¨achst als Listen (cons, first, rest, empty?, empty), sp¨ ater jedoch etwas spezieller. Schauen wir uns zun¨achst eine n¨ utzliche Operation an, die mehrere Str¨ ome aneinander reiht. 1 2 3 4 5 6

( d e f i n e ( append−stroeme s 1 s 2 ) ( i f ( leerer−strom ? s1 ) s2 ( cons−strom ( k o p f s 1 ) ( append−stroeme ( r es t s 1 ) s2 ) ) ) ) Nun betrachten wir eine Strukturierung mit den Str¨omen. Dazu schauen wir uns die Summierung im Bin¨ arbaum an.

3.5 Datenstr¨ome (Streams)

1 2 3 4 5

( d e f i n e ( gen−baum b ) ( i f ( blatt ? b) ( cons−strom b der−leere−strom ) ( append−stroeme ( gen−baum ( l i n k e r − a s t b ) ) ( gen−baum ( r e c h t e r − a s t b ) ) ) ) )

6 7 8 9 10 11 12 13 14

( define ( filter−ungerade s ) ( cond ( ( l e e r e r − s t r o m ? s ) der−leere−strom ) ( ( ungerade ? ( k o p f s ) ) ( cons−strom ( k o p f s ) ( f i l t e r − u n g e r a d e ( r es t−s tr om s ) ) ) ) ( else ( f i l t e r − u n g e r a d e ( r es t−s tro m s ) ) ) ) )

15 16 17 18 19 20

( d e f i n e ( abb−quadrat s ) ( i f ( leerer−strom ? s ) der−leere−strom ( cons−strom ( quadrat ( k o p f s ) ) ( abb−quadrat ( r es t−s tro m s ) ) ) ) )

21 22 23 24 25 26

( d e f i n e ( akkumuliere−+ s ) ( i f ( leerer−strom ? s ) 0 (+ ( k o p f s ) ( akkumuliere−+ ( re st−s tro m s ) ) ) ) )

27 28 29 30 31 32

( d e f i n e (summe−uq b ) ( akkumuliere−+ ( abb−quadrat ( filter−ungerade ( gen−baum b ) ) ) ) ) Die Implementierung f¨ ur die ungeraden Fibonacci-Zahlen geschieht analog. Zun¨achst scheint diese Implementierung sehr umst¨andlich zu sein, doch sie hat auch ihre Vorteile. Die Bausteine werden recht einfach zusammengesetzt. So k¨onnte man nun auch recht einfach die Summe der Quadrate der ersten n Fibonacci-Zahlen bilden:

1 2 3 4 5

( d e f i n e ( summe−qf n ) ( akkumuliere−+ ( abb−quadrat ( abb−fib ( gen−intervall 1 n ) ) ) ) )

3 Modularit¨at, Objekte, Zust¨ande Der Nachteil ist jedoch, dass Prozesuren wie abb-fib oder abb-quadrat viel zu spezifisch sind. Man br¨ auchte universale Prozeduren f¨ ur die Datenstr¨omen. So unterscheiden sich die verschiedenen Abbilder auf die Str¨ome nur durch die Abbildungsfunktionen. W¨ urde man die Funktion als Parameter u bergeben, so k¨ o nnte man recht universelle Abbilder ¨ erschaffen. 1 2 3 4 5

( d e f i n e ( abb f s ) ( i f ( leerer−strom ? s ) der−leere−strom ( cons−strom ( f ( k o p f s ) ) ( abb f ( r es t−s tr om s ) ) ) ) )

6 7 8 9 10 11 12 13 14

( define ( filter−strom p s ) ( cond ( ( l e e r e r − s t r o m ? s ) der−leere−strom ( ( p ( kopf s ) ) ( cons−strom ( k o p f s ) ( f i l t e r p ( r es t−s tro m s ) ) ) ) ( else ( f i l t e r − s t r o m p ( r es t−st ro m s ) ) ) ) ) ) So etwas ¨ ahnliches kann man auch mit dem Akkumulator machen. Er ben¨otigt zwei Parameter. Zum einen das neutrale Element (0, empty) und zum anderen einen bin¨ aren Operator (+, cons):

1 2 3 4 5 6 7

( d e f i n e ( akk op e s ) ( i f ( leerer−strom ? s ) e ( op ( k o p f s ) ( akk op e ( re s t−s tro m s ) ) ) ) ) Damit k¨ onnen wir auch unsere Prozedur summe-uq vereinfachen.

1 2 3 4 5

( d e f i n e (summe−uq b ) ( akk + 0 ) ( akk quadrat ( f i l t e r − s t r o m ungerade ? ( gen−baum b ) ) ) ) Mit unseren jetzigen Definitionen sind eine Menge neuer Kombinationen einfach realisierbar. Wir m¨ ochten zum Beispiel das Produkt der Quadrate der ungeraden Zahlen von 1 bis n bilden.

1 2

( d e f i n e ( prod−qu n ) ( akk ∗ 1

3.5 Datenstr¨ome (Streams) 3 4 5

( abb−quadrat ( f i l t e r − s t r o m ungerade ? ( gen−intervall n ) ) ) ) ) Der universelle Akkumulator ist auch noch auf ganz andere Probleme anwendbar. So k¨onnen wir etwa die Umwandlung von einem Strom von Str¨omen in einen einzigen Srom leicht realisieren:

1 2 3 4

( define ( glaetten s ) ( akk append−stroeme der−leere−strom s )) Die Anwendung beschr¨ ankt sich auch nicht nur auf mathematische Probleme. Nehmen wir als n¨achstes an, wir haben einen Strom mit Studentendaten. Nun wollen wir eine Liste aller Studenten mit der Klausurqualifikation erhalten. Dazu:

1 2 3 4 5

( d e f i n e ( k l a u s u r − q u a l i f studenten−strom ) ( akk cons empty ( f i l t e r − s t r o m >−h a e l f t e − u e b u n g s p u n k t e ? ( f i l t e r − s t r o m h o e r t− i n f o r m a t i k− 1 studenten−strom ) ) ) ) Als weitere n¨ utzliche Prozedur implementierungen wir nun die M¨oglichkeit, irgendeine Prozedur (mit eventueller Zustands¨ anderung) auf jedes Element anzuwenden:

1 2 3 4 5

( d e f i n e ( fuer−jedes proz s ) ( i f ( leerer−strom ? s ) ’ fertig ( begin ( proz ( kopf s ) ) ( f u e r − j e d e s p r o z ( re st−s tr om s ) ) ) ) ) Eine praktische Anwendung eben dieser Prozedur w¨are es, wenn man nun jedes einzelne Element des Stroms anzeigen m¨ ochte. Dazu: Willkommen bei DrScheme, Version 371 [3m]. Sprache: Fortgeschritten. > (fuer-jedes display s)

3.5.2 Implementierung von Datenstr¨ omen Bisher haben wir eine recht einfache Implementierung der Datenstr¨ome mithilfe von Listen geschaffen. Der Nachteil davon ist, dass wir einen unn¨otigen Aufbau von eventuell großen Datenstrukturen haben. Der stromorientierte Stil sieht etwa folgendermaßen aus:

3 Modularit¨at, Objekte, Zust¨ande

1 2 3 4 5 6

( akk ( filter ( abb ( abb ... strom ) . . . ) Die Idee w¨ are nun, dass wir f¨ ur jedes Element e ∈ Strom die Prozeduren abb...abb...filter...akk ausf¨ uhren. Allerdings ist dies nicht so einfach m¨oglich, da SCHEMEzun¨achst die Argumente auswertet. Dadurch kommt es zum Aufbau des komplizierten Stroms. Nehmen wir zum Beispiel die Berechnung der zweiten Primzahl im Intervall 10.000 bis 1.000.000.

1 2 3 4 5

... ( k o p f ( r es t−s tr om ( f i l t e r p r i m z a h l ? ( g e n − i n t e r v a l l 10000 1000000)))) ... Hier wird vor dem Primzahltest eine Liste von fast einer Million Elemente erzeugt. Eine verbesserte Implementierung w¨are es also, wenn wir keinen vollst¨andigen Aufbau der Stromstruktur h¨ atten, sondern nur soweit, wie wir wirklich ben¨otigen. Den Aufbau der Struktur k¨ onnten wir reduzieren durch die Anwendung der Technik der verz¨ogerten Auswertung. Dabei handelt es sich um eine Sonderform von SCHEME, wobei zun¨achst die zu verz¨ ogernde Auswertung mit (delay ausdruck) aufgerufen wird. Dies gibt ein Objekt O zur¨ uck, welches sp¨ater mit (force O) ausgewertet werden kann. Es gilt also (force (delay O)) = O. Eine Alternativimplementierung der Str¨ome w¨are es also, wenn (cons-strom a b) in etwa ¨ aquivalenz w¨are zu (cons a (delay b)). Dies l¨asst sich realisieren, jedoch nicht als Prozedur, sondern als Sonderform. Wie genau das zu implementieren w¨are, interessiert hier nun nicht. (kopf s) w¨are dann ¨aquivalent zu (first s) und (reststrom s) w¨ are ¨ aquivalent zu (force (rest s)). Die Auswertung des Reststroms w¨ urde also erst dann geschehen, wenn darauf zugegriffen wird. Die Regeln f¨ ur diese Implementierung des ADT w¨ aren noch immer korrekt und identisch zu den obigen. Wir schauen uns den Effekt der verz¨ ogerten Auswertung an einem Beispiel an:

1 2 3 4 5 6

( define ( gen−intervall a b) ( i f (> a b ) der−leere−strom ( cons−strom a ( g e n − i n t e r v a l l (+ a 1 ) b)))) Willkommen bei DrScheme, Version 372 [3m]. Sprache: Fortgeschritten angepasst. > (kopf (rest-strom (filter primzahl? (gen-intervall 10000 1000000))))

3.5 Datenstr¨ome (Streams) • Der innere Befehl (gen-intervall 10000 1000000) wird zun¨achst zu (cons-strom 10000 ”Verz¨ ogerung von (gen-intervall 10001 1000000)”) ausgewertet. • Der Filter wird angewendet. 10000 ist nicht prim, also wird der Reststrom gefiltert. • Die Verz¨ ogerung wird mittels force ausgewertet. • Der Filter wird angewendet. 10001 ist nicht prim, also wird der Reststrom gefiltert. • ... • Der Filter wird angewendet. 10007 ist prim, also wird folgender Strom gebildet: (cons-strom 10007 ”Verz¨ ogerung von (filter primzahl? (gen-intervall 10008 1000000))”) • Erst der Befehl rest-strom sorgt daf¨ ur, dass die Verz¨ogerung weiter ausgewertet wird. Also wird weiter gefiltert. • ... • 10009 ist prim. Es entsteht also (cons-strom 10009 ”Verz¨ogerung von (filter primzahl? (gen-intervall 10010 1000000))”). • Der Befehl kopf liefert schlussendlich 10009 zur¨ uck. Hier wird nun tats¨ achlich der Vorteil sichtbar. Wir haben keinen Aufbau des Gesamtstroms (10000 bis 1000000), sondern nur soweit, wie wir wirklich die Elemente ben¨otigen. Wir haben hier also eine anforderungsgesteuerte Auswertung und hierdurch eine Kombination von datenorientierter Programmstruktur 8erzeuge Daten, manipuliere Daten, akkumuliere) und von inkrementeller Auswertung (erzeuge Element, manipuliere dieses, erzeuge n¨achstes Element . . . ). Somit haben wir auch die Programmstruktur von der Auswertungsstruktur entkoppelt. Was zun¨achst nicht sonderlich spektakul¨ar erscheint, erlaubt uns jedoch im n¨ achsten Schritt die Nutzung von unendlich langen Str¨omen.

3.5.3 Implementierung der verz¨ ogerten Auswertung Die Befehle delay/force sind ziemlich m¨ achtig, aber relativ einfach zu implementieren. Wir suchen Ausdr¨ ucke, die nicht sofort ausgewertet werden, was uns genau zu Prozeduren f¨ uhrt. 1 2

( define ( delay o ) ( lambda ( ) o ) )

3 4 5

( d e f i n e ( f o r c e obj ) ( obj ))

3 Modularit¨at, Objekte, Zust¨ande Diese Implementierung ist simpel, hat jedoch einen Nachteil. Wenn wir Anwendungen nutzen, bei denen ein Strom mehrfach verwendet wird, so wertet wir mehrmals dieselben verz¨ ogerten Objekte aus. Wir k¨onnen das umgehen, indem wir die Ergebnisse bei der ersten Auswertung speichern und bei den weiteren Auswertungen dann jeweils das erste Ergebnis liefern. Diese sogenannten tabellierten Prozeduren implementieren wir nun: 1 2 3 4 5 6 7 8 9 10

( d e f i n e ( tab−proz p r o z ) ( l o c a l (( define bereits−ausgewertet f a l s e ) ( d e f i n e e r g e b n i s empty ) ) ( lambda ( ) ( i f bereits−ausgewertet ? ergebnis ( begin ( set ! e r g e b n i s ( p r o z ) ) ( set ! b e r e i t s − a u s g e w e r t e t ? t r u e ) ergebnis )))))

11 12 13

( define ( delay o ) ( tab−proz ( lambda ( ) o ) ) )

14 15 16

( d e f i n e ( f o r c e obj ) ( obj ))

3.5.4 Datenstr¨ ome unendlicher L¨ ange Bisher hatten wir nur die Auswertung von Teilen des Stroms gemacht, die wir wirklich gebraucht hatten. Falls also nur endliche Anteile eines Stroms ben¨otigt werden, kann der Stromrest durchaus beliebig oder gar unendlich groß sein. Betrachten wir als Beispiel einen Strom ganzer Zahlen: 1 2 3

( d e f i n e ( zahlen−von n ) ( cons−strom n ( zahlen−von (+ n 1 ) ) ) )

4 5

( d e f i n e a l l e − z a h l e n ( zahlen−von 0 ) ) Somit ist der Strom alle-zahlen tats¨achlich ein unendlich langer Strom. Um auf ein bestimmtes Stromelement nun zugreifen zu k¨onnen, schreiben wir uns eine weitere Prozedur.

1 2 3 4

( d e f i n e ( n−tes−strom n s ) ( i f (= n 0 ) ( kopf s ) ( n−tes−strom (− n 1 ) ( re st−s tr om s ) ) ) )

3.5 Datenstr¨ome (Streams)

Willkommen bei DrScheme, Version 372 [3m]. Sprache: Fortgeschritten angepasst. > (n-tes-strom 5 alle-zahlen) 5 Dabei k¨onnen unendliche Str¨ ome wie u ¨blich bearbeitet werden. Nehmen wir nun an, wir wollen den Strom aller Zahlen erhalten, die nicht durch 7 teilbar sind. 1 2 3

( define ( teilbar ? x y) (= ( re m ai n d e r x y ) 0))

4 5 6 7 8

( d e f i n e ohne−sieben ( f i l t e r ( lambda ( x ) ( not ( t e i l b a r ? x 7 ) ) ) alle−zahlen ))

Willkommen bei DrScheme, Version 372 [3m]. Sprache: Fortgeschritten angepasst. > (n-tes-strom 50 ohne-sieben) 59 Wir k¨onnen auch einen Strom mit s¨ amtlichen Fibonacci-Zahlen nun recht elegant erzeugen: 1 2 3 4

( d e f i n e ( fib−gen a b ) ( cons−strom a ( fib−gen b (+ a b ) ) ) )

5 6 7

( define fibs ( fib−gen 0 1 ) ) Hierbei handelt es sich tats¨ achlich um eine rekursive Definition, jedoch ohne die Iteration. Wir haben also eine lineare Laufzeit. Ein weiterer interessanter Strom w¨ are sicherlich der Strom aller Primzahlen. Dazu verwenden wir das Sieb des Eratosthenes. Idee ist folgende: • Konstruiere alle Zahlen von 2 an • Streiche im Reststrom alle durch 2 teilbaren Zahlen: 3,5,7,9,11,13. . . • Streiche im Reststrom alle durch 3 teilbaren Zahlen: 5,7,11,13. . .

3 Modularit¨at, Objekte, Zust¨ande • ... 1 2 3 4 5

( d e f i n e ( s i e b e strom ) ( cons−strom ( k o p f strom ) ( s i e b e ( f i l t e r ( lambda ( x ) ( not ( t e i l b a r ? x ( k o p f strom ) ) ) ) ( r es t−s tr om strom ) ) ) ) )

6 7

( d e f i n e p r i m z a h l e n ( s i e b e ( zahlen−von 2 ) ) )

Willkommen bei DrScheme, Version 372 [3m]. Sprache: Fortgeschritten angepasst. > (n-tes-strom 50 primzahlen) 253

3.5.5 Datenstr¨ ome ⇔ Lokale Zust¨ ande Was sind lokale Zust¨ ande? Allgemein sind das Gr¨oßen (Objekte), die sich zeitlich ver¨andern. Eine alternative Implementierung w¨are dann, wenn wir die Zust¨ande als Datenstrom von Werten darstellen. Dadurch k¨onnten wir set! vermeiden, sowie die daraus resultierenden Probleme der Zustandsumgebung. Dabei w¨ urden durch die relevante Auswertung nur die relevanten Zust¨ ande erzeugt. Nehmen wir dazu als Beispiel wieder unser Konto mit Abheben-Prozedur: 1 2 3 4 5 6 7

( d e f i n e ( konstr−abheben anfang ) ( l o c a l ( ( d e f i n e k o n t o s t a n d anfang ) ) ( lambda ( b e t r a g ) ( begin ( set ! k o n t o s t a n d (− k o n t o s t a n d b e t r a g ) ) kontostand ) ) ) )

Willkommen bei DrScheme, Version 372 [3m]. Sprache: Fortgeschritten angepasst. > (define k (konstr-abheben 200)) > (k 30) 170 > (k 40) 130 Um das nun alternativ zu implementieren, erhalten wir als Eingabe den Kontostand sowie den Strom der Abhebungen. Als Ausgabe gibt es dann einen Strom von Kontost¨anden.

3.5 Datenstr¨ome (Streams)

1 2 3 4 5 6

( d e f i n e ( strom−abheben k o n t o s t a n d betrag−strom ) ( cons−strom k o n t o s t a n d ( strom−abheben (− k o n t o s t a n d ( k o p f betrag−strom ) ) ( r es t−s tr om betrag−strom ) ) ) ) Wir haben somit eine wohldefinierte (mathematische) Funktion. Aus Benutzersicht weist diese Implementierung das gleiche Verhalten auf, wie die Implementierung mit lokalen Zust¨anden, doch arbeiten wir hier ohne set!. Als weiteres Beispiel schauen wir uns die Monte-Carlo-Simulation an. Diese sah damals folgendermaßen aus:

1 2 3 4 5 6 7

( define zufall ( local (( define x zufall−init )) ( lambda ( ) ( begin ( set ! x ( zufall−aktuell x)) x)))) Nun implementieren wir die Monte-Carlo-Simulation mit einem Strom von Zufallszahlen:

1 2 3 4 5

( define zufalls−zahlen ( cons−strom zufall−init ( abb z u f a l l − a k t u e l l zufalls−zahlen ))) Nun wenden wir den Cesaro-Test auf einem Strom von Zufallszahlen an. Dazu ben¨otigen wir eine Abbildung f¨ ur die bin¨ are Abbildung aufeinanderfolgender Stromelemente. Wir nehmen im folgenden an, dass der mitgelieferte Strom unendlich lang ist.

1 2 3 4 5 6

( d e f i n e ( abb−paare f s ) ( cons−strom ( f ( k o p f s ) ( k o p f ( r es t−s tr om s ) ) ) ( abb−paare f ( r es t−s tr om ( re s t−s tro m s ) ) ) ) ) Nun erzeugen wir einen Strom der Ergebnisse des Cesaro-Tests.

1 2 3 4

( d e f i n e cesaro−strom ( abb−paare ( lambda ( z1 z2 ) (= ( ggT z1 z2 )

3 Modularit¨at, Objekte, Zust¨ande 1)) zufallszahlen ))

5 6

Der Ergebnisstrom wird dann durch die Monte-Carlo-Methode ausgewertet. 1 2 3 4 5 6 7 8

( d e f i n e ( monte−carlo e x p e r i m e n t e aw a f ) ( l o c a l ( ( d e f i n e ( n a e c h s t e s aw a f ) ( cons−strom ( / aw (+ aw a f ) ) ( monte−carlo ( r es t−s tr om e x p e r i m e n t e ) aw−af ) ) ) ) ( i f ( kopf experimente ) ( n a e c h s t e s (+ aw 1 ) a f ) ( n a e c h s t e s aw (+ a f 1 ) ) ) ) )

9 10 11 12 13

( d e f i n e pi−strom ( abb ( lambda ( p ) ( sqrt ( / 6 p ) ) ) ( monte−carlo cesaro−strom 0 0 ) ) ) Auff¨ allig ist, dass wir hier keine feste Anzahl von Experimenten haben. Außerdem gibt es auf diese Weise eine stetige Verbesserung des Wertes f¨ ur pi. Die Kontrolle erfolgt dann ¨ u ¨ber Prozeduren wie zum Beispiel n-tes-strom. Wir k¨onnen also zeitliche Anderungen durch Str¨ ome modellieren. Dadurch vermeiden wir die theoretischen Probleme durch die Zustands¨ anderungen. Auch die logischen Schlussfolgerungen sind komplexer bei Zustands¨ anderungen. Da sich auch der Wert einer Variablen vor der Zuweisung bei Zustands¨ anderungen von dem Wert der Variable nach der Zuweisung unterscheidet, ist die strukturelle Induktion nicht ohne weiteres m¨oglich. Grunds¨ atzlich haben funktionale Programmiersprachen den Vorteil, dass die Prozeduren im Grunde mathematischen Funktionen mit ihren Argumenten entsprechen. Wir haben dann auch keine Zuweisungen mehr und k¨onnen uns eine rein funktionale Programmiersprache wie SCHEME vorstellen - nur ohne set!. Bei einer rein funktionalen Programmiersprache w¨ aren die Korrektheitsbeweise einfacher und sie w¨aren hochgradig f¨ ur Parallelverarbeitung geeignet, da kein gemeinsamer Zugriff auf Daten erfolgt und somit keine Synchronisationsprobleme auftreten k¨onnen. Das Problem, das nun aber besteht, ist das, ob Zuweisungen u ¨berhaupt vermeidbar sind. Im Grunde schon, aber bei interaktiven Systemen wird dies schon schwieriger. Betrachten wir dazu als Beispiel wieder unser Bankkonto, das von Peter und Paul gemeinsam genutzt wird. Objektorientiert hieße das, dass es sich bei dem Bankkonto um ein Objekt mit Zustand handelt, das auf Nachrichten von Peter und Paul reagiert. Stromorientiert hieße das, dass das Bankkonto eine Funktion ist, welche einen Strom von Nachrichten verarbeitet. Wie liefern nun aber sowohl Peter als auch Paul Nachrichten an Eingabestr¨ omen? Eine m¨ogliche L¨osung w¨are das Mischung der Nachrichten. Dies d¨ urfte aber nicht abwechselnd geschehen, da Peter und Paul nicht gleich oft auf das Bankkonto zugreifen. Ben¨ otigt w¨ urde also ein fairer, nicht deterministischer Mischer. Dieser w¨ urde, falls vorhanden, aus einem der beiden Eingabestr¨omen eine Eingabe neh-

100

3.5 Datenstr¨ome (Streams) men, sofern diese vorhanden ist, und dann fair zwischen den Eingabestr¨omen hin und her wechseln. Dazu w¨ are aber eine Erweiterung der rein funktionalen Sprache notwendig. Weitere Nachteile der stromorientierten Modelle sind, dass jede Komponente (jedes Objekt) Eingaben und Ausgaben besitzt. Falls die Aufteilung nicht direkt gegeben ist, wird es problematisch. Daazu br¨ auchte man dann schon logische Sprachen. Zusammengefasst kann man sagen, dass es kein universelles Programmierparadigma gibt, sondern Zustandsorientierte, funktionale, objektorientierte, relationale etc. Es gibt keine universelle Programmiersprache, denn je nachdem wie das Problem liegt, muss die Programmiersprache gew¨ ahlt werden.

101

3 Modularit¨at, Objekte, Zust¨ande

102

4 Einfu ¨hrung in JAVA 4.1 Allgemeines SCHEME verf¨ ugt u ¨ber eine einfache Syntax, flexible Sprache, Abstraktionen und kompakte Programme. F¨ ur die Entwicklung großer Systeme ist jedoch noch etwas mehr notwendig. • Gleiche Programmiertechniken (Abstraktionen) • Mehr Programmiersicherheit:Programmobjekte deklarieren mit (redundanten)Informationen ¨ • Der Compiler u uft selbige und findet Fehler zur Ubersetzungszeit ¨berpr¨ JAVA • ist eine imperative, objektorientierte Sprache • verf¨ ugt u ¨ber Typdeklarationen • verf¨ ugt u ¨ber Module • kann Prozesse/Netzwerkprogrammierung verwalten • ist plattformunabh¨ anig • verf¨ ugt u ufung ¨ber eine Sicherheitspr¨ • verf¨ ugt u ¨ber eine automatische Speicherverwaltung Das Grundkonstrukt eines jeden JAVAprogramms sieht folgendermaßen aus: 1 2 3 4 5 6 7

c l a s s HelloWorld { public s t a t i c void main ( S t r i n g [ ] a r g ) { System . out . p r i n t l n ( ” H e l l o World ! ” ) ; } } Dieses Programm wird zun¨ achst in plattformunabh¨angigen Code u ¨bersetzt, der dann schließen gestartet werden kann.

103

4 Einf¨ uhrung in JAVA

4.2 Ausdr¨ ucke und Anweisungen Kommentare: • // bis zum Zeilenende ¨ • /* Uber mehrere Zeilen*/ • /** Kommentare f¨ ur automatische Dokumentation mit javadoc */ Namen: • beginnen mit Buchstaben • gefolgt von Buchstaben, Ziffern, Unterstrich, Dollarzeichen • casesensitiv Konstanten: • je nach Datentyp: streng getypte Sprache

4.2.1 Grundtypen in JAVA Typname boolean char byte short int long float double String

Werte false, true 16-Bit-Unicode 8-Bit ganze, vorzeichenbehaftete Zahl 16-Bit ganze, vorzeichenbehaftete Zahl 32-Bit ganze, vorzeichenbehaftete Zahl 64-Bit ganze, vorzeichenbehaftete Zahl 32-Bit Gleitkommazahl 64-Bit Gleitkommazahl Zeichenketten

Initialwert false 0000 0 0 0 0 0.0 0.0

Im Gegensatz zu SCHEME wird unter JAVA nicht die Pr¨afix, sondern die Infixnotation verwendet. Das bedeutet im Gegenzug, dass Schreibweisen bei unzureichend gesetzten Klammern mehrdeutig sind. Um dies zu vermeiden gibt es sogannte Operatorpr¨ aferenzen, die in verschiedenen Tabellen aufgelistet sind. Unter JAVA sind Variablen lediglich Namen f¨ ur ver¨anderbare Speicherzellen. Dabei ist relevant, dass die Ver¨ anderung der Variablen in Anweisung geschieht. Elementare Anweisungen sind zum Beispiel die Zuweisung eines Wertes an eine Variable. Dies geschieht z.B. durch x=5;. Verzweigungen funktionieren ¨ahnlich wie in SCHEME, nur dass nicht zwingend ein Else-Zweig ben¨otigt wird. Auch werden die einzelnen Zweige i.d.R. durch geschweifte Klammern eingeklammert. Zur mehrfachen Fallunterscheidung gibt es das Switch-Konstrukt:

104

4.3 Typisierung

1 2 3 4 5 6 7

s w i c h ( ausdruck ) { case k1 : a1 ; break ; ... case kn : an ; break ; default an + 1 } Es gibt in JAVA auch mehrere Schleifentypen:

while

( ausdruck ) anweisung

2 3

do anweisung while ( ausdruck )

4 5

for ( i n i t ; bexp ; i e x p ) anweisung Mit break wird die aktuelle Schleife, bzw. Switch-Anweisung verlassen, mit continue wird der Schleifenrumpf verlassen und erst die n¨achste Iteration wieder gewertet. Mit return (optionaler ausdruck) wird der Prozedurrumpf verlassen.

4.3 Typisierung Ein typischer Fehler in SCHEME-Programmen ist der Laufzeitfehler u ¨nbound variable”. Dies kann in JAVA so nicht auftreten, da dort alle im Programm verwendeten Namen vorher deklariert werden m¨ ussen (falls diese noch nicht vordefiniert sind). Ein weiterer Fehler in SCHEM-Programmen sind unpassende Typen. Auch dies kann unter JAVA ¨ nicht passieren, da dort die Probleme schon beim Ubersetzen identifiziert werden. Jedes Objekt hat einen festen Typ, der bei der Deklaration angegeben wird. Generell werden Variablen in der Form ¡typ¿ ¡name¿ oder ¡typ¿ ¡name¿ = ¡Initialwert¿ deklariert. Dabei k¨onnen auch mehrere Namen hintereinander stehen. Zum Deklarieren von Konstanten wird lediglich das Schl¨ usselwort final davor gef¨ ugt. Die Anforderung an Zuweisungen der Art x = y ist, dass der Typ von y (verlustfrei) in den Typ von x umwandelbar sein muss. Jeder Wert von y muss also auch ein m¨oglicher Wert von x sein. 1 2

int i =12; double x = 1 . 5 ;

3 4 5 6 7

x i i i

= i ; // z u l ¨ assig = x ; // u n z u l ¨ assig = ( int ) x ; // z u l ¨ a s s i g , aber v e r l u s t b e h a f t e t =true ; // u n z u l ¨ assig

Bestimmte SCHEME-Programmiertechniken wie zum Beispiel die Nachrichtenweitergabe sind nicht anwendbar, daher ist zum Beispiel die Nachrichtenweitergabe selbst in

105

4 Einf¨ uhrung in JAVA JAVA schon fest eingebaut.

4.3.1 Felder Felder (engl. Arrays) sind geordnete Mengen von indizierten Variablen. Es handelt sich also sozusagen um eine Abbildung [0 . . . n] → V ariable ind ist vergleichbar zu einer Tabelle, jedoch mit einem festen Indexbereich. Deklariert werden Arrays zum Beispiel durch int[] a; F¨ ur die Erzeugung gibt es zwei M¨oglichkeiten. Entweder man generiert diese dynamisch durch z.B. a = new int[100] oder mit einem fixen Initialwert wie z.B. a ={1,2,3,4,5,17,32}. Der Zugriff auf die einzelnen Feldelemente geschieht durch a[i], wobei i der Index ist. Nehmen wir als Beispiel, wir wollen alle Feldelemente aufsummieren: 1 2

int [ ] a = \ { 1 , 2 , 4 , 8 , 1 6 \ } ; int s = 0 ;

3 4 5

fo r ( int i = 0 ; i < 5 ; i ++) s += a [ i ] ; Es sind auch mehrdimensionale Felder m¨oglich: int[][] m = new int[5][10]. Funktionen und Prozeduren bestehen in JAVA nur in Kombination mit Objekten. Methoden bestehen dabei aus dem Funktionsnamen, dem Ergebnistyp (bzw. void bei Prozeduren), den Parametertypen und -namen sowie dem eigentlichen Rumpf.

1 2 3 4

int quadrat ( int x ) { return x∗x ; }

5 6

int x = quadrat ( 3 ) ; Die Prozeduraufrufe funktionieren ansonsten wie in SCHEME, aber die aktuellen Parameter m¨ ussen ebenfalls in die formalen Parameter typkonvertierbar sein. Der Ergebnistyp void liefert, wie bereits gesagt, kein Ergebnis.

1 2 3 4

void d i s p l a y ( int x ) { System . out . p r i n t l n ( x ) ; }

5 6 7

int z = 9 9 ; display ( z );

106

4.4 Klassen und Objekte

4.4 Klassen und Objekte Ein JAVA-Programm entspricht im Grunde nur einer Definition von Klassen. Die Ausf¨ uhrung geschieht dabei durch das Senden von Nachrichten (z.B. als erstes an die Funktion ”main”der Hauptklasse). Objekte haben lokale Zust¨ande (Attribute), sie verstehen Nachrichten (z.B. Bankkonto) und haben eine Struktur sowie ein Verhalten, dass in Klassen definiert ist. Klassen beschreiben also die Merkmale der Objekte eines Typs. Sie enthalten Variablendeklarationen, Methodendeklarationen und Konstruktordeklarationen. Die generelle Struktur sieht wie folgt aus: 1 2 3

class C {

C( . . . ) { }

5 6 7 8 9

10 11

} Die Bedeutung ist ¨ ahnlich wie die Nachrichtenweitergabe in SCHEME, allerdings entf¨allt nun die ßuteilenFunktion. Konstruktoren sind Prozeduren (ohne void) mit gleichem Namen der Klasse und werden beim Objekterzeugen aufgerufen. Die Objekterzeugung geschieht in JAVA durch new C(...). Zur¨ uckgeliefert wird eine Referenz auf das neu entstandende Objekt. Eine Nachricht m wird an das Objekt o durch o.m(...) gesendet. Generell k¨onnen Variablendeklarationen etc. mit einem Modifizierer wie public, private, static, protected etc. versehen werden, welche die Sichtbarkeit nach außen steuert.

1 2 3 4 5 6 7

c l a s s Konto { int k o n t o s t a n d ; // l o k a l e r Zustand Konto ( int i ) { kontostand = i ; } // K o n s t r u k t o r

8 9 10 11 12 13 14 15

public int k o n t o s t a n d ( ) { // Methode return k o n t o s t a n d ; } public void abheben ( int b e t r a g ) {

107

4 Einf¨ uhrung in JAVA i f ( b e t r a g >k o n t o s t a n d ) System . out . p r i n t l n ( ”Konto n i c h t g e d e c k t ! ” ) ; else k o n t o s t a n d −= b e t r a g ;

16 17 18 19

} public void e i n z a h l e n ( int b e t r a g ) { k o n t o s t a n d += b e t r a g ; } public s t a t i c void main ( S t r i n g [ ] a r g s ) { Konto k = new Konto ( 1 0 0 ) ; System . out . p r i n t l n ( ” Kontostand : ” + k . k o n t o s t a n d ( ) ) ; k . einzahlen (10); System . out . p r i n t l n ( ” Kontostand : ” + k . k o n t o s t a n d ( ) ) ; k . abheben ( 1 3 0 ) ; System . out . p r i n t l n ( ” Kontostand : ” + k . k o n t o s t a n d ( ) ) ; }

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

}

35 36 37 38 39 40 41 42 43 44 45 46 47

c l a s s P r i v a t k o n t o extends Konto { int gebuehren = 1 0 ; P r i v a t k o n t o ( int i ) { super ( i ) ; } public void g e b u e h r e n E i n z i e h e n ( ) { k o n t o s t a n d −= gebuehren ; } }

48 49 50 51 52 53 54 55 56 57 58

c l a s s A u s b i l d u n g s k o n t o extends P r i v a t k o n t o { A u s b i l d u n g s k o n t o ( int i ) { super ( i ) ; } public void g e b u e h r e n E i n z i e h e n ( ) { } }

108

4.4 Klassen und Objekte Nehmen wir nun als Beispiel die Durchnummerierung aller Bankkonten: 1 2 3 4

c l a s s Konto { int kontostand , kontonr ; private s t a t i c int l f d n r = 0 ;

konto ( int i ) { kontostand = i ; kontonr = l f d n r ; l f d n r ++; }

6 7 8 9 10 11 12

} Klassen umfassen Werte (also die lokalen Zust¨ande) und die Operationen. Somit sind SCHEME-Strukturen mitsamt der Operationen als Klassen darstellbar. Nehmen wir dazu als Beispiel, wie wir Listen in JAVA darstellen k¨onnen:

1 2 3 4

class List { int f i r s t ; List rest ;

L i s t ( int f , L i s t r ) { first = f ; rest = r ; }

6 7 8 9 10 11

int l a s t ( ) { i f ( r e s t == null ) { return f i r s t ; } else { return r e s t . l a s t ( ) ; } }

12 13 14 15 16 17 18 19 20 21 22 23

} In JAVA muss jedes Objekt erst explizit erzeugt werden. Leere Listen stellen wir u ¨brigens mit dem leeren Pointer null da.

109

4 Einf¨ uhrung in JAVA

4.5 Vererbung Die Wiederverwertbarkeit von bereits existenten Programmteilen haben wir bisher haupts¨ achlich durch universelle Programmierung (und durch das Benutzen Prozeduren h¨oherer Ordnung), sowie durch Copy/Paste erreicht. Letzteres ist jedoch zum einen fehleranf¨ allig, außerdem unlesbar und unwartbar. Eine wesentlich strukturiertere L¨osung ist die sogenannte Vererbung. Dabei werden Merkmale einer bereits existierenden Oberklasse A in eine Unterklasse B u ¨bernommen. Außerdem k¨onnten dann zus¨atzliche Merkmale in B implementiert werden, beziehungsweise bereits existierende abge¨andert werden. Es wer¨ den also lediglich die Anderungen beschrieben. Mit der Vererbung erreichen wir i.d.R. eine u ¨bersichtlichere Struktur und eine gute Modellierung. Zu beachten ist, dass z.B. Konstruktoren nicht mitvererbt werden. Wir k¨onnen jedoch den Konstruktorrumpf der Oberklasse benutzen (mit super). Wenn wir explizit die eigene Klasse ansprechen wollen, so nutzen wir das Schl¨ usselwort this. Die Vererbung einer Klasse funktioniert u usselwort extens: ¨ber das Schl¨ 1 2 3 4

c l a s s B extends A { ¨ // Erweiterungen , Anderungen } Unter JAVA ist somit auch die Redefinition von Methoden m¨oglich. Dabei hat zum Beispiel die Methode in der Unterklasse Bdenselben Namen und die gleichen Parameter wie die Methode in der Oberklasse A, sodass die Methode u ¨berdeckt wird. Auch das soge¨ nannte Uberladen ist m¨ oglich. Dabei haben zwar zwei1 Methoden den gleichen Namen, jedoch insgesamt eine unterschiedliche Signatur.

1 2

class C { int i d ( int x ) { return x ; }

3 4 5 6 7

int i d ( double x ) { return −x ; }

8 9 10 11 12

}

Oder auch mehr.

110

4.6 Schnittstellen und Pakete

4.6 Schnittstellen und Pakete Schnittstellen2 sind im Grunde abstrakte Klassen ohne Implementierung. S¨amtliche Methoden haben also keinen Rumpf und s¨ amtliche Attribute sind (implizit) final static also Konstanten. Somit liegt es dann an der Klasse, welche die Schnittstellen einbindet, wie die Methoden schließlich implementiert werden. Dabei kann eine Klasse beliebig viele Schnittstellen implementieren - im Gegensatz zur Vererbung, wobei lediglich von einer Klasse geerbt werden kann. Insgesamt dient das Prinzip von Interfaces der Strukturierung. 1 2 3 4 5 6 7 8 9 10 11 12

i n t e r f a c e Lookup { Object lookup ( S t r i n g name ) ; } interface I n s e r t { Object i n s e r t ( S t r i n g name , Object v a l u e ) ; } c l a s s MyTable implements Lookup , I n s e r t { ... } Mit Ausnahme des Schl¨ usselworts new k¨ onnen Schnittstellen im Grunde wie Klassen benutzt werden. So kann im obigen Beispiel eine Prozedur etwa als Parameter ein Objekt des Typs Lookup erhalten. Pakete dienen der Strukturierung von Klassenansammlung. Dabei werden mehrere Klassen zuu einer gr¨ oßeren Einhgeit zusammengefasst. Jede Klasse geh¨ort dann zu einem Paket: Dazu wird der Paketname zu Klassenbeginn angegeben. Jede Klasse kann somit eindeutig u ¨ber den Paketnamen angesprochen werden. So werden auch gleichzeitig Namenkonflikte vermieden.

4.7 Weitere Aspekte von JAVA JAVA verf¨ ugt auch u oglichkeit der Generizit¨at. Somit k¨onnten Klassen auch ¨ber die M¨ Typparameter enthalten. Dies wird am Beispiel einer Klasse Liste gezeigt, wobei alle Elemente vom gleichen Typ T sind: 1 2 3 4

c l a s s L i s t e { T first ; L i s t r e s t ; 2

Auch Interfaces genannt

111

4 Einf¨ uhrung in JAVA ...

5 6

}

7 8

... L i s t l i s t ; s l i s t = new L i s t e ( ) ; s l i s t . f i r s t = new Student ( ) ;

9 10 11 12

... Weiterhin verf¨ ugt JAVA auch die M¨oglichkeit zur mehrl¨aufigen, beziehungsweise nebenl¨ aufigen Programmierung mit Threads.

112

5 Zusammenfassung In der gesamten Vorlesung wurden wichtige Aspekte der Programmierung gezeigt: • Die Entwicklung einer guten Programmstruktur • Der Schichtenentwurf von Programme. Dazu wurden verwendet: ADT Objekte Module Pakete • Bildung von Abstraktionen: Funktionen/Prozeduren: Die konkreten Verfahren wurden abstrahiert. Abstrakte Daten: Konkrete Darstellung Objekte:Darstellung + Verfahren wurden abstrahiert • Unn¨otige Komplexit¨ aten vermeiden: Keine globalen Variablen ver¨ andern, falls nicht unbedingt notwendig Keine Funktionen mit Seiteneffekten, sondern Prozeduren mit (begin...) Keine iterativen Verfahren, wenn rekursive Verfahren verst¨andlich und ausreichend sind.

ist der unterschied zwischen dem prozeduraufruf und der prozeduranwendung