Help for 1.19

We want to create a list of all the free variables in any expression with the following syntax:

<exp> ::= <id>                      -- variable references
        | (lambda (<id>) <exp>)     -- lambda expressions (only one formal allowed)
        | (<exp> <exp>)             -- applications

Check out this example of building Scheme functions from a BNF.

If it helps, you can define helper functions to access the pieces of the expression according to the BNF.  The first one should only be used if you know that the current exp is a list, and the second two access the specific pieces of the exp once we know it follows the lambda rule.

	

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

;;; syntax functions for lambda expressions

	(define is-lambda?     (lambda (lst) (eq? (car lst) 'lambda)))  ;; Note that this function assumes we're dealing with a list
	(define lambda-formals (lambda (lst) (cadr lst)))
	(define lambda-body    (lambda (lst) (caddr lst)))

	;;---- Test cases -----
	(is-lambda? '(lambda (x) y))
	> #t

	(lambda-formals '(lambda (x) y))
	> (x)

	(lambda-body '(lambda (x) y))
	> y 

Now, suppose that I had a list of all the variable declarations (i.e. what gets returned by lambda-formals). When we got a variable reference, we could just check the list to see if it was bound (i.e. in the list) or free (i.e. not in the list).  There is a function called member that tests for the occurrence of something in a list.  You probably used it when you wrote union.

In order to this, I will have to write an auxiliary function that accepts a new parameter holding the list of all currently bound variables. We'll call that variable cur-bound-lst.

	(define free-vars
	  (lambda (exp)
	    (free-vars-aux exp '()))

	(define free-vars-aux
	  (lambda (exp cur-bound-lst)
	    (cond ((symbol? exp)    (if (member exp cur-bound-lst)     

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

;; <exp> ::= <id>
	                                '()                            ;;    it's bound, so return nothing
	                                (list exp)))                   ;;    it's free, so return it in a list
	          ((is-lambda? exp) ...)                               ;; <exp> ::= (lambda (<id>) <exp>)

	           ...              ...                                ;; <exp> ::= (<exp> <exp>)
	    )))

You'll need to update cur-bound-lst whenever you recurse on a lambda, but not when you recurse for an application. Why?

This problem is easier (at least it was for me) using union, the function that you wrote for from HW-10 to return a list without duplicates.

If there are problems with this page, please send mail to <cs330ta@cs.byu.edu>
If you have a comment about the class, please send mail to <seamons@cs.byu.edu>

© 1994-2009, Phillip J. Windley and Bryan S. Morse.  All rights reserved.
Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy.

Last updated at 9:53 am on Friday, August 27, 2004.