Haskell, Clojure, and nondeterminism

September 10, 2012 at 8:24 pm
filed under Coding
Tagged , , ,

I can’t stop thinking about Haskell and Clojure, especially when it comes to the concept of safety. The concept of an option type, Maybe in particular, has been a huge influence on me.

Haskell and Maybe

One of the simplest monads to understand in Haskell is Maybe. It’s like a first-class option type, or a null object. For any type a (a list, an integer, etc), Maybe a can be Just a (a box containing a value of type a) or Nothing. Both Just a and Nothing are of type Maybe, so any function which returns Maybe a is telling you that it will return either.

Consequently, you know up front that you have to deal with both cases. Anywhere you want to use the result of finding an item in the list, for instance, you have to contend with the possibility that it was not found.

This is actually no different from any other language; they just return nil and it’s on you to deal with it. Crucially, there’s nothing in your average type system which semantically describes the concept of Nothing vs. Just something. nil or null is effectively a subtype of every possible type.

If it helps, think of it like old-school error handling in C: you return an int as an error code, where all possible outcomes (including success!) are encapsulated by that int. It worked but I think (hope) that people recognize that it is not a great idea to compress a wide variety of outcomes, each of which has different implications for decision-making, into a type which is used for such as counting things.

The difference with Haskell is that Maybe is one possible type to use for cases where you might have otherwise used nil. Its presence is an explicit warning sign. It is also richer, semantically, in that you’re not conflating success and various failure modes into one type. Maybe encapsulates nil and “something” in a single type, and this type itself can contain any other type. It’s a bit like how List<Foo> encapsulates Foos, theoretically containing any possible value of Foo, or (crucially) containing nothing at all!

You can bypass Maybe a, effectively converting it into a, with fromJust, but that introduces the possibility runtime failure in a case where you have Nothing. Of course you could explicitly check for Nothing. In that case you’re re-implementing a lot of the mechanisms put in place to deal with Maybe in the first place. In essence you are trapped inside a Maybe.

This is why >>=, et al, were invented. >>= is type Maybe a -> (a -> Maybe b) -> Maybe b. It handles Nothing for you as part of the check, before it even decides whether to run your function. The “down side” (which is by design) is that this is not a way to escape nondeterminism. Nothing is forever after a possibility.

When you use fromJust, even with an explicit check for Nothing, you’re doing what most languages do. You are returning -127, giving an arbitrary number privileged semantic meaning.

Now, the world hasn’t fallen to pieces because people aren’t using Haskell. But if you subscribe to the idea that at least one of the problems plaguing software is our ability to reason about it, Haskell offers one opinion: a type system can imbue parts of your program with richer semantic meaning, allowing you to describe your program in a more precise way and in a way that the compiler and type-checker can assist with.

The trade-off, of course, is that perhaps it makes nondeterminism — a critical part of practically any program which interacts with the real world — perhaps a bit too difficult to work with. As I pointed out above, the proliferation of Maybe throughout your program is not in itself a disease; it’s a symptom of how nondeterminism quickly pervades every aspect of your program. The difference is that in most programming languages this layer of complexity is implicit.

Clojure

Clojure takes a different tack, which is probably part of why it causes me a fair amount of cognitive dissonance. It says that, in reality, type systems are largely orthogonal to our ability to understand our programs. As Rich Hickey says, what’s true of every bug that you find in the wild? It passed the type checker and it passed your tests. Once you are faced with such a bug, all you have available to you is your program and your ability to reason about it. It is composition of orthogonal, simple components that makes software easier to understand.

I don’t think that the argument here is that types cannot help you, or that they are not in any way worth it. A type checking compiler can help catch basic mistakes, and it can make intent much clearer. It can make APIs clearer.

But, in the spirit of big-O notation, you could make a decent case that the type system will not be the dominant term; the size and complexity of your software, conversely, will dominate everything else. In other words, if complexity of increases by n^c and a type system reduces complexity by m^2, no matter how big m is, O(n^c - m^2) still reduces to O(n^c).

Also, I should say that orthogonality of components, in the context of Clojure, includes purity and referential transparency, implying immutability as well. In a pure function, time is orthogonal, whereas a method on an object with state will change its input depending on where you are in the lifetime of the object and therefore the program. So while Clojure does not bend over backwards to sequester state or side effects, immutability-by-default goes a rather long way towards purity.

With that in mind, I doubt that anyone sympathetic to this big picture view would be categorically against the use of a type system. Rather I think it probably comes down to a matter of preference. In the case of Haskell, the type system is an asset, and I imagine some people view the type system as a simplifying factor, as I described above; it makes complexity plain rather than implicit.

In the case of Lisp, I understand that people have been getting on by composing very simple components, like lists and functions. This reduces questions like “what kind of object does this return, again?” which I found myself running into in Python all the time.

I suspect there’s more to it than that (e.g. macros, fewer layers of tech), but that’s a topic for another time, I think.

%d bloggers like this: