On this page:
1.6.1 Efficiency
1.6.2 The Bitdiddle Algorithm
1.6.3 Application

1.6 Substitution

Complete this assignment with Team One.

1.6.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, implementing the cache using a simple stack of bindings (like we have) doesn’t seem very much more efficient because it still requires linear searching of the stack of bindings every time we encounter an identifier.

Answer the following two questions.
  • Provide a basic structure for a program (similar in style to the one we talked about 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) justify 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.

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

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