Dynamic Scope Call

Complete the given interp function to support a variant appDynE to call a function with dynamic rather lexical scope.

The following two tests contrast the lexically scoped appE with the dynamically scoped appDynE.

(module+ test
  (define (example body)
    (let1E 'x (numE 3)
           (let1E 'f (lamE 'y (plusE (varE 'x) (varE 'y)))
                  (let1E 'x (numE 5)
                         body))))

  (test (interp (example (appE (varE 'f) (numE 4))) mt-env)
        (numV 7))

  (test (interp
         (example (appDynE (varE 'f) (numE 4))) mt-env)
        (numV 9))

  (test (interp
         (example
          (let1E 'f (lamE 'x (varE 'x))
                 (appDynE (varE 'f) (numE 4))))
         mt-env)
        (numV 4))

  (test (interp
         (example
          (let1E 'f (lamE 'y (varE 'x))
                 (appDynE (varE 'f) (numE 4))))
         mt-env)
        (numV 5))

  (test (interp
         (example
          (let1E 'f (lamE 'y (varE 'x))
                 (let1E 'x (numE 3)
                        (appDynE (varE 'f) (numE 4)))))
         mt-env)
        (numV 3))

  (test/exn (interp (appE (varE 'g) (numE 4)) mt-env) "not bound")
  (test/exn (interp (example (appE (numE 4) (varE 'f))) mt-env) "function")
  (test/exn (interp (example (appDynE (numE 4) (varE 'f))) mt-env) "function")
  )

Combining GC passes

Below you are given a partial implementation of a plai/gc2 style collector for a simple heap with no freelist or bitmap in the style of Lecture 20. Unlike there, in this question you are asked to combine the phase of marking white with that of freeing any records previously marked white.

We will revisit these ideas in Lecture 23; you may find it helpful to read ahead.

Complete the function free/mark-white! so that the given tests pass.

Note:

You do not have to write the whole collector here, just the “sweep” part of a mark-and-sweep.
The code from Lecture 23 will not work directly due to a different heap representation.

(module+ test
  (with-heap (make-vector 7 '?)
    (init-allocator)
    (test (current-heap) (make-vector 7 'free))
    (gc:alloc-flat 'first)
    (test (current-heap) #(flat first free free free free free))
    (gc:alloc-flat 'rest)
    (test (current-heap) #(flat first flat rest free free free))
    (gc:cons 0 2)
    (test (current-heap) #(flat first flat rest cons 0 2))
    (free/mark-white!)
    (test (current-heap) #(white-flat first white-flat rest white-cons 0 2))
    (free/mark-white!)
    (test (current-heap)  (make-vector 7 'free))
    (gc:alloc-flat 'first)
    (gc:alloc-flat 'rest)
    (gc:cons 0 2)
    (free/mark-white!)
    (test (current-heap) #(white-flat first white-flat rest white-cons 0 2))
    )

  (with-heap  (vector 'flat 'first 'flat 'rest 'white-cons 0 2)
    (free/mark-white!)
    (test (current-heap) #(white-flat first white-flat rest free free free))
    (heap-set! 0 'flat)
    (free/mark-white!)
    (test (current-heap) #(white-flat first free free free free free)))

  (with-heap (make-vector 5 #f)
    (init-allocator)
    (gc:cons 0 0)
    (test (current-heap) #(cons 0 0 free free))
    (malloc 2)
    (test/exn (malloc 100) "out of memory")
    (heap-set! 0 'fail)
    (test/exn (malloc 2) "unexpected tag"))
  )