CS314-Fall-2018-Assign7-Solution
1 Scheme Programming
1.1
((lambda(x)(lambda(y)((lambda(z)e)v3)v2))v1)
1.2
(define maxAbsoluteVal
(lambda(l)
(let
((mal
(map
(lambda(x)(abs x))
l)
))
(reduce
(lambda(x y)
(if (> x y) x y)
)
mal -inf.0
)
)
)
)
2 Lambda Calculus
2.1
(((λx.x)(λx.28))(λz.z))=((λx.28)(λz.z))=28
No other order
2.2
((λx.((λz.((λx.(z x)) 2))(λy.(* x y)))) 6)
=((λx.((λz.(z 2))(λy.(* x y)))) 6)
1
=((λx.((λy.(* x y)) 2)) 6)=((λx.(* x 2)) 6)
=(* 2 6)=12
Other order:
((λx.((λz.((λx.(z x))2))(λy.(* x y)))) 6)
=((λx.((λz.((λm.(z m))2)) (λy.(* x y)))) 6)
=(λz.((λm.(z m))2))(λy.(* 6 y)))=(λm.(λy.(* 6 y))m))2)
=(λm.(* 6 m)2)= 12
result should be the same
2.3
((λz.((λy.z)((λx.(x x))(λx.(x x)))))11)
=((λy.11)((λx.(x x))(λx.(x x))))
=11
Other order:
((λz.((λy.z)((λx.(x x))(λx.(x x)))))11)
=((λz.((λy.z)((λx.(x x))(λm.(m m)))))11)
=((λz.((λy.z)((λm.(m m))(λm.(m m)))))11)
=((λy.11)((λm.(m m))(λm.(m m))))=11
result should be the same
3 Programming in Lambda Calculus
3.1
((and true) true)
=(((λu.(λv.((u v) false))) (λx.(λy.x))) true)
=((λv.(((λx.(λy.x)) v) false)) true)
=(((λx.(λy.x)) true) false)
=((λy.true) false)=true
3.2
or: λx.λy.((x true) y)
prove:
((or true) false)
=(((λx.λy.((x true) y)) true) false)
=((λy.((true true) y)) false)
=((true true) false)
=(((λa.λb.a) true) false)
=((λb.true) false)
=true
((or true) true)
=(((λx.λy.((x true) y)) true) true)
=((λy.((true true) y)) true)
=true
2
((or false) true)
=(((λx.λy.((x true) y)) false) true)
=((λy.((false true) y)) true)
=(((λa.λb.b) true) true)
=((λb.b)true)
=true
((or false) false)
=(((λx.λy.((x true) y)) false) false)
=((λy.((false true) y)) false)
=((false true) false)
=(((λa.λb.b) true) false)
=((λb.b) false)
=false
3.3
NOT:λx.((x false) true)
XOR:λx.λy.((x(NOT y)) y)
prove:
((xor true) false)
=((true (NOT false)) false)
=((true true) false)
=((λb.true) false)
=true
((xor true) true)
=((true (NOT true)) true)
=((true false) true)
=((λb.false) true)
=false
((xor false) true)
=((false (NOT false)) true)
=((false false) true)
=((λb.b) true)
=true
((xor false) false)
=((false (NOT false)) false)
=((false true) false)
=((λb.b) false)
=false
4 Lambda Calculus and Combinators S & K
((SK)K)
=(((λxyz.((x z)(y z)))K)K)
=((λyz.((K z)(y z)))K)
3
=(λz.((K z)(K z)))
=(λz.(((λxy.x) z)(K z)))
=(λz.((λy.z)(K z))
=(λz.z)=(λx.x)=I
4