Principles of Programming Languages — Homework 9

Due by class time Tuesday, October 12

Reading

Exercises

  1. In class, we included support in our interpreter for the equality and inequality operators == and !=. For example:

    (meaning '(c == 3))  → #t
(meaning '((1 + 1) == 2))  → #t
(meaning '((c + c) == (2 * c)))  → #t
(meaning '(pi == 3))  → #f
(meaning '((1 + 1) != 2))  → #f
(meaning '((1 + 1) != 3))  → #t
(meaning '(pi != 3))  → #t

    Add support for the comparison operators > and < to the interpreter. For example:

    (meaning '(pi < 3))  → #f
(meaning '((2 + 3) < (2 * 3)))  → #t
(meaning '(pi > 3))  → #t
(meaning '((2 + 2) > 4))  → #f

  2. We also added the boolean constants True and False to the initial environment. However, what happens when we try to compare these values directly using our == and != operators?

    (meaning '(True == True))
(meaning '(False == False))
(meaning '(True != False))
(meaning '(True != True))

    Fix the interpreter so that the == and != operators can be used to compare values of any type.

  3. The version of extend that we wrote in class creates a list of (symbol value) bindings to represent an environment. For example: 

    (define env1
  (extend '(a b c) '(5 4 0)
    (extend '(x y) '(15 3) empty-env)))

env1 → ((a 5) (b 4) (c 0) (x 15) (y 3))
    However, a more useful approach is to represent an environment as a list of frames, where each frame is a list containing a list of variables and a corresponding list of values. Replace your extend function with the new version shown below, which supports this new representation of environments: 
    (define extend
  (lambda (new-vars new-vals env)
    (let ([new-frame (list new-vars new-vals)])
      (cons new-frame env))))
    Redefining the environment env1 as shown above will now build a list containing two frames (the first frame is highlighted in red and the second frame in blue): 
    env1 → (((a b c) (5 4 0)) ((x y) (15 3)))

    Using this new representation of environments, write the functions (first-frame-vars env) and (first-frame-vals env), each of which takes an environment and retrieves the list of variables or values from the first frame of the environment. For example:

    (first-frame-vars env1) → (a b c)
(first-frame-vals env1) → (5 4 0)

  4. Write the function (retrieve var frame-vars frame-vals), which takes a variable var, a list of frame variables frame-vars, and a list of frame values frame-vals, and retrieves the value corresponding to var from frame-vals. You may assume that var will appear somewhere in frame-vars, and that frame-vars and frame-vals will be lists of the same length. For example:

    (retrieve 'b '(a b c d) '(1 2 3 4)) → 2
(retrieve 'd '(a b c d) '(1 2 3 4)) → 4
(retrieve 'z '(z y x) '(30 20 10)) → 30
(retrieve 'x '(z y x) '(30 20 10)) → 10
(retrieve 's '(p q r s t) '(6 2 9 0 5)) → 0

  5. Using your functions first-frame-vars, first-frame-vals, and retrieve as helper functions, write a new version of (lookup var env) that works with this new representation of environments. Hint: member? will also be useful as a helper. For example:

    (lookup 'c env1) → 0
(lookup 'a env1) → 5
(lookup 'x env1) → 15
(lookup 'y env1) → 3

  6. Write the function (frame-index var env), which returns the zero-based index number of the first frame of env that contains variable var. Use your helper functions to improve the readability of your code. For example:

    (define env2
  (extend '(a b) '(1 2)
    (extend '(x y z) '(10 20 30)
      (extend '(p q r s t) '(6 2 9 0 5) empty-env))))

(frame-index 'b env2) → 0
(frame-index 'x env2) → 1
(frame-index 's env2) → 2
(frame-index 'p env2) → 2
(frame-index 'z env2) → 1

Turning in Your Homework