The Yak Shaver's Creed

This is my yak. There are many like it,
but this one is mine.

My yak is my best friend. It is my life.
I must shave it as I shaved the one
before.

Without me, my yak is hairy. Without my
yak, I am productive. I must shave my
yak cleaner than the previous yak.

I must shave him before his hair grows
back. I will...

My yak and I know that what counts in
code is not the lines we write, the
cycles we burn, nor the data we process.
We know that it is the hair that counts.
We will shave...

My yak is human, even as I, because it
is my life. Thus, I will learn it as a
brother. I will learn its weakness,
its strength, its parts, its hooves,
its horns, and its hair. I will get my
yak shaven, even as the last was shaven.
We will become part of each other. We
will...

Before Finagle, I swear this creed. My
yak and I are the productivity blockers.
We are the unpassable wall. We are
holding up release. So be it, until the
code is shipped and there is no yak,
only hair!

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.

• Like this
• and this
• and this

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.

The Best-Laid Schemes O' Mice An' Constructors Gang Aft Agley

Last time I talked about how the Scala compiler currently translates try/catch expressions used as arguments to method or constructor call into separate method definitions which in turn may require boxing of mutable variables. That's because an exception in the try would blow away the local stack of stuff needed to make the original method/constructor call. So I proposed a plan for the Scala compiler to translate

expr0.foo(expr1, try/catch)

into

val temp0 = expr0
val temp1 = expr1
val temp2 = try/catch
t0.foo(temp1, temp2)

And to do that recursively as needed.

The Flaw

It was a great plan. A beautiful plan. It had only one flaw. Under some circumstances it would change the behavior of some constructors calls. To understand why we need to look at some JVM bytecode.

At the bytecode level, the constructor call

val foo = new Foo(expr1, expr2,...)

looks like(1)

new Foo
dup
// compute the result of expr1 and leave on stack
...
// compute the result of expr2 and leave on stack
...
invokespecial Foo.init
store foo

Which may need some explanation. The first instruction, "new Foo", creates a new, uninitialized Foo object but does not invoke its constructor. A reference to the uninitialized object is left on the top of the local stack. Then dup duplicates the top of the stack so now there are two references to the uninitialized object. Then a series of instructions computes the results of the arguments to the constructor, leaving each result at the top of the stack in turn (and pushing down the previous stuff). Finally, Foo's constructor is called which consumes all the constructor args and one reference to the Foo object. After the constructor is done, what's left behind on the stack is one reference to the now initialized Foo object. The store instruction consumes that and stuffs it into the foo variable.

If expr2 were a try/catch and my proposed transformation were to kick in, then that would look like

// compute the result of expr1 and leave on stack
...
store temp1
// compute the result of expr2 and leave on stack
...
store temp2
new Foo
dup
load temp1
load temp2
invokespecial Foo.init
store foo

At first glance that would appear to solve the problem nicely: the order of effects between expr1, expr2, and Foo's constructor is all preserved. Right? Sigh.

You see, the bytecode instruction "new Foo" potentially has a visible side effect. That's because it can cause Foo's static initializers to fire if they haven't already. In the original, inline version, the static initializers would have their effect before expr1 and expr2. In the second version the static initializer might happen after. Here's a bit of Java code that demonstrates the difference.

public class Sample {
  static class Foo1 {
    static { 
      System.out.println("Foo1 static init"); 
    }
public Foo1(int arg1, int arg2) {
      System.out.println("Foo1 constructor"); 
    }
  }
  static class Foo2 {
    static { 
      System.out.println("Foo2 static init"); 
    }
public Foo2(int arg1, int arg2) {
      System.out.println("Foo2 constructor"); 
    }
  }
static int expr1() {
   System.out.println("expr1");
   return 1;
  }
static int expr2() {
   System.out.println("expr2");
   return 2;
  }
public static void main(String[] args) {
    System.out.println("static init comes first.");
    Foo1 foo1 = new Foo1(expr1(), expr2());
System.out.println();
    System.out.println("static init comes later.");
    int temp1 = expr1();
    int temp2 = expr2();
    Foo2 foo2 = new Foo2(temp1, temp2);
  }
}

I wrote that in Java because Scala doesn't have static initializers (the equivalent is done via constuctors on declared objects). Which might make you think "then who cares." But, Scala has to inter-operate with Java. So we need a plan.

Plan 1 (which won't work)

It's tempting to try to stuff the uninitialized object into a variable before dealing with the args.

new Foo
store temp0
// compute the result of expr1 and leave on stack
...
store temp1
// compute the result of expr2 and leave on stack
...
store temp2
load temp0
dup
load temp1
load temp2
invokespecial Foo.init
store foo

That looks beautiful but, sadly, it is expressly forbidden by the JVM spec to have a ref to an uninitialized object in a local variable when a catch block is executed. The bytecode verifier will reject that approach outright.(2)

Plan 2 (which is annoying, quite probably slow, and may not work everywhere)

So we need to force class initialization early. One way way to do that is Class.forName. So now we have this

ldc classOf[Foo]
invokevirtual Class.getName
iconst_1 // push `true` onto the stack
invokevirtual Class.getClassLoader
invokestatic Class.forName
pop // throw away the class object that results from Class.forName
// compute the result of expr1 and leave on stack
...
store temp1
// compute the result of expr2 and leave on stack
...
store temp2
new Foo
dup
load temp1
load temp2
invokespecial Foo.init
store foo

That's a lot of code coming out of one measly constructor call! To some extent that can be mitigated by creating a static helper method in the runtime library and calling that instead. But that doesn't entirely mitigate a performance concern. How fast is Class.forName? The answer will take some benchmarking but I'll bet right now it's a whole lot slower than code without it.

Even ignoring pefromance concerns Class.forName has a potentially fatal flaw: security managers might very well prevent it. So library A happens to trigger this transformation and company B can't use the library because of a policy decision about restricting Class.forName.

Plan 2b (which might help a bit with Plan 2's slowness but definitely won't work everywhere)

A solution related to Plan 3 is to use sun.misc.Unsafe.ensureClassInitialized. It's a much simpler interface than Class.forName and is likely closer to the underlying mechanism to do class initialization win the "new" instruction. The problem is that it's not portable to all JVMs and it's even more likely to be hidden away by a security manager.

Plan 3 (which is so crazy it just might work)

A realistic possibility, which is a bit crazy, is to create an uninitialized object then throw it away which would force static initialization but wouldn't call the constructor.

new Foo // ensure initialization
pop // throw that object away, we don't need it
// compute the result of expr1 and leave on stack
...
store temp1
// compute the result of expr2 and leave on stack
...
store temp2
new Foo
dup
load temp1
load temp2
invokespecial Foo.init
store foo

Which looks distinctly WEIRD but it's valid bytecode and gets the job done. The annoying factor with this one is that it can only be expressed in bytecode so either the whole transformation has to be done at a very low level or we would have to add a new node type to the Scala AST which is used solely to express "force static initialization of thus and such class" and then let the code gen phase translate that to a new/pop pair.

There's also a bit of concern that it's TOO weird. It's valid by the spec, but it's nothing javac would ever spit out so it's entirely possible that some JVM implementation somewhere would be very confused by it.

Plan 4 (which is scary, but has some merit)

The final possibility is to ignore the problem. Scalac could just reorder expr1 and expr2 to come before the new and leave it at that. It's not something that most Scala programmers would ever even notice. The very few it does affect can manually do whatever translation they want to get their static initializers to fire at the right time. Perhaps the -Xlint flag could issue a warning about static initializer order when the transformation takes place.

But then again, the reason for the re-ordering will be pretty non-obvious so the few it does affect will likely struggle with it for awhile, then decide Scala is just broken without ever seeing what's behind -Xlint.

What Now?

Hopefully this has been an illuminating romp into some of the innards of compiling for the JVM. The immediate plan is that Scala will continue to turn problematic try/catch expressions into method definitions which will occasionally mean a bit of extra boxing. In the grand scheme of things that perf hit is probably small enough and rare enough to keep this whole experiment at a low-ish priority. Still, when I have some time I'd like to go see what other JVM language with try/catch expressions are doing here. They might have figured something out that I haven't.

Footnotes

1. I'm using javap as a guide for how to disassemble bytecode. But I'm keeping variable names and class names and ignoring details about variable slots and the constant pool that aren't important for this discussion.
2. Why is it not valid? The simple answer is "because the spec says so." Specifically it says "There must never be an uninitialized class instance in a local variable in code protected by an exception handler." But the underlying reason for that restriction isn't entirely clear to me. JVM bytecode is statically typed. The JVM's type system is just very peculiar by the standards of mainstream statically typed languages. The type checking is (a part of) the bytecode verification process. In the verifier, every variable and stack slot gets one static type over a static region of the bytecode. In different regions those types are allowed to be different, but when flow through the two regions converges all the types must be consistent. Now, the verifier thinks of an uninitialized Foo as a distinct type from an initialized Foo. Calls to a constructor (init) are the magic that turns an uninitialized and thus unsafe to use Foo in one region into one that is initialized and thus safe to use in another region. Which is all good. Except for some reason the uninitialized to initialized transition has been special cased for exception handlers rather than treated as just another type-state change to a variable that must converge consistently. Perhaps there was concern over the runtime cost of a more complicated verification rule. Or perhaps there was some soundness hole they didn't think they could plug. I dunno. Whatever the cause I have to go to war with the army I have not the army I wish I had.

Scala Try/Catch Lifting Proposal

TL;DR

Scalac currently deals with try/catch on a potentially non empty stack by lifting to a def. But that can lead to more boxing of vars captured in the lifted defs and a second pass to deal with try/catches that get put into the boxing constructor. I propose we use local vals to lift try/catch expressions instead of using defs. That will prevent the extra boxing and, perhaps later, allow us to inline more code.

Background

Scala makes try/catch an expression. But the JVM is actively hostile to using try/catch as an expression because the instant a throw happens the local stack frame is erased. So if we naively expand try/catch then an expression like "foo(bar(), try/catch)" leads to different stack heights before foo is finally applied. The "main" branch has both "this" and the bar() result on the stack, the catch branch does not. Boom, bytecode verify error. In fact that has been a source of several bugs as we've missed some corner case or other involving try/catch. In particular, nested try/catch can also break us in things like in foo(bar(), {val x = 42; blurg match {case whatever => if(something) x else try/catch}}) where the try/catch is nested in an if/else in a match in a block.

Current Situation

Currently UnCurry looks for try/catch in a spot where it could cause this problem and lifts such try/catch expressions into defs. In
other words

foo(bar(), try a catch {case b => c})

becomes

def liftedTry1 = try a catch {case b => c})
foo(bar(), liftedTry1)

And that's fine. But there's a nasty wrinkle. If the try/catch refers to a local var then suddenly that var is a captured var that needs boxing. That's a boxing that a user would probably not predict without a very subtle understanding of Scala internals.

Further, the boxing, which happens in LambdaLift, may well lead yet again to try/catch on a non-empty stack.

var x = try a catch {case b => c})
foo(bar(), try x catch{...})

After UnCurry

var x = try a catch {case b => c})
def litedTry1 = try x catch{...}
foo(bar(), liftedTry1)
After captured var boxing in LambdaLift

var x = new IntRef(try a catch {case b => c}))
def litedTry1 = try x.value catch{...}
foo(bar(), liftedTry1)

Having the try/catch in the constructor call means it's going to end up on a non-empty stack. To deal with that LambdaLift does a post-transform step to deal with try/catch yet again.

var x = try new IntRef(a) catch {case b => new IntRef(c)}))
def litedTry1 = try x.value catch{...}
foo(bar(), liftedTry1)

And again that post-transform needs to be smart about try/catch nested inside things.

Proposal Outline

I propose that we get rid of the try lifting logic in both UnCurry and LambdaLift and defer it to a later phase. That phase would look for try/catch problems and, when found, transform into local vals. An example:

val r = quux().foo(bar(), try a catch {case b => c}), baz())

So finding a try/catch inside an expression on a non-empty stack, we need to transform to local vals like so:

val r = {
  val temp0 = quux()
  val temp1 = bar()
  val temp2 = try a catch {case b => c})
  temp0.foo(temp1, temp2, baz())
}

It's important that quux() and bar() get evaluated and stuffed into vals in order to preserve order of evaluation. (By-name translation will have long since been done, so it need not be considered here)

We also need to deal recursively with nested try/catch

val r = quux().foo(bar(), qwerb().flurb(try a catch {case b => c})), baz())

step1:

val r = {
  val temp0 = quux()
  val temp1 = bar()
  val temp2 = qwerb().flurb(try a catch {case b => c}))
  temp0.foo(temp1, temp2, baz())
}

That leaves a try/catch expression on a non-empty stack, so
step2:

val r = {
  val temp0 = quux()
  val temp1 = bar()
  val temp2 = {
    val temp4 = qwerb()
    val temp5 = try a catch {case b => c})
    temp4.flurb(temp5)
  }
  temp0.foo(temp1, temp2, baz())
}

Details still need to be worked out. The existing logic in UnCurry seems to be a good starting point for finding problematic try/catch, though.

Inlining

The main body of the proposal stands alone and I think it's worth while no matter what. But it may allow some improvements in inlining

Because we want to inline code that may already be compiled, we defer inlining until we're working with i-code. As part of its analysis the inliner examines the code it wants to inline to see if it has any exception handlers. If it does then it refuses to inline the code into a spot that has a non-empty stack. In other words, it's a third place we deal with problematic try/catch, but this time by refusing to inline.

I propose that after try/catch lifting is implemented via local vals, we can make inlining decisions earlier in the compiler, perhaps right after UnCurry. Under this scheme, if we decide we want to inline then we would carry around a node representing the to-be inlined code. Then, when we get to the try/catch lifting phase it conservatively treat the code like any other node that has a try/catch, lifting to a local val if a potential try/catch would be problematic. Then the inlining phase would do the actual inlining.

Besides allowing code with exception handlers to be inlined, with this second part of the proposal the compiler should have to do less work over all. Currently we do a lot of work analyzing and transforming lambdas that may eventually be transformed away by the inliner.

I have to admit this second part of the proposal has no meat on it. It's not clear it's even workable. But it is at least some argument supporting lifting try/catch with local vals.

QR Flyer

(click to embiggen)

Checked Exceptions Might Have Their Place, But It Isn't In Java

In Java's more than 15 years no language has repeated Java's experiment with checked exceptions, other than some languages designed as Java extensions (e.g. MultiJava and GJ). Certainly no mainstream or even nearly mainstream languages have. Notable languages that don't bother with checked exceptions include C#, which started as very nearly a clone of Java, and Scala, which borrows many Java concepts and then beefs up their static type checking.

Even within the Java community checked exceptions have been at least somewhat deprecated. Spring and Hibernate, for instance, moved strongly away from checked exceptions. Bruce Eckel, author of Thinking in Java, considers them a mistake and Joshua Block, author of Effective Java, cautions against overuse.

Now, I've seen lots of arguments that you should "use checked exceptions when the caller must somehow recover." But that argument assumes that Java is basically a procedural language. It's not. It's an object oriented language where reusable abstractions are common. Just a couple of examples from the standard Java library reveals exactly what's wrong with Java's checked exceptions.

The java.util.Iterator methods, for instance, aren't declared as throwing any checked exceptions. If you create your own Iterator that calls a throwing method then the implementation must do a try {...} catch (CheckedException e) {throw new UncheckedException(e)}. Or worse, you swallow the exception. Either way it's boilerplate.

On the flip side, to avoid that problem the call method on the java.lang.Callable interface declares that it might throw "java.lang.Exception". But Exception tells you nothing about what might fail making it exactly equivalent to the unchecked RuntimeException except that you must "handle" it by either redeclaring it in the throws clause (which just pushes the problem upstream) or doing the try/catch/rethrow-unchecked dance. Again more boilerplate. Or, again, more opportunity to swallow.

You might think generics give a way out of the quagmire, but Java has a fatal flaw here. The throws clause is the only point in the entire Java language that allows union types. You can tack "throws A,B,C" onto a method signature meaning it might throw A or B or C, but outside of the throws clause you cannot say "type A or B or C" in Java. So if you have "interface MyInterface<T extends Exception> {void mightThrow() throws T...}" then T must be bound to a single exception type for any given instantiation of MyInterface. And, as special bonus, with that structure you can't say some particular implementation doesn't throw at all. Which means that in practice it's little better than the java.lang.Callable "throws Exception" solution.

The team working on lambdas for Java has found checked exceptions a major stumbling block essentially for the reasons outlined here. A significant amount of work is going into easing that pain

In short, as it stands the design of the Java language requires you to either avoid reusable abstractions or wrap useless checked exceptions in boilerplate. And if I want to avoid reusable abstractions then I know where to find Pascal. Could checked exceptions be made workable? Perhaps with some careful language design. But Java isn't that design.

Too Dense?

With this post I want to ask a question: what does it mean for code to be "too dense?" This question has implications on everything from languages to APIs to coding style.

I've seen debaters defending Java's verbosity precisely because it isn't "too dense." They say the sparsity of the code makes it easy to understand what's going on. Similarly it's common to bash programmers for playing "golf" when their code is dense. But if we're allergic to density then why do programmers seem to prefer to use tools that create code density when there are fairly straightforward ways to create less dense code?

For an example I'm going to use regular expressions(1) since just about every programmer knows what they are, they're very dense, they exist in direct or library form for every general purpose programming language, and they are easy to replace with "normal" code.

Regexes are tight little strings that have very little in the way of redundancy. They're frequently accused of being "write only" - impossible to read and maintain once written. They are the poster children for "too dense" if anything is.

With the modern-ish focus on refactoring and the understanding that code is read far more often than it is written then if regexes are too dense you'd think programmers would be eager to replace those dense strings with more standard code just to improve readability. After all, a regex encodes a simple state machine or perhaps something a bit stronger if the common Perl-ish extensions are used, so replacing them is easy.

Yet it doesn't happen, at least not much. Regexes remain a mainstay. New regexes are continually written and old ones aren't ripped out and rewritten as loops and if statements just to gain some more readability. They're expanded for performance reasons or when the logic needed exceeds the power of regexes, but they almost never get replaced with an explicit state machine just to improve maintainability.

Why is that? We can't blame a few bad programmers. Regexes are far too widely used for that simple cop out.

What regexes and our use of them suggests is that we're not allergic to density in information per character but to something else. One culprit is is simply unfamiliarity. Regexes are okay because we're familiar with them, other forms of density are bad because we're not familiar with them.

But maybe it's even stronger than that. Perhaps the familiarity with regexes makes us aware of a different kind of density/sparsity trade off. A regex's information density may make it slower to read in terms of characters per minute but we know that expanded code would be slower to read in terms of concepts per minute.

In this post, I picked on regular expressions because they're so widely known and used but the bigger question is in the design of languages, APIs, and coding conventions. This article started with a question and will end with more. Are regular expressions outliers, unusual in creating value out of density? Is there some optimum relationship between frequency of use and density where something becomes too dense if we don't use it often enough? If we create dense languages, APIs, or coding conventions are we creating impenetrable barriers to entry for newbies? If we don't create dense notations are we providing a disservice to those who will use the notation often? Is there any hope that a designer of a language, API, or coding convention can find a near optimum density for his or her target audience that remains near optimal for a long time over patterns of changing usage?

Footnotes

1. Insert "now you have two problems" joke here.

Type Errors as Warnings

Paul Snively and I are having a bit of disagreement about the value of treating type errors as warnings during development. It's hard to make anything like a cohesive point on Twitter so I thought I'd write a quickie post on what I mean and why I think it's valuable.

What I'm talking about is not revolutionary. Eclipse JDT does it and I'm sure others do as well. The idea in a nutshell is that when the compiler encounters a type problem in addition to reporting a problem and instead of stopping it should optionally elide the offending code and replaces it with code that will throw an exception if executed. As a trivial example the Java code

int foo(String x) {
   return x*2;
}

would get an error report and be replaced by the equivalent of

int foo(String x) {
  throw new TypeError("Expected an int but got a String at line 42 of Bar.java.");
}

That kind of loose handling of type errors obviously shouldn't be enabled for production builds or even continuous integration builds - otherwise I might as well use a dynamically typed language that does it better anyway. But for development I find that kind of behavior very useful. And while my toy example was in Java I have the same desire when working on any large program in a statically typed language.

My main use case is modifying a data structure definition that is used several places in a large program. As one concrete example, if I modify a language AST definition I may not want to bother fixing up the optimizing code path until I've ironed out the kinks in the non-optimizing code path. Perhaps the whole idea is rubbish and any work I do on the optimizing path would be wasted. Or if I had a Boolean field but realized I should have used something more meaningful or with more options then I could break code everywhere but want to fix and unit test parts of the program incrementally, allowing me to think about more manageably sized chunks than "everything this one change breaks."

When a program gets changed it may very well pass through stages where parts of it are nonsense, or at least not provably sensible. Rather than having to fix everything up before exploring the consequences of my change I find that it is sometimes handy to work in a more piecemeal fashion, restoring sense to some parts and exploring the consequences. Compilers that can treat type errors as warning support that work style. Without such support I frequently end up manually peppering my code with exceptions and TODOs. Why not let the compiler do that bookkeeping for me?

Edit: Clarifications and Rebuttals

I'm not talking about optional typing where you can turn off type checking. Nor am I talking about gradual typing where you can turn type checking on or off for various parts of your program. Optional and gradual typing might (or might not) be nice, but they're orthogonal to what I'm talking about. All I'm suggesting is that when a static type checker (optional or not, gradual or not) finds a problem I always want the error report but during development I don't necessarily want the errors to prevent code generation. And while there might be sophisticated ways to generate code around type errors the most straightforward is to emit code for an exception or program termination plus some diagnostics.

There are suggestions in the comments that the result will be something like the wars over turning on -Wall (warn for all known potential problems). But -Wall isn't the right comparison, since I'm not suggesting that any type checks can be turned off. What I'm proposing is more nearly the equivalent of turning off -Werror (error on warnings). The difference is that code will often work (or at least "work" with scare quotes) in the presence of warnings. The temptation to ignore warnings can be quite strong. But in the case of type errors my suggestion would produce an executable that absolutely can't work if an offending code path is executed. Thus the temptation to turn type errors into warnings on production builds should be minimal.

If a compiler writer is seriously concerned that this behavior would be abused for production builds then the answer might be to only expose it via an API that can be used by IDEs, Emacs SLIME style modes, etc, but which isn't available in the supplied command line batch compiler. That sounds like overkill to me, but whatever.

Sleep Sort! With Actors! For No Reason!

The world's stupidest, racy sort algorithm ported to Scala actors for no good reason.

import scala.actors._
import Actor._

def sleepSort(xs : List[Int]) : List[Int] = {
   def sorter(aggregator : Actor, n : Int) = actor {
      reactWithin(n * 1000) {
        case TIMEOUT => {
           aggregator ! n
           exit
        }
      }
   }

   xs map (sorter(self, _)) foreach (_.start)

   val inputLength = xs.length

   def aggregate(result : List[Int], resultLength : Int) : List[Int] = 
     if (resultLength == inputLength) {
        result.reverse 
     } else receive {
        case n : Int => 
          aggregate(n :: result, resultLength + 1)
     }

   aggregate(List[Int](), 0)
}

Example usage:

scala> sleepSort(List(3,1,2))
res0: List[Int] = List(1, 2, 3)

Caveats: Can take a shockingly long time. Doesn't handle negative numbers. Doesn't handle actor failures. Races are possible. If you try to use this in real code then you will be fired and possibly shot.

Why Eager Languages Don't Have Products and Lazy Languages Don't Have Sums

In The Point of Laziness, Bob Harper mentioned a core duality between lazy and eager languages[1]. Eager languages have sum types but not product types and lazy languages have product types but no sum types. I've seen a few questions about what he means. I thought I'd try to explain. It all has to do with non-termination, our old friend "bottom" which I'll write ⊥. In this entire article I'm focusing on languages that don't allow any side effects other than ⊥ - that way I don't have to deal with ordering print statements or whatever. Also, I'm using an MLish notation that hopefully isn't too confusing.

Update: This comment by Dan Doel does a better job of explaining the issues than my whole article.

Product Types

A product type is a pair. The pair type (A,B) is the product of A and B, and is often written as A * B or A × B. A 3-tuple[2] (A,B,C) can be seen as another way of saying ((A,B),C), etc. so any n-Tuple is just a pretty way to write nested pairs. The simplest way to define exactly what a pair means is through projection functions "first" and "second" which pull out the first or second element. The equations we want are

first (a,b) == a
second (a,b) == b

Pretty straight forward right? Well, those equations hold just fine in a lazy language even when a or b is ⊥. But in an eager language, first (a,⊥) == ⊥. Same deal with second. Oops. Hence lazy languages have product types in the sense that they completely meet these equations where eager languages don't.

That has a practical consequence. A compiler for an eager language can't necessarily simplify first(a, someComplicatedExpression) unless it can prove that someComplicatedExpression is never ⊥, and in general it can't do that. A lazy language compiler would always be free to throw away someComplicatedExpression.

Sum Types

A sum type is an alternative between two choices. A | B is the sum of the two things, A and B, and is frequently written A + B. Choices among three elements, like A | B | C can be considered as just a pretty form of (A | B) | C - a nesting of binary choices. The simplest sum type is good old Boolean, the choice between true or false. Here's one equation we might expect to hold for Booleans and something that examines booleans, the if expression[3]

((if condition then x else y), z) == if condition then (x,z) else (y,z)

Ignore the possibility of x, y, and z being ⊥ and focus on "condition". In an eager language, condition must be evaluated in either of the two forms above and either way you get ⊥ if condition is ⊥. But in a lazy language, the left side will compute (⊥, z) where he right side will compute ⊥. Pulling the second element from those two results gives differing results, proving they are unequal.

Again, this has consequences. An eager language can simplify the right side form to the left side form if it wants to. A lazy language can't.

Footnotes

1. Strictly speaking I should say strict and non-strict instead of eager and lazy, but I'll go with Dr. Harper's wording because the difference isn't that important to the point.
2. Or a record (aka a struct). A tuple can be seen as a record where the field labels are numbers or a record can be seen as a tuple with some convenient labels for the positions.
3. If you are more familiar with C like languages that treat "if/else" as statements instead of expressions then pretend I'm using a ternary operator "condition ? x : y" instead of "if condition then x else y"

The Read Eval Print Lie

It's a common misconception that a language must be "dynamic" or "interpreted" to have a REPL, a Read Evaluate Print Loop (also sometimes confusingly called an interpreter), or to have an "eval" function. That's not true at all.

Haskell, OCaml, F#, and Scala are all statically typed languages with very sophisticated static type systems, yet all have REPLs. All are usually compiled although interpreters exist for Haskell. Typed Racket (a variant of Scheme) is statically typed but has a REPL and I think it's always compiled.

Nor does a language have to be interpreted to have a REPL. Groovy is a dynamic language in both the dynamically typed sense and the "mutate my program structure at runtime" sense. It's always compiled, yet it has a REPL. JRuby (Ruby for the JVM) is similarly always compiled as far as I know, but has a REPL. Clojure and Erlang are always compiled, but both have REPLs.

The misconception about the nature of REPLs is caused by the C family of statically typed languages: C, C++, Java, C#, Objective-C and D. They do not tend to lend themselves to REPLs, but it's not because of the static typing or the compiling. It's because of the statement orientation and verbose boilerplate around every construct. A REPL is possible in those languages, it just wouldn't be very useful.

At heart, a REPL is always possible because "eval" is possible in any Turing complete language. That's CS 101 - see universal Turing machine and the Church-Turing thesis.

Remember that compiling vs interpreting is just an implementation choice as far as semantics are concerned. And stop looking to the C-ish languages as examples of the limits of static typing.

Local Version Control

My company uses a centralized version control system. It works reasonably well, but of course has all the downsides of centralized VCS. So I wanted to explain how I use a local version control system to supplement even if there isn't a real "bridge" like git-svn.

Why

Before I start let me sum up why you might want to.

1. It's not uncommon to work on task A only to have it interrupted by super critical task B. Local VCS makes it easy to put aside the work in progress for task A, go back to the state of the system before task A started, get task B done, and then pick up task A again.
2. Centralized version control almost never manages an entire configuration. In every development environment I've ever worked there are some local settings that you can't check in because they are for you only. Examples include editor preferences, personal credentials for a service, and machine specific configurations. A local VCS can hold your personal configuration just as well as shared configuration.
3. It can be hard to get the manager of a centralized version control system to create branches for your experiments. And checking in half-assed code to a central VCS's main line is usually frowned upon. A local VCS means you can take short steps forward, roll back, and branch in different directions at a whim all while maintaining as much history as you want.
4. You can do all the above even while offline.
5. If your central VCS uses a lock/edit/unlock (ick!) model then a local VCS makes it possible to do an edit/merge model locally and only lock the moment you're ready to commit.
6. If your local VCS is a distributed VCS (DVCS) then you can share your ongoing work with immediate teammates without polluting the main code line with something experimental or half-baked.

Which One?

Which local VCS to use? Other than the last use case it doesn't matter, much. Just beware that Subversion isn't so good at merging branches multiple times. Also, if your central VCS likes to play with read/write permissions then it's a bad idea to use a local VCS that also wants to do so. More generally the local and centrallized VCS can't keep metadata in the same place, so Subversion can't be used both locally and remotely. I'd heartily recommend git, Mercurial, Darcs, or Bazaar whatever you're most comfortable with.

The Basic Model

It's very simple to have local VCS for the most common workflow. The basic idea is to have a local repository that manages the same directories managed by your centralized VCS. Then a typical work session might look like

1. Synch with central VCS
2. Immediately commit to local VCS with a comment like "synch" so you know it wasn't your work
3. Do some work
4. Commit to local VCS
5. Do some more work
6. Commit to local VCS
7. Finish your work
8. Commit to local VCS
9. Synch from central VCS, merging as necessary
10. Make sure your stuff still works
11. Commit to local VCS with a comment like "merge"
12. Commit to centralized VCS

That's as simple as it can be. Other than the occasional commit to local VCS, it's exactly what you do now. The process works because the way your local VCS and distributed VCS track what has changed is different. The centralized VCS doesn't know anything about all the intermediate commits to local VCS. It just thinks you've made a bunch of changes and committed them. Similarly, the local VCS is oblivious to the central VCS. At step 2 it thinks you've just checked in some massive change.

There are more advanced uses of a local VCS but the above model seems to cover about 95% of what I use mine for.

Cloning/Branching

A slightly more advanced model when using DVCS is to clone the local "master" repository and work in the clone. This model can be very useful when working on something very experimental which is likely to take a long time with frequent interruptions for higher priority tasks. Upstream commits and synchs become a bit more complicated, but "shelving" is automatic: to jump on a quick high priority task just go work in the master repository or make another clone from the master.

Alternatively, if your local VCS supports another branching model then the same idea can be done with a branch.

Sharing

If you're using a DVCS then work-in-progress can be shared across a small team within the larger organization. However, it's probably a good idea to have one person (or one repository) responsible for synching from the centralized VCS to avoid spurious merge conflicts since the local VCS has no way to know that different people synching from the central VCS are pulling files with a common history.

The Fine Print

If you use an IDE to control your central VCS you may have to stick to command line for your local VCS or, if you prefer, use something like one of the Tortoise* style plugins for a graphical file manager. I've never experimented with getting an IDE to try to understand that one set of directories is managed by two version control systems, but I can't imagine that it would be pretty.

Some centralized VCSs really, really prefer to know what you're working on. They may have a lock/edit/unlock cycle (ick!) or they may just use knowledge of your "working" files as an optimization (Perforce does this). If so, cloning can be a problem because the checkout bit won't be tracked in the clone. If you modify files in the clone then push back to the master the centralized VCS will disagree with you about what state the file is in. The same problem goes for a shared DVCS model. It's not an insurmountable problem, but one to be aware of. Basically before committing to centralized VCS all the changed files will need to be "checked out" and merged with your work.

Conclusion

Stick to the basic model at first and you'll see it's very easy to get most of the benefits of local VCS. You'll quickly realize that the local VCS is an incredible safety net even with just the simple model. Later you can branch out *ahem* into more advanced uses.

Given the simplicity and safety of having a local VCS it's insane to work with only a centralized VCS. And who knows, maybe your little experiment will be the catalyst for moving your company to a DVCS.

Phantom Types In Haskell and Scala

/*
Some literate Haskell and Scala to demonstrate 
1) phantom types
2) I am a masochist
3) ???
4) profit!

The code is probably best viewed with a syntax colorizer
for one language or the other but I've colorized all my
 comments.

> {-# LANGUAGE EmptyDataDecls #-}
> module RocketModule(test1, test2, createRocket, addFuel, addO2, launch) where

*/
object RocketModule {

/*
None of these data types have constructors, so there are
no values with these types. That's okay because I only 
need the types at compile time. Hence "phantom" - 
ethereal and unreal.

> data NoFuel
> data Fueled
> data NoO2
> data HasO2

*/
   sealed trait NoFuel
   sealed trait Fueled
   sealed trait NoO2
   sealed trait HasO2

/*
The Rocket data type takes two type parameters, fuel and
o2.  But the constructor doesn't touch them.  I don't
export the constructor so only this module can create
rockets.

> data Rocket fuel o2 = Rocket

*/
   final case class Rocket[Fuel, O2] private[RocketModule]()

/*
createRocket produces a rocket with no fuel and no o2
 
> createRocket :: Rocket NoFuel NoO2 
> createRocket = Rocket

*/
   def createRocket = Rocket[NoFuel, NoO2]()

/*
addFuel takes a rocket with no fuel and returns one with
fuel.  It doesn't touch the o2
 
> addFuel :: Rocket NoFuel o2 -> Rocket Fueled o2
> addFuel x = Rocket

*/
   def addFuel[O2](x : Rocket[NoFuel, O2]) = Rocket[Fueled, O2]()

/*
Similarly, addO2 adds o2 without touching the fuel

> addO2 :: Rocket fuel NoO2 -> Rocket fuel HasO2
> addO2 x = Rocket
 
*/
   def addO2[Fuel](x : Rocket[Fuel, NoO2]) = Rocket[Fuel, HasO2]()

/*
launch will only launch a rocket with both fuel and o2

> launch :: Rocket Fueled HasO2 -> String
> launch x = "blastoff"

*/
   def launch(x : Rocket[Fueled, HasO2]) = "blastoff"

/*
This is just a pretty way of stringing things together,
stolen shamelessly from F#.  Adding infix operations is
a bit verbose in Scala.

> a |> b = b a

*/
   implicit def toPiped[V] (value:V) = new {
      def |>[R] (f : V => R) = f(value)
   }

/*
Create a rocket, fuel it, add o2, then 
launch it

> test1 = createRocket |> addFuel |> addO2 |> launch

*/
   def test1 = createRocket |> addFuel |> addO2 |> launch

/*
This compiles just fine, too.  It doesn't matter which 
order we put in the fuel and o2
 
> test2 = createRocket |> addO2 |> addFuel |> launch

*/
   def test2 = createRocket |> addO2 |> addFuel |> launch

//This won't compile - there's no fuel
 
// > test3 = createRocket |> addO2 |> launch

//    def test3 = createRocket |> addO2 |> launch

// This won't compile either - there's no o2

// > test4 = createRocket |> addFuel |> launch

//    def test4 = createRocket |> addFuel |> launch

// This won't compile because you can't add fuel twice

// > test5 = createRocket |> addFuel |> addO2 |> addFuel |> launch

//    def test5 = createRocket |> addFuel |> addO2 |> addFuel |> launch
}

Systems Design: Making a New Feature (Nearly) Too Much Trouble

EDIT: Since I wrote this BART has finally implemented an integration between parking payment and the Clipper card. It's a little more complicated to set up than it should be, but it works. I'll leave the rant up because the meta-point still stands.

This article will look like a random rant about public transportation, but it's really a random rant about bad systems design, especially when extending an existing system without understanding the interactions between the new and the old.

Every day I ride BART (the San Francisco bay area subway system) to and from work. The default procedure for BART is to put some cash or credit into a machine and get a ticket of that value. Then every time you want to ride you run the ticket through a turnstile, ride the train, then run the ticket through an exit turnstile to have value deducted from your ticket based on the distance between the stations. Keep doing that until the ticket is nearly depleted and then add some more value at a ticket machine.

In order to minimize the number of trips to the ticket vending machine I was buying the max value it would allow, $60. But the paper tickets are easily torn, easily lost, and um, easily destroyed in a washing machine. Before you ask yes I did. Fortunately it was a nearly depleted ticket.

Losing $60 on a maxed ticket wouldn't be pleasant. So I decided to get a Clipper card, an RFID based card that you can tie to a prepaid or credit account and use for BART, Muni (San Francisco's municipal bus and light-rail system), and Cal-Train (a commuter rail that connects San Francisco to Silicon Valley). Sounds like a good thing. But in practice it turns out to be (nearly) too much trouble.

I skipped over a point in describing my default procedure with tickets. You see, I have to park at the BART station near my house and BART charges a small $1 fee for parking. So the real procedure is: feed the ticket to the entrance turnstile, use the ticket at another machine to pay for parking, then ride the train, etc. That's important because, get this, you can't use the Clipper card for parking. I have no idea why not, but you can't. Period.

Okay, that's annoying. But I knew that when I got the card so I had a plan: I would continue to buy BART tickets but for much smaller amounts, like $10, in order to pay for parking. It wouldn't be perfect but still much better. Washing away, er accidentally tearing up $10 is much less painful than losing $60.

It was a good plan. But my plan was dashed by some system designer's brain fart. The machine that accepts a parking fee will not accept your ticket unless it has been used at the entrance turnstile. So if I enter using the Clipper card I can't use a ticket for parking.

If you're mentally asking "WTF?" at this point then you and I are on the same page. The designers had to work extra to add this restriction. Maybe it seemed like a good idea before the card system existed: somebody buying parking with a ticket not marked for entrance may have jumped the turnstile. Or something. I don't know. I do know that with the new system it's just a way to render the Clipper card (nearly) too much trouble.

Why too much trouble? Because other than tickets the parking machine only takes cash and only in $1 and $5 denominations. Not credit cards, not debit cards, not twenties. Nope. Only ones and fives. I don't know about you but I often have nothing but twenties because that's what ATMs dispense. Besides, the goal of me getting the Clipper card was to get rid of a bit of paper, not create a need to carry more bits of paper (with pictures of dead white guys).

The card is now very nearly too much trouble. Nearly. I'll still keep the Clipper card. I can use it for my return trips and thus cut the value of my tickets in half. And I can use it for Muni and Cal-Train. But my original goal, getting rid of paper, is dead, slaughtered on the altar of bad systems design.

Now let me get meta. The above sad but true story is an object lesson in extending an existing system. The next time you add a feature to a system you're working on ask yourself if interactions with existing features are going to cause your users problems. At the very least such bad interactions can lower the user's valuation of all your hard work in creating the new feature. But that's not all.

One of the strange things about user experience is that users subjectively put far more weight on negative experiences than positive ones. A new feature should create a positive experience and make users want to use your system even more. But if a new feature interacts poorly with old features then the user's impression can actually be more negative than it was before you extended your system. It would be a damn shame if trying to help your users eventually led them to conclude your whole system was (entirely) too much trouble.

How To Estimate Software

A guide to estimating percentage complete and remaining time.

I haven't looked at the problem. Completed: 0% Time esimate: about 2 weeks.

I've looked at the problem. Completed: 50% Time estimate: about 2 more weeks.

I've implemented almost everything. All that remains is the difficult stuff that I don't really know how to do. Completed: 90% Time estimate: about 2 more weeks.

I've done everything. All that remains is documentation, code review, tests and error handling. Completed: 99% Time estimate: about 2 more weeks.

I still haven't finished documentation, code review, tests, or error handling. The truth is I've been gold plating what I already wrote. But I just saw another problem that seems more interesting. Completed: 100% Time estimate: 0 more weeks.

Moron Why C Is Not Assembly

In response to a previous article a poster in some forum called me an idiot and said "everybody knows that C is a portable assembly language with some syntax sugar." The idiot insult hurt deeply and I cried, but once the tears were dry I resolved to write a bit more on why C isn't assembly, or is at best an assembly for a strange, lobotomized machine. Also, I may have misspelled "more on" in this article's title.

To compare the two things I kinda need to define what I'm comparing. By C I mean an ANSI C standard, whichever version floats your boat. Most real C implementations will go some distance beyond the standard(s), of course, but I have to draw the line somewhere. Assembly is more problematic to define because there have been so many and some have been quite different. But I'll wave my hands a bit and mean standard assembly languages for mainstream processors. To level set: my assembly experience is professionally all x86 and I had a bit of RISC stuff in college plus I did some 6502 back in the day.

Assembly-Like Bits

There are some very assembly like things about C and its worth mentioning them. The main one is that C gives you very, very good control over the layout of data structures in memory. In fact, on modern architectures, I'd bet that this fact is the primary ingredient in the good showing that C (and C++) have in the language shootout. Other languages produce some damn fine executable code, but their semantics make it hard to avoid pointer indirection, poor locality of reference, or other performance losses.

There are a few other assembly-ish thing in C. But not much. Now to why C is just not assembly. I'll start with...

The Stack

As far as I'm concerned the number one thing that makes C not assembly is "The Stack." On entry into a function C allocates space needed for bookkeeping and local variables and on function exit the memory gets freed. It's very convenient, but it's also very nearly totally opaque to the programmer. That's completely unlike any mainstream assembly where "the stack" (lower case) is just a pointer, probably held in a register. A typical assembly has no problem with you swapping the stack (e.g. to implement continuations, coroutines, whatever) while C defines no way to do much of anything with the stack. The most power that C gives you on the stack is setjmp/longjump - setjmp captures a point on the stack and longjmp lets you unwind back to that point. setjmp/longjmp certainly have an assembly-like feel to them when compared to, say, exceptions, but they are incredibly underpowered when compared to the stack swizzling abilities of a typical assembly language.

Speaking of continuations, let's talk about...

Parallel and Concurrent Code

The C standard has almost nothing to say about parallel and concurrent code except that the "volatile" keyword means that a variable might be changed concurrently by something else so don't optimize. That's about it. Various libraries and compilers have something to say on the subject, but the language is pretty quiet. A real assembly, or at least a real assembly on any modern architecture, is going to have all kinds of stuff to say about parallelism and concurrency: compare and swap, memory fences, Single Instruction Multiple Data (SIMD) operations, etc. And that leads a bit into...

Optimization

void doubleArray(int * restrict dest, 
     int const * restrict src, size_t size) {
   for (size_t i = 0; i < size; i++) {
      dest[i] = src[i] * 2;
   }
}

Under gcc -std=c99 -S at -O1 I get pretty standard sequential code. Under -O3 I get highly parallel code using x86 SIMD operations. An assembler that changed my code that way would be thrown out as garbage but a C compiler that DIDN'T parallelize that code on hardware that could support it would seem underpowered. And given the highly sequential nature of the original code the transformation to parallel code goes way beyond mere de-sugaring.

Optimization leads me to ...

Undefined Behavior

The C standard says a bunch of stuff leads to undefined behavior. Real compilers take advantage of that to optimize away code, sometimes with surprising results.

What assembly has undefined behavior on that scale? mov al, [3483h] ;(Intel syntax) is going to try to copy the byte at 3483h into the al register, period. It might trap due to memory protection but the attempt will be made.

Conclusion

Alan Perlis famously said "a programming language is low level when its programs require attention to the irrelevant." What's relevant depends on the problem and the domain, so a corollary would be that a language that's at too high a level prevents paying attention to some of what is relevant for your needs.

C is a low level language as compared with most languages used for most day to day programming. If you spend all day hacking Ruby or Haskell then C might look like assembly. But C is actually at a substantially higher level than assembly. Assembly both permits and requires you to do things that C hides.

Please stop perpetuating the myth that C is sugar for assembly because real compilers make complicated, non-obvious transformations to get from C to machine code that assemblers don't. And please stop saying that C is a portable assembly because if it is then it's the assembly for a very peculiar machine that is both underspecified and a bit stupid when compared to real hardware.

Why Scala's "Option" and Haskell's "Maybe" types will save you from null

Cedric Beust makes a bunch of claims in his post on Why Scala's "Option" and Haskell's "Maybe" types won't save you from null, commenters say he doesn't get it and he says nobody has argued with his main points. So I thought I'd do a careful investigation to see what, if anything, is being missed.

First, right off the top here: Scala has true blue Java-like null; any reference may be null. Its presence muddies the water quite a bit. But since Beust's article explicitly talks about Haskell he's clearly not talking about that aspect of Scala because Haskell doesn't have null. I'll get back to Scala's null at the end but for now pretend it doesn't exist.

Second, just to set the record straight: "Option" has roots in programming languages as far back as ML. Both Haskell's "Maybe" and Scala's "Option" (and F#'s "Option" and others) trace their ancestry to it.

Now, to the post.

First Objection

in practice, I find that hash tables allowing null values are rare to the point where this limitation has never bothered me in fifteen years of Java.

Really? Let me give one concrete example. You're writing a cache system (in the form of an associative map) in front of a persistent storage with nullable values. Question: how do you differentiate between "I haven't cached this value" from "I've cached the value and it was null in the database"? The answer is that you can't use "null" to mean both things, it's ambiguous. That may not "bother" Beust, but I find it irritating that you end up having to use two different mechanisms to say this in Java.

With Maybe/Option you just say that the map holds optional values. A fetch result of None/Nothing means you haven't put that key in your map. A result of Some(None)/Just Nothing means you've got the key but it maps to nothing, and a result of Some(value)/Just value means that the key is in the map and that there's a "real" value there in storage.

Save Me!

Back to Beust

The claim that Option eliminates NullPointerException is more outrageous and completely bogus. Here is how you avoid a null pointer exception with the Option class (from the blog):

val result = map.get( "Hello" )
 
result match {
  case None => print "No key with that name!"
  case Some(x) => print "Found value" + x
}

See what's going on here? You avoid a NullPointerException by... testing against null, except that it's called None. What have we gained, exactly?

Here, is, IMHO the heart of what people are arguing with Beust about. He thinks this code is no different from the kind of "if (result == null)" code you write in Java. Sure, identical. Except for one, huge, glaring, major, stab you in the face difference: in Java the type system says Map<T>#get will return a T. It doesn't say it MIGHT return a T. That's left to the documentation where it's out of reach for the compiler. Here in Java.

Map<String, Integer> myStuff = new HashMap<String, Integer()>;
myStuff.put("hello", 42);
int result = myStuff.get("goodbye") * 2; // runtime NPE

Java NPEs when you try to use the result of the fetch. On the other hand, when you use a Scala map you get an Option[T] while Haskell's says it returns a Maybe t. The type system says you can't use the underlying value directly. Here's me trying to pull something from a map and manipulate it directly in both Haskell

mystuff = fromList[("hello", 42)]
result = (lookup "goodbye" myStuff) * 2 -- compile time error

And Scala

val myStuff = Map("hello" -> 42)
val result = (myStuff get "goodbye") * 2 // compile time error

In both cases I get a static error.

Now...there are a lot of (IMHO crappy) debates on static vs dynamic typing. But one thing must be very clear: the two situations are at least different. This isn't the same as a Java NPE (or the equivalents in Ruby/Python/whatever). Option/Maybe tell the static type system that you may or may not have what you're looking for.

Blowups Can Happen

Onward.

The worst part about this example is that it forces me to deal with the null case right here. Sometimes, that's what I want to do but what if such an error is a programming error (e.g. an assertion error) that should simply never happen? In this case, I just want to assume that I will never receive null and I don't want to waste time testing for this case: my application should simply blow up if I get a null at this point.

There is a cavernous hole in Haskell Maybe and Scala Option. Beust's post does not talk about it at all, though. The hole is that Haskell and Scala are Turing complete, and that means that the type system cannot prevent you from throwing optionality out if that's what you really want to do. In Haskell

loopForever :: a
loopForever = loopForever -- really, forever

stripOption :: Maybe t -> t
stripOption Just x = x
stripOption _ = loopForever

-- or better yet
stripOption = fromMaybe loopForever

And Scala

final def loopForever[A] : A = loopForever // and ever, amen

def stripOption[T](o : Option[T]) : T = o match {
  case Some(x) => x
  case None => loopForever
}

// or, better still

def stripOption[T](o : Option[T]) : T = o getOrElse loopForever

In their respective languages language the following compile just fine but will cause non-termination at runtime.

result = (stripOption (lookup "goodbye" myStuff)) * 2
val result = stripOption(myStuff get "goodbye") * 2

Of course, if you really want to write that in real code you would replace "loopForever" with throwing an exception. That's exactly what Scala's Option#get and Haskell's Data.Option.fromJust do.

result = (fromJust (lookup "goodbye" myStuff)) * 2
val result = (myStuff get "goodbye").get * 2

Why did I write a silly loop? To make a point: Turing completeness punches a hole in the type system. "Throw" style operators exploit essentially the same hole. Every programmer should know this in the bottom of their heart.

Whether using the loopForever version or the exception version, stripOption/get/fromJust is different from null dereferencing. It requires an explicit step on the part of the programmer. The programmer says "I know what I'm doing here, let me continue, blow up if I'm wrong." But, IMHO, it's easy enough to say that it kills his objection of "forcing" him to deal with null instead of just blowing up. Yes, there's a hoop to jump through, but it's tiny. KABOOM!

Nullable Types

Next point:

When it comes to alleviating the problems caused by null pointer exceptions, the only approach I've seen recently that demonstrates a technical improvement is Fantom (Groovy also supports a similar approach), which attacks the problem from two different angles, static and runtime:

Static: In Fantom, the fact that a variable can be null or not is captured by a question mark appended to its type:

Str   // never stores null
Str?  // might store null

This allows the compiler to reason about the nullability of your code.

One technical quibble. Since Groovy doesn't have static types this static bit isn't relevant to Groovy.

Anyway, the equivalents in Scala and Haskell are String vs Option[String]/Maybe String. More characters, but the same idea. Except that Fantom and Nice and other languages with nullable types don't tend to support saying ??String whereas Option[Option[String]] and Maybe (Maybe String) are totally reasonable. See my caching example above.

Safe Invoke

Runtime: The second aspect is solved by Fantom's "safe invoke" operator, ?.. This operator allows you to dereference a null pointer without receiving a null pointer exception:

// hard way
Str? email := null
if (userList != null)
{
  user := userList.findUser("bob")
  if (user != null) email = user.email
}
 
// easy way
email := userList?.findUser("bob")?.email

Note how this second example is semantically equivalent to the first one but with a lot of needless boiler plate removed.

And in Scala that might look like

userList flatMap (_ findUser "bob") flatMap (_.email)

while haskell would use

userList >>= findUser "bob" >>= email

There are some more keystrokes indeed, but here's the thing...

Better

So, can someone explain to me how Option addresses the null pointer problem better than Fantom's approach

Option/Maybe/flatMap/>>= are all ordinary library code. No magic. The types are algebraic data types, an idea that is massively useful. The methods belong to a class of types called Monad. If Option/Maybe don't work for you as-is you can build your own versions. With nullable types and ?. operator you're stuck with what the language provides. If they don't work for your particular case then you can't create your own variants. Quick, in Fantom extend the ?. operator so that works for exception-like semantics such that failure carries a reason instead of just computing null. In Haskell and Scala that already exists and it's ordinary library code in a type called Either.

Conclusion

In practice, outside of learning, I've never ever gotten the equivelent of an NPE by abusing Haskell's fromJust or Scala's Option#get, not even in testing. On the other hand NPE's are a fact of my life when dealing with nulls in Java et al. And while it's true that testing has revealed the vast majority of potential NPEs (or equivalent) in my life, it certainly hasn't dug up all of them. I've seen plenty of production systems brought to their knees by NPEs.

Exceptions plus a deliberate weakening of the type system allow developers to create "oh, just blow up" code when that's the right answer. But the developer has to explicitly say so.

Fantom/Nice style nullable types plus a "safe invoke" operator are a nice improvement over plain old null. But they are not composable (no ??T) and they are special purpose magic aimed at a very narrow domain instead of general purpose magic such as algebraic data types and higher order functions that are broadly applicable to huge problem domains.

So there you have it, Cedric, what are we missing in your post?

PostScript on Scala and Null

Which brings me back to Scala's null. For interoperability reasons Scala has a full blown Java-like null. But the experience that all the Scala developers I know have is that NPE is mostly only a problem when dealing with existing Java libraries because Scala programmers and libraries avoid it. Plus, Scala's "Option(foo)" promotes foo to either Some(foo) or None depending on whether it's null or not that at least enables the map/flatMap style of "safe invoke." It's far less than perfect, but about the best that can be done when dealing directly with Java.

For Haskell, null is a non-issue.

Sometime in 1977

Kernighan:

"I know, let's open the book with a program that displays 'hello, world.'"

Ritchie:

"Great idea! I'll start the patent search."

On Removing Java Checked Exceptions By Means of Perversion

/*

What do you do in Java when you need to throw a checked exception in a context where it's not allowed, for instance when implementing a third party interface with no declared throws clause? If you're smart and its allowed you just write the code in another language. Otherwise you probably just wrap the bastard checked exception in an unchecked exception and be on your way.

But the wrapping solution a) requires an extra object allocation and b) unwrapping the original exception is a bit messy.

No, no, those justifications for what I'm about to do are horse shit rationalizations. The fact is I just want to pervert Java. I make it my job to pervert languages for their own good. Or at least, my own amusement.

Instead of "throw" meet "chuck" which turns checked exceptions into unchecked chucked exceptions. This post is an executable Java program.

Edit: This is an idea that can be traced back to Java Puzzlers by Bloch and Gafter and perhaps further. I've just refined it a bit with a bottom return and a way to catch the exception.

*/

import java.io.IOException;

public class Unchecked {

/*

The key to today's lesson in programming aberration is the fact that Java allows you to cast to a generic type parameter but can't actually check the cast at runtime due to type erasure. The following method does an unchecked cast from a Throwable to some generically specified subtype of Throwable and then immediately throws it. Neither the static nor dynamic type system ever have a chance to detect any deviant behavior such as casting to a "wrong" type. The code also lets the caller specify any return type. A previous article explains why that's useful.

*/

   @SuppressWarnings("unchecked")
   private static <T extends Throwable, A> 
     A pervertException(Throwable x) throws T {
      throw (T) x;
   }

/*

Then chuck puts some lipstick on that kinky little pig by telling it to act like it's throwing a RuntimeException. Et voilà, no need to declare the exception in a "throws" clause.

*/

   public static <A> A chuck(Throwable t) {
      return Unchecked.
        <RuntimeException, A>pervertException(t);
   }

/*

Some sample code shows how to use chuck.

*/

   public static int testChuck() {

/*

We can't throw an IOException because it's checked

*/

      // throw new IOException("checked, oh noes");

/*

But we can chuck an IOException

*/

      return chuck(new IOException("unchecked, hellsyeah"));

/*

And, just like with a throw the next line won't compile because it's unreachable.

*/

      // System.out.println("dead code");
   }

/*

If you never want to catch the exception or you want to handle it with a top level "catch Exception" then that's all there is to it. But if you want to catch and handle the IOException specifically then there's one tiny flaw in the system. Sadly, the following won't compile because IOException isn't statically known to be thrown by testChuck() and Java wouldn't want you to catch something that can't be thrown now would it?

*/

//   public static int wontCompile() {
//      try {
//         testChuck();
//      } catch (IOException e) {
//         System.out.println("Why did you leave me with" + 
//                            " the sad clown of life?");
//      }
//   }

/*

The fix is to add a way to tell the compiler what exceptions we might chuck, kinda like the "throws" keyword but this one chucks. Totally different. The chucks method threatens to throw a T but in a sudden fit of shame it does nothing - per a tip from a commenter it takes a class argument to avoid Java's hideous generic method invocation syntax.

*/

   public static <T extends Throwable> 
     void chucks(Class<T> clazz) throws T {}

/*

And here we go, we can catch our chucked exception.

*/

   public static void main(String[] args) {
      try {
         chucks(IOException.class);

         testChuck();         
      } catch (IOException e) {
         System.out.println("Caught chucked exception " + 
                             e + ".");
      }
   }
}

/*

Running that should display "Caught chucked exception java.io.IOException: unchecked, hellsyeah."

My depraved perversion work is done. Now I may rest. I leave you with this imponderable: how many unchecked checked exceptions will Unchecked.chuck() chuck?

*/

When CONSTants Vary

/*

Occasionally somebody will suggest that statically typed language X (Java, C#, Scala, F#, whatever) would be better off with C++'s "const", a type qualifer that supposedly makes objects immutable in certain contexts[1]. I'm not convinced. Const requires a fair amount of work and provides fairly small guarantees. This post is a bit of literate C++ program demonstrating some of the weaknesses in const.

There are a couple of holes that I want to dismiss quickly. First there's the weakness that const can be cast away. But hey, the C and C++ motto is "casting away safety since 1972." Blowing your leg off with a cast is half the fun of using the C derived languages. Second, there's the useful, if slightly misnamed, weakness of the "mutable"[2] keyword which can be applied to a field and says "this field can be mutated even in const contexts." Mutable is useful for things like memoizing.

But even ignoring those very deliberate issues, there are still a couple of fundamental weaknesses in how C++ deals with const.

For my example I'm going to use a simple toy class, a Counter that can be incremented (mutating its state) and then queried to see what the current count is.

*/

#include <iostream>

using namespace std;

class Counter {
   int _count;

public:
   Counter() : _count(0) {}
   void inc() {
      _count++;
   }

/*

A perfectly good use of const. The count() query doesn't change the state of this Counter.

*/

   int count() const{
     return _count;
   }
};

/*

Indirection

So far, so good. But we can easily destroy const with a bit of indirection. Imagine I need something that holds a pair of Counters and, for whatever reason, I need to do so via pointers.

*/

class CounterPair {
   Counter *_c1;
   Counter *_c2;

public:
   CounterPair() {
     _c1 = new Counter();
     try {
        _c2 = new Counter();
     } catch(...) {
        delete _c1;
        throw;
     }
   }

   // technically should have copy constructor 
   // and operator=, but I'm too lazy

   ~CounterPair() {
      delete _c1;
      delete _c2;
   }

/*

These two methods query the state of the CounterPair and are safely const

*/

   int count1() const {
     return _c1 -> count();
   }

   int count2() const {
     return _c2 -> count();
   }

/*

Up to this point everything is golden. But these next two methods modify the state of the CounterPair, yet are marked const.

*/

   void inc1() const {
     _c1 -> inc();
   }

   void inc2() const {
     _c2 -> inc();
   }
};

/*

What gives? Well, C++ doesn't appear to understand the that state and memory are two different things. I didn't modify the memory that lies directly in one CounterPair envelope but I'm clearly modifying the state of the CounterPair. "Transitive constness" is one area where the D programming language does much better than C++.

Aliasing

An even more subtle issue happens with aliasing. The following function does not modify its first argument but does modify its second. The first is marked const.

*/

void incSecondCounter(Counter const &c1, Counter &c2) {
  c2.inc();
}

int main(int argc, char** argv) {
   Counter c;

/*

But if we create a bit of aliasing then c1's referent gets modified

*/

   Counter const &c1 = c;
   Counter &c2 = c;
   cout << c1.count() << endl;
   incSecondCounter(c1, c2);
   cout << c1.count() << endl;
}

/*

In this toy program that looks silly, but in larger programs aliasing can be quite subtle. And aliasing is a tricky, tricky problem to deal with well at the type level so even the D language will have an equivalent hole in const. At best what const says here is that "the object won't be modified via that particular reference," which is a heck of a lot weaker than "the object won't be modified."

Conclusion

Const correctness requires a lot of typing of both the push-the-buttons-on-the-keyboard kind and the keep-certain-static-properties-consistent variety. Yet it gives back relatively little. Even without poking holes in const using casting or "mutable" it's easy to get mutation in something that's supposed to be immutable. C++'s variety of const doesn't deal with indirection at all well and aliasing is a tricky nut that would substantially alter a language's type system. Is const worth adding to other languages? I'm not sure.

Footnotes

1. C'99 also has a const keyword with very similar semantics. So if you replace references with pointers and strip out the thin veneer of OO this article would cover C as well.
2. Misnamed because fields are generally mutable even without the keyword. But I suspect the committee would balk at "mutable_even_under_const."

*/