Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
1095 lines (976 sloc) 37.6 KB
% Diese Datei ist Teil des Buchs "Schreibe Dein Programm!"
% Das Buch ist lizensiert unter der Creative-Commons-Lizenz
% "Namensnennung 4.0 International (CC BY 4.0)"
% http://creativecommons.org/licenses/by/4.0/deed.de
\chapter{Elemente des Programmierens}
\label{cha:whats-programming}
TBD
\section{Handwerkszeug für das Programmieren}
In diesem Kapitel wird zum ersten Mal die Programmierumgebung
\textit{\drscheme{}\index{\drscheme{}}} verwendet. (Bezugsquelle und
weitere Hinweise dazu stehen im Vorwort.) Zur Verwendung mit diesem
Buch müssen in \drscheme{} die DMdA-Sprachebenen\index{DMdA-Sprachebene} aktiviert
werden. Dies geschieht durch Auswahl des Menüpunkts \texttt{Sprache
$\rightarrow$ Sprache auswählen} (bzw.\ \texttt{Language
$\rightarrow$ Choose language} in der englischen Fassung), worauf
ein Dialog zur Auswahl von sogenannten
\textit{Sprach\-ebe\-nen\index{Sprachebene}} erscheint. Dort gibt es
in der Abteilung \texttt{Lehrsprachen} eine Überschrift namens
\texttt{DeinProgramm}, unterhalb dessen mehrere Einträge erscheinen, die
speziell auf die Kapitel dieses Buchs zugeschnitten sind.
Für den ersten Teil des Buches ist die Ebene \texttt{Die Macht der
Abstraktion - Anfänger} zuständig.\index{Sprachebene!Anfänger}
% HK: Die anderen Sprachebenen werden besser an den Stellen angesprochen,
% wo sie erstmalig gebraucht werden, sonst geht diese Information
% unter.
\drscheme{}
bietet dem Programmierer ein zweigeteiltes Fenster:
%
\begin{enumerate}
\item In der oberen Hälfte des Fensters (dem
\textit{Editor\index{Editor}} oder
\textit{Definitionsfenster\index{Definitionsfenster}}) steht der
Programmtext. Der Editor funktioniert ähnlich wie ein reguläres
Textverarbeitungsprogramm.
\item In der unteren Hälfte des Fensters (dem
\textit{Interaktionsfenster\index{Interaktionsfenster}}) werden die
Ausgaben des Programms angezeigt. Außerdem kann
der Programmierer hier "`Fragen"' an das Programm stellen, um
einzelne Programmteile gezielt auszuprobieren.
Im Interaktionsfenster berechnet \drscheme{} die
Antworten sofort nach Druck auf die Return-Taste und
druckt diese aus. Der Inhalt des
Interaktionsfensters kann allerdings nicht direkt abgespeichert werden. Der Editor ist
also für den entstehenden Programmtext gedacht, das Interaktionsfensters zum
schnellen Ausprobieren.
\end{enumerate}
%
\begin{figure}[tb]
\begin{center}
TDB
\caption{Das Interaktionsfenster von \drscheme{}}
\label{fig:drscheme}
\end{center}
\end{figure}
%
TBD
\section{Bausteine für Programme}
\label{sec:programming-elements}
TBD
\section{Rechnen ohne Zahlen}
Ausdrücke und Werte gibt es in Computerprogrammen nicht nur in Form
von Zahlen. Zum Beispiel gibt es auch Text, wie in
Abbildung~\ref{scheme:strings} beschrieben.
(Kästen wie Abbildung~\ref{scheme:strings} werden in diesem
Buch noch oft dazu dienen, neue Sprachelemente einzuführen.)
\begin{feature}{Zeichenketten}{scheme:strings}
\textit{Zeichenketten\index{Zeichenkette}} (auf Englisch
\textit{Strings}\index{String}) repräsentieren Text.
Literale für Zeichenketten haben folgende Form:
%
\begin{alltt}
"\(z\sb{1}\)\(z\sb{2}\) \(\ldots\) \(z\sb{n}\)"
\end{alltt}
%
Dabei sind die \(z\sb{i}\) beliebige einzelne Zeichen, außer \verb|"| selbst.
Beispiel:
%
\begin{alltt}
"Mike was here!"
\end{alltt}
%
Das Anführungszeichen (\verb|"|) kann nicht "`ungeschützt"' vorkommen, da es das Ende der
Zeichenkette markiert. Es wird als Zeichen innerhalb einer Zeichenkette
durch \verb|\"| dargestellt:
%
\begin{alltt}
"Herbert sagt, Mike wäre \backwhack{}"doof\backwhack{}"!"
\end{alltt}
\end{feature}
%
Mit Text kann DrRacket auch rechnen, und zwar mit der eingebauten
Prozedur \texttt{string-append}\index{string-append@\texttt{string-append}}, die zwei Zeichenketten
aneinanderhängt:
%
\begin{alltt}
(string-append "Herbert" "Mike")
\evalsto{} "HerbertMike"
(string-append "Mike" " " "ist doof")
\evalsto{} "Mike ist doof"
\end{alltt}
%
Die eingebaute Prozedur
\texttt{string-length}\index{string-length@\texttt{string-length}}
liefert die Anzahl der Buchstaben in einer Zeichenkette:
%
\begin{alltt}
(string-length "Herbert")
\evalsto{} 7
(string-length "Mike")
\evalsto{} 4
\end{alltt}
%
Die Prozeduren
\texttt{string->number}\index{string->number@\texttt{string->number}}
und \texttt{number->string} konvertieren zwischen Zahlen und den
Zeichenketten, die diese darstellen:
%
\begin{alltt}
(string->number "23")
\evalsto{} 23
(number->string 23)
\evalsto{} "23"
\end{alltt}
%
Programme können auch mit Bildern rechnen. Dazu wird eine
Erweiterung zu DrRacket benötigt, ein sogenanntes
\textit{Teachpack}\index{Teachpack}: Wählen Sie dazu im Menü
\texttt{Sprache} den Punkt \texttt{Teachpack hinzufügen} und wählen
Sie \texttt{image2.ss} aus. Danach können Sie zum Beispiel ins
Programm schreiben:
%
\begin{alltt}
(square 40 "solid" "red")
\evalsto{} \includegraphics[width=1cm]{square.eps}
(circle 40 "solid" "green")
\evalsto{} \includegraphics[width=1cm]{circle.eps}
(star-polygon 20 10 3 "solid" "blue")
\evalsto{} \includegraphics[width=1cm]{starpolygon.eps}
\end{alltt}
%
Diese Bilder sind Werte wie Zahlen und Zeichenketten auch.
Insbesondere können Sie mit Definitionen an Namen gebunden werden:
%
\begin{verbatim}
(define s1 (square 40 "solid" "slateblue"))
(define c1 (circle 40 "solid" "slateblue"))
(define p1 (star-polygon 20 10 3 "solid" "cornflowerblue"))
\end{verbatim}
%
Mit Bildern kann DrRacket ebenfalls rechnen:
%
\begin{alltt}
(beside/align "bottom" s1 c1 p1)
\evalsto{} \includegraphics[width=1cm]{square.eps}\includegraphics[width=1cm]{circle.eps}\includegraphics[width=1cm]{starpolygon.eps}
\end{alltt}
%
Bilder und Animationen mit Bildern werden ausführlich in
Kapitel~\ref{cha:representation-and-state} behandelt.
\section{Namen und Definitionen}
TBD
\section{Information und Daten}
Eine Definition wie
%
\begin{alltt}
(define mehrwertsteuer 19)
\end{alltt}
%
suggeriert, daß die Zahl 19 an dieser Stelle eine Bedeutung "`in der
realen Welt"' hat, zum Beispiel in einem Programm, das eine Registrierkasse
steuert oder das bei der Steuererklärung hilft. Die Bedeutung könnte
folgende Aussage sein: "`Der Mehrwertsteuersatz beträgt 19\%."'
Dieser Satz repräsentiert \textit{Information}\index{Information},
also ein Fakt über die Welt oder zumindest den Ausschnitt der Welt, in
dem das Programm arbeiten soll. In Computerprogrammen wird
Information in eine vereinfachte Form gebracht, mit der das Programm
rechnen kann~-- in diesem Fall die Zahl 19. Diese vereinfachte Form
heißt \textit{Daten}\index{Daten}: Daten sind
\textit{Repräsentationen}\index{Repräsentation} für Information.
Beim Programmieren ist eine
unserer Hauptaufgaben entsprechend, die richtigen Form für die Daten
zu wählen, um die für das Programm relevanten Informationen
darzustellen die Informationen dann in Daten zu übersetzen.
Nicht immer ist offensichtlich, welche Information durch bestimmte
Daten repräsentiert werden. Das Datum 23 zum Beispiel könnte eine Reihe
von Informationen darstellen:
%
\begin{itemize}
\item die Anzahl der Haare von Bruce Willis
\item die aktuelle Außentemperatur in °C in Tübingen
\item die Außentemperatur vom 1.7.2000 in °C in Tübingen
\item die Größe in m$^2$ des Schlafzimmers
\item die Rückennummer von Michael Jordan
\end{itemize}
%
Damit andere unsere Programme lesen können, werden wir also immer
wieder klarstellen müssen, wie Information in Daten zu übersetzen ist
und umgekehrt.
Manche Programme können auch Informationen direkt verarbeiten, meist
dadurch, daß sie diese erst in Daten übersetzen und dann die Daten
weiterverarbeiten. Der Teil, der diese Übersetzung leistet, heißt
\textit{Benutzerschnittstelle}\index{Benutzerschnittstelle}. Zunächst
werden wir uns allerdings primär mit rein datenverarbeitenden
Programmen beschäftigen; Benutzerschnittstellen kommen später.
\section{Domänenwissen}
\label{sec:domaenenwissen}
Hier ist eine einfache Denksportaufgabe:
%
\begin{quote}
Auf einem Parkplatz stehen PKWs und Motorräder ohne Beiwagen.
Zusammen seien es $n$ Fahrzeuge mit insgesamt $m$ Rädern. Bestimmen
Sie die Anzahl $P$ der PKWs.
\end{quote}
%
Die Anzahl $P$ der PKWs plus die Anzahl $M$ der Motorräder muß
offensichtlich die Gesamtzahl $n$ der Fahrzeuge ergeben. Außerdem hat
jeder PKW vier Räder und jedes Motorrad zwei Räder. Die Radzahlen der
PKWs und Motorräder zusammen müssen $m$ ergeben. Es ergibt sich
folgendes Gleichungsystem:
%
\begin{eqnarray*}
P+M&=&n\\
4P+2M&=&m
\end{eqnarray*}
%
Auflösen der ersten Gleichung nach $M$ ergibt
\begin{eqnarray*}
M &=& n-P
\end{eqnarray*}
%
und Einsetzen in die zweite Gleichung führt zu
\begin{eqnarray*}
4P+2(n-P) &=& m\\
4P+2n-2P &=& m\\
2P &=& m-2n\\
P &=& \frac{m-2n}{2}
\end{eqnarray*}
%
Am Ende steht also eine Formel, die wir für konkrete $m$ und $n$ auch
in einen Ausdruck verwandeln können:
%
\begin{alltt}
(/ (- 10 (* 2 4)) 2)
\evalsto{} 1
(/ (- 12 (* 2 3)) 2)
\evalsto{} 3
\end{alltt}
%
Um zu den Ausdrücken zu kommen, welche die Anzahl der PKWs ausrechnen,
haben wir sogenanntes \textit{Domänenwissen}\index{Domänenwissen}
benutzt: Die "`Domäne"' der Aufgabe sind PKWs und Motorräder, und wir
wissen, daß PKWs jeweils vier Räder und Motorräder zwei haben.
Schließlich haben wir noch Algebra benutzt, um aus dem Domänenwissen
eine Formel zu machen.
\section{Kommentare und Formatierung}
Der Ausdruck \texttt{(/ (- 10 (* 2 4)) 2)} ist für unbedarfte Leser
schwer zu verstehen. Manchmal hilft ein erläuternder Text beim
Verständnis:
%
\begin{alltt}
(/ (- 10 (* 2 4)) 2) ; 10 Räder, 4 Fahrzeuge
\evalsto{} 1
(/ (- 12 (* 2 3)) 2) ; 12 Räder, 3 Fahrzeuge
\evalsto{} 3
\end{alltt}
\begin{feature}{Kommentare}{scheme:comment}
Ein Semikolon \texttt{;} kennzeichnet einen
\textit{Kommentar\index{Kommentar}}. Der Kommentar erstreckt sich
vom Semikolon bis zum Ende der Zeile und wird vom Scheme-System
ignoriert.
\end{feature}
%
Der Text nach dem Semikolon ist ein \textit{Kommentar}\index{Kommentar} (siehe
Abbildung~\ref{scheme:comment}), der von DrRacket ignoriert wird, aber
für menschliche Leser hilfreich ist.
Beim Verständnis kann außerdem die
\textit{Formatierung}\index{Formatierung} des Programms helfen. Die
obigen Ausdrücke können auch folgendermaßen geschrieben werden:
%
\begin{alltt}
(/ (- 10 (* 2 4))
2)
(/ (- 12 (* 2 3))
2)
\end{alltt}
%
Daß die \texttt{2} jetzt jeweils in einer weiteren Zeile steht, läßt
die Ausdrücke so ähnlich aussehen wie der Bruch in der Formel. Die
Einrückung vor der \texttt{2} macht klar, daß die \texttt{2} noch in
die Klammern vom \texttt{/} gehört.
Wir als Programmierer müssen uns selbst darum kümmern, an sinnvollen
Stellen eine neue Zeile anzufangen. Um die Einrückung kann sich
allerdings DrRacket automatisch kümmern: Die Tab-Taste (links auf der
Tastatur, meist $\rightarrow$\verb/|/ o.ä.\ bedruckt) rückt die Zeile,
in der sich der Cursor befindet, ein. Außerdem gibt es noch den
Menüpunkt \texttt{Racket} $\rightarrow$ \texttt{Alles einrücken}, der
das gesamte Programm einrückt.
\section{Abstraktion}
Beim Parkplatzproblem aus Abschnitt~\ref{sec:domaenenwissen} ist es
umständlich, für jede Kombination aus konkreten $m$ und $n$ die
Formel neu hinzuschreiben und andere Werte für $m$ und $n$
einzusetzen. Außerdem ist es fehleranfällig. Es muß also besser
gehen. Ein erster Schritt in die richtige Richtung ist, für $m$ und
$n$ auch im Programm Namen zu verwenden:
%
\begin{alltt}
(define n 4)
(define m 10)
(/ (- m (* 2 n)) 2)
\end{alltt}
%
Immerhin ist die ursprüngliche Formel jetzt wieder erkennbar. Leider
kann sie nur einmal verwendet werden. Schreiben wir in dasselbe
Programm die hier darunter:
%
\begin{alltt}
(define n 3)
(define m 12)
(/ (- m (* 2 n)) 2)
\end{alltt}
%
\ldots{} dann meckert DrRacket:
%
\begin{alltt}
m: Für diesen Namen gibt es schon eine Definition
\end{alltt}
%
Für jeden Namen kann es nur eine Definition geben. Wir bräuchten
Formeln, die wir mehrfach verwenden können, bei denen wir sagen können
"`ich werde die Formeln mehrmals benutzen und möchte jedesmal andere
Werte für $n$ und $m$ einsetzen"'. Das geht beim Programmieren mit
\textit{Abstraktion}\index{Abstraktion} und sieht konkret so aus:
%
\begin{alltt}
(lambda (n m) (/ (- m (* 2 n)) 2))
\end{alltt}
%
Diese Abstraktion besteht aus folgenden Bestandteilen:
\begin{itemize}
\item das Schlüsselwort \texttt{lambda},
\item die Namen \texttt{n} und \texttt{m}, die \textit{Parameter},\index{Parameter}
\item der Ausdruck \texttt{(/ (- m (* 2 n)) 2)}, der \textit{Rumpf\index{Rumpf}}.
\end{itemize}
%
Die Abstraktion hat als Wert eine \textit{Prozedur\index{Prozedur}}. Wenn der
$lambda$-Ausdruck so in einem Programm steht, druckt beim Auswerten
DrRacket auch aus:
%
\begin{alltt}
#<procedure>
\end{alltt}
%
Für sich genommen macht eine Prozedur noch nichts interessantes. Sie kann jedoch
\emph{angewendet} werden, was heißt, das konkrete Werte für $m$ und
$n$ eingesetzt werden:
%
\begin{alltt}
((lambda (n m) (/ (- m (* 2 n)) 2)) 4 10)
\evalsto{} 1
((lambda (n m) (/ (- m (* 2 n)) 2)) 3 12)
\evalsto{} 3
\end{alltt}
\begin{feature}{Abstraktion und Anwendung}{scheme:abstraction}
Eine Abstraktion\index{Abstraktion} hat folgende Form:
\begin{alltt}
(lambda (\(p\sb{1} \ldots p\sb{n}\)) \(e\))
\end{alltt}
%
Die $p_i$ jeweils Namen, die \textit{Parameter}\index{Parameter} und
$e$ ist der \textit{Rumpf}\index{Rumpf}. In $e$ dürfen die $p_i$
vorkommen. Der Wert einer Abstraktion ist eine \textit{Prozedur}\index{Prozedur},
welche für jeden Parameter eine Eingabe erwartet.
Eine \textit{Anwendung} einer Prozedur hat folgende Form:
%
\begin{alltt}
(\(p\) \(a\sb{1}\) \ldots \(a\sb{n}\))
\end{alltt}
%
$p$ ist ein Ausdruck, der eine Prozedur ergeben muß, die $a_i$ sind
ebenfalls Ausdrücke, die \textit{Argumente}\index{Argument}. Bei
der Auswertung einer Anwendung werden zunächst $p$ und die $a_i$
ausgewertet; danach geht es mit der Auswertung des Rumpfes der
Prozedur weiter, wobei für die Parameter $p_i$ jeweils die Werte der
Argumente $a_i$ eingesetzt werden.
\end{feature}
%
Abbildung~\ref{scheme:abstraction} erklärt die beiden Konzepte
"`Abstraktion"' und "`Anwendung"' im allgemeinen.
Bisher ist jedoch noch nicht viel gewonnen, weil wir den
$lambda$-Ausdruck jedesmall wiederholen mußten. Da er jedoch beide
Male genau gleich ist, können wir ihm mit \texttt{define} einen Namen
geben:
%
\begin{alltt}
(define parking-lot-cars
(lambda (n m) (/ (- m (* 2 n)) 2)))
\end{alltt}
%
Am besten verteilen wir das Programm gleich noch auf etwas mehr Zeilen
und rücken es ein, um es lesbarer zu machen:
%
\begin{alltt}
(define parking-lot-cars
(lambda (n m)
(/ (- m (* 2 n))
2)))
\end{alltt}
%
\texttt{Parking-lot-cars} können wir jetzt mehrfach verwenden:
%
\begin{alltt}
(parking-lot-cars 4 10)
\evalsto{} 1
(parking-lot-cars 3 12)
\evalsto{} 3
\end{alltt}
%
Das sieht doch schon besser aus: Der Name \texttt{parking-lot-cars}
ist außerdem sprechend und erlaubt uns, die eigentliche Formel auch
wieder zu vergessen.
% FIXME: Warum heißt es eigentlich $lambda$?
\section{Kurzbeschreibung und Signatur}
\label{sec:sorts-and-contracts}
Angenommen, die Prozedurdefinition von \texttt{parking-lot-cars} wird
an jemanden weitergegeben, der dieses Buch nicht gelesen hat, aber die
Prozedur trotzdem einsetzen soll. Der potentielle Leser kann zwar
das Scheme-Programm prinzipiell verstehen, hat aber keinen weiteren
Hinweis darauf, wofür \texttt{parking-lot-cars} verwendet werden kann.
Das Problem ist, daß die Definition von \texttt{parking-lot-cars}
das Endprodukt des Denkprozesses ist, der in Kapitel~\ref{cha:intro}
beschrieben wurde. Der Denkprozeß selbst, der mit der Aufgabenstellung
anfängt, ist nicht Teil der Definition. Darum ist es hilfreich, wenn
wichtige Aspekte des Denkprozesses als Kommentare bei den Definitionen
stehen. Ein stets sinnvoller Kommentar ist eine \textit{Kurzbeschreibung}\index{Kurzbeschreibung} der
Aufgabenstellung:
%
\begin{alltt}
; aus der Anzahl der Fahrzeuge und Räder die Anzahl der PKWs bestimmen
\end{alltt}
%
Für die Kurzbeschreibung reicht in der Regel \emph{eine Zeile}: Nehmen
Sie diese Einschränkung als Gelegenheit, sich knapp, prägnant und
präzise auszudrücken.
Als nächstes ist eine besondere Formulierung hilfreich, die
sogenannte \textit{Signatur\index{Signatur}}. Wer nur gelesen hat, dass die
Prozedur \texttt{parking-lot-cars} zwei Argumente \texttt{n} und
\texttt{m} hat, könnte ja auf den Gedanken kommen, einen Aufruf der
Form
\begin{alltt}
(parking-lot-cars "zweiundzwanzig" "achtunddreissig")
\end{alltt}
zu notieren. Das wird bei der Ausführung eine Fehlermeldung erzeugen, weil die
eingebauten Prozeduren \texttt{/}, \texttt{-} und \texttt{*} nur mit Zahlen in
Form von Ziffernfolgen umgehen können, aber nicht mit Zeichenketten, die
vielleicht auch Zahlen bezeichnen könnten. In der Tat akzeptieren fast alle
Prozeduren nur Argumente einer ganz bestimmten \emph{Sorte}\index{Sorte}, in
diesem Fall Argumente der Sorte "`natürliche Zahl"'.
Hier eine Liste der wichtigsten "`eingebauten"' Sorten:
%
\begin{center}
\begin{tabular}{l|l}
natürliche Zahlen & \texttt{natural}\\\hline
ganze Zahlen & \texttt{integer}\\\hline
rationale Zahlen & \texttt{rational}\\\hline
reelle Zahlen & \texttt{real}\\\hline
Zahlen allgemein (inkl.\ komplexe) & \texttt{number}\\\hline
Zeichenketten & \texttt{string}\\\hline
Bilder & \texttt{image}
\end{tabular}
\end{center}
%
Eine Signatur\index{Signatur}
ist eine Vorstufe für die zu entwickelnde Prozedur und faßt einige
wichtige Informationen zusammen:
%
\begin{enumerate}
\item den Namen der Prozedur,
\item Anzahl und Sorten der Argumente und
\item die Sorte des Rückgabewerts der Prozedur.
\end{enumerate}
%
%Die \textit{Signaturen}\index{Signaturen} beschreiben die Sorten, aus
%denen die Argumente bzw.\ der Rückgabewert stammen.
Die Prozedur
\texttt{parking-lot-cars} akzeptiert zwei natürliche Zahlen und
liefert wieder eine natürliche Zahl. Deshalb sieht die Signatur von
\texttt{parking-lot-cars} so aus:
%
\begin{alltt}
(: parking-lot-cars (natural natural -> natural))
\end{alltt}
%
%Damit wird die Signatur \verb|(natural natural -> natural)| der
%Prozedur \texttt{parking-lot-cars} zugeordnet.
Diese Signatur besagt:
%
\begin{itemize}
\item \texttt{Parking-lot-cars} ist eine Prozedur (das sagt der Pfeil
\verb|->| zusammen mit den Klammern);
\item \texttt{parking-lot-cars}
\textit{akzeptiert}\index{akzeptieren} zwei Argumente (vor dem Pfeil
stehen zwei Wörter);
\item die beiden Argumente sind natürliche Zahlen (\texttt{natural});
\item die Prozedur liefert wieder eine natürliche Zahl (das ist
das \texttt{natural} hinter dem Pfeil).
\end{itemize}
%
Die Signatur ähnelt also der mathematischen Notation für Funktionen,
die einen bestimmten Typ haben.
Aus der Signatur ergeben sich, wenn für die beiden Argumente
sprechende Namen gefunden worden sind, die ersten beiden Zeilen der folgenden
Definition, das sogenannte \textit{Gerüst\index{Gerüst}}:
%
\begin{alltt}
(define parking-lot-cars
(lambda (n m)
...))
\end{alltt}
%
Es bleibt, die passende Formel einzusetzen. Die Definition
von \texttt{parking-lot-cars} sieht dann vollständig so aus:\index{parking-lot-cars@\texttt{parking-lot-cars}}
%
\begin{alltt}
; aus der Anzahl der Fahrzeuge und Räder die Anzahl der PKWs bestimmen
(: parking-lot-cars (natural natural -> natural))
(define parking-lot-cars
(lambda (n m)
(/ (- m (* 2 n))
2)))
\end{alltt}
%
Signaturen können für alle Arten von Werten deklariert werden, nicht
nur für Prozeduren. Zum Beispiel so:
%
\begin{verbatim}
(: pi real)
\end{verbatim}
%
Bei \texttt{parking-lot-cars} ist die Signatur noch nicht besonders
umfangreich oder kompliziert.
Spätere Kapitel werden zeigen, daß sich aus vielen Signaturen ganz
automatisch \textit{Schablonen\index{Schablone}} ergeben, die dem
Programmierer einen Großteil der Denkarbeit bei der Entwicklung von
Prozeduren abnehmen.
Aus diesem Grund schreiben wir in diesem Buch die
Kurzbeschreibung und die Signatur in das Programm, \emph{bevor} wir
die Definition entwickeln:
Die
nachträgliche Entwicklung dieser Kommentare ist mühselig und
langweilig. Außerdem sind die Kurzbeschreibung und die
Signatur ein hilfreicher Teil des Problemlösungsprozesses.
Schon mancher Programmierer~-- Anfänger und Profi~--
ist an Aufgaben gescheitert, die sich mit Hilfe systematischen Vorgehens
anhand der Signatur leicht hätten lösen lassen.
Aus dem fernen Osten stammt der Begriff des "`Mantras"' als einem
Sinnspruch, den es sich lohnt, auswendig zu lernen. Hier das erste Mantra:
%
\begin{mantra}[Signatur vor Ausführung]\label{mantra:contract}
\input{mantra:contract}
\end{mantra}
%
Ab jetzt werden sich die Programmbeispiele in diesem Buch natürlich
an dieses Mantra halten. Kurzbeschreibung, Signatur, Testfälle
(beschrieben im nächsten Abschnitt) Gerüst und
Schablone sind feste Bestandteile einer
\textit{Konstruktionsanleitung\index{Konstruktionsanleitung}}, die
systematisch beschreibt, wie eine Aufgabe schrittweise gelöst werden
kann. Dieses Buch wird eine Reihe von Konstruktionsanleitungen
vorstellen, die sich stets an der Signatur einer Prozedur orientieren.
Alle Mantras sind in Anhang~\ref{cha:mantras} und die
Konstruktionsanleitungen in Anhang~\ref{app:konstruktionsanleitungen}
zusammengefaßt.
\section{Testfälle}
\label{sec:test-cases}
\index{Testfall}Vertrauen ist gut~-- aber Fehler passieren, auch bei
sorgfältiger Programmierung. Angenommen, bei der Programmierung von
\texttt{parking-lot-cars} wäre folgendes herausgekommen:
%
\begin{alltt}
; aus der Anzahl der Fahrzeuge und Räder die Anzahl der PKWs bestimmen
(: parking-lot-cars (natural natural -> natural))
(define parking-lot-cars
(lambda (n m)
(/ (- m (* 4 n))
2)))
\end{alltt}
%
Sehen Sie den Fehler auf den ersten Blick?
Einfaches Ausprobieren ist da vielleicht schneller:
%
\begin{alltt}
(parking-lot-cars 1 4)
\evalsto{} 0
\end{alltt}
%
Bei der Entwicklung der Prozedur sollten also
\textit{Testfälle\index{Testfall}} konstruiert werden, die an
ausgewählten Beispielen überprüfen, ob die gerade programmierte
Prozedur auch korrekt funktioniert. Testen ist eine unverzichtbare
Tätigkeit des Programmierers.
Die Testfälle werden am besten \emph{vor} der Definition der Prozedur
aufgestellt, denn wenn sie erst hinterher geschrieben werden, ist die
Gefahr groß, daß unbewußt das tatsächliche Ergebnis
eines Prozeduraufrufs als das gewünschte eingegeben oder besonders
kritische Beispiele weggelassen werden. (In der industriellen Praxis ist sogar
oft üblich, daß jemand anderes als der Autor der Definitionen
die Testfälle schreibt.)
Es ist mühselig, bei der Programmentwicklung ständig Testfälle in die
REPL einzutippen und durch einen Vergleich mit den erwarteten
Ergebnissen herauszubekommen, ob alles in Ordnung ist. In \drscheme{}
geht es deshalb auch einfacher. Testfälle können zusammen mit den
erwarteten Ergebnissen wie folgt spezifiziert werden:
\begin{alltt}
(check-expect (parking-lot-cars 1 4) 1)
(check-expect (parking-lot-cars 2 6) 1)
(check-expect (parking-lot-cars 10 28) 4)
\end{alltt}
Beim Druck auf den \texttt{Start}-Knopf überprüft \drscheme{}, ob die
tatsächlichen Ergebnisse der Ausdrücke mit den Soll-Werten
übereinstimmen. Für fehlgeschlagene Testfälle öffnet sich ein neues Fenster
mit Informationen über die Unterschiede zwischen erwarteten und
tatsächlichen Ergebnissen; ansonsten gibt es eine kurze Meldung, dass die
Testfälle erfolgreich waren. Für die obere inkorrekte Version kommt
zum Beispiel folgendes heraus:
%
\begin{alltt}
3 Tests gelaufen.
0 Tests bestanden.
2 Signaturverletzungen.
Check-Fehler:
Der tatsächliche Wert 0 ist nicht der erwartete Wert 1.
in Zeile 4, Spalte 0
Der tatsächliche Wert -1 ist nicht der erwartete Wert 1.
in Zeile 5, Spalte 0
Der tatsächliche Wert -6 ist nicht der erwartete Wert 4.
in Zeile 6, Spalte 0
Signaturverletzungen:
bekam -1 in Zeile 5, Spalte 14 , Signatur in Zeile 2, Spalte 40
verantwortlich: Prozedur in Zeile 9, Spalte 2
bekam -6 in Zeile 6, Spalte 14 , Signatur in Zeile 2, Spalte 40
verantwortlich: Prozedur in Zeile 9, Spalte 2
\end{alltt}
%
Eine großzügige Verwendung
von Testfällen kann viele Programmierfehler
aufdecken und damit die Programmierung erleichtern und beschleunigen.
\begin{mantra}[Testfälle]\label{mantra:test}
\input{mantra:test}
\end{mantra}
% FIXME: Coverage
\section{Unsinnige Daten}
\label{sec:nonsensical-data-prequel}
Die Testfälle aus dem vorangegangenen Abschnitt sind alle
"`sinnvoll"'~-- die Eingabedaten passen alle zu tatsächlichen
Parkplatzsituationen. Was ist aber hiermit?
%
\begin{alltt}
(parking-lot-cars 3 9)
\end{alltt}
%
Wie schon in Kapitel~\ref{page:parking-lot-problem}
(Seite~\pageref{page:parking-lot-problem}) bereits angedeutet,
lassen sich die \emph{Daten} 3 und 9 nicht als \emph{Information}
interpretieren: Es gibt keinen Parkplatz mit 3 Fahrzeugen und 9
Rädern~-- zumindest nicht mit den Einschränkungen der Aufgabenstellung
auf vollberäderte PKWs und Motorräder.
Die Prozedur \texttt{parking-lot-cars} stört dies allerdings wenig:
Sie liefert munter die Ausgabe \texttt{1.5}. Allerdings meldet
DrRacket eine \textit{Signaturverletzung}\index{Signaturverletzung},
wenn es \texttt{(parking-lot-cars 3 9)} auswertet, da das Ergebnis
keine natürliche Zahl ist wie in der Signatur angegeben.
Das Programm sollte natürlich abseits der Signaturverletzung unsinnige
Daten soweit möglich und praktikabel zurückweisen. Für die Eingabe
\texttt{(parking-lot-cars 3 16)} hätte es nämlich keine Signaturverletzung
gegeben, sondern es wäre eine zunächst unschuldig aussehende $5$
herausgekommen. Da hätte es zuerst noch der Beobachtung bedurft, dass unmöglich
$5$ von $3$ Fahrzeugen PKWs sein können. Noch fehlen uns
die Mittel, solche unsinnigen Eingaben zurückzuweisen; in Abschnitt~\ref{sec:nonsensical-data} werden wir
dies nachholen.
\section{Probleme und Teilprobleme}
\label{sec:subproblems}
TBD
\section{Auswertung}
\label{sec:substitution-model}
\label{sec:scheme-anatomy}
Bei der Auswertung eines Programms geht DrRacket nach festen Regeln
vor. Schauen wir uns noch einmal das Programm zum Parkplatzproblem
an:
%
\begin{alltt}
(define parking-lot-cars
(lambda (n m)
(/ (- m (* 2 n))
2)))
(parking-lot-cars 4 10)
\end{alltt}
%
Bei der Auswertung \textit{substituiert}\index{Substitution} DrRacket
jeweils Namen durch ihre Werte. Der erste Schritt ist also,
\texttt{parking-lot-cars} durch den dazugehörigen
\texttt{lambda}-Ausdruck zu ersetzen:
%
\begin{alltt}
(parking-lot-cars 4 10)
\evalsto
((lambda (n m) (/ (- m (* 2 n)) 2)) 4 10)
\end{alltt}
%
Jetzt steht dort die Anwendung eines \texttt{lambda}-Ausdrucks auf die
zwei Zahlen \texttt{4} und \texttt{10}: Diese Argumente werden für die
ensprechenden Parameter \texttt{n} und \texttt{m} eingesetzt:
%
\begin{alltt}
((lambda (n m) (/ (- m (* 2 n)) 2)) 4 10)
\evalsto
(/ (- 10 (* 2 4)) 2)
\end{alltt}
%
Nun werden sukzessive die Teilausdrücke ausgewertet. Das passiert
immer von links nach rechts. Bei einer Anwendung werden erst einmal
alle Argumente fertig ausgewertet, bevor es mit der Substitution der
Parameter und dem Rumpf der Prozezedur weitergeht:
%
\begin{alltt}
(/ (- 10 (* 2 4)) 2)
\evalsto
(/ (- 10 8) 2)
\evalsto
(/ 2 2)
\evalsto
1
\end{alltt}
%
Diese Vorgehensweise entspricht der Algebra aus der Mathematik, wo wir
auch Ausdrücke umformen, indem wir gleiches durch gleiches ersetzen.
\begin{figure}[tb]
\centering
\includegraphics[width=\textwidth]{i1prog/stepper.png}
\caption{Stepper in DrRacket}
\label{fig:stepper}
\end{figure}
%
Normalerweise zeigt uns DrRacket nur das Endergebnis dieses Prozesses
an. Es ist aber auch in der Lage, die Schritte einzeln zu
visualisieren: Dazu müssen Sie auf den \texttt{Step}-Knopf drücken.
Es erscheint ein neues Fenster, der sogenannte \textit{Stepper}\index{Stepper}.
Sie können dann vorwärts und rückwärts durch den Substitutionsprozeß
navigieren. Abbildung~\ref{fig:stepper} zeigt das Stepper-Fenster.
\section*{Aufgaben}
\begin{aufgabe}
Betrachten Sie folgende Stromtarife. Beide Tarife
bestehen aus einer monatlichen Grundgebühr und einem Teil, der sich
nach den verbrauchten Kilowattstunden (kWh) richtet.
%
\begin{center}
\begin{tabular}{l|c|c|}
& Grundgebühr pro Monat & Verbrauchspreis pro kWh \\
\hline
Tarif "`Billig-Strom"' & 4,90 Euro & 19 Cent \\
\hline
Tarif "`Watt für wenig"' & 8,20 Euro & 16 Cent \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}
\item Schreiben Sie eine Prozedur
\texttt{billig-strom}, die den Monatsverbrauch in Kilowattstunden
akzeptiert und den im Tarif "`Billig-Strom"' zu zahlenden
monatlichen Rechnungsbetrag für einen übergebenen Verbrauch
berechnet.
\item Schreiben Sie eine Prozedur
\texttt{watt-für-wenig}, die den Monatsverbrauch in
Kilowattstunden akzeptiert und den im Tarif "`Watt für wenig"' zu
zahlenden monatlichen Rechnungsbetrag für einen übergebenen
Verbrauch berechnet.
\end{enumerate}
Halten Sie sich bei jeder Prozedur, die Sie schreiben, an die
Konstruktionsanleitungen: Schreiben Sie zuerst die Kurzbeschreibung
und die Signatur. Schreiben Sie als nächstes einige Testfälle.
Leiten Sie danach das Gerüst von der Signatur her und vervollständigen
Sie den Rumpf der Prozedur.
\end{aufgabe}
\begin{aufgabe}
Vervielfachung von Strings:
\begin{itemize}
\item Schreiben Sie eine Prozedur \texttt{double-string}, die eine Zeichenkette konsumiert und
diese "`verdoppelt"', d.h., für eine Eingabe \verb|"Sperber"| den
Rückgabewert \verb|"SperberSperber"| liefert.
\item Schreiben Sie eine Prozedur \texttt{quadruple-string}, die eine
Zeichenkette konsumiert und "`vervierfacht"'.
\item Schreiben Sie eine Prozedur \texttt{octuple-string}, die eine
Zeichenkette konsumiert und "`verachtfacht"'.
\item Schreiben Sie eine Prozedur \texttt{sixteentuple-string}, die
eine Zeichenkette konsumiert und "`versechzehnfacht"'.
\end{itemize}
% Schreiben Sie für jede Prozedur Kurzbeschreibung, Signatur, Testfälle, Gerüst und Rumpf.
%Vermeiden Sie bei all diesen Aufgaben, Code mehrfach zu schreiben.
\end{aufgabe}
\begin{aufgabe}
Ein Boot überquert einen Fluss mit Strömung und
kommt durch die Strömung vom geplanten Kurs ab. Dadurch wird die
Strecke, die das Boot tatsächlich zurücklegt, länger.
\begin{center}
\includegraphics{riverboat}
\end{center}
Geben ist die Breite des Flusses $a$, die Strömungsgeschwindigkeit
des Flusses $v_{\text{Fluss}}$ und die Geschwindigkeit des Bootes
$v_{\text{Boot}}$. Berechnen Sie die Länge der Strecke, die das
Boot tatsächlich zurücklegt. Programmieren Sie dazu Prozeduren, die
folgende Teilprobleme lösen:
\begin{enumerate}
\item Schreiben Sie zunächst eine Prozedur \texttt{speed-ratio}, die
das Verhältnis der Strömungsgeschwindigkeit des Flusses
$v_{\text{Fluss}}$ zur Geschwindigkeit des Bootes
$v_{\text{Boot}}$ berechnet.
\item Schreiben Sie dann eine Prozedur \texttt{other-shore-offset},
die die Länge der Strecke berechnet, die das Boot abgetrieben wird
(also den Versatz am anderen Ufer, im Schaubild die Strecke $b$).
% Dazu müssen Sie die Breite des Flusses $a$ mit dem Verhältnis von
% $v_{\text{Fluss}}$ zu $v_{\text{Boot}}$ multiplizieren.
\item Um $c$ zu berechnen, brauchen Sie den \textit{Satz des
Pythagoras}:
\begin{displaymath}
a^2 + b^2 = c^2
\end{displaymath}
Schreiben Sie eine Prozedur \texttt{pythagoras}, die $c$ der
obigen Gleichung berechnet. Erkennen und abstrahieren Sie weitere
Teilprobleme!
\item Schreiben Sie schließlich eine Prozedur
\texttt{boat-travel-distance}, die die tatsächliche Strecke
berechnet, die das Boot zurücklegt. Benutzen Sie dafür die bisher
geschriebenen Prozeduren.
\end{enumerate}
\end{aufgabe}
\begin{aufgabe}
In den USA und in Europa gibt es unterschiedliche
Maße für die Energieeffizienz von Kraftfahrzeugen:
\begin{itemize}
\item In Europa ist das gängige Maß der \emph{Verbrauch} in Liter
pro 100km (l/100km);
\item in den USA ist das gängige Maß die \emph{Reichweite} in Meilen
pro Gallone (mi/gal).
\end{itemize}
Schreiben Sie Prozeduren, die zwischen beiden Maßeinheiten
umrechnen. Gehen Sie dazu wie folgt vor:
Halten Sie sich bei jeder Prozedur, die Sie schreiben, an die
Konstruktionsanleitungen: Schreiben Sie zuerst die Kurzbeschreibung
und die Signatur. Schreiben Sie als nächstes einige Testfälle.
Leiten Sie danach das Gerüst von der Signatur her und vervollständigen
Sie den Rumpf der Prozedur.
\begin{enumerate}
\item Schreiben Sie eine Prozedur
\texttt{liters-per-hundred-kilometers}, die eine Menge Benzin in
Liter und die Reichweite dieses Benzins in Kilometer akzeptiert
und daraus den Verbrauch in Liter pro 100km berechnet.
\item Schreiben Sie eine Prozedur
\texttt{miles-per-gallon}, die eine Entfernung in Meilen und den
Benzinverbrauch auf diese Entfernung in Gallonen akzeptiert und
daraus die Reichweite in Meilen pro Gallone berechnet.
\item Definieren Sie eine Konstante
\texttt{kilometers-per-mile} (eine US-Meile entspricht etwa $1,61$
Kilometer) und schreiben Sie zwei Prozeduren
\texttt{kilometers->miles} und \texttt{miles->kilometers}, die
jeweils eine Entfernung in einer Maßeinheit akzeptieren und die
Entfernung in die jeweils andere Maßeinheit umrechnen.
\item Definieren Sie eine Konstante
\texttt{liters-per-gallon} (eine Gallone entspricht etwa $3,79$
Liter) und schreiben Sie zwei Prozeduren \texttt{liters->gallons}
und \texttt{gallons->liters}, die jeweils eine Menge in einer
Maßeinheit akzeptieren und die Menge in die jeweils andere
Maßeinheit umrechnen.
\item Schreiben Sie die Prozedur
\texttt{l/100km->mi/gal}, die einen Verbrauch in Liter pro 100km
akzeptiert und in die Reichweite in Meilen pro Gallone umrechnet.
Benutzen Sie dafür die Prozeduren, die Sie in den anderen
Teilaufgaben erstellt haben. Sollten Sie auf weitere Teilprobleme
stoßen, abstrahieren Sie diese Teilprobleme in eigene Prozeduren.
\item Schreiben Sie die Prozedur
\texttt{mi/gal->l/100km}, die eine Reichweite in Meilen pro
Gallone akzeptiert und in den Verbrauch in Liter pro 100km
umrechnet. Benutzen Sie dafür die Prozeduren, die Sie in den
anderen Teilaufgaben erstellt haben. Sollten Sie auf weitere
Teilprobleme stoßen, abstrahieren Sie diese Teilprobleme in eigene
Prozeduren.
\item Finden Sie heraus, wie hoch der Benzinverbrauch
verschiedener Kraftfahrzeuge ist, die Sie täglich im
Straßenverkehr in Deutschland sehen. Vergleichen Sie diesen
Verbrauch mit den Reichweitenangaben typischer Kraftfahrzeuge für
den US-amerikanischen Markt.
\end{enumerate}
\end{aufgabe}
% In vielen Ländern sind die Benzinpreise ein Grund zur allgemeinen
% Aufregung. In Deutschland wird immer die magische Marke von 1,50
% Euro pro Liter genannt, die USA haben große Angst vor der 4 Dollar
% pro Gallone. Auch sind Spritsparende Autos immer beliebter, in
% Deutschland wird auf das 3 Liter auf 100km Auto gehofft, die USA
% wünschen sich mehr 55 Meilen pro Gallone Autos. Diese verschiedenen
% Maßstäbe sind verwirrend.
% FIXME: Hier taucht noch "Substitutionsmodell" auf.
% FIXME: umbenennen von n und m in parking-lot-cars in sprechende Namen
\begin{aufgabe}
Betrachten Sie das folgende Programm:
\begin{verbatim}
(define x 2) ; --> zwei
(define y -1) ; --> minuseins
(define z -3) ; --> minusdrei
(define f
(lambda (x z)
(+ (* x x) z y)))
(f 4 -2)
\end{verbatim}
%
Benennen Sie die Variablen \verb"x", \verb"y" und \verb"z", die in
den ersten drei Zeilen des Programms definiert werden, im kompletten
Programm um, und zwar \verb|x| in \verb|zwei|, \verb|y| in
\verb|minuseins| und \verb|z| in \verb|minusdrei|. Achten Sie bei
der Umbenennung auf die lexikalische Bindung. Benennen Sie keine
Parameter der Prozedur \verb"f" um.
Nachdem Sie die Umbenennung durchgeführt haben, welches Ergebnis liefert
der Ausdruck \verb"(f 4 -2)"? Berechnen Sie das Ergebnis von Hand mit Hilfe
des Substitutionsmodells und halten Sie die Zwischenschritte fest.
\end{aufgabe}
\begin{aufgabe}
Betrachten Sie das folgende Programm:
\begin{verbatim}
(define x 2) ; --> zwei
(define y 4) ; --> vier
(define z ; --> f
(lambda (x y z)
(+ x (z y))))
(z y x (lambda (z) (+ x z)))
\end{verbatim}
%
Benennen Sie die Variablen \verb"x", \verb"y" und \verb"z", die in
den ersten drei Zeilen des Programms definiert werden, im kompletten
Programm um. Der neue Name der Variable steht als Kommentar im
Programm hinter dem Pfeil (\verb"-->"). Achten Sie bei der
Umbenennung auf die lexikalische Bindung. Benennen Sie keine
Parameter der Prozedur \verb"z" um.
Berechnen Sie, nachdem Sie die Umbenennung durchgeführt haben, von
Hand mit dem Substitutionsmodell \verb"(z y x"
\verb"(lambda (z) (+ x z))))" und halten Sie die Zwischenschritte
fest.
\end{aufgabe}
\begin{aufgabe}
Betrachten Sie das folgende Programm:
\begin{verbatim}
(define x 1)
(define y 3)
(define z 5)
(define f
(lambda (x)
((lambda (y)
((lambda (z)
(+ z (* x y)))
(+ x z)))
(+ x y))))
(f y)
\end{verbatim}
Benennen Sie hier alle lokalen Variablen, die innerhalb der Prozedur
\verb"f" gebunden werden, um. Verändern Sie nicht den Namen der
Variablen \verb"x", \verb"y" und \verb"z" aus den ersten drei Zeilen
des Programms.
Nachdem Sie die Umbenennung durchgeführt haben, welches Ergebnis liefert
der Ausdruck \verb"(f y)"? Berechnen Sie das Ergebnis von Hand mithilfe
des Substitutionsmodells und halten Sie die Zwischenschritte fest.
\noindent \emph{Hinweis:} In diesen Aufgaben finden Sie keine
Kommentare und Signaturen zu den Prozeduren. Hier können Sie an einem
Beispiel sehen, dass es sehr wichtig ist, diese Informationen
anderen Programmierern immer zur Verfügung zu stellen. Denn es kann
auch bei kleinen Programmen schwer sein, die Funktionsweise der
einzelnen Prozeduren ohne Kommentare zu verstehen.
\end{aufgabe}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "i1"
%%% End: