Thursday, July 23, 2009

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.

22 comments:

Daniel Spiewak said...

Quick note: I think you're forgetting about java.lang.Void. This is the "official" type of the non-existent value for "void". Of course, since it's a type with no members, it's really almost as bad as not existing in the first place. The one thing it's good for is situations like what you demonstrated (converting a void function into a value).

As for a return value for a function of type Void (notice the upper-case), you would have to use null. This is theoretically very ugly, but it does the job.

Just for the record, I still like Unit better. :-)

James Iry said...

Eek, I did forget Void. Hmmm, have to think about how to edit it in.

JH said...

But unit, as its name somewhat implies, has exactly one value

I think that in Haskell, at least, the type unit may have two values: () or bottom.

James Iry said...

@JH - in any Turing complete language unit has two values, () and bottom it's just that strict languages will diverge on bottom in cases where Haskell does not. However, explaining bottom as a value to reforming C/C++/C#/Java programmers is just a bit much when the thought of void as having a value is already pretty "out there."

My next article is about the bottom type. I haven't yet decided if I want to introduce it as a value.

Jeremy R. Fishman said...

Where does Python fit in, having first-class functions and the None type?

AlBlue said...

The type 'Void' is purely used by reflection to denote a return type of void. In fact, Void is a meta-type (it's the type of types) but in both cases, there is no value X such that X:void, or that you could pass in as an argument to a function. In other words, if f() is of type 'void', there is no way of constructing a function g(f()).

James Iry said...

@Jeremy,

None is used to mean something like null in the C derived languages. But as the footnote mentions, in dynamically typed languages such values can be punned and used in place of (). Still, Python doesn't really count. You can't write 'x = print "hello"' in Python. In an impure functional language you can and x would be ().

@AlBlue,

I presume you are talking about java.lang.Void. As Daniel Spiewak points out you can write

public Void foo() {
System.out.println("hello");
return null;
}

and

Void x = foo();

liyang.hu said...

“Void and unit are essentially the same concept.” — only insomuch as the Booleans False and True (respectively) are essentially the same concept, unless you wish to contradict Curry-Howard.

Here's a tuppence. Go buy yourself a real type system.

Daniel Spiewak said...

I'm not expert, but I'm almost positive that Curry-Howard doesn't deal with Void vs Unit. James is right on this issue.

I've always thought of void as being a unit type with no members. Even back when I was learning Java, it seemed more than a little odd.

Stephan.Schmidt said...

Excellent.

"reulst" ? :-)

Cheers
Stephan

Marius Gedminas said...

Would you please expand on your fifth note, saying that a Python tuple is really just a list? "A tuple is an ordered fixed size collection of values of (possibly) different types" seems to match Python's tuple semantics pretty much exactly. What am I missing?

James Iry said...

@liyang,

There's a terminological confusion here. Some type theorists sometimes use the word "void" to mean the bottom type. At the type level the bottom type is falsity as you point out where the unit value is more truthy. However, C style voids do not correspond with the bottom type. If they did, then you could write things like

String x = print("hello")

and

int x = print("goodbye")

That's because, by definition, the bottom type includes a type rule that for all types A Bottom :- A.

Or, to put it another way, if you transliterate a simple Java IO program into OCaml you'll replace voids with Units and the program will work the same way. You would not replace them with Scala's bottom type, Nothing.

@Marius Gedminas,

The isomorphism between python tuples and lists exists because of python's dynamically typed nature. For any operation defined for lists you can do the same operation for tuples (even if you have to convert back an forth in order to do it). In a statically typed language a tuple carries its length at the type level whereas the typical list does not. Now, with a sophisticated enough type system there are things called HLists which are isomoprhic to tuples, but it takes a lot of type fu to deal with them and neither Java or C# can do it. It seems likely that C++'s type system could but it gives me hives thinking about it.

helium said...

> if you transliterate a simple Java IO program into OCaml you'll replace voids with Units and the program will work the same way. You would not replace them with Scala's bottom type

When I transliterate into O'Caml I never use any of Scala's typs ;)

liyang.hu said...

@James, re: “There's a terminological confusion here.”

There is no confusion. I was simply fishing for a reaction. =)

Gavin Bong said...

In the google android sample code, java.lang.Void is used everywhere.

e.g.
AsyncTask<Void,Void,Void>

Gavin Bong said...

One more thing.

If you declare a method like so: void doFoo(), the implementation doesn't need to return anything.

But if the method sig is: Void doFoo();, you must return null.

Unknown said...

In the 4th footnote, you say C++0x won't have concepts. Do you have any references backing that? Because in the last working draft, concepts are present, and according to the documents on open-std.org it has been named as a feature in the registration document. If you meant other "concepts" than the constrained templates, consider this comment void :-)

I've got other comments on C++. You say it's a pity that C++'s void doesn't have values, but I think it doesn't need to have some values to be useful. What would be really useful, would be ability to create variables of type void etc. (ie. to have void as first class type), but you needn't spell any values - you just assign anything to it, it does nothing and that's it. However, this is probably not gonna happen, because allowing void in some contexts, eg. as base type of an array, would change the SFINAE rules and thus break existing code. There was a small change in the standard regarding what you describe, particularly, if you have an expression e which yields void, you can write "return e" in a function returning void.

If you care about code duplication, it's possible to create eg. a transform() function that would allow functions yielding void (I'd rather not think about its semantics, but lets abstract from that), create your own type with void semantics (like JamesIrysVoid) and create a type function that would translate real void to JamesIrysVoid and go with that (not that I think this particular case is useful, but it is sometimes used to overcome eg. limits of reference types in C++).

BTW there's other difference between foreach() and transform() in C++ (apart from transform() not accepting a function returning void): according to the standard, transform() function must not have any side effects (in C++03).

James Iry said...

@Jiri Palecek,

For more than you ever wanted to know about the death of concepts in C++0x, see http://lambda-the-ultimate.org/node/3518

Anonymous said...

Hey, James, could you provide us a feed with the complete contents of your posts (instead of just the first few words). I love your blog, but it's such a pain to switch between the reader and the browser. Pleeease! :)

Falcotron23 said...

The only reason you can't write 'x = print "hello"' in python is that print is a special statement defined by the language rather than a function, which is completely irrelevant here (and which is no longer true in 3.x). You can define a function 'def p(s): print s' and then write 'x = p("hello")' and it works just fine. You'll get None, the only value of type None, in x. Other than spelling, that's the same as getting () in Haskell.

Of course in a static language, f has type string->(), and x has type (), while in Python, neither variable has a type, only the runtime values (and even the value of f has only the type "value of any type -> value of unknown type"). But that's a completely separate issue from whether python has a unit type.

None is not like void, or like null; it really is like unit (even down to the fact that type(None)==None).

Anonymous said...

>>> type(None) == None
False

>>> type(None)
<type 'NoneType'>

Dobes Vandermeer said...

As far as java.lang.Void goes it is similar to "unit" in that it has only one member - "null", so it is suitable for that usage in Java.  It's also similar to the bottom type in that null is a member of all non-primitive types.  However, the similartiy stops there.  If it were truly the "top" type it would be the superclass of Object.  If it were truly the bottom type there would be NO values suitable for Void (or void).

Scala's "bottom" type Nothing means not only that the expression or function doesn't return anything - it literally doesn't return at all!  One use of it is to allow something like this to typecheck:

extern Nothing fail(char *msg);
int f(a,b) { return b==0? fail("div by zero") : a/b; }

The two branches of a ?: conditional must have a compatible type, and since Nothing is compatible with all types, this works.