A Critique of Impure Reason

Much has been made of the difference between “object-oriented” and “functional” programming. As much as I’ve seen people talk about this difference, or some kind of imperative/functional dichotomy, I don’t think it’s a meaningful distinction. I find that the question of OO vs FP, or imperative vs functional, is not interesting or relevant. The relevant question is one of purity, or the distinction between pure and impure programming. That is, respectively, the kind of programming that eschews data mutation and side-effects as against the kind that embraces them.

Looking at pure (referentially transparent, purely functional) programming from a perspective of having accepted the premise of impurity, it’s easy to be intimidated, and to see it as something foreign. Dijkstra once said that some programmers are “mentally mutilated beyond hope of regeneration”. I think that on one account, he was right, and that he was talking about this mental barrier of making the leap, from thinking about programming in terms of data mutation and effects, to the “pure” perspective. But I believe he was wrong on the other account. There is hope.

Contrary to what the last post indicated, this will not be a post about problems in “object-oriented” programming in particular, but about problems in impure programming in general. I will illustrate the issue of data mutation by way of two difficulties with it:

1. It blurs the distinction between values and variables, such that a term can be both a value and a variable.
2. It introduces an artificial distinction between equality and identity.

I will talk briefly about what the implications of each are, and what the alternative view is. But first I will discuss what I think motivates the impure perspective: an aversion to abstraction.

The Primacy of the Machine

In the early days of programming, there were no computers. The first programs were written, and executed, on paper. It wasn’t until later that machines were first built that could execute programs automatically.

During the ascent of computers, an industry of professional computer programmers emerged. Perhaps because early computers were awkward and difficult to use, the focus of these professionals became less thinking about programs and more manipulating the machine.

Indeed, if you read the Wikipedia entry on “Computer Program”, it tells you that computer programs are “instructions for a computer”, and that “a computer requires programs to function”. This is a curious position, since it’s completely backwards. It implies that programming is done in order to make computers do things, as a primary. I’ll warrant that the article was probably written by a professional programmer.

But why does a computer need to function? Why does a computer even exist? The reality is that computers exist solely for the purpose of executing programs. The machine is not a metaphysical primary. Reality has primacy, a program is a description, an abstraction, a proof of some hypothesis about an aspect of reality, and the computer exists to deduce the implications of that fact for the pursuit of human values.

Shaping Programs in the Machine’s Image

There’s a certain kind of programming that lends itself well to manipulating a computer at a low level. You must think in terms of copying data between registers and memory, and executing instructions based on the machine’s current state. In this kind of activity, the programmer serves as the interpreter between the abstract algorithm and the physical machine. But this in itself is a mechanical task. We can instead write a program, once and for all, that performs the interpretation for us, and direct that program using a general-purpose programming language.

But what kind of structure will that language have? Ideally, we would be able to express programs in a natural and concise notation without regard to the machine. Such was the motivation behind LISP. It was designed as an implementation of the lambda calculus, a minimal formal system for expressing algorithms.

This is not what has happened with languages like Java, C++, and some other of today’s most popular languages. The abstractions in those languages largely simulate the machine. You have mutable records, or objects, into which you copy data and execute instructions based on their current state. The identity of objects is based on their location in the computer’s memory. You have constructs like “factories”, “builders”, “generators”… machines.

What we have is a generation of programmers accustomed to writing programs as if they were constructing a machine. We hear about “engineering” and “architecture” when talking about software. Indeed, as users, we interact with software using pictures of buttons, knobs, and switches. More machinery.

Equality and Identity

Programmers are generally used to thinking of equality and identity as distinct. For example, in Java, (x == y) means that the variable x holds a pointer to the same memory address as the variable y, i.e. that the variable x is identical with y. However, by convention, x.equals(y) means that the object at the memory address pointed to by x is equivalent in some sense to the object at the memory address pointed to by y, but x and y are not necessarily identical.

Note that the difference between the two can only be explained in terms of the underlying machine. We have to invoke the notion of memory addresses to understand what’s going on, or else resort to an appeal to intuition with terms like “same object”, “same instance”, etc.

In a pure program, side-effects are disallowed. So a function is not allowed to mutate arguments or make calls to functions that have side-effects. So the result of every function is purely determined by the value of its arguments, and a function does nothing except compute a result. Think about the implications of that for a moment. Given that constraint, is there any reason to maintain a distinction between equality and identity? Consider this example:

String x = new String("");
String y = new String("");

If the values referenced by x and y are forever immutable, what could it possibly mean for them to not be identical? In what meaningful sense are they not the “same object”?

Note that there’s a philosophical connection here. The notion that every object carries an extradimensional identity that is orthogonal to its attributes is a very Platonic idea. The idea that an object has, in addition to its measurable attributes, a distinguished, eternal, noumenal identity. Contrast this with the Aristotelian view, in which an object’s identity is precisely the sum of its attributes.

Variables and Pseudovariables

So we find that, given the mutability premise, a term in the language may be not be equal to itself even as it remains identical with itself. In a sense, this is because it’s not entirely clear whether we are comparing values or variables when we compare a term. If that sounds a bit strange, consider the following snippet:

public class Foo {
  public int v;
  public Foo(int i) {
    v = i;
  }
}
...
public Foo f(Foo x) {
  x.v = x.v + 1;
  return x;
}
...
Foo x = new Foo(0);
boolean a = f(x) == f(x); // true
boolean b = f(x).v > f(x).v; // ???

Even that short and ostensibly simple code snippet is difficult to comprehend properly, because the f method mutates its argument. It seems that since the first boolean is true, the same object appears on either side of the == operator, so f(x) is identical with f(x). They’re the “same object”. Even so, it is not clear that this “same object” is equal to itself. To figure out the value of b, you have to know some things about how the machine executes the program, not just what the program actually says. You can argue about pass-by-reference and pass-by-value, but these are terms that describe the machine, not the program.

You will note that the Foo type above is mutable in the sense that it has accessible components that can be assigned new values. But what does that mean? Is an object of type Foo a value or a variable? It seems to have a kind of pseudo-variable v. To clarify this, we can imagine that a variable holding a value of type Foo also holds a further value of type int. Assignment to a variable x of type Foo also assigns the variable x.v of type int, but the variable x.v can be assigned independently of x.

So data mutation is, ultimately, variable assignment. Above, Foo is mutated by assigning a value to the pseudo-variable v.

Now, I say pseudo-variable, because it’s not obvious whether this is a value or a variable. A function that receives a value of type Foo, also receives the variable Foo.v, to which it can assign new values. So the variable is passed as if it were a value. Stated in terms of the machine, a pointer to a pointer is being passed, and the memory at that address can be mutated by writing another pointer to it. In terms of the program, the called function is able to bind a value to a variable in the calling scope.

This is why you have bugs, why programs are hard to debug, and software is difficult to extend. It’s because programs are difficult to comprehend to the extent that they are impure. And the reason for that is that they are not sufficiently abstract. A writer of impure code is not operating on the level of abstraction of programming. He’s operating at the level of abstraction of the machine.

Thinking Pure Thoughts

In a pure program, there are no side-effects at all. Every function is just that, a function from its arguments to its result. Values are immutable and eternal. A is A, and will always remain A. The only way to get from A to B is for there to be a function that takes A and returns B.

To a lot of programmers used to thinking in terms of mutable state, this perspective is completely baffling. And yet, most of them use immutable values all the time, without finding them particularly profound. For example:

int x = 1;
int y = x;
x = x + 1;

In that example, 1 is an immutable value. The + operator doesn’t modify the value of 1, nor of x, nor of y. It doesn’t take the value 1 and turn it into a 2. Every integer is equal to and identical with itself, always and forever.

But what’s special about integers? When adding a value to a list, a Java programmer will ordinarily do something like this:

list.add(one);

This modifies the list in place, so that any variable referencing it will change values. But why shouldn’t lists be as immutable as integers? I’m sure some readers just mumbled something about primitives and passing by reference versus passing by value. But why the distinction? If everything were immutable, you would never know if it were passed by value or reference under the covers. Nor would you care what’s primitive and what isn’t. For an immutable list, for example, the add function would not be able to modify the list in place, and so would return a new one:

list = list.add(one);

From this perspective, you can write programs that perform arithmetic with complex values as if they were primitive. But why stop with lists? When functions are pure, we can understand programs themselves as objects that are subject to calculation just like numbers in arithmetic, using simple and composable operators.

Assignment in a Pure World

Let’s take a simple example of just such an operator. We’ve talked about how mutation is really assignment. Now let’s take the leap fully into the pure perspective, in which assignment is really just closure (pure functions with free variables). To illustrate, here is an example that all Java and C programmers are familiar with. Let’s state the previous example again:

int x = 1;
int y = x;
x = x + 1;

The familiar semicolon represents a combinator called bind. In Haskell, this operator is denoted (>>=). In Scala, it’s called flatMap. To better see how this works, here’s a rough transliteration into Haskell:

\t -> (return 1) >>= \x -> (return x) >>= \y -> (return (x + 1)) >>= \x -> t x

Of course, this isn’t at all the kind of code you would normally write, but it serves to demonstrate the idea that assignment can be understood as binding to the free variable of a closure. Haskell is a purely functional language, and purity is enforced by its type system. If you haven’t taken it for a spin, I challenge you to do so. For more on the benefits of purely functional programming, see “Why Haskell Matters”.

Of course, purity is not purely the prerogative of Haskell. Sure, Haskell enforces purity, but you can write pure code in any language. That Java code above is pure, you know. If this is all new to you, I challenge you to give purity a shot. In your favourite language, be it Java or something else, start using immutable datastructure in preference to mutable ones. Try thinking in terms of functions from arguments to results rather than in terms of mutation and effects. For Java, you might consider using the immutable datastructures provided by Functional Java or Google Collections. Scala also has immutable datastructures as part of its standard libraries.

It’s time that we graduate from punching buttons and pulling levers — manipulating the machines. Here’s to programming as it could be and ought to be.

Higher-Order Java Parallelism, Part 1: Parallel Strategies and the Callable Monad

Now that even budget desktop and laptop computers are shipping with multi-core processors, it’s more important than ever to design programs so that they can take advantage of parallel processing. If you’re already writing software in Erlang or Parallel Haskell, then lucky you. But if you’re writing in Java (and are unable or unwilling to take up Scala), you will need to get organized.

Since Java 5, the JDK comes with a concurrency library that makes concurrent programming a lot easier than it used to be, and the library has been improved further in Java 6. This provides some basic abstractions that take care of the nitty-gritty of thread management for us. In this short series of articles, I’m going to show how we can build on top of that library to achieve concurrent programming of a higher order. We will employ some design patterns and simple abstract building blocks from functional programming. This style of writing concurrent programs will afford us the ability to:

• Compose ordinary functions into concurrent programs.
• Decouple parallel behavior from the algorithm itself.
• Turn existing code into parallel code, without refactoring, at runtime.
• Work with hypothetical results of concurrent computations, before they finish.

We will not use any locking or explicit synchronization. Basic familiarity with the java.util.concurrent package is assumed but not required. Familiarity with generics is highly recommended, and I recommend reading parts 1 and 2 of my Lazy Error Handling series as it explains some preliminaries. Most of the source code herein is already part of the Functional Java library, and I’ll use a fair bit of interfaces and classes from it, which I’ll introduce as we go along.

When we’re through, I will have demonstrated that a functional style of programming promotes code-reuse and modularity of parallel programs, above and beyond what can be achieved with the canonical object-orientated style.

The Callable Monad

The Callable interface is new in Java 5. It’s similar to the old Runnable interface that we all know and love, except that its call() method returns a result, and it may throw an Exception. If you followed my Lazy Error Handling articles, you will immediately notice that Callable is nearly identical to the Thrower interface described in that series, and you’ll know that it is indeed a potential monad. Treating Callable as a monad will allow us to work with it at a higher level of abstraction, letting us compose Callables, chain them, and project computations into them.

As you may already know, we need three ingredients (and only these three) to have a monad:

1. Type construction. This comes free with the Callable interface, since it takes a type parameter (i.e. it’s generic).
2. A unit function. This allows us to turn any value into a Callable that returns that value again.
3. A binding function. This allows us to chain together Callables with functions, without actually calling them.

Here is the unit function for Callable (we will refer to it as unit in the text to avoid ambiguity):

  public static <A> Callable<A> callable(final A a) {
    return new Callable<A>() {
      public A call() {
        return a;
      }
    };
  }

And here is its binding function:

  public static <A, B> Callable<B> bind(final Callable<A> a, final F<A, Callable<B>> f) {
    return new Callable<B>() {
      public B call() throws Exception {
        return f.f(a.call()).call();
      }
    };
  }

Note: The F interface is from Functional Java. It represents a first-class function (a function that can be treated like any other value). F<A, B> has one method that takes an argument of type A and returns a value of type B.

Given the above two methods, Callable is now a monad. All monads are also functors, so we can define a Callable functor. What I mean by “functor” is that we can define a method to turn any existing function into a function on Callables, or, in other words, to apply any function to a value wrapped in a Callable, without actually calling it (i.e. lazily). This method is called fmap, and we can define it in terms of bind:

  public static <A, B> F<Callable<A>, Callable<B>> fmap(final F<A, B> f) {
    return new F<Callable<A>, Callable<B>>() {
      public Callable<B> f(final Callable<A> a) {
        return bind(a, new F<A, Callable<B>>() {
          public Callable<B> f(final A ab) {
            return new Callable<B>() {
              public B call() {
                return f.f(ab);
              }
            };
          }
        });
      }
    };
  }

Useful operations on Callables, that the methods above allow us to implement, include sequence—which is a method of turning a list of Callables into a single Callable that returns a list—and join, which peels one layer of Callables from a Callable<Callable<A>> so that it becomes just Callable<A>. You will find the source code for those as part of Functional Java.

Parallel Strategies

When working with the java.util.concurrent library, you normally don’t work with Threads directly. You might instead implement Callable<A> and submit instances of your implementation to an ExecutorService, which yields values of type Future<A> which represents a running computation that yields an A. Future has a method called get() that returns the result as soon as it’s ready. This is a great improvement over managing threads and Runnables ourselves, but it still ties our hands somewhat to the ExecutorService, and encourages tight coupling of our code to the parallelisation library.

Inspired by Haskell’s “Parallel Strategies”, let’s instead work with parallelisation in the abstract. For what is ExecutorService, really? It’s a method of turning Callables into Futures. That means it’s a kind of function, so we can abstract from it, using a function type: F<Callable<A>, Future<A>>. Such a function can then be backed by an ExecutorService, or by something else entirely, such as a load-balancing facility that serializes Callables to be executed on remote servers.

We will use a new class, Strategy<A>, that allows us to effectively separate parallelism from the algorithm itself:

  public final class Strategy<A> {

    private F<Callable<A>, Future<A>> f;

    private Strategy(final F<Callable<A>, Future<A>> f) {
      this.f = f;
    }

    public F<Callable<A>, Future<A>> f() {
      return f;
    }

    public static <A> Strategy<A> strategy(final F<Callable<A>, Future<A>> f) {
      return new Strategy<A>(f);
    }

  }

We’ll add a couple of static functions to create simple strategies:

  public static <A> Strategy<A> simpleThreadStrategy() {
    return strategy(new F<Callable<A>, Future<A>>() {
      public Future<A> f(final Callable<A> p) {
        final FutureTask<A> t = new FutureTask<A>(p);
        new Thread(t).start();
        return t;
      }
    });
  }

  public static <A> Strategy<A> executorStrategy(final ExecutorService s) {
    return strategy(new F<Callable<A>, Future<A>>() {
      public Future<A> f(final Callable<A> p) {
        return s.submit(p);
      }
    });
  }

One of the neat things that working with Strategies as functions allows us to do is use the Callable monad to compose them with existing functions. Any function can be lifted into the Callable monad using fmap, and then composed with a Strategy to yield a concurrent function. Moreover, we can use Strategies to convert existing functions to concurrent functions. The following method on Strategy will take any function and return the equivalent function that executes concurrently. Calling such a function will give you a Future value from which you can get the computed result whenever it’s ready.

  public <B> F<B, Future<A>> lift(final F<B, A> f) {
    final Strategy<A> self = this;
    return new F<B, Future<A>>() {
      public Future<A> f(final B b) {
        return self.f().f(new Callable<A>() {
          public A call() {
            return f.f(b);
          }
        });
      }
    };
  }

Alert readers will note that lift represents the Kleisli arrow for the Future monad. As for most monads, this arrow is a very useful kind of thing (see Lazy Error Handling, Part 2). In the Future monad, the Kleisli arrow provides parallel function application. If you already have a function f, then calling lift(f).f(x) will apply that function to x while simultaneously continuing with the next statement in the current program.

Lazy Futures

For functions involving Futures, we generally always want to have the Future type in the codomain (on the right-hand side, in the return type). If you think about it, you’ll see that functions that take Futures in their arguments won’t be able to do much without blocking on Future.get(). However, that doesn’t mean we can’t compose Future-valued functions together. It just means that we can only compose two of them together in such a way that we either wait for the first Future to obtain a value before firing off the second one, or we have to spark a new thread that does nothing but wait on the first Future. We’re much better off composing Callables and then turning those into Futures as needed. In fact, we might want to wrap values of type Future<A> inside of a Callable<A> again so that we can manipulate their return values while they are running:

  public static <A> Callable<A> obtain(final Future<A> x) {
    return new Callable<A>() {
      public A call() throws Exception {
        return x.get();
      }
    };
  }

And this takes us full circle back into the Callable monad, where we can compose computations, bind them to functions and map functions over them, all lazily. Which means: without actually asking what their values are until we absolutely need to know.

So we have accomplished what we set out to do in this first part of the series. We’ve written a Callable monad that lets us compose existing code into concurrent programs. We’ve implemented parallel strategies to run those programs in parallel, without regard to the actual parallelisation implementation. We have a Kleisli arrow that lets us run ordinary functions concurrently with each other, and finally we have a way of taking concurrently running computations back into the Callable monad. Not bad for a day’s work.

In the next part of this series, we will employ what we’ve built here to develop some higher-order parallel functions, including a parallel list functor. I hope you join me.

Noumenal Null

Although most would not consider omniscience a reasonable requirement for a software system, it’s nevertheless a common complaint that computer systems are not omniscient. It’s not often worded quite that way, but we’re all familiar with the argument that a system (say, a database) must be able to represent a fact that it doesn’t contain, or rather, to represent missing values somehow.

That “somehow” normally takes the form of a special symbol, ω (omega), or “null”. This special symbol is assigned to variables that have not yet been initialized, that have no meaningful value in that context, or whose value is unknown, etc.

Now, let’s take a step back to reality. In reality (the world that’s actually out there), things either are or are not. Reality doesn’t care if we know about it or not, and there are no facts which aren’t facts about something in particular. And there are certainly no existents out there which are “not yet initialized”.

To be clear, the issue we are talking about pertains to variables in whatever language we’re using. A variable properly has some value, but may have any value (of the appropriate type). The notion of null is a variable which has no value at all. It’s my opinion that this amounts to a philosophical error known as reification of the zero.

Implications of Null

A software system models some abstraction from reality. To model the facts of reality (or a virtual reality), a very simple logical system suffices, since things either are or are not (law of the excluded middle). A simple enough system represents only facts about reality (or, rather, abstractions from such facts), and those things which aren’t facts about reality are simply omitted. This is not to say that it represents all facts of reality (that would be absurd), but only the ones about which we have something to say in the context of our system.

For a simple but contrived example, let’s make a kind of language that represents facts about people’s birthdays. We have a type of expression saying “The birthday of Person p is on Date d.” Call it a logical theorem that there exists some person p whose birthday is on some date d. To prove this theorem, one merely needs to supply some (but any) person who has some (but any) birthday. According to the Curry-Howard isomorphism, we could think of it as a function, a constructor of values of a specific type. Call the type and the constructor function BD, and let it take two arguments, p and d, which represent a person and a date, respectively, yielding values of the form BD(p,d).

Now comes the question of what to do when a fact is not yet known, not applicable, or can’t be found out (because of some error, for example). There are some options for representation here, of which, I will consider two. For example, in a system that tracks people’s birthdays, we could handle unknown birthdays in two ways:

1. State that the fact is unknown, using a new kind of expression: “Person p has an unknown birthday.” If this were a programming language, it would be something like a function UB which takes a value p and returns a value of the form UB(p). It’s like a logical formula with one variable p, such that any value for p provides a proof of the hypothesis that there exists some person whose birthday is unknown.
2. Create a special null value called ω, such that for an unknown birthday, we would simply say: “The birthday of person p is on date ω“, or: BD(p, ω), for some p. Or if the person, whose birthday it is, is unknown: BD(ω, d), for some d.

These are different approaches to the problem in a profound way. In the former, we have stayed within the framework of representing “that which is”, i.e. truths only, and used the semantics of the language to represent facts about the unknown (the fact that it is unknown). In the latter, we have imported the notion of the unknown, from the meta-level, into our algebra. As far as our algebra is concerned, ω is a kind of something that is nothing in particular and has no specific type. It has become a way of formalizing vagueness in our logic. We have in fact changed the logic of our language in such a way that the Curry-Howard isomorphism no longer holds, and the law of excluded middle is no longer applicable. Supplying null for either of the variables of BD(p,d) creates a value of the form BD(p,d) that is not a proof of the logical formula that BD(p,d) represents. Observe that “The birthday of person John is on date ω” does not constitute a proof of the hypothesis that there exists some person p whose birthday is on some date d.

In short, the difference between these two approaches is that the former treats the fact that something is unknown as just another fact, using grammar that already exists, while the latter is an attempt to formalize “unknown” as a new grammatical construct.

But once we invite null into the system, we have to come up with the semantics for how to handle it. We have to ask the question: “What exactly do we mean by null?” For every operator, we must decide what it means for one of its operands to be null. What does ω = ω yield? In some languages (most imperative programming languages), ω is considered equal to itself. In others, it’s considered an error to even ask the question, resulting in a runtime error or a non-terminating program. In yet others (SQL), such an operation always yields ω itself. This last kind is a kind of three-valued logic, which is fraught with difficulties. For example, in SQL, A=A is not true for all values of A. In other words, we have arrived at a logic in which the law of identity is not a tautology!

The implication of this last point is that a Boolean expression in such a system is to be considered valid even though it is neither true nor false. This means we can’t consider such a system to deal with propositions, since all valid propositions are either true or false (a proposition that is neither true nor false is arbitrary, i.e. invalid). From the standpoint of propositional logic, then, a database is corrupt to the extent that it contains nulls.

In fact, once we allow it, we may find that we need more than one kind of null, with differing semantics depending on what we mean by it in that context. One kind may mean “unknown”, another might mean “inapplicable”, and of course we might need a third to say that “we do not know if this is applicable or not”. When taken to its logical conclusion, this leads to an explosion of kinds of null. As a concrete example, consider a database that tracks people’s death dates. For the predicate Person p has a death Date of d, one might need at least three kinds of null: one to say that the person is not yet dead (inapplicable), another to say that the person is dead, but we don’t know when they died (unknown), and a third to say that we don’t know whether or not they have died (unknown whether or not a value is applicable). And this is just one really simple example.

But in practice, the meaning of null is often decided ad hoc by the user of the system or language, and may even not be decided at all, in which case the result of a program employing nulls has been consigned to chance to some degree.

Obviating Null

It should be abundantly clear that introducing null into a language is not much of a solution to anything. We don’t do that with natural language, and certainly not in formal logic, so why do it with programming languages? I believe it’s partially because people are used to thinking of a programming language as a machine rather than a logic. They are still thinking in terms of initializing pointers or registers and transitioning between memory states. But the power of languages is to abstract these things away, so that we can concentrate on the algebra while the machine does the arithmetic. Yet, I think we owe the acceptance of null largely to the fact that people are used to sloppy thinking. They’re used to treating nothing as if it were a thing, and using concepts of which they only know the approximate meaning.

Fortunately, there are real-world solutions for obviating the notion of null. Functional programming, for example, does away with it by employing monads. Haskell has the Maybe monad which is an abstraction from case analysis such that a value of type Maybe A can take one of two possible forms: Nothing or Just a where a is a value of type A. This might seem like it’s the same thing as null, but the fact that only certain operations are defined on the Maybe type class (i.e. it’s a monoid) keeps everything well defined. This concept is applicable to any language that supports functional style, and can even be implemented in Ruby. In some other languages, this monad is called Option.

In the realm of databases, work is being done on more abstract database languages than most of us are used to. Chris Date and Hugh Darwen have been instrumental in putting database systems on the sound theoretical footing of predicate logic, although products based on their research are largely in the early stages of development.