An Analogy for Functional versus Imperative programming.

I was thinking the other day, about many things, as we drove back from my Aunt and Uncles in NY. I had been discussing with my father about C vs Haskell and, more generally, about functional versus imperative programming. I had been trying to explain why Functional programming is useful, particularly in areas relating to parallelism and concurrent code. To put this in perspective, my father has been writing low level system verification code for a very long time. (he started way back in the 70s) so he's pretty situated in the imperative world, with a (vast) knowledge of C and languages like Verilog and stuff. Me, I've only been writing code since I was 14-15. I have far more knowledge in languages like Scheme, Haskell, and to an extent, the ML family. I also regularly use Java and friends, So it's safe to say that trying to cross our respective expertises is most often quite difficult. Anyway, I came up with a pretty clever analogy, I think, for how Functional and Imperative programs relate.

Factorys

I have no idea if this analogy has been used before, but if it has, kudos to whoever came up with it, basically, it goes like this.

an imperative language is monolithic. it effectively can be modelled as one giant state machine that gets permuted. Like a Rube Goldberg machine, you don't design an imperative program to manipulate inputs, you design it for its side effects.

Here in Massachusetts, we have the Boston science museum, in which, there is a rube goldberg machine (RGM). It is, (next to the math room), by far one of my favorite exhibits. But what does an RGM do? Put simply, its just a while(1) loop. It ferries some bowling balls or whatnot to the top, and then drops then. The interesting part is the side effects. The bangs and whizzes and clanking and ratcheting of the chain as various balls drop and gears spin and cogs do whatever they do, cogulate, I guess. The point of the RGM is to manipulate the world indirectly. Someone, at some point, "said" to the machine, "start." From thence, it has worked to make noise and spin and do all that nifty stuff.

So, RGM's, you say, are mildly useless, right? Well. We'll come back to that in a minute, but suffice to say, like everything else in the world, they have there place.

So if an Imperative language is Like a RGM, whats a functional language?

Well, lets realize that effectively, all a program does is turn some set of inputs, to some set of outputs. Kind of like how a factory may take in some raw material, (steel, plastics, etc.) and create a new, better "material" from those outputs, (eg, a car). A language does the same thing, a user "inputs" a query to a database server (technically, he, or someone else, have given the program the database, too. Kind of like currying, here. hmm). Then after your query, you get back a database entry or list thereof which match your search parameters. Now, a RGM-type machine, or more accurately, a monolithic program, which are typically written in imperative languages (though you can write monolithic functional programs) take an input, and, completely internally, turn that input to an output. Kind of like a whole factory in a box. useful, yes, reusable not necessarily. A functional approach, on the other hand, is like the components that make up a factory. When I write a program in Haskell, I have a series of functions which map input data to intermediate data, and functions which map intermediate data to intermediate data, and then finally functions which take intermediate data and map it to output data. For instance, if I want to create a function which takes a list and returns it along with its reversal, in Haskell, I'd write:


myReverse :: [a] -> [a]
retPair :: [a] -> ([a],[a])

myReverse [] = []
myReverse (x:xs) = myReverse xs : x

retPair ls = (ls , myReverse ls)


So you can see how retPair starts the chain by taking input. copies ls and sends it to an output, and then sends the other copy to another "machine" in the factory, which turns a list of anything '[a]' to a list of anything. The result is then sent to output with the original as a pair '([a],[a])'

You can see this in the diagram:


..........................myReverse..............................
................/---------[a]->[a]-------\...they get............
input...........|........................|...rejoined............
>---------------|split ls................|---([a],[a])-->output..
................|........................|.......................
................\---------[a]->[a]-------/.......................
..........................identity...............................
..........................function...............................


So what does this "individual machine method" give us? For one, its free to reuse, its very easy to pull apart this "factory" of "machines" and reuse any given "machine" in some other "factory". It would not be as easy to do if we had written it procedurally, as in C/C++. I can hear the screams of imperative programmers now, "We would have written exactly the same thing, more or less!" and I know this, and don't get me wrong, you _can_ write this "factory style" code in C/C++, but what about less trivial examples? In Haskell, I can only write pure functional code (barring monads, which are borderline non-functional). Whereas in C/C++, writing this kind of reusable code is often hard. In a functional language, writing this kind of code is almost implicit to the nature of how you think about code. The point I'm trying to make is simply this, FP-style languages force you to write (more or less) reusable code. Imperative languages in many cases force you to write once-off code you'll never see again. I'm not saying this makes FP better, in fact, in a huge number of cases, I, as an FP programmer, have to write one-off imperative-esque state mangling RGM's to get things done. The point is Haskell helps me avoid those things, which makes for more reusable code.

Another thing, FP is famous for being "good" at concurrency. This analogy works wonders at explaining why. Think about the factory example, when I split ls into two copies, I split the program into two "threads". I effectively set up an assembly line, when I send done the copy of ls to the myReverse function, you can imagine a little factory worker turning the list around pi/2 radians so that it was backwards, and sending it down the line... You can even imagine the type constrictions as another little worker who hits a siren when you send down the wrong material. Imagine, however, trying to parallelize an RGM. RGM's are often dependent on the inability to be made concurrent, even if that wasn't the programmers intention. Imperative programs fight the programmer with things like deadlocks (two balls in the RGM get stuck in the same spot) and race conditions (two balls in the RGM racing towards the conveyor belt, with no way of determining who will win, how do you handle that?) whereas FP implicitly allows multiple "workers" to manipulate there own personal materials to make there own personal products at there station. In a purely functional program, each function is implicitly a process, you could even go so far as to give it its own thread. Each machine's thread would just yield until it got something to work on, at which point it would do its work, and go back to waiting, it doesn't matter which information gets to the next machine first, because it will just wait till it has all the information it needs to execute. Bottlenecking (a common problem in all code) is easier to see in this "factory" style view, since a bottle neck will (*gasp*) look like a bottle neck, all the functions will output to a single function. Thats a sign that its time to break it up, or have two copies of it running in parallel. FP makes this stuff simple, which makes FP powerful. Because for a language to have true power, it must make it so the programmer has to only think about what he wants to do, and not how to do it.

On the other hand, Imperative programming world. You have a number of excellent things going for you. Imperative code is remarkably good at clever manipulations of the machine itself. It is, in some ways, "closer" to the machine than a Functional language could ever be. So even though you have your share of problems, (parallelism and code reuse are the two I think are the biggest.) you have benefits to. Code in C is well know to be very fast, Object Oriented Languages are, I think, best described imperatively, and OO is a wonderfully intuitive way to think about programming. Imperative Programming is also makes it infinitely easier to deal with state, which can be a good thing, if use properly. Don't get me wrong, I love monads, but even the cleverness of monads can't compare to the ease of I/O in Perl, C, Java, Bash, or any other imperative language.

Hopefully this was enlightening, again, I want to say, Imperative programming isn't Bad, just different. I like FP because it solves some big problems in Imperative Programming. Other people are of course allowed to disagree. It's not like I'm Jake or anything.