It's not about technology for its own sake. It's about being able to implement your ideas.
I have been accused of taking the long way around to obvious conclusions. Fair enough. But to me it's not the conclusion so much as tracking the path that leads there, so perhaps I need to be more verbose and not go for a minimalist writing style. We shall see.
The modern functional programming world can be a daunting place. All this talk of the lambda calculus. Monads. A peculiar obsession with currying, even though it is really little more than a special case shortcut that saves a bit of finger typing at the expense of being hard to explain. And type systems. I'm going to remain neutral on the static vs. dynamic typing argument, but there's no denying that papers on type systems tend to be hardcore reading.
Functional programming is actually a whole lot simpler than any of this lets on. It's as if the theoreticians figured out functional programming long ago, and needed to come up with new twists to keep themselves amused and to keep the field challenging and mysterious. So where did functional programming come from? I won't even try to give a definitive history, but I can see the path that led to it looking like a good idea.
When I first learned Pascal (the only languages I knew previously were BASIC and 6502 assembly), there was a fixation with parameter passing in the textbooks I read and classes I took. In a procedure heading like this:
function max(a: integer; b: integer): integer;
"a" and "b" are formal parameters. If called with max(1,2), then 1 and 2 are the actual parameters. All very silly, and one of those cases where the trouble of additional terminology takes something mindlessly simple and makes it cumbersome. Half of my high school programming class was hung up on this for a good two weeks.
But then there's more: parameters can be passed by value or by reference. As in C, you can pass a structure by value, even if that structure is 10K in size, and the entire structure will be copied to the stack. And that's usually not a good idea, so by reference is the preferred method in this case... except that data passed by reference might be changed behind the scenes by any function you pass it to. Later languages, such as Ada, got all fancy with multiple types of "by reference" parameters: parameters that were read-only, parameters that were write-only (that is, were assumed to be overwritten by a function), and parameters that could be both read from and written to. All that extra syntax just to reduce the number of cases where a parameter could be stomped all over by a function, causing a global side effect.
One thing Wirth got completely right in Pascal is that "by reference" parameters don't turn into pointers at the language level. They're the same as the references that eventually made it into C++. Introduce full pointers into a language, especially with pointer arithmetic, and now things are really scary. Not only can data structures be modified by any function via reference parameters, but any piece of code can potentially reach out into random data space and tromp other variables in the system. And data structures can contain pointers into other data structures and all bets are off at that point. Any small snippet of code involving pointers can completely change the state of the program, and there's no compile-time analysis that can keep things under control.
There's a simple way out of the situation: Don't allow functions to modify data at all. With that rule in place, it makes no difference if parameters are passed by value or by reference, so the compiler can use whatever is most efficient (usually by value for atomic, primitive types and by reference for structured types). Rather shockingly, this works. It's theoretically possible to write any program without modifying data.
The problem here is how to program in a purely functional manner, and this has gotten surprisingly short shrift in the functional programming community. Yes, types provide more information about intent and can be used to catch a certain class of errors at compile time. Higher-order functions are convenient. Currying is a neat trick. Monads allow I/O and other real-world nastiness to fit into a functional framework. Oh does mergesort look pretty in Haskell. I shudder to think of how tedious it was operating on binary trees in Pascal, yet the Erlang version is breathtakingly trivial.
But ask someone how to write Pac-Man--to choose a hopelessly dated video game--in a purely functional manner. Pac-Man affects the ghosts and the ghosts affect Pac-Man; can most newcomers to FP puzzle out how to do this without destructive updates? Or take just about any large, complex C++ program for that matter. It's doable, but requires techniques that aren't well documented, and it's not like there are many large functional programs that can be used as examples (especially if you remove compilers for functional programming languages from consideration). Monads, types, currying... they're useful, but, in a way, dodges. The most basic principle of writing code without destructive updates is the tricky part.
permalink January 31, 2008
I'm James Hague, a recovering programmer who has been designing video games since the 1980s. Programming Without Being Obsessed With Programming and Organizational Skills Beat Algorithmic Wizardry are good starting points. For the older stuff, try the 2012 Retrospective.
Where are the comments?