COSC 3410 Programming Languages

Fall 2011

Homework Assignment #4

Home of the Free and the Bound

Due: Wednesday, Sept 28, 11:00am CDT
Submit: Turn in a single Scheme source file called "hw4.scm" using the turnin command on the Systems Lab machines. Include the names of all authors at the top of the file in a comment block.
Work may be completed in pairs. Each team should submit only once.
The SchemeUnit facility provides a valuable mechanism for automatic unit testing of your Scheme code. I strongly recommend that you learn to create thorough testsuites for this and future assignments. As we add to our interpreter project, being able to quickly and automatically verify that earlier testcases still work will be invaluable. I am providing a basic Homework 4 Testsuite as a starting point; it contains the testcases on page 18 of our textbook. You will need to add additional tests as you progress through the assignment. Directions for running the testsuite are included in the comments at the top of the source file.

Q1 - occurs-free? with multiple parameters

Beginning with the code for occurs-free? on p.19 of Essentials of Programming Languages, add support for lambda expressions with multiple parameters.

Q2 - if-expressions

Add support for if expressions to occurs-free?.

Q3 - let-expressions

Add support for let expressions to occurs-free?.

Q4 - and the others

Completing most of our core Scheme grammar from lecture, add support for quote, set!, and numeric constants to occurs-free?.

Q5 - Occurs-bound?

Build a new function occurs-bound?.
occurs-bound? : Sym x LcExp → Bool
Usage: (occurs-bound? sym exp) = true if the symbol occurs as a bound variable reference in the expression, otherwise returns false.
Note that occurs-bound? is not simply the opposite of occurs-free?. It is possible for both functions to return false for a given expression (the variable does not occur at all,) and it is also possible for both functions to return true for a given expression (a variable occurs both free and bound in different places.)

Examples:
> (occurs-bound? 'x 'x)
#f
> (occurs-bound? 'x 'y)
#f
> (occurs-bound? 'x '(lambda (x) (x y)))
#t
> (occurs-bound? 'x '(lambda (y) (x y)))
#f
> (occurs-bound? 'x '((lambda (x) x) (x y)))
#t
> (occurs-bound? 'x '(lambda (y) (lambda (z) (x (y z)))))
#f