On this page:
6.1 Die posn Struktur
6.2 Strukturdefinitionen
6.3 Verschachtelte Strukturen
6.4 Datendefinitionen für Strukturen
6.5 Fallstudie:   Ein Ball in Bewegung
6.6 Tagged Unions und Maybe
6.7 Erweiterung des Entwurfsrezepts

6 Datendefinition durch Zerlegung: Produkttypen

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

Nehmen Sie an, Sie möchten mit dem "universe" Teachpack ein Programm schreiben, welches einen Ball simuliert, der zwischen vier Wänden hin und her prallt. Nehmen wir der Einfachheit halber an, der Ball bewegt sich konstant mit zwei Pixeln pro Zeiteinheit.

Wenn Sie sich an das Entwurfsrezept halten, ist ihre erste Aufgabe, eine Datenrepräsentation für all die Dinge, die sich ändern, zu definieren. Für unseren Ball mit konstanter Geschwindigkeit sind dies zwei Eigenschaften: Die aktuelle Position sowie die Richtung, in die sich der Ball bewegt.

Wäre es sinnvoll, Varianten des "universe" Teachpacks zu haben, in denen der WorldState zum Beispiel durch zwei Werte repräsentiert wird?

Der WorldState im "universe" Teachpack ist allerdings nur ein einzelner Wert. Die Werte, die wir bisher kennen, sind allerdings stets einzelne Zahlen, Bilder, Strings oder Wahrheitswerte — daran ändern auch Summentypen nichts. Wir müssen also irgendwie mehrere Werte so zusammenstellen können, dass sie wie ein einzelner Wert behandelt werden können.

Es wäre zwar denkbar, zum Beispiel zwei Zahlen in einen String reinzukodieren und bei Bedarf wieder zu dekodieren (in der theoretischen Informatik sind solche Techniken als Gödelisierung bekannt), aber für die praktische Programmierung sind diese Techniken ungeeignet.

Jede höhere Programmiersprache hat Mechanismen, um mehrere Daten zu einem Datum zusammenzupacken und bei Bedarf wieder in seine Bestandteile zu zerlegen. In BSL gibt es zu diesem Zweck Strukturen (structs). Man nennt Strukturdefinitionen auch oft Produkte, weil Sie dem Kreuzprodukt von Mengen in der Mathematik entsprechen. Aus dieser Analogie ergibt sich übrigens auch der Name ’Summentyp’ aus dem letzten Kapitel, denn die Vereinigung von Mengen wird auch als die Summe der Mengen bezeichnet. In manchen Sprachen werden Strukturen auch Records genannt.

6.1 Die posn Struktur

Eine Position in einem Bild wird durch zwei Zahlen eindeutig identifiziert: Die Distanz vom linken Rand und die Distanz vom oberen Rand. Die erse Zahl nennt man die x-Koordinate und die zweite die y-Koordinate.

In BSL werden solche Positionen mit Hilfe der posn Struktur repräsentiert. Eine posn (Aussprache: Position) ist also ein Wert, der zwei Werte enthält.

Im Deutschen wäre es eigentlich korrekt, von einem Exemplar einer Struktur zu sprechen. Es hat sich jedoch eingebürgert, analog zum Wort instance im Englischen von einer Instanz zu reden, deshalb werden auch wir diese sprachlich fragwürdige Terminologie verwenden.

Wir können eine Instanz der posn Struktur mit der Funktion make-posn erzeugen. Die Signatur dieser Funktion ist Number Number -> Posn.

Beispiel: Diese drei Ausdrücke erzeugen jeweils eine Instanz der posn Struktur.

(make-posn 3 4)
(make-posn 8 6)
(make-posn 5 12)

Eine posn hat den gleichen Status wie Zahlen oder Strings in dem Sinne, dass Funktionen Instanzen von Strukturen konsumieren oder produzieren können.

Betrachten Sie nun eine Funktion, die die Distanz einer Position von der oberen linken Bildecke berechnet. Hier ist die Signatur, Aufgabenbeschreibung und der Header einer solchen Funktion:

; Posn -> Number
; computes the distance of a-posn to the origin
(define (distance-to-0 a-posn) 0)

Was neu ist an dieser Funktion ist, dass sie nur einen Parameter, a-posn, hat, in dem aber beide Koordinaten übergeben werden. Hier sind einige Tests die verdeutlichen, was distance-to-0 berechnen soll. Die Distanz kann natürlich über die bekannte Pythagaros Formel berechnet werden.

(check-expect (distance-to-0 (make-posn 0 5)) 5)
(check-expect (distance-to-0 (make-posn 7 0)) 7)
(check-expect (distance-to-0 (make-posn 3 4)) 5)
(check-expect (distance-to-0 (make-posn 8 6)) 10)

Wie sieht nun der Funktionsbody von distance-to-0 aus? Offensichtlich müssen wir zu diesem Zweck die x- und y-Koordinate aus dem Parameter a-posn extrahieren. Hierzu gibt es zwei Funktionen posn-x und posn-y. Die erste Funktion extrahiert die x-Koordinate, die zweite die y-Koordinate. Hier zwei Beispiele die diese Funktionen illustrieren:

> (posn-x (make-posn 3 4))

3

> (posn-y (make-posn 3 4))

4

Damit wissen wir nun genug, um distance-to-0 zu implementieren. Als Zwischenschritt definieren wir ein Template für distance-to-0, in welchem die Ausdrücke zur Extraktion der x- und y-Koordinate vorgezeichnet sind.

(define (distance-to-0 a-posn)
  (... (posn-x a-posn) ...
   ... (posn-y a-posn) ...))

Auf Basis dieses Templates ist es nun leicht, die Funktionsdefinition zu vervollständigen:

(define (distance-to-0 a-posn)
  (sqrt
    (+ (sqr (posn-x a-posn))
       (sqr (posn-y a-posn)))))

6.2 Strukturdefinitionen

Strukturen wie posn werden normalerweise nicht fest in eine Programmiersprache eingebaut. Stattdessen wird von der Sprache nur ein Mechanismus zur Verfügung gestellt, um eigene Strukturen zu definieren. Die Menge der verfügbaren Strukturen kann also von jedem Programmierer beliebig erweitert werden.

Eine Struktur wird durch eine spezielle Strukturdefinition erzeugt. Hier ist die Definition der posn Struktur in BSL:

(define-struct posn (x y))

Im Allgemeinen hat eine Strukturdefinition diese Form:

(define-struct StructureName (FieldName ... FieldName))

Das Schlüsselwort define-struct bedeutet, dass hier eine Struktur definiert wird. Danach kommt der Name der Struktur. Danach folgen, eingeschlossen in Klammern, die Namen der Felder der Struktur.

Im Gegensatz zu einer normale Funktionsdefinition definiert man durch eine Strukturdefinition gleich einen ganzen Satz an Funktionen, und zwar wie folgt:

Der Rest des Programms kann diese Funktionen benutzen als wären sie primitive Funktionen.

6.3 Verschachtelte Strukturen

Ein sich mit konstanter Geschwindigkeit bewegender Ball im zweidimensionalen Raum kann durch zwei Eigenschaften beschrieben werden: Seinen Ort und die Geschwindigkeit und Richtung in die er sich bewegt. Wir wissen bereits wie man den Ort eines Objekts im zweidimensionalen Raum beschreibt: Mit Hilfe der posn Struktur. Es gibt verschiedene Möglichkeiten, die Geschwindigkeit und Richtung eines Objekts zu repräsentieren. Eine dieser Möglichkeiten ist die, einen Bewegungsvektor anzugeben, zum Beispiel in Form einer Strukturdefinition wie dieser:

(define-struct vel (delta-x delta-y))

Der Grad der Veränderung von Einheiten wird in der Informatik (und anderswo) häufig als Delta bezeichnet, daher der Name der Felder.

Der Name vel steht für velocity; delta-x und delta-y beschreiben, wieviele Punkte auf der x- und y-Achse sich das Objekt pro Zeiteinheit bewegt.

Auf Basis dieser Definitionen können wir beispielsweise berechnen, wie sich der Ort eines Objekts ändert:
; Posn Vel -> Posn
; computes position of loc moving it by v
(check-expect (move (make-posn 5 6) (make-vel 1 2)) (make-posn 6 8))
(define (move loc v)
  (make-posn
   (+ (posn-x loc) (vel-delta-x v))
   (+ (posn-y loc) (vel-delta-y v))))

Wie können wir nun einen sich bewegenden Ball repräsentieren? Wir haben gesehen, dass dieser durch seinen Ort und seinen Bewegungsvektor beschrieben wird. Eine Möglichkeit der Repräsentation wäre diese:

(define-struct ball (x y delta-x delta-y))

Hier ist ein Beispiel für einen Ball in dieser Repräsentation:

(define SOME-BALL (make-ball 5 6 1 2))

Allerdings geht in dieser Repräsentation die Zusammengehörigkeit der Felder verloren: Die ersten zwei Felder repräsentieren den Ort, die anderen zwei Felder die Bewegung. Eine praktische Konsequenz ist, dass es auch umständlich ist, Funktionen aufzurufen, die etwas mit Geschwindigkeiten und/oder Bewegungen machen aber nichts über Bälle wissen, wie zum Beispiel move oben, denn wir müssen die Daten erst immer manuell in die richtigen Strukturen verpacken. Um SOME-BALL mit Hilfe von move zu bewegen, müssten wir Ausdrucke wie diesen schreiben:

(move (make-posn (ball-x SOME-BALL) (ball-y SOME-BALL))
      (make-vel (ball-delta-x SOME-BALL) (ball-delta-y SOME-BALL)))

Eine bessere Repräsentation verschachtelt Strukturen ineinander:

(define-struct ball (position velocity))

Diese Definition ist so noch nicht verschachtelt — dies werden wir in Kürze durch Datendefinitionen für Strukturen deutlich machen. Die Schachtelung können wir sehen, wenn wir Instanzen dieser Struktur erzeugen. Der Beispielball SOME-BALL wird konstruiert, indem die Konstruktoren ineinander verschachtelt werden:

(define SOME-BALL (make-ball (make-posn 5 6) (make-vel 1 2)))

In dieser Repräsentation bleibt die logische Gruppierung der Daten intakt. Auch der Aufruf von move gestaltet sich nun einfacher:

(move (ball-position SOME-BALL) (ball-velocity SOME-BALL))

Im Allgemeinen kann man durch Verschachtelung von Strukturen also Daten hierarchisch in Form eines Baums repräsentieren.

6.4 Datendefinitionen für Strukturen

Der Zweck einer Datendefinition für Strukturen ist, zu beschreiben, welche Art von Daten jedes Feld enthalten darf. Für einige Strukturen ist die dazugehörige Datendefinition recht offensichtlich:

(define-struct posn (x y))
; A Posn is a structure: (make-posn Number Number)
; interp. the number of pixels from left and from top

Hier sind zwei plausible Datendefinitionen für vel und ball:

(define-struct vel (delta-x delta-y))
; A Vel is a structure: (make-vel Number Number)
; interp. the velocity vector of a moving object
 
(define-struct ball (position velocity))
; A Ball is a structure: (make-ball Posn Vel)
; interp. the position and velocity of a ball

Eine Struktur hat jedoch nicht notwendigerweise genau eine zugehörige Datendefinition. Beispielsweise können wir Bälle nicht nur im zweidimensionalen, sondern auch im ein- oder drei-dimensionalen Raum betrachten. Im eindimensionalen Raum können Position und Velocity jeweils durch eine Zahl repräsentiert werden. Daher können wir definieren:

; A Ball1d is a structure: (make-ball Number Number)
; interp. the position and velocity of a 1D ball

Strukturen können also "wiederverwendet" werden. Sollte man dies stets tun wenn möglich?

Prinzipiell bräuchten wir nur eine einzige Struktur mit zwei Feldern und könnten damit alle Produkttypen mit zwei Komponenten kodieren. Beispielsweise könnten wir uns auch vel und ball sparen und stattdessen nur posn verwenden:

; A Vel is a structure: (make-posn Number Number)
; interp. the velocity vector of a moving object
 
; A Ball is a structure: (make-posn Posn Vel)
; interp. the position and velocity of a ball

Wir können sogar prinzipiell alle Produkttypen, auch solche mit mehr als zwei Feldern, mit Hilfe von posn ausdrücken, indem wir posn verschachteln.

Beipiel:

; A 3DPosn is a structure: (make-posn Number (make-posn Number Number))
; interp. the x/y/z coordinates of a point in 3D space

Die Sprache LISP basierte auf diesem Prinzip: Es gab in ihr nur eine universelle Datenstruktur, die sogenannte cons-Zelle, die verwendet wurde, um alle Arten von Produkten zu repräsentieren. Die cons-Zelle entspricht folgender Strukturdefinition in BSL:

Die Namen cons, car und cdr haben eine Historie, die für uns aber nicht relevant ist. car ist einfach der Name für die erste Komponente und cdr der für die zweite Komponente des Paars.

(define-struct cons-cell (car cdr))

Ist diese Wiederverwendung von Strukturdefinitionen eine gute Idee? Der Preis, den man dafür bezahlt, ist, dass man die unterschiedlichen Daten nicht mehr unterscheiden kann, weil es pro Strukturdefinition nur ein Prädikat gibt. Unsere Empfehlung ist daher, Strukturdefinitionen nur dann in mehreren Datendefinitionen zu verwenden, wenn die unterschiedlichen Daten ein gemeinsames semantisches Konzept haben. Im Beispiel oben gibt es für Ball und Ball1d das gemeinsame Konzept des Balls im n-dimensionalen Raum. Es gibt jedoch kein sinnvolles gemeinsames Konzept für Ball und Posn; daher ist es nicht sinnvoll, eine gemeinsame Strukturdefinition zu verwenden.

Ein anderes sinnvolles Kriterium, um über Wiederverwendung zu entscheiden, ist die Frage, ob es wichtig ist, dass man mit einem Prädikat die unterschiedlichen Daten unterscheiden kann — falls ja, so sollte man jeweils eigene Strukturen verwenden.

6.5 Fallstudie: Ein Ball in Bewegung

Probieren Sie aus, was das folgende Programm macht. Verstehen Sie, wie Strukturen und Datendefinitionen verwendet wurden, um das Programm zu strukturieren!

(define WIDTH 200)
(define HEIGHT 200)
(define BALL-IMG (circle 10 "solid" "red"))
(define BALL-RADIUS (/ (image-width BALL-IMG) 2))
 
(define-struct vel (delta-x delta-y))
; A Vel is a structure: (make-vel Number Number)
; interp. the velocity vector of a moving object
 
(define-struct ball (position velocity))
; A Ball is a structure: (make-ball Posn Vel)
; interp. the position and velocity of a object
 
; Posn Vel -> Posn
; computes position of loc moving it by v
(check-expect (move (make-posn 5 6) (make-vel 1 2)) (make-posn 6 8))
(define (move loc v)
  (make-posn
   (+ (posn-x loc) (vel-delta-x v))
   (+ (posn-y loc) (vel-delta-y v))))
 
; Ball -> Ball
; computes movement of ball in one clock tick
(check-expect (move-ball (make-ball (make-posn 20 30)
                                    (make-vel 5 10)))
              (make-ball (make-posn 25 40)
                         (make-vel 5 10)))
(define (move-ball ball)
  (make-ball (move (ball-position ball)
                   (ball-velocity ball))
             (ball-velocity ball)))
 
; A Collision is one of:
; - "top"
; - "down"
; - "left"
; - "right"
; - "none"
; interp. the location where a ball collides with a wall
 
; Posn -> Collision
; detects with which of the walls (if any) the ball collides
(check-expect (collision (make-posn 0 12))  "left")
(check-expect (collision (make-posn 15 HEIGHT)) "down")
(check-expect (collision (make-posn WIDTH 12))  "right")
(check-expect (collision (make-posn 15 0)) "top")
(check-expect (collision (make-posn 55 55)) "none")
(define (collision posn)
  (cond
    [(<= (posn-x posn) BALL-RADIUS) "left"]
    [(<= (posn-y posn) BALL-RADIUS)  "top"]
    [(>= (posn-x posn) (- WIDTH BALL-RADIUS)) "right"]
    [(>= (posn-y posn) (- HEIGHT BALL-RADIUS)) "down"]
    [else "none"]))
 
; Vel Collision -> Vel  
; computes the velocity of an object after a collision
(check-expect (bounce (make-vel 3 4) "left")
              (make-vel -3 4))
(check-expect (bounce (make-vel 3 4) "top")
              (make-vel 3 -4))
(check-expect (bounce (make-vel 3 4) "none")
              (make-vel 3 4))
(define (bounce vel collision)
  (cond [(or (string=? collision "left")
             (string=? collision "right"))
         (make-vel (- (vel-delta-x vel))
                   (vel-delta-y vel))]
        [(or (string=? collision "down")
             (string=? collision "top"))
         (make-vel (vel-delta-x vel)
                   (- (vel-delta-y vel)))]
        [else vel]))
 
; WorldState is a Ball
 
; WorldState -> Image
; renders ball at its position
(check-expect (image? (render INITIAL-BALL)) #true)
(define (render ball)
  (place-image BALL-IMG
               (posn-x (ball-position ball))
               (posn-y (ball-position ball))
               (empty-scene WIDTH HEIGHT)))
 
 
; WorldState -> WorldState
; moves ball to its next location
(check-expect (tick (make-ball (make-posn 20 12) (make-vel 1 2)))
              (make-ball (make-posn 21 14) (make-vel 1 2)))
(define (tick ball)
  (move-ball (make-ball (ball-position ball)
                        (bounce (ball-velocity ball)
                                (collision (ball-position ball))))))
 
(define INITIAL-BALL (make-ball (make-posn 20 12)
                                (make-vel 1 2)))
 
(define (main ws)
  (big-bang ws (on-tick tick 0.01) (to-draw render)))
 
; start with: (main INITIAL-BALL)

Probieren Sie aus, was passiert, wenn der Ball genau in eine Ecke des Spielfeldes fliegt. Wie kann man dieses Problem lösen? Reflektieren Sie in Anbetracht dieses Problems darüber, wieso es wichtig ist, immer die Extremfälle (im Englischen: Corner Cases) zu testen ;-)

6.6 Tagged Unions und Maybe

Wie bereits im Abschnitt Unterscheidbarkeit der Alternativen bemerkt wurde ist es für Summentypen wichtig, dass die einzelnen Alternativen unterscheidbar sind. Nehmen wir zum Beispiel den Datentyp MaybeNumber aus Abschnitt Summentypen:

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

Das Konzept, dass eine Berechnung fehlschlägt, bzw. dass eine Eingabe optional ist, ist sehr häufig anzutreffen. Hier stellt der obige Summentyp eine gute Lösung dar.

Zur Erinnerung: Wir können den Summentyp aber nur so definieren, da der Wert #false nicht in Number enthalten ist und keine Zahl aus Number in der ein-elementigen Menge { #false } enthalten ist. Die beiden Mengen sind disjunkt.

Nun würden wir gerne die gleiche Idee auch für optionale Wahrheitswerte verwenden und definieren daher:

; A BadMaybeBoolean is one of:
; – a Boolean
; – #false
; interp. a boolean if successful, else false.

Die beiden Varianten sind offensichtlich nicht disjunkt: Die Vereinigung von { #true, #false } und { #false } hätte wieder nur zwei Elemente.

Um das zu verhindern, können wir mit einem tag markieren, zu welcher Alternative ein Wert gehört. Hierzu definieren wir zunächst die Strukturen

(define-struct some (value))
(define-struct none ())

Die erste Struktur nutzen wir, um zu markieren, dass es sich bei der Variante um einen vorhandenen Wert handelt – die zweite Struktur nutzen wir, um zu markieren, dass kein Wert vorhanden ist:

; A MaybeBoolean is one of:
; – a structure: (make-some Boolean)
; – (make-none)
; interp. a boolean if successful, else none.

Der Summentyp MaybeBoolean hat nun drei Elemente { (make-none), (make-some #true), (make-some #false) }. Die beiden Alternativen sind nun eindeutig zu unterscheiden. Insbesondere können wir jetzt eine Funktion, die ein MaybeBoolean erwartet, einfach nach dem Entwurfsrezept (in der Version für Summentypen) implementieren.

Würden wir MaybeNumber nun auch auf diese Weise definieren und danach die Summe aus MaybeBoolean und MaybeNumber bilden, hätten wir wieder das ursprüngliche Problem: Es ist nicht unterscheidbar, ob (make-none) "kein Wahrheitswert" oder "keine Zahl" ist. Haben Sie eine Idee, wie sich das Problem lösen lässt?

6.7 Erweiterung des Entwurfsrezepts

Die vorhergehenden Beispiele haben gezeigt, dass viele Probleme es erfordern, parallel mit Funktionen passende Datenstrukturen zu entwickeln. Dies bedeutet, dass sich die Schritte des Entwurfsrezepts aus Abschnitt Entwurfsrezept zur Funktionsdefinition wie folgt ändern:

  1. Wenn in einer Problembeschreibung Information auftauchen, die zusammengehören oder ein Ganzes beschreiben, benötigt man Strukturen. Die Struktur korrespondiert zu dem "Ganzen" und hat für jede "relevante" Eigenschaft ein Feld.

    Eine Datendefinition für ein Feld muss einen Namen für die Menge der Instanzen der Struktur angeben, die durch diese Datendefinition beschrieben werden. Sie muss beschreiben, welche Daten für welches Feld erlaubt sind. Hierzu sollten nur Namen von eingebauten Datentypen oder von Ihnen bereits definierten Daten verwendet werden.

    Geben Sie in der Datendefinition Beispiele für Instanzen der Struktur, die der Datendefinition entsprechen, an.

  2. Nichts ändert sich im zweiten Schritt.

  3. Verwenden Sie im dritten Schritt die Beispiele aus dem ersten Schritt, um Tests zu entwerfen. Wenn eines der Felder einer Struktur, die Eingabeparameter ist, einen Summentypen hat, so sollten Testfälle für alle Alternativen vorliegen. Bei Intervallen sollten die Endpunkte der Intervalle getestet werden.

  4. Eine Funktion die Instanzen von Strukturen als Eingabe erhält wird in vielen Fällen die Felder der Strukturinstanz lesen. Um Sie an diese Möglichkeit zu erinnern, sollte das Template für solche Funktionen die Selektorausdrücke (zum Beispiel (posn-x param) falls param ein Parameter vom Typ Posn ist) zum Auslesen der Felder enthalten.

    Falls der Wert eines Feldes selber Instanz einer Struktur ist, sollten Sie jedoch nicht Selektorausdrücke für die Felder dieser verschachtelten Strukturinstanz ins Template aufnehmen. Meistens ist es besser, die Funktionalität, die diese Unterstruktur betrifft, in eine neue Hilfsfunktion auszulagern.

  5. Benutzen Sie die Selektorausdrücke aus dem Template um die Funktion zu implementieren. Beachten Sie, dass Sie möglicherweise nicht die Werte aller Felder benötigen.

  6. Testen Sie, sobald Sie den Funktionsheader geschrieben haben. Überprüfen Sie, dass zu diesem Zeitpunkt alle Tests fehlschlagen (bis auf die bei denen zufällig der eingesetzte Dummy-Wert richtig ist). Dieser Schritt ist wichtig, denn er bewahrt Sie vor Fehlern in den Tests und stellt sicher, dass ihre Tests auch wirklich eine nicht-triviale Eigenschaft testen.

    Testen Sie so lange, bis alle Ausdrücke im Programm während des Testens mindestens einmal ausgeführt wurden. Die Codefärbung in DrRacket nach dem Testen unterstützt Sie dabei.