Programming Languages (CS 328) Homework 1 Computer Science and Engineering Out: 2000-08-12 Indian Institute of Technology Bombay Due: 2000-08-31

1. Evaluate

      (a) [(c d)/a] (λ b ((λ a (a b)) a) )
     (b) [(b d)/a] (λ b ((λ a (a b)) a) )

renaming variables as needed to preserve the Stoy diagram. Draw the final Stoy diagram.

2. Reduce the following expressions to normal order in as many different ways as possible, or show that there is no normal form.

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