Lambda the Ultimate

I would most certainly be among them. That's not to say that one should never use state (and that's why I'm still not a Haskell or Clean programmer). Rather, experience has reinforced the compelling nature of the argumentation of the CTM.

The question is whether the alternatives (pure FP) are indeed that much better (they have they problems as well), and which language constructs help most with the handling of state (e.g, is try_all such a good idea?)

The question is whether the alternatives (pure FP) are indeed that much better (they have they problems as well), and which language constructs help most with the handling of state (e.g, is try_all such a good idea?)

Right. The reason I mention the CTM specifically is because it discusses, e.g. that state need not necessarily be shared, which is where most of the problems actually arise. It also discusses non-determinism: if you have a general mechanism for "backtracking" that also undoes mutation, most of the issues also go away. The point is that there are multiple ways to skin the cat, but when most people talk about "state" they really mean "shared deterministic state" and aren't even aware of the other options unless they are equally absolutist, e.g. monads or uniqueness types, which can (often reasonably!) seem like a cure that's worse than the disease. This results in a "shared deterministic state or the highway" mentality, which is why the title of this post is "Totalitarian State." :-)

It might also be argued that the problem is not due to state as such, but rather programming style.

The paper is correct that restoring program state is often done incorrectly, but I'm not so sure that the language is always to blame. Object-oriented programming, for example, is supposed to encourage encapsulating "operations" and the means to undo them. Could the reason partly be because programmers program in FORTRAN even when they're actually programming in C#?

And OO languages aren't completely immune, either. See, for example, this thread from the Haskell mailing list, where people were seriously suggesting keeping a list of "edit operations" rather than using functional data structures as they were designed to do. BTW, I don't mean to single out Keean here. (I have nothing but the deepest respect for him.) My point is that merely programming in a pure language without "state" doesn't automatically free you from undo-related problems. You also have to think the right way; and even the best declarative programmers occasionally slip into imperative thinking.

If you don't have a pure language and need undo, IMO the best thing you can do is think in terms of transactions. Prepare everything that you need beforehand, and then only commit the operation at the end. (See, for example, this GotW article for examples in C++.) If the operation doesn't do any I/O, and you have appropriate memory-management, you can always do this. Note that in a lazy language, such as Haskell, you effectively get this for free; in a reduction, the result is computed in a first phase, and is committed (via an UPDATE operation) in the second phase.