Tuesday, March 26, 2013

King Null the Stubborn

It's mostly pretty easy to eliminate null in a language: just replace it with Maybe/Option types. Unfortunately it's only mostly easy to get rid of null that way in class based OO languages. There's one corner where null is surprisingly stubborn without limiting OO languages: initialization. I'll demonstrate using Java but I'll show that the same or similar problem can manifest in most class based mainstream OO languages.

Java

class Base {
  public Base() {
    System.out.println(message().length());
  }

  public String message() {
    return "Hello";
  }
}

class Sub extends Base{
  final String msg;

  public Sub() {
    msg = "HI!";
  }

  @Override public String message() {
    return msg;
  }
}

class Test {
  public static void main(String[] args) {
    new Sub();
  }
}

And that crashes with a nice null pointer exception even though null is nowhere to be found.

The null stems from a few simple rules:

  1. fields not initialized at their declaration are initialized to null.
  2. super constructors execute before sub class constructors.
  3. method invocation in a constructor exhibits the same runtime polymorphic method dispatch that you expect from method invocation outside of constructors.

So the Base constructor executes, calls the message implementation on Sub, which returns the msg field, but it's only been initialized to null, and kaboom.

Other OO Languages

Ruby and Python can exhibit a pretty similar problem, here some Ruby.

class Base
  def initialize
    puts message().size
  end

  def message
    "Hello"
  end
end

class Sub < Base
  def initialize
    super
    @msg = "HI!"
  end

  def message
    @msg
  end
end

Sub.new

Once again we get a null (well nil) related exception. The difference is that in Ruby and Python you have to explicit about calling the super class constructor and you have more flexibility about the placement of that super call, so the Ruby code can be fixed by writing

class Sub < Base
  def initialize
    @msg = "HI!"
    super
  end

  def message
    @msg
  end
end

But the point is that there's nothing preventing the "bad" version from being written.

Scala and C# work like the Java version. Scala has an extra wrinkle of having "abstract vals." C# has the small variation that methods aren't dynamically dispatched unless explicitly defined to be.

C++

Finally we get to the one mainstream OO language that has a guaranteed-to-work static solution for at least one part of the problem: C++ (1)

#include <iostream>
using namespace std;

class Base {
public:
  Base() {
    cout << message() << endl;
  }

  virtual string message() {
    return "Hello";
  }
};

class Sub : public Base {
private:
  string* msg;

public:
  Sub() {
    this -> msg = new string("HI!");
  }

  virtual string message() {
    return *msg;
  }
};

int main(int argc, char** argv) {
  Sub sub;
}

If you don't feel like compiling and running that then I'll cut to the chase: it prints "Hello". That's because in C++ 'this' is constructed in stages and during the Base constructor 'this' is only a Base and not yet a Sub. Even a variant which explicitly passes 'this' around will print 'Hello'

class Base {
public:
  Base(Base* self) {
    cout << self -> message() << endl;
  }

  virtual string message() {
    return "Hello";
  }
};

class Sub : public Base {
private:
  string* msg;

public:
  Sub() : Base(this) {
    this -> msg = new string("HI!");
  }

  virtual string message() {
    return *msg;
  }
};

C++'s rule works very well to prevent many uninitialized 'this` problems, but the downside is that it prevents some perfectly good code from working polymorphically. The following still gets "Hello" even though "HI!" would cause no problems.

class Sub : public Base {
public:
  virtual string message() {
    return "HI!";
  }
};

Which is a perpetual source of confusion.

The Big Hole

C++'s rule goes far, but it doesn't go far enough. If you're lucky the following code will seg fault. Formally it's completely undefined what will happen. In other, more safe languages, it will be a null pointer exception.

void dump(Base* base) {
  cout << base -> message() << endl;
}

class Sub : public Base {
private:
  string* msg;

public:
  Sub() {
    dump(this);
    this -> msg = new string("HI!");
  }

  virtual string message() {
    return *msg;
  }
};

Leaking 'this' out of a constructor is a known bad idea, but I don't think any mainstream-ish OO languages prevent it.

Nor does C++'s rule prevent doing something silly in a constructor like {string x = *msg; msg = new string("hello"); cout << x}

Conclusion

So there you have it, null is mostly preventable using Option/Maybe types. But to get rid of it entirely a class based OO language would need to

  1. limit the polymorphic dispatch on objects that are under construction like C++ does, and
  2. statically eliminate references to fields that aren't yet initialized in a constructor (e.g. {x = y; y = "hello";} needs to be prevented)

It would also have to do one of the following:

  1. prevent 'this' from leaking out of a constructor
  2. or only let 'this' leaking from a constructor represent the part of the object that has been fully initialized, e.g. a 'this' leaking from Sub's constructor must be a Base just as it is during Base construction.
  3. or require that all fields be initialized immediately at declaration site (or use an equivalent mechanism like C++'s initializer lists)(2)
  4. or do expensive whole program analysis to ensure that a leaking this isn't a problem

That's what it would take to make null go away. But it would also prevent perfectly good code from either working as desired or compiling at all.

Footnotes

  1. I'm avoiding initializer lists and needlessly using "new" and pointers on C++ strings to illustrate my point. If that bothers you then pretend I'm using something where pointers are actually useful. I should also be doing copy constructors, assignment operators, virtual destructors and all that other fun C++ stuff, but all that boilerplate would be a distraction from my point here.
  2. If you squint just right, the 'every field initialized at declaration site' rule is exactly how many statically typed functional languages like Haskell and ML deal with 'records' and algebraic data type constructors without requiring a null like construct for uninitialized fields.