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

   five