Übung 6

15. Dezember 2003 (Abgabe 14. Januar 2004)

In dieser Übung sollen Sie einen Lambda-Auswerter vervollständigen, erweitern sie den Quellcode uebung6.hs um die Funktionen, die in den Aufgaben 1 bis 5 beschrieben sind. Wenn Ihnen die Funktion substitute (Aufgabe 5) unklar ist, dann sollten Sie sich noch mal die eval-Funktion im Quellcode ansehen.

Aufgabe 1 (5 Punkte)

1. Definieren Sie eine Funktion showExpr::Expr->String, die einen Ausdruck in die Lambda-Schreibweise (mit "/" für "λ") übersetzt.
2. Definieren Sie eine Funktion isLambda::Expr->Bool, die prüft ob ein Ausdruck eine Lambda-Funktion ist.
3. Definieren Sie eine Funktion collectNames, die alle Variablennamen eines Ausdrucks genau einmal in eine Liste speichert.

Aufgabe 2 (3 Punkte)

Schreiben Sie in Haskell eine Funktion

   freie::Expr->[String]->[String],

die die freien Variablen in einem Ausdruck zurückgibt. Die Funktion wird beim ersten Aufruf mit dem Ausdruck und einer leeren Liste aufgerufen.

Aufgabe 3 (3 Punkte)

Schreiben Sie in Haskell eine Funktion

   bounded::Expr->[String]->[String],

die die gebundenen Variablen in einem Lambda-Ausdruck zurückgibt. Die Funktion wird beim ersten Aufruf mit dem Ausdruck und einer leeren Liste aufgerufen.

Aufgabe 4 (3 Punkte)

Schreiben Sie in Haskell eine Funktion

   find_new_name::[String]->String,

die einen Variablennamen zurückgibt, der nicht in der übergebenen Liste vorkommt. Variablennamen bestehen aus genau einem Kleinbuchstaben.

Aufgabe 5 (3 Punkte)

Schreiben Sie in Haskell eine Funktion

   rename::String->String->Expr->Expr,

die alle Variablen (egal ob gebunden oder frei) mit dem Namen des ersten Parameters durch den Namen des zweiten Parameters in dem als dritten Parameter übergebenen Ausdruck ersetzt.

Aufgabe 6 (8 Punkte)

Schreiben Sie in Haskell eine Funktion

   substitute::String->Expr->Expr->[String]->Expr,

die eine Variable (deren Name der erste Parameterder Funktion ist) in einem Ausdruck (3. Parameter) durch einen weiteren Ausdruck (2. Parameter) ersetzt. Dabei müssen evtl. Variablenumbenennungen durchgeführt werden. Der 4. Parameter enthält eine Liste der freien Variablennamen im einzusetzenden Ausdruck (2. Parameter). Es könnte hilfreich sein, die Funktionen der Aufgaben 1 bis 4 zu verwenden.