Question: Reducing to Normal Form

State whether each of the following lambda expressions are in normal form and if not, reduce it until it is.

  1. λx.xxx

Answer:

This expression is in normal form.

  1. (λx.xxx) (λx.x)

Answer:

This expression is not in normal form. It can be further reduced like so: (λx.xxx) (λx.x) →β (λx.x)(λx.x)(λx.x) →β (λx.x)(λx.x) →β (λx.x)

  1. λx.yz

Answer:

This expression is in normal form.

  1. (λx.(λy.yx) (xz)) y z

Answer:

This expression is not in normal form. It can be further reduced like so: (λx.(λy.yx) (xz)) y z →β (λx.xzx) y z →β yzy z

  1. (λx.x w)((λy.y)(λz.(λu.u)z))

Answer:

This expression is not in normal form. It can be further reduced like so: (λx.x w)((λy.y)(λz.(λu.u)z)) →β (λy.y)(λz.(λu.u)z) w →β (λz.(λu.u)z) w →β (λz.z) w →β w

Question: Lazily and Eagerly Evaluating Lambda Expressions

For each of the following expressions, try to evaluate them using the lazy method of evaluation and the eager method of evaluation. Do they both produce a result? If so, do they come up with the same result? Which was easier?

  1. (λx.λy.(y x)) ((λz.z) w)

Answer:

Eager Evaluation: (λx.λy.(y x)) ((λz.z) w) →β (λx.λy.(y x)) w →β λy.(y w)

Lazy Evaluation: (λx.λy.(y x)) ((λz.z) w) →β λy.(y ((λz.z) w)) →β λy.(y w)

  1. (λx.xy)(λy.zy)

Answer:

Eager Evaluation: (λx.xy)(λy.zy) →β (λy.zy)y →β zy

Lazy Evaluation: (λx.xy)(λy.zy) →β (λy.zy)y →β zy

Notice that both the eager and lazy evaluation are the same

  1. (λx.y)((λx.xx)(λx.xx))

Answer:

Eager Evaluation: (λx.y)((λx.xx)(λx.xx)) →β ((λx.y)((λx.xx)(λx.xx)) which is the exact same, so it repeats forever.

Lazy Evaluation: (λx.y)((λx.xx)(λx.xx)) →β y

Notice that the eager evaluation does not reach the normal form.

  1. (λx.x w)((λy.y)(λz.(λu.u)z))

Answer:

Eager Evaluation: (λx.x w)((λy.y)(λz.(λu.u)z)) →β (λx.x w)((λy.y)(λz.z)) →β (λx.x w)(λz.z) →β (λx.x w)(λz.z) →β (λz.z) w →β w

Lazy Evaluation: (λx.x w)((λy.y)(λz.(λu.u)z)) →β ((λy.y)(λz.(λu.u)z)) w →β (λz.(λu.u)z) w →β (λu.u) w →β w

  1. ((λf.(λx.fffx)) ((λy.yy) z)) z

Answer:

Eager Evaluation: ((λf.(λx.fffx)) ((λy.yy) z)) z →β ((λf.(λx.fffx)) zz) z →β (λx.zzzzzzx) z →β zzzzzzz

Lazy Evaluation: ((λf.(λx.fffx)) ((λy.yy) z)) z →β (λx.((λy.yy) z)((λy.yy) z)((λy.yy) z)x) z →β ((λy.yy) z)((λy.yy) z)((λy.yy) z)z →β zz((λy.yy) z)((λy.yy) z)z →β zzzz((λy.yy) z)z →β zzzzzzz