{
}
\newcommand{\BC}{\begin{center}}
\newcommand{\EC}{\end{center}}
\newcommand{\IT}{\item}
\newcommand{\bottom}{\perp}
\newcommand{\RA}{\rightarrow}
\newcommand{\RRA}{\Rightarrow}
\newcommand{\BT}{\begin{tabular}{p{1cm}cp{5.5cm}l}}
\newcommand{\ET}{\end{tabular}}
\newcommand{\ab}{\hspace*{1cm}}
\newcommand{\ah}{\hspace*{.5cm}}
\newcommand{\botelem}{\bot\!\!\!\in}
\newcommand{\topelem}{\top\!\!\!\!\in}
\newcommand{\nablaelem}{\nabla\!\!\!\in}
\newcommand{\triangleelem}{\triangle\!\!\!\in}
\newcommand{\comment}[1]{}
\title{\scriptsize
Prof. Dr. Manfred Schmidt-Schau"s \hfill
Fachbereich Informatik (20) \\
K"unstliche Intelligenz und Softwaretechnologie
\hfill Johann-Wolfgang-Goethe-Universit"at Frankfurt am Main \\
\normalsize \begin{center}
{\Large \bf "Ubung: funktionales Programmieren} \\
{\small Wintersemester 1995/96}
\end{center}}
\author{
Sven Eric Panitz
\and
Marko Sch"utz
\and
Frank Kiesel
\and
Norbert Klose
\and
M. Schmidt-Schau"s}
\maketitle
\tableofcontents
\bibliographystyle{alpha}
\section{Organisation}
\subsection{Sprechstunden}
W"ahrend des Semesters wird Norbert Klose eine
Sprechstunden haben, zu denen er bei Fragen oder Schwierigkeiten im
Raum 025
zur Verf"ugung stehen.\\
\begin{tabular}{lll}
Norbert Klose & ? &? Uhr\\
%Marko Sch"utz & Mittwoch & 10-12 Uhr
\end{tabular}\\
In sonstigen dringenden F"allen sind wir "uber e-mail erreichbar:\\
\begin{tabular}{ll}
Norbert Klose & klose@informatik.uni-frankfurt.de\\
%Frank Kiesel & kiesl@informatik.uni-frankfurt.de\\
%Marko Sch"utz& marko@informatik.uni-frankfurt.de\\
Sven Eric Panitz & panitz@informatik.uni-frankfurt.de
\end{tabular}\\
In weiteren Notf"allen ist Sven Eric Panitz in Raum 309 erreichbar.
\subsection{Computerraum}
Ebenfalls zu den Sprechzeiten, wird der Raum 02? im
Untergescho"s f"ur Studenten der Vorlesung reserviert sein.
Zus"atzlich stehen nat"urlich auch die Rechner in den Fischerr"aumen zur
Verf"ugung, so da\3, wie ich denke, es zu keinen Rechnerengp"assen
kommen sollte.
\subsection{Scheinvergabe}
Die Scheine f"ur die Vorlesung werden f"ur ein regelm"a\3iges und
bem"uhtes Mitarbeiten vergeben, was in diesem Falle, ein w"ochentliches
Bem"uhen die "Ubungsbl"atter zu l"osen, bedeutet.
Die "Ubungsbl"atter werden von Norbert mitentworfen und korrigiert.
Die Aufgaben werden sowohl theoretischer als auch praktischer Natur in
Form kleiner Programme sein. Programme, die eine gewisse L"ange
"uberschreiten, sind Norbert w"ahrend seiner Sprechzeit
vorzuf"uhren. N"aheres wird bei den entsprechenden Aufgaben angegeben.
\section{Programmiersprachen}
Die Vorlesung wird die ganze Breite der funktionalen
Programmiersprachen abdecken. Dieses beinhaltet damit sowohl strikte
als auch lazy Sprachen, Sprachen mit und ohne Typsystem, reine
funktionale Sprachen und Sprachen mit destruktiven
(speicherver"andernden) Befehlen.
F"ur die "Ubung stehen uns Scheme und Gofer zur Verf"ugung.
\subsection{Scheme}
Scheme ist eine strikte, dynamisch getypte funktionale Sprache
h"oherer Ordnung mit Seiteneffekten.
Scheme gibt es f"ur verschiedene Rechner und Betriebssysteme: darunter
Artari, Amiga, DOS PCs oder Unix Rechner. Auf den HPs ist Scheme so
installiert, da"s mit dem Kommando
\verb|scheme| am Shell-Prompt der Interpreter gestartet wird. Scheme
ist ein Dialekt der verbreitesten funktionalen Sprache Lisp
\cite{steele:90}.
Zu Scheme gibt es ein Einf"uhrungsbuch \cite{abelson-sussman:85},
welches in ausreichender Zahl in der Bibliothek auch auf Deutsch
vorhanden ist. Es gibt f"ur den Scheme-Interpreter, den wir benutzen,
auch ein Sprachmanual, welches als Kopiervorlage (paperware)
in der Bibliothek
vorhanden ist.
\subsection{Gofer}
Gofer gibt es f"ur verschiedene Rechner und Betriebssysteme:
darunter Macs, DOS PCs oder Unix Rechner, wie die HPs hier an der Uni
und die Linux PCs, die einige m"oglicherweise verwenden.
Auf den HPs ist Gofer so installiert, da"s mit dem Kommando
\verb|gofer| am Shell-Prompt der Interpreter gestartet wird.
Gofer implementiert einen gro"sen Teil von Haskell,
einer, zur Zeit wohl der bedeutendsten, nicht-strikten, funktionalen
Programmiersprache. Wer sich eingehender in Haskell vertiefen
m"ochte sei auf den Haskell-Report \cite{haskell-report1.2}
verwiesen, in dem die Sprache definiert wird.\\
F"ur den Goferinterpreter gibt es auch ein Sprachmanual,
welches als Kopiervorlage (paperware)
in der Bibliothek
vorhanden ist.
\subsection{weitere Sprachen}
Wir wollen hier eine kurze "Ubersicht "uber die verschiedenen
funktionalen Sprachen und ihre Implementierungen geben. Weitere
Informationen lassen sich auf dem Netz unter\\
\verb|http://www.cs.nott.ac.uk/Department/Staff/mpj/faq.html#Haskell|\\
finden.
\begin{description}
\item[Lisp] Lisp findet seit Jahrzehnten besonders in der KI-Gemeinde
Verwendung. Es ist eine strikte dynamisch getypte Sprache h"oherer Ordung. Es
gibt eine Vielzahl freier und kommerzieller Implementierungen von
Lisp. Das von uns benutzte Scheme ist auch ein Lisp-Dialekt.
\item[ML] ML steht f"ur Meta Language \cite{milner:90}
und ist eine strikte funktionale
Sprache h"oherer Ordnung mit dem statischen Typsystem von Milner.
ML ist am RBI nicht installiert, was aber bei entsprechenden Bedarf
ge"andert werden kann.
\item[Miranda]\footnote{Miranda ist ein Warenzeichen von Research
Software Limited} Miranda ist eine kommerziell verkaufte
Programmiersprache, die in vieler Hinsicht Gofer bzw.~Haskell "ahnelt.
Miranda ist eine der "altesten nicht-strikten funktionalen Sprachen und
wird deshalb in sehr vielen Lehrb"uchern verwendet.
Miranda steht auf den RBI-Rechnern leider nicht zur Verf"ugung. F"ur sehr
motivierte Studenten l"a\3t sich eventuell ein gemeinsamer account auf
den Rechnern des KI-Netzes einrichten, so da\3 man die M"oglichkeit hat,
auch Miranda auszuprobieren. Es gibt auch eine
Linux-Version von Miranda. Sie kostet allerdings eine Stange Geld.
\item[LML] LML steht f"ur {\underline L}azy {\underline ML} und
implementiert die Programmiersprache ML nicht-strikt im Gegensatz zu
SML, was eine strikt auswertende Umsetzung von ML ist.
\item[HBC] Der {\underline H}askell {\underline B} {\underline
C}ompiler, h"alt sich an den Haskell-Report, erweitert diesen aber auf
verschiedene (oft syntaktische) Arten. Z.~B.~sind im HBC Identifier
zul"assig, die l"anderspezifische Zeichen verwenden. Der HBC ist aus
dem LML Compiler entwickelt worden und ist auf
vielen Platformen, ebenso wie LML, verf"ugbar. Leider sind beide nicht
auf HP-PA RISC Architekturen verf"ugbar. Es gibt hingegen eine Linux-Version.
\item[GHC] Der {\underline G}lasgow {\underline H}askell {\underline
C}ompiler h"alt sich ebenso wie der HBC an den Haskell-Report. Im GHC
gibt es Erweiterungen, die die Darstellung von Ein- und Ausgabe in
funktionalen Programmen betreffen. Der GHC ist vollst"andig in Haskell
geschrieben und erzeugt, anders als LML oder HBC, C-Code als
Zwischencode, der dann von einem auf dem System verf"ugbaren
C-Compiler in ein ausf"uhrbare Programm "ubersetzt wird. Diese
Tatsache macht den GHC "au"sert portierbar und wir haben ihn auch auf
den HPs des KI-Netzes zum Laufen gebracht.
F"ur sehr motivierte Studenten gilt wieder das unter Miranda
geschriebene.
Bei entsprechenden Bedarf k"onnen wir den GHC auch auf das RBI-Netz
installieren lassen, was allerdings mit einigen Aufwand verbunden ist.
\item[Gofer Compiler] Zu Gofer gibt es einen Compiler, der die in
Gofer geschriebenen Programme nach C compiliert. Das Kommando
\verb|gofc| ruft ihn auf. Es kann bei gr"o"seren Programmen zu
C-Funktionen kommen, die der C-Compiler nicht mehr "ubersetzen kann.
Au"serdem fehlen viele (fast alle) der optimierenden
Programmtransformationen, die in den anderen Compilern verwendet
werden.
\item[hugs] Hugs ist im Kern derselbe Interpreter wie Gofer mit dem
Unterschied, da"s sich hugs an den Haskell-Report h"alt.
\item[Clean] Clean \cite{clean} ist eine nicht-strikte funktionale
Sprache,
die an der Universit"at in Nimwegen entwickelt wurde. Sie ist f"ur
Suns,
OS2
und Macs \footnote{Die Version f"ur Macintosh kann bei uns kopiert
werden} implementiert. Weitere Portierungen sind in Arbeit.
Sie ist urspr"unglich als Zwischensprache f"ur einen
Kompilierer aus einer h"oheren funktionalen Sprache (Miranda) entwickelt
worden, hat aber mit Version 1.0 den Stand von Haskell errreicht (was
Sprachsyntax und Ausdrucksm"achtigkeit betrifft). Haskellprogramme
lassen sich somit schnell ein-zu-eins in Clean-Programme "ubersetzen.
Besonders ist an Clean das I/O Konzept, das es erlaubt, alle
m"oglichen Fenster-, Maus- etc Anwendungen zu programmieren.
Die I/O-Module sind dabei f"ur alle Systeme implementiert. Man hat
also mit einem Programmtext
Anwenderprogramme f"ur verschiedenste Plattformen.
Eine
Striktheitsanalyse \cite{noecker:93} erlaubt effizienten Code zu
generieren. Eine ganze Reihe beeindruckende Beispielprogramme sind dem
Programmpaket beigelegt. (Darunter ein Spreadsheet, ein
Zeichenprogramm, Tetris)
\item[Yale-Haskell] Yale-Haskell h"alt sich auch an den
Haskell-Report. Es erzeugt "ahnlich wie der GHC C-Code erzeugt
Lisp. Yale-Haskell ist f"ur verschiedene Plattformen portiert,
darunter auch der Macintosh. Man braucht allerdings zus"atzlich einen
Lisp-Compiler, der aus dem erzeugten Lisp-Code ausf"uhrbare Programme
erzeugt. Yale-Haskell ist nicht am RBI installiert.
\end{description}
\subsection{Einf"uhrungsliteratur}
Die meiste Literatur "uber lazy funktionales Programmieren bezieht sich auf
Miranda. Man kann sich aber relativ einfach von der Syntax bei Miranda auf
Haskell/Gofer einstellen und lernt dabei dann gleich noch mehr.
Es gibt mitlerweile eine ganze Reihe von Einf"uhrungen.
Ein gern benutztes Einstiegsbuch ist hierbei
\cite{birdwadler:88}. Ebenfalls auf Miranda bezieht sich
\cite{holyer:91}. Ein auf \cite{birdwadler:88} aufbauendes, jedoch f"ur
Gofer geschriebenes Skript ist \cite{cunningham:94}.
Ein Buch, das sich an Haskell orientiert ist
\cite{davie92}. Hier findet sich auch ein bi\3chen mehr theoretische
Hintergrund. F"ur anglophobe gibt es auch eine Einf"uhrung auf deutsch
in \cite{hinze:92}. Ein etwas "alteres Buch noch aus Lisp-Zeiten ist
\cite{henderson:80}. F"ur den zweiten Teil der Vorlesung sind
\cite{pj-lester-book} und in Teilen auch \cite{peyton-jones87} zu empfehlen.
Eine Einf"uhrung aus der Clean-Gruppe ist \cite{plasmeijer-eekelen},
die auch auf Miranda basiert. Eine Lehrbuch f"ur Clean scheint in
Arbeit, zumindest gibt es die ersten Kapitel als Beigabe des
Clean-Pakets.
\section{Programmieren in Scheme und Gofer}
\subsection{Scheme}
\subsection{Gofer}
\subsubsection{literate programming}
Es sind zwei Arten von Programmskripts m"oglich: Programme, in denen die
Kommentarzeilen mit der Zeichenfolge {\tt --} markiert sind, oder
Programme, in denen Codezeilen mit {\tt >} markiert sind. Die zweite Art
eignet sich, wenn man zu einem Programm viel theoretische Erkl"arungen
hat. Dann kann das Progrmm im \LaTeX -Format geschrieben werden, in dem
der Code in der Verbatim-Umgebung steht. Der Gofer-Interpretierer wird
durch die Kommandos {\tt :set -l} bzw. {\tt :set +l} von den einen in
den andren Modus umgestellt.
\subsubsection{Worte der Warnung}
Gofer und Haskell ersparen dem Benutzer, Bl"ocke durch entprechende
Worte oder Klammern zu markieren und Zeilen mit einem entsprechenden
Zeichen zu markieren. Das hat aber seinen Preis: Die Aufgabe der
Strukturierung "ubernehmen jetzt Einr"uckungsregeln. Verletzt man
diese kann es zu Fehlermeldungen kommen, die dann unverst"andlich
erscheinen. Betrachten wir ein Beispiel, in dem wir zwei Funktionen
definieren wollen, eine die aus einer Liste eine Liste macht in der
nur noch jedes zweite Element der Liste enthalten ist und eine die das
gleiche macht, aber f"ur jedes dritte Element. Dazwischen Kommntar.
\begin{verbatim}
> zweiteElemente :: [a] -> [a]
> zweiteElemente [] = []
> zweiteElemente x:[] = []
> zweiteElemente _:x2:xs = x2:(zweiteElemente xs)
Das hier ist Kommentar, der nat"urlich viel l"anger sein k"onnte...
> dritteElemente :: [a] -> [a]
> dritteElemente [] = []
> dritteElemente _:[] = []
> dritteElemente _:_:[] = []
> dritteElemente _:_:x3:xs = x3:(dritteElemente xs)
Das Programm enthält Fehler. Gofer meldet beim Einlesen:
Reading script file "usegofer.tex": Parsing ERROR "usegofer.tex" (line 73): Syntax error in input (unexpected `=')Die 73. Zeile war in diesem Fall die Zeile für
dritteElemente [].
Die Fehlermeldung läßt einen hier also im Dunklen darüber, was
wirklich falsch ist. Es ist die Einrückung. Da die Zeilen von
dritteElemente ein Leerzeichen weiter eingerückt sind als die
Zeilen von zweiteElemente, versucht Gofer diese als Fortsetzung
der letzten Zeile von zweiteElemente zu interpretieren, was
schief geht. Es ist also wichtig auf Einrückung zu achten.
Besonders sollte man sich nicht durch Fehlermeldungen über falsche
Semikolonzeichen verwirren lassen. Textuell wird das Programm durch
Einrücken strukturiert; intern aber durch Semikolonzeichen. Die
Fehlermeldungen beziehen sich manchmal auf diese.