Brown Computer Science: cs173, Programming Languages, Fall 2002: Assignment 1

This assignment has two unrelated problems. The first strengthens your understanding of eagerness and laziness, while the second deals with a question we left open in class. We will post instructions on the newsgroup on how to turn in the individual files.

Problem 1

Is Java eager or lazy?

Write a Java program to determine the answer to this question. The same program, run under the two different regimes, should produce different results. You may use any Java features you want, but keep your program relatively short — we will penalize you for programs we consider excessively long or obfuscatory. (Tip: It's possible to solve this problem with a program no more than a few dozen lines long.)

You must turn in your program (as a single Java source file). You must also turn in a document (in either text or PDF formats) that answers the question of whether Java is eager or lazy, and how your program determines this. That is, you should provide a brief and unambiguous answer (e.g., ``Java is lazy'') followed by a description of what result would obtain under each regime, along with a brief explanation of why that regime would generate that result.

In general, it would be a good idea to discuss your plan of attack with the course staff. This will help you avoid falling into a trap of measuring the wrong entity, and will improve your understanding of eagerness and laziness. (Remember to email the class list or ask during office hours — don't post to the newsgroup!)

Problem 2

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 cache using a stack doesn't seem very much more efficient.

Answer the following two questions. Submit your answers as either a text or PDF document.

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

	cs173: Assignment 1
This assignment has two unrelated problems. The first strengthens your understanding of eagerness and laziness, while the second deals with a question we left open in class. We will post instructions on the newsgroup on how to turn in the individual files. Problem 1 Is Java eager or lazy? Write a Java program to determine the answer to this question. The same program, run under the two different regimes, should produce different results. You may use any Java features you want, but keep your program relatively short — we will penalize you for programs we consider excessively long or obfuscatory. (Tip: It's possible to solve this problem with a program no more than a few dozen lines long.) You must turn in your program (as a single Java source file). You must also turn in a document (in either text or PDF formats) that answers the question of whether Java is eager or lazy, and how your program determines this. That is, you should provide a brief and unambiguous answer (e.g., ``Java is lazy'') followed by a description of what result would obtain under each regime, along with a brief explanation of why that regime would generate that result. In general, it would be a good idea to discuss your plan of attack with the course staff. This will help you avoid falling into a trap of measuring the wrong entity, and will improve your understanding of eagerness and laziness. (Remember to email the class list or ask during office hours — don't post to the newsgroup!) Problem 2 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 cache using a stack doesn't seem very much more efficient. Answer the following two questions. Submit your answers as either a text or PDF document. 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. 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 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.

cs173: Assignment 1

Problem 1

Problem 2