4 Konstruktionsanleitungen

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

4.1 Ablauf

4.2 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.3 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.4 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.5 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.6 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.7 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.8 Fallunterscheidung: Datenanalyse

Versuche, für die Datendefinition eine Formulierung “... ist eins der folgenden” zu finden. Wenn da 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.9 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.10 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.11 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.12 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.13 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-functions 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.14 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.15 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.16 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.17 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.18 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.19 Listen als Eingabe: Schablone

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

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

(define func

(lambda (lis)

(cond

((empty? lis) ...)

((cons? lis)

... (first lis)

... (func (rest lis)) ...))))

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üllen Sie in der Schablone zuerst den empty?-Zweig aus. Vervollständigen Sie dann den anderen Zweig unter der Annahme, daß der rekursive Aufruf (func (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)

((cons? lis)

(+ (first lis)

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

4.20 Natürliche Zahlen als Eingabe: Schablone

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

(: func (natural -> ...))

(define func

(lambda (n)

(if (= n 0)

...

... (func (- 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 (func (- 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.21 Funktionen mit Akkumulatoren: Schablone

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

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

(define func

(lambda (lis)

(func-helper lis z)))

(: func ((list-of elem) sig -> ...))

(define func-helper

(lambda (lis acc)

(cond

((empty? lis) acc)

((cons? lis)

(func-helper (rest lis)

(... (first lis) ... acc ...))))))

Hier ist func der Name der zu definierenden Funktion und func-helper der Name der Hilfsfunktion 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)

((cons? lis)

(invert-helper (rest lis)

(cons? (first lis) acc))))))

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

(: func (natural -> ...))

(define func

(lambda (n)

(func-helper n z)))

(define func-helper

(lambda (n acc)

(if (= n 0)

acc

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