Assignment 12, due Dec 1Solutions
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) {
Int i = term( 1 );
Int j = term( 0 );
for (int x = 0; x < 5; x++) {
Int k = j;
j = i;
i = add( j, k );
System.out.println( "gets " + k.eval() );
}
}
}
As stated then, this code works, but it is too lazy. Although there are only 5 calls to add, the body of the λ expression inside add is evaluated 7 times, and the number of extra evaluations grows exponentially with each successive iteration of the loop in the main method.
The problem is that the code given above embodies only one of the two key properties of lazy evaluation. It defers computation until need, but it retains no copy of the values it computes, so if the same lazy Int object is eval'd twice, all the computations are repeated because the object retains no copy of the sum it already computed.
A problem: Write a new version of add that fixes this and completely matches the full definition of lazyness. (1 point)
Hint: You can't do it with lambda expressions. You'll have to explicitly return a new object of an appropriate implementation of the Int interface, where that new object has a field it can use to remember its value.
public static Int add( Int i, Int j ) {
return new Int() {
int val; // the value of this Int, if defined.
boolean valUnd = true; // is the value undefined?
public int eval() {
if (valUnd) {
val = i.eval() + j.eval();
valUnd = false;
}
return val;
}
};
}
Just for fun, substitute the above into the original program and count the number of integer additions. You get exactly one addition per iteration after the first two iterations.
A problem: What variables referenced inside this method require some kind of solution to the up-level addressing problem? (0.5 points)
public static Int add( Int i, Int j ) {
return new Int() {
public int eval() {
return i.eval() + j.eval();
}
};
}
A problem: Translate the version of add given above to one that uses an explicitly named outer class instead of an inner class. Note, the program is small enough that you can easily test your work. (0.5 points)
public static Int add( Int i, Int j ) {
static class AddInt extends Int {
public int eval() {
return i.eval() + j.eval();
}
}
return new AddInt();
}
The last step is to move the inner class to an outer class:
static class AddInt extends Int {
Int i; // copies of up-level addressed variables
Int j;
public AddInt( Int i, Int j ) { // constructor to initialize copies
this.i = i;
this.j = j;
}
public int eval() {
return i.eval() + j.eval();
}
}
public static Int add( Int i, Int j ) {
return new AddInt( i, j ); // make copies of up-level addressed variables
}
RoadNetwork.class: classes $(JavaSourceFiles) javac @classes
This misses out on the opportunity to document the inter-file dependencies in our application. In fact, we could have written this:
mainSupport = ScanSupport.class Errors.class Simulator.class RoadNetwork.class: RoadNetwork.java Road.class Intersection.class $(mainSupport) javac RoadNetwork.java
That is, we document all the other classes on which class RoadNetwork depends by referencing their .class files. If we do this throughout, the makefile becomes comprehensive documentation of the relationships between all the classes in the program.
a) Give an appropriate makefile entry for class ScanSupport. (0.5 points)
Once we do this, we know that the following line in the Makefile should suffice:
ScanSupport.class: ScanSupport.java Errors.class javac ScanSupport.java
b) Give an appropriate makefile entry for class Road. (0.5 points)
[dwjones@serv16 ~/AAA]$ make clean rm -f *.class *.html package-list script.js stylesheet.css [dwjones@serv16 ~/AAA]$ javac Road.java [dwjones@serv16 ~/AAA]$ ls *.class Errors.class Simulator.class Intersection.class 'Simulator$Event.class' 'Intersection$ConstructorFailure.class' Sink.class 'NoStop$1.class' 'Source$1.class' 'NoStop$2.class' 'Source$2.class' NoStop.class 'Source$3.class' PRNG.class Source.class 'Road$1.class' 'StopLight$1.class' Road.class 'StopLight$2.class' 'Road$ConstructorFailure.class' 'StopLight$3.class' RoadNetwork.class 'StopLight$4.class' ScanSupport.class 'StopLight$5.class' 'ScanSupport$Message.class' StopLight.class 'ScanSupport$NotFound.class'
This is too cluttered with automatically generated .class files for all of the inner classes, but a bit of work with regular expressions cleans them out:
[dwjones@serv16 ~/AAA]$ ls *.class | grep '^[^$]*$' Errors.class Intersection.class NoStop.class PRNG.class Road.class RoadNetwork.class ScanSupport.class Simulator.class Sink.class Source.class StopLight.class
To avoid long lines, I grouped them into sensible categories in my solution, and I only mentioned the main .class file for Intersection since the subclasses of Intersection are all the result of compiling Intersection.java:
roadSupport = Errors.class ScanSupport.class PRNG.class Simulator.class Road.class: Road.java RoadNetwork.class Intersection.class $(roadSupport) javac Road.java
As an afterword, you might wonder why bother using a makefile to do this, since the Java compiler automatically finds all the files on which something depends and compiles them for you.
There are several answers: First, the compiler always recompiles everything if you use an @classes file, while make will be selective. Second, while Java can find dependencies automatically, it doesn't document them for you, nor does it offer you a convenient place to comment the dependencies. Third, make can handle building applications that have parts written in other languages or where a preprocessor is used to automatically generate some part of a Java program.