Laziness (Written)

Complete this assignment with the same team you worked with for Substitution (Written). You and your partner must each understand the answers to all the problems, so don't just split up the work.

Problem 1

Write a Java program which demonstrates whether Java is eager or lazy. 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, if not shorter.)

You must turn in both the source code to your program (in printed or written form) as well as an answer to the question of whether Java is eager or lazy, and an explanation of 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 one 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.

Problem 2

In our lazy interpreter, we identified three points in the language where we need to force evaluation of expression closures (by invoking strict): the function position of an application, the test expression of a conditional, and arithmetic primitives. Doug Oord, a fairly sedentary student, is rather taken with the idea of laziness. He suggests that we can reduce the amount of code we need to write by replacing all invocations of strict with just one. In the interpreter from class, he removes all instances of strict and replaces

 [id (v) (lookup v env)] 
 [id (v) (strict (lookup v env))] 

Doug's reasoning is that the only time the interpreter returns an expression closure is on looking up an identifier in the environment. If we force its evaluation right away, we can be sure no other part of the interpreter will get an expression closure, so removing those other invocations of strict will do no harm. Being lazy himself, however, Doug doesn't bother to figure out whether this will result in an overly eager interpreter.

Is it possible to write a program that will produce different results under the original interpreter and Doug's? You should answer this question for two languages:

  1. The first language supports arithmetic, first-class functions, with, if0, and rec (even though these are not in our in-class lazy interpreter).
  2. The second language supports all of the features of the first language, and also supports cons, first, and rest.

If it's possible, hand in two interpreters (one with the strictness points used by the class interpreter, and another with Doug's strictness point), an example program, and the result under each interpreter. Make sure to clearly identify which interpreter will produce each result.

If it's not possible, prove (by cases and induction) why such a counterexample cannot exist.

Be sure to compare this behavior against that of the lazy interpreter of the sort we've written in class rather than the behavior of Haskell! Also, keep in mind that the REPL is always a strictness point. If you were running your lazy interpreter from DrScheme, you would type the following into the interactions pane:

> (strict (interp '{...} (mtSub)))

Note: it should not be difficult to construct test interpreters from your solution to the Extended Interpreter assignment and the code we give you in the textbook.

Problem 3

It is virtually unheard of for a lazy language to have state operations (such as mutating the values in boxes, or assigning values to variables). Why is this so?

The best answer to this question would include two things: a short program (which we assume will evaluate in a lazy regime) that uses state, and a brief explanation of what problem the execution of this program illustrates. Please be sure to use the non-caching (ie, original) notion of laziness. If you present a sufficiently illustrative example (which needn't be very long!), your explanation can be quite short.


Turn in your answer to each problem in a separate text or PDF file. If you hand in any interpreters, include each one in a separate, clearly-labeled Scheme file.