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
}

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.

Code Monkeyism's Post Is Unfit For Serious Reading

Stephan Schmidt makes several points in Scala Is Unfit For Serious Development . Some are even valid. Unfortunately, the valid points are buried in over-generalizations and attacks on the attitudes of the developers and community.

It's unfit because the developers and the community are unwilling.

At the end of his little diatribe he thanks 2 members of the community for helping him with his problems. Sounds pretty willing to me.

1. The developers are interested in language research and writing papers, not in making a language for real development

So far from true. Yes they write papers. But real development is very much a goal of Scala. If it weren't then Java interoperability would be ditched yesterday. Java interop is a giant albatross around Scala's theoretical neck. Some examples of how Java interop fights Scala: null sucks, the jvm doesn't do general tail calls, structural types are hacked in using reflection, and traits/mixins require a rube-goldberg copy mechanism. Java interop is only a practical concern for real programmers who want to get stuff down now with existing libraries.

2. The version hell that is 2.8 - calling this version 2.8.0 is deceptive. As Python (3000) or Ruby (2.0) this should have been a major version called 3.0

Some truth. Ruby made nasty breaking changes in 1.9.1 and Python isn't immune to them. None-the-less, it really should be called Scala 3.0 to communicate the extent of the changes.

3. The developers do not care about binary compatibility, deprecated, soft migration or API compatibility. Things are changed on a whim - from one RC to the next, and they change major parts of the language/libraries in point releases.

There is a significant technical challenge to maintain binary compatibility given the fact that the JVM has no multiple-inheritance mechanism. But that shouldn't be confused with a lack of caring. Martin Odersky has promised that the next major release will focus on solving the binary compatibility issue once and for all. Deprecation - could have been done better. Definitely. Then again, Schmidt is playing with beta software where API INcompatibility are pretty much guaranteed.

4. They remove and add classes just as they see fit.

A repeat of point 3.

5. The community loves cutting edge. Instead of fixing bugs they upgrade to all new released RCs - so have you. It's called cutting edge for a reason: You'll cut yourself. And it's called bleeding edge because you will bleed.

An overgeneralization. "The community" is apparently represented by the library causing Schmidt his problem. Other developers seem to be more careful. lift, for instance, has been very careful about its migration policy and just released version 2.0 against the stable version of Scala.

Conclusion

Scala's binary compatibility sucks due to a real technical challenge interoperating efficiently with the JVM. The 2.8 series is really 3.0. Deprecation could be done better. One library that Schmidt used decided to fix a bug and compile against a beta version of Scala. Schmidt jumped into the beta version. A small bit of versioning hell ensued. From this Schmidt concluded that the Scala development team do not care and that Scala is unfit for development.

In the meantime, back in reality, the small Scala development team is continuing to move forward with a great language. The community continues to put out awesome libraries. Businesses like Novell, Twitter, and FourSquare continue to make bets on Scala.

Is Scala flawed. Hell yes. But if you think it's a great language then contribute. Help make it and its ecosystem better. Help the developers of libraries maintain bug fixes on stable branches, or help test for breaking changes and push for a deprecation model, or contribute constructively to the binary compatibility challenge. Don't take potshots against the developers from the sidelines.

Robert Fischer Finally Admits that Scala is Functional

Robert Fischer says

If your language doesn’t lead people to re-discover point free programming at least in the small, then the language really isn’t taking function manipulation and functional language type conceptions seriously.

Thus Fischer has finally recognized that Scala is functional.

val double : Int => Int = 2 * // point free function definition
List(1,2,3) map double /* removes one point from List(1,2,3) map {x 
   => double(x)} */

Thank you Robert for finally getting to the truth.

Oh, the Underscore

Now, Robert may object because I didn't combine map and double into one super function, mapDouble. Okay

val mapDouble : List[Int] => List[Int] = _ map double
mapDouble(List(1,2,3))

Crap, there's an underscore. Is it a "point"? Good question. And the answer is no. In fact, what it is is a hole in the expression. Oleg Kiselyov, somebody who actually knows about functional programming, says they're related to delimited continuations and what could be more functional than delimited continuations?

Also, Erlang Remains Unfunctional

For some reason Fischer really hates on Erlang. Point-free is definitely not Erlang's strong suit at all due to it's ability to overload on arity. I don't know why the Erlangers don't go picket his blog.

Post Script on Converses

David MacIver points out (correctly) that my post assumes that a statement implies its converse. To that I say "pffft, write your own damn parody, David!"

Getting to the Bottom of Nothing At All

Except when I'm being a total smart ass or self indulgent emo telling the Ruby community to f' off, most of what I write talks about practical stuff, often with a small dose of theory. But this time it's about theory with a small dose of practice.

Last time I talked about the way programmers in popular C derived languages C++, Java, and C# think of a void function as being one that returns nothing. I contrasted this with the functional view that such functions return something, they just return the unit value (), something that doesn't carry any information. To expand on this I want to talk about actually returning nothing.

In any Turing complete language it is possible to write a function that really truly never returns anything, not even a made-up singleton value like (). In C style languages the simplest such function might contain an infinite loop like

while(true);

For my purposes a better way to explore the idea is with infinite recursion. Pretend your favorite C style language does tail call optimization[1] so we can ignore stack overflow issues and examine the following

X foo(){ return foo(); }

The question is what should the X be? And the answer is that if you plug that line of code into C, C++, C#, or Java then X can be just about any type you want[2].

If that doesn't give you pause then consider this: your type system appears to be lying to you. The function is promising an X but has no hope of delivering. And its quite happy to promise you any X. If you write "String foo(){ return foo(); }" then your type system considers the expression "foo();" to have type String so that you can write "String myFoo = foo();". But guess what, foo doesn't return a String and myFoo will never get a String. Is the type system lying?

The answer is no, of course not. It's just proving something a bit weaker than you might think at first. Instead of proving that "foo() will compute something that is a String" it's proving that "foo() won't compute something that isn't a String." If your "Law of the Excluded Middle" sense just tweaked, then you're on the right page. You'd think there are only two cases to consider: either the function definitely computes a String or it definitely doesn't. But there's this third case where it doesn't compute anything, and since the type checker can't reliably detect non-termination (c.f. Turing Halting Problem) it has to do something a bit odd. First, it assumes that the foo() declaration is correct and does return a String. Then it goes looking for a contradiction such as returning an int. Inside the function the compiler sees that the return is the result of the expression foo(). But the compiler has already assumed that foo() returns a String. There's no contradiction between declared and result so all is happy. The word "tautology" should come to mind right about now. By assuming X is true the type checker has proved that X is true. This weakening is a practical consequence of the Turing Halting Problem and there are at least two good ways to think about it. But first some more examples of the phenomenon.

Exceptions and Exits and ...

I very casually suggested that we ignore stack overflow issues in the infinite recursion above. But exceptions are an important part of this story because they are, in some interesting way, related to non-termination. Consider this function (or its equivalent in your favorite language)

X foo(){ throw new RuntimeException(); }

Once again, X can be any type. And once again foo() does not in fact compute an X.

Clearly these two definitions of foo are different things. Non-termination means we're stuck whereas an exception means we might be able to recover and try something else, or at least notify that there's a problem and shutdown cleanly. None-the-less they both behave similarly. First, they hijack the normal flow of control in such a way that it never returns back to the caller. And second they are both examples of a kind of weakening in the type system since any type can be substituted for X. Formally they are both examples of functions that diverge (functions that return normally are said to converge).

The Type

Here's a third example of a diverging function in Java. Translate as necessary for your language (in Java System.exit(n) stops the program immediately and returns n to the calling process).

X foo(){ System.exit(1); return null; }

Yet another case where foo() won't compute anything, it diverges. In fact, the return statement after the exit call is dead code. However, this is example is slightly different than the other examples because we had to create the dead code for the compiler to be happy[3] and, in fact for a different "X" like int the return value might have to be changed. That bit of dead code is closely related to the heart of this article.

Java can detect some kinds of dead code. If you write "X foo() { throw new RuntimeException(); return null; };" then Java recognizes that the return is unreachable and complains. In my System.exit(1) example Java didn't recognize that the call to exit() will never return so it required a following return statement. Obviously "throw" is a keyword and can get special attention that a mere library function can't but it would be useful to be able to let Java know that, like throw, exit() diverges.

One of the best ways to tell a compiler how a function behaves is by using types and, in type theory, there's a type that expresses just what we need. The type is called bottom (often written ⊥), and while there are different ways to look at the bottom type I'm going to go with a subtyping based view that should be accessible to C++, C#, and Java programmers.

If a language has subtyping and a function says it will return a type "X" then the function is allowed to return a "Y" instead as long as Y is a subtype of X. In my example of a function that just throws an exception the return type could be anything at all. So if we wanted System.exit(1) to indicate that it diverges the same way throw does, then its return type should be a subtype of all types. And indeed, that's exactly what bottom is.[4] bottom is a subtype of String, and int, and File, and List<Foo>, and every other type. Usefully, conventional type hierarchies are written with supertypes above subtypes, which makes a convenient mnemonic for "bottom" which needs to go below everything on such a hierarchy.

Now, if you're used to OO thinking then you expect a value with a certain subtype to in some sense be substitutable everywhere that a supertype is expected. But how can any one object behave like a String, an int, a File, etc? Remember that bottom indicates divergence: an expression with type bottom can never compute a value. So if exit()'s return type was bottom it would be totally safe to write "String foo() { return System.exit(1); }" while another bit of code could have "int bar() {return System.exit(1); }."

Making it Useful, A Divergence to Scala Divergence

Occasionally it might be useful to indicate that a function diverges. Examples are functions like System.exit(1), or functions that always throw an exception, perhaps after logging something or doing some useful calculation to create the exception. But interestingly out of all the statically typed languages that have any following outside of pure research only Scala has an explicit bottom type, which it calls Nothing. The reason Scala has a bottom type is tied to its ability to express variance in type parameters.

For some reason a lot of programmers run screaming into the night when you say "covariance" or "contravariance." It's silly. I won't get into all the details of variance, but I will say that in Scala the declaration "class List[+T] {...}" means that List[Subtype] is a subtype of List[Supertype]. No screaming necessary. And List[+T] brings me to one extremely practical use of bottom - what type should an empty List have?

Well, an empty List can have type List[String] or List[Foo] or List[int]. T can be whatever. And what's a subtype of whatever for all values of whatever? You guessed it: bottom (Nothing). Indeed, Scala has one constant called Nil whose type is List[Nothing]: a subtype of List[String], List[int], and List[whatever]. It all ties up in a bow when you consider that a List[T] has a method called head which returns the first element of the list as type T. But an emtpy list has no first value, it must throw an exception. And sure enough, head in List[Nothing] has type Nothing.

C# 4.0 is supposed to be getting definition site variance similar to Scala's but using the clever mnemonic keywords "in" and "out". I haven't heard anything yet on whether it will also add a bottom type, but it would make a lot of sense.

Java has usage site variance using wildcards. You can say "List<? extends Supertype> x" to indicate that x can have a List<Supertype> or a List<Subtype>. The bottom type would be useful in Java, too, although not as compelling since wildcards are so verbose people rarely use them even when they would make sense. Plus, Java folk tend to mutate everything and List[Nothing] in part makes sense in Scala because Scala Lists are immutable.

C++ does not have any simple way to express this kind of variance so the bottom type is even less compelling in C++ than it is in Java.

Back On Track

Haskell and languages in the ML family don't have an explicit bottom type. Their type systems don't have subtyping so adding bottom as a subtype would confuse things. None-the-less, they do have a nice way to express bottom that can be teleported back to Java, C#, and C++ (but not C). Recall that bottom is a subtype of all types. Another way of saying that is that if a function returns type bottom then for all types A, the function returns something compatible with A so why not express that directly? In Haskell the "error" function takes a string and throws an exception.

Prelude> :type error
error :: [Char] -> a

In Haskell, a lower case identifier in type position is always a type parameter, and [Char] means "list of Char", aka String. So for all types a, if "error" doesn't diverge then it will take a String and return an a. That can pretty much be expressed directly in Java

public static <A> A error(String message) { throw new RuntimeException(message); }

or C++

class message_exception : public std::exception {
  public:
    explicit message_exception(const std::string& message) : message_(message) {}
    virtual ~message_exception() throw() {};
    virtual const char * what() const throw() { return message_.c_str(); };
  private:
 const std::string message_;
};

template <typename A>
A error(const std::string& message) {throw message_exception(message); }

And for either language, usage would be something like

int divide(int x, int y) {
  if (y == 0) {
    return error<int>("divide by zero"); // drop the "<int>" in Java
  } else {
    return x / y;
  }
}

Haskell also has a function called "undefined" that simply throws an exception with the message "undefined." It's useful when you want get started writing some code without fully specifying it.

Prelude> :type undefined
undefined :: a

The function isn't as interesting as the type, which promises that for any type a "undefined" can compute an a or diverge. Since "undefined" can't possible just produce a value of any arbitrary type, it has no choice but to diverge. The same idea can be added to Java

public static <A> A undefined() {return error("undefined"); }

or C++

template <typename A>
A undefined() { return error<A>("undefined"); }

In either language it might be used as

string IDontKnowHowToComputeThis(int input) { 
  return undefined<string>(); // again, make appropriate changes for Java
} 

Given the requirement to write the "return" keyword in C#, Java, and C++ I'm not sure how practical something like a generified error function really is as compared to having it return an exception and making the user write 'throw error("blah")', nor whether "undefined" is that much more useful than just throwing an UndefinedException, but this does illustrate the relationship between the bottom type and functions that, in Haskell terms, compute "forall a.a" or in C#/Java/C++ terms return the type parameter A without taking an A as an argument.

Also, as always care should be taken when transliterating from one language to another. Java would allow a function like "undefined" to return a null instead of diverging. C++ would allow it to return anything all and would only fail to compile if it were used in an incompatible way. That contrasts with languages like Haskell and ML in which the only way to implement "undefined :: a" is to make it diverge in some form or fashion[5].

The Bottom Value

I've spent some time talking about the bottom type as having no values. But it does have expressions like "undefined()" and that leads to a rather philosophical notion of how to think of bottom as having a value. Sorta. Skip this section if you don't like total gray beard philosophizing. If you're brave, then stick with me and imagine a subset of your favorite C derived language that does not allow side effects. No mutation, no IO, and no exceptions. In this strange world functions either just compute values or they diverge by not halting. In such a world the order of evaluation mostly isn't important as long as data dependencies are met - in f(a(), b()), you can compute a() before b() or b() before a(), whatever, they can't interfere with each other. Doesn't matter. The only time order of evaluation is forced on us is when there are data dependencies, so "a() + b()" must compute a() and b() (or b() and a()) before their sum can be computed. Nice.

Well, almost. Order of evaluation can matter for expressions that diverge. Let me give an example.

int infiniteLoop() {return infiniteLoop();}
int f(int x) {return 42;}
int result = f(infiniteLoop());

Because f ignores its argument, if we call "f(infiniteLoop());" there are two possible outcomes. If "infiniteLoop()" is eagerly evaluated before f is called then the program will diverge. On the other hand, if the expression "infiniteLoop()" is lazily remembered as being potentially needed later then f can successfully return 42 and the diverging expression can be forgotten just like it never happened (because it didn't).

We've gone to the pain of eliminating side effects from our language so it's a little irritating to have to keep thinking about evaluation order just to deal with divergence, so we perform a little mental trick; a little white lie. Imagine that functions like infiniteLoop above don't get stuck, they compute a value called ⊥, which is the only value of type bottom.

Now, since the bottom type is a subtype of all types and ⊥ is the bottom value, then it follows that every type must be extended with ⊥. Boolean = {⊥, true, false}, int = {⊥, 0, 1, -1, 2, -2, ...}, and unit = {⊥, ()}. That means we need some rules for ⊥ and how it interacts with everything else. In the vast majority of languages including Java, C#, and C++ but also impure functional languages like F# and OCaml doing just about anything with ⊥ can only compute ⊥. In other words, for all functions f, f(⊥) = ⊥. If you write f(infiniteLoop()) in those languages then the result is ⊥. This kind of rule is called "strictness".

In contrast, Haskell is often called a "lazy language," meaning that expressions aren't evaluated until they're needed. That's not quite technically correct. The Haskell spec just says that it is "non-strict." The spec doesn't care when expressions are evaluated so long as programs allow ⊥ to slide as far as possible. An expression like f(infiniteLoop) must evaluate to 42. Haskell basically forces an expression involving ⊥ to evaluate to ⊥ only when the argument must be used[6]. The distinction between "lazy" and "non-strict" is subtle, but by being "non-strict" rather than "lazy" a Haskell compiler can use eager evaluation anytime it can prove that doing so doesn't change behavior in the face of ⊥. If a function always uses its first argument in a comparison, then Haskell is free to use eager evaluation on that argument. Since Haskell truly does forbid side effects(unlike our imagined neutered language above), the choice of evaluation strategy is up to the compiler and invisible except for performance consequences[7].

C++, Java, and C# have just a tiny bit of non-strictness. In these languages "true || ⊥" is true and "false && ⊥" is false. If these languages were totally strict then "true || ⊥" would be ⊥. Users of these languages call this behavior "short circuiting" and it's done for performance reasons rather than being a philosophical goal, but it's still a curious departure from their normal rules.

There you have it. The bottom value ⊥ is a clever mental hack to allow purely declarative functional code to be reasoned about without injecting sequencing into the logic. It allows people to talk about the difference between a purely declarative strict language and a purely declarative non-strict language without getting into details of evaluation order. But since we're talking about languages that aren't so purely declarative, we can take off our philosopher hats and return back to the world where side effects are unrestricted, bottom is a type with no values and divergence means that flow of control goes sideways.

Tuples and Aesthetics

Last time I talked about the unit type and how, if you interpret types as logical propositions, the unit type behaves as a "true" and tuple types act as logical and "∧." I also talked about an algebraic interpretation where unit type acts like 1 and tuple types act like multiplication "×". So the type (A,B) can also be written as A∧B or A×B. The type (A,unit) is isomorphic to A, A×1 = A, and A∧True <=> A.

Bottom has similar interpretations as 0 or False. The type (A,bottom) is isomorphic to the bottom type because you can't compute any values of type (A,bottom). A×0 = 0, and A∧False <=> False. Nice how it all hangs together, eh?

Bottom behaves like False in another way. In logic if you assume that False is true you can prove anything. Similarly in type systems the bottom type allows the programmer to promise to do even the impossible. For instance, here's a Java function signature that promises to convert anything to anything.

public static <A,B> B convert(A arg) {...}

If you ignore dynamic casting and null (they're both weird in different ways) there's no meaningful way to implement that function except by diverging. More on this in an upcoming episode.

Conclusion

I somehow don't think anybody will be running into the office saying "I just read an article on the bottom type, so now I know how to solve our biggest engineering challenge." But the bottom type is still interesting. It's a kind of hole in your static type system that follows inevitably from the Turing Halting Problem[8]. It says that a function can't promise to compute a string, it can only promise to not compute something that isn't a string. It might compute nothing at all. And that in turn leads to the conclusion that in a Turing complete language static types don't classify values (as much as we pretend they do) they classify expressions.

Footnotes

1. gcc does do tail call optimization under some circumstances.
2. Oddly, in C, C#, and Java X can't be "void" because its an error to return an expression of type void. C++ does allow void to make writing templates a bit easier.
3. Yes, I can make it a void function and not have a return. But again that would illustrate how exit() is different from a throw: throw doesn't require the return type to be void.
4. Note I'm saying "subtype" here and not "subclass." int, List<String>, and List<File> are 3 different types. In C++, Java, and C# int doesn't have a class. In Java and C# List<String> and List<File> both come from the same class. Yet bottom must be a subtype of all 3 so it can't be a subclass.
5. A plea to my readers: I'm too lazy to see if "forall a.a" is bottom in F# or C#, or if, like Java, null would be allowed. My bet is that null won't be allowed because only Java has the peculiar notion that type parameters must be bound to reference types.
6. Very loosely speaking. Please see the Haskell Report for all the gory details about when Haskell implementations are allowed to diverge.
7. Haskell has another clever hack where throwing an exception isn't an effect, but catching one is. Since order of evaluation is unspecified in Haskell, the same program with the same inputs could conceivably cause different exceptions. Exceptions are theoretically non-deterministic in Haskell.
8. A language that isn't Turing complete can prove termination and does not need a bottom type, but such a language isn't powerful enough to have a program that can interpret the language.

Void vs Unit

I suspect most people who come to one of the statically typed functional languages like SML, OCaml, Haskell, F#, or Scala will have only seen static typing in one of the popular C derived languages like C++, Java, or C#. Some differences in type system become clear fast. One particular spot is the relationship and difference between void and unit.

So imagine your favorite C derived language. Consider your language's equivalent of the following function definition [1]

void printHello(String name) { printf("hello %s", name); }

What does the word "void" mean? To any C, C++, Java, C# programmer it means that printHello doesn't return anything. Simple.

But a functional programmer[2] sees it quite differently. This article will explain the different point of view and why it's useful.

What's a Function?

It turns out to be very hard to write a single definition of "function" that covers all the ways the word has been used. But to a functional programmer at the very least a function is something that maps inputs to outputs. In the impure functional languages that function may also have an effect like printing "hello." I'll stick with the impure definition in this article.

Now, when a functional programmer talks about mapping inputs to outputs he or she doesn't mean taking a string as an input and outputting it on the console. Instead he or she is talking about arguments and returns of a function. If something is to have any pretense at being a function, or at least a function that returns normally, then it must return something.

printHello clearly does return normally so a functional programmer insists that it returns something. But a functional programmer also must recognize that it doesn't return anything "meaningful."

Thus rather than the concept "void," a functional programmer thinks of unit. In some languages the unit type is written as (), but for clarity I'm going to stick with "unit." Now, unit is a type, conceptually not much different from say "int". But unit, as its name somewhat implies, has exactly one value conventionally represented as an empty pair of parentheses ().

In OO terms () is a "singleton". There's only one instance of it. It's also immutable. In a very real sense it carries no information. You can't write a program that behaves differently based on what a function of type unit returns - it always returns the same ().

A Performance Diversion

At this point a little guy in the back of your head might be asking "doesn't returning something meaningless just waste cycles?" Well, it's important to distinguish between abstraction and implementation. The unit value, (), is an abstraction that the implementation is free to optimize away. If you write in Scala

def printHello : Unit = {
  println("hello")
  ()
}

Then the compiler will generate the equivalent of the original void based code. If in Scala you write

print(printHello)

Then the compiler might generate something like

printHello
print( () )

Because () is a singleton it doesn't matter at the machinecode/bytecode level that it's not "actually" returned. The compiler can figure it out with no performance hit at all.

Making It Useful

Okay, blah, blah, blah, functional think this, unit that. Whatever. What's the point? () is a value with no information, unit is a type with only that value...what's the practical use?

Well, it turns out that its useful for writing generic[3] code. Java and C++, somewhat famously, do not have first class functions. But they can be faked. Here's the Java

interface Function<Arg, Return> {
   Return apply(Arg arg);
}
Function<String, Integer> stringLength = new Function<String,Integer> {
  Integer apply(String arg) {
    return arg.length();
  }
}

In C++ you can do it essentially the same way with a template and operator() overloading[4]

template <typename Arg, typename Result>
struct Function {
  virtual Result operator()(Arg arg) = 0;
};
struct StringLength : Function<string, int> {
  int operator()(string arg) {
     return string.length();
  }
}
Function<int, string> *stringLength = new StringLength();

C# has a function type and lambdas so it's very easy to write.

Func<string, int> stringLength = s => s.Length;

So, if stringLength is an object of type Function<String, int> / Function<int, string> * / Func<string, int> then I can write the following

int result = stringLength.apply("hello"); // Java
int result = (*stringLength)("hello"); // C++
int reulst = stringLength("hello"); // C#

So here's the question: how would I convert the printHello function earlier into a Function<String,X>/Function<string, X> */Funct<string, X>. What type is X?

If you've been playing along so far you recognize that it "should be" void, but Java and C# don't allow it. It's invalid to write Function<String, void> in either language.

Let's pretend you could. After all, C++ will let you write a class PrintHello : Function<std::string, void>. But there's still a problem even in C++. Generic code might expect a result and none of these languages let you denote a value of type void. For instance (in Java) imagine thise simple bit of reusable code.

public static <A,B> List<B> map(List<A> in, Function<A,B> f) {
  List<B> out = new ArrayList<B>(in.size());
  for (A a : in) {
     out.add(f.apply(a));
  }
  return out;
}

C++ has std::transform and C# has IEnumerable#Map, which are more or less the same idea.

Anyway, given something like the above calling map/transform/Map with a list of strings and the printHello object should result in a List<void> of the same length as the original list. But what's in the list? The answer, in a functional language, is a bunch of references to (). Tada, the meaningless is useful for writing generic code.

C++ will allow a Function<std::string, void> but any attempt to call something like map with it will fail to compile. C++ doesn't have a () value so our generic code has become slightly less generic.

The Work Arounds

Java, C++, and C# programmers do solve this problem all the time. One common option is to not use Function<string, void> but some other concept like "Action<string>" to mean a function that takes a string, performs a side effect, and returns nothing useful. Then you essentially duplicate "map" into something called perhaps "foreach" that expects an Action<T> and returns void. That probably makes sense in this case since a list of references to a meaningless value is perhaps silly, but it also means a great deal of code duplication if this kind of higher order programming is common. For instance, you can't write just one compose function that creates a function from two other functions, you also have to write a compose that takes an action and a function to create an action.

Another answer is to make the printHello function object have type Function<String,Object>/Function<string,void*>/Func<string,object> and return a null. That's pretty disgusting.

Perhaps the best option is to create your own Unit enumeration with only a single value. That does leave Unit nullable in Java, but railing against nullability in Java is another blog post.

enum Unit { unit }; // C++, Java, or C#

As for good old C, well, the type system doesn't do parametric polymorphism so generic code in C is problematic no matter what you do. Still, with function pointers it's conceivable you might find a use for a unit value. Typically a C programmer would use 0.

A Quick Aside About Purity

For the most part I've casually used effects everywhere. Most functional languages like SML, OCaml, F#, and Scala are impure and let the programmer get away with that. Some functional languages, e.g. Haskell without unsafe* extensions, do not. They must track effects using the type system. But even with this caveat, the unit type is still useful to, for instance, distinguish from a function that fetches a string from the keyboard which would have might have type IO String vs one that prints to the console which might have type String -> IO Unit.

Conclusion

Void and unit are essentially the same concept. They're used to indicate that a function is called only for its side effects. The difference is that unit actually has a value. That means that unit functions can be used generically wherever a generic first class function is required. The C derived languages miss out by treating void functions as functions that don't return anything instead of as functions that don't return anything meaningful.

Next time I'll talk about functions that really, truly return nothing.

Postscript on Aesthtics and Tuples

Mostly I've talked about the practical value of the unit type in this article, but I do love it when convenient practice and beautiful theory line up. So here's an attack from a different direction.

Many functional languages have tuples. A tuple is an ordered fixed size collection of values of (possibly) different types[5]. Tuple types are usually written with parens. For instance, (Foo, Bar) is the type of pairs (2-tuples) with one Foo, one Bar. The same type is sometimes written as Foo × Bar, which makes sense too. You can see the type as a set that consists of a kind of Cartesian product of the Foo and Bar sets. For instance if Foo has only two possible values {f1, f2} and Bar has only two possible values {b1, b2} then the type Foo × Bar has 4 possible values, {(f1, b1), (f1, b2), (f2, b1), and (f2, b2)}.

You can have tuples that with higher numbers of members like triples and 4 tuples and such.

What about a 1-tuple? Well, the type Foo can be seen as a 1-tuple. There's would be no useful difference between the type Foo and the type (Foo).

The question to ask is, given that we have 3-tuples, 2-tuples, and 1-tuples does it make sense to have a 0 tuple? The answer, dear reader, is unit. The unit value is a tuple with no members. That's why Haskell calls both the type and the value "()" - it's like the type (A,B) without the A,B. And just as an empty list and empty set aren't quite "nothing" neither is the empty tuple.

And here's another interesting thing, type theorists will also call the unit type "1" (not to be confused with the value 1). To see why, look at the type (Foo, unit) which can also be written as Foo × 1. If Foo only has 2 possible values {f1, f2} then the entire set of possible values for the type Foo × 1 is {(f1, ()), (f2, ())}. It's the same 2 values extended with a little bit of "meaningless" information that can be stripped off or added back in as desired. Formally speaking it's isomorphic to the type Foo. To abuse notation slightly, Foo × 1 = Foo. So unit is not only the type that has only 1 value, it's the type that behaves like a 1 at the type level.

Footnotes

1. In C of course it would be char *name, in C++ it might be char * or I might use the string and iostream libraries. Whatever. The differences aren't that relevant to this discussion.
2. To save myself a lot of time I'm using phrases like "functional language" to mean the statically typed functional languages that have been influenced to a large extent by ML. Some of what I'm talking about does translate into some dynamically typed languages as well, although they often "pun" things so that there isn't a unit value that's distinct from nil, null, false or some other singleton value.
3. I use the phrase "generic" here to mean what the functional community means by "parametrically polymorphic" or just "polymorphic." However, my target audience is more likely to associate polymorphism with OO dispatch, so "generic" it is.
4. In C++ you can also do it without the pure virtual base class and just use template structural typing based on operator(), but shortly it'll be easier for me to describe a problem if I use a base class to give the concept a name. I could also allocate on the stack but that slightly confuses my point. I'm going this route to keep things symmetrical among the languages. Besides, this isn't a tutorial on why C++ isn't Java. On a related note it's a shame C++0x won't have concepts.
5. This is quite different from a Python tuple which is really just a list.

"Fixing" Groovy?

In response to my last article on Groovy's lack of static typing James Strachan, the original Groovy guy, tweeted "groovy should fix this really IMHO." Well, perhaps. But "fixing" it would substantially change Groovy's semantics. Most importantly it would prevent Groovy from executing some programs that work just fine right now.

An Example

Here's a simple example of a program that works now but wouldn't under a static typing regime. It's a simple variation on the program from the previous article.

interface Foo {}
interface Bar {}
class Baz implements Foo, Bar {}

Foo test(Bar x) {return x}

test(new Baz())
println("Everything's Groovy")

Compile it, run it, and feel groovy.

~/test$ groovyc test.groovy
~/test$ groovy test
Everything's Groovy

If I transliterate into Scala

trait Foo
trait Bar
class Baz extends Foo with Bar

def test(x : Bar) : Foo = x

test(new Baz)
println("Everything's Scala?")

And try to compile

~/test$ scalac -Xscript test test.scala
!!!
discarding <script preamble>
(fragment of test.scala):5: error: type mismatch;
 found   : this.Bar
 required: this.Foo
def test(x : Bar) : Foo = x
                           ^
one error found

Scala rejects a program that Groovy is happy with.

Conclusion

That's the nature of the beast. Static typing rejects some good programs that might otherwise work. And as my last article showed, dynamic typing allows some bad programs that can't possibly work. That's a pretty fundamental difference and there's no way around it.

If the Groovy community wants to make its type annotations work in a more statically typed manner that's ok. This article just shows that such a change wouldn't be 100% compatible with today's Groovy.

Groovy Does Not Have Optional Static Typing

Every now and then somebody writes that Groovy supports optional static typing. But it doesn't. They've confused the use of type annotations on variables with a static type system.

This article is emphatically not an entry in the long, sad, and mostly insipid static vs. dynamic debate. It is a clarification of a misunderstanding.

Definitions

The word "static" in "static type system" is related to phrases like "static analysis." Basically, without executing the code in question, a static type system analyzes code to prove that certain kinds of misbehaviors won't ever happen.

The word "dynamic" in "dynamic type system" is related to the "dynamic execution" of a program. In contrast to a static type system, a "dynamic type system" automatically tests properties when expressions are being (dynamically) evaluated.[1]

The Proof

With those definitions its easy to show that adding type annotations to a Groovy program does not make it statically typed. Create a file named test.groovy. In it define a couple of unrelated classes

class Foo {}
class Bar {}

Now write a function that promises to take a Bar and return a Foo. Add a println for fun.

Foo test(Bar x) { return x }
println("Everything's groovy")

Compile it and run it (explicitly compiling isn't necessary, it just reinforces my point)

~/test$ groovyc test.groovy
~/test$ groovy test
Everything's groovy

There were no complaints at all. A static type system would have rejected the program.

Open up test.groovy and make a slight adjustment so that the function is actually called

Foo test(Bar x) {return x}
println("Everything's groovy")
test(new Bar())

Compile and run this

~/test$ groovyc test.groovy
~/test$ groovy test
Everything's groovy
Caught: org.codehaus.groovy.runtime.typehandling.GroovyCastException: 
Cannot cast object 'Bar@861f24' with class 'Bar' to class 'Foo'
 at test.test(test.groovy:4)
 at test.run(test.groovy:6)
 at test.main(test.groovy)

A runtime exception is finally thrown at the (dynamic) moment when the test function is executed. That's dynamic checking rather than any form of static proof.

Actual Static Typing

Now open a file named test.scala.

class Foo
class Bar
def test(x : Bar) : Foo = x

Compile as a script

~/test$ scala -Xscript test test.scala
(virtual file):1: error: type mismatch;
 found   : this.Bar
 required: this.Foo
object test {
^
one error found

Ta da, static typing. With no attempt to execute my test function the type checker says "I have reason to believe this might go sideways."

The Misunderstanding

There's an oft repeated phrase that "in a statically typed language variables are typed." There's also a common misunderstanding that static typing and type annotations are the same thing. I can show a simple counter example to both misconceptions with one language: Haskell.

Create a file named Test.hs. Here's a function called flatten. It flattens a list of lists one "level" to just be a list.[2]

flatten = foldl (++) []

No variables were harmed during the creation of that function. It's written in what's called "point free" style. Yet with neither variables nor type annotations I can show it's statically typed by defining a bogus main function

main = print $ flatten [1,2,3,4,5,6]

And trying to compile

~/test$ ghc Test.hs -o test
Test.hs:3:24:
    No instance for (Num [a])
      arising from the literal `1' at Test.hs:3:24
    Possible fix: add an instance declaration for (Num [a])
    In the expression: 1
    In the first argument of `flatten', namely `[1, 2, 3, 4, ....]'
    In the second argument of `($)', namely
        `flatten [1, 2, 3, 4, ....]'

Thus you need neither variables nor annotations to have static typing. A small change fixes things right up

main = print $ flatten [[1,2,3],[4,5,6]]

~/test$ ghc Test.hs -o test
~/test$ ./test
[1,2,3,4,5,6]

It's easy enough to see what type GHC has assigned the function. Just add a module declaration at the very top of the file

module Main (flatten, main) where

And fire up ghci

~/test$ ghci
Loading package base ... linking ... done.
Prelude> :load Test
Ok, modules loaded: Main.
Prelude Main> :type flatten
flatten :: [[a]] -> [a]

Exactly as described, it takes a list of lists and returns a list.

Groovy Does Have Static Typing

Having shown that Groovy does not have static typing let me show that it does have static typing. :-) At least, it has static typing for some kinds of things. Open up test.groovy again and add this

class MyRunnable implements Runnable {}

Compile that and you get an error

~/test$ groovyc test.groovy
org.codehaus.groovy.control.MultipleCompilationErrorsException: startup failed, test.groovy: 8: 
Can't have an abstract method in a non-abstract class. 
The class 'MyRunnable' must be declared abstract or the method 'void run()' must be implemented.
 @ line 8, column 1.
   class MyRunnable implements Runnable {}
   ^

1 error

The error happens without executing anything so it's a form of static analysis, and it's caused by failure to adhere to the Runnable type's requirements hence it's a static type error. But it's not an optional static type check - you can't turn it off.

Interesting, no?

Conclusion

Whatever you feel positively or negatively about Groovy please don't perpetuate the myth that it has optional static types. It doesn't. Groovy's optional type annotations are used for dynamic testing not static proofs. It's just that with type annotations Groovy dynamically tests are for "dynamic type" tags attached to objects rather than its more normal mechanism of dynamically testing for the presence of certain methods. What little static typing Groovy does have is not optional.

Update: Some time after this article was written, a team announced Groovy++, an extension to Groovy that really does have optional static typing.

Footnotes

[1] In a certain formal sense the phrase "dynamic type system" is an oxymoron and "static type system" is redundant. However, the phrases are commonly used and there doesn't seem to be a commonly recognized concise phrase to describe what a "dynamic type system" does. Pedants will argue for "untyped" but that doesn't give me a concept on which to hang the different ways that say Groovy, Ruby, and Scheme automatically deal with runtime properties.

[2] A more general function called join already exist for all monads in Control.Monad module. It can be defined as "join m = m >>= id"

Java Has Type Inference and Refinement Types (But With Strange Restrictions)

When enthusiasts talk about Scala they frequently start with "it's a lot like Java but with all this other cool stuff like type inference and structural types and..." I guess it's okay to introduce Scala that way. I've done it myself. But it does give the impression that Scala has somehow heaped complexity onto the Java. Oddly enough, it hasn't, at least not in the areas of type inference and structural types. Java has both. Sorta. They're just not very useful.

In this short article I'm going to try to show that while type inference and structural types appear to be additions to Scala over and above Java, they can also be explained as the removal of peculiar restrictions from Java. The goal is not just to illustrate these two points, but to make a broad statement: Scala isn't a just bunch of features heaped on top of Java. To a significant degree it's a generalization of things already found in Java. The result is that many aspects of Scala are both simpler and more regular than Java.

Type Inference

Java folk get excited about Scala's type inference. Usually positively, but sometimes negatively. But here's the thing: every practical statically typed language has some type inference. Every one. Even Java has type inference. It's just very limited. Let me show you by starting with a simple class

class Foo {
  public Foo bar() { return this; }
  public String toString() { return "Foo!"; }
}

With that I can write

System.out.println(new Foo().bar().bar().bar());

It's silly code but it illustrates my point. Java doesn't need me to explicitly annotate the return type of each call to bar(). Java infers the type resulting from new Foo().bar() as being a Foo, which in turn can be sent a bar() message resulting in a Foo, etc. If I change things just a little the type system complains

System.out.println(new Foo().bar().bar().baz()); // bzzt error!

In Java I "only" have to annotate types when I want to assign to a variable or return from a method. Which, come to think of it, is an odd restriction. The compiler obviously knows the type, so why do I have to tell it yet again?

Foo f = new Foo().bar().bar().bar();

Thus, rather than saying Scala adds type inference we can equally well say that it removes a silly restriction from Java's type inference[1].

Structural Refinement Types

The fact that you don't have to annotate types when building expressions in Java is well known even if people don't usually call it type inference. What's not as well known is that Java has refinement types. So I'll have to explain, this time starting with Scala.

In Scala you can say method doSomething takes any object with a bar method, like so

def doSomething(x : {def bar : Unit}) = ...

That's called structural typing - the doSomething method puts a constraint on the structure of objects that may be passed to it. But actually, in Scala, that's just shorthand for the following refinement type

def doSomething(x : AnyRef {def bar : Unit}) = ...

That says that x must be a subtype of AnyRef and must have a bar method. The type of x is a "refinement" of AnyRef with an additional structural constraint. Scala's refinement types aren't limited to just refining AnyRef, but that's really not important to my point here. My point is that Java has refinement types, too.

If you're a Java programmer, you're probably scratching your head thinking I've lost my sanity. But I promise I haven't. I ask you, in Java what exactly is the type of this expression?

new Object() { 
  public void bar() {
     System.out.println("bar!"); 
  } 
}

If you said "Object!" think again. In Java it's actually something more sophisticated. Go paste this into your favorite Java IDE and run it. I'll wait

public class Test {
  public static void main(String[] args) {
    (new Object() { 
      public void bar() { 
        System.out.println("bar!"); 
     } 
    }).bar();
  }
}

Surprised? Remember my point about limited type inference above? Here, Java has clearly inferred that the result of the expression is an Object refined with a bar method[2]. And so it lets you send a bar() message to the object. Rename either the method or the call to "baz" and you get a type error. But if you want to do anything interesting with the (new Object {public void bar() {...}};) object, like assign it to a variable, return it from a method, or apply it as an argument to a method then Java has a problem. It has no way to denote the refinement. So the refinement gets "lost" from the static type system. Poof. Gone. It's part of the object, you can find it via reflection, but the static type system won't let you get at it. The static type system only lets you get at a refinement "immediately" in a surrounding expression. Which is pretty close to useless. When you look at it that way, Scala hasn't so much added refinement types as removed another silly Java restriction.

Conclusion

When Java people first start looking into Scala it's common to think of Scala as being some complicated mishmash. In large part, evangelists (including me) are to blame. It's surprisingly hard to convey a nice feature of language A to users of language B without making it sound like something totally new, hence something that will complicate their lives. Hopefully this article has helped illustrate that in a very real sense some of the things that appear to be "new" in Scala are really "old" but generalized to be made more useful.

So this article is a call to all Scala pundits out there: when comparing Scala to another language, especially Java, go ahead and get excited about a "new" feature...but then see if you can't explain it as a generalization of an "old" one. You might be surprised how often you can and your audience might come away less intimidated.

Foot Notes

1. Technically, Scala's type inference is quite a bit more sophisticated than Java's. But I won't let inconvenient facts like that get in the way of making a good point.
2. Technically, I think the Java spec says that the type isn't structural, but some anonymous nominative type that the compiler can infer and use over a very limited scope. Then again, maybe not. I'm too lazy to go re-read the spec. Also, as already established, I won't let inconvenient facts like that get in the way of making a good point.

Is Scala for Academics and Egomaniacs?

This one isn't going to be a meaty technical article nor a deep philosophical exploration. Instead it's about perception vs reality. What moves me to post is the following 3 twits from Tim Dysinger.

• The guys in #scala on irc are academics...
• Just got kicked from #scala for arguing.
• scala sucks at gaining any momentum with that kind of academic egomaniac cliques

Edit: A few more

• R.I.P. Scala You were barely a twinkle in somebody's eye and now your dead.
• code to prove to #scala that they have a tard for a channel op
• Erlang, Ruby and Java = no scala hassles

Edit 2: One more, a blog post this time

• Scala is a Ghetto

I happened to be involved in the discussion that led to his conclusions. Here's the complete, unedited log from the #scala IRC channel. I leave it to posterity to decide if there was too much academia or egomania or if the guy was kicked for arguing.

Warning:Foul Language

(09:34:37 AM) doub: how can I print the address of an object rather than the output of its toString ?
(09:35:27 AM) dysinger: ah not c++
(09:35:32 AM) dysinger: it's java
(09:36:02 AM) dysinger: the default toString implies there is an address available
(09:36:04 AM) paulp: what is this "address" you speak of
(09:36:21 AM) paulp: you're harshing my abstraction mellow
(09:36:32 AM) doub: anything that could let me distinguish two distinct objects that have the same contenty
(09:36:34 AM) doub: *content
(09:36:43 AM) JamesIry: .equals
(09:36:45 AM) paulp: hashCode?
(09:36:49 AM) JamesIry: oops, .eq I mean
(09:36:49 AM) dysinger: Not even via JNI. JNI doesn't hand out objects' addresses, only "handles" that
(09:36:49 AM) dysinger: can be used to refer to them.
(09:37:05 AM) dysinger: hashCode is what you want.
(09:37:30 AM) doub: i have one object now, and one object later, and i want to know if that's the same or not, and i'd rather not store a reference to the first until i get the second
(09:37:37 AM) JamesIry: It's not what he wants. It's overridable and not guaranteed unique
(09:37:51 AM) dysinger: you should over-ride equals and hashCode if you want to compare content
(09:37:55 AM) DRMacIver: System.identityHashCode will give you the system version though
(09:37:58 AM) ijuma: hashCode is not necessarily good enough because it's an int and you may be running a 64-bit machine
(09:38:23 AM) ijuma: I mean System.identityHashCode above
(09:38:25 AM) dysinger: ^ the default impl you mean
(09:38:54 AM) DRMacIver: Sure. It's not foolproof.
(09:39:13 AM) JamesIry: System.identityHashCode isn't guaranteed unique either.
(09:39:26 AM) JamesIry: Only guaranteed to always be the same for the same object
(09:39:44 AM) doub: the System in java.lang ?
(09:39:47 AM) dysinger: doub if you over-ride hashCode and equals like it says in the core javadocs, you'll have all the control you need to compare two objects of the same class.
(09:39:48 AM) DRMacIver: Why don't you want to store a reference to the first?
(09:40:36 AM) JamesIry: doub, yes, System in Java.lang
(09:42:49 AM) doub: DRMacIver: i can't clearly state my reasons, so i guess they're bad ones
(09:43:05 AM) JamesIry: doub, the only thing guaranteed to work is .eq
(09:43:47 AM) dysinger: doub if you don't want to keep a reference to a previously seen object, take a hash of the object and keep that.
(09:44:21 AM) doub: with identityHashCode ?
(09:44:38 AM) dysinger: I would just use a library because I am lazy like that
(09:44:39 AM) dysinger: http://commons.apache.org/lang/api/org/apache/commons/lang/builder/HashCodeBuilder.html
(09:44:41 AM) lambdabot: Title: HashCodeBuilder (Lang 2.3 API), http://tinyurl.com/5639k7
09:45
(09:45:08 AM) dysinger: http://commons.apache.org/lang/api/org/apache/commons/lang/builder/EqualsBuilder.html
(09:45:10 AM) lambdabot: Title: EqualsBuilder (Lang 2.3 API), http://tinyurl.com/5n3wyz
(09:45:18 AM) doub: isn't there something low level in the jvm itself that can give me a unique string for an object ?
(09:45:36 AM) dysinger: hashCode is ok
(09:45:43 AM) JamesIry: Everybody please stop suggesting hash codes, identityHashCode or not. There is no guarantee that objects with unique identity will have unique hash codes.
(09:46:15 AM) dysinger: ah lol
(09:46:25 AM) dysinger: there is if I have the keyboard.
(09:46:50 AM) JamesIry: Read the spec for identityHashCode
(09:47:18 AM) JamesIry: It says not one word about uniqueness guarantees. A perfectly legal JVM could return 0 everytime the method is called.
(09:47:48 AM) dysinger: jameslry read the docs on equals and hashCode -> one of the fundementals of java.
(09:48:08 AM) dysinger: you don't just "use" them - you over-ride them.
(09:48:13 AM) DRMacIver: It's appropriate that "one of the fundamentals of java" is fundamentally broken. :)
(09:48:15 AM) JamesIry: equals -> same hash code, not the other way around
(09:48:47 AM) JamesIry: You can write your own hashCode to always return 0 and it will obey that contract
(09:48:55 AM) JamesIry: It would be stupid, but it would be "legal"
(09:49:17 AM) dysinger: lol what are you smoking ?
(09:49:42 AM) dysinger: omg - same shit different day - it's a formula - #1 hang out, #2 bash java/ruby/perl/etc, #3 don't actually know any java.
(09:49:51 AM) DRMacIver: It's a really powerful drug called "Knowing what you're talking about". :)
(09:50:01 AM) ijuma: dysinger: you are not paying attention to the discussion
(09:50:02 AM) JamesIry: Here's a proof. There are 2^32 unique ints. How many unique strings are there? Infinitely many. Ergo, there must be a possibility of collision.
(09:51:24 AM) ijuma: JamesIry: btw, there's a blurb in Object.hashCode about returning distinct integers for distinct objects where reasonably practical. of course, there's no guarantee, but in some cases it may be good enough.
(09:51:35 AM) ijuma: (the native Object.hashCode implementation that is)
(09:51:46 AM) JamesIry: ijuma: I agree, if you control the JVM it may very well be enough to use identityHashCode
(09:52:00 AM) JamesIry: But just using .eq is far more robust and guaranteed to work in the future.
(09:52:00 AM) dysinger: There is theoretically a possibility of a collision in the RFC for UUID too. It doesn't paralyze anybody except academics that don't actually code but stand around and debate edge cases.
(09:52:16 AM) JamesIry: dysinger, please read the original requirement
(09:52:24 AM) dysinger: please pontificate
(09:52:25 AM) ijuma: JamesIry: yeap, agreed
(09:52:40 AM) dysinger: I did read the original
(09:52:51 AM) JamesIry: doub wanted to know when he got the same (as in identity) object twice
(09:53:00 AM) dysinger: yep
(09:53:12 AM) dysinger: which can be handled perfectly by over-riding equals and hashCode
(09:53:18 AM) JamesIry: No!
(09:53:21 AM) ijuma: lol
(09:53:28 AM) JamesIry: Same identity, not content
(09:53:42 AM) ijuma: communication is hard sometimes
(09:53:54 AM) DRMacIver: It's not like this is a weird theoretical possibility which never crops up.
(09:53:54 AM) dysinger: over-riding those gives you any amount of comparison you want.
(09:54:01 AM) DRMacIver: scala> "\0".hashCode == "".hashCode
(09:54:01 AM) DRMacIver: res1: Boolean = true
(09:54:31 AM) dysinger: he didn't say I have random objects of different classes coming through
(09:54:52 AM) DRMacIver: Strings are not a particularly random choice. :)
(09:54:57 AM) ppohja: DRMacIver: you evil academic, standing around and finding just the corner cases :)
(09:55:05 AM) JamesIry: dysinger, why would you want to override equals to do a job when there's already a perfectly good .eq (or Java ==) method/operator that does the job?
(09:55:15 AM) JamesIry: Seriously, why?
(09:55:49 AM) JamesIry: Override equals when you want a non-identity based comparison. Override hashCode to be consistent. But when you want identity, there are tools built in to Java
(09:55:50 AM) DRMacIver: ppohja: It's amazing how often I genuinely get accused of being an academic in programming related discussions. I find it really funny. :)
(09:55:52 AM) JamesIry: or Scala
(09:55:54 AM) dysinger: because the default equals does not compare conntent.
(09:55:55 AM) dysinger: content
(09:55:59 AM) dysinger: it compares hashCodes
(09:56:12 AM) JamesIry: dysinger, no it compares identity, which is what doub was talking about
(09:56:22 AM) doub: given my system it would take some time to implement a storing mechanism for reference to past objects and comparisons with the new ones
(09:57:03 AM) doub: just printing the hash gave me a very loose but still usefull information about my object, and took less time than the conversation about my question :-)
(09:57:08 AM) dysinger: jameslry the default java equals compares the class and the hash code giving you identity
(09:57:08 AM) JamesIry: doub, stick 'em in an IdentityHashMap
(09:57:24 AM) doub: but I agree with all you said JamesIry, and I would use .eq for a production system
(09:57:36 AM) JamesIry: dysinger, no the contract just says identity. hashCode is not part of the contract.
(09:58:08 AM) DRMacIver: That would be a pretty stupid implementation when you can just compare the addresses of the objects...
(09:58:10 AM) JamesIry: The fact that a particular jvm uses an object's unique handle as a hashCode is an implementation detail
(09:58:37 AM) JamesIry: DRMacIver: except that internally a JVM can use 64 bit addresses
(09:58:51 AM) DRMacIver: Hm. Why is that a problem?
(09:59:09 AM) JamesIry: DRMacIver: sorry, I misunderstood you
(09:59:42 AM) JamesIry: DRMacIver: you're right, a JVM should compare addresses (or handles or something). It MAY base identityHashCode on that address or handle or whatever, and most probably do.
10:00
(10:00:00 AM) DRMacIver: I think hotspot uses the address in the lock table for hashCode
(10:00:19 AM) DRMacIver: Wouldn't swear to it though
(10:00:36 AM) dysinger: jameslry - if you have been on java very long you would know that the defaul equals uses class and hash code.
(10:00:39 AM) DRMacIver: (It definitely doesn't use the object's address, as that will change on a fairly regular basis)
(10:00:55 AM) dysinger: and that anytime you over-ride one of those methods - you over-ride both.
(10:00:59 AM) doub: would that be too restricting to require the jvm to expose a unique id per object (independent from the hash mechanism) ? like the address of some underlying memory structure
(10:01:11 AM) doub: is the JVM GC allowed to move objects in memory ?
(10:01:16 AM) dysinger: and that unless the universe explodes tomorrow - you will probably do just fine.
(10:01:33 AM) dysinger: doub - the vm moves shit all the time as needed.
(10:01:42 AM) DRMacIver: doub: Very much so.
(10:03:49 AM) DRMacIver: To the second part. The first part, probably not. But you'd have to account for the fact that collisions can still occur due to address reuse between GC cycles.
(10:04:19 AM) JamesIry: dysinger please point me to the line in the JLS that says that "==" uses class and hashCode. There's no need for us to argue. Just point it out to me.
(10:04:33 AM) dysinger: I said equals
(10:04:36 AM) dysinger: I never typed ==
(10:04:41 AM) JamesIry: The default equals is based on ==
(10:04:44 AM) dysinger: lol
(10:04:54 AM) DRMacIver: So the only guarantee you could get would be that if x and y are both live then address(x) == address(y) implies x == y. If you saw x and y at a different point in time you wouldn't be able to guarantee that same address meant x == y
(10:05:05 AM) dysinger: this is what I am talking about
(10:05:14 AM) dysinger: academic arguing
(10:05:24 AM) ijuma: interesting, it seems like once you call identityHashCode, it's computed once and then stored in the mark word
(10:05:37 AM) JamesIry: From the doc: The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value
(10:05:42 AM) ppohja: dysinger, no, it's that you're offering the wrong solution to the original problem.
(10:05:43 AM) dysinger: java has been around a dozen years with no one running away screaming from having been burned from hashCode and equals.
(10:05:45 AM) ijuma: for HotSpot, that is
(10:06:07 AM) ijuma: derived from the following statement, "Finally, there's not currently space in the mark word to support both an identity hashCode() value as well as the thread ID needed for the biased locking encoding. Given that, you can avoid biased locking on a per-object basis by calling System.identityHashCode(o)."
(10:06:31 AM) dysinger: ppohja - what's the "right" sollution in scala ? seems like we have been discussing this for 30 minutes.
(10:06:45 AM) dysinger: I know java like the back my hand.
(10:06:48 AM) JamesIry: ppohja: .eq is semantically the same as Java's "=="
(10:06:55 AM) JamesIry: I mean dysinger
(10:07:04 AM) dysinger: in scala - ok
(10:07:16 AM) JamesIry: Scala's "a eq b" translates to Java's "a == b"
(10:08:44 AM) JamesIry: Also from the doc: As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)
(10:09:10 AM) JamesIry: Note the caveat: this implementation technique is not required by the JavaTM programming language.
(10:09:30 AM) DRMacIver: So, just for the record, I looked up the source code for Object.equals
(10:09:49 AM) DRMacIver: public boolean equals(Object obj) {
(10:09:49 AM) DRMacIver: return (this == obj);
(10:10:11 AM) JamesIry: dysinger, have you looked at the back of your hand recently?
(10:10:12 AM) DRMacIver: dysinger: Or, in other words, you're full of shit. Kindly shut up about this now.
(10:11:49 AM) ijuma: JamesIry: Looks like he pays more attention to the front of his hand ;)
(10:11:54 AM) dysinger: fuck you guys
(10:12:12 AM) doub: do I get bad karma points for being the initiator of a conflict ?
(10:12:13 AM) dysinger: read the javadoc
(10:12:20 AM) JamesIry: I quoted the javadoc
(10:12:28 AM) dysinger: so did I
(10:12:33 AM) DRMacIver: dysinger: Sorry, but no thanks. I find idiocy a huge turnoff.
(10:12:45 AM) dysinger: nobody is trying to turn you on
(10:12:54 AM) ijuma: doub: no :)
(10:13:11 AM) dysinger: fuck you drmaciver - you and I have debated endlessly on other topics.
(10:13:24 AM) JamesIry: dysinger says: the default object.equals is based on class and hashCode. DRMacIver shows that it's based on ==. Dysinger gets mad
(10:13:34 AM) DRMacIver: Really? I dont' remember any instances.
(10:13:43 AM) dysinger: show me the code
(10:13:46 AM) DRMacIver: You probably blended into the endless sea of unwashed idiocy on the internet
(10:13:49 AM) JamesIry: DRMacIver: showed you the code
(10:14:04 AM) ppohja: DRMacIver: To me, this seems like you're talking to a eliza.
(10:14:12 AM) DRMacIver: ppohja: It does rather, doesn't it?
(10:14:17 AM) JamesIry: A troll
(10:14:26 AM) dysinger: "If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. "
(10:14:27 AM) DRMacIver: I'm about ready to break out the banstick to be honest
(10:14:37 AM) dysinger: eat a dick egomanics
(10:14:38 AM) JamesIry: dysinger, I already says equals implies same hashcode.
(10:14:46 AM) JamesIry: Look back through there. I said that.
(10:14:47 AM) mode (+o DRMacIver ) by ChanServ
(10:14:54 AM) dysinger: there is no implies
(10:14:55 AM) ppohja: dysinger, after all these years with java, you're forgotten the difference between -> and <-> ?
(10:14:58 AM) mode (+b *!*n=tim@*.hsd1.or.comcast.net ) by DRMacIver
(10:14:58 AM) dysinger left the room (Kicked by DRMacIver (I've already told you you're not my type.)).