On this page:
5.1 Konstruktion von Prozeduren
5.2 Fallunterscheidung
5.3 zusammengesetzte Daten
5.4 zusammengesetzte Daten als Argumente
5.5 zusammengesetzte Daten als Ausgabe
5.6 gemischte Daten
5.7 Listen
5.8 natürliche Zahlen
5.9 Prozeduren mit Akkumulatoren
5.10 gekapselter Zustand

5 Konstruktionsanleitungen 1 bis 10

This documents the design recipes of the German textbook Die Macht der Abstraktion.

    5.1 Konstruktion von Prozeduren

    5.2 Fallunterscheidung

    5.3 zusammengesetzte Daten

    5.4 zusammengesetzte Daten als Argumente

    5.5 zusammengesetzte Daten als Ausgabe

    5.6 gemischte Daten

    5.7 Listen

    5.8 natürliche Zahlen

    5.9 Prozeduren mit Akkumulatoren

    5.10 gekapselter Zustand

5.1 Konstruktion von Prozeduren

Gehen Sie bei der Konstruktion einer Prozedur in folgender Reihenfolge vor:
  • Kurzbeschreibung Schreiben Sie eine einzeilige Kurzbeschreibung.

  • Datenanalyse Führen Sie eine Analyse der beteiligten Daten durch. Stellen Sie dabei fest, zu welcher Sorte die Daten gehören, ob Daten mit Fallunterscheidung vorliegen und ob zusammengesetzte oder gemischte Daten vorliegen.

  • Vertrag Wählen Sie einen Namen und schreiben Sie einen Vertrag für die Prozedur.

  • Testfälle Schreiben Sie einige Testfälle.

  • Gerüst Leiten Sie direkt aus dem Vertrag das Gerüst der Prozedur her.

  • Schablone Leiten Sie aus dem Vertrag und der Datenanalyse mit Hilfe der Konstruktionsanleitungen eine Schablone her.

  • Rumpf Vervollständigen Sie den Rumpf der Prozedur.

  • Test Vergewissern Sie sich, daß die Tests erfolgreich laufen.

5.2 Fallunterscheidung

Wenn ein Argument einer Prozedur zu einer Fallunterscheidung gehört, die möglichen Werte also in feste Kategorien sortiert werden können, steht im Rumpf eine Verzweigung. Die Anzahl der Zweige entspricht der Anzahl der Kategorien.

Die Schablone für eine Prozedur proc, deren Argument zu einer Sorte gehört, die n Kategorien hat, sieht folgendermaßen aus:

  (: proc (ctr -> ...))
  (define proc
    (lambda (a)
      (cond
        (test1 ...)
        ...
        (testn ...))))
Dabei ist ctr der Vertrag, den die Elemente der Sorte erfüllen müssen. Die testi müssen Tests sein, welche die einzelnen Kategorien erkennen. Sie sollten alle Kategorien abdecken. Der letzte Zweig kann auch ein else-Zweig sein, falls klar ist, daß a zum letzten Fall gehört, wenn alle vorherigen testi #f ergeben haben. Anschließend werden die Zweige vervollständigt.

Bei Fallunterscheidungen mit zwei Kategorien kann auch if statt cond verwendet werden.

5.3 zusammengesetzte Daten

Wenn bei der Datenanalyse zusammengesetzte Daten vorkommen, stellen Sie zunächst fest, welche Komponenten zu welchen Sorten gehören. Schreiben Sie dann eine Datendefinition, die mit folgenden Worten anfängt:

  ; Ein x besteht aus / hat:
  ; - Feld1 (ctr1)
  ; ...
  ; - Feldn (ctrn)

Dabei ist x ein umgangssprachlicher Name für die Sorte (“Schokokeks”), die Feldi sind umgangssprachliche Namen und kurze Beschreibungen der Komponenten und die ctri die dazugehörigen Verträge.

Übersetzen Sie die Datendefinition in eine Record-Definition, indem Sie auch Namen für den Record-Vertrag ctr, Konstruktor constr, Prädikat pred? und die Selektoren selecti wählen:
  (define-record-procedures ctr
    constr pred?
    (select1 ... selectn))

Schreiben Sie außerdem einen Vertrag für den Konstruktor der Form:

  (: constr (ctr1 ... ctrn -> ctr))

Ggf. schreiben Sie außerdem Verträge für das Prädikat und die Selektoren:

  (: pred? (%a -> boolean))
  (: select1 (ctr -> ctr1))
  ...
  (: selectn (ctr -> ctrn))

5.4 zusammengesetzte Daten als Argumente

Wenn ein Argument einer Prozedur zusammengesetzt ist, stellen Sie zunächst fest, von welchen Komponenten des Records das Ergebnis der Prozeduren abhängt.

Schreiben Sie dann für jede Komponente (select a) in die Schablone, wobei select der Selektor der Komponente und a der Name des Parameters der Prozedur ist.

Vervollständigen Sie die Schablone, indem Sie einen Ausdruck konstruieren, in dem die Selektor-Anwendungen vorkommen.

5.5 zusammengesetzte Daten als Ausgabe

Eine Prozedur, die einen neuen zusammengesetzten Wert zurückgibt, enthält einen Aufruf des Konstruktors des zugehörigen Record-Typs.

5.6 gemischte Daten

Wenn bei der Datenanalyse gemischte Daten auftauchen, schreiben Sie eine Datendefinition der Form:

  ; Ein x ist eins der Folgenden:
  ; - Sorte1 (ctr1)
  ; ...
  ; - Sorten (ctrn)
  ; Name: ctr

Dabei sind die Sortei umgangssprachliche Namen für die möglichen Sorten, die ein Wert aus diesen gemischten Daten annehmen kann. Die ctri sind die zu den Sorten gehörenden Verträge. Der Name ctr ist für die Verwendung als Vertrag.

Aus der Datendefinition entsteht eine Vertragsdefinition folgender Form:

  (define ctr
    (contract
      (mixed ctr1
             ...
             ctrn)))

Wenn die Prädikate für die einzelnen Sorten pred?1 ... pred?n heißen, hat die Schablone für eine Prozedur, die gemischte Daten konsumiert, die folgende Form:

  (: proc (ctr -> ...))
  
  (define proc
    (lambda (a)
      (cond
        ((pred?1 a) ...)
        ...
        ((pred?n a) ...))))

Die rechten Seiten der Zweige werden dann nach den Konstruktionsanleitungen der einzelnen Sorten ausgefüllt.

5.7 Listen

Eine Prozedur, die eine Liste konsumiert, hat die folgende Schablone:

  (: proc ((list elem) -> ...))
  
  (define proc
    (lambda (lis)
      (cond
        ((empty? lis) ...)
        ((pair? lis)
         ... (first lis)
         ... (proc (rest lis)) ...))))

Dabei ist elem der Vertrag für die Elemente der Liste. Dies kann eine Vertragsvariable (%a, %b, ...) sein, falls die Prozedur unabhängig vom Vertrag der Listenelemente ist.

Füllen Sie in der Schablone zuerst den empty?-Zweig aus. Vervollständigen Sie dann den anderen Zweig unter der Annahme, daß der rekursive Aufruf (proc (rest lis)) das gewünschte Ergebnis für den Rest der Liste liefert.

Beispiel:

  (: list-sum ((list number) -> number))
  
  (define list-sum
    (lambda (lis)
      (cond
        ((empty? lis) 0)
        ((pair? lis)
         (+ (first lis)
            (list-sum (rest lis)))))))

5.8 natürliche Zahlen

Eine Prozedur, die natürliche Zahlen konsumiert, hat die folgende Schablone:

  (: proc (natural -> ...))
  
  (define proc
    (lambda (n)
      (if (= n 0)
          ...
          ... (proc (- n 1)) ...)))

Füllen Sie in der Schablone zuerst den 0-Zweig aus. Vervollständigen Sie dann den anderen Zweig unter der Annahme, daß der rekursive Aufruf (proc (- n 1)) das gewünschte Ergebnis für n-1 liefert.

Beispiel:

  (: factorial (natural -> natural))
  
  (define factorial
    (lambda (n)
      (if (= n 0)
          1
          (* n (factorial (- n 1))))))

5.9 Prozeduren mit Akkumulatoren

Eine Prozedur mit Akkumulator, die Listen konsumiert, hat die folgende Schablone:

  (: proc ((list elem) -> ...))
  
  (define proc
    (lambda (lis)
      (proc-helper lis z)))
  
  (: proc ((list elem) ctr -> ...))
  
  (define proc-helper
    (lambda (lis acc)
      (cond
        ((empty? lis) acc)
        ((pair? lis)
         (proc-helper (rest lis)
                      (... (first lis) ... acc ...))))))

Hier ist proc der Name der zu definierenden Prozedur und proc-helper der Name der Hilfsprozedur mit Akkumulator. Der Anfangswert für den Akkumulator ist der Wert von z. Der Vertrag ctr ist der Vertrag für den Akkumulator. Der Ausdruck (... (first lis) ... acc ...) macht aus dem alten Zwischenergebnis acc das neue Zwischenergebnis.

Beispiel:

  (: invert ((list %a) -> (list %a)))
  
  (define invert
    (lambda (lis)
      (invert-helper lis empty)))
  
  (: invert ((list %a) (list %a) -> (list %a)))
  
  (define invert-helper
    (lambda (lis acc)
      (cond
        ((empty? lis) acc)
        ((pair? lis)
         (invert-helper (rest lis)
                        (make-pair (first lis) acc))))))

Eine Prozedur mit Akkumulator, die natürliche Zahlen konsumiert, hat die folgende Schablone:

  (: proc (natural -> ...))
  
  (define proc
    (lambda (n)
      (proc-helper n z)))
  
  (define proc-helper
    (lambda (n acc)
      (if (= n 0)
          acc
          (proc-helper (- n 1) (... acc ...)))))

Dabei ist z das gewünschte Ergebnis für n = 0. Der Ausdruck (... acc ...) muß den neuen Wert für den Akkumulator berechnen.

Beispiel:

  (: ! (natural -> natural))
  
  (define !
    (lambda (n)
      (!-helper n 1)))
  
  (define !-helper
    (lambda (n acc)
      (if (= n 0)
          acc
          (!-helper (- n 1) (* n acc)))))

5.10 gekapselter Zustand

Falls ein Wert Zustand enthalten soll, schreiben Sie eine Datendefinition wie bei zusammengesetzten Daten.

Schreiben Sie dann eine Record-Definition mit define-record-procedures-2 und legen Sie dabei fest, welche Bestandteile veränderbar sein sollen. Geben Sie Mutatoren für die betroffenen Felder an. Wenn der Selektor für das Feld select heißt, sollte der Mutator i.d.R. set-select! heißen. Die Form sieht folgendermaßen aus, wobei an der Stelle k ein veränderbares Feld steht:

  (define-record-procedures-2 ctr
    constr pred?
    (select1 ... (sk mutatek) ... sn))

In der Schablone für Prozeduren, die den Zustand eines Record-Arguments r ändern, benutzen Sie den dazugehörigen Mutator mutatek Wenn a der Ausdruck für den neuen Wert der Komponente ist, sieht der Aufruf folgendermaßen aus: (mutatek r a).

Um mehrere Komponenten in einer Prozedur zu verändern, oder um einen sinnvollen Rückgabewert nach einer Mutation zu liefern, benutzen Sie begin.