\documentclass[a4paper,11pt]{article} \usepackage[german]{babel} \usepackage{epsfig} \usepackage{verbatim} \newcommand{\tilda}{\def\~{}} \newcommand{\grad}{\ensuremath{^\circ}} %\usepackage{german} %\selectlanguage{\austrian} \usepackage[breaklinks=true]{hyperref} \hypersetup{ pdfauthor = {Alexander \"Olzant}, pdftitle = {Praktikum zur Fachdidaktik: Funktionale Programmierung mit Haskell}, pdfsubject = {Haskell}, pdfkeywords = {Martin Piskernig}, pdfcreator = {LaTeX with hyperref package}, pdfproducer = {dvips + ps2pdf}} \begin{document} \titlepage \title{Funktionale Programmierung mit Haskell\\ 050071 Praktikum zur Fachdidaktik SoSe 2006\\ bei Martin Piskernig } \author{Alexander \"Olzant\\ 9301547\\ E 190 884 423} \maketitle \thispagestyle{empty} \newpage \tableofcontents \newpage \section{Einleitung} Gerade zur schulischen Instruktion erscheint es wichtig, nicht nur die \"ublichen imperativen und objektorientierten Programmiersprachen zu unterrichten, sondern m\"oglichst fr\"uh einen Einblick in funktionale Strukturen zu gew\"ahren. Im Gegensatz etwa zu Logo, das als funktionale Programmiersprache im Unterricht gerade mit j\"ungeren Kindern gerne eingesetzt wird, ist Haskell einerseits eine sauberere/reinere funktionale Sprache und wird von vielen auch als sch\"oner gesehen, andererseits bringt es nicht den Ballast der graphischen Ausgabe inklusive Schildkr\"ote mit, sodass es wohl als weniger \glqq verspielt\grqq{} angesehen werden wird. \subsection{Funktionale Programmierung} Als Alternative zur objektorientierten Programmierung bietet sich die funktionale Programmierung an: bereits vor deren Erfindung wurden in funktionalen Sprachen Polymorphismus, Vererbung, Encapsulation implementiert, sodass das objektorientierte Modell aus dieser Sicht keinerlei Vorteile brachte. Der Begriff \glqq funktional\grqq ist im Bereich der Programmiersprachen in unterschiedlichen Bedeutungen in Verwendung: \begin{itemize} \item funktional = reich an Funktionalit\"at \item funktional = beinhaltet die Abarbeitung von Ausdr\"ucken, die keinerlei Nebeneffekte (side effects) aufweisen im Gegensatz zur Abarbeitung von Befehlen. \end{itemize} Die FAQ der Newsgroup comp.lang.functional definiert dementsprechend funktionale Programmierung folgendermassen: \begin{quote} Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands. The expressions in these language are formed by using functions to combine basic values. A functional language is a language that supports and encourages programming in a functional style. \end{quote} (http://cbbrowne.com/info/functional.html) W\"ahrend also in imperativen Programmiersprachen Variablen verwendet werden, um Zwischenergebnisse zu speichern, z\"ahlt hier vor allem der R\"uckgabewert. Ein weiterer positiver Aspekt der funktionalen Sprachen liegt in der Formulierung von Programmen, die der mathematischen Formelsprache \"ahnlicher ist als entsprechend aufbereitete Algorithmen in prozeduralen Sprachen. In diesem Zusammenhang wird besonders Haskell gerne als {\em mind-expanding} bezeichnet, da sich besonders kompakter, subjektiv huebscher, lesbarer Code mit sauberen Definitionen formulieren laesst. Auch bez\"uglich der Abarbeitungsreihenfolge (lazy Evaluation) bietet die funktionale Programmierung den Vorteil, dass nicht ben\"otigte Ergebnisse gar nicht erst berechnet werden. Die Auswertungsreihenfolge ist einerlei, und wenn es eine terminierende Auswertungsreihenfolge gibt, so terminiert auch die normal order evaluation (Theorem von Church/Rosser, Konfluenz-, Diamanteigenschaft). Zirkul\"are Definitionen sind m\"oglich, wenn auch nicht immer leicht zu formulieren. % TODO Durch {\em Tail Recursion} kann Rekursion erst effizient implementiert werden: indem der Stack Frame der aufrufenden Funktion weiter verwendet wird, anstatt einen neuen anzulegen, koennen beliebige Rekursionstiefen ohne zus\"atzlichen Speicherverbrauch realisiert werden. \cite{schani2001} \subsection{Die Programmiersprache Haskell} Benannt ist die Sprache nach dem Mathematiker Haskell Curry (1900 - 1982), dessen Name von Christopher Strachey auch f\"ur die Benennung des Prinzip des {\em Currying} verwendet wurde. Dieses wurde eigentlich von Moses Schönfinkel und Gottlob Frege erfunden (die Begriffe sch\"onen f\"ur currying und finkeln fuer uncurrying haben sich jedoch im Sprachgebrauch nicht wirklich durchgesetzt) bedeutet die Umsetzung einer Funktion mehrerer Variablen auf eine mit nur einer - intuitiv werden dabei die anderen festgesetzt. Currying: $$f : (X \times{} Y) \rightarrow{} Z$$ Uncurrying: $$g : X \rightarrow{} (Y \rightarrow{} Z)$$ Die Sprache selbst entstand im Jahre 1987, als ein Kommitee gegr\"undet und die Sprache standardisiert wurde, um eine saubere Implementierung einer funktionalen Sprache von Grund auf zu erm\"oglichen. Der aktuelle Standard {\em Haskell 98} stammt, wie der Name schon sagt, aus dem Jahr 1998. Zum interaktiven Kennenlernen eignet sich am besten der Interpreter {\em hugs} (Haskell User's Gofer System), es gibt jedoch auch einen Compiler ({\em GHC}, Glasgow Haskell Compiler), der wie etwa bei Java oder inform Bytecode f\"ur die zugeh\"orige Virtuelle Maschine produziert. Beide sind Open Source und f\"ur die g\"angigsten Betriebssysteme (Unices, Mac OS, Windows, VMS, ...) verf\"ugbar, wenngleich nicht unter der GPL. Wie bereits bei der Einf\"uhrung der funktionalen Programmiersprachen erw\"ahnt sind dank der lazy evaluation zirkul\"are Definitionen in Haskell formulierbar, es gibt jedoch auch mindestens einen Dialekt mit einem anderen Paradigma: Eager Haskell implementiert speculative evaluation. \subsection{Andere Implementationen von Haskell} % TODO: GPL Seit seiner Entstehung wurde neben den oben genannten verbreiteten Versionen GHS und HUGS noch andere programmiert: \begin{itemize} \item Objektorientierte Versionen: Haskell++, O\'{}Haskell und Mondrian \item Distributed Haskell \item Eager Haskell (speculative evaluation) \item Concurrent Clean: GUI-Integration, keine Monaden, sondern unique types\\ http://www.cs.ru.nl/\~{}clean/ \end{itemize} \section{Erste Schritte} Die Einf\"uhrung in eine funktionale Sprache bietet nat\"urlich einige interessante M\"oglichkeiten. Einfache Berechnungen und String-/Listenbeispiele koennen schon bald die list comprehension von Haskell demonstrieren \begin{verbatim} Prelude> 2*2 4 Prelude> ['h','e','l','l','o'] ++ " world" "hello world" Prelude> [n | n <- [0..10], mod n 2 == 0 ] [0,2,4,6,8,10] Prelude> fac 5 where fac = product . enumFromTo 1 120 \end{verbatim} Ganz leicht kann auch die lazy evaluation gezeigt werden: aus der unendlich langen Liste ... \begin{verbatim} Prelude> enumFrom 1 [1,2,3,4,5,6,7,... \end{verbatim} ... wird bei Bedarf nur der tats\"achlich ben\"otigte Teil berechnet: \begin{verbatim} Prelude> take 10 (enumFrom 1) [1,2,3,4,5,6,7,8,9,10] \end{verbatim} Neben der Erl\"auterung der einfachen Datentypen und der wichtigsten Operatoren sollte wohl auf die Fehlermeldungen eingegangen werden. \begin{verbatim} Prelude> sum == 2) ERROR - Syntax error in input (unexpected `)') \end{verbatim} Abgesehen davon darf auch die Einf\"uhrung in den Interpreter hugs nicht zu kurz kommen \begin{verbatim} Prelude> :? LIST OF COMMANDS: Any command may be abbreviated to :c where c is the first character in the full name. :load load modules from specified files :load clear all files except prelude :also read additional modules :reload repeat last load command :edit edit file :edit edit last module :module set module for evaluating expressions evaluate expression :type print type of expression :? display this list of commands :set set command line options :set help on command line options :names [pat] list names currently in scope :info describe named objects :browse browse names exported by :find edit module containing definition of name :!command shell escape :cd dir change directory :gc force garbage collection :version print Hugs version :quit exit Hugs interpreter \end{verbatim} \section{Rekursion} Das beliebteste Beispiel zur Erl\"auterung der Rekursion ist vielleicht die Implementation der Funktion zur Berechnung der {\em Faktoriellen} \begin{verbatim} fac :: Integer -> Integer fac 0 = 1 fac n | n > 0 = n * fac (n-1) \end{verbatim} Dies erfordert jedoch, dass das Ergebnis jedes Funktionsaufrufes mit n multipliziert wird und verhindert damit die Wiederbenutzung des Stack Frame (tail recursion). Durch eine Modifikation kann dieser Sch\"onheitsfehler behoben werden. In dieser Variante ist nur ein Stack Frame f\"ur die Rekursion notwendig, daher ist sie nicht weniger effizient und viel eleganter als eine iterative Variante: \begin{verbatim} fac :: [Integer] -> [Integer] -> Integer fac c m | m == 1 = c | otherwise = fac (c*m) (m-1) fac> fac 1 99 933262154439441526816992388562667004907159682643816214685929638952175999932 299156089414639761565182862536979208272237582511852109168640000000000000000 000000 \end{verbatim} \section{Lambda-Operator} Ebenfalls unumg\"anglich ist die Verwendung des Lambda-Operators zur Definition anonymer Funktionen. \begin{verbatim} Prelude> do_something 99 (\x -> x * x) where do_something x fn = fn x 9801 \end{verbatim} %TODO: type \begin{verbatim} msort = foldl (\s -> \t -> (\(u, v) -> u++[t]++v) (break (>t) s) ) [] Prelude> msort "ZyXVAbCdE1230" "0123ACEVXZbdy" \end{verbatim} \section{Datentypen} Zus\"atzlich zu den anfangs besprochenen einfachen Datentypen wie Integer, Bool, String (eigtl. liste von Char) sind dann Tupel und der Zugriff auf die Elemente zu behandenln: \begin{verbatim} type Tier = (String, String, Int) name :: Tier -> String linne :: Tier -> String nummer :: Tier -> Int name (n,l,u) = n linne (n,l,u) = l nummer (n,l,u) = u \end{verbatim} \section{Unterrichtsplan} \begin{enumerate} \item {\bf Einf\"uhrung 1}\\ Erl\"auterung iterative, funktionale, objektorientierte Programmiersprachen\\ diverse Beispiele\\ Hinweis auf funktionale Eigenschaften (list comprehension, Rekursion, anonyme Funktionen ...) \item {\bf Einf\"uhrung 2}\\ Erkl\"arung der Arbeitsumgebung\\ hugs - Interpreter, Fehlermeldungen\\ literale und traditionelle Scripte\\ einfache funktionale Konstrukte\\ \item {\bf Einf\"uhrung 3}\\ Elementare Datentypen\\ Operatoren\\ Konstanten\\ Relatoren \item {\bf Rekursion}\\ Vergleich iterativer und rekursiver Algorithmen\\ mathematische Schreibweise\\ Beispiele: Faktorielle, Fibonacci-Zahlen\\ \item {\bf Rekursion Wiederholung}\\ Tail recursion\\ repetitive (schlichte), lineare, geschachtelte, baumartige Rekursion\\ Effizienz (z. B. von Fibonacci-Implementierungen) \item{\bf Lambda-Operator}\\ freie und gebundene Variablen\\ Lambda-Ausdr\"ucke, anonyme Funktionen\\ Sortierfunktionen \item{\bf Layout-Konventionen, Notation, Muster} Abseitsregel\\ \item{\bf Lambda-Operator Wiederholung} \item{\bf Tupel}\\ festgelegte Zahl von Werten zur Modellierung von Strukturen\\ \item{\bf Listen}\\ beliebige Zahl von Werten gleichen Typs\\ Kurznotation [5 .. 10] \\ Listenkomprehension wieder einmal\\ \begin{verbatim} [ n*n | n <- list, n < 10 ] \end{verbatim} \item{\bf Polymorphie, Muster}\\ Polymorphie == \glqq Vielgestaltigkeit\grqq\\ \"Uberladen == ad-hoc Polymorphie\\ Muster: Werte, Variablen, Wild cards \item{\bf Typen}\\ Produkttyp vs Tupel: beim Tupel kein Kunstruktor\\ Summentyp\\ Rekursive Typen (B\"aume, ...)\\ polymorphe Typen \item{\bf Polymorphie, Vererbung}\\ Wiederverwendung!\\ Typen, Funktionen\\ \item{\bf Funktionale}\\ Funktionen h\"oherer Ordnung (involvieren Funktionen in Argumenten oder Resultaten)\\ \item{\bf Currying, Funktionskomposition}\\ mehrstellige Funktionen - Funktionspfeil statt Tupel \item{\bf Monaden}\\ Ein-/Ausgabe - Schnittstelle zur imperativen Programmierung\\ Festlegung der Reihenfolge von Operationen \item{\bf Module} (optional)\\ Export/Import, Kollisionen\\ \end{enumerate} \section{\"Ubungsbeispiele} \subsection{Rekursion: Fibonacci-Zahlen} Schreibe eine rekursive Funktion, welche die Fibonacci-Zahlen berechnet. Diese Zahlen $f_0, f_1, ...$ sind folgendermassen definiert: $f_0 = f_1 = 1$ und $f_{n+2} = f_n + f_{n+1}$. Abzugeben ist eine rekursive Funktion {\tt fibonacci}, welche eine nat\"urliche Zahl $n$ als Parameter nimmt und $f_n$ als Ergebnis ausgibt. \subsection{Listen und Strings: Palindrome} Schreibe eine Funktion {\tt isPal}, die fuer eine Eingabeliste oder einen String feststellt, ob sie ein Palindrom darstellt, also von vorne nach hinten die gleiche Folge von Elementen aufweist wie von hinten nach vorne. \subsection{Tupeln und Listen: Primfaktorenzerlegung} Schreibe eine Haskell-Funktion zur Primfaktorenzerlegung, die eine Liste der Primfaktoren fuer den Eingabeparameter ausgibt. Empfehlung: implementiere dazu eine Funktion, die \"uberpr\"uft, ob eine Zahl eine Primzahl ist. \subsection{Typklassen und ihre Instanzen} \begin{verbatim} data Baum a = Empty | Node a (Baum a) (Baum a) \end{verbatim} Schreibe Haskell-Funktionen, die die Hoehe des Baumes (also den l\"angsten Weg von der Wurzel bis zum letzten Ast) und die Anzahl der \"Aste berechnen! \subsection{Currying} Schreibe eine curryfizierte, polymorphe Funktion {\tt zauberwort a -$>$ [b] -$>$ [b]}, die eine Eingabeliste folgendermassen modifiziert: \begin{itemize} \item wenn {\tt a == 1}, dann drehe die Reihenfolge der Elemente in der Ausgabeliste um \item wenn {\tt a == 2}, dann erhoehe den Wert jedes Elements in der Ausgabeliste um 1 \item wenn {\tt a == 3}, dann ersetze A..Za..z durch Z..Az..a, drehe also das Alphabet um \item ansonsten gebe \glqq Hokuspokus\grqq{} aus \end{itemize} Implementiere die Varianten 1 bis 3 dazu als einstellige Funktionen. \section{Fallstricke/Caveats} Eine Eigenschaft, die in vielen anderen Programmiersprachen so nicht vorkommt, ist die Bedeutung von Einr\"uckungen. W\"ahrend es grunds\"atzlich in fasst jeder Sprache zur Lesbarkeit beitr\"agt, zusammengeh\"orige Codebl\"ocke entsprechend einzur\"ucken, markieren Einr\"uckungen in Haskell die Bindungsbereiche und m\"ussen daher unbedingt eingehalten werden, was daf\"ur die Typographie vereinfacht (keine Strichpunkte notwendig). Die beiden Varianten von script ({\em traditional}, {\bf .hs} und {\em literal}, {\bf .lhs}) k\"onnen ebenfalls zur Verwirrung beitragen. Syntax und Semantik kann f\"ur Anf\"angerInnen funktionaler Programmierung verwirrend sein. http://www.haskell.org/tutorial/pitfalls.html f\"uhrt noch folgende Probleme an: \begin{itemize} \item Typisierung: keine implizite Umwandlung \item explizite Rekursion wegen der high order functions meist nicht notwendig\\ \begin{verbatim} raise :: Num a => a -> [a] -> [a] raise _ [] = [] raise x (y:ys) = x+y : raise x ys \end{verbatim} eleganter:\\ \begin{verbatim} raise x ys = map (x+) ys \end{verbatim} \end{itemize} \section{Iterative Programmeirung} {\bf nicht} zur Nachahmung, von http://www.willamette.edu/~fruehr/haskell/evolution.html \begin{verbatim} fac n = result (for init next done) where init = (0,1) next (i,m) = (i+1, m * (i+1)) done (i,_) = i==n result (_,m) = m for i n d = until d n i \end{verbatim} % * Welche "Fallstricke" gibt es in der Sprache (C: "if(c = 3) do_something();")? % * Wie einfach ist die Syntax zu erlernen (Java: "public static void main(String[] args)")? % * Welche Konzepte vermittelt die Sprache vorwiegend (Rekursion, Vererbung, ...)? % * In welcher Reihenfolge werden diese Konzepte erklärt? % * Wie könnten erste Übungsbeispiele aussehen? % * Gibt es geeignete Entwicklungsumgebungen (IDEs)? % * Wie schwierig zu verwenden ist die Sprache (interpretiert, kompiliert, ...)? % * Welcher Familie gehört die Sprache an (prozedural, funktional, ...)? % * usw. usf. % \section{Fazit} Im Besonderen f\"ur eine funktionale Programmiersprache hat Haskell also einiges zu bieten, in einem Semester sind zumindest die Grundz\"uge unterzubringen, ohne die Sch\"ulerInnen zu \"uberbeanspruchen. Auch ohne vorhergehende Erfahrungen etwa in der Unterstufe sollte es durchaus m\"oglich sein, Rekursion, Currying und dar\"uber hinausgehende Konstrukte nahezubringen, zumal wenn in einem weiterf\"uhrenden Kurs die Konzepte erweitert und vertieft werden k\"onnen, eine erstmalige Verwendung in einer h\"oheren Schulstufe wird vermutlich zu interessanten Relativierungen der zu diesem Zeitpunkt m\"oglicherweise bereits einge\"ubten imperativen Konstrukte aus anderen Programmiersprachen f\"uhren. Durch die mathematische Formulierung der Programme ist eine direkte Kooperation mit dem Fach Mathematik m\"oglich, keinesfalls aber zwingend notwendig. Eine funktionale Grundeigenschaft ist {\em list comprehension}, mit Listen (und sogar dem \"Aquivalent des mathematischen Allquantors) kann elegant nicht nur ein Iteratives Konstrukt, sondern auch direkte Rekursion vermieden werden. Der \glqq freundliche\grqq{} Interpreter hugs, der meist aussagekr\"aftige Fehlermeldungen ausgibt, scheint f\"ur den Unterricht ebenfalls sehr geeignet, da f\"ur Prototyping nicht erst Compile-Zyklen eingeschoben werden m\"ussen. Zuvorderst (und als Mindestmass f\"ur die Bewertung) sind wohl die Beherrschung funktionaler Konstrukte zu sehen, aus denen Programme mit einfachen Algorithmen zu konstruieren sind; weitergehende Projekte werden wohl einen gr\"osseren Antel des umfangreichen Vokabulars nutzen. \section{Links, weitere Informationen} \begin{itemize} \item Eleven Reasons to use Haskell as a Mathematician \\ http://sigfpe.blogspot.com/2006/01/eleven-reasons-to-use-haskell-as.html \item Haskellwiki \\ http://www.haskell.org/ \item Haskell Reference (zvon.org) \\ http://zvon.org/other/haskell/Outputglobal/index.html \item Functional Programming in the Real World\\ http://homepages.inf.ed.ac.uk/wadler/realworld/index.html \item Funktionale Programmierung - Lehrveranstaltung des Instituts f\"ur Computersprachen an der TU Wien\\ http://www.complang.tuwien.ac.at/knoop/fp185161\_{}ws0506.html \end{itemize} \nocite{*} \section{Bibliographie} \bibliographystyle{plainnat} % (uses file "plain.bst") \bibliography{fachdidaktikpraktikum_haskell} \end{document} % vim: textwidth=75