Laziness (Written)
Problem 1
Write a Java program to determine 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. One of
our sedentary students is rather taken with the idea of laziness; he
suggests we can get away with only one strictness point, at
the point of looking up identifiers. That is, he replaces
[id (v) (lookup v env)]with
[id (v) (strict (lookup v env))]
He reasons 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. And there ends
his reasoning.
Is it possible to write a program that will produce different results under the original interpreter and this modified one? You should answer this question for two languages:
- The first language supports arithmetic, first-class functions, recursive functions, and conditionals.
- The second language supports all of the features of the first language, and also supports lists.
You could, if you wanted, implement these features in an interpreter and produce those, with input programs, to justify your answer. However, you can also describe their behavior without having to implement them. Your choice.
Keep three things in mind: (1) We're using the class's definition of laziness. Haskell is a little different. (2) In a lazy language, the printer of the interactions window is also a strictness point! Assume that's true when running interpreters with the suggested modification, too. (3) It shouldn't be too hard to actually implement these two interpreters to test your intuitions.
Problem 3
Lazy languages usually don't have stateful operations such as mutating values in boxes, or assigning values to variables. Why not?
The best answer 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 indeed.
Problem 4
Consider the typing rules discussed in the textbook. These rules are for an eager language, not a lazy one. Focusing on the rules for function definition and function application, provide new rules for a lazy language. If you believe the rules won't change, explain why not. If you believe any other typing rules should change, mention those as well.
Handin
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 Racket file.
From the directory containing the files for the assignment you wish to hand in, execute
/course/cs173/bin/cs173handin laziness-writ