Functional Programming Doesn’t Work (and what to do about it)
planeterlang.org
planeterlang.org
Try reading it (and his archives, at http://prog21.dadgum.com/archives.html ) in that light. It's not just somebody ranting about how FP is junk after halfheartedly trying to learn Haskell. The "Purely Functional Retrogames" series is particularly good.
I would love to see more blogs that have people seriously evaluating how "newer"* languages hold up for real work, not just page-sized Greenfield projects. As he puts it, "Timidity does not convince." (http://prog21.dadgum.com/35.html).
* I know, Erlang isn't that new.
However, his critique shouldn't be surprising to anyone but blind believers. Paradigms and features all have comfort zones and none of those is large enough to cover even nearly everything.
Analogously to strong/weak typing and dynamic/static binding, you rarely only want either. You either start with strong and/or static and build yourself dynamic and/or weak behaviour by hand. Or you start dynamically and later enforce certain type constraints deemed appropriate. There are a few holy wars in between but you can raise above that.
Similarly pure functions and impure state management ought to support each other, not fight each other. Pure functions are pure, clean, and functional so that mutations can be sparse and well-controlled. Conversely, the state must be destructively updated in some place by the impure code so that the pure functions are relieved from having to bother with it.
Similarly you can start at either of the pure and impure ends but you're bound to end up somewhere in between for any useful program.
You can start with pure functions and build something with them and worry about saving the state later. The original author is right in that that I often start with the latter and feel somehow guilty when writing the state. I shouldn't! Personally, I've noticed that this approach too often equals gigantic mutations on huge, monolithic states that yield huge, monolithic new states that you have to store somewhere.
Alternatively you can start with impure code and clean out stuff into pure functions as you learn how the program evolves. Each time I do this in, for example, Python I get the sense of how fucking brilliant I am. I should do it more often! Personally, while "erring" on the impure side at first I've noticed that the resulting program is often more beautiful as pieces of pure art rise from a pool of impure goo.
Imagine you’ve implemented a large program in a purely functional way. All the data is properly threaded in and out of functions, and there are no truly destructive updates to speak of. Now pick the two lowest-level and most isolated functions in the entire codebase. They’re used all over the place, but are never called from the same modules. Now make these dependent on each other: function A behaves differently depending on the number of times function B has been called and vice-versa.
In C, this is easy! It can be done quickly and cleanly by adding some global variables. In purely functional code, this is somewhere between a major rearchitecting of the data flow and hopeless.
I am almost certain a Haskellite will say something about monads or arrows, but I don't know what.
EDIT: I guess another criticism might be "when would you possibly need this?". It smells suspiciously like a symptom of bad design -- these two totally independent, low-level calculations are now dependent on each other. A possible use case might be a tweak to an artificial physics, as in a simulation or game.
As long as programs are regarded as linear strings of basic symbols of a programming language and accordingly, program modification is treated as text manipulation on that level, then each program modification must be understood in the universe of all programs (right or wrong!) that can be written in that programming language. No wonder that program modification is then a most risky operation! The basic symbol is too small and meaningless a unit in terms of which to describe this.
Using global variables in C is still rearchitecting the data flow. It's just a really obvious way to do it.
You basically have 4 things here: functions A and B and variables a and b. Calling A increases a, calling B increases b. Function A depends on a, b. Function B depends on a, b.
In FP, you would probably pass those variables around. In C or some other language you could store them as global variables or pass them around. Global variables are a shortcut for passing them around. Just as you don't pass around all of the assembly code of the functions you want to use to the next function, you don't need to pass all variables around all the time.
To answer your edit: these two totally independent, low-level calculations are now dependent on each other.
This is normal, just look at any example of co-routines. It's like a two-player game where one player goes first but it doesn't matter which.
The point is that you might have to rewrite every part of the program in order to "pass around" those variables, where as in an impure language with global variables, this sort of major rearchitecting is not going to be necessary.
With what little information we have in this example, it would be best to modify the language so that it includes those two low-level functions in its specifications and make those global variables they require.
Modifying the language spec...is that pure or impure I wonder?
Neither, it's completely orthogonal to the pure/impure distinction.
There are inherently some changes that are extremely hard to make to a well-constructed functional program, and there are equally some changes that are hard to make to a well-constructed procedural program.
I would hypothesize there is no language paradigm in existence that provides optimal efficiency for implementing all possible types of architecture changes.
No one disputes that sometimes imperative styles of programming are clearer, or more efficient. Efficient functional programming is a new topic that is growing in importance as it becomes clear that the future is rooted in highly parallel programming.
But these specific complaints mounted at Erlang don't really ring true to me. For one, it's idiomatic to pass state along in functions, and it's not difficult at all to write branching logic based on a variety of cases in state. Now, if you have hundreds of fields in your state you will surely find Erlang to be more awkward than other functional languages, because you can't do things like pattern match and run guards into dictionary structures. But this isn't a failure of "functional programming", it's probably more of the nature of Erlang. Erlang just isn't optimal for that kind of work.
It seems to me like the author's complaint is more "Erlang wasn't the best for my projects and programming style" rather than "Functional programming has failed." Erlang is written by engineers who understood their target domain very well and wrote a very elegant system for wrangling it. Game development wasn't exactly on that list of things Erlang was meant to do well. :)
I do a lot of statistical work, and sometimes I use python, sometimes I use C or Fortran, sometimes I use R or PLT Scheme if I want to have some fun. I would agree that I am not a true expert in any of those languages, whatever that may mean, but I can solve the wide range of computational problems that I need to address quickly and efficiently in one of those languages.
This might just come from that fact that an undergrad class drilled into me a healthy disregard for the idiosyncrasies of syntax, libraries and idioms, and instead instilled in me the idea that semantics is the only serious issue for a student of programming languages.
The question becomes, though, why are A and B suddenly interlinked? Why was this context not already in place? Is there not a better structure to this data that would allow a minimization of stateful computations? Does this sudden A<->B dependence actually suggest a radically different shape of the code?
A well-written functional program should make these refactorings "easy" by having many useful and well-defined interchangeable pieces, and often it turns out that complex Haskell programs must refactor until the best dataflow structure is found (Theory of Patches for Darcs or the Zipper in xmonad).
Which in the worst case will involve lifting the type of pretty much every function in the program into a monad. Which is not going to be necessary in C.
Here's an example, roughly taken from a project I did not too long ago (in an imperative language, not a functional language). Suppose you have an e-commerce system. One day, the business decides to start giving out coupons, say for 10% off. Any order can have a 10% off coupon applied to it. All is fine and good, orders now have an optional coupon attribute, you compute order totals in an obvious way, coupons are nicely orthogonal to the rest of the system.
Then some time later, we decide to add free shipping coupons. But, there's a wrinkle: they only apply to ground shipping. Now, you can only add a free shipping coupon to an order with ground shipping; and, also, if the user changes their shipping method, you have to go look to see if they have a discount which now must be removed from the order. Now, two previously independent aspects of order placement and processing are coupled together.
Because this was written in an imperative language and backed with a stateful database store, it was mostly trivial to make the changes required. This scenario is not actually as bad as the situation the OP described, but my feeling is that it would be more difficult to have dealt with in a pure functional environment.
(BTW, this is actually a fairly mild example of the sort of complicated, non-orthogonal rules which come up in e-commerce systems. I picked it not because it was the hardest to translate to a functional paradigm, but because it was easy to explain in a couple paragraphs.)
For some reason I'm stuck on the idea of using heterogenous lists to store "things that can affect the order". You apply them in order in a stateful context and produce a finalized order or an error. To add coupons you just make an instance that lets coupons be a "thing that affects the order" and stick it in the list. The code is decoupled, order processing is modular, and you're using a data structure which fits the problem well.
I'm obviously using some 20/20 hindsight, but I think that frequently the initial headaches of refactoring by type turn into insights to how the problem is forcing you to use the right tools.
But to "design something well" requires omniscience, because it depends on understanding the problem, and in what ways that problem will likely change in future. It's a question of fact about the world, not an intellectual, mathematical or computational truth. When you are very familiar with a problem, you acquire this domain knowledge, much of it informally and unconsciously, and then you can design well... or, well enough for practical purposes.
Along the way, in the process of acquiring this domain knowledge, you will make mistakes, and you will need to change things. Fred Brooks: Build one to throw away. You will anyway. Oh, and then you get the second system effect, when you try to correct all the mistakes of the first disaster.
Unfortunately (or fortunately, if you like learning), most of us move on to new projects and new domains so quickly, that we never acquire that level of mastery of a problem domain. How many people have written the same kind of application three times from scratch?
I disagree with that. If you can easily accomodate any changes it means you probably over-designed and over-generalized and made your solution too complicated.
> But to "design something well" requires omniscience, because it depends on understanding the problem, and in what ways that problem will likely change in future.
Yes, that is the problem. A lot of good programmers are prone to over-generalizing, even for code that should be simple and straight-forward. Sometimes it pays off, but not always.
> Fred Brooks: Build one to throw away. You will anyway.
I tend to approach programming as experimentation. "Let's build something and try it out" kind of approach. Then "if it works, we'll enhance it, otherwise we'll throw it away and try something else". It seems wasteful but with a language like Python it is easy to prototype things out.
I get your point, I just meant that "doesn't work" is quite a stretch from "doesn't allow ugly global variable hacks".
(+) http://xml.resource.org/public/rfc/html/rfc2119.html#anchor3
You end with code that is hard to reason about.
For me it's good, that making the code complicated to understand is hard.
Obviously you can do that. The author mentions this possibility. But his point is that passing the state around may involve adding extra parameters to a very large number of functions, which is much more difficult than just using a global variable.
It seems odd to me to say that faking global variables by clumsy manual state threading is cleaner than just using global variables. It is more error-prone, more verbose, and less indicative of program structure and programmer intent.
Of course this doesn't mean that a program will be easier to read after going the easier to write way too many times...
if a > 0
then let a = a + 1
in # do smtg with a
else # do smtg with a
With a little bit of syntactic support from the language, you could easily write this in a natural, comfortable form, which will then automatically get compiled to the code above. In Haskell, it's pretty easy to do that with monads:
do $ when (a > 0)
a <- a + 1
A bigger problem is when you're dealing with iteration, and you can't know at compile time how long the loop is. Then you can't unroll it, which means the compiler implementors can't use the technique above. But they can use a different technique - recursion, which can later be compiled back to iteration via tail calls optimization, removing any awkwardness. Again, with the do monad, it's trivial in Haskell.
Of course the question is, if you go through all the trouble to build up the beautiful, elegant mechanics that make it possible to write imperative code that gets compiled to purely functional code, that gets compiled back into imperative machine code for efficiency - what's the point? IMO the point is mathematical beauty - something you can't easily put a price tag on. There are some empirical benefits as well, but I'm not sure if they outweigh the troubles. Anyway, there is a great argument here, but the author only scratches the surface of the problem and doesn't dig nearly deep enough to get to the meat of the problem.
A1 = ...
A2 = ...
I see putting stuff in a variable as a way to 'take a breather' in the middle of code:
A = some(hairy(function(that() + does() * lots()));
B = back(into(A) + the(A) fray());
While putting intermediate steps of a calculation into variables can help clean up the code, if there's any sort of conceptual significance to that value, it's worth choosing a better name than X1. "ATC" (with "Avg. Triangle Count" as an end-of-line comment), for example, would actually mean something.
the fact that the author is dropping erlang because of (largely) syntax issues, without apparently understanding what they are losing that other languages - imperative or functional - simply don't provide suggests they shouldn't be given that much weight...
Also, his archives are worth a read, particularly the Purely Functional Retrogames series. Excellent stuff.
As for running a static variable across to unrelated functions, I don't know any language where that's considered a good idea. Well maybe Fortran, but that really doesn't help the argument.
let a = (if a > 0 then a + 1 else a)
in #something or otherTwo library calls, deep in vastly different parts of the code. And you're going to make them mess with each other? For christ's sake, they're used everywhere, they've been working fine for ages, and now you're going to mess with them, make them intertwined and thus complicated, for one stupid edge case.
You know if you really wanted to do it, you could do an unsafePerformIO, but...
...I'm just not buying it. I can think of many ways that FP (not just pure FP) is deficient, but this is not one of them. The biggest problem I see with FP is that when your data model is sparse, imperative-style state change updates are just more efficient from a programming perspective.
I should note that I'm not the first one to spot this. It was talked about amongst the FPers I knew in school. Lets just say each variable, every function input and function output is a vertex in a graph. When I say that the data model is sparse, what I mean is that the edge count on the vertices is small. How small? I dunno, it's a gut feeling sort of thing, or maybe someone could correct me on it.
These are both easy tasks in Haskell. Just use the state monad. You also get 100% certainty that the state isn't leaking into places where you didn't want it to leak to.
Lack of controlled mutable state is a failure of Erlang, not functional programming.
Also, counting function calls would actually be fairly straightforward in Erlang as well. You create a process which counts function calls to B. A then queries this process when it needs to find out how many function calls were made to B. Slightly harder to program, but it works even in the distributed setting.
Should have been something more like:
"Purely Functional Programming doen't always work"In C, this is easy! It can be done quickly and cleanly by adding some global variables. In purely functional code, this is somewhere between a major rearchitecting of the data flow and hopeless.
In Common Lisp, I'd DEFVAR a variable with dynamic scope, then LET its value be incremented on each call to B. I'd never use SETQ or its variants. There's no major re-architecting here, and no breakage of the functional style. Dynamically-bound variables are like implicitly passed-through arguments to every function call.
Think of dynamic variables as constituting merely the implicit passing of a symbol->value hash table as an argument to every function call, and a LET as a local modification to this hash table.
So:
(defvar a 10)
(defun x () (if (= a 0) t (let ((a (- a 1))) (x))))
behaves the same as:
(defun x (&optional (a 10)) (if (= a 0) t (x (- a 1))))
edit: I forgot to mention that Dijkstra had some complaints when Functional Programming first reared its head, http://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EW...
What's so confusing about that? This is not a shortcoming of FP.
I think the culture surrounding each of those languages does look down on using the mutation features (and for good reasons), but it's not like the message is "never use them", but rather "don't use them if you don't have to".
Maybe the fact that he doesn't emphasize that his gripe is with pure functional programming and calls it plain "functional programming" is a little misleading.
But, overall I guess some FunctionalWeenie learnt about NoSilverBullet, to put it into C2-wiki terms (so don't take the mild burn too serious :) ).
Oh, and the links work fine in the original post (http://prog21.dadgum.com/54.html).
"No one thing is good for everything."
However, good languages like Erlang offer many alternatives. Mnesia has near real-time access speeds, which you could for example implement in your render thread/process. It also has things like per-process dictionaries/hash, and ets for dirty and even faster access to 'global' data.
I suspect that a lot of it has to do with the architecture of the code. I tend to prototype fast, so I run into these issues often. But I tend to keep mental notes as to how the code would be better broken off into modules, reduce the number of passed arguments, (and makes those to the fastest possible primitives.) and move any 'global' data to mnesia.