Lambda the Ultimate

The grace and dart guys were talking about this recently. In the worst case, control dependent typing seems workable. Their solutions were more structured: they restrict the language of initializers and what can be done in a constructor (which may lead to programming an additional post-construction init method, where type state becomes relevant). Staging also helps as it provides better perf control to programmers.

A language I worked on over the summer at Adobe is (last I knew) going to have two-part constructors like you described. Use of 'this' is restricted in the first phase, to prevent leaking uninitialized state. The second phases happen in reverse order (following inheritance) and have access to 'this'.

Cool, does the system have a name?

I think the real question here isn't "how do I use types to describe canonical XYZ" but "what properties do I want for initialization" and from there, mechanism follows choice. Syntactic restrictions, APIs, types, etc. seem to be confounding the issue. For example, I believe Dart wanted the separation, in part, for reducing memory consumption by guaranteed-safe sharing across instances.

The language or model for initialization?

Virgil has three stages of construction for objects.

The first stage is initializing expressions of fields for the class of the object being allocated. This code is outside of the constructor and thus cannot access the "this" object. It can only reference other initialized fields, in initialization order. It cannot call methods on the object (since it cannot access "this") and it cannot pass "this" to another method. The second stage is the call to the super constructor's code. This stage can only contain expressions that similarly do not access "this". The third stage, the code in the constructor body, has no restrictions. The "this" object is accessible, and by this point it is guaranteed that any fields declared with initializers have been initialized. Virtual dispatch, passing "this" to outside methods, etc, is totally safe now. This three stage approach guarantees that no code can ever access an uninitialized field, even if it is called virtually from the super class's constructor. I found that this works well in practice, and establishes the invariants that are expected when writing a field initializer, with the small cost of not being allowed to access "this" in those initializing expressions.

class X {
  def f = A;
  new(h: int) {
    B;
  }
}
class Y extends X {
  def g = C;
  new(h: int) super(D) {
    E;
  }
}
Y.new(0);

In the code above, the evaluation order would be C, D, A, B, E.

You can see a bit more here.

I ended up coming up with a staged approached for my hobby language Magpie too. I wrote a bit about it here. The basic gist was that I wanted:

1. A window where you can do arbitrary calculation without having access to the object being constructed. That lets you calculate whatever you need to determine the state needed to actually create the object.
2. A window where you can do arbitrary calculation and you do have access to the object. That lets you call methods on it, send it to other places, store it in caches, etc.

And, ideally, you want both of those encapsulated with the "constructor" call so that from the outside they just ask for a new object and get a fully-initialized one back.

Dart has this in two ways. First, you have C++-style initialization lists where you can evaluate expressions to evaluate your fields. You don't have access to this and by the end of this, all final must be initialized. That ensures you can never see an uninitialized field. (I find it a bit ironic that Dart cares so much about this given that all variables are nullable in Dart anyway, so a default value is always available, but I digress.)

If "one expression per field" is too limiting, you also have "factory constructors". These look like constructors from the caller's perspective (new Foo()) but are basically static methods that do not implicitly create a new instance. Instead, you must do that yourself.

That lets you write a method that does whatever calculation up front, then creates an instance using the "real" constructor for the class and returns that.

Yes. This is probably the reference I was trying to remember.

More specifically, I'm after something that deals with the question "What is the type of a Java/C++ object while we are in the middle of constructor execution?" It isn't like constructors in ML or Haskell; these constructors perform computation. In one sense, the type of a new instance isn't stable until it's constructor has finished. But in another sense, the constructor body is free to perform operations that source or target fields of the object that is currently under construction. From a type perspective, it seems rather a bad mess.

I vaguely recall that there were a couple of papers trying to deal with issues of this nature. The CompCert work was certainly one of them. I should probably pull the paper and look at the citations.

...Qi and Myers' Masked Types for Sound Object Initialization, which deals with precisely this issue.

IIRC, their approach specializes techniques from typestate-based approaches to object initialization, with the usual tradeoff (less expressiveness versus less overhead). For a full-blown typestate system for Java, see Bierhof et al's work on Plural.

If you are designing a new initialization model, rather than trying to verify code using an existing one, I would highly recommend you take a look at Virgil's initialization rules. They are actually quite simple, give you good guarantees, are trivially statically checkable, and practical.

The paper I cited above tackles issues that do not appear in your (interesting) description of Virgil's model in the above thread. For example, in presence of multiple inheritance, you have several super constructors to call. The type of the object "evolves" between these calls in the sense that method dispatch tries to find the most precise implementation that has already been initialized. Finally, in presence of virtual inheritance (two different subobjects A and B share a common subobject X, instead of having two different copies), these super constructor calls cannot be understood independently of each other, as building A first will affect B's build in that B.X will be already constructed. Of course, there are unreasonable^Winteresting questions to be asked about the influence of initialization order, etc.

(Of course you can also question the cost/benefit ratio of multiple and virtual inheritance, and prefer simpler object systems that allow simpler initialization models. But if the question is to understand the subtleties of object interface evolution during initialization, I suspect studying a language with this rich features will provide you with stronger insights and force your design into less-comfortable, yet useful, areas.)

Sure, Jonathan was after the papers you cited, but it was my supposition based on his prior work on BitC that he was interesting in new design alternatives. Those references represent advancements in applying a lot of powerful static analyses to what I consider an unfortunate, avoidable problem. In that vein I think that the contortions one has to go through with applying advanced type systems and analyses to make some sense of the disaster that is C++ should at best serve as a warning post to others. I think venturing further down those paths isn't likely to be as useful as it may seem, and simpler solutions are already available. Virgil may not be particularly interesting in that academic sense, but I thought I'd at least mention it.