Assignment 2 - Free, Bound, and Lexical Address

• Place the definitions of the following functions in a file called a2.scm and submit it to Vincent. For the purposes of this assignment, assume that lambda-calculus expressions consist of variables, lambda-expressions that take exactly one argument, and function applications.
• Please use pmatch in your assignment.

1. Define a function walk-symbol that takes a symbol x and an association list s. An association list is a list of pairs of associated values, for example ((a . 5) (b . (1 2)) (c . a)). Your function should search through s for the value associated with x. If the associated value is a symbol, it too must be walked in s. If x has no association, then walk-symbol should return x.

   (walk-symbol 'a '((a . 5) (b . 6) (c . a))) => 5
(walk-symbol 'c '((a . 5) (b . (a . c)) (c . a))) => 5
(walk-symbol 'b '((a . 5) (b . ((c . a))) (c . a))) => ((c . a))
(walk-symbol 'd '((a . 5) (b . (1 2)) (c . a) (e . c) (d . e))) => 5
(walk-symbol 'd '((a . 5) (b . 6) (c . f) (e . c) (d . e))) => f


2. Define a function free that takes a lambda-calculus expression and returns a list of all the variables that occur free in that expression. The list must not contain duplicate variables.

   (free '((lambda (x) ((x y) e)) (lambda (c) (x (lambda (x) (x (e c))))))) => (y e x)


3. Define a function bound that is identical to free except that it returns a list of all the variables that occur bound in the input expression. The list must not contain duplicate variables.

   (bound '((lambda (x) ((x y) e)) (lambda (c) (x (lambda (x) (x (e c))))))) => (x c)


4. Define a function lex that takes a lambda-calculus expression, and returns the same expression with all variable references replaced by lists of two elements whose car is the symbol var and whose cadr is the lexical address of the referenced variable. Each free variable is similarly wrapped within a list whose car is the symbol free-var.

   (lex '((lambda (x) (x y)) (lambda (c) (lambda (d) (e c))))) =>
((lambda ((var 0) (free-var y))) (lambda (lambda ((free-var e) (var 1)))))

5. Define a predicate weird? that takes a variable x and a lambda-calculus expression e, and returns #t if there occurs within e a subexpression (lambda (x) e^) such that x occurs both free and bound within e^. Otherwise, weird? returns #f.

   (weird? 'x '(lambda (x) (x (lambda (x) x)))) => #t
(weird? 'x '(x (lambda (x) x))) => #f
(weird? 'x '(lambda (y) (x (lambda (x) x)))) => #f

6. Brainteaser:

   Two values u and v are equivalent relative to an association list s if:

   1. u and v are equal? -or-
   2. if we were to substitute the walked (defined below) values for all the symbols in u and v, the resulting values would be equal? -or-
   3. we can add associations to s to make u and v equivalent with respect to the extended association list.
   Define a function equiv that takes two values u and v, and an association list s. equiv returns #f if u and v are not equivalent; otherwise, equiv returns s or an extended association list in which u and v are equivalent.
   (equiv 'x 'y '()) => ((x . y)) or ((y . x))
(equiv '(x) '(y) '()) => ((x . y)) or ((y . x))
(equiv 5 5 '()) => ()
(equiv 5 6 '()) => #f
(equiv '(5 6) '(x y) '()) => ((x . 5) (y . 6)) or ((y . 6) (x . 5))
(equiv '(z 5) '(5 x) '((z . 3) (x . z))) => #f
(equiv '((x . 5) (y . z)) '((y . 5) (x . 5)) '((z . 5) (x . y)))
=> ((z . 5) (x . y)) or ((x . y) (z . 5)) etc.

   (define walk
     (lambda (v s)
       (if (symbol? v)
           (walk-symbol v s)
           v)))