On this page:
4.1 Konstruktion von Prozeduren
4.2 Fallunterscheidung
4.3 zusammengesetzte Daten
4.4 zusammengesetzte Daten als Argumente
4.5 zusammengesetzte Daten als Ausgabe
4.6 gemischte Daten
4.7 Listen
4.8 natürliche Zahlen
4.9 Prozeduren mit Akkumulatoren

4 Konstruktionsanleitungen 1 bis 10

This documents the design recipes of the German textbook Schreibe Dein Programm!.

    4.1 Konstruktion von Prozeduren

    4.2 Fallunterscheidung

    4.3 zusammengesetzte Daten

    4.4 zusammengesetzte Daten als Argumente

    4.5 zusammengesetzte Daten als Ausgabe

    4.6 gemischte Daten

    4.7 Listen

    4.8 natürliche Zahlen

    4.9 Prozeduren mit Akkumulatoren

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

  • Signatur (im Buch “Vertrag”) Wählen Sie einen Namen und schreiben Sie eine Signatur für die Prozedur.

  • Testfälle Schreiben Sie einige Testfälle.

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

  • Schablone Leiten Sie aus der Signatur 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.

4.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 (sig -> ...))
(define proc
  (lambda (a)
    (cond
      (test1 ...)
      ...
      (testn ...))))
Dabei ist sig die Signatur, 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.

4.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 (sig1)
; ...
; - Feldn (sign)

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

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

Schreiben Sie außerdem eine Signatur für den Konstruktor der Form:

(: constr (sig1 ... sign -> sig))

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

(: pred? (any -> boolean))
(: select1 (sig -> sig1))
...
(: selectn (sig -> sign))

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

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

4.6 gemischte Daten

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

; Ein x ist eins der Folgenden:
; - Sorte1 (sig1)
; ...
; - Sorten (sign)
; Name: sig

Dabei sind die Sortei umgangssprachliche Namen für die möglichen Sorten, die ein Wert aus diesen gemischten Daten annehmen kann. Die sigi sind die zu den Sorten gehörenden Signaturen. Der Name sig ist für die Verwendung als Signatur.

Aus der Datendefinition entsteht eine Signaturdefinition folgender Form:

(define sig
  (signature
    (mixed sig1
           ...
           sign)))

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 (sig -> ...))
 
(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.

4.7 Listen

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

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

Dabei ist elem die Signatur für die Elemente der Liste. Dies kann eine Signaturvariable (%a, %b, ...) sein, falls die Prozedur unabhängig von der Signatur 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-of number) -> number))
 
(define list-sum
  (lambda (lis)
    (cond
      ((empty? lis) 0)
      ((pair? lis)
       (+ (first lis)
          (list-sum (rest lis)))))))

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

4.9 Prozeduren mit Akkumulatoren

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

(: proc ((list-of elem) -> ...))
 
(define proc
  (lambda (lis)
    (proc-helper lis z)))
 
(: proc ((list-of elem) sig -> ...))
 
(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. Die Signatur sig ist die Signatur für den Akkumulator. Der Ausdruck (... (first lis) ... acc ...) macht aus dem alten Zwischenergebnis acc das neue Zwischenergebnis.

Beispiel:

(: invert ((list-of %a) -> (list-of %a)))
 
(define invert
  (lambda (lis)
    (invert-helper lis empty)))
 
(: invert ((list-of %a) (list-of %a) -> (list-of %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)))))