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