CIS 352   —   SPRING 2008

Homework 3

Coverage

Logistics

You may work singly or in pairs on this assignment.

What to Turn in:

• A copy of the source code and verified test cases demonstrating that your code is correct.
• Be sure to include contract and purpose statements for each procedure you are asked to write. (See the Homework Policy for more details.)

EXERCISES

1. (10 points) Consider the following lambda-calculus expression:

    ((lambda (r) 
       ((lambda (s) 
          (r (u s))) 
        (s (lambda (t) (v t))))) 
     (r (lambda (v) u))) 

   1. Which of the variables r, s, t, u, and v occur free in the expression?
   2. Which of the variables r, s, t, u, and v occur bound in the expression?

2. (32 points) EOPL, Exercise 1.19 (both free-vars and bound-vars).

   You may use the union and remove procedures available in the file union.scm, unless you prefer to write your own. You will also probably want to look up the Scheme functions member, memq, and memv. (You can look here.)

3. (20 points) EOPL, Exercises 1.22 and 1.23.

   Augment both the formal definitions (i.e., Definition 1.3.3) and the procedures occurs-free? and occurs-bound? (see Figure 1.1).

4. (12 points) EOPL, Exercises 1.24.

   Augment the formal definitions (i.e., Definition 1.3.3) for let only, also you do not need to implement these cases.

5. (16 points) Consider the following expression:

   (lambda (c b a)          ;; line 1 
     (b                     ;; line 2
      (lambda (w x y z)     ;; line 3 
        ((lambda (z a)      ;; line 4 
           (y (a x) (c z))) ;; line 5 
         (z (a c))) )))     ;; line 6 
   

   Fill in the following table with the correct lexical address for each of the indicated variable references.

   Variable reference	Lexical address (d,p)
   b on line 2
   y on line 5
   a on line 5
   x on line 5
   c on line 5
   z on line 5
   c on line 6
   z on line 6