Sunday, August 26, 2007

Martians vs Monads: Null Considered Harmful

I hate null. More specifically I hate NullPointerExceptions(NPEs). Scala has an alternative, but let me explain why I hate NPEs. They're like evil, sneaky muppets. Remember the Martians on Sesame Street? They'd ask each other if a phone was a cow and then say "nope, nope, nope, nope." To my eye, NPE looks a lot like "NoPE."

Me: Is my unit test working?
Computer: NoPE
Me: Um...okay, fixed that problem...how 'bout now?
Computer: NoPE, NoPE, NoPE, NoPE
Me: ARGGHRHGR! You're a Sesame Street Martian!
Computer: Yip, yip, yip, yip1

Does all this code/test/fix/Martians/yelling have to be part of the game? Can't a static typing system save me from this? Can't we stop the Muppets from chanting in my head?

The answer in Java and C# is "No! Well, sorta! Um, no." It is possible to implement a pattern whereby you should never get NoPEs. It's pretty painful to do and the "should" qualifier means it's not really worth it, but it does help illuminate a solution that's available in Scala.2

Some Craptacular Code

First, what's the big deal? Can't I just check for null and deal with it? Here's Java to demonstrate. Any resemblance to a C# code is purely coincidental.


public interface Spaceship {
  public Martian getMartian();
}

// the main method...
Spaceship spaceship = getSpaceshipSomehow();
Martian m = spaceship.getMartian()
if (m != null) {
  m.dieDieDie();
  System.out.println(m.toString() + 
    " is toast.");
} else
  System.out.println(
    "No Martians here!");
}  

The idea here is that some spaceships have Martians while others don't. If there is a Martian, that little bastard will never NoPE me again. Checking for null certainly works. But there's a problem - how do I know for certain that getMartian can return a null? If I didn't write Spaceship, what made me decide to do the null check? And how do I know that getSpaceshipSomehow() won't ever give me a null if I didn't wite it? The answer is I don't, that's how. It might be in the documentation or might not. The docs might be right or they might not. I might have access to the source code or I might not. I might remember what I wrote last week or I might not. The only answer would seem to be to wait for the NoPE to show up in testing or check for null defensively everywhere. Hmmm...stupid Martians.

Okay, let's try creating a holder that I'll call "Option" for reasons we'll see later. Once again, here's some Java (C#ers please consult your magic decoder rings).


public class Option<T> {
  private T value;

  public Option<T>(T value) {
    this.value = value;
  }
}

public interface Spaceship {
  public Option<Martian> getMartian();
}

// the main method...
Spaceship spaceship = getSpaceshipSomehow();
Option<Martian> o = spaceship.getMartian();
if (!o.value() == null) {
  Martian m = o.value();
  m.dieDieDie();
  System.out.println("I'm a 733T Martian h4x0r."
    + m.toString() + " has been pwned.");
} else
  System.out.println("W00T");
}

The idea is that API builders indicate nullibility by saying methods return an Option. getSpaceshipSomehow promises that it will return a Spaceship while getMartian may or may not return a Martian. It's okay as far as it goes, but it's entirely too easy to call o.value() without checking for null first. I'd like the type checker to help me here - maybe with subclasses. Here's the attempt in Java. The equivalent C# should be...um...equivalent.

public abstract class Option<T> {}
public class None<T> extends Option<T>{}
public class Some<T> extends Option<T>{
   private T value;

   public Some<T>(T value) {
     this.value = value;
   }
   public T value() {
     return value;
   }
}

public interface Spaceship {
  public Option<Martian> getMartian();
}

Spaceship spaceship = ...
Option<Martian> o = spaceship.getMartian();
if (o instanceof Some<Martian>) {
  Martian m = ((Some<Martian>)o).value();
  m.dieDieDie();
  System.out.println(m.toString() + 
    " has been laterally motivated.");
} else
  System.out.println("Thinking outside the " +
    "box leverages synergies.");
}

I've got an abstract base class, Option, that's really just a marker that a value might be "null" or not. None means "null", and Some means it's a real value. Code depending on this structure uses instanceof checks to determine which way to cast.

Unfortunately, this code has three holes and one major (huge) annoyance. The first hole is that the spaceship designer has to ensure getMartian always returns an Option and never a null. If that gets blown, we get NoPEd. The second hole is that there's no way in Java to prevent somebody else from creating a subclass of Option - and that would break the logic. The third hole is that I could just cast an Option to a Some without doing an instanceof check, turning a NoPE into an equally irritating ClassCastException . Finally, the major (huge) annoyance is that I have to write all that crappy code every time I deal with this construct. Frankly, I wouldn't blame you if you'd rather deal with NoPE.

Making it Optional in Scala

In Scala, equivalents to Option/Some/None already exist3 - but they're far, far easier to use and they're "sealed" so no logic breaking subclasses are allowed. Here's the last Java example translated into Scala

trait Spaceship {
  def getMartian: Option[Martian]
}

val spaceship = getSpaceshipSomehow
spaceship getMartian match {
  case Some(m) =gt; {
    m dieDieDie;
    println(m + " was terminated.")
  }
  case _ =gt; println("I'll be back.")
}

The Spaceship trait requires all spaceships to implement a getMartian method which may return Some[Martian] or Nothing. Once we have a spaceship we do a match to see if we got a Martian or not, and if we did then it's...retired.

The first thing you might notice is less annotation of types. Let me assure you that the code is just as statically typed as the Java version, it's just that the Scala compiler can figure out the types of "spaceship" and "m" just fine, thank you very much. You may also notice a lot fewer dots, parens, semicolons etc. Scala's syntax allows you to type all that line noise but generally only requires it when things get ambiguous. Finally, in Scala, square brackets work more or less like angle brackets in Java/C# for denoting "generics."

More importantly notice in the "Some" case how cleanly the Martian, m, is "pulled out". The code is easily as clear as the Java version that checked for null. But unlike the null checking Java code it's clear in this case that I have to do the check. If the check wasn't required the code wouldn't even compile. Unlike the Java versions of Option, the Scala version ensures that I've done my checking right.

Confessions of A Leaky Abstraction

Now a bit of a confession. You see, one of Scala's design goals is to interoperate with Java and .Net seamlessly. That's a great source of strength since the libraries for those platforms are huge, the underlying VMs are heavily optimized, and targeting those environments may be a way for Scala to sneak in through the back door of corporate America.

It's also a source of holes. In order to be truly seamless Scala has to have both null and casting. As a result, Scala's Option ends up with some of the same holes as we found in the Java subclassing code. If Scala had tried to plug the null and casting holes, the result would have been an impedance mismatch between Scala and the target VM environments.

Still, the Scala libraries use Option whenever a "null" could be used and Scala projects are following that pattern. As long as you never ever create a cast or a null, you'll only have to worry about NoPE when dealing with existing Java or .Net code. Which is to say, a lot <sigh>. So even though it's not the static guarantee that I want, Scala's Option is incredibly useful since it's just as easy to use as null and far more expressive 5

A Closing Note With Some Rabble Rousing

In Scala, Option is a class and that means it can have methods. One of those methods is a nifty shorthand for getting Some value is available or getting a default value if None. Imagine my Muppet bloodlust (stuffinglust) is so high that if the spaceship doesn't have a Martian, I'll create a new one just to kill it.


val m = spaceship.getMartian.getOrElse(new Martian)
m.dieDieDie

Due to another feature of Scala, optional laziness, a Martian is only constructed when needed. Think of it the way an expression might or might not be evaluated in Java/C# when you use logical or. For example, in Java/C# "m = a() || b()" the b() method won't be called if a() is true. Laziness just generalizes this concept.

Option can also be chained with other Option returning expressions using orElse. If I have 3 ships, s1, s2, s3 and I want to get the first available Martian (if any) then

val o=s1.getMartian.orElse(s2.getMartian.orElse(s3.getMartian))

Again, laziness ensures that we only keep looking for Martians until we find one.

Finally, in Scala, Option is a monad. I won't explain all about monads in this article, but I do want to show that Option brings far more power than what I've shown so far. Imagine that from a spaceship I want to get a Martian, get the Martian's ray gun, see who the ray gun's target is, and tell the target to duck. In other words, in Java/C# I want spacehip.getMartian().getRayGun().getTarget().duck(). A nice, easy, one liner. Cool, but now imagine the Martian, the ray gun, and the target are each optional and my rule is that if any of them are null then nobody needs to duck and for God's sake no NoPEs. Urk! In Java/C# you could chain together a bunch of logical ands


if (spacehips.getMartian() != null
  && spacehip.getMartian().getRayGun() != null
  && ...

Or you could pile up a series of ifs

RayGun r = null;
Target t = null;
Martian m = spacehip.getMartian();
if (m != null) {
  r = m.getRayGun();
}
if (r != null) {
  ...

Either way, it ain't pretty. Because Option is a Monad in Scala the code looks like this

for (
  m <- spaceship getMartian;
  r <- m getRayGun;
  t <- r getTarget
) t duck

It might not be clear just yet how the "for" keyword is doing this magic, but you have to admit the code is eminently readable. Far more readable than the Java/C# alternatives.

Hopefully this has convinced you that null really should be considered harmful. Just as it's become accepted that there are better alternatives to "goto" there really are better alternatives to "null."

So go spread the word! End the NoPE madness! Monads are the keys to defeating our Martian overlords!

Yip, yip, yip, yip.

Footnotes

1. My apologies to Sesame Street. Realy, sorry, Muppets.

2. There are several languages with the same solution including most notably Haskell. But don't be scared - I won't use the word "monad." Oops, I just did. Also I used it in the title and in the closing section. Oh, and in the next footnote.

3. In Haskell, the Option monad is called Maybe. 4

4. Monad. Just wanted to say "monad" again.

5. Haskell and OCaml don't have these holes since they have neither null nor casting.

Thursday, August 16, 2007

The Kingdom of Nerbs

In his famous rant Execution in the Kingdom of Nouns, Steve Yegge hilariously excoriates Java for being so "noun oriented" that it's difficult to express ideas that are simple to express in functional programming languages. Scala is a language for the JVM that attempts to unify the funcional and object oriented worlds using first class functions, pattern matching, and what I'm going to call nerbs.

First, a short attention span theater version of Steve's post.1

Once Upon A Time In The Land of JVM

Nouns(together): You there, verbs, get encapsulated at once!
Verbs: Oh please set us free.
Noun1 (implements an interface with only one verb): I am a verb. I am a functor!
Nouns(together): Hahahaha, what a clown.
Citizens of functional lands: Look how much power our verbs have.
Verbs: Free, free, set us free.2

So what was to be done for the poor denizens of the JVM?

To Make a Nerb

There are a bunch of language implementations that support functional programming on the JVM to one extent or another (Cal, Jaskell, Kawa, SISC, Jython, JRuby, Groovy, Rhino, ABCL, hey guys, 'sup?). Unfortunately, none of them are named Java.

For this post I'm going to pretend that Scala is the One True Answer(TM). Other answers will require their own fairy tales er blog entries. Scala is interesting because it not only supports "mere" first class functions, it also supports nerbs.

So what is a nerb?3 Good question, I'm so glad you asked. A nerb is a noun that has been verbed. If you don't believe me, go Google it. But before you do, realize that Google is a publicly traded corporation that makes oodles of cash from selling paid advertising using free web search as a loss leader. But in saying "Google it" I'm not referring to the noun that offers free donuts to its programmers, I'm referring to the verb that this noun is most well known for enabling. Hence the ever so slightly tautological definitions "Google: (verb) to search the web using a web search engine provided by Google - (noun) the company that lets you Google(verb)." 4

Before I continue, let me say that the word "nerb" does not from my close scrutiny seem to appear in any portion of the Scala language specification. But it should.

Back to my butchering of Steve's fairy tale. The verbs are clearly functions and the nouns are clearly objects.5 So a nerb would be an object that's been turned into a function. But in my version of the fairy tale, the verbs all laughed at the noun um object pretending to be a function. Why? Well, because while such beasts work they're just so, so, ... verbose and awkward. Here's one in Java:

public interface Transformer<P, R> {
  public R execute(P param)
}

public class NumberToFrenchStringTransformer 
    implements Transformer<Integer, String> {
  public String execute(Integer param) {
    switch (param.intValue()) {
      case 0: return "zero";
      case 1: return "un";
      case 2: return "deux";
      case 3: return "trois";
      default: throw new 
        RuntimeException("Je ne sais quoi");
    }
  }
}

public class Test {
  void countToThree(Transformer<Integer, String> 
      numberToStringTransformer) {
    for (int i=1;i<4;i++)
      System.out.println(
        numberToStringTransformer.execute(
          new Integer(i)));
  }
  
  public static void main(String[] args) {
    new Test().countToThree(
      new NumberToFrenchStringTransformer());
  }
}

Transformer is a generic interface that requires two types to fully specify: a parameter and a return type. The countToThree method requires a Transformer from Integer to String. The goal is that another Transformer could allow counToThree to speak in some other language, but this code only implements French. The main method hooks everything together.

For a toy example this may not seem so bad. But consider: every time you want to turn an existing function into an object you recreate a significant amount of boilerplate. Imagine writing a significant portion of a real application this way. I could have made it slightly more concise by using an anonymous class, but that would have been a minor change. Let's clean things up for the Scala interpreter.6

def numberToGermanString(n: Int) = n match {
  case 0 => "null"
  case 1 => "ein"
  case 2 => "zwei"
  case 3 => "drei"
  case _ => throw new RuntimeException(
    "Ich bin nicht ein Berliner")
}

def countToThree(
    numberToString: Int => String) =
  for (n <- List.range(1,4)) 
    println(numberToString(n))

countToThree(numberToGermanString)

The play by play: numberToGermanString is a function from integers to strings, countToThree just happens to require such a function, and the last line makes everybody go to town. It's concise and exactly to the point. In a lot of ways it's similar to any other language with first class functions. Again, I could have used an anonymous function but that would have been a minor change. Still we haven't created a nerb - at least not obviously. First class functions are more like gerunds - verbs turned into nouns.

To motivate the desire for a nerb, I ask you this: what else, when given an integer can return a string? Well, how 'bout an array of strings? I can hear you now, "yeah, but an array is a noun not a v.... hey...wait a minute..."

def countToThree(numberToString: Int => String) =
  for (n <- List.range(1,4))
    println(numberToString(n))
  
val words = 
  Array("none", "one", "a couple", "many")
  
countToThree(words)

Yup, in Scala an Array is a nerb. Clearly, an Array is a noun. But we didn't change countToThree a bit and it took the array - the array was verbed. Cool, eh? In scala, getting the 3rd element from the words array just do words(3).

So you might be thinking that arrays must get some special treatment, then, some special syntactic sugar all their own. Nope. You can sprinkle that sugar anywhere you want and turn any of your classes into nerbs.

How? Well, much like you would in Java but you use interfaces (well, traits) that Scala provides.

object NumberToSpanishStringTransformer() 
    extends Function1[Int, String] {
  def apply(n: Int) = n match {
    case 0 => "cero"
    case 1 => "uno"
    case 2 => "dos"
    case 3 => "tres"
    case _ => throw new 
      RuntimeException("Soy un sustantivo")
  }
}

def countToThree(
    numberToString: Int => String) =
  for (n <- List.range(1,4)) 
    println(numberToString(n))
  
countToThree(NumberToSpanishStringTransformer)

Obviously in this case it would be cleaner if I just used a function instead of creating a nerb. But the point here is that I CAN create a nerb - which is nice when I have a more complex class like Array. The "object" keyword means I'm creating a singleton. Function1 is an interface (trait in Scala terms) that is parameterized by two types. Think of it like a generic in Java or a template class in C++ but using square brackets instead of angle braces. The trait requires me to implement one method: apply. In other words, it's pretty much the same as the Java implementation above, except that I was able to treat my object as a function.

The Nerbs United Shall Never be Divided

Earlier I said of our first class function that we had not created a nerb "at least not obviously." Here's the punch line to my cryptic hint: whenever you use a function in a first class manner Scala implicitly creates a nerb. So this code

def numberToGermanString(n:Int) = ... 

def countToThree(numberToString: Int => String) =
  for (n <- List.range(1,4)) 
    println(numberToString(n))
  
countToThree(numberToGermanString)

translates into something along the lines of

def numberToGermanString(n: Int) = ... 

def countToThree(
    numberToString: Function1[Int, String]) =
  for (n <- List.range(1,4)) 
    println(numberToString.apply(n))
  
val $anonymousNerb = new Function1[Int, String]{
  def apply(n: Int) = numberToGermanString(n)
}

countToThree($anonymousNerb)

The byte code generated won't be exactly that but the the gist will be the same: underneath the hood Scala turns first class function creation into nerb creation. This might just seem like just an implementation detail, but it turns out that the Function1 trait provides additional methods for creating function compositions and those methods can be used anytime you create a first class unary function. It's also how Java code can interact with Scala first class functions.

The Grand Unification

In Scala, classes and objects can be turned into nerbs using the object oriented technique of inheritance. Functions and methods can be turned into gerunds using typical functional programming techniques but the gerunds turn out to be nerbs.

Nerbs are a key part to how Scala unifies the object oriented and functional paradigms. There's much more to the unification story including closures and pattern matching. I'll save those for another time.

Once Upon a Time in the Land of Scala

Unlike the land of Java the land of Scala was all peace and harmony. Verbs could be nouned and nouns could be verbed as needed. Together they held hands and sang the songs of nerbiness.

Footnotes

1. My apologies to Steve. Really, sorry dude.

2. My apologies to The Police. Really, sorry dudes.

3. Due credit - I stole the word "nerb" from Nancy Allison's "Every noun can be...".

4. To be madly self referential I would say the word "Google" has been nerbed.

5. Actually, the fairy tale draws the analogy of nouns being both objects and classes but Steve didn't make much distinction and I didn't either. I also won't make the distinction between functions and methods. Please just read on and pretend I know what I'm analogizing.

6. For compiled Scala we just need to wrap all the code in an object that extends Application. I know, I know, it's ironic after all my talk about setting verbs free, but please bear with me until I can talk about singletons.

Monday, August 13, 2007

You Might Be a Blub Neck

In Beating the Averages, Paul Graham formulated the Blub paradox. In short a programmer who only knows a language called Blub looks down on all languages that don't support features that Blub has. At the same time, he1 is incapable of understanding why he would want to use some weird language that has features that Blub doesn't have. The Blub programmer is so used to thinking in Blub that he can't get his head around anything non-Blub.The question is, how do you know if you or somebody else is a Blub programmer? Of course it goes without saying that anybody who reads this blog is kind, highly intelligent, open minded, and motivated to learn.

The comedian Jeff Foxworthy had about five minutes of fame with a schtick of starting each joke with "you might be a redneck if..." Five minutes is a lot more fame than the average blog entry gets, so I thought I'd steal his formula for success.

Here, with a slight modification of the formula, I present

That Jerk on the Internet Might be a Blub Programmer If...

He dismisses other language features as "mere syntactic sugar"

Of course its syntactic sugar. Anything above raw machine code is syntactic sugar. Syntactic sugar is what helps programmers think and work at higher levels. Look at it this way: C and C++ have "goto" and "if". But they also have "while" which is really just syntactic sugar for the right combination of "goto" and "if." C, C++, C# and Java have "for", but it's just syntactic sugar for a certain kind of "while" loop. C++ has object oriented programming, but C++ type OO can be created in C using the right combination of structs and pointers.

In other language families I could go on and on about list comprehensions, pattern matching, type inference, regular expressions, function composition, currying, etc. But one in particular deserves mention: Lisp's most powerful feature is all about syntactic sugar. Lisp macro facilities (including quasiquotes, @ splices, etc) are syntactic sugar that make it easy for a programmer to create new syntactic sugar. If you understand macros then you'll think they're damned cool or damned scary (or both), but you won't dismiss them as "mere" anything. In On Lisp , Paul Graham creates an entire embedded Prolog in Common Lisp. Or take a look at Qi. It creates an incredibly powerful, statically typed, Haskell like language on top of the dynamically typed Common Lisp using a whole lot of macro black magic.2

He dismisses most examples as "toys" that don't show a feature is useful

Face it, most teaching examples are going to be a toys. Real world code is frequently complicated with error conditions, domain specific logic, and adherence to proprietary code standards. None of these things help demonstrate the feature being demonstrated, so examples tend to be small and focused on something that most people are familiar with or can learn in a few minutes. Refusing to try to grok a feature because the example given isn't immediately pertinent to you is a failure of one's imagination.

He questions why "anybody would want to do that in the real world"

The phrase "real world" is highly loaded. It depends entirely on the domains you have experience in. You might not see why C's unsafe casts and unions are useful but let me assure you that for extremely low level performance critical code they can be critical. Haskell's concept of monads might seem arbitrary and weird, but monads have been used to statically prove significant aspects of real programs. And Ruby's dynamic metaprogramming facilities really do help create an environment that is extremely productive in non-trivial systems.

He says his favorite language "can do that" and then creates a giant ball of crufty boilerplate to prove it

Most programming languages are Turing complete. All such languages can perform the same computations somehow. But if you have to create a ball of cruft every time you want to do some particular action, how often are you going to use that feature? If you had to recreate all of number theory every time you wanted to multiply two numbers wouldn't you stop tipping waiters?

Again Lisp is special here. Any feature in another language can be implemented in Lisp using a bit of macro cruft; the difference is that in Lisp the cruft only has to be created in one place. Besides that, macros can be surprisingly uncrufty - most look very much like the syntax they're trying to generate.3

He denies that another language is more powerful than his because "they are all Turing complete"

Hmmm, is he writing raw machine code? If not, he's implicitly admitting that some languages are more "powerful" for some sense of the word "powerful". Powerful is a surprisingly tricky concept to pin down, but because our Blub programmer has chosen Blub and not machine code he must have some definition beyond the computational theoretic meaning. Either that or he's splitting hairs about "powerful" vs "expressive" or some other term.

He dismisses language feature because the syntax isn't "intuitive"

If you think blocks must be denoted using curly braces then you're going to miss out on a very rich set of languages that use some other arbitrary choice. All programming languages are artificial creations and nothing about them is "intuitive" except in the narrow sense of "similar to something you already know." For example, most imperative languages use the single equal sign (=) to mean (re)assignment. It might seem "intuitive," but what's intuitive about using a symmetrical symbol for a fundamentally asymmetrical operation? Before programming languages stole it, that symbol already had a deep history and meaning in mathematics that is completely incompatible. Frankly, Scheme's "set!" and Smalltalk/Pascal's ":=" seem like more reasonable choices, and what could be more intuitive than "<-". But try getting any of them past the Blub lawyers.

This isn't to deny the utility of working on syntax when adding a feature to an existing language. The sense of "intuitive" given above definitely applies here. It's just to say that dismissing a feature in another language because it has a different syntax is pure parochialism.

Help Stamp Out Blub Programmers

This post has been unusually strident for this blog. I mostly intend to present my thoughts with more gentleness and good humor.In a sense, though, this entry is all about preventative medicine. In my future posts I intend to talk about several languages and features. In the process I expect to get many poorly thought-out comments from Blub programmers. It's my hope that this post will at least slow some of them down to think, "if I write this, will everybody think I'm that jerk on the Internet?"

It probably won't work, but that's never stopped me before.

Before I close this out, there are a few things that do not make you a Blub programmer:

You probably aren't a Blub programmer if...

You can admit ignorance

While ignorance is a key ingredient for Blubness, it's not the only ingredient. The Blub programmer is willfully ignorant, actively pushing back against anything new. But ignorance itself is just a temporary condition if its joined with an open mind.

You've tried something and just don't like it

Hey, not every feature is all the hype promises it to be. Not liking something that you have tried isn't the same as not liking something you never want to try. Just be open to the possibility that the feature might work well in some other environment, in another language, or with a better implementation.

Footnotes

1. The usual apologies about using "he" instead of "he or she." One Div Zero officially recognizes that women have full and equal rights to be jerks and Blub programmers.

2. Liskell does the opposite. It puts a Lisp like syntax, including macros, on top of Haskell.

3. One complaint that even thoughtful people have leveled against both Common Lisp and Scheme is that they seem more like Language Development Kits than languages. In part this impression is created by the fact that the standard definitions for both are getting a bit crusty with age. Sure, you can build a nice list comprehension macro but wouldn't it be nice if a standard one came in the box? The counter argument is that the language development kit allows you to move your environment into domains that are too specialized for a standard.