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"