Written Assignment 1

Answer both of the following problems. (You and your partner should each understand the answers to both problems, so don't just do one each.) Even though this assignment is not all code, please submit it via email in the usual fashion.

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 delaying substitution using a cache. However, as we discussed in class, implementing the environment using a linked list doesn’t seem very much more efficient.

Answer the following two questions.

1. Provide an example program that illustrates the performance problem with the linked-list implementation of environments. Explain briefly why the execution time for this example is non-linear in its size, and describe what its worst-case time complexity is.
2. Describe a data structure for an environment 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 Java, say. However, the responsibility for providing a clear enough description lies on you. Remember that simple code is often the clearest form of 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.)