4 Konstruktionsanleitungen

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

4.0 Ablauf

4.1 Kurzbeschreibung

Schreibe für die Funktion zunächst einen Kommentar, der ihren Zweck kurz beschreibt. Ein Satz, der auf eine Zeile passen sollte, reicht. Beispiel:

; monatlichen Rechnungsbetrag für Tarif Billig-Strom berechnen

4.2 Signatur-Deklaration

Schreibe für die Funktion direkt unter die Kurzbeschreibung eine Signatur-Deklaration. Dazu denke Dir zunächst einen möglichst aussagekräftigen Namen aus. Überlege dann, welche Sorten die Ein- und Ausgaben haben und schreibe dann eine Signatur, welche die Ein- und Ausgaben der Funktion möglichst präzise beschreiben. Beispiel:

(: billig-strom (natural -> rational))

Achte bei den Zahlen-Signaturen besonders auf eine möglichst präzise Signatur. Bei billig-strom wäre auch die Signatur (number -> number) korrekt, aber nicht so genau.

4.3 Tests

Schreibe unter die Signatur Tests für die Funktion. Denke Dir dafür möglichst möglichst einfache, aber auch möglichst interessante Beispiele für Aufrufe der Funktion auf und lege fest, was dabei herauskommen soll. Mache aus den Beispielen Tests mit check-expect. Beispiel:

(check-expect (billig-strom 0) 4.9)

(check-expect (billig-strom 10) 6.8)

(check-expect (billig-strom 20) 8.7)

(check-expect (billig-strom 30) 10.6)

Achte darauf, dass die Tests dafür sorgen, dass der Code Deiner Funktion durch die Tests vollständig abgedeckt wird.

4.4 Gerüst

Schreibe unter die Tests ein Gerüst für die Funktion: Dazu übernimmst Du den Namen aus der Signatur-Deklaration in eine Funktionsdefinition wie zum Beispiel:

(define billig-strom

(lambda (...)

...))

Denke Dir Namen für die Eingaben der Funktion aus. Das müssen genauso viele sein, wie die Signatur Eingaben hat. Schreibe dann diese Namen als Eingaben in die lambda-Abstraktion. Beispiel:

(define billig-strom

(lambda (kWh)

...))

4.5 Rumpf

Als letzten Schritt fülle mit Hilfe des Wissens über das Problem den Rumpf der Funktion aus.

(define billig-strom

(lambda (kWh)

(+ 4.9 (* 0.19 kWh))))

4.6 Datenanalyse

Suche in der Aufgabenstellung nach problemrelevanten Größen; Kandidaten sind immer die Substantive. Schreibe für jede dieser Größen eine Datendefinition, es sei denn, diese ist aus dem Kontext offensichtlich.

Wenn es für die Datendefinition noch keine Signatur gibt, schreibe eine Signaturdefinition dazu. Schreibe außerdem Beispiele auf und schreibe jeweils einen Kommentar, der die Beziehung zwischen Daten und Information beschreibt.

4.7 Fallunterscheidung: Datenanalyse

Versuche, für die Datendefinition eine Formulierung “... ist eins der folgenden” zu finden. Wenn das möglich ist, beschreibt Deine Datendefinition eine Fallunterscheidung. Schreibe dann eine Auflistung aller Fälle, jeder Fall auf eine separate Zeile:

; Ein X ist eins der folgenden:

; - Fall 1

; - Fall 2

; - ...

; - Fall n

4.8 Aufzählung: Datenanalyse

Falls Deine Datendefinition eine Fallunterscheidung beschriebt und jeder der Fälle nur aus einem einzelnen Wert besteht, handelt es sich um eine Aufzählung.

Schreibe für jede Aufzählung eine Signaturdefinition der Form:

(define s (signature (one-of ...)))

Achte darauf, dass die Anzahl der Fälle der Signaturdefinition der Anzahl der Fälle der Datendefinition entspricht.

4.9 Schablone

Wenn Du das Gerüst fertiggestellt hast, benutze die Signatur und die dazugehörigen Datendefinitionen, um Konstruktionsanleitungen mit ein oder mehreren Schablonen auszuwählen und übertrage die Elemente der Schablonen in den Rumpf der Funktion.

4.10 Fallunterscheidung: Schablone

Wenn Du eine Funktion schreibst, die eine Fallunterscheidung als Eingabe verarbeitet, schreibe als Schablone in den Rumpf eine Verzweigung mit sovielen Zweigen, wie es in der Fallunterscheidung Fälle gibt, nach folgendem Muster:

(define f

(lambda a

(cond

(... ....)

...

(... ...))))

Schreibe danach Bedingungen in die Zweige, welche die einzelnen Fälle voneinander unterscheiden.

4.11 boolesche Fallunterscheidung: Schablone

Wenn sich das Ergebnis einer Funktion nach einer booleschen Größe richtet, welche die Funktion mit Hilfe der Eingaben berechnen kann, benutze als Schablone im Rumpf eine binäre Verzweigung:

(define f

(lambda (e)

(if ... ; hier wird die boolesche Größe berechnet

...

....)))

4.12 Zusammengesetzte Daten: Datenanalyse

Zusammengesetzte Daten kannst Du an Formulierungen wie “ein X besteht aus ...”, “ein X ist charakterisiert durch ...” oder “ein X hat ...” erkennen. Manchmal lautet die Formulierung etwas anders. Die daraus resultierende Datendefinition ist ein Kommentar im Programm in folgender Form:

; Ein X hat / besteht aus / ist charakterisiert durch:

; - Bestandteil / Eigenschaft 1

; - Bestandteil / Eigenschaft 2

; ...

; - Bestandteil / Eigenschaft n

Auf die Datendefinition folgt eine entsprechende Record-Definition. Dafür überlege Dir Namen für den Record-Typ T und für die Felder, f1 ... fn. Für jedes Feld solltest Du außerdem die dazu passende Signatur sigi angeben. Die Record-Definition hat dann folgende Form:

(define-record T

make-T

(T-f1 sig1)

...

(T-fn sign))

Der Name des Record-Typs T ist die Record-Signatur, make-T ist der Konstruktor und T-fi sind die Selektoren.

Dass der Konstruktorname mit make- anfängt und dass die Selektornamen sich aus dem Namen des Typs und der Felder zusammensetzt, ist reine Konvention. Von ihr solltest Du aber nur aus guten Gründen abweichen.

Unter die Record-Definition gehören die Signaturen für den Konstruktor und die Selektoren:

(: make-T (sig1 ... sign) -> T)

(: T-f1 (T -> sig1))

...

(: T-fn (T -> sign))

4.13 Zusammengesetzte Daten als Eingabe: Schablone

Wenn Deine Funktion zusammengesetzte Daten als Eingabe akzeptiert (das ergibt sich aus der Signatur), gehe nach Schreiben des Gerüstes folgendermaßen vor:

• Für jede dieser Komponenten, schreibe (sel r) in die Schablone, wobei sel der Selektor der Komponente und r der Name des Record-Parameters ist, also zum Beispiel:

  (wallclock-time-hour wt)

• Vervollständige die Schablone, indem Du einen Ausdruck konstruieren, in dem die Selektor-Anwendungen vorkommen.

• Es ist möglich, dass nicht alle Selektor-Anwendungen im Rumpf verwendet werden: In diesem Fall lösche die Selektor-Anwendung wieder.

4.14 Zusammengesetzte Daten als Ausgabe: Schablone

Wenn Deine Funktion zusammengesetzte Daten als Ausgabe hat, schreibe einen Aufruf des passenden Record-Konstruktors in den Rumpf, zunächst mit einer Ellipse für jedes Feld des Records, also zum Beispiel:

(make-wallclock-time ... ...)

4.15 Gemischte Daten: Datenanalyse

Gemischte Daten sind Fallunterscheidungen, bei denen jeder Fall eine eigene Klasse von Daten mit eigener Signatur ist. Schreibe bei gemischten Daten eine Signaturdefinition der folgenden Form unter die Datendefinition:

4.16 Gemischte Daten als Eingabe: Schablone

Eine Schablone für eine Funktion und deren Testfälle, die gemischte Daten akzeptiert, kannst Du folgendermaßen konstruieren:

• Schreibe Tests für jeden der Fälle.

• Schreibe eine cond-Verzweigung als Rumpf in die Schablone, die genau n Zweige hat - also genau soviele Zweige, wie es Fälle in der Datendefinition beziehungsweise der Signatur gibt.

• Schreibe für jeden Zweig eine Bedingung, der den entsprechenden Fall identifiziert.

• Vervollständige die Zweige, indem Du eine Datenanalyse für jeden einzelnen Fall vornimmst und entsprechende Hilfsfunktionen und Konstruktionsanleitungen benutzt. Die übersichtlichsten Programme entstehen meist, wenn für jeden Fall separate Hilfsfunktionen definiert sind.

4.17 Selbstbezüge als Eingabe: Schablone

Wenn Du eine Funktion schreibst, die Daten konsumiert, in denen Selbstbezüge enthalten sind, dann schreibe an die Stellen der Selbstbezüge jeweils einen rekursiven Aufruf.

4.18 Listen als Eingabe: Schablone

Eine Funktion, die eine Liste akzeptiert, hat folgende Schablone:

(: f (... (list-of elem) ... -> ...))

(define f

(lambda (... list ...)

(cond

((empty? list) ...)

((cons? list)

... (first list)

... (f ... (rest list) ...) ...))))

Dabei ist elem die Signatur für die Elemente der Liste. Dies kann eine Signaturvariable (%a, %b, ...) sein, falls die Funktion unabhängig von der Signatur der Listenelemente ist.

Fülle in der Schablone den empty-Zweig aus. Vervollständige den cons- Zweig unter der Annahme, dass der rekursive Aufruf (f (rest lis)) das gewünschte Ergebnis für den Rest der Liste liefert.

Beispiel:

(: list-sum ((list-of number) -> number))

(define list-sum

(lambda (list)

(cond

((empty? list) 0)

((cons? list)

(+ (first list)

(list-sum (rest list)))))))

4.19 Natürliche Zahlen als Eingabe: Schablone

Eine Funktion, die natürliche Zahlen akzeptiert, hat folgende Schablone:

(: f (... natural ... -> ...))

(define f

(lambda (... n ...)

(cond

((zero? n) ...)

((positive? n)

...

(f ... (- n 1) ...)

...))))

Beispiel:

(: power (number natural -> number))

(define power

(lambda (base exponent)

(cond

((zero? exponent) 1)

((positive? base)

(* base

(power base (predecessor exponent)))))))

4.20 Abstraktion

Wenn Du zwei Definitionen geschrieben hast, die inhaltlich verwandt sind und viele Ähnlichkeiten aufweisen, abstrahiere wie folgt:

1. Kopiere eine der beiden Definitionen und gib ihr einen neuen Namen.

2. Ersetze die Stellen, bei denen sich die beiden Definitionen unterscheiden, jeweils durch eine neue Variable.

3. Füge die neuen Variablen als Parameter zum lambda der Definition hinzu oder füge ein neues lambda mit diesen Parametern ein. Du muss gegebenenfalls rekursive Aufrufe der Funktion anpassen.

4. Schreibe eine Signatur für die neue Funktion.

5. Ersetze die beiden alten Definitionen durch Aufrufe der neuen Definition.

Beispiel:

; Definition 1

(define home-points

(lambda (game)

(define goals1 (game-home-goals game))

(define goals2 (game-guest-goals game))

(cond

((> goals1 goals2) 3)

((< goals1 goals2) 0)

((= goals1 goals2) 1))))

; Definition 2

(define guest-points

(lambda (game)

(define goals1 (game-guest-goals game))

(define goals2 (game-home-goals game))

(cond

((> goals1 goals2) 3)

((< goals1 goals2) 0)

((= goals1 goals2) 1))))

; Abstraktion 1

(define compute-points

(lambda (game)

(define goals1 (game-guest-goals game))

(define goals2 (game-home-goals game))

(cond

((> goals1 goals2) 3)

((< goals1 goals2) 0)

((= goals1 goals2) 1))))

; Abstraktion 2

(define make-compute-points

(lambda (get-goals-1 get-goals-2)

(lambda (game)

(define goals1 (get-goals-1 game))

(define goals2 (get-goals-2 game))

(cond

((> goals1 goals2) 3)

((< goals1 goals2) 0)

((= goals1 goals2) 1)))))

4.21 Listen als Eingabe, mit Akkumulator: Schablone

Wenn Du eine Funktion schreibst, die eine Liste akzeptiert und einen Akkumulator benutzen soll, gehe folgendermaßen vor:

1. Überlege Dir, was für Information der Akkumulator repräsentieren soll. Das ist typischerweise ein Zwischenergebnis - also ein vorläufiger Wert für das Endergebnis.

2. Konstruiere die Schablone wie folgt:

   (: f (... (list-of elem) ... -> ...))

   (define f

   (lambda (list0)

   (define accumulate

   ; Invariante

   (lambda (list acc)

   (cond

   ((empty? list) acc)

   ((cons? list)

   (accumulate (rest list) (... (first list) ... acc))))))

   (accumulate list0 ...)))

3. Formuliere eine möglichst konkrete Invariante zwischen list0, list und acc und schreibe sie als Kommentar zu accumulate.

4. Fülle mit Hilfe der Invariante die Ellipsen in der Funktion aus.

Beispiel:

(: list-sum ((list-of number) -> number))

(define list-sum

(lambda (list0)

(define accumulate

; sum ist die Summer aller Elemente in list0 vor list

(lambda (list sum)

(cond

((empty? list) sum)

((cons? list)

(accumulate (rest list) (+ (first list) sum))))))

(accumulate list0 0)))

4.22 Natürliche Zahlen als Eingabe, mit Akkumulator: Schablone

Wenn Du eine Funktion schreibst, die eine natürliche Zahl akzeptiert und einen Akkumulator benutzen soll, gehe folgendermaßen vor:

1. Überlege Dir, was für Information der Akkumulator repräsentieren soll. Das ist typischerweise ein Zwischenergebnis - also ein vorläufiger Wert für das Endergebnis.

2. Konstruiere die Schablone wie folgt:

   (: f (... natural ... -> ...))

   (define f

   (lambda (... n0 ...)

   (define accumulate

   ; Invariante

   (lambda (n acc)

   (cond

   ((zero? n) ... acc ...)

   ((positive? n)

   (accumulate (- n 1) (... n ... acc ...))))))

   (accumulate n0 ...)))

3. Formuliere eine möglichst konkrete Invariante zwischen n0, n und acc und schreibe sie als Kommentar zu accumulate.

4. Fülle mit Hilfe der Invariante die Ellipsen in der Funktion aus.

Beispiel:

(: factorial (natural -> natural))

(define factorial

(lambda (n0)

(define accumulate

; acc ist das Produkt aller Zahlen von (+ n 1) bis n0

(lambda (n acc)

(cond

((zero? n) acc)

((positive? n)

(accumulate (- n 1) (* n acc))))))

(accumulate n0 1)))