Prof. Dr. Manfred Schmidt-Schauß Fachbereich Informatik (20) Künstliche Intelligenz/Softwaretechnologie Johann Wolfgang Goethe-Universität Frankfurt am Main

Einführung in das funktionale Programmieren

Wintersemester 1995/96

Übungsblatt Nr. 3

Free as a bird

Is the next best thing to be Free as a bird

John Lennon (Nov 1995)

Aufgabe 1 Übersetzen sie den λ-Ausdruck

λf.λx.λh.(λz.((/ z) h) (λy.((− (f y)) (f x)) (λm.((− m) h) x)))

mittels Einführung expliziter Funktionsnamen und Lambda-Lifting in ein CORE-FP Programm.

Aufgabe 2 Schreiben Sie in Scheme eine Funktion

        (define (konstr-monitor fkt) (...)),

die die Funktionsaufrufe von fkt zählt. Angenommen wir hätten die Fakultätsfunktion fak. Dann soll

        (define mfak (konstr-monitor fak))

eine Funktion sein, die einmal wie fak selbst wirkt, d.h. (mfak 5) sollte als Ausgabe 120 liefern und zum anderen sollten folgende Eingaben möglich sein:

• (mfak 'aufrufe) liefert die Anzahl der Funktionsaufrufe von mfak als Fakultätsfunktion und

• (mfak 'nullen) setzt den Zähler zurück auf Null.

Aufgabe 3 Betrachten sie die Funktion append in Scheme oder Gofer. Warum ist es sinnvoll, daß eine Folge von Anwendungen von append der Art (x_{1}++x_{2}++…++x_{n}) rechtsassoziativ ausgewertet wird?

Programmieraufgabe (Abgabe in 2 Wochen) Programmieren Sie in Gofer eine Funktion reduce, die einen CORE-FP-Asudruck, wie auf dem letzten Übungsblatt definiert, um genau einen Schritt in normaler Reihenfolge reduziert. Die Funktion reduce soll dabei die zwei Argumente der Typen Core_Fp und [(String,Int,[String],Core_Fp)] haben. Das zweite Argument repräsentiert das CORE-FP-Programm. Jedes Listenelement stellt eine Funktionsdefinition dar. Der 4-Tupel besteht dabei: aus dem Funktionsnamen, der Funktionsstelligkeit, einer Liste der Argumentnamen und schließlich der rechten Seite der Funktionsdefinition.

Zusatzaufgabe Schreiben Sie quicksort in CORE-FP und versuchen Sie das Programm zum Sortieren einer 2-elementigen Listen auf dem CORE-FP-Interpreter im www zu benutzen.

http://kiste-5.ki.informatik.uni-frankfurt.de/persons/panitz/corefpmask.html