The Y Conspiracy

Some phenomena are so outlandish that to explain them seems to require a conspiracy by the powerful.

For example, consider the modern computer chip. Is it really believable that a tiny piece of slightly adulterated silicon can, when an electric current is passed through it, compute millions of digits of pi? Well, maybe you can swallow the pi, but doesn't it burst the bounds of credulity to accept that it can also show you videos of cute kittens dancing?

Surely there's a more plausible explanation for the technology we all enjoy, preferably an explanation involving wickedness and shadowy forces. Is it possible that the computer companies of the world have made a deal with Satan, and imprisoned damned souls inside their machines, forcing them to do billions of calculations per second under threat of intensified torment?

Alas, my theory doesn't stand up to examination. There are conspiracies in the world, but they don't explain all hard-to-believe phenomena. For a conspiracy theory to be plausible, the conspiracy has to have a small enough number of participants that its details could reasonably remain secret—or at any rate, that has to be more reasonable than the alternatives. Given how much difficulty most people I know have in keeping a secret, my minions-of-Satan hypothesis falls apart if more than about three people are involved in the computer industry. Lacking a better explanation, then, I'll just have to accept the information-processing abilities of dirty sand.

Even more mind-bending are the properties of fixpoint combinators. No matter how many times I step through a demonstration of the Y combinator turning a nonsensical up-by-its-own-bootstraps lambda expression into a tidy well-behaved function, I can't quite convince myself that it could ever really work.

The problem with disbelief in stuff that can be demonstrated mathematically is that you have no freedom to invoke a conspiracy. Not even the Trilateral Commission with a fleet of black helicopters could fool us into putting our faith in the Y combinator if it didn't actually perform as advertised.

I'll just have fall back on the idea that The Lambda Calculus Is Magic.

Landauer vs. the Fan

Darn that !@#$% laptop fan. Why is it running again?

Maybe because I took Stanford's free online courses in artificial intelligence and machine learning last quarter, and I've been running experiments with neural networks on and off since then.

Neural networks are fun and flexible ways of coming up with a function when you really have no clue how the outputs relate to the inputs, but it sure takes a lot of time and electricity to train them. I'm basically turning coal (or whatever the local power plant burns) into functions.

I suppose the fact that we recently put photovoltaic panels on our roof should salve my conscience a little, but it still seems as if it's going to take an awful lot of expensive electrons to train enough AIs to provide us all with robot maids and butlers. Can't we do any better?

A recent Scientific American article suggests that Fujitsu's K Computer has around 4 times as much computational power as a human brain, but uses about half a million times as much energy. There's plenty of room to argue that the K computer and the brain do types of processing that aren't comparable, and even if you ignored that, I imagine there's plenty of fudging in the figure the article cites for the brain. Still, we can probably say that the brain is several decimal orders of magnitude more efficient than a modern electronic computer.

What about the brain itself? Is it actually as efficient as possible, or does physics permit computational systems that use even less energy? Well, it was only recently that I discovered the Landauer limit, which describes the minimum energy required to change one bit of information. The Wikipedia article says that at room temperature, the Landauer limit requires at least 2.85 picowatts to record a billion bits of information per second. I'm not sure what that translates to in flops—maybe a single floating point operation requires recording a thousand bits of intermediate information? If so, a billion bits per second is a megaflop, or less than a billionth of a human brain, per the Scientific American article. If I've done the math right, that leaves the brain only a few orders of magnitude less efficient the room-temperature limit (but fortunately, Landauer says colder computers would do better).

At any rate, physics does leave some room for cooler computers. Maybe I won't have to listen to fan noise every time I hang out with Rosey and Mac after all.

Yes, I Have No Class

OK, I think I do kind of get what's going on with Beta. Yes, function activations are objects, and function bodies are object initializers. (I can find references to this being a concept that Beta inherited from Simula, but what I haven't found is any actual Simula documentation that says Simula does things this way. As far as I can see, Simula has rather conventional-looking, distinct syntaxes for declaring classes and procedures. But Beta has just one syntax for both.)

(There's some other stuff going on in Beta, like the ability to keep a function activation around and rerun it in the same activation frame. This is excusable as an optimization of tail recursion, but letting people do it by hand at arbitrary points in the program is a perfect example of the principle that just because you can think of something, you are not obliged to go off and implement it.)

Not Your Grandpappy's this

To illustrate the activation-as-object idea (without resorting to Beta syntax, which is baffling to the uninitiated), here's a bowdlerized version that I hope won't be too offensive to modern functional sensibilities. Consider a representation of binary expressions:

    def Binary (
        public left: Expr,
        public op: BinOp,
        public right: Expr) =
      this

using the usual ill-defined mongrel syntax. In this case, this is understood not to mean what it would in Java or Scala (the object that owns the function where this appears), but rather the current invocation (or call or activation) of the Binary function itself. So Binary is the name of a class. It's also the name of a function that constructs an instance of the class. We can tell Binary is a class because it returns this. (We could also make the return type of Binary explicit, as in:

    def Binary (
        public left: Expr,
        public op: BinOp,
        public right: Expr): Binary =
      this

but my imaginary compiler for this non-language is somehow smart enough to infer this.)

A class with no features is not very useful. Binary has three features, all functions (because the universe contains nothing except functions and activations of functions. Of course, the functions themselves must be activations of the function constructor function. Does my head hurt enough yet?). I've marked these functions (left, op, and right) with public, not the more Scalaish val, to emphasize that I'm specifying only the visibility of these features, not that they are variables (even constant variables) in the usual sense—because there are no variables in the usual sense, only functions that always return the same value. Things that look like variable bindings are just functions defined always to return the argument (a function activation) passed to them.

A fatter example:

    def Binary (
        public left: Expr,
        public op: BinOp,
        public right: Expr) = {
      def eval: Int =
        left.eval mumble mumble right.eval
      def show: String =
        "(" + left.show + " " + op.show + " " + right.show + ")"
      this
    }

where I suppose the defs should actually be publics for consistency, but this train of thought is still way too half-baked to merit consistency (or unmixed metaphors). Since eval doesn't return an eval, and show doesn't return a show, we know these aren't constructors; they're just plain old functions.

Calling a plain old function, like calling a constructor function, allocates an activation record for the function (at least conceptually). But if the activation never escapes, it becomes garbage as soon as the function returns. An execution environment with a lick of sense would put such a thing on a stack instead of a heap, but let's loftily dismiss that as a mere implementation detail.

Found: One Grail (Slightly Holy)

Anyway, yes, activation-as-object does offer a solution to the puzzle of constructors.

To recap, that puzzle is: what is an object before its constructor is called? Bytecode fans will recall that the JVM constructs an object in two phases, first allocating it with the new instruction, and then invokespecialing its class's <init> method. The JVM verifier ensures that you can't get a hold of the object in between new and <init>, because it's not valid then: it's not a proper instance of its class yet, but (because new had to refer to the class to allocate it), it's clearly not an instance of anything else. It's just a nonthing from which you must avert your eyes.

But function invocation, at least as far as we let ourselves know, is atomic. Once the arguments are prepared, boom!, you're executing the function, with its activation record all nicely laid out for you, and with not so much as an eyeblink in between (assembly language programmers may dissent, but our fingers are firmly in our ears and we can't hear a word they're saying). That means that when objects are activations, there is no object to wonder about before its constructor is called: the object is the call to the constructor.

Further Adventures of a Vague Idea

In this non-language that I'm not describing, every identifier that appears in an expression (as opposed to a type declaration) is the name of a function. If that identifier is followed by an open paren or nothing, it's a function invocation. So left.eval above invokes left, which returns the first argument passed to Binary, and then invokes the eval function that is a feature of left (and presumably of every Expr). An identifier followed by an underscore is a reference to the function itself, as in Scala.

Since classes are functions, Expr _ is properly the name of the type of instances of (activations of, calls to) Expr. But after a colon, the trailing underscore is implied, so we can say left: Expr instead of left: Expr _. You might need the underscore in other contexts, like if (foo.class == Expr _) ....

Another random observation is that in Scala, val and var have different meanings in classes and functions. Declarations in a class can refer to each other (so that functions can recurse, and so on); but variable definitions in a function can refer only to local identifiers declared earlier in the function, not later. Since Non-Language functions are both classes and functions, you'll need some kind of syntax to distinguish between letrec-like declarations and sequential declarations, unless you can persuade yourself that you can do without the latter (can you? I never thought about this).

Hey, Look at the Ducks!

Please distract yourself immediately, lest you come up with questions about how this scheme might relate to inheritance, or parametric types, or anything else complicated. If you must, consider these an exercise for the reader (or for Gilad Bracha, whose Newspeak also borrows ideas, but thankfully not syntax, from Beta).

A Funny Type of Contract

Alex Cruise posted the link on the Scala language mailing list to these slides by Benjamin Pierce (along with Nate Foster and Michael Greenberg). Pierce is the author of Types and Programming Languages (which I confess I'm still working my way through).

Even if you have absolutely no interest in type systems, these slides are worth a look for their punchy visuals. Perhaps Pierce should also teach a course on the effective use of PowerPoint.

What Pierce is getting at (if I understand right) is that type systems can get too heavyweight to be worth the trouble. He's looking at a particularly complex case, that of the Boomerang programming language, so perhaps the typechecking in your favorite language (if it's not Boomerang) may still be lightweight enough not to be under suspicion.

Pierce's conclusion seems to be that contracts (in the form of runtime assertion checks) may have to supplement compiletime typechecking to make the overall problem of verifying program correctness tractable.

I've been thinking for a while that it would be nice if there were some way that types and assertions could be unified. Types constitute a form of contract that is verified at compiletime (and/or loadtime, in languages that do loadtime verification), while assertions are verified at runtime. Runtime assertion checking is easy enough, so the difficulty in bridging the two is coming up with a general way to specify how contracts can be checked at compiletime: this requires giving your compiler and/or loader enough ammunition to do an automated proof, which is extremely hard except for the simplest cases (something like Java's nominal type system, before generics, constitutes a pretty simple case).

Eiffel is the only language I've seen that makes a big deal of method pre- and postconditions in a way that is analogous to typechecking on methods: that is, when you override a method m with a method m′, m′'s postconditions must be more specific than m's (covariantly), but its preconditions must be less specific (contravariantly).

It might be cool if a language had a sort of Third Way with respect to types and assertions, where you could tell the compiler to check a contract at compiletime if the compiler can figure out how (and it doesn't take too long), or at runtime otherwise. Runtime checking is generally inferior to compiletime checking, but most of us would settle for it if the compiletime check would take forever.

Always in Beta

My quest to understand What Programming Languages Are Made Of has led to me start reading the Beta Programming Language book. I've only gotten as far as Chapter 3 so far, but I've already seen enough quirks in the language to have repaid the time.

If I see the implications properly, it looks as if Beta unifies method calls and object construction. That is, the language has no functions or methods per se; rather, all code lives in what would Java or Scala would consider constructors or instance initialization. Instance variables play the role of local variables.

It's easy to observe that stack frames are like objects, in that both are usually laid out as structs accompanied (in languages with managed memory) by a pointer to some sort of descriptor. But it's a bold leap to say that stack frames are objects.

I haven't read far enough to be sure that my understanding is correct. It would also be interesting to see whether Beta has any notion of alternate constructors—which, when viewing Beta objects as functions, would have an effect something like default function arguments.

Is the Beta approach part of the answer to the puzzle of What Are Constructors Made Of? I haven't figured that out yet.

I've seen Beta mentioned a few times, but never heard of anyone using for it anything. I wonder whether it failed to gain traction because people always assumed it was still in beta.

Sticking to Mutability

In our last episode, we left Minty Fresh Construction lying tied to the tracks with the Locomotive of Hopeless Complexity bearing down on her at full steam. Well, Minty, you're just going to have to hang on for a bit, because we have more characters to introduce to the story. Maybe we'll see you again after the plot has thickened enough.

Immutability's Evil Stepsiblings

We all know that Mutability Is Bad. Bad to the bone. The language construct that dare not speak its name (at least in some languages). Or at any rate, those of us with a properly strict functional upbringing know this; there are still heathens out there who write Java (or even Scala or C++) code containing single equal signs without the least hint of shame.

Shudder.

Not talked about in the Best Families is the fact that the languages we all know and love are inclined, in the depths of night with the shades drawn, to treat the contents of memory as a big mutable array whose contents they can toy with as they please. An even darker secret is that the designers of libraries for ostensibly immutable data structures sometimes hide mutable variables in their cellars (at least temporarily, like Scala Builders).

Of course, there have been attempts to dress mutability up in civilized clothing and bring it into Polite Society. We've seen enough of Haskell's by-need evaluation and Scala's lazy vals that they rarely elicit anything more than mild titters.

Dare we ask ourselves now if there any more forms of mutability out there, longing to discard their black hats and shave their twirly mustaches, ready to submit themselves to the conventions of decent society and become upstanding, productive citizens?

We dare.

Lazy References

Lazy vals and by-need parameters can be understood as the combination of a mutable reference cell, a flag, and a nullary function. The flag tells whether the cell has been initialized; if set, the cell can be examined. If not set, any attempt to examine the cell invokes the function, puts the resulting value in the cell, sets the flag, and returns the value:

    class LazyRef[T] (private var f: () => T) {
      private var initialized = false
      private var value: T = null.asInstanceOf[T]
      def get: T =
        synchronized {
          if (! initialized) {
            value = f()
            initialized = true
            f = null // lest f become garbage
          }
          value
        }
    }

There's mutability here, all right, but it's a very disciplined sort of mutability that can mingle with the inhabits of Immutableland without causing the least alarm. value can be changed, but only once, and you can never observe it before it gets changed, so it's as good as immutable if you overlook the peculiar circumstances of its birth—er, conventions of its initialization.

Compulsive optimizers may observe that a straightforward implementation of LazyRef can take more space than necessary. At any given moment, either value or f is of interest, but never both at the same time. You might reimagine LazyRef as:

    class LazyRef[T] (private var funOrVal: Either[() => T,T]) {
      def get: T =
        synchronized {
          funOrVal match {
            case Right(v) =>
              v
            case Left(f) =>
              val v = f()
              funOrVal = Right(v)
              v
          }
        }
    }

Whether this version of LazyRef is any faster or more compact than the previous version depends on your execution environment. The point is, though, that because this construct is so useful, you're likely to make heavy use of it, and attention (from the language or VM) to make it more efficient might be well repaid.

Sticky References

Lazy Val has a more rakish cousin I call a sticky reference, or stickref for short. Stickref is mostly safe around Respectable Society, but you'll want to ensure that he's properly chaperoned whenever he's in the presence of impressionable young algorithms.

Stickref differs from Lazy Val in that he doesn't start life with an initialization function. Instead, he remains brazenly uninitialized until given a value, which he then holds steadfastly ever after—he's immutable once initialized:

    class UninitializedException extends RuntimeException
    class AlreadyInitializedException extends RuntimeException
    class StickRef[T] {
      private var value: Option[T] = None
      def get: T =
        synchronized {
          value match {
            case Some(v) => v
            case None => throw new UninitializedException
          }
        }
      def freeze (newValue: T): T =
        synchronized {
          value match {
            case Some(_) =>
              throw new AlreadyInitializedException
            case None =>
              value = Some(newValue)
              newValue
          }
        }
    }

Stickref clearly feels less safe than Lazy Val; using a stickref can result in an exception, whereas using a lazy val cannot (unless its initialization function throws an exception).

On the other hand, a stickref can keep mutability from getting out of hand even when there's no readily available initialization function suitable for constructing a lazy val. This might bring to mind, for example, the setting of a final instance variable in a constructor.

Minty, are you still holding on?

Construction Revisited

The whistle blows continuously and sparks fly from the great driving wheels as the engineer brakes, having spotted our heroine in her peril. It seems the heavy express train will never stop in time—but wait, who rides over the hill on a white horse? Could it be that wild fellow Stickref? It is! And quick as a flash he leaps down, undoes the ropes, and pulls Minty to him, averting disaster by a hair's breadth!

To revisit the last example from the previous post:

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

Can translating this into something with a stickref prevent access to uninitialized final instance variables?

It can. In not-quite-Java:

    class T {
      private final StickRef<int> i = new StickRef<>;
      private final StickRef<String> s = new StickRef<>;
      public T (int i, String s) {
        this.i.freeze(i);
        escapeFromHere(this);
        this.s.freeze(s);
      }
      public int i { return this.i.get(); }
      public String s { return this.s.get(); }
    }

Unlike the solutions of the previous post, I've made no attempt to catch invalid accesses at compiletime. Instead, I've wrapped the final instance variables in something that gives a runtime error for such accesses. It does, at least, catch the accesses as soon as they occur—unlike the regular Java semantics, which don't immediately throw an exception unless the default null or zero value for the final variables triggers such an exception.

You'll notice that this solution is quite a bit simpler than my previous ideas; I don't need to generate any synthetic partially-constructed classes.

Minty-fresh constructor semantics look feasible after all, provided that you're patient enough to wait until runtime to enforce them.

But Can I Afford It?

Readers on a budget will have noticed that the indirection involved in a stickref has a cost. freezeing isn't free, as they say. I haven't tried to benchmark the difference between access to a straight instance variable and access to one wrapped in a StickRef, but I'll bet you that any VM you try it on will show that the stickref is quite a bit slower. (Let me know if there's some VM for which that's not true!)

So how can I be pushing this stickref thing as a practical solution? What kind of Scala library author spendthrift would act as if allocating additional wrapper objects all over the place had no adverse consequences?

Well, I'm not really envisioning StickRef as a standalone thing. Existing VMs probably aren't tuned to detect this particular pattern (or LazyRef, for that matter). But if you built StickRef into a VM that knew to look for it, it doesn't take very sophisticated flow analysis to see that in most real-world constructors, the stickrefs are all frozen (the final variables are all set) before the constructor returns. Seeing that, a smart VM would just discard the stickrefs and set the variables directly, which should eliminate the cost except when there's genuine uncertainty about whether an illegal access will occur.

Multitrick Pony

OK, fine, so Stickref rescues Minty. Big deal. I mean, what kind of Itanium instruction set designer madman would come up with such an elaborate Sarah Winchester architecture of quasi-mutable references just to get one little lousy effect, an error message for something hardly anyone (besides me) is actually stupid enough to do?

As it happens, stickref semantics are a perfect fit for binding variables in Scheme's letrec*. And since letrec* is more or less the archetype for initialization of mutually referential expressions, I can fairly claim that, in a multilingual environment, stickrefs are going to show up in quite a few places. And if you optimize stickrefs for minty-fresh construction, you optimize them for all those places, too.

Bring the Whole Family

Incarnations of the idea of controlled mutability start popping out of the woodwork as soon as you start looking for them. Imaginge, for example, a variation on the Java semantics that guards against changing final variables at runtime rather than compiletime. The regular Java semantics set finals exactly twice: the first time to the default value, and the second time to the constructed value. To achieve this effect you need something a little more flexible than a sticky reference: a freezable reference, which can be examined and set as many times as you like before you freeze it into immutability:

    class AlreadyInitializedException extends RuntimeException
    class FreezaRef[T] (private var value: T) {
      private var frozen = false
      def get: T = synchronized(value)
      def set (newValue: T): T =
        synchronized {
          if (frozen)
            throw new AlreadyInitializedException
          else {
            value = newValue
            value
          }
        }
      def freeze (newValue: T): T =
        synchronized {
          if (frozen)
            throw new AlreadyInitializedException
          else {
            value = newValue
            frozen = true
            value
          }
        }
    }

Beyond FreezaRef we can spot the outlines of some more exotic members of the family, such as meltable references. These references are also freezable, but they can also be unfrozen and become mutable again. Unlike ordinary mutable variables, meltable references expect to be unfrozen only infrequently—that is, the VM can assume they will be unfrozen infrequently in choosing how to optimize them. You could use something like meltable references as building blocks in a data structure holding code that can be optimized and deoptimized: when the reference to a piece of code is frozen (perhaps it's a method call whose target has been resolved), the code becomes eligible for optimization. When you melt the reference (perhaps another method has been loaded so that the original call site is no longer monomorphic), you'll need to deoptimize the code (perhaps optimizing it again later if it can be refrozen).

The common theme with all these forms of mutable references is that they're only mutable sometimes. Over large and well-defined portions of a program's execution, they're immutable. That makes it easier for people to understand how they'll behave, and easier for compilers and VMs to figure out how to optimize them by eliding the synchronization and flag checks implied by the sort of code I've shown above.

So maybe we don't have to be so afraid of mutability. Give it a bath, teach it some table manners, keep it on a short-short leash, and we can welcome it into our home like a member of the family. Only VM and language designers need lie awake at night in a cold sweat over what might happen if something goes wrong.

Meanwhile, Back at the Construction Site

Controlled immutability is all very well, but it's distracted me from my original mission. What ever happened to unifying constructors and factory methods? I still have some half-baked ideas on that, but my blogging muscles are getting kind of sore, so I'll have to save it for another time.

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.