26. How nesting works in Java

Part of CS:2820 Object Oriented Software Development Notes, Spring 2017
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

Introduction

A few lectures back, we introduced this improved simulation framework that avoided using lambda expressions.

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?

Activation Records

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, the method discussed above, creates 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.

Constructors are really just methods that create, operate on and return a new object. Inline initialization of fields of a class and anonymous constructor code is just another constructor that is called as a prefix to every explicit constructor. When one class extends another, the anonymous constructor for the new class begins by calling the anonymous constructor for the parent class.

You can think of parameter passing as assignment to the parameter after the activation record is created but before the body of the method is called.

Inside the CPU

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 instruction. 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.

Uplinks

Using the Algol 60 model of nested blocks, 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 in languages such as C++ and Java, the uplink from within a method has a special name, this.

For inner classes, the Algol-60 model requires that each object that is a member of an inner class hold an uplink that refers to the enclosing block (either an outer class or a method of some outer class). Simula 67, the first object-oriented language did this. When an object of a non-static inner class is created, the uplink for that object gives it access to the enclosing activation record (if the inner class is local to a method) or to the enclosing object (if the inner class is defined in an outer class, as is the case with class Event inside class Simulator. This chain of uplinks links the activation records or objects up through each level of nested curly braces ({ and }) out to the outer nesting level of the program.

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 up.x, following the uplink up a level. If that does not work, it looks up two levels for up.up.x, 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, up.up.a and up.up.b good compilers will create a temporary, for example, t=up.up, and then reference t.a and t.b.

Devolution from Algol 60 to Java

Java is descended from Algol 60:

How Java Handles Up-Level Addressing

Java documentation offers few clues to how Java handles up-level addressing, so we have to infer what's going on.

From within an inner class or lambda expression, Java permits access to static variables in enclosing blocks (objects or activation records). This is easy to implement because static variables are assigned fixed global memory addresses so there is never any need for a chain of uplinks to access them.

All other variables referenced from an inner class and defined in an outer nesting level are required to be final or "effectively final". What's going on? Let's look at the example we gave above:

    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 ); }
            }
        );
    }

First, let's rewrite this code to de-anonymize the inner class, making it clear that this code really does use an inner class:

    void entryEvent( float t ) {
        // A vehicle arrives at the road entrance at time t

        class E extends Simulator.Event {
            E( float t ) { super( t ); }
            void trigger() { Road.this.exitEvent( time ); }
        }

        Simulator.schedule( new E( t + travelTime ) );
    }

Recall that inner classes in Java are really an afterthought. This means that they were cobbled onto an existing foundation that did not support inner classes. If you try to rewrite the above code without inner classes, you have to add a parameter to the constructor for the class E:

class E extends Simulator.Event {
    Road roadDotThis;

    E( float t, Road r ) { super( t ); roadDotThis = r; }

    void trigger() { roadDotThis.exitEvent( time ); }
}

... // later on, inside class Road:

    void entryEvent( float t ) {
        // A vehicle arrives at the road entrance at time t

        Simulator.schedule( new E( t + travelTime, Road.this ) );
    }

The above code is exactly the code generated by the Java compiler when it sees the inner class (whether it is anonymous or not). When you look at the object files generated by the Java compiler, in addition to finding Road.class holding the compiled version of class Road, you also find classes with names like 'Road$1.class'. These classes hold the object code for inner classes, with the prefix (before the $) being the outer class where the inner class was declared, and the suffix being either the name of the inner class, if it was named, or a number for anonymous inner classes.

For every non-static variable referenced from within the inner class but declared at an outer nesting level, there will be an extra field of the object holding the value of that variable, and the constructor for the inner class will take, as a parameter, the value of that field.

The designers of Java didn't want to document this kluge (a word worth looking up). So, they hid it behind the semantic restriction that non-static variables declared outside an inner class may only be referenced from within that class if they are "final or effectively final."

The general solution using uplinks allows references to outer variables that change after an instance of the inner class is constructed. Java's solution makes copies of the values, so changes made outside the object of an inner class will not be visible to the inner class, and changes made inside the inner class will not be visible from outside. By requiring that the variable be final or effectively final, Java prevents any changes, and therefore guarantees that programmers will never need to know that a copy was made.

Another benefit of Java's scheme is that it allows all activation records to be allocated on a stack. That is, it guarantees that no object will contain links to the activation record after the method returns. Note that a method can contain the definition of an inner class that references variables local to that method. As a result, if the method returns an object of this inner class, uplinks from that object to the method's activation record will force the activation record to be retained. Java's scheme allows immediate reclamation of activation records after each return from a method. Here is an example that illustrates this:

public class Lazy { // a demonstration of lazy evaluation in Java

    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) { // compute the Fibonacci numbers
        Int i = term( 1 );
        Int j = term( 0 );
        for (int x = 0; x < 5; x++) {
            Int k = j;
            j = i;
            i = add( j, k ); // this is lazy, addition is deferred until eval
            System.out.println( "gets " + k.eval() );
        }
    }
}

The add and term methods above return objects that, if implemented with uplinks, would require retention of their activation records. As implemented in Java, these activation records need not be retained after the methods return.

Object-oriented languages have been implemented without stacks. This requires that all activation records be allocated on the heap by a mechanism equivalent to the new operator used to create new objects. With modern heap managers, this can be surprisingly efficient, but it is always more expensive than using a simple stack. With a stack, the deallocation of an activation record on return from a method is almost free, while with a heap manager, activation records are only deallocated when the garbage collector determines that there are no surviving references to that activation record from any object.

Sub Classes

If up-level addressing is done using uplinks, objects of an inner sub-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 only 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 inner class must be final or effectively final eliminates these uplinks at the cost of making local copies of the non-local variables. 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.