BuK/IIm14/Studenten/s3ankrau1/Vorlesung8

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
'''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 (($\lambda$x. ((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 <tt>if true e1 e2 = e1</tt>.'''

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

<code id="55894f07e46aa">
(define add3Parameter
    (lambda (x y z)
         (+ x y z)))
</code>
<run id="55894f07e4741">(add3Parameter 1 2 3)</run>

<code id="55894fe488415">
(define curryAdd3Parameter
    (lambda (x)
      (lambda (y)
        (lambda (z)
         (+ x y z)))))
</code>
<run id="55894fe48849f">(((curryAdd3Parameter 1)2)3) </run>
BuK/IIm14/Studenten/s3ankrau1/Vorlesung8

Suche
