Two Vexing Problems in Functional Programming

Interesting thread. Although most of the comments are "you're holding it wrong", I think the author brings up good points, which are roughly along the lines of : the FP language tutorials don't tell you how to write real programs. Now, granted the problems cited will show up at some level of scale in non-FP programming -- you can't just rummage around in some huge nested data structure inside a C++ server application for example because you'll end up holding dangling pointers among other things. However, perhaps you can get much further with non-FP languages by following the basic tutorials.

Also interesting to note that modern UI application frameworks such as React/Redux don't mutate state in-place. They tend to generate some kind of mutation object that is "played" against the in-memory stored application state. Probably similar to the FP-kosher solutions suggested here.

If you used the State monad for the author's interpreter example, and you did it in Racket (your "state of the world" is a cons-list), what would be the run-time of the resulting interpreter? Similar question for streams (although I'm not that familiar with streams, so I don't know how they would apply here, or if they can be implemented without changes to the base language)

> Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence.

Depending on your definition of "way" this is true. A lot of persistent vector-like structures can have quite good performance, but if your runtime is dominated by iteration and random updating, you will still get a speed up by using raw arrays, i.e. guaranteed contiguous blocks of memory.

> This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks.

This is not. The whole point of immutable data structures and concurrency is that iterating over them does not require any locks because the structure won't change! So concurrent reads require absolutely no new code and certainly no locks. For concurrent writes, the usual strategy is a single CAS-like operation at the top-level to swap out the old immutable structure for a new one (e.g. Clojure atoms, Java AtomicReferences, Haskell IORefs, etc.). But that's a single thing for the whole structure, not every level.

In general concurrent update in the functional programming world is handled by CAS not locks.

> Indeed, Perlis’s quip gestures toward the ulti­mate tension within all program­ming languages: how to connect the gossamer realm of human ideas to the grubby reality of a computing machine. Arguably the whole point of program­ming languages is to insu­late us from those details, and allow us to express ourselves natu­rally. But the farther we drift from reality of the machine, the less effi­ciently we can use its resources.

I would call it challenge, rather than tension, and I don't think expressing ourselves naturally is the only goal. We also want to express a solution that is tractable, that we can understand and have confidence in. "Natural" imperative programming can become intractable when mutating state; the goal of functional programming is to find a different way that is more tractable for humans, without worrying about if it feels "natural." If there's one thing programming (and mathematics!) has shown us, it's that anything we can do will eventually feel natural if we do it enough.

(We produced multiple generations of programmers for whom C-style for loops were the most natural thing in the world, almost the benchmark for what felt natural in a programming language. The "map" function was weird-ass shit to them. I know because the experienced programmers I worked with called it weird-ass shit when I discovered it in Python as a wee junior in 2000 and wondered why Java and C++ didn't have it.)

I don't think functional programmers consistently write code that is more tractable than imperative code, not yet. (I think some of them aren't trying, honestly.) But I think functional programming languages will evolve to better support that goal. It has only been in the last 10-20 years that the majority of working software engineers have fully recognized the difficulty of managing shared mutable state, generating widespread demand for functional programming languages for practical applications like web services, data processing, user interfaces, and so on. The trade-offs for those applications are different from the trade-offs for academic research, and the trade-offs for most industry programmers are different from the trade-offs for researchers who are immersed in the mathematical foundations. The academics have shaped functional languages for decades, but working software engineers will have more and more influence in the future.

> If that's your defense, party on.

I’m not the author. But that’s one explanation.

This goes back to the old “this is Hacker News” explanation. Some things are just implemented for the heck of it. Some things are just done according to a certain paradigm for the heck of it. Or in order to see how far you can go.

Why not see how far you can go with pure FP before it breaks down? Or you have to make compromises.

And not everything on this site is about “good engineering practices”. (Not that I would file your original, mocking comment under such a professional label, either.)

On a second skim though the submission is more naive than I would have expected from a Racket programmer. Using imperative datastructures like arrays (contiguous chunks of memory) and then copying for every action is not really recommended. You should use purely functional datastructures if you really want to not do destructive updates.