Monday, July 25, 2011

Deconstructing Construction

Construction Semantics

Construction in many OO languages, including Java (and Scala), still mystifies me. First you have nothing, then you have something... but in between, you have neither nothing nor something, or at least not a properly initialized something. “Properly initialized”, in this context, means that all the immutable parts of the object you're creating (its final variables, in Javaspeak) have been given their final values. I know I'm not the only one foolish enough to have inadvertently written a Java constructor that passed the object under construction to code that observed the object's final variables in their default state—the null or zero to which Java sets final variables before they're assigned. It would be nice if there were some mechanism that could prevent me from sabotaging myself like this.

By contrast with Java, in Haskell (if my limited knowledge is accurate), there is no in-between when you invoke a data constructor; the arguments to the constructor are instantaneously wrapped in the result, and the constructor does nothing else. The price for this simplicity is that the constructed value exposes just the values used in its creation, neither more nor less; OO languages are more flexible in that they let you hide (or forget) the values passed to the constructor, and instead expose other values derived from the constructor values—the constructed object has complete control over how it appears to the outside world.

For convenience, let's name the types of constructor semantics I've mentioned above:

  • Regular semantics are those of Java: construction is nonatomic, and it's possible to observe uninitialized final variables as nulls or zeros.
  • Diet semantics are the simpler semantics of Haskell: construction is atomic, and does nothing but wrap the constructor arguments in the result.
  • New minty-fresh semantics are like those of Java, except that you can never observe a final variable in its uninitialized state.

Bonus Track: Factory Methods

While we're here, it would be nice to have a better handle on the relationship between constructors and factory methods. Java enforces the view that constructors and factory methods are entirely different by requiring different syntax to invoke them. You can wrap a constructor in a factory method, but not vice versa (see my previous whine). Can we imagine a world without this constraint, or if not, at least clarify why the constraint is necessary?

A Brief and Maybe Totally Wrong History of Constructors

As far as I know, earlier OO languages didn't worry much about the consistency of object construction. Smalltalk doesn't have (except by convention) constructors as distinct from ordinary methods. The default built-in class method new allocates an uninitialized object, and you're free to wrap new in any method you like, or not. Smalltalk also lacks built-in immutability, although it gives you the information-hiding tools to hide variables behind accessors, if you like.

The first language I can recall with detailed rules for construction was C++, whose constructors are distinct from regular methods. C++ requires that you initialize an object with a constructor, and that you call superclass constructors before subclass constructors. These rules avoid some conceptual inconsistencies, but since C++ is not a particularly safe language in general, are hardly sufficient to keep you out of trouble.

Java adds rules for constructing final variables to constructor rules that are similar to C++'s. In Java, you call new followed by the name of the class you're allocating, along with the arguments from which the correct constructor can be deduced. At the JVM level, this does two things: executes a new instruction (which is invisible at the language level), and then passes the result to the constructor proper, which looks to the VM like a method named <init>.

I'm too ignorant and lazy to figure out whether I've omitted important details about constructors here or gotten my history wrong, but as usual, Wikipedia will set you straight if I've steered you wrong.

The Sun Always Shines in My Imaginary Little World

So where are we going with all this?

I'm trying to imagine the details of an execution model that accommodates all three flavors of construction: regular, diet, and minty-fresh. I'm not saying any existing system currently does or doesn't support all three varieties, and I'm not saying I'm going to build one that does. I'd just like to figure out what such a thing would look like if it existed.

And of course I'd like it all for free. That is, construction should be as simple as possible, in terms of the numbers of concepts needed to support it, and as cheap as possible, in terms of runtime overhead. At least in my imaginary little world.

Oh Yeah, and Type Safety Too

And I'd like to be able to phrase my solution in a way that is consistent in terms of types. That is, I don't want programs to have to use casts or reflection or otherwise take heroic measures to get the various forms of constructor to work properly or typecheck correctly.

The argument to a Java constructor for a type T is nominally a T, but under the minty-fresh rules, it's not a fully valid T until the constructor completes, because you can observe uninitialized finals. The regular-flavor rules do make a halfhearted attempt to ensure that you only deal with fully constructed objects, in that you have to call superclass constructors before accessing any subclass features, but those rules aren't airtight enough to preserve the minty-fresh flavor I'm after.

One reason for leaving loopholes in the regular rules is that you'd like to be able to create immutable cyclic data structures: a partially constructed object A can pass itself to the constructor for an object B in such a way that A and B wind up with final references to each other.

class A {
final B b;
A () { this.b = new B(this); }
}
class B {
final A a;
B (A a) { this.a = a; }
}

You can imagine rules that forbid a partially constructed object from ever escaping its constructor (like the diet rules), but then there's nothing else (at least in the Java model) that would let you create a cycle of final variables. I'd like the minty-fresh rules to let you create cycles, too.

Dieting is Easy

Implementing the diet constructor rules is easy in terms of JVM semantics: any constructor that consists only of assignments from constructor arguments to final variables implements the diet rules. Because such constructors don't allow partially constructed objects to escape, the Java memory model rules regarding final instance variables ensure that no thread can ever see a partially constructed object.

So for the rest of this post, I can concentrate on the minty-fresh rules.

Construction in Terms of Types

One way to understand construction of a value of type T with arguments args might be to treat it as a function of type (T0,args) => T (apologies to anyone offended by mixing Scala and Java conventions), where T0 is a synthetic supertype of T that represents an uninitialized T—that is, it doesn't provide the features of T that depend on the constructor arguments to T.

Factory Work

Treating a constructor as an ordinary function opens the door to unifying factory methods and constructors. If you can declare a factory method that has the same signature as a constructor, then maybe there's a way to do it the other way around, and redirect construction to a factory method that returns a subtype of the type you're nominally constructing.

For Example

As an example of the above proposal, imagine treating:

class T {
private final int i;
public T (int i) { this.i = i; }
public int i () { return this.i; }
}

as (ignoring illegalities):

interface T {
T T (T0 this, int i);
int i ();
}
synthetic class T0 {
public TImpl T (/* T0 this, */ int i) {
TImpl t = (TImpl) this;
t.i = i;
return t;
}
}
synthetic class TImpl extends T0 with T {
private final int i;
public int i () { return this.i; }
}

so that new T(n) translates to (new T0).T(n).

What this accomplishes is that T0, the uninitialized version of T, doesn't declare the accessor i(). i doesn't exist yet, so you can't get in trouble by referring to it, if you somehow get hold of a T0 that has escaped its constructor.

Assumptions made include:

  • new still allocates an uninitialized version of a class.
  • A cast from the uninitialized version of a class to the full version is allowed, at least within the constructor.

The rules need more elaboration. What if T has a method that doesn't depend on its own state, like this?:

public void sayHello () { System.out.println("Hello"); }

(Functional purists, please avert your eyes from the side effect.) And what about methods that are not themselves simple accessors, but depend on them?:

public int iPlusOne () { return this.i + 1; }

Is either sayHello or iPlusOne declared in T0? And if the constructor allows a T0 t0 to escape:

  • Does a call to t0.sayHello, if declared, actually succeed?
  • What's to prevent (T) t0 outside the constructor?

But wait, there's more! What if T contains more than one final variable that needs to be initialized?:

class T {
private final int i;
private final String s;
public T (int i, String s) {
this.i = i;
escapeFromHere(this);
this.s = s;
}
public int i { return this.i; }
public String s { return this.s; }
}

All Is Not So Clear and Simple

At the call to escapeFromHere, T is partially constructed—i is valid, but s isn't. So do there now have to be multiple stages of uninitialized classes corresponding to each order in which T's final variables could be initialized, something like this?:

interface T {
T T (T0 this, int i);
int i ();
String s ();
}
synthetic class T0 {
public TImpl T (/* T0 this, */ int i, String s) {
T1 t = (T1) this;
t.i = i;
escapeFromHere(t);
return t.T1(i,s);
}
}
synthetic class T1 extends T0 {
public TImpl T1 (/* T1 this, */ int i, String s) {
TImpl t = (TImpl) this;
t.s = s;
return t;
}
}
synthetic class TImpl extends T1 with T {
private final int i;
private final String s;
public int i () { return this.i; }
public String s () { return this.s; }
}

I suppose this kind of thing is feasible, but it's starting to look unattractive.

The requirement that a cast to the full T fail on an incompletely initialized T outside the constructor is particularly vexing, because although you can munge the class pointer for the object under construction (so that the object never claims to be more initialized than it actually is), you need to ensure that the object makes this claim in every thread that can observe it—that is, you have to introduce synchronization guarantees for partial initialization of final instance variables, as well as the guarantees for full initialization provided by the JVM.

This naive typesafe approach to construction appears to be collapsing under its own weight. Can minty-fresh construction be rescued from death by a thousand implementation details? Are we doomed to stew forever in a conceptual muddle over constructors? Stay tuned.

3 comments:

  1. Howdie,

    I think I lost the root issue you're trying to solve. Is it merely that you want to protect screwing around during initialization?

    If so, perhaps we can take a look at it from another angle. Rather than /enabling/ a new construction paradigm, can we /disable/ aspects of initialization? I know boxing people in isn't generally the nicest way to go, but perhaps here it's not too bad.

    First, the compiler will disallow calls to polymorphic methods during initialization. I'm sure you know the havoc this can wreak in C++ and it's a "convention" that you shouldn't do it, but no sane person breaks that convention :) But, Zeus help you if you take a previously non-virtual function that you called from the constructor and then made it virtual some day. So, this shouldn't be a problem for anyone.

    Second, the compiler disallows the escape of "this" from the initializer. Now, this one would be more contentious, I'm sure, so we need to provide an "out" here. Why not allow for a closure that you can define during initialization that delays the "escapism" until after initialization completes (successfully)?

    Thus, the compiler catches you from shooting yourself in the (insert favourite body part here) but gives you a safe (?) alternative to do what you want.

    Was there another issue you were trying to solve? (i.e. did I miss the point? :D)

    ReplyDelete
  2. I must admit I've come at this with a specific use case in mind, and that case might not be a practical one. What I envision is being able to take existing Java code (sloppily written constructors and all) and run it through something that catches the places where you've invalidly accessed an uninitialized variable.

    The semantics I'm proposing violate the Java rules (however poorly those rules may sometimes serve us), so I doubt there's much of an audience for that particular application of minty-fresh constructors.

    You can certainly get by with stricter limits on constructors for at least some use cases. For example, instead of building a cyclic reference between classes A and B the way I did it above (allow the A to escape its constructor), you could declare A like this in Scala:

        class A { lazy ref b = new B(this) }

    which defers linking to the B instance until after A is constructed (as long as A's constructor doesn't need to refer to it), without making b mutable.

    However, I haven't convinced myself that I can cover all use cases (at least those in the OO style) under any significant restriction of constructor functionality, relative to Java. That would require thinking about everything that's reasonable to do during construction—registering an object with a service, for example—and convincing myself there's a reasonable alternative.

    Boxing people in may actually be the nicest way to go, if you give them a big enough box, and the box is empty—you have no existing code (or habits) to deal with. I'm trying for a more incremental approach here, which may show no more than my lack of vision. But I think I'll stay on this train of thought a bit longer and see where it gets me.

    ReplyDelete
  3. More power to you, dood. My only concern was that your current path seems to create another issue that needs solving as you create solutions to previous issues; as such, a different approach might be more appropriate. But your current line of reasoning certainly deserves more exhaustive thought.

    ReplyDelete