BuK-Übung08

Semantik: \alpha-Regel (Felix Nitsche, Stefan Lüttke)

Wenden Sie für ((\lambda x. ( \lambda y. ((x y)))(y w)) vor der \beta-Reduktion die \alpha-Konvention an.

Semantik: \eta-Regel (Daniel Tasche, Jens Heider)

Vereinfachen Sie den Racket-Ausdruck (\lambda(z)((\lambda(x)(* 3 x)) z)).

(\lambda(z)((\lambda(x)(* 3 x)) z)) \Rightarrow (\lambda(x)(* 3 x)).

Reduktion (Raik Bieniek, Max Wielsch)

Reduzieren Sie ((λ(x)(x x))(λ(x) x)) und ((λ(x)(x x))(λ(x)(x x)))

1. ((λ(x)(x x))(λ(x) x)) \xrightarrow{β} ((λ(x) x) (λ(x) x)) \xrightarrow{β} (λ(x) x)

2. ((λ(x)(x x))(λ(x)(x x))) \xrightarrow{β} ((λ(x)(x x))(λ(x)(x x))) \xrightarrow{β} …

Terminiert nicht

Zeigen Sie, dass für Y := (λ f. ((λ x. (f (x x)))(λ x. (f (x x))))) gilt: (Y g) = (g (Y g))

Reduktionsreihenfolge (Ingo Körner, Christof Ochmann)

Zeigen Sie dass es von der Reduktionsreihenfolge abhängen kann, ob die für ((\lambda y. z)((\lambda x. (x x))(\lambda x. (x x)))) existierende Normalform z gefunden wird oder nicht.

Linksaußen-Reduktion \beta_0: ((\lambda y.z)((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x)))) \xrightarrow{\beta_0} z

Linksinnen-Reduktion \beta_i: $((\lambda y.z)((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x)))) \xrightarrow{\beta_i} ((\lambda y.z)((((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x))))))$

Verwenden Sie zur Berechnung von ((\lambdax. ((x d)((\lambda y. (x y)) a))) b) unterschiedliche Reduktionsreihenfolgen.

Linksaußen-Reduktion \beta_0: $((\lambda x.((x \text{ } d)((\lambda y.(x \text{ } y))a)))b) \xrightarrow{\beta_0}

((b \text{ } d)((\lambda y.(b \text{ } y))a)) \xrightarrow{\beta_0} ((b \text{ } d)(((b \text{ } a))))$

Linksinnen-Reduktion \beta_i: $((\lambda x.((x \text{ } d)((\lambda y.(x \text{ } y))a)))b) \xrightarrow{\beta_i} ((\lambda x.((x \text{ } d)(((x \text{ } a))))) b) \xrightarrow{\beta_i} ((b \text{ } d)(((b \text{ } a))))$

Boolesche Werte (Stefan Scheumann, Robert Rosenberger)

Berechnen Sie if true e1 e2 = e1.

Vorbedingung

\lambda xy. x nennen wir true.

\lambda xy. y nennen wir false.

if\equiv \lambda txy. txy (Hinweis: txy \equiv ((t\text{ }x)\text{ }y)))

Berechnung

Curryfizierung (Ronald Krause, Tobias Salzmann)

Currifizieren Sie f(x, y, z) = x + y + z

Die Funktion f(x,y,z) besitzt drei Argumente, woraus die Summe derer gebildet werden soll. Bei der Anwendung der Curryfizierung wird die Funktion f mit deren Argumenten so umgewandelt, dass eine Funktion entsteht, welche genau einen Parameter als Eingabe besitzt.

Grund für die Curryfizierung ist die Verwendung von einstelligen Funktionen, wie z.B. im \lambda-Kalkül oder Haskell.

Im Allgemeinen beschreibt folgende mathematische Notation die Umwandlung durch die Curryfizierung:

f: A_1 \times A_2 \times ... \times A_3 \rightarrow R zu F: A_1 \mapsto (A_2 \mapsto (A_3 \mapsto (... \mapsto (A_n \mapsto R)))), sodass f(x,y,z)= F(x)(y)(z).

Beispiel: f(x,y,z)

Folgende Scheme-Prozedur beschreibt das Addieren von drei Argumenten:

Beispiel: F(x)(y)(z)

Folgende Scheme-Prozedur beschreibt die Addition von drei Argumenten nach der Curryfizierung:

Vorgehensweise: F(x)(y)(z)

1. ((\lambda.x~(\lambda.y~(\lambda.z~(+~x~y~z))))~1~2~3)

2. ((\lambda.y~(\lambda.z~(+~1~y~z)))~2~3)

3. ((\lambda.z~(+~1~2~z)~3)

4. (+~1~2~3)

5. 6

Registermaschine(Ronald Krause, Tobias Salzmann)

Führen Sie folgendes Programmbeispiel per Hand aus.

Beispiel:

Das Programm stoppt beim Erreichen des STOP-Befehls mit dem Ergebnis in R0.

Ausführung