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

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:

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.

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