Vorlesung8

Aus ProgrammingWiki
< BuK < IIm14 < Studenten < s3ankrau1

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

((\lambda x. (\lambda y. (x y)))(y w)) \leftrightarrow ((\lambda x. (\lambda z. (x z)))(y w)) \xrightarrow{β} (\lambda z. ((y w)) z))



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


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



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))

(Y g) = ((λf.((λx.(f(x x)))(λx.(f(x x)))))g) \xrightarrow{β} ((λx.(g(x x)))(λx.(g(x x)))) \xrightarrow{β} (g ((λx.(g(x x))) (λx.(g(x x))))) (g (Y g)) = (g ((λf.((λx.(f(x x)))(λx.(f(x x)))))g)) \xrightarrow{β} (g ((λx.(g(x x)))(λx.(g(x x)))))



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))))$



Berechnen Sie if true e1 e2 = e1.

\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)))


((\lambda txy (t(x\text{ } y)))(\lambda xy (x))\text{ } e{1}\text{ } e{2})\equiv ((\lambda xy(x))\text{ } e{1}\text{ } e{2})\text{ }\equiv (e_{1})



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

Durch die Currifizierung sollen einstellige Funktionen entstehen. In diesem Fall sollen 3 Parameter addiert werden. Die Currifizierung ergibt folgende Funktion: F : X \mapsto (Y \mapsto ( Z \mapsto R)). Daraus folgt: F(x)(y)(z) = f(x,y,z).