Since my last post, I have been implementing all of the details of properties. They’re almost done now, I just have a bit of code generation to finish.

While I was implementing them, I was thinking about the system for initialisation I described in my last post, and discovered how broken it was.

Escape Analysis

While an object is being initialised, the value of ‘this‘ is not allowed to escape from the initialiser or the constructor. For example, you can’t do the following:

class Foo
{
  string uninitialised;
  static ?Foo stored;
  constructor() throws Exception
  {
    stored = this;
    throw new Exception();
  }
  static uint main([]string args)
  {
    try
    {
      Foo f = new Foo();
    }
    catch Exception e
    {
      if stored != null
      {
        stdout::println((cast<Foo> stored).uninitialised);
      }
    }
    return 0;
  }
}

If ‘this‘ was allowed to escape the constructor, the stdout::println() would have undefined behaviour, probably causing a crash. So obviously escape analysis is necessary; usually we enforce it by stopping anyone from using ‘this‘ or calling an instance method before the object is fully initialised, but how do we cope with it for properties?

One thing to note about properties is that some of them have to be initialised in the constructor. For example, properties which do not have a default value for their backing variable must always be initialised, and final properties must always be initialised exactly once.

The problem is how to do this initialisation. If we call the setter, it could allow ‘this‘ to escape (and we can’t just check that it doesn’t, because it could be overridden by a subclass). We could check setters much more strictly, but this would stop us from ever doing a lot of the things we might like to do in a setter, such as using the old value of the property.

Property Constructors

To solve this problem, Plinth allows properties to have constructors, which can only run once during object initialisation, and never again. This is the much more strictly checked version of the setter: it is not allowed to use ‘this‘ or depend on anything in the object being initialised, or even depend on anything definitely not yet being initialised (so it can’t either read or write from final variables).

To reduce the amount of unnecessary code written, if a constructor is required but not implemented, it defaults to using the setter’s implementation. (Of course, this doesn’t always work, and in such cases a separate implementation must be provided).

When you are initialising an object, you are allowed to call a property’s constructor by assigning to it for the first time. However, once the constructor has been called, you are not allowed to call its setter until the object is fully initialised. This can lead to interesting situations where we can’t decide between the constructor and the setter:

class Asdf
{
  property string text
  // (use the default getter)
  setter(value)
  {
    stdout::println("setter");
    text = value;
  }
  constructor(value)
  {
    stdout::println("constructor");
    text = value;
  };

  // constructor for Asdf:
  selfish constructor(boolean b)
  {
    if b
    {
      this.text = "blah"; // prints "constructor"
    }
    this.text = text; // control flow error: impossible to decide between setter and constructor
    this.text = "Asdf"; // prints "setter" (allowed because the object is fully initialised)
  }
}

Static and Final Properties

Properties don’t only work for instances of objects, and they are allowed to be final.

The definition of ‘final’ in plinth is: ‘must be assigned to exactly once’, with the extra restriction for instance members: ‘must be assigned to before it can be read’. (The same definition is used for both fields and properties).

So what does this mean for the property functions? As you might guess, final properties never have a setter, and must have a constructor. However, depending on what you’re expecting, non-final properties might look slightly weird.

In the case of static non-final properties, they must have a setter, but they cannot ever have a constructor. This is because you could never enforce that the constructor would be called before the getter or setter: a static initialiser from another class might call the setter before you get a chance to call the constructor. Because of this, a constructor would be meaningless.

For non-static, non-final properties, constructors are actually optional. If you declare one, it definitely exists; if you don’t declare one, it *might* not exist, but it’s still possible. A property which has a backing variable which doesn’t have a default value has to have a constructor, for example:

property string s
getter { return s; }
setter(value) { s = value; };

This property has a constructor which defaults to using the setter’s implementation, even though it wasn’t declared. This allows a subclass to override the constructor to do something different during initialisation if necessary.

The truth table for when getters, setters, constructors exist is as follows:

The ‘?’ means that there is a constructor if either a) one is declared, or b) the property is not marked as unbacked and has a type which does not have a default value.

Properties are a special way of storing and accessing data. They usually act exactly like fields, but you can also define custom getters and setters to get/set a property’s value in a special way.

The normal way of defining a property is:

property Foo someFoo;

This defines a property called someFoo of type Foo, with default a default getter and setter. The default getter and setter simply assign and retrieve a backing variable. To access this property (assuming it is in a class Bar), we treat it as if it were a field:

Bar bar = new Bar();
Foo oldFoo = bar.someFoo;
bar.someFoo = createNewFoo();

Custom Getters and Setters

Sometimes, it is useful to do some processing in the getter or the setter of a property. In fact, the whole reason for having properties is so that we can override this behaviour if we want to. Here’s how we do it in Plinth:

property string name
getter
{
  return name;
}
setter(newName)
{
  logNewName(newName);
  name = newName;
};

Inside the getter and setter, the references to name actually refer to the backing variable for the property. But they don’t have to be used. In fact, you can declare a property without a backing variable:

string actualName;
unbacked property string name
getter
{
  return actualName;
}
setter(newName)
{
  actualName = newName;
};

In this case, you must define a custom getter and setter, because the default ones cannot be used.

A property can also be abstract, and properties in interfaces are abstract by default. Abstract properties are always unbacked, and have no implementation for their getter and setter. Any types inheriting an abstract property must always define it, even if they do not provide custom getters and setters, as the backing variable must be defined in order to generate the default getter and setter.

Immutability and Properties

By default, properties have a normal setter and an immutable getter. This allows you to read the variable from an immutable context (e.g. inside an immutable method), but modify it only from a normal (mutable) context.

However, this behaviour can be changed using modifiers. If you want a mutable getter, it can be marked as such using the mutable modifier, but the property will no longer be readable from an an immutable context:

property uint x
mutable getter
{
  ++x;
  return x;
};
immutable uint getThriceX()
{
  return x * 3; // error: x cannot be read from an immutable context
}

Another thing you can do is mark a property’s setter as immutable. This allows you to call the setter from inside an immutable method:

unbacked property uint y
immutable setter(value)
{
  stderr::println("y = " + value);
}
getter
{
  return 17;
};

Of course, it is usually impossible to alter anything from inside an immutable function, and a setter is no exception. The only way to modify something from within an immutable function in plinth is to mark the variable being modified as mutable. So we could use our own backing variable and mark it as mutable, or we could mark the property itself as mutable, which accomplishes the same thing. Making a property mutable only affects the backing variable (so mutable unbacked properties are impossible). We can define a property with an immutable setter as follows:

mutable property uint z
immutable setter
immutable getter;

immutable void quadrupleZ()
{
  z *= 4; // works, because the getter and setter are both immutable
}

Here, we declare the property’s setter as immutable. This allows the setter to be called from an immutable context, such as quadrupleZ(). We also declare the getter as immutable for consistency, but this is not necessary since getters are immutable by default.

Returning from a Getter

Forget about properties for a moment. When you read from a field, the value is immutable if the thing you are accessing it on is immutable. For example:

class Foo
{
  Foo next;
}
// in some method:
#Foo myFoo = new Foo();
Foo nextFoo = myFoo.next; // error: myFoo.next is a #Foo, so it can't convert to a Foo

This happens because Plinth has deep immutability, meaning that accessing data on an immutable object results in more immutable data.

The same is true when we use properties: reading a property on an immutable object results in an immutable piece of data. However, reading a property on a normal object results in a normal piece of data. For example:

class Foo
{
  property Foo next;
}
// in some method:
#Foo myFoo = new Foo();
Foo nextFoo = myFoo.next; // error: myFoo.next is a #Foo, so it can't convert to a Foo
Foo otherFoo = new Foo();
Foo otherNextFoo = otherFoo.next; // fine, otherFoo is not immutable, so neither is otherFoo.next

This is fine so far, but now imagine that the getter is a normal method:

class Foo
{
  Foo next;
  immutable Foo getNext()
  {
    return next; // error: next is a #Foo in this context, which can't convert to a Foo
  }
}

As you can see, it is not possible for an immutable method to return one of its fields without the result being immutable.

So how do getters work in this situation? They cheat.

A property’s getter can return values “against contextual immutability”. This means that if it returns a value which is only immutable because it was accessed inside an immutable context, then returning that value works. For example:

class Foo
{
  Foo realNext;

  unbacked property Foo next
  setter(value)
  {
    realNext = value;
  }
  immutable getter 
  {
    if true
    {
      // this works, because although realNext is immutable in this context,
      // immutable getters can return values against contextual immutability
      return realNext;
    }
    #Foo otherValue = new Foo();
    return otherValue; // error: otherValue is explicitly immutable, not just contextually immutable
  };
}

Initialisers and Backing Variables

As with fields, properties can have initialisers. Initialisers simply call the setter with some value, for example:

property uint x = 45
setter(value)
{
  stdout::println("new x=" + value);
  x = value;
};

This will print out “new x=45” during initialisation.

However, there is a subtlety about initialisation which involves the property’s backing variable: accessing the old value from the setter:

property string y = "hello, world!"
setter(value)
{
  string old = y; // error: y may not have been initialised
  stdout::println("old y=" + old + " new y=" + value);
  y = value;
};

If the property’s type does not have a default value (e.g. null or zero), then the backing variable must be initialised before it is read. This means the setter cannot access the old value, since before the setter is called for the first time, the backing variable’s value is undefined.

There is a way around this, but it requires slightly more work. It involves using a custom backing variable and an unbacked property:

string backingStr = "initial";
unbacked property string str = "hello, world!"
setter(value)
{
  string old = backingStr;
  stdout::println("old=" + old + " new=" + value);
  backingStr = value;
}
getter
{
  return backingStr;
};

This will print "old=initial new=hello, world!" during initialisation.

In theory, it would be possible to design the language to allow access to the backing variable from outside the getter and setter. However, the confusion this would cause as to whether or not the setter is called in a given assignment makes it much clearer to use a custom backing variable if access to the old value is needed.

Last week, I discussed how the internals of the stack unwinder work during exception handling. This week, I am going to talk about how Plinth’s exceptions look from a programmer’s point of view, and their semantics.

Exceptional Type System

Everything which can be thrown in plinth implements an interface called Throwable. If something implements Throwable, it can be thrown and caught using throw statements and try-catch blocks.

Underneath Throwable, there are two classes: Error and Exception. The distinction between these is slightly fuzzy, but the main idea is:

Anything which a programmer should expect to have to handle should be an Exception.
Anything which a programmer shouldn’t expect should be an Error.

For example, a programmer shouldn’t expect a cast to fail. Since the value being cast is completely under their control, they should check the value for themselves before casting. Thus, a cast failure results in a CastError (which extends Error).

In another case, a programmer might be interacting with some system they don’t have control over, such as the file system. If they try to open a non-existent file, the I/O library might throw a FileNotFoundException (which extends Exception).

Checked Exceptions

This is a feature a lot of languages either skip (C♯) or get slightly wrong (Java).

A checked exception is an exception that the compiler checks the propagation of. If something throws some checked FooException, then that FooException must either be caught or be declared to be thrown onwards.

In Java, this ensures that if something might throw an exception, you have to declare it as being rethrown at every stage until it’s caught. This can be a big problem if you want to use higher order functions (e.g. as described here), since the higher-order function usually has no idea what exceptions might be thrown through it. You can get around this problem by tunnelling: boxing a checked exception inside an unchecked exception and re-throwing that. The problem with this is that in order to catch the boxed exception again, you must write a catch block which matches any instance of the unchecked exception, and do instanceof checks on the one boxed inside it.

In my opinion, Plinth handles cases like this much better than Java. Instead of having certain types which are checked and others which are unchecked, Plinth considers every Throwable to be checked. However, it allows you to rethrow them as unchecked:

void mightThrow() throws Error, unchecked FooException
{
  if someTest()
  {
    throw new FooException();
  }
  throw new Error();
}

void caller() throws Error
{
  mightThrow();
}

Here, mightThrow() has to declare all of the Throwables it might throw. Because it can throw both FooException and Error, and doesn’t catch either of them, it must have both in its throws clause.

The point here is that it declares FooException as unchecked. Because of this, caller() doesn’t have to declare that it could throw FooException. Nevertheless, it must declare that it throws Error, since it doesn’t catch it.

One point to mention here is that any method can declare that it throws any Throwable type without generating compiler warnings for unnecessary declared exceptions. This is because it could always be rethrowing an unchecked exception as a checked exception.

This system still has the useful property that you have to deal with every exception somewhere, the difference is that now you can explicitly decide to ignore it without writing a whole try-catch statement.

Try-Catch-Finally

Try statements are very useful not just in exception handling, but in general for cleanup code. They function very similarly in Plinth to how they do in other languages.

The basic semantics are that the try block tries to execute, and if it fails at any point by throwing an exception, the language checks each of the catch blocks to see if any of them match the exception. If any do, the first matching catch block is run. The finally block is run after all of the try/catch blocks have finished, even if any of the try or catch blocks throw an exception, return, or try to break out of or continue through an enclosing loop. After the finally block has been run, execution continues wherever it was going before it entered the finally, for example it could continue throwing an exception, or it could branch back to the start of a loop.

An example of a try-catch-finally statement is as follows:

try
{
  callSomething();
}
catch IOException | FooException exc
{
  stderr::println("Caught an IOException or a FooException!");
}
catch Error err
{
  stderr::println("Caught an Error!");
}
finally
{
  doSomeCleanup();
}

As you can see, multiple exceptions can use the same catch block. In the first catch block above, the type of exc is the lowest common super-type of IOException and FooException (or Throwable if there are two equally-close super-types).

Control Flow of Try-Catch-Finally

Control flow checking is a compiler pass which tracks which variables are initialised where. It primarily maintains two sets: the set of initialised variables, and the set of possibly-initialised variables. These sets are used to check that variables are not used before they are initialised, and that final variables are not initialised twice. During a constructor, the control flow checker checks some extra things, such as member variables.

Try-catch-finally statements are easily the most complicated statements in terms of control-flow. If a finally block is involved, the semantics involved in tracking which variables are initialised are very tricky to define. To illustrate this, here is a sketch of the threads of control flow that can happen in a try-catch-finally statement (ignoring break and continue):

The arrow coming from the top is where control begins, and the one exiting at the bottom is where it goes on to any statements after the try-catch-finally statement.

The first thing to notice is that on the way to join-up point (a), the try statement may not be executed. This models the fact that an exception may be thrown at any point during the try statement, causing it to terminate abruptly. In fact, any lines of control flow in the try statement that stop execution (i.e. with a break/continue/throw/return) are also combined into join-up point (a). This allows that point to model accurately which variables have been initialised after the try statement halts abnormally.

After point (a), control goes through the catch blocks. Since each of these can also terminate with a break/continue/throw/return, we must also short-circuit all of the catches on the way to the finally block, as we did with the try block. We then reach join-up point (b).

Next, we must process the finally block. There is only one finally block, but the diagram contains it twice. Finally [1] is to do a control-flow check on the finally block with an accurate model of all possible control flow states entering it. Whereas finally [2] is there to help us find out which variables are initialised when control continues on to the statement immediately after the end of the try-catch-finally statement.

At join-up point (b), we have an accurate model that says which variables definitely are initialised and which might be initialised just before the finally block. We use this to check that the finally block doesn’t break any control-flow rules about variables.

In order to model the control flow after the try-catch-finally statement, we combine together the states at each of the returning try and catch blocks at join-up point (c). If a try/catch block doesn’t return, we don’t combine it into that join-up point, because it won’t affect what happens to the control flow after the finally block. Finally, finally [2] finishes, and we can continue to process whatever statements are next.

But what happens after finally [1]? The answer is that it can go to many different places, depending on what caused us to enter the finally block in the first place. If someone broke out of some loops through a finally block, control would branch to after the outer loop. If someone returned, the function might return. On the other hand, there might be another finally block higher up in the function that we also have to process before returning. In general, execution can go to lots of different places. To implement this, the code generator will create an internal integer variable which will decide where to jump to after the finally block finishes.

Before this week, I had no idea how exception handling worked. I assumed languages which use virtual machines do a lot of bookkeeping in order to maintain some data structure to jump back through, but C++ exceptions may as well have been magic.

During the last week, I’ve come to understand a lot more about how they work, and also struggled a lot at working out how to implement them in Plinth.

There are two main ways to do exception handling: use the Itanium ABI, or use calls to setjmp() and longjmp().

Itanium ABI for Exception Handling

The Itanium ABI, and the variations of it used on other architectures, can also be referred to as “zero-cost” exception handling. This is because they don’t use any CPU time or stack space unless an exception is actually thrown.

The core of this form of exception handling is implemented by a library called an unwinder. The unwinder is what you call to raise an exception in the first place, and it knows how to unwind the stack and call something called a “personality function” for each function call it unwinds.

A personality function is a language-specific function which works out what to do when the unwinder unwinds into a given stack frame; it is passed the exception being thrown and the unwinder’s context for this frame. From this context, it can find out what the instruction pointer was at the time of the call, and it uses this in combination with some language-specific data about the current function to decide whether to continue unwinding past this frame, or to jump into a catch or finally block.

It then sets some registers, including the instruction pointer, and execution jumps to a landing pad. This landing pad does whatever cleanup the personality function signalled it to do. So if the personality function decided that one of the catch blocks was triggered, one of the registers it set would indicate that to the landing pad, which would branch on the contents of that register and execute that catch block.

If a finally block was encountered, and it didn’t throw another exception or return in the mean-time, it would eventually call back into the unwinder to resume the unwinding process from where it left off.

setjmp() / longjmp() Exception Handling

setjmp() and longjmp() are C functions which have the interesting semantics that when you call longjmp(jmp_buf, value), execution jumps directly to the original call to setjmp(jmp_buf), which then returns for a second time, this time returning the value passed into longjmp().

The most important part of this form of exception handling is its linked-list structure. Each function which needs to handle exceptions allocates an entry in this linked-list on the stack, inside which it stores a reference to the previous piece of memory along with a buffer for the setjmp() and longjmp() functions to use. The current top-of-the-stack is stored in a thread-local variable.

In order to call a function, the execution state must first have been saved to the function’s buffer using setjmp(), so that if the function throws an exception, execution can begin again at the relevant catch or finally block.

Apart from the linked-list allocated on the stack, this method of exception handling is very similar to the Itanium ABI. In particular, each linked-list entry contains a pointer to a personality function, which does the same sorts of processing (using the same sort of language-specific data) that the Itanium ABI’s personality function does. The main difference is that it unwinds using longjmp() rather than setting the program counter directly.

As you might have noticed, setjmp() / longjmp() exception handling is much more expensive than it is with the Itanium ABI, as it uses more CPU time and stack space maintaining the linked-list structure. It can be faster when propagating exceptions, but since exception handling is meant to be rare, the Itanium ABI is the preferred method for exception handling most of the time.

LLVM’s Exception Handling

LLVM supports both the zero-cost method and setjmp() / longjmp(). The problem is that it doesn’t support either of them on all platforms.

One example for this is ARM. On ARM, the zero-cost exception handling ABI (EHABI) is slightly different from the Itanium ABI. The unwinder still calls the personality function once per stack frame, but it also delegates the unwinding of that stack frame to the personality function (i.e. the personality function must know how to unwind out of the current function).

From what I can tell, LLVM doesn’t yet emit the correct DWARF exception tables (or language specific data blocks, as they are called in the Itanium ABI) necessary to support ARM’s EHABI (http://llvm.org/bugs/show_bug.cgi?id=7187), which is why LLVM recommends using setjmp()/longjmp() on ARM.

Another problem is that setjmp() / longjmp() exception handling is broken on most platforms which are not ARM: http://llvm.org/bugs/show_bug.cgi?id=1642

Plinth’s Exception Handling

With Plinth, I am trying as hard as I can to keep the generated bitcode files platform independent. This means generating platform-independent code to handle exceptions in a given function. The problem is that from what I can tell, neither of LLVM’s methods for exception handling work on all platforms.

In order to get around this, I will probably have to implement my own exception handling system. The design I am currently working on is very similar to the normal setjmp() / longjmp() system, but without personality functions and without any form of DWARF exception tables (since I cannot generate DWARF myself).

Hopefully, next week I will have a basic exception handling system implemented.

Update 2013/02/12: After asking the LLVM developers about exactly how setjmp() / longjmp() exceptions are written in bitcode, it turns out that the bitcode is the same no matter which scheme you use (email link). Since this allows me to generate bitcode that will work on all platforms (given a compatible unwinding library and a personality function), I will be using zero-cost exceptions where possible, and falling back to SJLJ exceptions everywhere else.

Last week, I implemented the instanceof operator. Doing this made me consider in much more detail how casting and instanceof should work, as there are several ways that they could.

The Unified Type System

A unified type system is one where every type can be cast to some all-encompassing super-type. In Plinth, the name of that type is ‘object‘, or to be more specific ‘?#object‘ in order to account for nullability and immutability.

When you cast, say, a double to an object, you are implicitly performing a heap allocation so that the double can be stored on the heap inside something that looks like an object. In fact, it is just an object with a double tacked onto the end, and with its virtual functions replaced by ones which extract that double and call the real functions. The same system is used to cast tuples, compounds, functions, and all of the other primitives to objects.

On the other hand, arrays and classes already look enough like objects to be cast to them directly (using the same pointer).

Because we might want to use instanceof on an object, or check whether to throw a CastError before we actually do a cast, every object stores a pointer to a block of run-time type information (RTTI). This RTTI holds data about the sort of type (e.g. ‘primitive’ or ‘array’), and the properties of the individual type (e.g. the kind of primitive it is, or an array’s base type). When we cast a double to an object, that object has an RTTI block for double.

Casting

Different casts are performed in very different ways. A cast from uint to long simply zero-extends the binary value from 32 bits to 64 bits, whereas a cast from a class Foo to object is just a matter of reinterpreting the same pointer as a different type.

Casting from an object to some other type is much more complicated. If the RTTI for the object does not match the destination type properly, we need to throw a CastError. If it does match, we might have to extract a value from inside the object, or maybe reinterpret that object as a class, or possibly search through the RTTI for a super-interface’s VFT and tuple it with the object pointer.

But what happens if we do the following:

long a = 5;
object obj = a;
int b = cast<int> obj;

The object is a long, but longs can be cast to ints easily – they are just a truncation from 64 bits to 32 bits.

The problem is knowing that obj is a long. It might be anything from a boolean to a string, in which cases the result should definitely be a CastError. Since the RTTI for long doesn’t match the values we expect for an int, the cast won’t be allowed.

However, with a lot of work, it would be possible to allow it. We could write a really long line of checks for whether the run-time-type is int or ubyte or boolean or float or {uint -> string} or [][]double. We would actually only need to check the types that we could convert from, but it would require a huge amount of LLVM code for such a small amount of Plinth code.

This type of “transitive” cast gets especially cumbersome when you consider the fact that you can convert tuples like (ubyte, short, boolean) to (int, long, boolean). If this type of cast were allowed, casting from an object to a tuple would require looking through the RTTI for each of the tuple’s values (recursively) to first check whether the conversion is possible, and second find out how to perform it.

In Plinth, transitive casts are not allowed. In order to handle the sort of cast we tried to do above, we would have to do something like:

int b = cast<int> cast<long> obj;

Instanceof

The instanceof operator (which might be renamed to ‘is‘ at some point) allows you to check whether a value is an instance of a given type. For example:

long a = 5;
object obj = a;
boolean isInt = obj instanceof int; // false
boolean isFoo = obj instanceof ?#Foo; // type error: cannot check against a nullable or immutable type

As shown, you cannot check whether something is nullable or data-immutable. This is because these are properties of the reference, not the value itself: even if the reference is immutable, the value behind the reference usually won’t be. Similarly, the value behind a nullable field won’t itself be nullable – it can’t be null. The exception to this is when checking nested types: []boolean is different from []?boolean.

There are several different ways which instanceof could have worked. For example it could return true whenever the value is assignable to the type without losing data, so a uint with value 3 would be an instance of ubyte, because it fits inside an 8 bit unsigned value. This scheme would have required the same sort of transitive checking described above.

Another way would have been to return true whenever the assignment would work in a single step without losing data (i.e. the same, but without the transitive checks), which would illustrate exactly when casting would work. This could give you true for (ubyte, Foo, string) instanceof (uint, Bar, string). It could even allow nullable values, returning true if a null value were checked against a nullable type. The problem is that this system is very often confusing and can’t tell you unambiguously whether this number you’ve got is a ubyte.

Plinth uses the simplest and hopefully the most obvious system: value instanceof type is only true when the value is already an instance of type. For classes and interfaces, this means checking against all super-types as well, because those super-types are part of the sub-type. But comparing a short to an int will result in false even if the cast is known at compile time to be just a sign-extension to 32 bits.

The Plinth compiler turns source code into LLVM bitcode. This bitcode is a very versatile format, because it can be translated into machine code that runs on most processors. Not only that, but it can be used to store arbitrary metadata. Plinth takes advantage of this in several ways.

Metadata

Plinth bitcode files do not just store executable code, they also store metadata about how that code works. The high-level structure of a program is encoded in metadata and stored in the generated .pbc files.

The plinth compiler reads code from source files, and generates a single LLVM module for each type definition (class, interface, etc.)¹. At this point, it generates the metadata for that type definition. A class’s metadata consists of:

• The class’s fully-qualified name.
• The super-class’s fully-qualified name (if any).
• A list of fully-qualified names of its implemented interfaces.
• Whether or not the class is abstract, immutable, and other applicable modifiers.
• Lists of fields, constructors, and methods.

All of the relevant data about each field, constructor, and method is also stored in the metadata, for example their types.

The reason for all of this metadata is to allow bitcode files to be used as libraries to import types from. Given all of the information from the metadata, the compiler can resolve a type and any/all of its members without seeing its source code. It can also generate references to things inside that type which will be filled in at link-time.

During linking, LLVM resolves all of the function calls and global variable accesses to the right places so that the code can run. But in addition to this, it links all of the types’ metadata together. The result is a .pbc file which contains all of the metadata required to import any type that was linked into it, as well as the code to link against. This allows you to link all of the bitcode files from your library together, and import them all at once by using the compiler switch: -i mylibrary.pbc

Executable Code

The rest of what the plinth compiler generates is executable code. What actually gets encoded in machine code is a set of functions and global variables. Each method becomes a function, and each static field becomes a global variable; but there are other uses, such as run-time type information, virtual function tables, and string constants.

When you create a class, the code generator does two things: calls its allocator to allocate enough memory for it and populate its run-time type information (RTTI) and virtual function table (VFT) fields, and calls its constructor to perform any user-specific construction that must be done. In order to understand how this works, let’s take a look at the native layout of an object:

class Foo
{
  uint fooField;
  void print()
  {
    stdout::println("Hello, World!");
  }
}

class Bar extends Foo
{
  string barField;
  uint add(uint x, uint y)
  {
    return x + y;
  }
}

The first thing to point out is that Foo’s native representation is compatible with the start of Bar’s native representation. The differences between Foo and Bar are:

• The RTTI of the object is different. This means that it always gives the most-derived type of the object.
• The VFT pointers are different. VFTs are recalculated at run-time for each class, so that they always contain the most-specific methods for their run-time type. This adjustment is what makes virtual function tables useful, and the fact that it is done at run-time allows for methods to be overridden without breaking binary compatibility. (See also: Binary Compatibility²)

In order to create an instance of Bar, its allocator must allocate enough memory to hold it, and then fill in the RTTI pointers and the VFT pointers. Since it knows the most derived type of this new object, it can just copy these pointers from some LLVM global variables. Once it has been allocated, it can be passed into the constructor to be properly initialised by some user-defined code.

Run-time Type Information

Run-time type information, as already mentioned, is a block of data (stored in a global variable) that describes a particular type. All objects on the heap store a pointer to the RTTI block for their type, including arrays, objects, and all other types which have been cast to an object.

Some of the data stored in RTTI is quite interesting. There is the obvious byte representing the sort of type being represented (i.e. array, primitive, tuple, etc.), but there is also a special pointer to something called a VFT search list.

A VFT search list is a simple array of tuples, each containing a raw string ([]ubyte) and a pointer to a VFT. The string is the fully qualified name of a (super-)type of the actual run-time type, and the VFT pointer is for the VFT corresponding to that (super-)type. To explain why this is required, we must consider how interfaces are represented in code.

Interfaces are really just lists of (usually abstract) methods which are inherited by any classes deriving from them. The problem is that any class can implement an interface, and they do not have anything in common whatsoever in terms of object layout, so what is the native representation of an interface? The answer is that it must be a pointer to the object, combined with a VFT for all of the methods the interface declares. In LLVM bitcode, this is represented by a simple structure type (passed by value, not stored on the heap):

{ foo.bar.MyInterface_VFT* , object* }

So where does this VFT pointer come from? If we are converting from a type which we know implements this interface, we know exactly the offset to the interface’s VFT pointer, so we can just look it up. However, if we are casting from something else, such as object, we need to search somewhere for the pointer. This is where the VFT search list comes in: we know the fully qualified name of the interface we are casting to, so we can just look up the VFT in this search list. Of course, this is quite inefficient, but it is the only way to perform the cast correctly.

There is another reason to have VFT search lists, or at least the string part of them, and that is so that the instanceof operator can check whether a given class/interface makes up part of an object.

Calling Conventions

In order to call functions in native code, all of the arguments must be passed from the caller to the callee, either using registers or on the stack. These calling conventions are handled automatically by LLVM (although it is possible to specify whether to use the C calling convention or one of several others).

Plinth doesn’t really care which low level calling convention is used, as long as it is used consistently. However, it does care about the way that callees and arguments are passed into functions. One particular influence is the native representation of function types.

Function types are not just represented by a standard function pointer. This is because LLVM functions are essentially static, and passing just a function pointer would make it impossible to pass an instance method around. Instead, function types are actually a tuple of the function’s callee and the function to call on it. For example, if we translated the type of {uint -> boolean}, we would get the LLVM type:

{ opaque* , i1 (opaque*, i32)* }

Here, opaque* means a pointer to some structure we do not know the layout of. So now we can convert any object to an opaque*, and convert the method which takes it as a callee to a function taking an opaque* as its first argument. In order to call it, we pass the callee opaque* as the first argument to the function. This works for instance methods, but for static methods the cast won’t work unless we add an extra unused opaque* argument to the start of the argument list, and pass null as that argument whenever we call it; this is the calling convention for all static methods in plinth.

The most difficult calling convention to get right is the one for interface methods. What you might expect is that the interface callee is passed in the representation described above, as a tuple of a VFT pointer and an object pointer. Unfortunately, things are much more complicated in practise.

The main consideration is that interface methods can override methods from object or any super-interfaces, and can be overridden by methods from any sub-type. This means that in order to insert interface methods into a VFT, they must conform to the normal calling convention for instance methods: the callee must be a pointer to an object. This has the unfortunate side-effect that every interface method must begin with a cast from object to their own interface type, which (as mentioned above) requires a search through that object’s VFT search list.

A much more complicated system that I may investigate in the future might be able to avoid this search, at the cost of much more indirection for VFT pointers and method calls on interfaces. However, this could be precluded by concerns about binary compatibility.

1: If you run the compiler with the -d <output-dir> option, it will write them to files in that directory.

2: Since this post, the object representation has been changed to add RTTI, an object VFT for builtin methods, and interface VFTs.

Plinth has an extensive type system. As described in last week’s post, there are several different sorts of user defined types, but there are also lots of different sorts of built-in types:

Primitives

There are three main sorts of primitive type: integers, floating point numbers, and booleans. Integers have both signed and unsigned variants.

As in several other languages (and in contrast to C/C++), bytes are 8 bits, shorts are 16 bits, ints are 32 bits, and longs are 64 bits.

One thing to note is that there is no char type. This is because it would just be an alias for an integer large enough to hold all of the possible character code points (i.e. uint), and we may as well use integers instead. Character literals will be allowed, but they will be equivalent to an integer literal for the character code they represent (so writing ‘a’ will be the same as writing 97).

Arrays

Array types are written slightly differently than they are in most other languages. Here are a few array declarations and creations:

[]uint arrayOfUnsignedIntegers = new [5]uint;
[]?float arrayOfNullableFloats = new [9]?float;
[]string arrayOfStrings = new []string {"Hello", "Arrays"};
?[]#object nullableArrayOfImmutableObjects = null;

As you can see, this syntax allows us to represent the nullability and immutability of each part of the type precisely and unambiguously. With the postfix notation that most languages use, this sort of type would be much more difficult to understand.

Array accesses, however, are still postfix. This makes much more sense for indexing, since this way for multidimensional arrays the indices are in the same order as in the type signature:

[][]double matrix = new [2][10]double;
double lastValue = matrix[1][9];
[]double lastRow = matrix[matrix.length - 1];
double sameLastValue = lastRow[lastRow.length - 1];

If an array is nullable, array element (or even length) accesses on it are not allowed. You must first cast it to a not-null array type.

Tuples

Tuple types are written by enclosing a list of types in parentheses. They can be declared and assigned to as follows:

(uint, string) test = foo();
(?[]object, boolean) asdf = null, false;

The assignment syntax is quite flexible, and allows you to declare multiple variables at once, while extracting their values from e.g. a function call:

uint x, y = 5, 4; // this is equivalent to: (uint, uint) x, y = 5, 4;
x, y = y, x;
([]string, double) str, d = function();

Tuples can also be nullable:

?(uint, string) test2 = test;
?(bigint, double) tuple = check ? bigint(2), 5.3 : null;

There are two different ways to extract a single value from a tuple:

(bigint, string) values = getValues();
bigint large = values ! 1;                 // (the index into the tuple must be a constant value - calculations are not allowed)
(bigint, string) _, text = values;
large, _ = values;

Of course, splitting up a nullable tuple in this way is not allowed, you would have to cast it to not-null first.

Object

The object type is the super-type of all other types. It can be used as follows:

object nothing = object();
object integer = 5;
object tuple = 7, "hello";
?object nullable = null;
#object immutableArray = new [4]short;

As with several other types, objects can be nullable and/or immutable.

Objects are always stored on the heap. This means that in order to convert primitives, compound types, tuples, and functions to objects, we must store them on the heap, boxed inside objects. This is unfortunate, since this conversion is often implicit and is not at noticeable as a normal heap allocation using ‘new’ would be, but it is required in order to have a unified type system, and it is the only way of doing generics without templated code.

Some weird situations start occurring when you convert a compound type to an object. Compound types are usually passed by value, but when we store them as objects on the heap, all references to them will use the same instance of that object, bypassing the usual pass-by-value semantics.

Functions

Function types are written as a list of parameter types followed by a return type:

{uint, string -> void} foo = someMethod;
#{ -> string} toStr = 9.81.toString;

All methods can be accessed as function-typed values in this way. The interesting thing about function values is that they not only store a function pointer, but a pointer to the callee to call the function on. This allows you to pass around a method that changes some of an object’s state. For types which are not just pointers (i.e. primitives, compound types, tuples, functions), the callee is first stored as an object on the heap.

Functions can be nullable and/or immutable, but immutability means something different for functions than it does for objects and arrays. Objects and arrays have data-immutability, where an immutable value cannot have any of its data modified. In contrast, functions have method-immutability, in the sense that an immutable method cannot modify any global state. If you call an immutable function, you can be fairly sure that it won’t have any side-effects (modulo native methods and mutable fields).

Strings

string is actually just a compound type, but string values are special because they can be created by using string literals in double quotes, and because they can be concatenated using the + operator. Other than this, strings are an immutable compound type which has methods for common operations like finding the character at a given position, or finding its length.

Strings have full support for unicode; in fact, they are stored in UTF-8 by default because it usually uses much less memory than UTF-32. Since UTF-8 is a variable-length format, with a single character taking anywhere from one to six bytes, getting the length of a string is an O(n) operation. Under the hood, the string type lazily calculates the UTF-32 representation the first time it is needed (e.g. when finding the length), and stores it for later use.

Here is the source code for string, and some actual plinth code which isn’t just an example.

Next week’s post will be on plinth’s generated LLVM bitcode, and run-time type information.

Plinth has several different sorts of user-defined type: classes, interfaces, compound types, and (eventually) enums. In this post, I will talk about how each of them works.

Classes

Classes act much as they do in Java and C♯, with single inheritance of classes, but multiple inheritance of interfaces. They are allocated on the heap, and must be created with the new keyword, as follows:

class Foo extends Test implements Runnable
{
  uint value;
  static uint lastValue;
  this(uint value)
  {
    this.value = value;
    lastValue = value;
  }
  void run()
  {
    stdout::println(toString());
  }
}
// ...in a method somewhere...
Foo foo = new Foo(12);

Classes can have all of the different types of members: initialisers, constructors, fields, methods, and properties. All of these (except constructors) can optionally be static, which means they do not require an instance of the class to be used. Members of an instance of a class can be accessed using the . operator, but static members of a class must be accessed with the :: operator on the class’s type. For example:

foo.value = 8;
Foo::lastValue = 97;
foo.run();

Classes also inherit instance members from their super-classes and super-interfaces. All classes (and in fact, all types) get default implementations of certain methods, such as toString() and equals().

Something that all classes must implement is the set of abstract methods and properties which their super-types declare but do not define. One point that is worth noting here is that abstract methods may have implementations which are higher up in the class hierarchy than the abstract method itself (e.g. something may override toString() and make it abstract). In this case, any subclasses would have to provide their own implementation of that method (or use one from an interface – see the next section). This allows interfaces to specify that their implementations do not just use object.toString() or object.equals(...).

Interfaces

Interfaces are the feature I am currently working on. They will work quite differently from those in Java and C♯, in that they will be able to contain implementations of methods. This makes them very similar to mixins (thank you to William Berg for pointing me towards them).

All of their members will be abstract by default, unless an implementation of a given method is provided. They will not be able to contain any data (unless it is static), however they will be able to specify abstract properties that must be implemented by a subclass.

Interfaces will have full multiple inheritance, which is something that can be difficult to implement well. One reason for this is the well-known diamond problem, which is to decide where to look first for a method on an object of type D in the following class hierarchy (remember the method could be implemented on both B and C):

  A
 / \
B   C
 \ /
  D

This problem is fairly easy to solve by starting with the leftmost super-type and checking each parent from left to right in the list, giving the method resolution order of D, B, C, A.

A much more difficult problem is what happens in the following example:

A    B
| \ /|
|  /\|
| /  |\
|/   |/
C    D
 \  /
  E

It may not be clear from the ASCII art, but C extends A before B, whereas D extends B before A. Individually, C and D are well defined, but their subtype E is not. Suppose A and B both implement some method foo(), and something in C depends on inheriting A.foo(), but something else in D depends on inheriting B.foo(). In this case, whichever way around E inherits foo(), it will break something in either C or D.

To combat inconsistencies like this, I am using C3 linearisation to decide on a consistent order for inheritance, or fail in cases where the class hierarchy is inconsistent. This is the same system used by Python, and it also has the side effect that all super-classes of a class are searched before any of its inherited interfaces.

Compound Types

This is a type which I have still not finalised the name of, although its behaviour has been decided. They are very similar to value types, but I don’t want to make ‘value’ a keyword, so I will probably change it from ‘compound’ to ‘value_type’ at some point.

Their main property is that they are stored on the stack (or directly embedded in another object when stored as a field), and because of this, their values are routinely copied into new variables, rather than passed into a function by reference. The only exception to this is when they are the value which the function is being called on, in which case they must be passed by reference in order to allow the function to modify the value.

Due to their fixed size and object layout, they cannot have any form of inheritance (even interfaces). However, they can have all of the normal members that are allowed in classes.

Enums

Enums are a well known concept, but they can be implemented in very different ways. In C, C++, and C♯, they are syntactic sugar for integers, whereas in Java, they are a constant set of Objects. In plinth, they will be more similar to Java’s representation, which allows enum constants to store data.

However, there is a problem: each enum constant must be created statically, which means that there must be an order in which the enum constants are created. What happens if the constructor for the first enum constant tries to use the value for the second, before it has been created? This is a case where using C-style enums would be much easier. (In Java, the JRE ignores the problem and just allows the constants to be null before they are created – something I would like to avoid in plinth.)

The system I am currently considering for plinth is to disallow enums from storing any data which would need to be initialised (similarly to how static variables are already handled). This would mean that the enum constants could be allocated early, and if necessary they could be used safely before any of their constructors are called.

This scheme would make an enum extending a class impossible, because classes need to guarantee that they are initialised before use. However, interface inheritance (including mixins) would be possible.

Next week’s post will be about the rest of the type system, and how it all interacts.

Binary compatibility is a feature which is often overlooked in programming languages. These days, many languages use some form of interpreter or virtual machine (e.g. the JVM, Python’s interpreter, the CLR), which means they don’t have to deal with it.

However, in languages which compile to native code (e.g. C, C++, D, Plinth), there are often many restrictions on what a programmer can change in a library without breaking binary compatibility.

What is binary compatibility?

Binary compatibility relates to backwards compatibility for libraries. For a library to be backwards compatible, programs which were compiled against an old version of it should still work with a newer version, without crashing.

In practise, this means that a newer version of the library has to contain all of the same methods and fields that the old one contained. But not only that: the binary representation of every object must also be compatible, so for example the order of fields inside the binary object may not change. To illustrate the sorts of things you can and can’t do while maintaining binary compatibility, a list of rules for C++/Qt is here: KDE Binary Compatibility Dos and Don’ts

How does plinth handle binary compatibility?

Plinth tries to allow as much as possible. However, there will always be some constraints. For example, it will always be forbidden to remove a function which existed in a previous version. Here is a list of some of the things which can and can’t be done while maintaining binary compatibility:

You can:

• Add new static methods
• Add new static fields
• Add new non-static (virtual) methods, if you use a since(…) specifier
• Override a virtual method from a superclass, if you use a since(…) specifier
• Add new non-static fields to a sealed class (one which cannot be extended), if you use a since(…) specifier
• Add new type definitions (classes, compound types, interfaces, enums)
• Change an existing method into a native upcall or downcall
• Make a field or method more visible (e.g. change it from private to public)
• Reorder the fields or methods in a class
• Remove a private static field or method, if it is never used

You can not:

• Add a new non-static field to a class which is not sealed
• Change a since(…) specifier in a way that would change the order of fields or virtual methods
• Change a since(…) specifier on a constructor or a static method
• Change the type signature of a method
• Decrease the visibility of a field or method (e.g. change it from public to private)
• Remove a static field which could have been used externally
• Remove a static method which could have been used externally
• Remove a non-static field
• Remove a non-static method
• Remove a public class, or change it from public to package visibility
• Rename any types, fields, or methods

One important thing to point out in this list is that you can always add new virtual methods, and override existing ones. This is impossible in languages like C++, because they generally only have one virtual function table per object.

Virtual Function Tables (VFTs)

A virtual function table is just a list of pointers to functions. In languages like C++, every object which has virtual functions has a VFT to look them up in; inside the object is a pointer to that object’s VFT.

In order to call a virtual function, you must have a pointer to an object, and you must know the function’s index in the VFT. Given this, you can find the VFT by looking inside the object, and find the function by looking at this index into the VFT. Here is an example:

class Foo
{
  uint fooField;
  void print()
  {
    stdout::println("Hello, World!");
  }
}

class Bar extends Foo
{
  string barField;
  uint add(uint x, uint y)
  {
    return x + y;
  }
}

As you can see, Bar’s VFT has the same layout as Foo’s VFT, but with some extra methods added on the end. This makes it impossible to add virtual methods to Foo later on and maintain binary compatibility, because anything which extends Foo has to know exactly how many virtual methods Foo has in order to put its own methods after the end of that list.

So how does plinth manage to allow adding virtual methods? The key is to have several different VFTs, one for its actual class, and one for each class which it inherits from:

Now, since the VFTs are separate, Bar’s does not have to start with Foo’s. This means that, as long as you always add new virtual functions at the end of a VFT, then adding them is binary compatible. This is where since(…) specifiers come in.

Since Specifiers

Whenever you use a since(…) specifier, you provide a version number in brackets, such as since(8.4.2) or since(4.10). The compiler uses this to sort the methods before they are added to the VFT, so that methods with the largest since specifier will always go at the end of the VFT (methods without a since specifier always go at the start). So if you use a since specifier to add methods at the end of the VFT, adding methods is binary compatible.

Fields are more difficult, because each object must start with its superclass’s fields and VFT pointers. This makes it impossible to add new fields to a class which might be extended. However, if a class is sealed (i.e. it cannot be extended), then new fields can be added to the end of it without breaking binary compatibility. This is done in the same way as for virtual methods, by using a since(…) specifier.

Adjusting superclass VFTs

In the example above, there is a “Pointer to Foo’s VFT (adjusted for Bar)”. In that example the adjusting process had no effect, but when methods are overridden, this step is important as it ensures the correct method is always called. Consider this example:

class Foo
{
  uint fooField;
  void print()
  {
    stdout::println("Hello, World!");
  }
  since(1.8) uint add(uint x, uint y)
  {
    stderr::println("Foo.add()");
    return x + y;
  }
}

class Bar extends Foo
{
  string barField;
  uint add(uint x, uint y)
  {
    stderr::println("Bar.add()");
    return x + y;
  }
}

Without the adjusting process, if we had an object which we knew was a Foo but was actually a Bar as well, we would look in Foo’s VFT for the add method and call Foo.add(), even though the actual object was a Bar – defeating the purpose of virtual functions entirely. With the adjusting process, we would call Bar.add() through the adjusted VFT.

But what if we compiled Bar against version 1.7 of Foo, and then ran it with version 1.8? If the adjustment happened at compile time, the adjusted VFT would only have one element: “Foo.print” (since that’s all that existed in version 1.7), and so calling Foo.add() would make us crash.

Clearly, the adjustment needs to happen at run time, and this is exactly what plinth does. Before execution of any code, plinth will go through each superclass method and search for any overrides of it in subclasses. It does this using VFT descriptor tables which are stored along with the original VFT for that class.

Static members and constructors

During compilation, static members are translated into global variables and functions. This means that accessing them never depends on the layout of an object. Because of this, we can easily have more than one version of a static method in the same class.

Imagine you have a static method which performs something badly, which you want to deprecate and replace with a newer version which does things slightly differently. Usually, you would have to change the name or the type signature of the method so that code compiled against the old version of your library would still work, while forcing new code to use your new version. However, with plinth you can just create a new version of the method with a more recent since specifier. This allows both versions of the method to exist in the library, but things compiled against this version will always use the most recent one, and using older versions of the method is not possible when a new once is available.

The same thing is possible with constructors, since they are called in the same way as static methods, without using a VFT. Static fields are not affected at all by since specifiers (although they are allowed), since only one field can exist with any given name.

Other considerations

Plinth is built with binary compatibility in mind throughout, and features which could cause compatibility problems are avoided where possible.

For example, my last post was about nullability and initialisation. In the Freedom Before Commitment scheme that was outlined in the Summers & Müller paper, the check for whether an object had been initialised depended on which of the fields inside that object had been initialised. The problem with this is that when you call a constructor, you do not necessarily know about all of the fields of the object. In particular, new fields could have been added to the end of a sealed class, which could allow a new object to be used before all of the new fields were initialised. To combat this, the proposal outlined in last weeks post did not allow not-null fields to be first initialised outside a constructor – constructors must always give values to all not-null fields.

Next week’s post will be about interfaces and how they are implemented.

Nullability is a feature that allows you to specify whether or not something can be null. This is useful because it allows the language to enforce that access to a field or method is via a non-null value. This should make NullPointerExceptions a thing of the past!

In fact, the only place in plinth where you might get a run-time error because of a null value is when you cast from a nullable type to a not-null type.

Let’s start by looking at some of the things we can and can’t do with nullable values (the ?: and ?. operators are based on those in languages like Groovy):

// casting between null and not-null values:
Foo foo = new Foo();
?Foo nullable = foo;
Foo notNull = cast<Foo> nullable; // throws a run time error if nullable is null

// accessing fields and methods:
stdout::println(nullable.someText); // error: cannot access a field on a nullable object
nullable.doSomething(); // error: cannot call a method on a nullable object

// the null coalescing operator (giving a default value):
?uint index = null;
uint notNullIndex = index ?: 0;

// the null traversal operator:
// (the result is always null if the left-hand-side is null)
?string str = null;
?string subString = str?.substring(0, 2); // method call (the arguments are only evaluated if str is not null)
?#[]ubyte bytes = str?.bytes; // field access
?{string -> boolean} equalsFunc = str?.equals; // method access

Before I implemented nullability in Plinth, every type was not-null, including custom type definitions. The main thing you need to consider with not-null fields is that they have no default value; this makes plinth’s default behaviour very different from most major object oriented languages.

Because some fields have no default value, they must be initialised before the end of the constructor. In fact, they must be initialised before the newly allocated object could possibly be accessed from outside the constructor. This means that, until all of the fields of this have been given values (or have default ones like zero or null), the value of this cannot escape the constructor. In plinth, making sure of this amounts to stopping people from using this (except for things like this.field = value;) and stopping people from calling non-static methods.

So far this is all fine, but what happens when we have two (or more) classes which need not-null references to each other? This problem is difficult to solve, for a number of reasons. I’ll use the following as a very simple example:

class A
{
  B b;
  this(B b) // <-- constructor
  {
    this.b = b;
  }
}
class B
{
  A a;
  this(A a)
  {
    this.a = a;
  }
}

Obviously, in this scenario, one of the constructors must always be run first. This seems like it makes it impossible to create either of them, but let’s suppose that we have a way of allocating an object without calling its constructor. When an object has just been allocated, it’s still ‘uninitialised’ until its constructor has been run. Now, if we could pass an uninitialised object into another constructor, we might be able to do something like this:

uninitialised A allocA = alloc A;
uninitialised B allocB = new B(allocA);
A a = new (allocA) A(allocB); // creates an A inside allocA, like C++'s placement-new operators
B b = allocB;

But now we have more problems. B’s constructor can’t let this escape until all of the fields are initialised, but now after it’s done this.a = a; it can do whatever it wants, including letting ‘this’ escape and trying to access data inside a (which still hasn’t been initialised yet). We need to mark that the constructor can take certain uninitialised values, and then make sure that it can’t let ‘this’ escape even after everything’s been initialised. We could do this with an ‘uninitialised’ modifier:

class B
{
  A a;
  uninitialised this(uninitialised A a)
  {
    this.a = a;
  }
}

Now, we know exactly what isn’t allowed to escape: ‘this’ and ‘a’ (we only allow uninitialised parameters in uninitialised constructors). Then, once we’ve created allocB, we know that it being initialised depends only on allocA being initialised, since it is the only uninitialised argument.

Next, we call the constructor on allocA, to produce a (A’s constructor will have to be modified the same way as B’s). We now also know that allocA being initialised depends only on allocB being initialised. We know the dependency cycle! All that we need to do is find the solution which makes the most things initialised (i.e. the greatest fixpoint of these simultaneous equations). Then we will know that both of them are initialised, thus allowing the assignments to a and b.

This scheme is based loosely on some discussions with and papers recommended to me by James Elford, in particular the Freedom Before Commitment paper[1]. However, it is not yet anywhere near implemented in plinth, for several reasons:

• I’ve just come up with it recently, and I have lots of other things before it on my to-do list (interfaces! properties! exceptions!).
• Processing the type system for uninitialised values would be extremely complicated, and would involve each type having a list of things which its initialisation state is conditional upon. I’d like to fill in the rest of the type system before adding this complexity.
• It can be easily added later. The only things which would not be backwards compatible with the current language are the keywords.
• There are workarounds which can be used in the mean time (see below)

That said, this cyclic initialisation scheme is something I would very much like to implement eventually, once all of the problems with uninitialised variables have been well-thought-out.

The slightly ugly workaround which can be used until this scheme is implemented is to have a nullable field and a property to access it. This will give a run-time error whenever a field is accessed on a not-properly-initialised object:

class A
{
  ?B realB;
  property B b
    getter { return cast<B> realB; }
    setter { realB = value; };

  this()
  {
  }
  void setB(B b)
  {
    // this method is only necessary if we make property's setter private
    this.b = b; // calls property setter
  }
}

Next week’s post will talk about binary compatibility, and how objects in plinth are represented in LLVM bitcode.

References:
[1] Summers, Alexander J., and Peter Müller. “Freedom Before Commitment.” (2010).