Homework #11

This problem requires Lecture 9 and book section 1.3.

Exercise 1.19, p.31 - (50 minutes)
Write a procedure free-vars that takes a list structure representing an expression in the lambda calculus syntax given above and returns a set (a list without duplicates) of all the variables that occur free in the expression. Similarly, write a procedure bound-vars that returns a set of all the variables that occur bound in its argument.

See the help page. The concept of free and bound variables is an important one in programming languages. Use your union function to return a list without duplicates.

For instance, given

(define exp '(lambda (x)
               ((lambda (z) (x y))
                (lambda (y) y))))

your answers should be some permutation of the correct answer (i.e.: both '(x y) and '(y x) are valid)

    > (bound-vars exp)
    (x y)

    > (free-vars exp)
    (y)

YOU MUST NAME YOUR FUNCTIONS WITH THE SAME NAME THEY HAVE IN THE BOOK: free-vars, bound-vars.

Exercise 1.27, p.34 - (10 minutes)
In the following expressions connect each variable reference to its associated formal parameter declaration.

	(lambda (x)
		(lambda (y)
			((lambda (x)
				 (x y))
			x)))

	(lambda (z)
		((lambda (a b c)
			(a (lambda (a) (+ a c)) b))
		(lambda (f x)
			(f (z x)))))

Notice:  Uninitialized string offset:  1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150

You may want to type these in to DrScheme and use parentheses matching to help you find the end of expressions. Use numbers to distinguish occurrences instead of drawing arrows as suggested by the book since you'll be typing your answers. For instance, given

(lambda (x)
  (x (lambda (x) x)))

your answer should be

(lambda (x.1)
  (x.1 (lambda (x.2) x.2)))

This part will not be autograded, so please comment it out to avoid any errors with the submit script..

You must log in first before submitting homework assignments.

Instructions on submitting homework is here

Last updated at 11:43 am on Friday, September 23, 2005.