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.
Define a function walk that takes a value x
and an association list s. An association list is one of
the form ((a . 5) (b . 6) (c . a)), where each element of
the list is a pair of associated values. Your function should search
through s for the value x as the
car of one of the pairs. If the associated value (the
cdr of that pair) is a non-symbol, simply return it. If,
however, the value you find is a symbol, you must then search the list
for that symbol. If you don't find an association for that symbol,
just return the symbol.
(walk 'a '((a . 5) (b . 6) (c . a))) => 5
(walk 'c '((a . 5) (b . 6) (c . a))) => 5
(walk 'b '((a . 5) (b . 6) (c . a))) => 6
(walk 'd '((a . 5) (b . 6) (c . a) (e . c) (d . e))) => 5
(walk 'd '((a . 5) (b . 6) (c . f) (e . c) (d . e))) => f
(walk '(a b c) '((a . 5) (b . 6) (c . a))) => (a b c)
(walk 6 '((a . 5) (b . 6) (c . a))) => 6
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) (lambda (x) (x (e c)))))) => (y e)
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) (lambda (x) (x (e c)))))) => (x c)
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)))))
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