In the environment-based interpreter, an identifier is free (and
reported as such by
lookup) when it isn't in the current
environment. What determines whether an identifier is free under
The simple definition of substitution results in an inefficient operator: in the worst case, it can take time at least quadratic in the size of the program (where we define the program size as the number of nodes in the abstract syntax tree). An environment defers substitution but, assuming an environment is implemented as a linked list (as it is in our class version), is this any more (time-)efficient?
If it is, explain how.
If it is not: (a) give an example that shows that its worst-case time behavior is the same, and (b) suggest a data structure that will work better. Be sure to think through the consequences of choosing this data structure! (For instance, does the interpreter need to change?) You may refer to your knowledge of data structures from other languages; you don't have to limit yourself to your knowledge of Racket or of what the language seems to provide.
The Racket program
(let ((x 4)) (let ((f (lambda (y) (+ x y)))) (let ((x 5)) (f 10))))
should evaluate to 14 by static scoping. Evaluating
the environment at the point of invoking
yields a value of 15 for the program. A sharp if
eccentric student points out that we can still use the dynamic
environment, so long as we take the oldest value of
the environment rather than the newest. Is this true in general?
If it is, justify.
If it is not, provide a counterexample and explain why this strategy will produce the wrong answer. If you think this proposal is based on a conceptually wrong understanding of environments, explain.
Look up the
static scope? Argue either from reason or with counterexamples.
Our interpreter constructs a closure by closing over the whole of the current environment at the point where the closure is defined. Could it close over a smaller environment? Explain and justify.
Turn in your answer to each problem in a separate text or PDF file.