►C311/  H311/  A596/  B521 Fall 2024 – Programming Languages
▼Assignments
•3 Assignment 3:   Lexical Addressing, Environments and Interpreters
    contents  ← prev  up  next → 

3 Assignment 3: Lexical Addressing, Environments and Interpreters

Inverting the adage that a data type is just a simple programming language, we take the position that a programming language is, semantically, just a complex data type; evaluation of a program is just another operation in the data type.

——Mitch Wand

Assignment

Place your code in a file named a3.rkt and submit it to Autograder.

Part 1: Lexical Addressingo

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

Part 2: Interpreters and Higher Order Function Representation

  1. In recent lectures, we’ve learned how to write an interpreter that takes a Racket expression and returns the result of evaluating that expression. We have also learned to make it representation independent with respect to environments and closures. We have written helper functions that manipulate the representations of environments and closures: extend-env, apply-env, empty-env, apply-clos and make-clos. In Part 2, we will implement two interpreters in total: the basic representation dependent (RD) interpreter, and the representation independent (RI) interpreter, along with helper functions for the RI interpreter.

    • You must define a set of environment helpers: that uses functional (higher-order) representation of environments. Call the representation-dependent version value-of, and the representation independent version value-of-fn.

    • Notice these names may be different from those presented in lecture. This is a framework for how you should name your procedures and helpers:

      (define value-of ...)
       
      (define value-of-fn ...)
      (define empty-env-fn ...)
      (define extend-env-fn ...)
      (define apply-env-fn ...)
      (define apply-clos-fn ...)
      (define make-clos-fn ...)

    • Your interpreter must handle the following forms: numbers, booleans, variables, lambda-abstraction, application, zero?, sub1, *, if, and let

    • Unlike in Racket, here let can bind only one variable.

    • Remember, your solutions should be compositional.

    • You may have seen the expansion of (let ((x e)) body) as ((lambda (x) body) e). When you are comfortable with the environment, however, you can implement let without using this expansion.

    • As usual, these references are not required, but yield a wider understanding of what we’re doing, see Reynolds and Danvy.

    > (value-of
       '((lambda (x) (if (zero? x)
                         #t
                         #f))
         0)
       (lambda (y) (error 'value-of "unbound variable ~s" y)))
    #t
    > (value-of
       '((lambda (x) (if (zero? x)
                         12
                         47))
         0)
       (lambda (y) (error 'value-of "unbound variable ~s" y)))
    12
    > (value-of
       '(let ([y (* 3 4)])
          ((lambda (x) (* x y)) (sub1 6)))
       (lambda (y) (error 'value-of "unbound variable ~s" y)))
    60
    > (value-of
       '(let ([x (* 2 3)])
          (let ([y (sub1 x)])
            (* x y)))
       (lambda (y) (error 'value-of "unbound variable ~s" y)))
    30
    > (value-of
       '(let ([x (* 2 3)])
          (let ([x (sub1 x)])
            (* x x)))
       (lambda (y) (error 'value-of "unbound variable ~s" y)))
    25
    > (value-of
       '(let ((! (lambda (x) (* x x))))
          (let ((! (lambda (n)
                     (if (zero? n) 1 (* n (! (sub1 n)))))))
            (! 5)))
       (lambda (y) (error 'value-of "unbound variable ~s" y)))
    80
    > (value-of
       '(((lambda (f)
            (lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n))))))
          (lambda (f)
            (lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n)))))))
         5)
       (lambda (y) (error 'value-of "unbound variable ~s" y)))
    120
    > (value-of-fn
       '((lambda (x) (if (zero? x)
                         #t
                         #f))
         0)
       (empty-env-fn))
    #t
    > (value-of-fn
       '((lambda (x) (if (zero? x)
                         12
                         47))
         0)
       (empty-env-fn))
    12
    > (value-of-fn
       '(let ([y (* 3 4)])
          ((lambda (x) (* x y)) (sub1 6)))
       (empty-env-fn))
    60
    > (value-of-fn
       '(let ([x (* 2 3)])
          (let ([y (sub1 x)])
            (* x y)))
       (empty-env-fn))
    30
    > (value-of-fn
       '(let ([x (* 2 3)])
          (let ([x (sub1 x)])
            (* x x)))
       (empty-env-fn))
    25
    > (value-of-fn
       '(((lambda (f)
            (lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n))))))
          (lambda (f)
            (lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n)))))))
         5)
       (empty-env-fn))
    120
Brainteasers

  1. Extend your interpreter value-of to support set! and begin2, where begin2 is a variant of Racket’s begin that is restricted to exactly two arguments, and set! mutates variables. You could use mutable boxes to hold values in your immutable environment using only (set-box! b value) and (box value).

    > (value-of
        '(* (begin2 1 1) 3)
        (lambda (y) (error 'value-of "unbound variable ~s" y)))
    3
    > (value-of
        '((lambda (a)
            ((lambda (p)
               (begin2
                 (p a)
                 a))
         (lambda (x) (set! x 4))))
          3)
         (lambda (y) (error 'value-of "unbound variable ~s" y)))
    3
    > (value-of
       '((lambda (f)
           ((lambda (g)
              ((lambda (z) (begin2
                            (g z)
                            z))
               55))
            (lambda (y) (f y)))) (lambda (x) (set! x 44)))
       (lambda (y) (error 'value-of "unbound variable ~s" y)))
    55
    > (value-of
        '((lambda (x)
            (begin2 (set! x 5) x))
          6)
        (lambda (y) (error 'value-of "unbound variable ~s" y)))
    5
    > (value-of
        '(let ((a 3))
            (begin2 (begin2 a (set! a 4)) a))
        (lambda (y) (error 'value-of "unbound variable ~s" y)))
    4
    > (value-of
        '((lambda (x)
            (begin2
              ((lambda (y)
             (begin2
               (set! x 0)
               98))
               99)
              x))
          97)
        (lambda (y) (error 'value-of "unbound variable ~s" y)))
    0
    > (value-of
        '((lambda (y)
            (let ((x (begin2
                       (set! y 7)
                       8)))
              (begin2
                (set! y 3)
                  ((lambda (z) y)
                   x))))
          4)
        (lambda (y) (error 'value-of "unbound variable ~s" y)))
    3
    > (value-of
        '(let ((a 5))
           (let ((y (begin2 (set! a (sub1 a)) 6)))
             (begin2
               (* y y)
               a)))
        (lambda (y) (error 'value-of "unbound variable ~s" y)))
    4

  2. Consider the following interpreter for a deBruijnized version of the lambda-calculus (i.e. lambda-calculus expressions using lexical addresses instead of variables). This interpreter is representation-independent with respect to environments. There are a few other slight variations in the syntax of the language, but are of no particular consequence.

    (define value-of-lex
      (lambda (exp env)
        (match exp
          [`(const ,expr) expr]
          [`(mult ,x1 ,x2) (* (value-of-lex x1 env) (value-of-lex x2 env))]
          [`(zero ,x) (zero? (value-of-lex x env))]
          (`(sub1 ,body) (sub1 (value-of-lex body env)))
          (`(if ,t ,c ,a) (if (value-of-lex t env) (value-of-lex c env) (value-of-lex a env)))
          (`(var ,num) (apply-env-lex env num))
          (`(lambda ,body) (lambda (a) (value-of-lex body (extend-env-lex a env))))
          (`(,rator ,rand) ((value-of-lex rator env) (value-of-lex rand env))))))
     
    (define empty-env-lex
      (lambda ()
        (lambda (y) (error 'value-of "unbound variable ~s" y))))

    From the following call one can see we’re using a functional representation of environments.

    > (value-of-lex '((lambda (var 0)) (const 5)) (empty-env-lex))
    5

    Define apply-env-lex and extend-env-lex. As ever, you are not required to handle bad data. Make sure to add value-of-lex and empty-env-lex to your file, so that we can test your helpers.

Just Dessert

  1. The lambda calculus can be used to define a representation of natural numbers, called Church numerals, and arithmetic over them. For instance, c5 is the definition of the Church numeral for 5.

    > (define c0 (lambda (f) (lambda (x) x)))
    > (define c5 (lambda (f) (lambda (x) (f (f (f (f (f x))))))))
    > ((c5 add1) 0)
    5
    > ((c0 add1) 0)
    0

    The following is a definition for Church plus, which performs addition over Church numerals.

    > (define c+ (lambda (m)
                   (lambda (n)
                     (lambda (add1)
                       (lambda (zero)
                         ((m add1) ((n add1) zero)))))))
    > (let ((c10 ((c+ c5) c5)))
        ((c10 add1) 0))
    10

    One way to understand the definition of c+ is that, when provided two Church numerals, it returns a function that, when provided a meaning for add1 and a meaning for zero, it returns the meaning of the sum of m and n.

    Your task, however, is to implement csub1, Church predecessor. The following tests should pass.

    > (((csub1 c5) add1) 0)
    4
    > (((csub1 c0) add1) 0)
    0

    In the second case, the Church predecessor of Church zero is zero, as we haven’t a notion of negative numbers.

    This was a difficult problem, but it’s fun, so don’t Google it. If you think it might help though, consider taking a trip to the dentist.

    contents  ← prev  up  next →