Csc 4330/6330, Programming Language Concepts (Spring 2018)

Homework 4b (Due: 21 March (Wednesday))

  1. Make all parentheses explicit in the following expressions:
    λx.xz λy.xy
    (λx.xz) λy.w λw.wyzx 
    λx.xy λx.yx
  2. Apply β-reductions to the folowing λ expressions as much as possible:
    (λz.z) (λy.y y)(λx.x a)
    (λz.z)(λz.z z)(λz.z y)
    (λx.λy.x y y)(λa.a) b
    ((λf.λa.(f a) λx.x) λs.(s s))
    ((λf.λa.(f a) λs.(s s)) λx.x)
  3. Consider the following definitions for the numerals 0,1,2,...
    zero = λs.λz.z
    one = λs.λz.(s z)
    two = λs.λz.(s (s z))
    three = λs.λz.(s (s (s z)))
    four = λs.λz.(s (s (s (s z))))
    five = λs.λz.(s (s (s (s (s z)))))
    and the definition of addition:
    plus = λm.λn.λs.λz.(m s (n s z))
    Show that
    (plus two three)
    reduces to