CIS 352   —   SPRING 2008

Homework 4

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. (15 points) Draw the abstract-syntax tree for the following lambda-calculus expression, using the abstract syntax given on page 49 of EOPL:

   (lambda (z) ((f z) (lambda (w) (g w)))) 

2. (15 points) Write a Scheme procedure count-decls that takes a lambda-calculus expression in abstract-syntax form and returns the number of variable declarations in that expression. For example:

   > (count-decls (parse-expression '((lambda (z) (x y)) (lambda (y) (y w))) )) 
   2

3. (15 points) Write a Scheme procedure innermost that takes a lambda-calculus expression in abstract-syntax form and returns a list of those bindings (i.e., abstractions) in exp that do not contain any nested bindings. For example:

   > (define exp1 '(lambda (w) ((lambda (t) (t u)) 
                                (lambda (y) (lambda (u) (u y))))) )
   
   > (map unparse-expression (innermost (parse-expression exp1))) 
   ((lambda (t) (t u)) (lambda (u) (u y)))
   
   > (map unparse-expression (innermost (parse-expression '(x t)))) 
   () 
   

4. (20 points) Write a Scheme procedure hole-in-scope? that takes a lambda-calculus expression in abstract-syntax form and determines whether it contains at least one binding with a hole in its scope. For example:

   > (define exp2 '(lambda (z) (lambda (x) ((y x) (lambda (x) x)))) ) 
   > (define exp3 '(lambda (z) (lambda (y) ((y x) (lambda (x) x)))) ) 
   > (hole-in-scope? (parse-expression exp2)) 
   #t 
   
   > (hole-in-scope? (parse-expression exp3)) 
   #f 
   

5. (30 points) Recall the following BNF specification for binary trees from Lab 3:

   <bin-tree> ::= ()   |   (<number>   <bin-tree>   <bin-tree>)

   We can define a datatype to represent the abstract syntax of binary trees as follows:

   (define-datatype bintree bintree? 
                    (empty-tree) 
                    (node (id number?) 
                          (left bintree?) 
                          (right bintree?)) 
   ) 
   

   1. Write a Scheme procedure parse-tree that takes a binary tree in concrete-syntax form (i.e., in the form used in Lab 3) and returns the abstract-syntax form of the binary tree. You may assume that the input to parse-tree is well formed.

   2. Write a Scheme procedure unparse-tree that takes a binary tree in abstract-syntax form and returns the concrete-syntax form of the binary tree.

   For example, your procedures should have the following behavior:

   >(unparse-tree (parse-tree '(5 (2 () (4 () ())) (7 (6 () ()) (15 () ()))))) 
   (5 (2 () (4 () ())) (7 (6 () ()) (15 () ()))) 
   

   Note: Your test cases for these procedures will need to be combined, as in the example above.