14 DRY: Abstraktion überall!

Dieser Teil des Skripts basiert auf [HTDP/2e] Part III

Wir haben bereits in Abschnitt DRY: Don’t Repeat Yourself! das "Don’t Repeat Yourself" Prinzip kennengelernt: Gute Programme sollten keine Wiederholungen enthalten und nicht redundant sein. Wir haben gelernt, dass wir diese Redundanz durch verschiedene Abstraktionsmechanismen beseitigen können.

In diesem Abschnitt werden wir zunächst diese bereits bekannten Abstraktionsmechanismen nochmal Revue passieren lassen. Allerdings sind diese Mechanismen nicht für alle Arten von Redundanz geeignet. Wir werden in diesem Kapitel daher weitere mächtige Abstraktionsmechanismen kennenlernen. Hierzu brauchen wir neue Sprachkonzepte, die Sie bitte durch das Umschalten auf den "Zwischenstufe mit Lambda" Sprachlevel aktivieren.

Unsere Programmiersprache wird hierdurch erstmal komplexer. Am Ende des Kapitels werden wir sehen, dass es allerdings eine so mächtige Art der Abstraktion gibt, dass wir damit viele andere Abstraktionsarten damit subsumieren können. Dies wird die Sprache konzeptuell wieder vereinfachen.

14.1 Abstraktion von Konstanten

Die wohl einfachste Art der Abstraktion ist anwendbar, wenn es in einem Programm an mehreren Stellen Ausdrücke gibt, die konstant sind, also immer zum gleichen Wert auswerten. Der Abstraktionsmechanismus, den wir in diesem Fall verwenden können, ist die Definition von Konstanten. Diese Möglichkeit haben wir bereits ausführlich im Abschnitt DRY: Don’t Repeat Yourself! besprochen.

14.2 Funktionale Abstraktion

Häufig gibt es in einem Programm die Situation, dass an vielen Stellen Ausdrücke vorkommen, die nicht gleich sind, aber sich nur in einigen Stellen in den verwendeten Werten unterscheide.

Beispiel:

; (list-of String) -> Boolean

; does l contain "dog"

(define (contains-dog? l)

(cond

[(empty? l) false]

[else

(or

(string=? (first l) "dog")

(contains-dog?

(rest l)))]))

; (list-of String) -> Boolean

; does l contain "cat"

(define (contains-cat? l)

(cond

[(empty? l) false]

[else

(or

(string=? (first l) "cat")

(contains-cat?

(rest l)))]))

Die Ausdrücke in den beiden Funktionsbodies sind bis auf den String "dog" beziehungsweise "cat" gleich.

Gute Programmierer sind zu faul, viele ähnliche Ausdrücke und Funktionen zu schreiben. Für die Elimination dieser Art von Redundanz ist funktionale Abstraktion geeignet:

; String (list-of String) -> Boolean

; to determine whether l contains the string s

(define (contains? s l)

(cond

[(empty? l) false]

[else (or (string=? (first l) s)

(contains? s (rest l)))]))

Falls gewünscht, können contains-dog? und contains-cat? auf Basis dieser Funktion wieder hergestellt werden:

Wenn Sie einmal contains? definiert haben, wird es nie wieder nötig sein, eine Funktion ähnlich wie die erste Variante von contains-dog? zu definieren.

14.3 Funktionen als Funktionsparameter

Betrachten Sie folgenden Code:

; (list-of Number) -> Number

; adds all numbers in l

(define (add-numbers l)

(cond

[(empty? l) 0]

[else

(+ (first l)

(add-numbers (rest l)))]))

; (list-of Number) -> Number

; multiplies all numbers in l

(define (mult-numbers l)

(cond

[(empty? l) 1]

[else

(* (first l)

(mult-numbers (rest l)))]))

In diesem Beispiel haben wir eine ähnliche Situation wie bei contains-dog? und contains-cat?: Beide Funktionen unterscheiden sich nur an zwei Stellen: a) Im empty? Fall wird einmal 0 und einmal 1 zurückgegeben. b) Im anderen Fall wird einmal addiert und das andere mal multipliziert.

Der Fall a) ist völlig analog zu contains-dog? und contains-cat? lösbar, indem wir diesen Wert als Parameter übergeben.

Eine andere Situation haben wir im Fall b). Hier unterscheiden sich die Funktionen nicht in einem Wert, sondern im Namen einer aufgerufenen Funktion! Hierzu brauchen wir eine neue Art der Abstraktion, nämlich die Möglichkeit, Funktionen als Parameter an andere Funktionen zu übergeben.

Wenn wir mal einen Augenblick lang dieses Problem ignorieren und einfach auf gut Glück das offensichtliche tun:

(define (op-numbers op z l)

(cond

[(empty? l) z]

[else

(op (first l)

(op-numbers (rest l) z))]))

(define (add-numbers l) (op-numbers + 0 l))

(define (mult-numbers l) (op-numbers * 1 l))

... so stellen wir fest, dass wir tatsächlich über Funktionen genau so abstrahieren können wie über Werte! Wir können also Funktionen als Parameter übergeben und diese Parameter an der ersten Position eines Funktionsaufrufs verwenden!

Das entscheidende an op-numbers ist nicht, dass add-numbers und mult-numbers nun Einzeiler sind. Der entscheidende Punkt ist, dass wir nun eine sehr mächtige abstrakte Funktion geschaffen haben, die wir nun universell auch für viele andere Dinge benutzen können.

Zum einen können wir feststellen, dass op-numbers überhaupt keinen Code mehr enthält, der spezifisch für Zahlen ist. Das deutet darauf hin, dass wir die Funktion auch mit Listen anderer Werte verwenden können. Der Name op-numbers ist daher irreführend und wir benennen die Funktion um:

(define (op-elements op z l)

(cond

[(empty? l) z]

[else

(op (first l)

(op-elements op z (rest l)))]))

Zum anderen können wir als Parameter für op nicht nur primitive, sondern auch beliebige selber definierte Funktionen übergeben.

Schauen wir uns an einigen Beispielen an, was man mit op-elements alles machen kann:

Wir können Bilder komponieren:

> (op-elements beside empty-image (list (circle 10 "solid" "red")                                         (rectangle 10 10 "solid" "blue")                                         (circle 10 "solid" "green")))

Wir können eine Liste kopieren, was alleine nicht sehr nützlich ist:

> (op-elements cons empty (list 5 8 12 2 9))

'(5 8 12 2 9)

...aber zeigt, dass wir mit leichten Variationen davon andere interessante Dinge tun können. Beispielsweise können wir zwei Listen aneinanderhängen:

(define (append-list l1 l2)

(op-elements cons l2 l1))

> (append-list (list 1 2) (list 3 4))

'(1 2 3 4)

Wir können aus einer Liste von Listen eine Liste machen:

> (op-elements append-list empty (list (list 1 2) (list 3 4) (list 5 6)))

'(1 2 3 4 5 6)

Und schliesslich, als etwas fortgeschrittenes Beispiel, können wir mit op-elements eine Liste von Zahlen sortieren. Zu diesem Zweck benötigen wir eine Hilfsfunktion, die eine Zahl in eine Liste sortierter Zahlen einfügt:

> (op-elements insert empty (list 5 2 1 69 3 66 55))

'(1 2 3 5 55 66 69)

Übrigens geht es beim Entwurf von Funktionen wie op-elements nicht nur um die Wiederverwendung von Code, sondern auch um die "Wiederverwendung" von Korrektheitsargumenten. Betrachten Sie beispielsweise die Frage, ob ein Programm terminiert oder vielleicht eine Endlosschleife enthält. Dies ist einer der häufigsten Fehler in Programmen und bei Schleifen, wie bei den Beispielen oben, immer ein potentielles Problem. Wenn wir einmal zeigen, dass op-elements terminiert, so wissen wir, dass alle Schleifen, die wir mit Hilfe von op-elements bilden, auch terminieren (sofern die Funktion, die wir als Argument übergeben, terminiert). Wenn wir nicht op-elements benutzen würden, müssten wir diese Überlegung jedes mal aufs neue anstellen.

14.4 Abstraktion in Signaturen, Typen und Datendefinitionen

14.4.1 Abstraktion in Signaturen

Redundanz kann auch in Signaturen auftreten, und zwar in dem Sinne, dass es viele Signaturen für den gleichen Funktionsbody geben kann.

Betrachten wir zum Beispiel die Funktion second, die das zweite Element aus einer Liste von Strings berechnet:

; (list-of String) -> String

(define (second l) (first (rest l)))

Hier ist eine Funktion, die das zweite Element aus einer Liste von Zahlen berechnet:

; (list-of Number) -> Number

(define (second l) (first (rest l)))

Die Funktionsdefinitionen sind bis auf die Signatur identisch. Wir könnten, um den Code nicht zu duplizieren, mehrere Signaturen zu der gleichen Funktion schreiben:

; (list-of String) -> String

; (list-of Number) -> Number

(define (second l) (first (rest l)))

Offensichtlich ist dies aber keine sehr gute Idee, weil wir die Liste der Signaturen erweitern müssen, immer wenn die Funktion mit einem neuem Elementtyp verwendet werden soll. Es ist auch nicht möglich, alle Signaturen hinzuschreiben, denn es gibt unendlich viele, z.B. folgende unendliche Sequenz von Signaturen:

; (list-of String) -> String

; (list-of (list-of String)) -> (list-of String)

; (list-of (list-of (list-of String))) -> (list-of (list-of String))

; (list-of (list-of (list-of (list-of String)))) -> (list-of (list-of (list-of String)))

; ...

Wir haben jedoch bereits informell einen Abstraktionsmechanismus kennengelernt, mit dem wir diese Art von Redundanz eliminieren können: Typvariablen. Eine Signatur mit Typvariablen steht implizit für alle möglichen Signaturen, die sich ergeben, wenn man die Typvariablen durch Typen ersetzt. Wir kennzeichnen Namen als Typvariablen, indem wir den Namen der Typvariablen in eckige Klammern vor die Signatur setzen. In der Signatur können wir dann die Typvariable verwenden. Hier ist das Beispiel von oben mit Typvariablen:

; [X] (list-of X) -> X

(define (second l) (first (rest l)))

; (list-of Number) -> String

steht, aber dies ist keine gültige Signatur für second.

14.4.2 Signaturen für Argumente, die Funktionen sind

Wir haben in diesem Kapitel die Möglichkeit eingeführt, Funktionen als Parameter an andere Funtionen zu übergeben. Wir wissen aber noch nicht, wie wir Signaturen solcher Funktionen beschreiben.

Dieses Problem lösen wir dadurch, dass wir es zulassen, Signaturen als Typen zu verwenden. Betrachten wir beispielsweise eine Funktion, die ein Bild mit einem Kreis kombiniert, aber die Art, wie es kombiniert werden soll, zu einem Parameter der Funktion macht:

(define (add-circle f img)

(f img (circle 10 "solid" "red")))

Beispielsweise kann diese Funktion so verwendet werden:

> (add-circle beside (rectangle 10 10 "solid" "blue"))

oder so:

> (add-circle above (rectangle 10 10 "solid" "blue"))

Die Signatur von add-circle können wir nun so beschreiben:

; (Image Image -> Image) Image -> Image

(define (add-circle f img)

(f img (circle 10 "solid" "red")))

Diese Signatur sagt aus, dass der erste Parameter eine Funktion mit der Signatur Image -> Image sein muss. Wir verwenden also nun Signaturen als Typen oder, anders gesagt, wir unterscheiden nicht mehr zwischen Signaturen und Typen.

Funktionen können nicht nur Funktionen als Argumente bekommen, sondern auch Funktionen als Ergebnis zurückliefern. Beispiel:

; Color -> Image

(define (big-circle color) (circle 20 "solid" color))

; Color -> Image

(define (small-circle color) (circle 10 "solid" color))

; String -> (Color -> Image)

(define (get-circle-maker size)

(cond [(string=? size "big") big-circle]

[(string=? size "small") small-circle]))

Die Funktion get-circle-maker können wir nun aufrufen und sie liefert eine Funktion zurück. Das bedeutet, dass wir einen Aufruf von get-circle-maker an der ersten Position eines Funktionsaufrufs haben können. Bisher stand an dieser Position immer der Name einer Funktion oder (seit wir Funktionen als Parameter kennen) Namen von Funktionsparametern.

Beispiel:

> ((get-circle-maker "big") "cyan")

Beachten Sie in dem Beispiel die Klammersetzung: Dieser Aufruf ist ein Funtionsaufruf einer Funktion mit einem Parameter. Die Funktion, die wir aufrufen, ist (get-circle-maker "big") und ihr Parameter ist "cyan". Dies ist also etwas völlig anderes als der ähnlich aussehende, in diesem Beispiel aber unsinnige Ausdruck (get-circle-maker "big" "cyan").

14.4.3 Funktionen höherer Ordnung

Funktionstypen können beliebig verschachtelt werden. Nehmen wir beispielsweise an, wir haben noch andere Funktionen mit der gleichen Signatur wie add-circle, zum Beispiel add-rectangle. Eine Funktion, die wir mit einer dieser Funktionen parametrisieren können, ist zum Beispiel:

Funktionen, in deren Signatur nur ein einziger Pfeil vorkommt (also Funktionen, die keine Funktionen als Parameter haben oder zurückgeben), heißen in diesem Kontext auch Funktionen erster Ordnung oder first-order functions. Beispiele für Funktionen erster Ordnung sind circle oder cons. Funktionen, die Funktionen als Parameter bekommen oder als Ergebnis zurückgeben, nennt man auch Funktionen höherer Ordnung oder higher-order functions. Beispiele für Funktionen höherer Ordnung sind add-circle und add-two-imgs-with.

Manchmal unterscheidet man bei Funktionen höherer Ordnung noch, was die maximale Schachtelungstiefe der Funktionspfeile in den Argumenten einer Funktion ist. Beispielsweise nennt man add-circle eine Funktion zweiter Ordnung und add-two-imgs-with eine Funktion dritter Ordnung.

In der alltäglichen Programmierung sind Funktionen zweiter Ordnung sehr häufig, aber Funktionen von drittem und höherem Grad werden recht selten gebraucht.

14.4.4 Polymorphe Funktionen höherer Ordnung

Auch polymorphe Funktionen können Funktionen höherer Ordnung sein. Wir haben bereits die Funktion op-elements oben kennengelernt. Schauen wir uns an, mit welchen Typen sie in den Beispielen verwendet wird.

; [X] (X X -> X) X (list-of X) -> X

(define (op-elements op z l)

(cond

[(empty? l) z]

[else

(op (first l)

(op-elements op z (rest l)))]))

Allerdings passt diese Signatur nicht zu allen Beispielen von oben. Beispielsweise benötigen wir für das (op-elements cons empty (list 5 8 12 2 9)) die Signatur

; (Number (list-of Number) -> (list-of Number)) (list-of Number) (list-of Number) -> (list-of Number)

Es gibt keine Ersetzung von X durch einen Typ in der Signatur oben, die diese Signatur erzeugt. Wenn wir uns die Funktionsdefinition etwas genauer hinschauen, können wir allerdings auch noch eine allgemeinere Signatur finden, nämlich diese:

; [X Y] (X Y -> Y) Y (list-of X) -> Y

(define (op-elements op z l)

(cond

[(empty? l) z]

[else

(op (first l)

(op-elements op z (rest l)))]))

Die Signatur ist allgemeiner, weil sie für mehr konkrete Signaturen (ohne Typvariablen) steht und ist ausreichend für alle Beispiele, die wir betrachet haben.

14.4.5 Abstraktion in Datendefinitionen

Bei generischen Datentypen wie solchen für Listen oder Bäume haben wir bereits gesehen, dass man in diesem Fall nicht redundante Datendefinitionen wie folgt schreiben möchte:

; a List-of-String is either

; - empty

; - (cons String List-of-String)

; a List-of-Number is either

; - empty

; - (cons Number List-of-Number)

Ähnlich wie bei Funktionssignaturen abstrahieren wir über die Unterschiede mit Hilfe von Typvariablen:

; a (list-of X) is either

; - empty

; - (cons X (list-of X))

Im Unterschied zu Funktionssignaturen verzichten wir bei Datendefinitionen darauf, die verwendeten Typvariablen separat zu kennzeichnen (wie bei Funktionssignaturen mit den eckigen Klammern), weil bei Datendefinitionen durch die Position der Typvariablen in der ersten Zeile einer Datendefinition klar ist, dass es sich um eine Typvariable handelt.

Wir können Datendefinitionen auch nutzen, um viele weitere Eigenschaften der Werte, die durch die Datendefinition beschrieben werden, festzulegen. Zum Beispiel können wir so die Menge der nicht-leeren Listen definieren:

; a (nonempty-list-of X) is: (cons X (list-of X))

14.4.6 Grammatik der Typen und Signaturen

Wir können die Typen und Signaturen, mit denen wir nun programmieren können, durch eine Grammatik beschreiben. Diese Grammatik spiegelt gut die rekursive Struktur von Typen wieder. Nicht alle Typen, die mit dieser Grammatik gebildet werden können, sind sinnvoll. Beispielsweise ist ‹X› ein Typ, der nicht sinnvoll ist. Eine Bedeutung haben nur die Typen, bei denen alle vorkommenden Typvariablen durch ein im Ableitungsbaum darüber liegende Typabstraktion der Form [   ‹X›   ]   ‹Typ›) gebunden wurden.

Wir haben bisher nicht gesagt, wie wir Funktionstypen interpretieren sollen. Im Moment können wir es als die Menge aller Funktionen, die diesem Typ genügen, interpretieren. Später werden wir dies noch präzisieren.

14.5 Lokale Abstraktion

Häufig benötigt man Konstanten, Funktionen oder Strukturen nur lokal, innerhalb einer Funktion. Für diesen Fall gibt es die Möglichkeit, Definitionen lokal zu definieren, und zwar mit local Ausdrücken.

14.5.1 Lokale Funktionen

Betrachten wir als erstes lokale Funktionen. Hier ein Beispiel:

Da local Ausdrücke Ausdrücke sind, können sie überall stehen, wo ein Ausdruck erwartet wird. Häufig werden als äußerster Ausdruck eines Funktionsbodies verwendet, aber sie können auch an jeder anderen Stelle stehen.

Diese Ausdrücke sind daher äquivalent:

> (local [(define (f x) (+ x 1))] (+ (* (f 5) 6) 7))

43

> (+ (local [(define (f x) (+ x 1))] (* (f 5) 6)) 7)

43

Ein Extremfall ist der, die lokale Definition so weit nach innen zu ziehen, dass sie direkt an der Stelle steht, wo sie verwendet wird.

> (+ (* ( (local [(define (f x) (+ x 1))] f) 5) 6) 7)

43

Wir werden später sehen, dass es für diesen Fall noch eine bessere Notation gibt.

14.5.2 Lokale Konstanten

Nicht nur Funktionen können lokal sein, sondern auch Konstanten und Strukturdefinitionen.

Betrachten wir beispielsweise eine Funktion zum Exponentieren von Zahlen mit der Potenz 8:

Zum Beispiel:

> (power8 2)

256

Diese Funktion benötigt acht Multiplikationen zum Berechnen des Ergebnis. Eine effizientere Methode zum Berechnen der Potenz nutzt die Eigenschaft der Exponentialfunktion, dass a2*b = ab * ab.

(define (power8-fast x)

(local

[(define r1 (* x x))

(define r2 (* r1 r1))

(define r3 (* r2 r2))]

r3))

Mit Hilfe einer Sequenz lokaler Konstantendeklarationen können wir also die Zwischenergebnisse repräsentieren und mit nur 3 Multiplikationen das Ergebnis berechnen. Diese Konstantendeklarationen könnte man nicht durch (globale) Konstantendeklarationen ersetzen, denn ihr Wert hängt von dem Funktionsparameter ab.

Im Allgemeinen verwendet man lokale Konstanten aus zwei Gründen: 1) Um Redundanz zu vermeiden, oder 2) um Zwischenergebnissen einen Namen zu geben. Auf den ersten Punkt kommen wir gleich nochmal zu sprechen; hier erstmal ein Beispiel für den zweiten Fall:

Im Abschnitt Fallstudie: Ein Ball in Bewegung haben wir eine Funktion programmiert, die einen Bewegungsvektor zu einer Position addiert:

(define (posn+vel p q)

(make-posn (+ (posn-x p) (vel-delta-x q))

(+ (posn-y p) (vel-delta-y q))))

Mit Hilfe lokaler Konstanten können wir den Zwischenergebnissen für die neue x- und y-Koordinate einen Namen geben und deren Berechnung von der Konstruktion der neuen Position trennen:

(define (posn+vel p q)

(local [(define new-x (+ (posn-x p) (vel-delta-x q)))

(define new-y (+ (posn-y p) (vel-delta-y q)))]

(make-posn new-x new-y)))

Die andere wichtige Motivation für lokale Konstanten ist die Vermeidung von Redundanz. Tatsächlich können wir mit lokalen Konstanten sogar zwei unterschiedliche Arten von Redundanz vermeiden: Statische Redundanz und dynamische Redundanz.

Mit statischer Redundanz ist unser DRY Prinzip gemeint: Wir verwenden lokale Konstanten, um uns nicht im Programtext wiederholen zu müssen. Dies illustriert unser erstes Beispiel. Illustrieren wir dies, indem wir unsere power8-fast Funktion wieder de-optimieren indem wir alle Vorkommen der Konstanten durch ihre Definition ersetzen:

(define (power8-fast-slow x)

(local

[(define r1 (* x x))

(define r2 (* (* x x) (* x x)))

(define r3 (* (* (* x x) (* x x)) (* (* x x) (* x x))))]

r3))

Diese Funktion ist, bis auf die Assoziativität der Multiplikationen, äquivalent zu power-8 von oben. Offensichtlich ist hier aber das DRY-Prinzip verletzt, weil die Unterausdrücke (* x x) und (* (* x x) (* x x)) mehrfach vorkommen. Diese Redundanz wird durch die Verwendung der lokalen Konstanten in power8-fast vermieden.

Die zweite Facette der Redundanz, die wir durch lokale Konstanten vermeiden können, ist die dynamische Redundanz. Damit ist gemeint, dass wir das mehrfache Auswerten eines Ausdrucks vermeiden können. Dies liegt daran, dass der Wert einer lokale Konstante nur einmal bei ihrer Definition berechnet wird und im folgenden nur das bereits berechnete Ergebnis verwendet wird. Im Beispiel power8-fast haben wir gesehen, dass wir dadurch die Anzahl der Multiplikationen von 8 auf 3 senken konnten. Im Allgemeinen "lohnt" sich die Definition einer lokalen le aus Sicht der dynamischen Redundanz dann, wenn sie mehr als einmal ausgewertet wird.

Zusammengefasst haben lokale Konstanten also den gleichen Zweck wie nicht-lokale (globale) Konstanten, nämlich der Benennung von Konstanten bzw. Zwischenergebnissen und der Vermeidung von statischer und dynamischer Redundanz; lokale Konstanten sind allerdings dadurch mächtiger, dass sie die aktuellen Funktionsparameter und andere lokale Definitionen verwenden können.

14.5.3 Intermezzo: Successive Squaring

Als fortgeschrittenes Beispiel für die Verwendung lokaler Konstanten können wir die Verallgemeinerung des Potenzierungsbeispiels auf beliebige Exponenten betrachten. Dieser Abschnitt kann übersprungen werden.

Um den Effekt der Vermeidung dynamischer Redundanz noch deutlicher zu illustrieren, betrachten wir die Verallgemeinerung von power8 auf beliebige (natürlichzahlige) Exponenten. Wenn wir den Exponenten wie in Abschnitt Natürliche Zahlen als rekursive Datenstruktur beschrieben als Instanz eines rekursiven Datentyps auffassen, so ergibt sich folgende Definition:

; NaturalNumber Number -> Number

(define (exponential n x)

(if (zero? n)

1

(* x (exponential (sub1 n) x))))

Eine kleine Komplikation der Anwendung der Technik von oben auf den allgemeinen Fall ist, dass der Exponent im Allgemeinen keine Potenz von 2 ist. Wir gehen mit diesem Problem so um, dass wir die Fälle unterscheiden, ob der Exponent eine gerade oder eine ungerade Zahl ist. Insgesamt ergibt sich dieser Algorithmus, der in der Literatur auch als Exponentiation durch successive squaring bekannt ist.

(define (exponential-fast x n)

(if (zero? n)

1

(local

[(define y (exponential-fast x (quotient n 2)))

(define z (* y y))]

(if (odd? n) (* x z) z))))

14.5.4 Lokale Strukturen

Es ist möglich, auch Strukturen mit define-struct lokal zu definieren. Wir werden diese Möglichkeit bis auf weiteres nicht verwenden.

14.5.5 Scope lokaler Definitionen

Der Scope einer Definition eines Namens ist der Bereich im Programm, in dem sich eine Verwendung des Namens auf diese Definition bezieht. Unserer Programmiersprache verwendet lexikalisches Scoping, auch bekannt als statisches Scoping. Dies bedeutet, dass der Scope einer lokalen Definition die Unterausdrücke des local Ausdrucks sind.

In diesem Beispiel sind alle Verwendungen von f und x im Scope ihrer Definitionen.

(local [(define (f n) (if (zero? n)

0

(+ x (f (sub1 n)))))

(define x 5)]

(+ x (f 2)))

In diesem Ausdruck hingegen ist die zweite Verwendung von x nicht im Scope der Definition:

(+ (local [(define x 5)] (+ x 3))

x)

Es kann vorkommen, dass es mehrere Definitionen eines Namens (Konstanten, Funktion, Strukturkonstruktoren/-selektoren) gibt, die einen überlappenden Scope haben. In diesem Fall bezieht sich eine Verwendung des Namens immer auf die syntaktisch näheste Definition. Wenn man also im abstrakten Syntaxbaums eines Programms nach außen geht, so "gewinnt" die erste Definition, die man auf dem Weg von dem Auftreten eines Namens zur Wurzel des Baums trifft.

Beispiel: Kopieren Sie das folgende Programm in den Definitionsbereich von DrRacket und drücken auf "Syntaxprüfung". Gehen Sie nun mit dem Mauszeiger über eine Definition oder Benutzung eines Funktions- oder Konstantennamens. Die Pfeile, die Sie nun angezeigt bekommen, illustrieren, auf welche Definition sich ein Name bezieht.

(add1 (local

[(define (f y)

(local [(define x 2)

(define (g y) (+ y x))]

(g y)))

(define (add1 x) (sub1 x))]

(f (add1 2))))

14.6 Funktionen als Werte: Closures

Betrachten Sie folgende Funktion zur numerischen Berechnung der Ableitung einer Funktion:

; (Number -> Number) Number -> Number

(define (derivative f x)

(/ (- (f (+ x 0.001)) (f x))

0.001))

Diese Funktion gibt uns die (numerische) Ableitung einer Funktion an einem speziellen Punkt.

Aber es wäre eigentlich besser, wenn uns diese Funktion die Ableitung selber als Funktion als Ergebnis liefert. Wenn wir zum Beispiel eine Funktion

; (Number -> Number) -> (Number -> Number)

(define (derivative f)

(local

[(define delta-x 0.001)

(define (delta-f-x x) (- (f (+ x delta-x)) (f x)))

(define (g x) (/ (delta-f-x x) delta-x))]

g))

Was für eine Art von Wert ist es, der von derivative zurückgegeben wird?

Nehmen wir es an, es wäre sowas wie die Definition von g, also (define (g x) (/ (delta-f-x x) delta-x)). Wenn dem so wäre, was passiert mit der Konstanten delta-x und der Funktion delta-f-x? Diese sind ja in derivative nur lokal gebunden. Was passiert beispielsweise bei der Auswertung von diesem Ausdruck:

(local [(define f (derivative exp))

(define delta-x 10000)]

(f 5))

Wird die delta-x Konstante während der Auswertung von (f 5) etwa zu 10000 ausgewertet? Das wäre ein Verstoß gegen lexikalisches Scoping und würde zu unvorhersehbaren Interaktionen zwischen unterschiedlichen Programmteilen führen. Offensichtlich sollte delta-x in der zurückgegebenen Funktion sich immer auf die lokale Definition beziehen.

Wenn wir eine Funktion als Wert behandeln, so ist dieser Wert mehr als nur die Definition der Funktion. Es ist nämlich die Definition der Funktion und die Menge der lokal definierten Namen (Konstanten, Funktionen, Strukturen, Funktionsparameter). Diese Kombination aus Funktionsdefinition und lokaler Umgebung nennt man Funktionsabschluss oder Closure. Die Auswertung einer Funktion (nicht eines Funktionsaufrufs) ergibt also einen Closure. Wird dieser Closure irgendwann später wieder im Rahmen eines Funktionsaufrufs angewendet, so wird die gespeicherte lokale Umgebung wieder aktiviert. Später werden wir das Konzept des Closure noch präzisieren; im Moment merken wir uns, dass die Auswertung einer Funktion die Funktionsdefinition plus ihre lokale Umgebung ergibt, und diese lokale Umgebung bei Anwendung des Closure verwendet wird, um Namen im Funktionsbody auszuwerten.

14.7 Lambda, die ultimative Abstraktion

Nehmen sie an, sie möchten mit Hilfe der map Funktion alle Elemente in einer Liste von Zahlen lon verdoppeln. Dies könnten Sie wie folgt anstellen:

(local [(define (double x) (* 2 x))]

(map double lon))

Dieser Ausdruck ist komplizierter als es ein müsste. Für eine so einfache Funktion wie double, die nur lokal verwendet wird, ist es Verschwendung, einen Namen zu vergeben und eine komplette Extra Zeile Code zu verwenden.

In ISL+ (dem Sprachlevel von HTDP welches wir zurzeit verwenden) gibt es aus diesem Grund die Möglichkeit, anonyme Funktionen, also Funktionen ohne Namen, zu definieren. Anonyme Funktionen werden mit dem Schlüsselwort lambda gekennzeichnet. Daher nennt man solche Funktionen auch lambda-Ausdrücke.

Hier ist das Beispiel von oben, aber so umgeschrieben, dass statt double eine anonyme Funktion definiert wird.

(map (lambda (x) (* 2 x)) lon)

Ein lambda Ausdruck hat im Allgemeinen die Form (lambda (x-1 ... x-n) exp) für Namen x-1,...,x-n und einen Ausdruck exp. Ihre Bedeutung entspricht in etwa einer lokalen Funktionsdefinition der Form (local [(define (f x-1 ... x-n) exp)] f). Beispielsweise hätten wir den Ausdruck von oben auch so schreiben können:

(map (local [(define (double x) (* 2 x))] double) lon)

(define (f x-1 ... x-n) exp)

entspricht

(define f (lambda (x-1 ... x-n) exp))

Die lambda-Ausdrücke machen also sehr deutlich, dass Funktionen "ganz normale" Werte sind, an die wir Konstanten binden können. Wenn wir also bei obiger Definition von f einen Funktionsaufruf (f e-1 ... e-n) haben, so ist das f an der ersten Position kein Funktionsname, sondern ein Konstantenname, der zu einem λ-Ausdruck ausgewertet wird. Im Allgemeinen hat ein Funktionsaufruf also die Syntax (exp-0 exp-1 ... exp-n), wobei alle exp-i beliebige Ausdrücke sind aber exp-0 bei der Auswertung eine Funktion (genauer: ein Closure) ergeben muss.

Das Wort lambda-Ausdruck stammt aus dem λ-Kalkül, welches in den 1930er Jahren von Alonzo Church entwickelt wurde. Das λ-Kalkül ist eine Untersprache von ISL+: Im λ-Kalkül gibt es nur λ-Ausdrücke und Funktionsapplikationen — keine Zahlen, keine Wahrheitswerte, keine Konstantendefinitionen, keine Listen oder Strukturen, und so weiter. Dennoch sind λ-Ausdrücke so mächtig, dass man sich all diese Programmiersprachenfeatures innerhalb des λ-Kalkül nachbauen kann, beispielsweise mit Hilfe sogenannter Church-Kodierungen.

(map (λ (x) (* 2 x)) lon)

14.8 Wieso abstrahieren?

Programme sind wie Bücher: Sie werden für Menschen (Programmierer) geschrieben und können halt nebenbei auch noch auf einem Computer ausgeführt werden. Auf jeden Fall sollten Programme, genau wie Bücher, keine unnötigen Wiederholungen enthalten, denn niemand möchte solche Programme lesen.

Die Einhaltung des DRY Prinzips durch die Erschaffung guter Abstraktionen hat viele Vorteile. Bei Programmen mit wiederkehrenden Mustern besteht stehts die Gefahr der Inkonsistenz, da man an jeder Stelle, an der das Muster wieder auftritt, dieses Muster wieder korrekt nachbilden muss. Wir haben auch gesehen, dass es zu nicht unerheblicher Vergrößerung des Codes führen kann, wenn man keine guten Abstraktionen hat und sich oft wiederholt.

Der wichtigste Vorteil guter Abstraktionen ist jedoch folgende: Es gibt für jede kohärente Funktionalität des Programms genau eine Stelle, an der diese implementiert ist. Diese Eigenschaft macht es viel einfacher, ein Programm zu schreiben und zu warten. Wenn man einen Fehler gemacht hat, ist der Fehler an einer Stelle lokalisiert und nicht vielfach dupliziert. Wenn man die Funktionalität ändern möchte, gibt es eine Stelle, an der man etwas ändern muss und man muss nicht alle Vorkommen eines Musters finden (was schwierig oder praktisch unmöglich sein kann). Wichtige Eigenschaften, wie Terminierung oder Korrektheit, können Sie einmal für die Abstraktion nachweisen und sie gilt dann automatisch für alle Verwendungen davon.

Diese Vorteile treffen auf alle Arten der Abstraktion zu, die wir bisher kennengelernt haben: Globale und lokale Funktions- und Konstantendefinitionen, Abstrakte Typsignaturen, Abstrakte Datendefinitionen.

Aus diesem Grund formulieren wir folgende Richtlinie als Präzisierung des DRY-Prinzips:

Definieren Sie eine Abstraktion statt einen Teil eines Programms zu kopieren und dann zu modifizieren.

Diese Richtlinie gilt nicht nur während der ersten Programmierung eines Programms. Auch in der Weiterentwicklung und Wartung von Programmen sollten Sie stets darauf achten, ob es in ihrem Programm Verstöße gegen dieses Prinzip gilt und diese Verstöße durch die Definition geeigneter Abstraktionen eliminieren.