36. How nesting works in Java
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2015
|
In the last lecture, we introduced this simulation framework.
class Simulator {
/** Users create subclasses of event to schedule anything
*/
public static abstract class Event {
protected final float time; // the time of this event
public Event( float t ) {
time = t; // initializer
}
abstract void trigger(); // what to do at that time
}
...
The entryEvent method of class Road in our road-network simulator ended up coded like this, using an anonymous subclass of Simulator.Event to give a concrete implementation of the trigger() method.
void entryEvent( float t ) {
// A vehicle arrives at the road entrance at time t
Simulator.schedule(
new Simulator.Event( t + travelTime ) {
void trigger() {
Road.this.exitEvent( time );
}
}
);
}
The big question is how does this actually work?
Nested scope rules were invented by the developers of the Algol 60 programming language, during the period from 1958 to 1960. At first, it was not at all clear how this could be implemented. The first successful compiler for Algol 60 was written in Holland by Edsger W. Dijkstra in 1960, although Edgar Irons in the United States came in a close second. These compiler writers figured out the basic solution to how to implement programming languages with nested block structures.
Here, we'll focus on variables. Any attributes that the compiler can compute statically is a different issue, but variables are inherently dynamic.
The first issue is local variables. In any block of code, there is some object that is the most local scope. This may be an object, for example, an instance of an anonymous subclass of Event above, or it may be the block of memory representing the call to a method, for example, a call to entryEvent. In effect, each method has an associated class that holds the local variables for that method. Calling the method allocates an object of that class. We'll call this object an activation record.
So, for example, you can imagine that each call to entryEvent creates and then discards a new object of this class:
class EntryEventAR {
float t; -- the parameter
}
There are typically other fields for the anonymous variables used in the code. Note that if you call f(g(i),h(j)) what really happens is first a call t1=g(i), then a call t2=h(j), and finally the call f(t1,t2). The temporary variables t1 and t2 must exist whether they are explicitly named or not, and these temporary variables are part of the activation record.
Inside the CPU, the minimum number of registers, that is, variables that the CPU uses to execute programs, is on the order of 4.
We need a program counter, that is a register that holds the address of the next instruction in the program. Each time the program executes an instruction, this register is incremented to point to the next. When the program reaches the end of a loop, this register is adjusted to point back to the start of the loop, and so on.
When the computer executes a call, the current value of the program counter must be saved somewhere so that it can be recovered when the called code returns. As a result, the activation record for any block of code typically includes a location used to save and resture the program counter.
We need an activation record pointer, that is, the address of the block of memory holding the current activation record. When a call is executed, this must be saved somewhere, and then a new block of memory must be allocated to hold the activation record of the called routine. On return, that block of memory is abandoned.
And, of course, we need at least 2 operand registers, one of which can hold the result of the most recent operation.
Real machines do this with different register structures. For example, a program counter, a stack pointer, and two operand registers, or a program counter, a memory address register, a memory data register, and an operand register, but the minimum register count is almost always on the order of 4 registers.
When a block of code is entered, there is always an implicit parameter to that block, the uplink pointing to the activation record for the block that textually surrounds that block. So, when someone calls a method of an object, an activation record for that method is allocated, but also, a pointer to the object is passed. In the context of method calls, Java names the uplink this. When the object itself is created, if the object is a member of a non-static member of an inner class, the object itself has an uplink that holds the value of this for the instance of the outer class that it is nested within.
When a programmer writes x, the compiler first tries to find a declaration of x in the current block. That is, it looks for a local variable or local class declaration with that name. If it does not find it, the next step is to try this.x, following the uplink up a level. If that does not work, it looks up two levels, and so on.
Note that this search is done at compile time; that is, it is done just once. At run time, the code generated will just use the appropriate number of links on the uplink-chain to get to the variable. Furthermore, good compilers can optomize. If there are two different variable references, for example, uplink.uplink.a and uplink.uplink.b, good compilers will create a temporary, for example, t=uplink.uplink, and then reference t.a and t.b.
When you declare a sub-class, objects of this class will have two uplinks! One uplink, known only to the code of methods in the parent class, points to the context in which the parent class was declared, while the other uplink, known to the code in the methods of the child class, points to the context in which the child was declared.
Java's strange and poorly documented restriction that non-local variables referenced from inside an anonymous subclass must be final or effectively final appears to be an attempt to minimize the cost of these uplinks. The problem is, an uplink to an activation record from within an object is expensive because it prevents that activation record from being allocated on a stack. The activation record must be allocated on the heap, with its deallocation deferred until the object that references it is no-longer reachable. Heap allocation is much slower than stack allocation, so any trick that allows stack allocation will lead to faster performance.
By requiring that variables be final or effectively final, I speculate that this allows a copy of the non-local variable can be made when the instance of the anonymous subclass is created. By keeping these copies, the need for the uplink is eliminated, and this, in turn, allows the activation record to be stacked.