5 Strukturierung von Daten und Programmen

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

Die Datentypen, die wir bisher kennengelernt und genutzt haben, umfassen Zahlen, Strings, Wahrheitswerte sowie in informellen Datendefinitionen definierte Datentypen wie Temperatur.

Um realistische Anwendungen zu programmieren, ist es hilfreich, ein größeres und flexibel erweiterbares Repertoire an Datentypen zu haben. In diesem Kapitel schauen wir uns an, welche Arten von Datentypen es noch gibt und wie man Programme entwirft, die diese Datentypen benutzen.

5.1 Auzählungstypen

Häufig hat man den Fall, dass ein Datentyp nur eine endliche aufzählbare Menge von Werten enthält. Wir nennen solche Datentypen Aufzählungstypen oder Enumerationstypen. Hier ist ein Beispiel wie ein Aufzählungstyp definiert wird:

; A TrafficLight shows one of three colors:

; – "red"

; – "green"

; – "yellow"

; interp. each element of TrafficLight represents which colored

; bulb is currently turned on

Das Programmieren mit Aufzählungstypen ist sehr einfach. Wenn eine Funktion einen Parameter hat, der einen Aufzählungstyp hat, dann enthält das Programm typischerweise eine Fallunterscheidung, in denen alle Alternativen des Aufzählungstyps separat voneinander definiert werden. Hier ein Beispiel:

; TrafficLight -> TrafficLight

; given state s, determine the next state of the traffic light

(check-expect (traffic-light-next "red") "green")

(define (traffic-light-next s)

(cond

[(string=? "red" s) "green"]

[(string=? "green" s) "yellow"]

[(string=? "yellow" s) "red"]))

Manchmal ist eine Funktion auch nur an einer Teilmenge der möglichen Werte eines Aufzählungstypen interessiert. In diesem Fall werden nur die interessanten Fälle abgefragt und der Rest ignoriert. Ein Beispiel dafür ist die on-mouse-event Funktion aus Das Universe Teachpack, die eine Eingabe vom Aufzählungstypen MouseEvent erhält. MouseEvent ist folgendermaßen definiert:

; A MouseEvt is one of these strings:

; – "button-down"

; – "button-up"

; – "drag"

; – "move"

; – "enter"

; – "leave"

Es kann auch sein, dass ein Funktionsparameter einen Aufzählungstyp hat, aber trotzdem keine Fallunterscheidung vornimmt, weil hierzu eine Hilfsfunktion aufgerufen wird. Dennoch ist es eine gute Heuristik, im Schritt 3 des Entwurfsrezepts aus Abschnitt Entwurfsrezept zur Funktionsdefinition mit einem Funktionstemplate zu starten, welches alle Fälle des Parameters unterscheidet. Beispielsweise würde das Template für die traffic-light-next Funktion von oben so aussehen:

(define (traffic-light-next s)

(cond

[(string=? "red" s) ...]

[(string=? "green" s) ...]

[(string=? "yellow" s) ...]))

Wie sie sehen, können sie einen großen Teil einer Funktionsdefinition quasi mechanisch generieren, indem Sie systematisch den Schritten aus dem Entwurfsrezept folgen.

5.2 Intervalltypen

Betrachten Sie ein Programm, welches ein Ufo beim landen zeigen soll. Ein Programm hierzu könnte wie folgt aussehen:

; constants:

(define WIDTH 300)

(define HEIGHT 100)

; visual constants:

(define MT (empty-scene WIDTH HEIGHT))

(define UFO

(overlay (circle 10 "solid" "green")

(rectangle 40 2 "solid" "green")))

(define BOTTOM (- HEIGHT (/ (image-height UFO) 2)))

; A WorldState is a number.

; interp. height of UFO (from top)

; WorldState -> WorldState

; compute next location of UFO

(define (nxt y)

(+ y 1))

; WorldState -> Image

; place UFO at given height into the center of MT

(define (render y)

(place-image UFO (/ WIDTH 2) y MT))

; WorldState -> Boolean

; returns true when UFO has reached the bottom, i.e. y >= BOTTOM

(define (end-of-the-world y) (>= y BOTTOM))

; wire everything together; start descend at position 0

(big-bang 0 (on-tick nxt) (to-draw render) (stop-when end-of-the-world))

Betrachten Sie nun folgende Erweiterung der Problemstellung:

The status line should say "descending" when the UFO’s height is above one third of the height of the canvas. It should switch to "closing in" below that. And finally, when the UFO has reached the bottom of the canvas, the status should notify the player that the UFO has "landed."

Der Datentyp, die sich in dieser Problemstellung versteckt, ist kein Enumerationstyp, denn es gibt eine unendliche Zahl unterschiedlicher Höhen (oder, sofern wir nur die ganzen Zahlen zählen, so viele unterschiedliche Höhen, dass es unpraktisch wäre, hierfür einen Aufzählungstypen zu definieren).

Daher verwenden wir Intervalle, um zusätzliche Struktur auf geordneten Datentypen wie Zahlen oder Strings zu definieren. Im folgenden konzentrieren wir uns auf (ganzzahlige oder nicht-ganzzahlige) Zahlen. Ein Intervall wird durch seine Grenzen definiert. Ein Intervall hat entweder eine unter und obere Grenze, oder es hat nur eine dieser Grenzen und ist zur anderen Seite offen.

In unserem Beispiel können wir die Datendefinition für den WorldState als Intervall ausdrücken, um eine Datendefinition zu haben, die die Intention der Problemstellung besser erfasst.

; constants:

(define CLOSE (* 2 (/ HEIGHT 3)))

; A WorldState is a number. It falls into one of three intervals:

; – between 0 and CLOSE

; – between CLOSE and BOTTOM

; – at BOTTOM

; interp. height of UFO (from top)

Nicht alle Funktionen, die einen Intervalltypen als Argument bekommen, nutzen diese zusätzliche Struktur. So kann zum Beispiel die render Funktion von oben so wie sie ist, weil das Intervall nur für die Statusanzeige aber nicht für das Ufo relevant ist.

Funktionen, die jedoch die zusätzliche Struktur des Intervalls benötigen, enthalten typischerweise einen cond Ausdruck, der die unterschiedlichen Intervalle unterscheidet.

; WorldState -> Image

; add a status line to the scene create by render

(define (render/status y)

(cond

[(<= 0 y CLOSE) (above (text "descending" 12 "black") (render y))]

[(< CLOSE y BOTTOM) (above (text "closing in" 12 "black") (render y))]

[(= y BOTTOM) (above (text "landed" 12 "black") (render y))]))

Es empfiehlt sich, diesen cond Ausdruck im Rahmen der Templatekonstruktion aus dem Entwurfsrezept direkt in das Template mit aufzunehmen. Allerdings findet die Fallunterscheidung nicht notwendigerweise als erstes statt sondern kann auch tiefer im Funktionsbody stattfinden. Dies bietet sich in unserem Beispiel an, denn wir haben gegen das DRY Prinzip verstossen (Wenn wir die Farbe des Textes beispielsweise auf "red" ändern möchten müssten wir drei Zeilen ändern). Deshalb ist es vorteilhaft, den konditionalen Ausdruck nach innen zu ziehen:

; WorldState -> Image

; add a status line to the scene create by render

(define (render/status y)

(above

(text

(cond

[(<= 0 y CLOSE) "descending"]

[(< CLOSE y BOTTOM) "closing in"]

[(= y BOTTOM) "landed"])

12 "black")

(render y)))

Intervalle liefern uns außer neuen Funktionstemplates auch Anhalte zum Testen: Typischerweise möchte man einen Testcase für jedes Intervall und insbesondere für die Intervallgrenzen haben.

5.3 Summentypen

Die Alternativen eines Aufzählungstypen sind nicht notwendigerweise konstante Strings, sondern können beliebige andere Typen sein. Im universe Teachpack wird beispielsweise ein Datentyp KeyEvent definiert, der Benutzereingaben von der Tastatur repräsentiert.

5.4 Strukturtypen