Functional Programming Doesn't Work (and what to do about it)

http://prog21.dadgum.com/54.html

by ColinWright • 15 years ago

71 54 15 years ago

prog21.dadgum.com

fexl• 15 years ago

I concur. I've been working on http://fexl.com for some time, and when all is said and done, for my embedded scripting applications I prefer to use simple line- and token-oriented languages, where everything looks like this:

  word word word
  word word
  word word word word
  ... etc.

The semantics of these embedded languages tend to be domain-specific, or in the cases where I need Turing-equivalence, revolve around the notion of a general "whiteboard" where the program can scribble key-value pairs, and do basic conditions and looping. I find that non-programmers can follow this sort of logic very easily.

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.

anon_d2• 15 years ago

Could people please stop use "Functional Programming" as a synonym for "Pure Functional Programming"? The author uses them interchangeably even though his arguments do not apply to the impure style.

fuzzyman• 15 years ago

And whilst we're at it can people stop using "water" as a synonym for "pure water". Mud is water too, it's just not as pure!

dlikhten• 15 years ago

anon_d has a point, im interested in the same take on using scala and other hybrids.

mattdeboard• 15 years ago

Terrible, terrible, terrible analogy.

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).

chc3• 15 years ago

Even in impure languages, writing simple functions without side effects is the ideal of functional programming — the language just doesn't force it. If you want to write imperative code, just call it imperative. Don't call it functional just because that's the cool buzzword nowadays.

anon_d2• 15 years ago

s/use/using/. I hate not being able to edit my comments.

silentbicycle• 15 years ago

I think that's his point.

"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)

diolpah• 15 years ago

I stopped reading when I got to this gem:

"It can be done quickly and cleanly by adding some global variables."

We differ by orders of magnitude on what constitutes 'cleanly'.

zorked• 15 years ago

I suggest that you read the whole sequence of articles, particularly the ones where he tries to implement Pac Man in a purely functional way.

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.

KirinDave• 15 years ago

Except that he doesn't try and implement it in a pure, functional way.

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.

ldar15• 15 years ago

His solution is the "problem" of having to update the whole game state in a function is "is not to return new versions of anything, but to simply return statements about what happened" and "Actually handling what happened is a separate step, one that can be done later on in the frame."

Did he just make an imperative DSL out of erlang?

pessimizer2• 15 years ago

He's talking about the smallest and simplest of global variables in that quote, hence:

"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.

weavejester2• 15 years ago

"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."

That kinda sounds suspiciously like a monad.

tomp2• 15 years ago

Am I the only one that sees a big difference between functional programming and what the author is describing? For me, a functional programming language is one that allows for closures, inline functions, and functions as first class values (allowing higher-order functions such as map and fold). The author is describing what I would call a purely functional language, or even better, referentially transparent functions.

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.

epidemian2• 15 years ago

> For me, a functional programming language is one that allows for closures, inline functions, and functions as first class values (allowing higher-order functions such as map and fold).

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.

tomp2• 15 years ago

> OO languages (i.e. imperative)

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]

Here, we're using "the imperative style":

  even = []
  for i = 1 to 100
    if i % 2 == 0
      even.append(i)

This is functional style:

  even = filter(nats[1:100], i -> i % 2 == 0)

However, this is also imperative - we're telling the computer what to do. The main difference is just that in the "imperative style", we're dealing with elements, while functional style is focused around sequences.

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...

Jach2• 15 years ago

You're getting mixed up with what a technical form of functional programming is (which can be summarized with "nothing changes", which is more inline with your "pure" quantifier; try this: http://academicearth.org/courses/the-structure-and-interpret... ), and with features of what members of the Functional Family tend to have.

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.

chc3• 15 years ago

I don't see how function pointers allow inline or anonymous functions. They point to already-defined functions, which can't be defined inline or anonymously.

locci• 15 years ago

The same argument could be made about structured programming: "Why should I restrict my programs to have one entry point, one exit point and a single flow?"

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 eﬀects, no ﬂow 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 beneﬁts, 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).

[1] http://www.cse.chalmers.se/~rjmh/Papers/whyfp.pdf

psykotic2• 15 years ago

The modularity advantage of shared state's "spooky action at a distance" when properly employed is not a fresh insight. It's even addressed in good textbooks on programming such as van Roy and Haridi's Concepts, Techniques and Models of Computer Programming. Here's an old related LtU post by van Roy: http://lambda-the-ultimate.org/classic/message9361.html. Another dramatic example (which is one of the book's exercises) is revocable capabilities.

gruseom• 15 years ago

not a fresh insight

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.

psykotic2• 15 years ago

My comment was not meant to disparage James, so there's no need for you to valiantly leap to his defense. It was just an attempt at putting his observation into a wider context. :)

yummyfajitas3• 15 years ago

Functional programming works just fine.

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.

yoklov3• 15 years ago

It took me a while to realize, but monads are a great solution to the problem of state (to mention just one thing).

Now that I've gotten used to them though, it sucks not having them in (many) other languages... Haskell has spoiled me :(.

rbxbx• 15 years ago

Most other (good?!) languages should allow you to define monadic data structures fairly easily. Many languages are able to make use of monads, the difference being that Haskell leaves you (almost) no other option.

SamReidHughes• 15 years ago

Refactoring a stateless program into one that uses state is a big pain. Making programs that use different amounts of state, or kinds of state, at different parts within the program, is also a big pain. Functional programming languages including ones where monads are regularly used are just bad at this. You get towers of state transformers, or a lot of boilerplate for converting between one kind of state to another, and boilerplate for entering and leaving different kinds of stateful situations. Or you can just have one big state monad that goes everywhere, in which case there's three kinds of things, which are functions that live purely in IO, those which are pure, and those which live in your state monad.

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.

yummyfajitas3• 15 years ago

I agree with you that Haskell's approach is imperfect. There are too many liftIO's, and some method of taking the union of state monads (rather than nesting them) would be vastly better.

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.

weavejester2• 15 years ago

"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."

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.

yoklov3• 15 years ago

Agreed, but just because: Quicksort in Haskell:

  quicksort [] = []
  quicksort (x:xs) = quicksort front ++ [x] ++ quicksort behind
     where front = filter (<= x) xs
           behind = filter (> x) xs

xyzzyz4• 15 years ago

I hate this example. This is not what quicksort is about. Quicksort is about sorting array in place. The preceding code is not. Also I can't see how it's relevant to the thread.

dwc• 15 years ago

Minor[1] nit: quicksort is not a problem, it's a solution to a problem. The problem in question in efficient general-purpose sorting.

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.

comex• 15 years ago

If you are designing a program, even in an impure language, it's a good idea to design it so that it never has to do this. It's confusing and bad style.

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?

yummyfajitas3• 15 years ago

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.

babel17• 15 years ago

- When you change a function b so that it depends on the number of times a has been called, then this is a pretty deep change; but yes, it should be simple to do in situations like logging etc.

- 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)

xyzzyz4• 15 years ago

Why care about converting to SSA, when your objective is to convert to CPS?

demian• 15 years ago

"No reason to add extra complexity just to dodge having a single global variable"

Yes, yes there is. It's called "reducing side effects".

raganwald• 15 years ago

In all fairness, "reducing side-effects" is a means; "ease of composing a program," "ease of understanding a program" and "ease of extending or changing a program" are ends.

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."

marshray• 15 years ago

Anyone who's been a programmer very long has pulled their hair out over programs which have been extended far beyond the intentions of the original developer. It's not the right reaction to make everything as extensible as possible either, but eventually one learns a healthy respect for the dangers of global variables.

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.

sirphilip• 15 years ago

Title: Functional Programming Doesn't Work

Content: At this point I should make it clear: functional programming is useful and important.

schiptsov• 15 years ago

It is remarkable stupidity to post such nonsense on the site which is a reality-check example of the exactly opposite. ^_^

zach• 15 years ago

Original discussion: http://news.ycombinator.com/item?id=1020130

Original discussion on follow-up article: http://news.ycombinator.com/item?id=1023232

Functional Programming Doesn't Work (and what to do about it)

Related Stories