Principles of Programming Languages — Homework 8

Due by class time Tuesday, October 8

Reading

Review this week's code examples from class.

Exercises

For these exercises, download the file assign8.scm and use it as your starting point. There is also a tester program available. To use the tester program, download hw8-tester.scm (and auto-tester-base.scm if you don't already have it), and put them in the same place as assign8.scm.

  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? Try out the examples below in the interpreter to see:

    (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) '(1 2 3)
    (extend '(x y) '(10 20) empty-env)))

env1 → ((a 1) (b 2) (c 3) (x 10) (y 20))
    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 like (a b c) and a corresponding list of values like (1 2 3). So a single frame would be a list like ((a b c) (1 2 3)). Replace the extend function included in assign8.scm (which is the version that we wrote in class) 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 using the new version of extend will now build a list containing two frames as shown below. The first frame is highlighted in red and the second frame in blue (just match up the parentheses carefully): 
    env1 → (((a b c) (1 2 3)) ((x y) (10 20)))

    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) → (1 2 3)

  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:

    env1 → (((a b c) (1 2 3)) ((x y) (10 20)))

(lookup 'c env1) → 3
(lookup 'a env1) → 1
(lookup 'x env1) → 10
(lookup 'y env1) → 20

  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. For example, in the environment env2 below, b is a member of the first frame, so its frame index is 0, x is a member of the second frame, so its frame index is 1, and s is a member of the third frame, so its frame index is 2. Use your helper functions to improve the readability of your code. 

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

env2 → (((a b) (1 2)) ((x y z) (10 20 30)) ((p q r s t) (6 2 9 0 5)))

(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