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. 4

So können denn die Intelligenzen verschiedener Ordnungen tatsächlich als zu einer einzigen Art gehörig betrachtet werden, ganz so, wie auch die schwierigste Berechnung dennoch als zur Rechenart der Addition und Subtraktion gehörend angesehen werden kann. Auch jede mathematische Abhandlung stellt, wenn sie nicht lückenhaft ist, wirklich eine Stufenfolge von Abstraktionen dar, von der einfachsten bis zur höchsten

und schwierigsten. aus Jan Graf Potocki Die Abenteuer in der Sierra Morena

Aufgabe 1

a) Übersetzen Sie zunächst Schritt für Schritt mittels SKI-Kombinatoren folgenden λ-Ausdruck in einen äquivalenten CORE-FP Ausdruck.

λx.(case true (< x 0) − 1 (case true (= x 0) 0 1))

= λx.(if (< x 0) − 1 (if (= x 0) 0 1))

b) Reduzieren Sie Schritt für Schritt den CORE-FP Ausdruck (a x) ⇝^{∗} e, wobei a der aus Aufgabenteil a) erhaltenen CORE-FP Ausdruck ist.

c) Verifizieren Sie, daß

(e[x/z]) = \{ \begin{matrix}1 & falls z > 0, \\ 0 & falls z = 0, \\ −1 & falls z < 0. \end{matrix} ,

wobei e der aus Aufgabenteil b) erhaltene λ-Ausdruck ist.

Aufgabe 2 Im λ-Kalkül besitzen wir nicht die Fähigkeit wie in CORE-FP, Funktionen an Namen binden zu können. Angenommen wir hätten eine ”Standardumgebung“, in der Funktionen wie +, -, *, /, = , !=, ..., das case wie wir es von CORE-FP her kennen, natürliche Zahlen, true und false bekannt seien. Wir könnten dann Fakultät nicht einfach rekursiv wie folgt definieren:

fak = λn.(case true (= n 1) 1 (∗ n (fak (− n 1)))),

wobei die Zuordnung fak = … hier als reines Text-Makro zu verstehen ist. Würden wir das Makro fak expandieren, erhielten wir einen unendlichen String.

a) Zeigen Sie, daß Y = λf.(λx.(f (x x)) λx.(f (x x)) ein Fixpunktoperator ist, d.h. für jeden

beliebigen λ-Ausdruck e gilt:

(Y e) = e (Y e)

b) Benutzen Sie den Fixpunktoperator Y aus Aufgabenteil a), um die rekursive Funktion fak in eine gültige λ-Version zu überführen und berechnen Sie mit Ihrer Version das Ergebnis von 2!.

Aufgabe 3 Betrachten sie folgende Funktion zur Berechnung der Fakultät in CORE-FP.

fak a n = if (== n 0) a (fak (* n a) (- n 1))

In welchen Argumenten ist diese Funktion strikt?