CS计算机代考程序代写 Lambda Calculus PowerPoint Presentation

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.(z true) ((λx.λy.λf.((f x) y) one) two))

(λz.(z true) (λy.λf.((f one) y) two))

(λz.(z true) λf.((f one) two))

(λf.((f one) two)) true)

((true one) two))

((λx.λy.x one) two))

one

Lazy / Non-strict / Normal

(λz.(z true) ((λx.λy.λf.((f x) y) one) two))

(((λx.λy.λf.((f x) y) one) two) true)

((λy.λf.((f one) y) two) true)

(λf.((f one) two) true)

((true one) two)

((λx.λy.x one) two)

one

(λz.(z true) ((λx.λy.λf.((f x) y) one) two))

Will the outputs always be the same?
Eager / Strict / Applicative

((λf.λx.(x (f f)) λs.(s s)) false)

(λx.(x (λs.(s s) λs.(s s))) false)

(false (λs.(s s) λs.(s s)))

(false (λs.(s s) λs.(s s)))

Doesn’t terminate!
Lazy / Non-strict / Normal

((λf.λx.(x (f f)) λs.(s s)) false)

(λx.(x (λs.(s s) λs.(s s))) false)

(false (λs.(s s) λs.(s s)))

(λx.λy.y (λs.(s s) λs.(s s)))

λy.y
((λf.λx.(x (f f)) λs.(s s)) false)

Let’s practice repetition some more:
sum-from-one

/docProps/thumbnail.jpeg