3 Assignment 3: 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.

• You may find letrec, assv, remv, and filter useful.

Assignment

Part 1: Natural Recursion Refresher

Functions defined in Part 1 can (actually, should) be used as helper functions for the later problems.

1. 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.

2. 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)

3. 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 and Bound Variables

4. Redefine and test the below procedure lambda-exp? that takes a value 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

5. 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

6. 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)

7. Define and test a modification of vars called unique-vars that behaves like vars but does not return duplicates. It may help you review how the function sparse-natset-union was implemented in Assignment 2: Representation Independence.

   > (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)

8. 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

9. 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

10. 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 7 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.

11. 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)

Part 3: Lexical Addressing

12. Here we restrict our lambdas to have only one argument. The lexical address of a variable is the number of lambdas between the place where the variable is bound (also known as the formal) and the place where it occurs. For example, in the following expression:

    (lambda (x)

    (lambda (o)

    (lambda (r)

    (lambda (s)

    (lambda (p)

    (lambda (g)

    o))))))

    The o at the very bottom is a bound occurrence. It has a lexical address of 4, because there are four lambda expressions between the formal o at the top and the occurrence of o at the bottom.

    Define and test a procedure lex that takes a lambda-calculus expression and an accumulator (which starts as the empty list), and returns the same expression with all bound variable references replaced by lists of two elements whose first member is the symbol var and whose second member is the lexical address of the referenced variable. You should leave free variables as is.

    > (lex '(lambda (x) x)

    '())

    (lambda (var 0))

    > (lex '(lambda (y) (lambda (x) y))

    '())

    (lambda (lambda (var 1)))

    > (lex '(lambda (y) (lambda (x) (x y)))

    '())

    (lambda (lambda ((var 0) (var 1))))

    > (lex '(lambda (x) (lambda (x) (x x)))

    '())

    (lambda (lambda ((var 0) (var 0))))

    > (lex '(lambda (x) (lambda (x) (y x)))

    '())

    (lambda (lambda (y (var 0))))

    > (lex '(lambda (y) ((lambda (x) (x y)) (lambda (c) (lambda (d) (y c)))))

    '())

    (lambda ((lambda ((var 0) (var 1))) (lambda (lambda ((var 2) (var 1))))))

    > (lex '(lambda (a)

    (lambda (b)

    (lambda (c)

    (lambda (a)

    (lambda (b)

    (lambda (d)

    (lambda (a)

    (lambda (e)

    (((((a b) c) d) e) a)))))))))

    '())

    (lambda

    (lambda

    (lambda

    (lambda

    (lambda

    (lambda

    (lambda

    (lambda

    ((((((var 1) (var 3)) (var 5)) (var 2)) (var 0)) (var 1))))))))))

    > (lex '(lambda (a)

    (lambda (b)

    (lambda (c)

    (lambda (w)

    (lambda (x)

    (lambda (y)

    ((lambda (a)

    (lambda (b)

    (lambda (c)

    (((((a b) c) w) x) y))))

    (lambda (w)

    (lambda (x)

    (lambda (y)

    (((((a b) c) w) x) y)))))))))))

    '())

    (lambda

    (lambda

    (lambda

    (lambda

    (lambda

    (lambda

    ((lambda

    (lambda

    (lambda

    ((((((var 2) (var 1)) (var 0)) (var 5)) (var 4)) (var 3)))))

    (lambda

    (lambda

    (lambda

    ((((((var 8) (var 7)) (var 6)) (var 2)) (var 1)) (var 0))))))))))))

    > (lex '(lambda (a)

    (lambda (b)

    (lambda (c)

    (lambda (w)

    (lambda (x)

    (lambda (y)

    ((lambda (a)

    (lambda (b)

    (lambda (c)

    (((((a b) c) w) x) y))))

    (lambda (w)

    (lambda (x)

    (lambda (y)

    (((((a b) c) w) h) y)))))))))))

    '())

    '(lambda

    (lambda

    (lambda

    (lambda

    (lambda

    (lambda

    ((lambda

    (lambda

    (lambda ((((((var 2) (var 1)) (var 0)) (var 5)) (var 4)) (var 3)))))

    (lambda

    (lambda

    (lambda ((((((var 8) (var 7)) (var 6)) (var 2)) h) (var 0))))))))))))

    There are a number of ways you can approach this problem. Our suggestion is to build some lambda expressions with pen and paper, and then by hand find the lexical addresses of some variables that occur in them. Try and do it almost mechanically, starting from the body of the innermost lambda of the expression and working your way out. If there is more than one innermost lambda, pick one, resolve it and repeat. Then think about what it is you’re doing, and figure out how to do it without having to go back up the tree. That is, ensure that when you get to a variable position in the expression where you need to fill in the lexical address, that you already have all the information you need to figure it out.

13. 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))

    (`((lambda (,x1) ,b1) (lambda (,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)))

    (`,_ #f))))

    It does not know the following two lambda expressions are the same:

    (e1=e2? '(lambda (x) x) '(lambda (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? '(lambda (x) (lambda (y) (x y))) '(lambda (x) (lambda (z) (x z))))

    #t

    > (e1=e2? '(lambda (x) (lambda (y) (x y))) '(lambda (x) (lambda (x) (x x))))

    #f

Brainteasers

14. 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

15. 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

16. 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)