2 Assignment 2: Free, Bound variables
There may, indeed, be other applications of the system than its use as a logic.
——Alonzo Church, writing about the lambda calculus in 1932
Guidelines for this assignment
You must test your solutions before submitting your assignment. We have provided some test cases for each exercise to get you started, but the provided test cases are not exhaustive.
For the purposes of this assignment, assume that lambda-calculus expressions consist of:
variables
lambda expressions that take exactly one argument and have exactly one body
applications of two lambda calculus expressions
Assignment
Part 1: Natural Recursion Refresher
Functions defined in Part 1 can(actually, should) be used as helper functions for the later problems.
Consider the following partial definition of the list-ref function. It is intended to operate similarly to Racket’s list-ref. n is a zero-based index. Therefore, n cannot be greater than or equal to the length of ls and is treated as bad data.
(define list-ref (lambda (ls n) (letrec ([nth-cdr (lambda (n) ;; complete the definition )]) (car (nth-cdr n))))) The body of the function that is the right-hand side of nth-cdr is missing. Complete the definition of list-ref with a naturally-recursive implementation of nth-cdr, so that the following work correctly. You should not need to modify the provided code beyond completing the function body containing a comment.
> (list-ref '(a b c) 2) 'c > (list-ref '(a b c) 0) 'a Remember, you need not consider bad data in your definition.
Define and test a procedure union that takes two lists with no duplicates, and returns a list containing the union of the two input lists. You may find it helpful to use Racket’s memv for this definition. Again, the order of the elements in your answer does not matter.
> (union '() '()) '() > (union '(x) '()) '(x) > (union '(x) '(x)) '(x) > (union '(x y) '(x z)) '(x y z) Define and test a procedure stretch that takes two arguments, say pred and x. The first argument pred is a predicate. (Recall what predicates are and how to use them from the previous assignment.) What stretch returns should be another predicate. The returned predicate should be satisfied exactly by those things that are eqv? to x or satisfy pred.
> ((stretch even? 1) 0) #t > ((stretch even? 1) 1) #t > ((stretch even? 1) 2) #t > ((stretch even? 1) 3) #f > (filter (stretch even? 1) '(0 1 2 3 4 5)) '(0 1 2 4) > (filter (stretch (stretch even? 1) 3) '(0 1 2 3 4 5)) '(0 1 2 3 4) > (filter (stretch (stretch (stretch even? 1) 3) 7) '(0 1 2 3 4 5)) '(0 1 2 3 4) Define and test a procedure 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, the following is an association list:
'((a . 5) (b . (1 2)) (c . a)) Your procedure 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. You might find assv useful.
> (walk-symbol 'a '((a . 5))) 5 > (walk-symbol 'a '((b . c) (a . b))) 'c > (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
Part 2: Free, Bound variables
Unless otherwise stated, you must use match in each of the remaining problems. The brainteasers might be easier with it as well. You may find some of the functions from Part 1 of use to you as well. For the most part, you should expect to be performing recursion on lambda-calculus expressions. You should only need to make use of the features of match demonstrated in class. The lambda-expressions in the questions below are not necessarily lambda-expression programs, unless stated otherwise.
Redefine and test the below procedure lambda-exp? that takes a lambda-calculus expression E and returns #f (false) if the input lambda-expression is not well formed, i.e. it contains bad data. Otherwise it returns #t (true).
(define lambda-exp? (λ (E) (letrec ([p (λ (e) (match e [`,y #t] [`(lambda (,x) ,body) (p body)] [`(,rator ,rand . ,more) (or (p rator) (p rand))] [else #f]))]) (p E)))) Unfortunately, the above program doesn’t meet these expectations. Fix it so it does.> (lambda-exp? 'x) #t > (lambda-exp? '(lambda (x) x)) #t > (lambda-exp? '(lambda (f) (lambda (x) (f (x x))))) #t > (lambda-exp? '(lambda (x) (lambda (y) (y x)))) #t > (lambda-exp? '(lambda (z) ((lambda (y) (a z)) (h (lambda (x) (h a)))))) #t > (lambda-exp? '(lambda (lambda) lambda)) #t > (lambda-exp? '((lambda (lambda) lambda) (lambda (y) y))) #t > (lambda-exp? '((lambda (x) x) (lambda (x) x))) #t > (lambda-exp? '((lambda (5) x) (lambda (x) x))) #f > (lambda-exp? '((lambda (x) x) (lambda (x) x) (lambda (x) x))) #f > (lambda-exp? '((lambda (lambda (x) x) x) (lambda (x) x))) #f Define and test a procedure var-occurs? that takes a variable name and a lambda-calculus expression and returns a boolean answering whether that variable occurs in the expression. Here and forevermore in this class we use the word occur in its technical sense: for us, a formal does not count as a variable occurrence.
> (var-occurs? 'x 'x) #t > (var-occurs? 'x '(lambda (x) y)) #f > (var-occurs? 'x '(lambda (y) x)) #t > (var-occurs? 'x '((z y) x)) #t Define and test a procedure vars that takes a lambda-calculus expression and returns a list containing all variables that occur in the expression. This should be a straightforward modification of the fixed up lambda-exp? in question 5, and the order of the variables in your answer does not matter.
> (vars 'x) (x) > (vars '(lambda (x) x)) (x) > (vars '((lambda (y) (x x)) (x y))) (x x x y) > (vars '(lambda (z) ((lambda (y) (a z)) (h (lambda (x) (h a)))))) (a z h h a) Define and test a modification of vars called unique-vars that behaves like vars but does not return duplicates. Use your union defined in this question.
> (unique-vars '((lambda (y) (x x)) (x y))) (x y) > (unique-vars '((lambda (z) (lambda (y) (z y))) x)) (z y x) > (unique-vars '((lambda (a) (a b)) ((lambda (c) (a c)) (b a)))) (c b a) Define and test a procedure var-occurs-free? that takes a symbol and a lambda-calculus expression and returns #t if that variable occurs free in that expression, and #f otherwise.
> (var-occurs-free? 'x 'x) #t > (var-occurs-free? 'x '(lambda (y) y)) #f > (var-occurs-free? 'x '(lambda (x) (x y))) #f > (var-occurs-free? 'x '(lambda (x) (lambda (x) x))) #f > (var-occurs-free? 'y '(lambda (x) (x y))) #t > (var-occurs-free? 'y '((lambda (y) (x y)) (lambda (x) (x y)))) #t > (var-occurs-free? 'x '((lambda (x) (x x)) (x x))) #t Define and test a procedure var-occurs-bound? that takes a symbol and a lambda-calculus expression and returns #t if that variable occurs bound in the expression, and #f otherwise.
> (var-occurs-bound? 'x 'x) #f > (var-occurs-bound? 'x '(lambda (x) x)) #t > (var-occurs-bound? 'y '(lambda (x) x)) #f > (var-occurs-bound? 'x '((lambda (x) (x x)) (x x))) #t > (var-occurs-bound? 'z '(lambda (y) (lambda (x) (y z)))) #f > (var-occurs-bound? 'z '(lambda (y) (lambda (z) (y z)))) #t > (var-occurs-bound? 'x '(lambda (x) y)) #f > (var-occurs-bound? 'x '(lambda (x) (lambda (x) x))) #t Define and test a procedure unique-free-vars that takes a lambda-calculus expression and returns a list of all the variables that occur free in that expression. Order doesn’t matter, but the list must not contain duplicate variables. You may find it helpful to use the definition of unique-vars from question 8 as a starting point.
> (unique-free-vars 'x) (x) > (unique-free-vars '(lambda (x) (x y))) (y) > (unique-free-vars '((lambda (x) ((x y) e)) (lambda (c) (x (lambda (x) (x (e c))))))) (y e x) Note that in the third example above,
((lambda (x) ((x y) e)) (lambda (c) (x (lambda (x) (x (e c))))))
is a single lambda-calculus expression (a procedure application), not a list of lambda-calculus expressions.
Define and test a procedure unique-bound-vars that takes a lambda-calculus expression and returns a list of all the variables that occur bound in the input expression. Order doesn’t matter, but the list must not contain duplicate variables.
> (unique-bound-vars 'x) () > (unique-bound-vars '(lambda (x) y)) () > (unique-bound-vars '(lambda (x) (x y))) (x) > (unique-bound-vars '((lambda (x) ((x y) e)) (lambda (c) (x (lambda (x) (x (e c))))))) (x c) > (unique-bound-vars '(lambda (y) y)) (y) > (unique-bound-vars '(lambda (x) (y z))) () > (unique-bound-vars '(lambda (x) (lambda (x) x))) (x) In class, we defined the function e1=e2? as below:
(define e1=e2? (λ (e1 e2) (match `(,e1 ,e2) (`(,y1 ,y2) #:when (and (symbol? y1) (symbol? y2)) (eqv? y1 y2)) (`((λ (,x1) ,b1) (λ (,x2) ,b2)) #:when (and (symbol? x1) (symbol? x2)) (and (e1=e2? b1 b2) (eqv? x1 x2))) (`((,rator1 ,rand1) (,rator2 ,rand2)) (and (e1=e2? rator1 rator2) (e1=e2? rand1 rand2)))))) It does not know the following two lambda expressions are the same:
(e1=e2? '(λ (x) x) '(λ (y) y))
Use lex to improve e1=e2? so that for two lambda expressions that have different bound variable names, it returns #t. You can assume that the lambda expressions we pass to e1=e2? do not have free variables.
Some more examples:
> (e1=e2? '(λ (x) (λ (y) (x y))) '(λ (x) (λ (z) (x z)))) #t > (e1=e2? '(λ (x) (λ (y) (x y))) '(λ (x) (λ (x) (x x)))) #f
Brainteasers
Given the following definition of factorial function
(define fact (λ (n) (cond [(zero? n) 1] [else (* n (fact (sub1 n)))]))) define a function t-fact which generates a "snake" when traced with trace (or is a tail recursive implementation of factorial).
(define t-fact (λ (n result) ;; complete the definition )) > (fact 5) 120 > (t-fact 5 1) 120 Consider again the scenario of the walk-symbol problem. Imagine that we frequently look up values in that association list. Walking the full chain every time may become prohibitively expensive, as certain perverse chains may be arbitrarily long. Consider the work you would have to do to walk "a" twice in the following association list.
'((z . 26) (y . z) (x . y) ... (b . c) (a . b))
To partially alleviate this burden, we will implement walk-symbol-update with path-compression, in the following manner. We will write our association list such that the right-hand side of each association is always a box that contains a value. Boxes are mutable memory references, meaning we can change the value the box contains. Then, when we walk the association list to find the final value for the symbol we started with, we can also change the values in boxes we had to walk through along the way, so that the right-hand side of each of those also contains the final value. Thus, if we have to walk that same symbol again, the lookup will be faster. See the following example.
> (define a-list `((c . ,(box 15)) (e . ,(box 'f)) (b . ,(box 'c)) (a . ,(box 'b)))) > a-list ((c . #&15) (e . #&f) (b . #&c) (a . #&b)) > (walk-symbol-update 'a a-list) 15 > a-list ((c . #&15) (e . #&f) (b . #&15) (a . #&15)) > (walk-symbol-update 'a a-list) 15 > a-list ((c . #&15) (e . #&f) (b . #&15) (a . #&15)) Without boxes (or some side-effect) we would have been required to re-copy the entire data structure each time we wanted to change a portion of it. You will find it useful to consult the Racket Documentation about Boxes for information about the box, unbox, and set-box! operations for this problem. You will also find begin useful.
Just Dessert
A variable can both occur free and occur bound in the same expression. Define a predicate var-occurs-both? that takes a variable x and a lambda-calculus expression, and returns two values, the first of which is a boolean answering whether the variable occurs free in the expression, and the second is a boolean answering whether the var occurs bound in the expression. Your solution should be a one-pass solution, meaning you should not recur over the same data twice, and you should not use an accumulator. In order to return multiple values, you should return them as cons pairs. match-let might prove helpful for this exercise.
> (var-occurs-both? 'x '(lambda (x) (x (lambda (x) x)))) (#f . #t) > (var-occurs-both? 'x '(x (lambda (x) x))) (#t . #t) > (var-occurs-both? 'x '(lambda (y) (x (lambda (x) x)))) (#t . #t) > (var-occurs-both? 'x '(lambda (x) (lambda (x) (x (lambda (x) x))))) (#f . #t) > (var-occurs-both? 'x '(lambda (x) (lambda (y) (lambda (x) (x (lambda (x) x)))))) (#f . #t) > (var-occurs-both? 'x '(lambda (y) (lambda (x) (lambda (z) (lambda (x) (x (lambda (x) x))))))) (#f . #t)