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.

15 comments:

  1. You say it would prevent "perfectly good code" from working, but isn't the code "perfectly good" only because it compiles with today's languages? Of course, there are places where e.g. passing this around (while knowing the potential pitfalls) makes things easier.

    ReplyDelete
  2. Sam Tobin-HochstadtMarch 26, 2013 at 2:42 PM

    My colleague Richard Cobbe wrote his dissertation on eliminating `null` from OO languages, dealing with issues like this: http://www.ccs.neu.edu/racket/pubs/dissertation-cobbe.pdf

    ReplyDelete
  3. This is a great discussion, thanks.

    "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."

    I either never realized or forgot that it worked this way in C++. I really like this idea. It seems like the proper way to scope initialization.

    ReplyDelete
  4. Also in the design space, the language could check for reads from uninitialized variables. Instead of giving you a null, it could throw an exception.

    The implementation would use similar tricks to lazy vals, where a bit field is stored on the side for whther the field has been initialized.

    In some cases, static analysis could allow optimizing away the initialized bit.



    In the case of Scala, this would not be enough to get rid of null, because there is the teency little issue of interop with existing Java libraries....

    ReplyDelete
  5. See how Objective Caml safely constructs objects by requiring all member variables to be explicitly initialized prior to dispatching any methods in the object initializer.

    ReplyDelete
  6. None or Nothing.

    If something can be nothing, let nothing be a legit value!

    ReplyDelete
  7. Calling non final methods from a constructor is well known to cause problems, as is letting this escape during construction, which is why editors mark your code with warnings when you write it like that. Put your example into IDEA and it will light up like a christmas tree. Not really sure what you trying to show here!

    ReplyDelete
  8. You should take a look at how Dart constructors work. Dart has initializer lists that ensures all final fields are initialized before the constructor body, so even though 'this' can leak out of the constructor it's not a problem. This does prevent circular references from being final, however.

    ReplyDelete
  9. I've seen some Microsoft Research paper where they investigated a possibility for eliminating null from C#. It basically was done with elaborating the notion of "not-initialized variable/field", and annotating object's methods as "may work during intialization" or "call on fully initialized objects only", if I remember correctly.

    ReplyDelete
  10. Alexander KosenkovApril 2, 2013 at 1:23 AM

    Have you heard about Kotlin? It's a JVM-based language from JetBrains with built-in zero-overhead null-safety. It's not possible to get NPE there unless you explicitly throw it :-)

    http://confluence.jetbrains.com/display/Kotlin/Null-safety

    ReplyDelete
  11. Here is that paper: Manuel Fähndrich, K. Rustan M. Leino, "Declaring and Checking Non-null Types in an Object-Oriented Language", http://research.microsoft.com/en-us/um/people/leino/papers/krml109.pdf .

    ReplyDelete
  12. One of the JSR308 checkers makes a distinction between "raw" (under construction) and "cooked" (i.e. fully-constructed) objects, and you pass this through the type system in the same way as a distinction between nullable and not (i.e. polymorphic methods that you want to be callable during construction must be explicitly annotated as such, and it is an error to access a field that is not initialized at declaration site within a method so annotated, or call a method not so annotated, and if you store this in a variable or pass it to a method then that method or variable must declare it takes a raw type and the same constraints apply to it). I think that's more elegant than any of the approaches you list here (though obviously it would be much better to have it fully integrated into the language than in an external checker).

    ReplyDelete
  13. "require that all fields be initialized immediately at declaration site"

    And that's called: dependency injection. And works great !

    ReplyDelete
  14. using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleApplication1
    {
    public class Base
    {
    public Base()
    {
    Console.WriteLine(message().Length);
    }
    public virtual string message()
    {
    return "Hello";
    }
    }
    public class Sub : Base
    {
    string msg;
    public Sub()
    {
    msg = "HI!";
    }
    public override string message()
    {
    return msg;
    }
    }
    class Program
    {
    static void Main(string[] args)
    {
    new Sub();
    Console.Read();
    }
    }
    }

    ReplyDelete
  15. I did squint, but it was because you did not delete msg in a destructor.

    ReplyDelete