You must complete this assignment with a partner. You and your partner should each understand the answers to both problems, so don't just do one each.

Substitution (Written)

Problem 1

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.

Answer the following two questions.

  1. Provide a schema 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. Explain briefly why its execution time is non-linear in its size.
  2. 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.

Problem 2

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