Funktionale Programmierung ALP I Einführung in Haskell WS 2012/2013 Prof. Dr. Margarita Esponda Prof. Dr. Margarita Esponda Funktionale Programmierung Was ist Haskell? Haskell ist eine rein Funktionale Programmiersprache mit einer nach Bedarf Auswertung-Strategie oder "Lazy Evaluation". Prof. Dr. Margarita Esponda Funktionale Programmierung Was bedeutet rein funktional? - Programme werden als mathematische Funktionen dargestellt - Haskell Funktionen haben keine Seiteneffekte. keine Seiteneffekte ⇒ Referenzielle Transparenz - Eine Funktion liefert immer bei gleicher Eingabe das gleiche Ergebnis. - Der Wert eines Ausdrucks hängt nur von den Werten der aktuellen Parameter ab. Prof. Dr. Margarita Esponda Funktionale Programmierung Funktionen e 1 e 2 F a nur ein Eingabewerte . Ausgabewert . e n Das Ergebnis einer Funktion hängt nur von den Eingabewerten ab. Beispiel: f(1,2) 1 2 f ( x , y ) = x 2 + y 3 Prof. Dr. Margarita Esponda Funktionale Programmierung Funktionen Arithmetische Operationen können auch als Funktionen betrachtet werden 1 + 3 2 1 2 ( + ) ( x , y ) = x + y 3 Prof. Dr. Margarita Esponda Funktionale Programmierung Funktionen in Haskell Einfache Funktionsdefinitionen in Haskell: f x = x*x quadrat x = x*x Allgemeine Syntax: Ausdruck, dessen Wert dem Ergebnis der Funktion entspricht Funktionsname f e e e ... = Funktionskörper 1 2 n Eingabeargumente ohne Klammern und Kommas Prof. Dr. Margarita Esponda Funktionale Programmierung Funktionsapplikation Die Anwendung einer Funktion mit konkreten Argumenten wird als Funktionsapplikation bezeichnet. Funktionsdefinition: f x y z = x*y + x*z Funktionsapplikation: Funktionsreduktion f 1 0 2 ⇒ 1*0 + 1*2 Die Variablen auf der rechten ⇒ 0 + 2 Seite der Funktionsdefinition werden durch die ⇒ 2 entsprechenden konkreten Argumente ersetzt. Prof. Dr. Margarita Esponda Funktionale Programmierung Normalform Kann ein Ausdruck nicht mehr weiter reduziert werden, dann befindet er sich in seiner Normalform und die Berechnung ist beendet. Beispiele: Ausdruck Normalform des Ausdruck 3 + 7 10 Zahlen sin 0 0.0 Zeichenkette "text" "text" "1 + 2" "1 + 2" '2' '2' Zeichen Prof. Dr. Margarita Esponda Funktionale Programmierung Auswertungsstrategie ✴ Innerhalb eines Ausdrucks kann es mehrere Funktionsapplikationen geben. ✴ Die Reihenfolge, in der unabhängige Teilausdrücke ausgewertet werden, verändert nicht den Wert des gesamtes Ausdrucks. ✴ Aber verschiedene Reihenfolgen können die Anzahl der notwendigen Berechnungen stark beeinflussen. ✴ Eine Auswertungsstrategie kann sogar entscheiden, ob eine Berechnung beendet werden kann oder nicht. Prof. Dr. Margarita Esponda Funktionale Programmierung Bottom (⊥) ✴ Wenn die Auswertung eines Ausdrucks zu einer unendlichen Folge von Reduktionen führt, wird entweder • das Programm nicht beendet oder • es stürzt ab, weil der Speicher voll wird. ⊥ ✴ In der Theorie wird das Symbol Bottom verwendet, um den Wert von Ausdrücken darzustellen, die nicht vollständig ausgewertet werden können (die divergent sind). Prof. Dr. Margarita Esponda