Immutability is not enough

271 pointsby r4umabout 9 years ago

29 comments

joramsabout 9 years ago

> This is exactly the kind of problem that functional programming was supposed to help us avoid!No, no it isn't. Just like you wouldn't expect 2 * 3 + 8 to suddenly return 22 when you intend it to, you shouldn't expect the order in which you apply functions to not matter.When you pass around a changing state object to every step of your program, you are effectively doing normal imperative programming with global-ish state.

评论 #11396753 未加载

评论 #11396173 未加载

jasonkesterabout 9 years ago

Oh dear.I read the first half of this article watching him take the simple OO game loop and iteratively make it worse and worse, leaving it nearly unreadable and impossible to follow the logic or know what the state would be at any given moment. Then I came to this line:Let’s take a moment to appreciate a few of the things we’ve gained by rewriting this code in a functional styleHe actually thinks that he has improved the program. By piling functions up six deep and replacing pos.x += 3 with four lines of object accessor code (using strings for property names). Oh dear.The second half of the article, where he realizes that he has not actually gained anything by ruining his game is just the icing on the cake.I don't feel as though I've been sold on the benefits of Immutability today.

评论 #11396699 未加载

评论 #11396948 未加载

评论 #11396550 未加载

评论 #11396484 未加载

评论 #11396553 未加载

victorNicolletabout 9 years ago

The bugs described in the article stem from the existence of a "state" type. If you're allowed to call draw() on the result of handleCollisions(), but not on the result of processInput(), that means there are actually two state types in your program:<pre><code> draw : cleanState -> unit handleCollisions : dirtyState -> cleanState processInput : cleanState -> dirtyState </code></pre> These signatures allow draw(handleCollisions(processInput(state)) but forbid the incorrect ordering draw(processInput(handleCollisions(state)).Effect systems boil down to "discovering" these types eventually, but it is easier for a human to think in terms of what invariants are enforced by a given type. Even if there is no language support for actually checking those invariants before execution.

评论 #11395518 未加载

评论 #11395565 未加载

zbyabout 9 years ago

Can anyone explain why it is:<pre><code> var newState = drawManuel( drawBackground( processInput(state))); </code></pre> and not:<pre><code> var newState = processInput(state); drawManuel(newState); drawBackground(newState); </code></pre> When I read the first my intuition is that application of drawManual and drawBackground is important for the value of newState. The second one makes it clear that newState does not depend on drawManual (or drawBackground).It would also make the first bug more easier to spot:<pre><code> var newState = handleCollisions(state) newState = processInput(newState) drawBackground(newState) drawManuel(newState) </code></pre> The problem with the order of handleCollisions and processInput is now more visible because now it is obvious that just those two change the state - so we concentrate on them. And there are less parentheses.(Initially I used another variable here to make it more functional - but then I decided this is useless - we are still in an imperative language)I have a feeling that the author have some strange idea about what functional means. I stopped reading after this part.

评论 #11396222 未加载

_0w8tabout 9 years ago

It is interesting that the solution for order dependency problem essentially turns functions that update the state into functions that writes a program in a mini-language. When interpreted, the language updates the state. In Haskell this is known as Operational Monad [1].The nice thing with that approach is that it decouples complex application-specific logic from state management allowing to test both components separately. Another bonus is that it enables things like Elm's time traveling debugger [2].The drawback is that this adds maintenance burden as now one has to deal with the intermediate language. If that language is a poor fit for the problem, the burden can be rather high. This is especially bad in JavaScript where lack of rich static types makes generating programs and writing an interpreter is rather error prone.[1] <a href="https://wiki.haskell.org/Operational" rel="nofollow">https://wiki.haskell.org/Operational</a>[2] <a href="http://debug.elm-lang.org/" rel="nofollow">http://debug.elm-lang.org/</a>

Kiroabout 9 years ago

> However, we still don’t know what they do with the state. Do they modify it, or do they only read it?<pre><code> var newState = drawManuel( drawBackground( processInput(state))); </code></pre> I don't see how this makes it more readable. I still don't know which functions actually modify the state. This is what I imagined the result to be:<pre><code> var newState = processInput(state); drawBackground(newState); drawManuel(newState);</code></pre>

cousin_itabout 9 years ago

Don't try to use functional programming for GUIs, simulations, or games. That's what OO was invented for.Don't try to use OO for compilers or formal verification. That's what FP was invented for.Don't try to use OO or FP for operating systems. That's what imperative languages were invented for.Anyone who insists on a single style for the whole software industry is probably underinformed and overconfident.

评论 #11397169 未加载

评论 #11397319 未加载

评论 #11397361 未加载

评论 #11397201 未加载

raspasovabout 9 years ago

Here's a ClojureScript + core.async + Om + my own animation lib solution. No surprises, no weird bugs. Dead simple functional code + CSP = WIN! : )<a href="https://gist.github.com/raspasov/e894a0c6c26e5814d752b3fc9075c601" rel="nofollow">https://gist.github.com/raspasov/e894a0c6c26e5814d752b3fc907...</a>Here's also the anim lib gist, if anyone is interested <a href="https://gist.github.com/raspasov/f9ca712571efd932169e" rel="nofollow">https://gist.github.com/raspasov/f9ca712571efd932169e</a>

评论 #11396535 未加载

ktRolsterabout 9 years ago

"You will never find a programming language that frees you from the burden of thinking about bugs" <a href="https://xkcd.com/568/" rel="nofollow">https://xkcd.com/568/</a>

评论 #11396394 未加载

theseoafsabout 9 years ago

It seems what the author learned is that "programming languages sometimes let you do things in the wrong order", which is so obvious that it's kind of a non-observation.Anyway, functional programming on its own doesn't get you there, but functional programming with a solid type system does prevent this bug from happening.

akkartikabout 9 years ago

Great article, feeds all my prejudices. For example, I'm tempted to link to it in <a href="http://akkartik.name/post/modularity" rel="nofollow">http://akkartik.name/post/modularity</a> at the point where I say that "There seems the very definite possibility that the sorts of programs we humans need to help with our lives on this planet intrinsically require state."

评论 #11396073 未加载

评论 #11395507 未加载

jw-about 9 years ago

The problem doesn't really have anything to do with immutability; the problem is dependency and composition. E.g.f :: A -> Bg :: B -> Cwill let me write g(f(x)), but not f(g(x)). It does not matter if f and g are 'pure', the point is that f must come before g. I think the mistake is to think that functional programming is about immutability, and that immutability solves the problems. Immutability is there to keep the types honest, it is fine to have effects aslong as we are upfront about them, and don't conceal them under false names such as "int" and "bool".

fnordsenseiabout 9 years ago

Just as it's possible to model immutability on top of mutable structures, it's possible to model mutability on top of immutable structures. Regardless of which way you go, you end up with the properties associated with the kind of structure you're building. This is not too surprising, I would think.

DanielBMarkhamabout 9 years ago

There's a funky thing going on here because of the environment this guy is using: Javascript and a JS library to handle immutability.Because of the way he's coding, he's doing a lot of horsing around with several things at once. He's not writing functions and then composing them. He's refactoring multiple functions at the same time. As it turns out, this difference is important. Looking at it from one angle, from small pieces into larger pieces, you'll be solving the order of functions almost immediately. Looking at it from another angle, from big pieces into smaller pieces, you solve problems in a different order. You make pieces with names on them that do what you want, then you look at whether there's support in the code to do what you want to do, regardless of how that integrates. In fact, you end up (as he does) integrating later. You're not composing, you're decomposing.This is why one of the recommended ways to do FP is to use the REPL and get the core, toughest function working first. Then start composing. Work outwards from there.The first function you'd probably write in this case would perhaps be moveTheGuy which would move the guy from one place to another. You would immediately be solving the problem of whether or not the guy could actually move. Contrast this with the first function being updateTheWorld, where you can start inventing all kinds of stuff that might or might not happen. Then you horse around trying to figure out what should go under updateTheWorldI remember the first conference talk I saw with a guy talking about F#. It was still new in the industry, and many of the folks who were using it were true-blue OO coders.The guy gets up, shows some code, then goes behind-the-scenes to show us the "real" C# code. "As you can see, all this really is? It's do-while loop. You could code this way with C# and never touch F#"Yeah sure, but the environment you're in can help lead you to write better or worse code. It seems to me if I wanted to do pure functional stuff and Javascript I'd be pretty freaking careful how I coded. Lots of things there that point you in the wrong direction. Functional code just isn't regular code with all sorts of weird syntax; it's actually a different way of looking at solving problems.

_pmf_about 9 years ago

It seems to be a common trend to claim that functional programming solves the problem of state.It can solve the problem of accidental state in the solution space, but it obviously cannot change the fact that a specific problem space has stateful characteristics.Don't introduce accidental state, yes. But embrace the problem's states as first class elements of your solution and don't try to hide them.

评论 #11398121 未加载

RichieAHBabout 9 years ago

I don't see how functional programming would ever solve the problem of chronology. If the collision engine needs to know the new position in that frame then it needs to run that code first. You can't just run code whenever and expect functional programming to fix it. Nor will assigning different areas of the state to specific functions fix that either.I think immutable data solves a lot of headaches and using Redux and Immutable together in our current stack has shown me some of the benefits of immutability and a more functional programming style. However, much of this article was about immutability not being a silver bullet for things that, IMO, were never going to be solved by immutability. It's like saying it would be solved by writing everything in Haskell, there are some "complexities" that can't be hidden, e.g. order of events. Maybe I missed something.

评论 #11395837 未加载

yasonabout 9 years ago

<pre><code> var newState = drawManuel( drawBackground( processInput(state))); </code></pre> This isn't how functional programming must work to be functional programming. The point is always to write as much as possible in functional, preferably immutable style, if only it fits well. You can write a large portion of your program that way.The next sacrifice is to glue the functional calls together with more of a stateful approach, but preferably keep the mutable state more contained. For example, having a single function that handles the state, calls into the immutable functional code to do the heavy lifting, then sew everything together and ideally return something that is immutable and stateless. Like little bubbles of state where absolutely needed. For example, draw() calls in the above example can't be functional as drawing relies on side-effects. There's nothing to return from a drawing function, so those can't natively be chained into nested function calls.The final level is usually some hodge-podge state management at the very top level where it becomes unavoidable in order to keep things organised and beautiful. There's always some state, so you'll have to do it somewhere, but the more localized and minimized the better state management it is.

susi22about 9 years ago

I've said this a few years back in some other thread but it's so fitting here I'll say it again:In a few years down the road I hope that the JS folks take a very very close look at Rule engines. These kind of errors can be easily avoided with them.There is actually folks in the Clojurescript world using clara-rules for Browser state/rendering and it apparently works very well for them. I really wish some bigger player would push in that direction.

评论 #11398566 未加载

lliamanderabout 9 years ago

I really liked this post. It reminds me of a similar post by James Hague[0]A number of people seem to be hung up on what is meant by FP advocates saying "order doesn't matter". In all the literature I have read when I first learned about FP it seemed pretty clear to me that it meant "function composition is associative", not "function composition is commutative".But whether this is obvious is beside the point. The hypothetical confused programmer is merely a rhetorical device to set the reader up to think more deeply about how they handle state. FP teaches us to push state changes to the boundaries of the system. OK, once it is there, now what do we do with it?We handle it declaratively[1]. That's what treating the updates as data allows.[0]<a href="http://prog21.dadgum.com/189.html" rel="nofollow">http://prog21.dadgum.com/189.html</a> [1]<a href="https://awelonblue.wordpress.com/2012/01/12/defining-declarative/" rel="nofollow">https://awelonblue.wordpress.com/2012/01/12/defining-declara...</a>

hellofunkabout 9 years ago

Here is a related article for anyone curious about, or who uses, persistent/immutable data structures:<a href="http://concurrencyfreaks.blogspot.nl/2013/10/immutable-data-structures-are-not-as.html" rel="nofollow">http://concurrencyfreaks.blogspot.nl/2013/10/immutable-data-...</a>

wodenokotoabout 9 years ago

I've never really dived into functional programming but often end up reading a lot about it here.There's always been something about state and immutability that irked me the wrong way and I'm very happy to see it being put into words and code examples.

评论 #11395589 未加载

sesquipedalianabout 9 years ago

First of all, it's great that you're exploring functional programming paradigms and their applicability to game programming/state management.That being said I have to point out some things that bothered me: I believe you're conflating immutability and commutativity -- these things are not the same thing. Functional programming does not absolve you of paying attention to the order of operations. For example if you had two functions plus1 and plus2, you can order those any way you like since summation is commutative. However if you had plus1 divide2 functions, you have to pay attention to the order of application due to non-commutativity.

chriswarboabout 9 years ago

I think this is an example of something I see often, where a particular idea (e.g. immutability, interfaces, modularity, etc.) gets confused with a particular feature of a particular language which shares the same name. In this case, the author's code isn't using immutability; it just-so-happens to be creating an object called "Immutable.Map".Following the author's terminology, mutability is when we replace the contents of a memory location with different values, e.g.:<pre><code> Time | RAM ------+-------------------------------- 0 | foo 1 | bar 2 | baz . . . </code></pre> The author is using the term immutable to mean never replacing the contents of a memory location, so in their view this is immutability:<pre><code> Time | RAM 1 | RAM 2 | RAM 3 | ------+-------+-------+-------+--... 0 | foo | | | 1 | foo | bar | | 2 | foo | bar | baz | . . . . . . . . . . . . </code></pre> However, this is really just an implementation detail; Javascript programming isn't really about values in RAM (unlike, e.g. C where pointers are first-class values in the language). Instead, Javascript is conceptually built around variables, objects, scope, etc. So let's see how these RAM details translate to the values of variables.The "mutable" version:<pre><code> Time | "state" var ------+------------- 0 | foo 1 | bar 2 | baz . . . </code></pre> The "immutable" version:<pre><code> Time | "state" var 0 | "state" var 1 | "state" var 2 | ------+---------------+---------------+---------------+--... 0 | foo | | | 1 | foo | bar | | 2 | foo | bar | baz | . . . . . . . . . . . . </code></pre> So far so good. However, scope plays a large part in Javascript programming: we can only access variables which are in scope, and what's more the same variable name can refer to different values depending on the scope we're in. This is where the author confuses the concept of immutability with the name of a library they just-so-happen to be using. Their code keeps generating new scopes, in which the variable name "state" refers to a different value than in the previous scopes. Conceptually, the variable "state" is not immutable because it keeps referring to different things, even though the implementation details could be argued to be immutable.As an analogy, consider a display which shows the current value of a stock price. That is certainly not immutable, and trying to use that reading to perform calculations will be tricky since it keeps changing. This is like the author's original, mutable "state" variable.Now consider a plotter drawing a graph of how that price varies over time:<pre><code> | | _--. ____ Price | / \ / \ |__/ \__; \__/ | +----------------------------------- Time ^ | Now </code></pre> This is like the author's "immutable" version, where values are never changed once they're defined. This seems more useful for performing calculations, however, because the author keeps creating new scopes, they have no access to these old values! We have no access to the graph paper, we're only allowed to see the current position of the pen; which is exactly the same as if we only had the original display!If we take scope into account, we actually get the following:Mutable version:<pre><code> Time | Scope | Current "state" ------+-------+----------------- 0 | 0 | foo 1 | 0 | bar 2 | 0 | baz . . . . . . </code></pre> Immutable version:<pre><code> Time | Scope | Current "state" | "state" var 0 | "state" var 1 | "state" var 2 | ------+-------+-----------------+---------------+---------------+---------------+--... 0 | 0 | foo | foo | | | 1 | 1 | bar | foo | bar | | 2 | 2 | baz | foo | bar | baz | . . . . . . . . . . . . . . . . . . </code></pre> I do think the author has a few good points to make; however, I don't think it's an argument between being mutable vs. being immutable, so much as one between being implicit vs. being explicit.

评论 #11397199 未加载

评论 #11399447 未加载

tomeabout 9 years ago

The point of functional programming (or any good programming style, really) is to eliminate unneccesary dependencies (by which process the necessary dependencies are clarified) not to remove necessary dependencies (which by definition is impossible).

leshowabout 9 years ago

reminds me of Elm's Effects system.great article.

hathymabout 9 years ago

sounds like a solution looking for a problem.

dschiptsovabout 9 years ago

Immutability as absense of over-writes or mutations of existing values (in Erlang one just introduces a new binding for a new value) is obviously enough.State and I/O is easily incapsulable inside closures with CPS or with explicit message passing.For a lazy language one needs some ADT, like Monad, for explicitly "enforcing" a strict order of evaluation for a specific set of expressions, because I/O implies a strict order. Think of it as a transformation from a set to sequence (by defining an order as an ADT).Lifting State or IO into Monadic world is mere a trick to satisfy a typechecker and enforce a strict order by using an ADT. A strict language with optional lazynes could use ordinary type-tags.Nothing to see here.

评论 #11397396 未加载

kordlessabout 9 years ago

Not one mention of the blockchain in the story or here. How interesting.

riprowanabout 9 years ago

As a non-game-programmer, the idea of "collision detection and prevention" seems like a case of bad modeling.In the real world, two objects don't start by occupying the same space, then deciding that's not a valid state and taking corrective action.

评论 #11396168 未加载

评论 #11396204 未加载

评论 #11399845 未加载