13 ms·

Immutability is not enough

271 points by r4um 11y ago

fpoling 11y 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] https://wiki.haskell.org/Operational https://wiki.haskell.org/Operational [2] http://debug.elm-lang.org/ http://debug.elm-lang.org/
victorNicollet 11y 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: draw : cleanState -> unit handleCollisions : dirtyState -> cleanState processInput : cleanState -> dirtyState 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.
- shiro 11y ago
  I think the uber point of the article is that, even with the help of types, you cannot design the whole type structures until you know the entire picture. Suppose you throw some autonomous to your character (e.g. pathPlanning, preprogrammed behavior, subcomponents moving autonomously otherwise interfering other objects or user input, etc.) then there are many types of state, and you'll design what operation gets which type of state and returns which type of state, and that's essentially the same as how you design with chaining State -> State functions or working with imperative procedures. Sure, types will keep you away from shooting yourself---once you design the whole type chain the compiler will detect if you swap or drop operations inadvertently. But during the stage of your designing the type structure itself, the issue described in the article still exists.
  - victorNicollet 11y ago
    My point is that you don't have to design the whole type chain ahead of time, you can discover new type constraints as you go and apply them straight away (in the same way that you don't have to wait until you finish your design to start writing unit tests). Maybe an experienced game programmer would notice straight away that it could be a problem to draw a state that has not undergone collision detection, and design this state constraint into the game straight away (as a type, as an assert, etc.) and maybe another programmer wouldn't notice this requirement until they ran the game and noticed something odd (or someone from QA notified them) and had to dig through the system to find the underlying reason. But once they shot themselves in the foot once, it makes sense to implement _something_ to detect when they make the same mistake again.
    - shiro 11y ago
      During the design stage, you do need working components, independently implemented, and experiment various combinations. If you use types, that means frequently rewriting types to match the reorganizations of control flow. Types still help to prevent mistakes, but the main part of actual design process (like working on clay, or, scrap & rebuild with Lego pieces) is just as tedious as other ways. I read that the original article is trying to address that problem.
  - dllthomas 11y ago
    "even with the help of types, you cannot design the whole type structures until you know the entire picture" Sure you can. And like your design of anything else without knowing the entire picture, some bits of it will be wrong. A good type-checker - especially with inference - helps you find where you'll have inconsistencies in the assumptions you've made (usually before you've coded all the way to them), will give you a sense of the form of those inconsistencies, and when you change the types will point you at the code that needs to change in tandem.
    - shiro 11y ago
      I write a bit of Haskell in small projects but my background is largely Lisp/Scheme (the mud ball approach). I do admire hard-core Haskellers who seem "thinking in types". I wonder if there are good articles that tell how type-based approach helped dynamic development (meaning, lots of trial-and-errors, and rapidly changing spec, involving many components developed simultaneously by different programmers). I assume you can encode implicit constraints in types, for example (suppose components form DG, you might encode dependencies to ensure restructuring graphs always satisfy them). Just like to see how it works in real life development.
- ajuc 11y ago
  Now let's say you want collision with one special item change the way inputs are interpretted (you iterate on the game rules and someone had an idea to add alcohol that reverses the controls). This very detailed specification of dependencies in applications make it hard to change them quickly, and gamedev is mostly about how quickly you can iterate to make the game fun. I would love a hybrid system, where you get a "root" object passed to each function, that keeps the whole state, and you can just do side effects on that, but you are required by convention to always reference the members of that root object by full path. And then when you're finished you run a macro, and it generates nice elegant minimaly coupled functional code that passes only the required stuff around. Don't know if that's possible but it would be great.
  - zdkl 11y ago
    This with lisp syntax, compiling to Rust code & datastructures would be fun!
    - ajuc 11y ago
      I was thinking of a system generating code in the same language, and still keeping the root object, so that you can experiment, add some new dependencies, and regenerate dependenceis, many times. But you can at any moment pass null from the main loop instead of the proper root object to see if the code is generated properly and works only with the functional part. It's more complicated than a system that just regenerates everything from scratch every time. And removing dependencies would be tricky. So maybe your idea is better.
      - zdkl 11y ago
        Well you could precompile part of the guaranteed immutable stuff and distribute it seperately from the mutable execution part... Wait we've reinvented the JVM at this point!
      - zdkl 11y ago
        Come to think of it you should take a look at clojure/script, the pattern you describe could easily be implemented with maps in atoms. Cf the 'reagent' libs way of handling state
akkartik 11y ago
Great article, feeds all my prejudices. For example, I'm tempted to link to it in http://akkartik.name/post/modularity http://akkartik.name/post/modularity 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."
- mbrock 11y ago
  That's why Haskell programmers, for example, try to represent state in clear ways. The basic mathematical model of functions and values turns out to be able to represent state in several ways: the "monadic" way of composing state transforming functions; the "functional-reactive programming" way of modelling signals and events (which offers interesting solutions to the OP's game problems); various "interpreter" patterns; and so on. I point this out just because there's a widespread misunderstanding that pure functional programming is somehow opposed to modelling state. It's definitely not. It just involves building state models on the coherent basis of functions and values. Put simply, in Haskell, when your problem requires state, you can just use the "State" type, just like when you require I/O, you use the "IO" type.
  - idanoeman 11y ago
    Absolutely. In "The Awkward Squad," SPJ says "Haskell is the finest imperative programming language in the world," not entirely tongue-in-cheek. :)
- dkersten 11y ago
  Immutable state, functional programming, etc, is not about eliminating state, its about isolating it and carefully managing it. In a standard-imperative-mutable world, you can never be completely sure that state isn't being modified behind your back, you can never be completely sure that concurrent access is safe, you can never be completely sure how far reaching state changes you make are. The idea, IMHO, isn't to remove state. All programs need state. All interesting programs need state that changes over time. The "big idea" is that these changes are isolated and managed carefully so that nobody can pull the rug out from under you and change something behind your back or in a way that makes concurrent access unsafe. Immutable data means that the data you are reading will never change. If you read it again in ten minutes, it will still give you the same value. No other module or thread can change it. Concurrent access is safe too and all reads give the same consistent view. But even immutable data needs to be updated, so there will always be some mutable state (for example, in Clojure, you might have one or more atoms, which are mutable cells into which you can put immutable data. The data doesn't mutate -- it gets replaced[0]. Only the cell is mutated, but in a carefully managed way. There are other mutable state management primitives too). The programmer cannot accidentally mess up the state, they have to intentionally do it. So to reiterate: its not about eliminating all mutable state, its about isolating and carefully managing it. [0] and anyone still holding a reference to the data (not the atom) will continue to see the same data as before, unchanged. That is, if I take the value from the atom, somebody else updating the atom will not change the value I took out of it. This of course introduces things like the dual-writes problem, but Clojure gives me other tools (like refs with STM) to tackle these: ie atoms aren't the right tool for all use cases, just one example I chose.
wodenokoto 11y 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.
- ktRolster 11y ago
  Well, immutability is something that can help you in non-functional programming languages too: even C has const. It doesn't solve every problem, but it reduces the cognitive load.
  - RyanZAG 11y ago
    > but it reduces the cognitive load. No. It can reduce the cognitive load if applied in the correct place. It can just as easily increase the cognitive load if applied in the wrong place. Immutability should be used with care, not used always.
    - fnordsensei 11y ago
      I would contend that it's exactly the opposite; mutability should be used with care, not used always.
      - louthy 11y ago
        Totally agree. Mutability adds significant cognitive difficulty that just goes away with immutable structures. Here's a great talk by Rich Hickey on the subject. http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hic...
        kkoomi 11y ago
        I'm watching this now and just wanted to say thanks for the great link!
ktRolster 11y ago
"You will never find a programming language that frees you from the burden of thinking about bugs" https://xkcd.com/568/ https://xkcd.com/568/
- pron 11y ago
  Moreover, the following theorem is easily proved: there cannot exist a useful general-purpose programming language in which all (or even most) programs can be efficiently verified to be correct, either by man or machine[1]. Where "useful general-purpose" means any language with forward branching and some form of looping recursion (even if bounded) -- it does not need to be Turing complete -- and "efficient" means done in time polynomial in the size of the program. [1]: ... unless PSPACE = P, in which case some small class of languages that are not quite general purpose but useful nonetheless may have this property, because verifying useful finite-state machine languages is PSPACE-complete.
  - pron 11y ago
    For those interested, the proof for the Turing-complete and nearly-TC (as in total functional programming) cases is the same as the proof of the time hierarchy theorems[1], and for finite-state-machines the proof is based on results showing that verification of a (concise program expressing) finite state machine is PSPACE-complete. Those results are not surprising, as it is easy to see how any problem in computer science can be reduced (efficiently) to verification, so being able to efficiently prove correctness of a language capable of describing algorithms with super-polynomial complexity (this, BTW, only requires the ability to loop/recurse to depth 2) would mean contradiction. [1]: https://en.wikipedia.org/wiki/Time_hierarchy_theorem https://en.wikipedia.org/wiki/Time_hierarchy_theorem
deleted 11y ago
[deleted]
RichieAHB 11y 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.
- kristiandupont 11y ago
  My typical analogy is this: mutable state is to software as movable parts are to hardware. There are a group of problems that cannot be solved without it, but introducing it makes everything a bit more fragile.
dschiptsov 11y 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.
- marcosdumay 11y ago
  > A strict language with optional lazynes could use ordinary type-tags. And then you'll have a total order, that makes your code hard to parallelize. But more important, it mixes state updating (that can be actually done in several orders, can be rewinded, and has several other interesting properties) with IO, with list mapping, with exception handling, and everything else.
fnordsensei 11y 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.
jorams 11y 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.
- coldtea 11y ago
  >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.* Only the latter (that the order that pure functions are applied doesn't matter) has been touted forever as a benefit of functional programming, and what supposedly makes it "trivially parallelizable".
  - simoncion 11y ago
    > Only the latter (that the order where pure functions are applied doesn't matter) has been touted forever as a benefit of functional programming, and what supposedly makes it "trivially parallelizable". Functions that return the same values when given the same arguments are substantially easier to reason about than functions that return values that depend on both the arguments passed in and some state somewhere else in the system. Additionally, functions that don't modify their arguments are relatively easy to parallelize. (Due in part to the fact that it's really easy to figure out locking in a share-nothing system.) Anyway. I'm no scholar, but I'm pretty sure that no knowledgable FP proponent has ever seriously said "FP lets you call your pure functions in any order whatsoever and get the same end result, every time.". Perhaps I'm misunderstanding your statement?
    - the_af 11y ago
      Especially since shuffling the order functions get called often means they do NOT get called with the same arguments. This is important!
  - 11y ago
_pmf_ 11y 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.
- the_af 11y ago
  FP is all about embracing state as a first class element and reducing accidental state. I hope nobody claims otherwise :) The confusion is that people sometimes say "state" when they mean "mutable shared state".
susi22 11y 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.
- Chris_Newton 11y ago
  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. I agree up to a point, but I think off-the-shelf rule engines will only ever get us so far. Front-end web development in recent years has been going through its “Visual Basic phase”. We’ve been developing tools to help automate basic UI interactions and communications between front- and back-end. Those often get the job done better than the more manual techniques we used to use, but mostly they work best with simple presentation like forms or charts, and with simple data models and limited relationships — in other words, the kind of thing you need for a simple CRUD app UI where the tricky issues like scalability are handled on the back-end, like a lot of the web apps being developed today. However, you didn’t see a many people trying to build more demanding UIs in Visual Basic, things like CAD applications or DTP software or flight simulator games or tools for visualising and exploring tricky data sets. I agree that to build more sophisticated web apps, the front-end world is going to need to broaden its horizons. Tools that let you systematically represent large numbers of rules without hand-crafting a custom function for every one of them will surely be necessary in some cases. As with so much of web development, lot of lessons learned some time ago in other programming fields will be relearned by a new group of developers. However, that’s all still relatively easy. The hard part is how you reconcile the effects of those rules when they conflict, and there aren’t any universal right answers to that one. In fact, often there aren’t any good answers at all that can be fully automated. That can create a whole new world of nasty, awkward interactions where users have to actively deal with those conflicts. Maybe even that isn’t going to be scalable or efficient enough, and you have to design the entire system to operate with only incomplete or potentially incorrect information and still have acceptable if not always ideal behaviour. There are lots of interesting problems at this level, but a basic rule engine is never going to solve them alone.
riprowan 11y 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.
- jon-wood 11y ago
  Its less a case of them occupying the same space, and more one of each object running its movement code and stating where it would like to be in the next frame. Collision detection then takes place, finds that two objects want to share the same position, and notifies the object of that fact so that it can compensate. That compensation might take the form of changing velocity, blowing into a hundred pieces, or just outright ignoring the fact and carrying on.
  - riprowan 11y ago
    But in the example, the character in the game actually is moved to the invalid location, then the test is run for invalidity. Not sure why I'm downvoted, this seemed like a reasonable objection to me. Like I said I'm not a game dev.
- Kiro 11y ago
  Can someone explain why I cannot just check for collision before moving the character?
  - catmanjan 11y ago
    If the character moves faster than the space between him and the block, he will not be able to stand flush with the block - this can be fixed on other ways though.
  - tome 11y ago
    You can. It's called collision detection!
- GFK_of_xmaspast 11y ago
Kiro 11y ago
> However, we still don’t know what they do with the state. Do they modify it, or do they only read it? var newState = drawManuel( drawBackground( processInput(state))); 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: var newState = processInput(state); drawBackground(newState); drawManuel(newState);
zby 11y ago
Can anyone explain why it is: var newState = drawManuel( drawBackground( processInput(state))); and not: var newState = processInput(state); drawManuel(newState); drawBackground(newState); 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: var newState = handleCollisions(state) newState = processInput(newState) drawBackground(newState) drawManuel(newState) 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.
- dkersten 11y ago
  Indeed. If the state is immutable, then drawing (which shouldn't modify the state) can be, conceptually, done in parallel. While in practice this is unlikely to actually happen, your code snippet reflects this conceptual property better and is therefore, in my opinion, much easier to read: I know where the state is modified and where it is merely read. I also know that drawManuel cannot mess with drawBackgrounds data and vice-versa.
  - ajuc 11y ago
    It's not only conceptual difference. It is a good practice to decouple state manipulation from drawing (even to do drawing in different thread, and with different frequency, than state manipulation). This allows for computers with wastly different processing power to run the same simulation in sync, while the more powerful computer can draw 10 times as many intermediate frames. Alternatives are variable step length (makes it hard to write deterministic simulation), or fixed step length and capping framerate to it (sacrifices animation quality on better computers for easy implementation). EDIT: also - the ordering between drawManuel and drawBackground probably do matter, and there's probably some state related to drawing (like animation frame numbers etc) so there should be separate screenState that reflects that. state = processInput(state); screenState = drawBackground(state, screenState); screenState = drawManuel(state, screenState);
raspasov 11y ago
Here's a ClojureScript + core.async + Om + my own animation lib solution. No surprises, no weird bugs. Dead simple functional code + CSP = WIN! : ) https://gist.github.com/raspasov/e894a0c6c26e5814d752b3fc9075c601 https://gist.github.com/raspasov/e894a0c6c26e5814d752b3fc907... Here's also the anim lib gist, if anyone is interested https://gist.github.com/raspasov/f9ca712571efd932169e https://gist.github.com/raspasov/f9ca712571efd932169e
- retrogradeorbit 11y ago
  Here's a complete web game a mate and I did for global game jam this year in less than 24 hours from scratch using ClojureScript and core.async targeting pixi.js. https://github.com/retrogradeorbit/moonhenge https://github.com/retrogradeorbit/moonhenge It even has multiple weapons, enemy waves and an end sequence if you complete the game! The code is not as clean as it could be. For instance it has many more atoms than it needs and lots of code that could be simplified and re-factored. But time was extremely tight and it was a massive rush job. But even so in the end it came together seamlessly with no weird bugs or crashes of any kinds and it is rock solid. I attribute this to the immutable data structures and pure functions used. I've done games before using mutable OOP and in my experience they never come together this easily or with so few bugs.
  - raspasov 11y ago
    This is awesome - great job! : )
jasonkester 11y 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 style He 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.
- zby 11y ago
  My theory is that he thinks that variables are an imperative language feature - so he tries to avoid using them to make it all functional. He is partially right - variables are imperative. What he does not know is that he can use his variables in a way that directly translates into purely functional 'value binding' and leave them readable.
  - brlewis 11y ago
    I wish they would still use Scheme in intro computer science. It's so obvious in that language what is and isn't pure functional.
    - rubidium 11y ago
      They still do at some universities. https://www.rose-hulman.edu/Users/faculty/young/CS-Classes/csse304/syllabus.html https://www.rose-hulman.edu/Users/faculty/young/CS-Classes/c...
    - DanFeldman 11y ago
      We use it at Berkeley for the first CS class, CS61a. The final project is writing a scheme interpreter in python!
- 11y ago
hellofunk 11y ago
Here is a related article for anyone curious about, or who uses, persistent/immutable data structures: http://concurrencyfreaks.blogspot.nl/2013/10/immutable-data-structures-are-not-as.html http://concurrencyfreaks.blogspot.nl/2013/10/immutable-data-...
hathym 11y ago
sounds like a solution looking for a problem.
cousin_it 11y 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.
- Illniyar 11y ago
  I really like your sentiment, but I'm not sure if "OO was invented for X" or "FP was invented for Y" is right. They are abstract paradigms that were created with very little connection to their underling usage at the time (FP in particular stems from a mathematical background, but most of OO as well). Rather I would say more then "OO is more suitable for GUI" and "FP is more suitable for compilers" (though I'm not sure if I agree with that)
  - deleted 11y ago
    [deleted]
- _asummers 11y ago
  I'm not convinced GUIs can't be built with functional programming techniques. My GUIs (in Android and more recently with React) generally tend to follow a unidirectional data flow, where the view building is really a dumb passthrough of massaged data that's stored in a local DB (like SQLite). The view state could be represented ENTIRELY by a JSON object, e.g. and since it's all stored locally, it's replayable if something goes wrong.
  - creshal 11y ago
    Configuring and assembling a GUI out of an existing GUI framework, and writing that framework in the first place, are two different use cases IMO. OOP works a lot better for the latter case.
- the_af 11y ago
  This isn't true about games; FP isn't a bad fit for them. Games can be written in FP, and there are some interesting things you can do with it, it's just that it's obviously less explored and more "researchy". See: - Nikki and the Robots (Haskell): https://github.com/nikki-and-the-robots/nikki https://github.com/nikki-and-the-robots/nikki - Frag, a simple 3D shooter (Haskell): https://wiki.haskell.org/Frag https://wiki.haskell.org/Frag - Clean Game Library, using Clean, an FP language with a different philosophy from Haskell's: http://cleangl.sourceforge.net/ http://cleangl.sourceforge.net/ - For my (abandoned :( ) master's thesis, I was also writing a platformer in Haskell and was doing just fine. I abandoned it because I'm lazy, not because of FP :P
chriswarbo 11y 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.: Time | RAM ------+-------------------------------- 0 | foo 1 | bar 2 | baz . . . The author is using the term immutable to mean never replacing the contents of a memory location, so in their view this is immutability: Time | RAM 1 | RAM 2 | RAM 3 | ------+-------+-------+-------+--... 0 | foo | | | 1 | foo | bar | | 2 | foo | bar | baz | . . . . . . . . . . . . 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: Time | "state" var ------+------------- 0 | foo 1 | bar 2 | baz . . . The "immutable" version: Time | "state" var 0 | "state" var 1 | "state" var 2 | ------+---------------+---------------+---------------+--... 0 | foo | | | 1 | foo | bar | | 2 | foo | bar | baz | . . . . . . . . . . . . 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: | | _--. ____ Price | / \ / \ |__/ \__; \__/ | +----------------------------------- Time ^ | Now 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: Time | Scope | Current "state" ------+-------+----------------- 0 | 0 | foo 1 | 0 | bar 2 | 0 | baz . . . . . . Immutable version: 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 | . . . . . . . . . . . . . . . . . . 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.
DanielBMarkham 11y 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 updateTheWorld I 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.
kordless 11y ago
Not one mention of the blockchain in the story or here. How interesting.
theseoafs 11y 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.
leshow 11y ago
reminds me of Elm's Effects system. great article.
yason 11y ago
var newState = drawManuel( drawBackground( processInput(state))); 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.
jw- 11y ago
The problem doesn't really have anything to do with immutability; the problem is dependency and composition. E.g. f :: A -> B g :: B -> C will 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".
lliamander 11y 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]http://prog21.dadgum.com/189.html http://prog21.dadgum.com/189.html [1]https://awelonblue.wordpress.com/2012/01/12/defining-declarative/ https://awelonblue.wordpress.com/2012/01/12/defining-declara...
tome 11y 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).
sesquipedalian 11y 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.

271 points by r4um 11y 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] https://wiki.haskell.org/Operational https://wiki.haskell.org/Operational [2] http://debug.elm-lang.org/ http://debug.elm-lang.org/

victorNicollet 11y 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: draw : cleanState -> unit handleCollisions : dirtyState -> cleanState processInput : cleanState -> dirtyState 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.

shiro 11y ago
I think the uber point of the article is that, even with the help of types, you cannot design the whole type structures until you know the entire picture. Suppose you throw some autonomous to your character (e.g. pathPlanning, preprogrammed behavior, subcomponents moving autonomously otherwise interfering other objects or user input, etc.) then there are many types of state, and you'll design what operation gets which type of state and returns which type of state, and that's essentially the same as how you design with chaining State -> State functions or working with imperative procedures. Sure, types will keep you away from shooting yourself---once you design the whole type chain the compiler will detect if you swap or drop operations inadvertently. But during the stage of your designing the type structure itself, the issue described in the article still exists.
- victorNicollet 11y ago
  My point is that you don't have to design the whole type chain ahead of time, you can discover new type constraints as you go and apply them straight away (in the same way that you don't have to wait until you finish your design to start writing unit tests). Maybe an experienced game programmer would notice straight away that it could be a problem to draw a state that has not undergone collision detection, and design this state constraint into the game straight away (as a type, as an assert, etc.) and maybe another programmer wouldn't notice this requirement until they ran the game and noticed something odd (or someone from QA notified them) and had to dig through the system to find the underlying reason. But once they shot themselves in the foot once, it makes sense to implement _something_ to detect when they make the same mistake again.
  - shiro 11y ago
    During the design stage, you do need working components, independently implemented, and experiment various combinations. If you use types, that means frequently rewriting types to match the reorganizations of control flow. Types still help to prevent mistakes, but the main part of actual design process (like working on clay, or, scrap & rebuild with Lego pieces) is just as tedious as other ways. I read that the original article is trying to address that problem.
- dllthomas 11y ago
  "even with the help of types, you cannot design the whole type structures until you know the entire picture" Sure you can. And like your design of anything else without knowing the entire picture, some bits of it will be wrong. A good type-checker - especially with inference - helps you find where you'll have inconsistencies in the assumptions you've made (usually before you've coded all the way to them), will give you a sense of the form of those inconsistencies, and when you change the types will point you at the code that needs to change in tandem.
  - shiro 11y ago
    I write a bit of Haskell in small projects but my background is largely Lisp/Scheme (the mud ball approach). I do admire hard-core Haskellers who seem "thinking in types". I wonder if there are good articles that tell how type-based approach helped dynamic development (meaning, lots of trial-and-errors, and rapidly changing spec, involving many components developed simultaneously by different programmers). I assume you can encode implicit constraints in types, for example (suppose components form DG, you might encode dependencies to ensure restructuring graphs always satisfy them). Just like to see how it works in real life development.
ajuc 11y ago
Now let's say you want collision with one special item change the way inputs are interpretted (you iterate on the game rules and someone had an idea to add alcohol that reverses the controls). This very detailed specification of dependencies in applications make it hard to change them quickly, and gamedev is mostly about how quickly you can iterate to make the game fun. I would love a hybrid system, where you get a "root" object passed to each function, that keeps the whole state, and you can just do side effects on that, but you are required by convention to always reference the members of that root object by full path. And then when you're finished you run a macro, and it generates nice elegant minimaly coupled functional code that passes only the required stuff around. Don't know if that's possible but it would be great.
- zdkl 11y ago
  This with lisp syntax, compiling to Rust code & datastructures would be fun!
  - ajuc 11y ago
    I was thinking of a system generating code in the same language, and still keeping the root object, so that you can experiment, add some new dependencies, and regenerate dependenceis, many times. But you can at any moment pass null from the main loop instead of the proper root object to see if the code is generated properly and works only with the functional part. It's more complicated than a system that just regenerates everything from scratch every time. And removing dependencies would be tricky. So maybe your idea is better.
    - zdkl 11y ago
      Well you could precompile part of the guaranteed immutable stuff and distribute it seperately from the mutable execution part... Wait we've reinvented the JVM at this point!
    - zdkl 11y ago
      Come to think of it you should take a look at clojure/script, the pattern you describe could easily be implemented with maps in atoms. Cf the 'reagent' libs way of handling state

akkartik 11y ago

Great article, feeds all my prejudices. For example, I'm tempted to link to it in http://akkartik.name/post/modularity http://akkartik.name/post/modularity 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."

mbrock 11y ago
That's why Haskell programmers, for example, try to represent state in clear ways. The basic mathematical model of functions and values turns out to be able to represent state in several ways: the "monadic" way of composing state transforming functions; the "functional-reactive programming" way of modelling signals and events (which offers interesting solutions to the OP's game problems); various "interpreter" patterns; and so on. I point this out just because there's a widespread misunderstanding that pure functional programming is somehow opposed to modelling state. It's definitely not. It just involves building state models on the coherent basis of functions and values. Put simply, in Haskell, when your problem requires state, you can just use the "State" type, just like when you require I/O, you use the "IO" type.
- idanoeman 11y ago
  Absolutely. In "The Awkward Squad," SPJ says "Haskell is the finest imperative programming language in the world," not entirely tongue-in-cheek. :)
dkersten 11y ago
Immutable state, functional programming, etc, is not about eliminating state, its about isolating it and carefully managing it. In a standard-imperative-mutable world, you can never be completely sure that state isn't being modified behind your back, you can never be completely sure that concurrent access is safe, you can never be completely sure how far reaching state changes you make are. The idea, IMHO, isn't to remove state. All programs need state. All interesting programs need state that changes over time. The "big idea" is that these changes are isolated and managed carefully so that nobody can pull the rug out from under you and change something behind your back or in a way that makes concurrent access unsafe. Immutable data means that the data you are reading will never change. If you read it again in ten minutes, it will still give you the same value. No other module or thread can change it. Concurrent access is safe too and all reads give the same consistent view. But even immutable data needs to be updated, so there will always be some mutable state (for example, in Clojure, you might have one or more atoms, which are mutable cells into which you can put immutable data. The data doesn't mutate -- it gets replaced[0]. Only the cell is mutated, but in a carefully managed way. There are other mutable state management primitives too). The programmer cannot accidentally mess up the state, they have to intentionally do it. So to reiterate: its not about eliminating all mutable state, its about isolating and carefully managing it. [0] and anyone still holding a reference to the data (not the atom) will continue to see the same data as before, unchanged. That is, if I take the value from the atom, somebody else updating the atom will not change the value I took out of it. This of course introduces things like the dual-writes problem, but Clojure gives me other tools (like refs with STM) to tackle these: ie atoms aren't the right tool for all use cases, just one example I chose.

wodenokoto 11y 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.

ktRolster 11y ago
Well, immutability is something that can help you in non-functional programming languages too: even C has const. It doesn't solve every problem, but it reduces the cognitive load.
- RyanZAG 11y ago
  > but it reduces the cognitive load. No. It can reduce the cognitive load if applied in the correct place. It can just as easily increase the cognitive load if applied in the wrong place. Immutability should be used with care, not used always.
  - fnordsensei 11y ago
    I would contend that it's exactly the opposite; mutability should be used with care, not used always.
    - louthy 11y ago
      Totally agree. Mutability adds significant cognitive difficulty that just goes away with immutable structures. Here's a great talk by Rich Hickey on the subject. http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hic...
      - kkoomi 11y ago
        I'm watching this now and just wanted to say thanks for the great link!

ktRolster 11y ago

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

pron 11y ago
Moreover, the following theorem is easily proved: there cannot exist a useful general-purpose programming language in which all (or even most) programs can be efficiently verified to be correct, either by man or machine[1]. Where "useful general-purpose" means any language with forward branching and some form of looping recursion (even if bounded) -- it does not need to be Turing complete -- and "efficient" means done in time polynomial in the size of the program. [1]: ... unless PSPACE = P, in which case some small class of languages that are not quite general purpose but useful nonetheless may have this property, because verifying useful finite-state machine languages is PSPACE-complete.
- pron 11y ago
  For those interested, the proof for the Turing-complete and nearly-TC (as in total functional programming) cases is the same as the proof of the time hierarchy theorems[1], and for finite-state-machines the proof is based on results showing that verification of a (concise program expressing) finite state machine is PSPACE-complete. Those results are not surprising, as it is easy to see how any problem in computer science can be reduced (efficiently) to verification, so being able to efficiently prove correctness of a language capable of describing algorithms with super-polynomial complexity (this, BTW, only requires the ability to loop/recurse to depth 2) would mean contradiction. [1]: https://en.wikipedia.org/wiki/Time_hierarchy_theorem https://en.wikipedia.org/wiki/Time_hierarchy_theorem

deleted 11y ago

[deleted]

RichieAHB 11y 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.

kristiandupont 11y ago
My typical analogy is this: mutable state is to software as movable parts are to hardware. There are a group of problems that cannot be solved without it, but introducing it makes everything a bit more fragile.

dschiptsov 11y 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.

marcosdumay 11y ago
> A strict language with optional lazynes could use ordinary type-tags. And then you'll have a total order, that makes your code hard to parallelize. But more important, it mixes state updating (that can be actually done in several orders, can be rewinded, and has several other interesting properties) with IO, with list mapping, with exception handling, and everything else.

fnordsensei 11y 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.

jorams 11y 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.

coldtea 11y ago
>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.* Only the latter (that the order that pure functions are applied doesn't matter) has been touted forever as a benefit of functional programming, and what supposedly makes it "trivially parallelizable".
- simoncion 11y ago
  > Only the latter (that the order where pure functions are applied doesn't matter) has been touted forever as a benefit of functional programming, and what supposedly makes it "trivially parallelizable". Functions that return the same values when given the same arguments are substantially easier to reason about than functions that return values that depend on both the arguments passed in and some state somewhere else in the system. Additionally, functions that don't modify their arguments are relatively easy to parallelize. (Due in part to the fact that it's really easy to figure out locking in a share-nothing system.) Anyway. I'm no scholar, but I'm pretty sure that no knowledgable FP proponent has ever seriously said "FP lets you call your pure functions in any order whatsoever and get the same end result, every time.". Perhaps I'm misunderstanding your statement?
  - the_af 11y ago
    Especially since shuffling the order functions get called often means they do NOT get called with the same arguments. This is important!
- 11y ago

_pmf_ 11y 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.

the_af 11y ago
FP is all about embracing state as a first class element and reducing accidental state. I hope nobody claims otherwise :) The confusion is that people sometimes say "state" when they mean "mutable shared state".

susi22 11y 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.

Chris_Newton 11y ago
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. I agree up to a point, but I think off-the-shelf rule engines will only ever get us so far. Front-end web development in recent years has been going through its “Visual Basic phase”. We’ve been developing tools to help automate basic UI interactions and communications between front- and back-end. Those often get the job done better than the more manual techniques we used to use, but mostly they work best with simple presentation like forms or charts, and with simple data models and limited relationships — in other words, the kind of thing you need for a simple CRUD app UI where the tricky issues like scalability are handled on the back-end, like a lot of the web apps being developed today. However, you didn’t see a many people trying to build more demanding UIs in Visual Basic, things like CAD applications or DTP software or flight simulator games or tools for visualising and exploring tricky data sets. I agree that to build more sophisticated web apps, the front-end world is going to need to broaden its horizons. Tools that let you systematically represent large numbers of rules without hand-crafting a custom function for every one of them will surely be necessary in some cases. As with so much of web development, lot of lessons learned some time ago in other programming fields will be relearned by a new group of developers. However, that’s all still relatively easy. The hard part is how you reconcile the effects of those rules when they conflict, and there aren’t any universal right answers to that one. In fact, often there aren’t any good answers at all that can be fully automated. That can create a whole new world of nasty, awkward interactions where users have to actively deal with those conflicts. Maybe even that isn’t going to be scalable or efficient enough, and you have to design the entire system to operate with only incomplete or potentially incorrect information and still have acceptable if not always ideal behaviour. There are lots of interesting problems at this level, but a basic rule engine is never going to solve them alone.

riprowan 11y 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.

jon-wood 11y ago
Its less a case of them occupying the same space, and more one of each object running its movement code and stating where it would like to be in the next frame. Collision detection then takes place, finds that two objects want to share the same position, and notifies the object of that fact so that it can compensate. That compensation might take the form of changing velocity, blowing into a hundred pieces, or just outright ignoring the fact and carrying on.
- riprowan 11y ago
  But in the example, the character in the game actually is moved to the invalid location, then the test is run for invalidity. Not sure why I'm downvoted, this seemed like a reasonable objection to me. Like I said I'm not a game dev.
Kiro 11y ago
Can someone explain why I cannot just check for collision before moving the character?
- catmanjan 11y ago
  If the character moves faster than the space between him and the block, he will not be able to stand flush with the block - this can be fixed on other ways though.
- tome 11y ago
  You can. It's called collision detection!
GFK_of_xmaspast 11y ago

Kiro 11y ago

> However, we still don’t know what they do with the state. Do they modify it, or do they only read it? var newState = drawManuel( drawBackground( processInput(state))); 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: var newState = processInput(state); drawBackground(newState); drawManuel(newState);

zby 11y ago

Can anyone explain why it is: var newState = drawManuel( drawBackground( processInput(state))); and not: var newState = processInput(state); drawManuel(newState); drawBackground(newState); 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: var newState = handleCollisions(state) newState = processInput(newState) drawBackground(newState) drawManuel(newState) 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.

dkersten 11y ago
Indeed. If the state is immutable, then drawing (which shouldn't modify the state) can be, conceptually, done in parallel. While in practice this is unlikely to actually happen, your code snippet reflects this conceptual property better and is therefore, in my opinion, much easier to read: I know where the state is modified and where it is merely read. I also know that drawManuel cannot mess with drawBackgrounds data and vice-versa.
- ajuc 11y ago
  It's not only conceptual difference. It is a good practice to decouple state manipulation from drawing (even to do drawing in different thread, and with different frequency, than state manipulation). This allows for computers with wastly different processing power to run the same simulation in sync, while the more powerful computer can draw 10 times as many intermediate frames. Alternatives are variable step length (makes it hard to write deterministic simulation), or fixed step length and capping framerate to it (sacrifices animation quality on better computers for easy implementation). EDIT: also - the ordering between drawManuel and drawBackground probably do matter, and there's probably some state related to drawing (like animation frame numbers etc) so there should be separate screenState that reflects that. state = processInput(state); screenState = drawBackground(state, screenState); screenState = drawManuel(state, screenState);

raspasov 11y ago

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

retrogradeorbit 11y ago
Here's a complete web game a mate and I did for global game jam this year in less than 24 hours from scratch using ClojureScript and core.async targeting pixi.js. https://github.com/retrogradeorbit/moonhenge https://github.com/retrogradeorbit/moonhenge It even has multiple weapons, enemy waves and an end sequence if you complete the game! The code is not as clean as it could be. For instance it has many more atoms than it needs and lots of code that could be simplified and re-factored. But time was extremely tight and it was a massive rush job. But even so in the end it came together seamlessly with no weird bugs or crashes of any kinds and it is rock solid. I attribute this to the immutable data structures and pure functions used. I've done games before using mutable OOP and in my experience they never come together this easily or with so few bugs.
- raspasov 11y ago
  This is awesome - great job! : )

jasonkester 11y 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 style He 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.

zby 11y ago
My theory is that he thinks that variables are an imperative language feature - so he tries to avoid using them to make it all functional. He is partially right - variables are imperative. What he does not know is that he can use his variables in a way that directly translates into purely functional 'value binding' and leave them readable.
- brlewis 11y ago
  I wish they would still use Scheme in intro computer science. It's so obvious in that language what is and isn't pure functional.
  - rubidium 11y ago
    They still do at some universities. https://www.rose-hulman.edu/Users/faculty/young/CS-Classes/csse304/syllabus.html https://www.rose-hulman.edu/Users/faculty/young/CS-Classes/c...
  - DanFeldman 11y ago
    We use it at Berkeley for the first CS class, CS61a. The final project is writing a scheme interpreter in python!
11y ago

hellofunk 11y ago

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

hathym 11y ago

sounds like a solution looking for a problem.

cousin_it 11y 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.

Illniyar 11y ago
I really like your sentiment, but I'm not sure if "OO was invented for X" or "FP was invented for Y" is right. They are abstract paradigms that were created with very little connection to their underling usage at the time (FP in particular stems from a mathematical background, but most of OO as well). Rather I would say more then "OO is more suitable for GUI" and "FP is more suitable for compilers" (though I'm not sure if I agree with that)
- deleted 11y ago
  [deleted]
_asummers 11y ago
I'm not convinced GUIs can't be built with functional programming techniques. My GUIs (in Android and more recently with React) generally tend to follow a unidirectional data flow, where the view building is really a dumb passthrough of massaged data that's stored in a local DB (like SQLite). The view state could be represented ENTIRELY by a JSON object, e.g. and since it's all stored locally, it's replayable if something goes wrong.
- creshal 11y ago
  Configuring and assembling a GUI out of an existing GUI framework, and writing that framework in the first place, are two different use cases IMO. OOP works a lot better for the latter case.
the_af 11y ago
This isn't true about games; FP isn't a bad fit for them. Games can be written in FP, and there are some interesting things you can do with it, it's just that it's obviously less explored and more "researchy". See: - Nikki and the Robots (Haskell): https://github.com/nikki-and-the-robots/nikki https://github.com/nikki-and-the-robots/nikki - Frag, a simple 3D shooter (Haskell): https://wiki.haskell.org/Frag https://wiki.haskell.org/Frag - Clean Game Library, using Clean, an FP language with a different philosophy from Haskell's: http://cleangl.sourceforge.net/ http://cleangl.sourceforge.net/ - For my (abandoned :( ) master's thesis, I was also writing a platformer in Haskell and was doing just fine. I abandoned it because I'm lazy, not because of FP :P

chriswarbo 11y 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.: Time | RAM ------+-------------------------------- 0 | foo 1 | bar 2 | baz . . . The author is using the term immutable to mean never replacing the contents of a memory location, so in their view this is immutability: Time | RAM 1 | RAM 2 | RAM 3 | ------+-------+-------+-------+--... 0 | foo | | | 1 | foo | bar | | 2 | foo | bar | baz | . . . . . . . . . . . . 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: Time | "state" var ------+------------- 0 | foo 1 | bar 2 | baz . . . The "immutable" version: Time | "state" var 0 | "state" var 1 | "state" var 2 | ------+---------------+---------------+---------------+--... 0 | foo | | | 1 | foo | bar | | 2 | foo | bar | baz | . . . . . . . . . . . . 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: | | _--. ____ Price | / \ / \ |__/ \__; \__/ | +----------------------------------- Time ^ | Now 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: Time | Scope | Current "state" ------+-------+----------------- 0 | 0 | foo 1 | 0 | bar 2 | 0 | baz . . . . . . Immutable version: 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 | . . . . . . . . . . . . . . . . . . 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.

DanielBMarkham 11y 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 updateTheWorld I 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.

kordless 11y ago

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

theseoafs 11y 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.

leshow 11y ago

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

yason 11y ago

var newState = drawManuel( drawBackground( processInput(state))); 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.

jw- 11y ago

The problem doesn't really have anything to do with immutability; the problem is dependency and composition. E.g. f :: A -> B g :: B -> C will 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".

lliamander 11y 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]http://prog21.dadgum.com/189.html http://prog21.dadgum.com/189.html [1]https://awelonblue.wordpress.com/2012/01/12/defining-declarative/ https://awelonblue.wordpress.com/2012/01/12/defining-declara...

tome 11y 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).

sesquipedalian 11y 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.