2.7 Substitution
Complete this assignment with Team One.
You must submit this in an archive named "wsubst.zip".
You must submit this in a file named "wsubst.pdf".
2.7.1 Efficiency
We have discussed how the 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 can define the program size as the number of nodes in the abstract syntax tree). We talked about deferring substitution using a cache. However, as we discussed in class, implementing the cache using a simple stack of bindings doesn’t seem very much more efficient.
Provide a template for a program (similar in style to the one we saw in class for the non-linearity of substitution) that illustrates the non-linearity of the stack-based cache implementation. (For example, you could give an informal specification that can be used to generate a program for any number n.) Explain briefly why its execution time is non-linear in its size.
Describe a data structure for a substitution cache that a FWAE interpreter can use to improve its complexity, and show how the interpreter should use it (if the interpreter must change to accommodate your data structure, describe these changes by providing a pseudocode version of the new interpreter). State the new complexity of the interpreter, and (informally but rigorously) prove it. You don’t need to restrict yourself to the subset of Scheme we are using in this course; you may employ all your knowledge of, say, Java. However, the responsibility for providing a clear enough description lies on you. Remember that simple code is often the clearest description.
2.7.2 The Bitdiddle Algorithm
The program
| {with {x 4} |
| {with {f {fun {y} {+ x y}}} |
| {with {x 5} |
| {f 10}}}} |
should evaluate to 14 by static scoping. Evaluating x in the environment at the point of invoking f, however, yields a value of 15 for the program. Ben Bitdiddle, a sharp if eccentric student, points out that we can still use the dynamic environment, so long as we take the oldest value of x in the environment rather than the newest and for this example, he’s right!
Is Ben right in general? If so, justify. If not, provide a counterexample program and explain why Ben’s evaluation strategy would produce the wrong answer. (A bonus point for explaining why Ben’s way of thinking about environments is conceptually wrong, irrespective of whether or not it produces the right answer.)
2.7.3 Application
In 850 words or less, describe if and how your knowledge of first-class functions will help you in your future programming practice. Good answers might discuss how this concept can be applied in interesting programming environments or how knowledge of its subtleties clarifies or improves existing practices, techniques, tools, etc.