Programming Languages (CS 328) Homework 1 Computer Science and Engineering Out: 2000-01-27 Indian Institute of Technology Bombay Due: 2000-02-15

1. For each of the lambda expressions below,

• draw the parse tree according to the λ-grammar,

• draw the Stoy diagram, and

• indicate for each occurrence of a variable if it is bound or free.

Convert curried terms to un-curried forms first, if necessary.

 (a) (λ x (x y))
 (b) ((λ (z x) (x y z)) z)
 (c) (z (λ y ((λ z (x y)) z)))
 (d) (λ x (((λ y ((λ z (x r)) y)) y) z))

2. Write down all the possible reduction sequences for the expression

       ((λ a ((λ b c) a)) (λ d (e d))).

3. Reduce the following expressions to normal form if possible, otherwise indicate that a normal form does not exist. Some expressions may be in curried form.

 (a) ((λ y (y y)) (λ x x))
 (b) (y (λ y (y (λ x (x y)))))

4. Write a lambda term to define the macro EVEN? which accepts a single Church numeral as argument and returns a boolean TRUE or FALSE according as the integer corresponding to the Church numeral is even or odd. Do not use recursion or the Y -combinator.

5. Here is a variant form of the Y -combinator:

                    Y = (λ f ((λ x (f (x x))) (λ x (f (x x)))))

Reduce to normal form if possible:

 (a) (Y (λ x x))
 (b) (Y (AND FALSE))
 (c) (Y (λ x ((TIMES ¯2) x)))

In each case rationalize and explain and final answer you get through reductions. (Can you guess some of the answers ahead of time given the intent of Y?)

6. In the same style as in the lecture, interpret the following FL program using the FLK interpreter. Be sure to show the different environments at different points in the ‘execution’ of the program. The answer should be 18.

    (let ((x 5))
        (let ((x 6) (f (nlambda (y z) (* y (- z x)))))
            (f x 8)))