On this page:
5.1 Aufzählungstypen
5.2 Aufzählungstypen mit überprüfbaren Signaturen
5.3 Intervalltypen
5.4 Summentypen
5.4.1 Entwurf mit Summentypen
5.5 Unterscheidbarkeit der Alternativen

5 Datendefinition durch Alternativen: Summentypen

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, wie man mit Datentypen unterschiedliche Situationen unterscheiden kann und wie diese Datentypen den Entwurf von Programmen beeinflussen.

5.1 Aufzä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 is one of:
; – "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 behandelt 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:
; – "button-down"
; – "button-up"
; – "drag"
; – "move"
; – "enter"
; – "leave"
; interp. the kind of mouse event that has been triggered

In der Funktion on-mouse-event interessieren wir uns nur für die Alternative "button-down". Für alle anderen Alternativen von MouseEvent, lassen wir den Zustand unverändert.

Es kann auch sein, dass ein Funktionsparameter einen Aufzählungstyp hat, aber die Funktion 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 Aufzählungstypen mit überprüfbaren Signaturen

Die Sprache für überprüfbare Signaturen in BSL erlaubt es uns, Aufzählungstypen zu definieren und ihnen einen Namen zu geben. Mit Hilfe von enum kann ein Aufzählungstyp definiert und benutzt werden:

(: traffic-light-next ((enum "red" "green" "yellow") -> (enum "red" "green" "yellow")))

Allerdings ist es, wie so oft in der Programmierung, sinnvoll, solchen wiederkehrenden Konzepten einen Namen geben. Mit Hilfe der signature Form kann ein Name definiert werden, der im folgenden dann für die angegebene Signatur steht.

(define TrafficLight (signature (enum "red" "green" "yellow")))
; interp. each element of TrafficLight represents which colored
; bulb is currently turned on

Mit Hilfe dieser Definition kann die traffic-light-next Funktion dann wie folgt definiert werden.

(: traffic-light-next (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"]))

5.3 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, der 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 untere 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 one of:
; – Number between 0 and CLOSE
; – Number between CLOSE and BOTTOM
; – 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 bleiben 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 created 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 verstoßen (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 created 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)))

Nun muss nur noch der big-bang Ausdruck angepasst werden, so dass render/status und nicht mehr render zum Zeichnen verwendet wird.
; wire everything together; start descend at position 0
(big-bang 0 (on-tick nxt) (to-draw render/status) (stop-when end-of-the-world))

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.4 Summentypen

Intervalltypen unterscheiden unterschiedliche Teilmengen der Zahlen (oder anderer geordneter Werte). Aufzählungstypen zählen die unterschiedlichen Elemente des Typs Wert für Wert auf.

Summentypen verallgemeinern Intervalltypen und Aufzählungstypen. Mit Summentypen können existierende Datentypen und individuelle Werte beliebig miteinander kombiniert werden. Ein Summentyp gibt verschiedene Alternativen an, von denen jeder Wert dieses Typs genau eine Alternative erfüllt.

Betrachten wir als Beispiel die string->number Funktion, die einen String in eine Zahl konvertiert, falls dies möglich ist, und andernfalls #false zurückgibt.

Hier ist die Definition eines Summentyps, der das Verhalten dieser Funktion beschreibt:

; A MaybeNumber is one of:
; – #false
; – Number
; interp. a number if successful, else false.

Damit können wir für string->number folgende Signatur definieren:

; String -> MaybeNumber
; converts the given string into a number;
; produces #false if impossible
(define (string->number str) ...)

Summentypen werden manchmal auch Vereinigungstypen (union types) genannt. In HTDP/2e werden sie Itemizations genannt.

In der Dokumentation der HTDP-Sprachen ist die Signatur von string->number so angegeben:

String -> (union Number #false)

Der Operator union steht für die “on-the-fly” Konstruktion eines anonymen Summentyps mit der gleichen Bedeutung wie unser MaybeNumber oben.

Was macht man mit einem Wert, der einen Summentyp hat? Wie bei Aufzählungs- und Intervalltypen auch ist typischerweise die einzige sinnvolle Operation die, welche die unterschiedlichen Alternativen voneinander trennt, beispielsweise im Rahmen eines cond Ausdrucks. Hier ein Beispiel:

; MaybeNumber -> MaybeNumber
; adds 3 to a if it is a number; returns #false otherwise
(check-expect (add3 5) 8)
(check-expect (add3 #false) #false)
(define (add3 a)
  (cond [(number? a) (+ a 3)]
        [else #false]))

Funktionen mit Summentypen unterscheiden sich in ihrer Entwurfsmethodik etwas von den Funktionen, die wir bisher kennengelernt haben. Deswegen gehen wir nochmal durch unser Entwurfsrezept (Entwurfsrezept zur Funktionsdefinition) und beschreiben, wie sich der Entwurf von Funktionen mit Summentypen vom allgemeinen Entwurfsrezept unterscheidet.

The tax on an item is either an absolute tax of 5 or 10 currency units, or a linear tax. Design a function that computes the price of an item after applying its tax.

5.4.1 Entwurf mit Summentypen

Das Entwurfsrezept für den Entwurf von Funktionen ergänzen wir wie folgt:
  1. Falls die Problemstellung Werte in unterschiedliche Klassen unterteilt, so sollten diese Klassen durch eine Datendefinition explizit definiert werden.

    Beispiel: Die Problemstellung oben unterscheidet drei verschiedene Arten der Steuer. Dies motiviert folgende Datendefinition:

    ; A Tax is one of
    ; - "absolute5"
    ; - "absolute10"
    ; - a Number representing a linear tax rate in percent
  2. Im zweiten Schritt ändert sich nichts, außer dass typischerweise der definierte Datentyp in der Signatur verwendet wird.

    Beispiel:

    ; Number Tax -> Number
    ; computes price of an item after applying tax
    (define (total-price itemprice tax) 0)
  3. Bzgl. der Tests ist es ratsam, pro Alternative des Datentypen mindestens ein Beispiel zu haben. Bei Intervallen sollten die Grenzen der Intervalle getestet werden. Gibt es mehrere Parameter mit Summentypen, so sollten alle Kombinationen der Alternativen getestet werden.

    Beispiel:

    (check-expect (total-price 10 "absolute5") 15)
    (check-expect (total-price 10 "absolute10") 20)
    (check-expect (total-price 10 25) 12.5)
  4. Die größte Neuerung ist die des Templates für die Funktion. Im Allgemeinen folgt die Struktur der Funktionen aus der Struktur der Daten. Dies bedeutet, dass in den meisten Fällen der Funktionskörper mit einem cond Ausdruck startet, der die unterschiedlichen Fälle des Summentypen unterscheidet.

    Wieso ist in diesem Beispiel die Reihenfolge der Zweige des cond Ausdrucks wichtig?

    (define (total-price itemprice tax)
      (cond [(number? tax) ...]
            [(string=? tax "absolute5") ...]
            [(string=? tax "absolute10") ...]))

  5. Diese Unterscheidung der Fälle ist ein Beispiel für ein allgemeineres Entwurfskonzept für komplexe Systeme, welches sich separation of concerns (Trennung der Belange) nennt.

    Im fünften Schritt werden die ... Platzhalter durch den korrekten Code ersetzt. Hier ist es sinnvoll, jeden Zweig des cond Ausdrucks einzeln und nacheinander durchzugehen und zu implementieren. Der Vorteil ist, dass Sie sich bei dieser Art der Implementierung immer nur um einen der Fälle kümmern müssen und alle anderen Fälle ignorieren können.

    Möglicherweise stellen Sie während dieses Schritts fest, dass es sinnvoll ist, den cond Ausdruck nach innen zu ziehen (ähnlich wie in create-rocket-scene-v6 in Abschnitt DRY Redux), oder vielleicht müssen Sie gar nicht alle Fälle unterscheiden, oder vielleicht möchten Sie die Unterscheidung auch in eine Hilfsfunktion auslagern – dennoch ist es in der Regel sinnvoll, mit diesem Template zu starten, selbst wenn am Ende ihre Funktion anders aussieht.

    Beispiel:
    (define (total-price itemprice tax)
      (cond [(number? tax) (* itemprice (+ 1 (/ tax 100)))]
            [(string=? tax "absolute5") (+ itemprice 5)]
            [(string=? tax "absolute10") (+ itemprice 10)]))

  6. Im letzten Schritt ändert sich nichts, aber überprüfen Sie, dass Sie Testfälle für alle Alternativen definiert haben.

5.5 Unterscheidbarkeit der Alternativen

Was wäre, wenn wir in unserem letzten Beispiel statt zwei absoluten Steuersätzen ein kontinuierliches Spektrum hätten? Wir könnten unsere Datendefinition wie folgt abändern:

; A Tax is one of
; - a Number representing an absolute tax in currency units
; - a Number representing a linear tax rate in percent

So weit so gut – aber wie können wir in einem cond Ausdruck diese Fälle unterscheiden? Wir haben zwar das Prädikat number?, aber damit können wir nicht zwischen diesen beiden Fällen unterscheiden.

In unseren Summentypen ist es wichtig, dass man eindeutig unterscheiden kann, welche Alternative in einem Wert, der einen Summentyp hat, gewählt wurde. Daher müssen die Mengen der möglichen Werte für jede Alternative disjunkt sein.

Die Variante der Summentypen, die wir verwenden, bezeichnet man deshalb auch als untagged unions.

Falls sie nicht disjunkt sind, muss man zu jedem Wert eine zusätzliche Information abspeichern, die aussagt, zu welcher Alternative dieser Wert gehört: ein sogenanntes tag ("Etikett", "Anhänger"). Mit den Mitteln, die wir bisher kennengelernt haben, können wir den oben gewünschten Datentyp nicht sinnvoll ausdrücken. Im nächsten Kapitel werden wir jedoch ein Sprachkonstrukt kennenlernen, mit dem man solche tags und damit auch solche Datentypen strukturiert definieren kann.