Vorlesung 9 Lemke

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Übungsaufgabe S. 5 1.1 Implementation der angegebenen Lambdafunktionen in Python 2 Übungsaufgabe S. 11 2.1 Erklärung der Funktion free() (bound() funktioniert analog) 3 Übungsaufgabe S. 13 3.1 Anwendung der ɑ-Konvention 4 Übungsaufgabe S. 14 4.1 Reduktion mit η-Regel und mit β-Regel 5 Übungsaufgaben S. 15 5.1 Reduzieren Sie ((λ(x)(x x))(λ(x) x)) und ((λ(x)(x x))(λ(x)(x x))) 5.2 Zeigen Sie, dass für Y := (λf . ((λx. (f (x x)))(λx. (f (x x))))) gilt: (Y g ) = (g (Y g )) 6 Übungsaufgabe S. 17 6.1 Zeigen Sie, dass es von der Reduktionsreihenfolge abhängen kann, ob die für ((λy . z)((λx. (x x))(λx. (x x)))) existierende Normalform z gefunden wird oder nicht 6.2 Verwenden Sie zur Berechnung von ((λx. ((x d)((λy . (x y )) a))) b) unterschiedliche Reduktionsreihenfolgen 7 Übungsaufgabe S. 22 7.1 Currifizieren Sie f (x, y , z) = x + y + z 8 Übungsaufgabe S. 23 8.1 Erklärung der boolschen Werte 8.2 Berechnen Sie if true e1 e2 = e1

Übungsaufgabe S. 5

Implementation der angegebenen Lambdafunktionen in Python

(λx. x)

identity_function = lambda x : x

(λf . (λx. (f x) ) )

Als Python-Lambdafunktion:

application = lambda f : lambda x : f(x)

test_f = lambda x : x * 3 applied = application(test_f) print(applied(4))

ausführen

Als reguläre Pythonfunktion:

def outer(f): def inner(x): return f(x) return inner

def test_f(x): return x * 3 applied = outer(test_f) print(applied(4))

ausführen

Übungsaufgabe S. 11

Erklärung der Funktion free() (bound() funktioniert analog)

Übungsaufgabe S. 13

Anwendung der ɑ-Konvention

Übungsaufgabe S. 14

Reduktion mit η-Regel und mit β-Regel

Übungsaufgaben S. 15

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

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

Übungsaufgabe S. 17

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

Verwenden Sie zur Berechnung von ((λx. ((x d)((λy . (x y )) a))) b) unterschiedliche Reduktionsreihenfolgen

Übungsaufgabe S. 22

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

Mit Python-Lambdafunktionen:

xyz = lambda x : lambda y : lambda z : x + y + z

x = xyz(1) y = x(2) z = y(3) print(z)

ausführen

Mit regulären Pythonfunktionen:

def pythonic_xyz(x): def fy(y): def fz(z): return x + y + z return fz return fy

x = pythonic_xyz(1) y = x(2) z = y(3) print(z)

ausführen

Übungsaufgabe S. 23

Erklärung der boolschen Werte

Berechnen Sie if true e1 e2 = e1