3.7 Substitution
Complete this assignment with Team One.
You must submit this in an archive named "wsubst.zip". This archive must contain a folder named "wsubst". This folder must contain all the files specified below. You must attach "wsubst.zip" to an email whose subject is "BYU - Fall 2010 - CS 330 - wsubst" and whose message body contains the name of everyone on your team (each on a separate line.) You must send this email to jay@cs.byu.edu before 5pm (Provo time) on 9/28. Ensure that what you are satisfied with what you submit, because only your chronologically first submission will be graded. Ensure that you follow these instructions exactly, since submissions that do not meet these requirements (i.e. do not have the correct format) will receive no credit, despite the time and energy you put into the assignment. Please see Turn In Policy for more information.
You must submit this in a file named "wsubst.pdf".
3.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 Racket 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.
3.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.)
3.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.