Assignment 11, due Nov 17Solutions
Part of
the homework for CS:2820, Fall 2017
|
public class Lazy {
public static interface Int {
int eval();
}
public static Int add( Int i, Int j ) { return ()->i.eval() + j.eval(); }
public static Int term( int i ) { return ()->i; }
public static void main(String[] args) { // 1
Int i = term( 1 ); // 2
Int j = term( 0 ); // 3
for (int x = 0; x < 5; x++) { // 4
Int k = j; // 5
j = i; // 6
i = add( j, k ); // 7
System.out.println( "gets " + k.eval() ); // 8
} // 9
} //10
}
This code has been tested. It works. It is obvious that the add method is called exactly 5 times by the above loop, once for each execution of line 7 in the code.
a) The integer add operation inside the lambda expression in the add method is performed a different number of times by this code. How many? (Hint: You can get the answer from understanding Java and lambda expressions, or you can rewrite the code to count the additions.) (0.5 points)
Theory and practice agree: There are 7 integer additions.
My initial careless guess was that there would be 10, that is 0 + 1 + 2 + 3 + 4, but my empirical test showed me that I was wrong, leading me to rethink my understanding of the code.
My empirical test used an alternative version of the add function; this prints out add each time it computes the sum of two integers, using a little integer add function called ad to do so:
public static int ad( int i, int j ) {
System.out.println( "add" );
return i + j;
}
public static Int add( Int i, Int j ) { return ()->ad( i.eval(), j.eval() ); }
Run the above, and you get:
gets 0 gets 1 add gets 1 add add gets 2 add add add add gets 3
b) Which line of the above code actually causes the integer additions discussed in part a) to be performed. (0.5 points)
All the actual additions are done by calls to eval triggered by line 8 in the original code.
By way of added explanation, on the first and second iterations, the initial values of j and then i are printed. The calls to eval for these values involve initial term values and no arithmetic.
After the second iteration, each call to eval uses a number of additions that is one plus the sum of the number of additions on the previous two iterations. Note that the final call to add produced a value to which eval is never applied, so the additions latent in the final value are never done.
c) Look up lazy evaluation in Wikipedia. The code given above emboies one of the key properties of lazy evaluation defined there, but not the other. Which property has it missed (what you learned in the first parts of this question are relevant).
The first sentence of the Wikipedia article defines lazy evaluation as "an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing)."
The code given above has the first property, but not the second. As demonstrated in parts a and b, it does numerous repeated evaluations.
It is a fun exercise to rewrite the code so that it also avoids unnecessary re-evaluations of expressions that were previously evaluated. A version of add that fully satisfies the definition of lazy evaluation takes about 11 lines of well-formatted Java code incorporating 2 field declarations and 3 executable statements.
(Hint: In this question, focus on the nature of the activity being scheduled, that is, the body of the Lambda expression or trigger method. Also note that none of the code in the simulations we've written creates one of the counterexamples that are the subject here.)
a) Can any call to Simulation.schedule written in the old framework be rewritten as a single call to Simulation.schedule in the new one? If not, provide a counterexample. (0.5 points)
Yes, trivially. The form of λ expression used in the old framework had just one expression as its body, and this expression can trivially be used as a statement, the body of the trigger method in the new framework.
b) Can any call to Simulation.schedule written in the new framework be rewritten as a single call to Simulation.schedule in the old one? If not, provide a counterexample. (0.5 points)
The body of the trigger method in the new framework can be an arbitrary sequence of statements.
void entryEvent( float t ) {
Simulator.schedule(
new Simulator.Event( t + travelTime ) {
void trigger() {
Do.something( time );
And.do( time ).somethingElse();
}
}
);
}
The above cannot be rewritten in this form:
void entryEvent( float t ) {
Simulator.schedule(
t+travelTime,
(float time)->ThisIs.justOneMethodCall( time )
);
}
But see below!
c) Rewrite any counterexamples you came up with so that they work under the framework where they couldn't be written as a single call to Simulation.schedule under the other framework. (Big hint, two calls might suffice, or perhaps new method is needed.) (0.5 points)
Here is the first of several possible rewrites:
class ThisIs {
static void justOneMethodCall( float time ) {
Do.something( time );
And.do( time ).somethingElse();
}
}
void entryEvent( float t ) {
Simulator.schedule(
t+travelTime,
(float time)->ThisIs.justOneMethodCall( time )
);
}
The above solution requires learning no new features of Java, it is based entirely on the limited subset of Java we have used in lectures up to this point.
A student pointed out that Java λ expressions allow a more general form than we have been using. It is legal to write this:
void entryEvent( float t ) {
Simulator.schedule(
t+travelTime,
(float time)->{
Do.something( time );
And.do( time ).somethingElse();
}
);
}
Anyone who pointed out this possibility should get full credit, despite the fact that this more complex version of λ notation is not something we have discussed.