Computer Science 3675
Fall 2015
Practice Questions for Quiz 12

1. What is the significance of λ-calculus to the semantics of programming languages? Answer

2. If you perform a single β-reduction on (λx.λy.y x)(w z), what do you get?

   Answer

3. If you perform a single β-reduction on expression (λx.λy.x x y) (λz.z z), what do you get?

   1. λy.λz.z z (λz.z z) y
   2. (λx.λy.x x y) (λx.λy.x x y)
   3. λx.λy.(x x y) (x x y)
   4. λy.(λz.z z) (λz.z z) y

   Answer

4. For this problem, the following λ-calculus functions are assumed to be predefined, where x and y are Church-numerals and true and false are the standard boolean values.

   • cond is the conditional function (cond A B C = B when A = true and C when A = false),
   • isZero(x) yields true if x = 0 and false if x ≠ 0,
   • times x y is the product of x and y,
   • pred x is x − 1, for x > 0 and pred 0 = 0,
   • fix is a fixed-point finding function.

   Suppose that function k is defined in λ-calculus by k = λf.λx.cond (isZero(x)) (1) (times (2) (f (pred x))).

   If function g is defined by g = fix k, then which of the following is true of g?
   1. g(0) = 0, g(1) = 1, g(2) = 2.
   2. g(0) = 1, g(1) = 2, g(2) = 4.
   3. g(0) = 1, g(1) = 1, g(2) = 1.
   4. g(x) has no normal form for every Church-numeral x.

   Answer

5. A combinator is a term of λ-calculus that has no free variables. Which of the following are combinators?

   1. λx.λy.x
   2. λx.λy.λz.x z (y z)
   3. λx.λy.y z x

   Answer