Functional Programming Doesn't Work (and what to do about it)
prog21.dadgum.com
prog21.dadgum.com
If you want to take two isolated functions and make them behave in some complicated manner depending on how often one or both are called, simply refactor them into the state monad. I.e., replace f: a -> a with f: a -> State a, and do the same for g.
This is likely to break stuff. In C, good luck figuring out what might be broken as a result. In a pure functional language, you know the damage is limited to the state monad. Anything outside of state is safe.
Now that I've gotten used to them though, it sucks not having them in (many) other languages... Haskell has spoiled me :(.
But then you realize that certain purely IO actions need to do some logging and then they can't live in the IO monad and you need to refactor logging out of everything else and put your logging monad inside your state monad (and put a bunch of new liftIO's all over the place), but wait, didn't you just want to add some logging statements to debug this thing, and now you're tearing apart the structure of the world.
So maybe we could come up with some abstraction for logically separate components of a program's state, and then create a type of action that uses descriptors telling what subset of a program's state components are used, or we could not do that and recognize that functional programming does not work just fine, and that pure functional languages are bad at working with state.
But I'm going to disagree with you regarding the claim that pure functional languages are bad at state. All of the problems you mentioned also exist in a non-functional language. In a non-functional language, you have functions which live in IO, in StateT GameState IO, and pure functions. The only difference is that you must carefully read the code to figure out which is which.
The approach of having one gigantic state monad which goes everywhere is precisely what you do in an impure language - just with some syntactic sugar to hide the liftIO.
Why would anyone want to do this? This sounds like a really, really bad idea.
I'm sure there are legitimate problems that are easier to solve with an imperative language than a functional one (such as quicksort, perhaps), but this article doesn't provide any.
quicksort [] = []
quicksort (x:xs) = quicksort front ++ [x] ++ quicksort behind
where front = filter (<= x) xs
behind = filter (> x) xsThe fact that you can update in-place is a nice bonus that gives the algorithm great performance and space characteristics in languages with mutable datastructures, but that implementation detail is not an inherent part of the beauty of the algorithm.
It's relevant because weavejester suggested quicksort is easier to implement in an imperative language.
So is Quicksort. There needn't be just one algorithm that demonstrates divide and conquer.
The whole point of quicksort is that it is in place, which makes it fast in spite of the pessimistic quadratic time
That's not the whole point of quicksort. It is done in-place, but that's just a great side effect of the algorithm. But assuming a cacheless memory model (for example the RAM model) the complexity of the out-of-place version is unchanged. The great thing about QS, IMO, is that it's easy to implement and typically O(n log n). When it is quadratic it is slow -- being in-place only barely makes the quadratic version more tolerable.
With that said, I know what you're saying :-)
If you read "Purely Functional Data Structures" there are a lot of tree/graph manipulations that are cake to do in C, but are a bear in ML/Haskell. A great programmer has all tools at her disposal, not just one (even if it is finely tuned).
Modifying the array in place is a inherently imperative technique, and while you /could/ do something like that in Haskell using, say, Data.Array.ST, you would loose the expressiveness of programming functionally and be programming imperatively just for the heck of it.
Trying to solve a problem in a functional language exactly the same as in an imperative one is foolish. They're different paradigms with different strengths and weaknesses, and if you try to map concepts 100% from one to another, it will often end in tears.
1. It may not be such a minor nit. Too often comparisons are made based on implement algorithm X where the algo is something that is specific to, say, imperative programming. This leads to endless and mostly meaningless arguments.
But if you've already designed the program, and you want to make a semantically minor change that requires linking formerly unrelated parts of the program, an impure language lets you do it without modifying half the program to keep up with new signatures.
I think the fact that the author is writing games-- where the user literally interacts with a big mutable world, and "when A happens, B should happen" is a natural request-- magnifies the problem, but it could happen anywhere.
Actually, I can think of an example: in New Super Mario Bros. Wii, there is a nice toy feature where when the music reaches a certain point, the enemies dance to it: http://www.youtube.com/watch?v=s03Kco-XQCY . I don't know anything about the actual development of the game, but as this doesn't significantly affect gameplay, I could imagine that this feature was added late in development, making what was formerly a one-way pipe from gameplay to sound into two-way communication. In a well designed program in a pure language, wouldn't this be hard to implement?
I'd rephrase this slightly.
If you want to make a semantically minor change that involves linking formerly unrelated parts of a program, an impure language permits you to do so without thinking through the effects this might have on your whole program.
In contrast, a pure program forces you to walk through your code and replace "a -> a" with "a -> GameState a" in every single function that might have broken. This includes the functions you might have forgotten about.
Now lets look at how this would explicitly work in your example of dancing enemies. In a pure functional language, your game logic is probably something along the lines of GameState a = State GameWorld a, with GameWorld a type describing the state of your world.
To add the dancing koopa troopa logic, you'd merely need to modify the GameState object and include (MusicTrack, MusicTime) as a field. There would be very little messing around with type signatures - the function advanceEnemyState: () -> GameState EnemyState is already expected to vary based on the world.
The author's whole point about SSA has nothing to do with purely functional programming. It's funny that assignment to variables has nothing to do with referential transparency - you can easily create as many true variables in a function (locally), assign all you want, and still have a purely functional / referentially transparent function.
I disagree. A language may have all those things and still be imperative. Smalltalk is regarded as one of the first and most importat OO languages (i.e. imperative) and has all those things you mention.
I think functional programming _is_ about pure functions, side-effect-free code and, in general, declarativity instead of an imperative style of programming. However, even the most "pure" functional programming languages, like Haskell, have some way of writing imperative, side-effect-full code. After all, you _need_ those side effects to make the program _do_ something hehe.
Why can't an OO language be functional? OCaml is OO, and it's one of the most functional languages I know (the other being Haskell). Scala is a functional language and an OO language (and an imperative language, as a matter of fact). Clojure could also be considered OO, with the new protocols. Javascript is a very OO language, and quite functional as well (especially considering the libraries such as Underscore). Maybe we should be talking about functional and imperative programming styles instead, imperative being a loop, and functional being a recursive function (map, filter, fold/reduce).
> declarativity instead of an imperative style of programming
I guess there's a thin line separating these concepts, and also a great deal of overlap and confusion. Here, we're declaring what we want:
even = [i from nats[1:100] where i % 2 == 0]
even = []
for i = 1 to 100
if i % 2 == 0
even.append(i)
even = filter(nats[1:100], i -> i % 2 == 0)
On the other hand, these concepts and expressions are used with so many different meanings and in so many different contexts, that it's no surprise that different people understand them differently. Maybe it's better to just talk in code...
Interestingly, the class system of Ocaml is one of its least useful parts. This is basically because most uses for inheritance (mixins, interfaces) are covered by first class functions.
> However, this is also imperative - we're telling the computer what to do.
No we don't (if you except the assignment to even). The fact that "filter" is an active verb is slightly misleading here. It deludes us into thinking the computer does something. (Well, it does, but not in the imperative programming sense of the word.) A more correct name would be "filtered", which makes it clearer that it produces a result, which is a filtered version of its second argument. I we wanted to be pedantic, "filter" should be reserved for a procedure that actually modifies its argument in place. But as there's no such procedure in the standard library of the typical functional language, it doesn't really matter.
Yes, I think you are totally right. As I see it, OO is about data and behaviour encapsulation, and object polymorphism. There is no reason why objects need to carry mutable state. But, they often do, and I think most authors do put OOP in the procedural/imperative side of programming.
Of course come cool hybrid languages do mix concepts from OOP and functional programming in order to have more expressive power. But most of them still map pretty closely to the Von Neumann model: a set of statements executed one after the other that alter the program's state, and hence are imperative too.
A functional program does not map it's computation to this Von Neuman model, which pretty much represents how computers work, but to an abstract model, usually based on mathematical concepts.
Therefore,
even = filter(nats[1:100], i -> i % 2 == 0)
But, in the end, I think that all that is a very absolutist approach to what is functional and what is not. Trying to draw that line is usually quite futile, as it really depends on very strict definitions, and, well, everybody agreeing on those definitions. I just wanted to clarify my point a little bit (though I probably failed)
> On the other hand, these concepts and expressions are used with so many different meanings and in so many different contexts, that it's no surprise that different people understand them differently. Maybe it's better to just talk in code...
Totaly agreed. Probably a more "fuzzy" definition of "functional", thus allowing one to say that some construct "more functional" than an other one, is more pragmatic. I also would say that
even = filter(nats[1:100], i -> i % 2 == 0)
even = []
for i = 1 to 100
if i % 2 == 0
even.append(i)
even = [i for i in range(0,100) if i % 2 == 0]
If you ignore closures, C has "inline [anonymous functions]" as well as "first class functions" in the form of function-pointers. The fact that the syntax is less than pleasant doesn't mean you can't do those things in it. C is also Object-Oriented-Capable, just like C++. Ignoring the C debates, you can even go up to ActionScript/Javascript which have those features you described, yet I wouldn't call them functional programming languages even if you can write functional code in them. They don't embody the ideal of "nothing changes" that, as you say, is more "purely functional". What member of the Functional Programming Language family loves the idea of side-effects? They all support it begrudgingly of course.
The answer is "Because it helps you to manage complexity in the long run".
To continue the "just add a simple global" analogy: after a while you add another, then you peek from a completely different function inside the global variable, modify it if the day is odd and soon you have made a mess of your program. In this case globals are simply a patch to an outdated design.
"It [all the restrictions] says a lot about what functional programming isn’t (it has no assignment, no side effects, no flow of control) but not much about what it is. The functional programmer sounds rather like a mediæval monk, denying himself the pleasures of life in the hope that it will make him virtuous. To those more interested in material benefits, these “advantages” are totally unconvincing."[1]
But the new kinds of glue functional programming brings about are usually worth the squeeze (for some kind of programs in some kind of situations, maybe).
The ecosystem of programming languages are analogous to class&race interplay in RPGs, especially RPGs where youve got strong distinctions between melee (imperative) and casting (functional) classes, with a smattering of hybrids (Python, Ruby, Scala, Clojure).
"After spending a long time in the functional programming world, and using Erlang as my go-to language for tricky problems, I've finally concluded that purely functional programming isn't worth it." (emphasis mine)
word word word
word word
word word word word
... etc.
Nice thing is, I can write these interpreters in any language, such as C or Perl or whatever, and "sandbox" their semantics in an airtight way for security.
James Hague would know this as he was the second replier to van Roy in the thread you cite. Freshness of the insight is hardly the point.
I'm glad you posted it, though. It's a good discussion. I particularly agree with this formulation of van Roy's: It is the overall simplicity of the system that counts, not whether it is written in a functional or stateful style. Using true state in the right places makes the system simpler overall.
Content: At this point I should make it clear: functional programming is useful and important.
Original discussion on follow-up article: http://news.ycombinator.com/item?id=1023232
Yes, yes there is. It's called "reducing side effects".
They're all reasons, but it's possible that adding complexity to facilitate a means may compromise the end, aka "winning the battle but losing the war."
Pacman is a toy application by today's standards. Imagine developing an MMO. Sometimes the biggest part of the problem is precisely figuring out what state lives where authoritatively and exactly how far out-of-date each asynchronous copy can be safely allowed to drift.
"It can be done quickly and cleanly by adding some global variables."
We differ by orders of magnitude on what constitutes 'cleanly'.
Keep in mind that he is an Erlang fan, and he is not trying to "debunk" functional programming. He's just toying with applying it to a domain where it's not used often (action video-games). The whole series is excellent, as is, in fact, the whole blog.
Every linked article discusses his adventures with Erlang. Erlang is a great language, one that I've used to great effect and enjoyed very much, but Erlang is really bad at representing rich type relations. The author is absolutely right that records are a painful substitute for dictionaries (a construct he reached for naturally because Erlang is a dynamic language).
He tried to implement it in Erlang's curious and somewhat isolated pseudo-functional rigid-actor paradigm. People have been making games and game-like demos in Haskell and OCaml for quite some time now (OCaml especially seems like very good fit). Erlang is a beautiful tool designed to solve one very specific set of problems. In its domain, it is nearly unrivaled. Outside of its domain, it is lackluster and limiting. It's only recently that modern functional programming techniques like monads and a cheap lambda syntax have started to make their way into Erlang (see Erlando: http://www.rabbitmq.com/blog/2011/05/17/can-you-hear-the-dru...), so it should be no surprise that someone writing in 2008 found a lot of awkward edges.¹
Am I wrong? I quickly scanned every linked article (and their follow-ups) and didn't see a single mention of anything but Erlang, including an all-too-common digression into using tuples as a dynamic substitute for algebraic data types.
¹ I can't help but feel like people assume most Haskell and OCaml programmers are chronic masturbators; making constructs like Monads and Functors because they just love category theory instead of the reality; building a functional pattern language on the same order as what Gamma, Helm, Johnson and Vlissides captured for OO programming.
Did he just make an imperative DSL out of erlang?
"it's completely doable to write [Pac-Man] in a purely functional style. The dependencies can be worked out; the data flow isn't really that bad. It still may be a messy endeavor, with lots of little bits of data to keep track of, and selectively moving parts out of the purely functional world will result in more manageable code. Now the obvious target is either the state of Pac-Man himself or the ghosts, but those are part of the core data flow of the program. Make those globally accessible and modifiable and all of a sudden a large part of the code has shifted from imperative to functional...and that wasn't the goal."
meaning that trying to make Pac-Man or ghosts into pieces of mutable state will result in them being manipulated entirely by being passed between functions, an even more functionally tangled program (in terms of less being able do some modifications to it as easily as could be done in a similar imperative program.)
Instead he's suggesting adding tiny self-managed globals for little values that truly are global (used almost everywhere) but aren't constant. Basically segregating tiny pieces of mutable state into their own little cubbyholes in order to simplify the logic.
Or at least that's how I'm reading it.
That kinda sounds suspiciously like a monad.
- Single-assignment really has NOTHING to do with purely functional programming; see my article "Purely Functional Structured Programming" or my (purely functional) programming language Babel-17 (www.babel-17.com)
- Random is an interesting operation; it is not purely-functional, but can be considered side-effect free; so it is not really imperative, either (although implementations via seed are)