PowerPoint Presentation
CS 345
Lecture 14
Using lab 4 starter file, review numbers, succ and pred, and add.
Take a moment to talk about cn-to-num
1
New Today
Considerations of evaluation order in more complex Lambda Calculus expressions
((λx.λy.x λa.a)λb.b)
Evaluation order?
Eager / Strict / Applicative
(λb.b(λx.λy.x λa.a))
(λb.bλy.λa.a)
λy.λa.a
Lazy / Non-strict / Normal
(λb.b(λx.λy.x λa.a))
(λx.λy.x λa.a)
λy.λa.a
(λb.b(λx.λy.x λa.a))
Evaluation order?
Eager / Strict / Applicative
((λp.λq.(p q) (λx.x λa.λb.a)) λk.k)
((λp.λq.(p q) λa.λb.a) λk.k)
(λq.(λa.λb.a q) λk.k)
(λa.λb.a λk.k)
λb.λk.k
Lazy / Non-strict / Normal
((λp.λq.(p q) (λx.x λa.λb.a)) λk.k)
(λq.((λx.x λa.λb.a) q) λk.k)
((λx.x λa.λb.a) λk.k)
(λa.λb.a λk.k)
λb.λk.k
((λp.λq.(p q) (λx.x λa.λb.a)) λk.k)
Evaluation order?
Eager / Strict / Applicative
(λz.(ztrue)((λx.λy.λf.((fx)y)one)two))
(λz.(ztrue)(λy.λf.((f one)y)two))
(λz.(ztrue)λf.((f one) two))
(λf.((f one) two))true)
((true one) two))
((λx.λy.x one) two))
one
Lazy / Non-strict / Normal
(λz.(ztrue)((λx.λy.λf.((fx)y)one)two))
(((λx.λy.λf.((fx)y)one)two)true)
((λy.λf.((fone)y)two)true)
(λf.((fone)two)true)
((trueone)two)
((λx.λy.xone)two)
one
(λz.(ztrue)((λx.λy.λf.((fx)y)one)two))
Will the outputs always be the same?
Eager / Strict / Applicative
((λf.λx.(x(ff))λs.(ss))false)
(λx.(x(λs.(ss)λs.(ss)))false)
(false(λs.(ss)λs.(ss)))
(false(λs.(ss)λs.(ss)))
Doesn’t terminate!
Lazy / Non-strict / Normal
((λf.λx.(x(ff))λs.(ss))false)
(λx.(x(λs.(ss)λs.(ss)))false)
(false(λs.(ss)λs.(ss)))
(λx.λy.y(λs.(ss)λs.(ss)))
λy.y
((λf.λx.(x(ff))λs.(ss))false)
Let’s practice repetition some more:
sum-from-one
/docProps/thumbnail.jpeg
Reviews
There are no reviews yet.