May 28, 2009

Functional Programming is Not All or Nothing

I’ve noticed a flurry of discussion around the blogosphere lately about what is and is not a functional programming language and what is or is not stateful. After being interested in functional programming (FP) for many years, I’m glad that it is finally getting some mainstream attention. I think FP has some valuable lessons for all programmers, and that it provides a better default mindset for programming than traditional imperative programming.

However, a lot of the discussion seems to make the mistake of assuming that functional programming and statefulness are all-or-nothing properties, that either you have a total purity of statelessness or you have opened Pandora’s Box and let all the evils of state into your program or programming language. But the truth is that functional programming is best viewed as a style of programming with different default assumptions about state. And statefulness is best viewed as a continuum that varies along at least two dimensions — locality and monotonicity — both of which I will explain shortly.

What is state?

Before I do that, I had best describe in simple terms what state is. The easiest way to understand state is to imagine that I have given you a distinctive-looking box. If each time you open the box you find exactly the same contents, then the box can be said to be stateless. (This is also known as referential transparency). If each time you open the box the contents vary — the box could be empty sometimes, but full later, it could have different items in it or the same items with some new ones added — then it is stateful.

As you can see from this description, most boxes that we use in the real world are stateful, since it is very unusual for their contents to remain the same throughout their lifetime. However, if you are doing something complicated, say keeping financial records from past years in banker’s boxes, you might impose a discipline on your boxes, such as designating a particular box to contain only those financial records from April 2002, so that you can reliably find the records for a given month when you are looking for them.

Two styles of programming

Programming is like this as well. “Normal” imperative programming uses variables that can have changing values throughout the life of the program, which matches our understanding of boxes in the real world. FP takes the banker’s view of boxes. Since programs are very complex, and you want to be assured of finding what you expect, then the default assumption is that the contents of boxes will be the same throughout the life of the program.

So the key difference between a functional and an imperative style of programming is not whether there is any state at all in the program but where you start from. With imperative programming you start by assuming total changeability of all values you work with and have to add disciplines to get that state under control, whereas with FP you start from a place of statelessness and strategically loosen the reins in small amounts when you need to. The great strength of the FP approach is that it is much easier to maintain control by letting the genie out of the bottle slowly than by starting with the genie out of the bottle and trying to jam it back in.

Locality of State

The first dimension of state I want to discuss, locality, should be the easiest for programmers to understand but, for some reason, often causes confusion. Locality for state is just like scope for names in that it ranges from totally private to global, depending on how widely in your program it can be seen. A well-known property that makes state more local is encapsulation, when it is used to limit the visibility of a particular bit of state to a small part of the program. For encapsulation to accomplish this, though, it must actually hide the effects of the state from the parts of the program outside its scope.

To explain this, it is helpful to consider a common objection to functional programming languages by people new to the subject: how can a stateless program be built on a computer, which is an inherently stateful machine? The answer is that so long as the state is completely localized “under the hood”, it isn’t state at the next level up.

If we go back to the box analogy, let’s say that you have a very high-tech box that has the same contents every time you open it, but that, instead of the contents just being there when the box is closed, it actually disassembles the item when you close it and re-assembles it when you open the box again. The box is stateless because its contents never change from your point of view, even though its contents change when you can’t see inside.

So you can reduce the state in your program by ensuring that its various components look to each other as if they are stateless, even if internally they are implemented with large amounts of state, say for efficiency.

Monotonicity of State

Monotonicity of state is a little bit more subtle and probably less consciously familiar to programmers. Monotonic is a fancy way to say that once you add something, you can’t take it away. Using our boxes, the simplest example of monotonic state would be if, when you first open a box, you might find either nothing or something, but, as soon as you open the box and find something there, you must find the same something in the box every time you look in it thereafter. Upon finding the box empty, you could stop what you are doing and wait for something to show up in the box, after which you could be sure that it was not going to change, or you could take the opportunity to fill the box with something you want to fill it with, confident that someone else won’t be able to change it later. This is how dataflow variables work.

A more complex example of monotonic state would be a stream.
Once you have asked for the first value from the stream, it is as if you have filled the first box in the sequence, even if the box for the next item in the stream might still be empty.

With non-monotonic state, items can be added and taken away from the box at will, so that the box might have one thing in it the first time you open it, nothing in it the second time, and something totally new the third time. This is the kind of state that we normally think about when we talk about default imperative statefulness.

You can see that, though monotonic state is still state, it is much more predictable and manageable then full non-monotonic state, since you can always tell how much has changed from the last time you checked and you can be assured that what you found before will still be there. Furthermore, there is an explicit order to the changes in state that allows you to understand the history of operations, and thereby to make better automated decisions about what to do.

This is why the kind of message-passing concurrency, such as is found in Erlang is less stateful and relatively safer and more scalable than full shared-state concurrency, since an asynchronous message queue can be thought of as a monotonically-stateful stream.


While it would be much easier to talk about functional programming if statefulness were a nice black and white property that could be assigned to a particular language or program, I hope it is clear now that things are not quite so simple, and that degrees of state and “functionalness” could be present in any language or program. Obviously some languages and programs are going to make reduced state the default, and thus easier to implement, but the functional perspective can be applied to any language or program.

And making use of this perspective will help tame the complexity of software, especially in the face of concurrency.

No comments:

Post a Comment