C311 Fall 1996 -- Programming Languages

Assignment 2: Static Properties

Due Friday, September 20, 5:00P

EOPL Exercise 2.3.1, bound-vars procedure

> (bound-vars '((lambda (x) x) y))
(x)
> (bound-vars '(lambda (x) (y (lambda (y) (y z)))))
(y)

EOPL Exercise 2.3.2, bound? procedure

> (bound? 'x '(lambda (x) x))
#t
> (bound? 'y '(lambda (x) y))
#f
> (bound? 'x '((lambda (x) x) x))
#t

EOPL Exercise 2.3.10

For variable references v that are free in the expression, replace the variable reference with the list (v : free).

(lexical-address '(lambda (a b c)
		    (if (eq? b c)
		      ((lambda (c) (cons a c)) a) b)))

(lambda (a b c)
  (if ((eq? : free) (b : 0 1) (c : 0 2))
      ((lambda (c)
         ((cons : free) (a : 1 0) (c : 0 0))) (a : 0 0))
      (b : 0 1)))

Try to find linear-time algorithms for these procedures. Hint: for each procedure, define an auxiliary procedure that takes an extra argument, which records information on the nature of lexically enclosing bindings.

Submission

Write your answers to the exercises in a file (following the indentation rules), and send that file to

c311@lakshmi.cs.indiana.edu

with the subject line

handin 2

Assuming you've saved your homework in the file ``two.ss'' in the current directory, one way to submit is with the command:

Mail -s "handin 2" c311@lakshmi.cs.indiana.edu < two.ss

Chris Haynes / chaynes@indiana.edu