Higher Order

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:

It blurs the distinction between values and variables, such that a term can be both a value and a variable.
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.

To say that a computer “requires programs to function” is not at all like saying that an automobile requires fuel. It’s like saying that it needs a driver. While that’s true, the driver doesn’t exist for the sake of the car. The driver has somewhere to go and the car exists to serve that purpose.

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 rebind a variable in the scope of the caller.

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;
int z = 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:

int x = 1;
int y = x;
x = y + 1;
t(x + y)

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:

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

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 the argument to a function. The Haskell code above roughly means:

Pass 1 to f, where f passes its argument to unchanged to g. And g adds 1 to its argument and passes the result to a function that adds y to its argument and passes that to t.

So in the Java version, we can understand everything after the first semicolon to be a function that takes an argument x and we happen to be passing it 1. Everything after the second semicolon is a function that takes an argument y and we happen to be passing it x (which has the value 1). And everything after the third semicolon is a function that takes an argument called x (shadowing the first x) and passes x + y to some function t.

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.

Coming from a background in Pascal and C, during the 1990s, like most others, I became infatuated with Object-Oriented programming. I thought they were really on to something. It seemed intuitive. I read and re-read the GoF book. I became fluent in UML. I read Chris Alexander. I wrote factories and metafactories, and more class hierarchies than I’ll ever count. I embraced Java eagerly, and XML moreso. But with experience came the realisation that I was solving the same problems over and over again. There was some governing principle that I was missing but knew I had to grasp if I were to progress in my chosen profession. I went back to the fundamentals. I learned about LISP, lamdba calculi, type theory, relational programming, category theory, and epistemology. And I’m still learning. But in integrating all of that into my existing knowledge, I discovered something that I found liberating:

There is no such thing as Object-Oriented programming.

I realise that I might risk starting a religious war here, but I don’t intend to. If you think I’m attacking you personally in some way, please stop reading and come back later with fresh eyes. Note that I’m not saying that OO is a bad thing. I’m saying that there isn’t any special kind of programming that is object-oriented as against programming that isn’t. It is a useless distinction, in exactly the same way that “race” is a useless distinction. And holding on to a useless concept isn’t good for anybody. The term “object-oriented” is at least honest in that it says what it implies, which is a frame of mind, an orientation of the programmer. However, the practical effect of this orientation is anti-conceptual, in that it displaces actual concepts like algebra, calculus, closure, function, identity, type, value, variable, etc. It fosters an aversion to abstraction. So you could say that there are object-orientated programmers.

“Object-Oriented” as a non-concept

Remember, you cannot be called upon to prove a negative. The burden of proof falls on whomever is claiming that there is such a thing as OO. But try as you might, there’s no objective definition of what “object-oriented” refers to. It means anything you want, which is to say that it’s rather meaningless. Peddlers of “object methodology” readily admit that “object-oriented” means different things to different people. To quote Aristotle: “Not to have one meaning is to have no meaning, and if words have no meaning, our reasoning with one another, and indeed with ourselves, has been annihilated.”

When I say that there’s no such thing as OO, I mean, more precisely, that there exists some abstraction (or several) that is referred to as “object-oriented”, but that this abstraction has no actual referent in reality. It is an abstraction that is made in error. It is not necessary, and serves no cognitive purpose. It is “not even false”.

This is to say that it’s not like the concept of Santa Claus, which is a fiction, a falsehood. OO is not a fiction, but a misintegration. It is a term that sounds like a concept, but denotes nothing more than a vague collection of disparate elements, any of which can be omitted, and none of which are essential.

A Proper Method of Concept-Formation

How is Object-Oriented a non-concept? Let’s demonstrate that very cursorily. First, we have to explicitly identify what it means for a concept to be valid.

Valid concepts are arrived at by induction. Induction is the process of integrating facts of reality by observing similarities and omitting particulars. Or, if you will, the process of applying logic to experience. Our induction must adhere to the corollary laws of identity, noncontradiction, and the excluded middle, and it must observe causality.

Note that a correct concept of concepts is the vehicle and not the cargo of this post. In brief, a valid concept or theory must meet the following criteria (hat tip: David Harriman):

It must be derived from observations by a valid method (by logical induction from experience or experiment as described above). A valid concept can have no arbitrary elements and no relations that are unsupported by the facts being integrated.
It must form an integrated whole in which every part supports every other. It cannot be a conglomeration of independent parts that are freely adjusted to fit a given situation.
It must be no more and no less general than required to meet criteria 1 and 2.

OO doesn’t meet criterion #1. There’s nothing about the nature of programming that gives rise to a concept of object-orientation. Rather, the notion is sparked by the desire to make an analogy between manipulating physical objects in the real world and manipulating abstract entities in the computer. The motivation is understandable, to help people think about programs in the same way that they are used to reasoning about physical objects. But the analogy isn’t warranted by the facts, and therefore it is arbitrary. The concepts simply don’t transfer, because they are abstractions over entities of a different kind. The mistake is to use the concepts anyway, choosing the illusion that software is like physical systems rather than understanding the actual nature of programs.

OO doesn’t meet criterion #2: There’s no consistent definition of object-orientation. It’s a loose grab-bag in which nothing is essential. Even if you start removing things, it’s not at all clear at what point your programming stops being object-oriented. One would think that it’s at the point where you stop programming with objects, but that’s merely begging the question since it’s not clear what kind of entity is an object and what kind of entity isn’t. We are to rely on intuition alone in discovering that. What’s more, some of the contents of the “object-oriented” bag contradict one another (both inheritance and mutation contradict encapsulation, for example).

Repairing the Disorientation

Of course, it does no good to tear down the cognitive package-deal that is “object-oriented” if you don’t replace it with something. If you entered a village of little blue creatures and convinced them that the term “smurf” had no cognitive utility, you would have to teach them a whole host of concepts to use in its stead. There are two main ideas that the anti-concept “object-oriented” annihilates:

It introduces the false dichotomy of identity as apart from equivalence.
It blurs the distinction between values and variables.

I will elaborate on each of these points in two follow-up posts. Stay tuned.