20

FP proponents have claimed that concurrency is easy because their paradigm avoids mutable state. I don't get it.

Imagine we're creating a multiplayer dungeon crawl (a roguelike) using FP where we emphasize pure functions and immutable data structures. We generate a dungeon composed of rooms, corridors, heroes, monsters and loot. Our world is effectively an object graph of structures and their relationships. As things change our representation of the world is amended to reflect those changes. Our hero kills a rat, picks up a shortsword, etc.

To me the world (current reality) carries this idea of state and I'm missing how FP overcomes this. As our hero takes action, functions amend the state of the world. It appears to be every decision (AI or human) needs to be based on the state of the world as it is in the present. Where would we allow for concurrency? We can't have multiple processes concurrently ammending the state of the world lest one process base its outcomes on some expired state. It feels to me that all control should occur within a single control loop so that we're always processing the present state represented by our current object graph of the world.

Clearly there are situations perfectly suited for concurrency (i.e. When processing isolated tasks whose states are independent of one another).

I'm failing to see how concurrency is useful in my example and that may be the issue. I may be misrepresenting the claim somehow.

Can someone better represent this claim?

  • 1
    You're referring to shared state; shared state will always be what it is and will always require some form of synchronization, the oft preferred form among pure FP people is STM which allows you to treat shared memory as local memory by having an abstraction layer over it that makes access transactional so race conditions are handled automatically. Another technique for shared memory is message passing where instead of having shared memory, you have local memory and knowledge of other actors to ask for their local memory – Jimmy Hoffa Apr 22 '13 at 14:24
  • 1
    So... you're asking how shared-state concurrency being easy helps manage state in a single-threaded application? On the other hand, your example clearly lends itself to concurrency conceptually (a thread for each AI-controlled entity) whether or not it's implemented that way. I'm confused what you're asking here. – C. A. McCann Apr 22 '13 at 14:54
  • 1
    in a word, Zippers – jk. Apr 22 '13 at 15:06
  • 2
    Every object would have their own view of the world. There will be eventual consistency. It's probably also how things work in our "real world" with the wave function collapse. – herzmeister Apr 22 '13 at 15:57
  • 1
    You may find "purely functional retrogames" interesting: prog21.dadgum.com/23.html – user802500 May 3 '13 at 20:42
15

I'll try to hint on the answer. This is not an answer, only an introductory illustration. @jk's answer points to the real thing, zippers.

Imagine you have an immutable tree structure. You want to alter one node by inserting a child. As a result, you get a whole new tree.

But most of the new tree is exactly the same as old tree. A clever implementation would reuse most of the tree fragments, routing pointers around the altered node:

From Wikipedia

Okasaki's book is full of examples like this.

So I suppose you could reasonably alter small parts of your game world each move (pick up a coin), and only actually change small parts of your world data structure (the cell where the coin was picked up). Parts that only belong to past states will be garbage-collected in time.

This probably takes some consideration in designing the data game world structure in an appropriate way. Unfortunately, I'm no expert in these matters. Definitely it must be something else than a NxM matrix one would use as a mutable data structure. Probably it should consist of smaller pieces (corridors? individual cells?) that point to each other, as tree nodes do.

  • 3
    +1: For pointing at Okasaki's book. I haven't read it but it is on my to do list. I think what you depicted is the correct solution. As an alternative, you can consider uniqueness types (Clean, en.wikipedia.org/wiki/Uniqueness_type): using this kind of types you can destructively update data objects while retaining referential transparency. – Giorgio Apr 22 '13 at 15:16
  • Is there a benefit for relationships to be defined via indirect reference via keys or ids? That is, I was thinking that fewer actual touches of one structure to another would necessitate fewer amendments to the world structure when a change occurs. Or is this technique not really used in FP? – Mario T. Lanza Apr 22 '13 at 16:16
9

9000's answer is half the answer, persistent data structures allow you to reuse unchanged parts.

You may already be thinking however "hey what if I want to change the root of the tree?" as it stands with the example given that now means changing all the nodes. This is where Zippers come to the rescue. They allow element at a focus to be changed in O(1), and the focus can be moved anywhere in the structure.

The other point with zippers is that a Zipper exists for pretty much any data type you want

  • I'm afraid it will take me some time to dig into "zippers" since I'm on the fringe any only exploring FP. I have no experience with Haskell. – Mario T. Lanza Apr 22 '13 at 16:14
  • I'll try to add an example later today – jk. Apr 22 '13 at 16:21
4

Functional style programs create lots of opportunities like that to use concurrency. Anytime you transform or filter or aggregate a collection, and everything is pure or immutable, there's an opportunity for the operation to be sped up by concurrency.

For example, suppose you perform AI decisions independently of each other and in no particular order. They don't take turns, they all make a decision simultaneously and then the world advances. The code might look like this:

func MakeMonsterDecision curWorldState monster =
    ...
    ...
    return monsterDecision

func NextWorldState curWorldState =
    ...
    let monsterMakeDecisionForCurrentState = MakeMonsterDecision curWorldState
    let monsterDecisions = List.map monsterMakeDecisionForCurrentState activeMonsters
    ...
    return newWorldState

You have a function to compute what a monster will do given a world state, and apply it to every monster as part of computing the next world state. This is a natural thing to do in a functional language, and the compiler is free to perform the 'apply it to every monster' step in parallel.

In an imperative language you'd be more likely to iterate over every monster, applying their effects to the world. It's just easier to do it that way, because you don't want to deal with cloning or complicated aliasing. The compiler can't perform the monster computations in parallel in that case, because early monster decisions affect later monster decisions.

  • That helps quite a bit. I can see how in a game there would be great benefit to having monsters concurrently deciding what they'll do next. – Mario T. Lanza Apr 21 '14 at 17:07
4

Listening to a few Rich Hickey talks -- this one in particular -- alleviated my confusion. In one he indicated that it is okay that concurrent processes may not have the most current state. I needed to hear that. What I was having trouble digesting was that programs would actually be okay with basing decisions on snapshots of the world that have since been superseded by newer ones. I kept wondering how concurrent FP got around the issue of basing decisions on old state.

In a banking application we would never want to base a decision on a snapshot of state that has since been superseded by a newer one (a withdrawal occurred).

That concurrency is easy because the FP paradigm avoids mutable state is a technical claim that doesn't attempt to say anything about the logical merits of basing decisions on potentially old state. FP still ultimately models state change. There's no getting around this.

0

FP proponents have claimed that concurrency is easy because their paradigm avoids mutable state. I don't get it.

I wanted to pitch in about this general question as someone who is a functional neophyte but has been up to my eyeballs in side effects over the years and would like to mitigate them, for all kinds of reasons, including easier (or specifically "safer, less error-prone") concurrency. When I glance over at my functional peers and what they're doing, the grass seems a bit greener and smells nicer, at least in this regard.

Serial Algorithms

That said, about your specific example, if your problem is serial in nature and B cannot be executed until A is finished, conceptually you can't run A and B in parallel no matter what. You have to find a way to break the order dependency like in your answer based on making parallel moves using old game state, or use a data structure which allows parts of it to be independently modified to eliminate the order dependency as proposed in the other answers, or something of this sort. But there are definitely a share of conceptual design problems like this where you can't necessarily just multithread everything so easily because things are immutable. Some things are just going to be serial in nature until you find some smart way to break the order dependency, if that's even possible.

Easier Concurrency

That said, there are many cases where we fail to parallelize programs that involve side effects in places that could potentially significantly improve performance simply because of the possibility that it might not be thread-safe. One of the cases where eliminating the mutable state (or more specifically, external side effects) helps a lot as I see it is that it turns "may or may not be thread-safe" into "definitely thread-safe".

To make that statement a bit more concrete, consider that I give you a task to implement a sorting function in C which accepts a comparator and uses that to sort an array of elements. It's meant to be quite generalized but I'll give you an easy assumption that it will be used against inputs of such a scale (millions of elements or more) that it will doubtlessly be beneficial to always use a multithreaded implementation. Can you multithread your sorting function?

The problem is that you cannot because the comparators your sorting function calls may cause side effects unless you know how they are implemented (or at the very least documented) for all possible cases which is kind of impossible without degeneralizing the function. A comparator could do something disgusting like modify a global variable inside in a non-atomic way. 99.9999% of comparators may not do this, but we still can't multithread this generalized function simply because of the 0.00001% of cases that might cause side effects. As a result you might have to offer both a single-threaded and multithreaded sort function and pass the responsibility to the programmers using it to decide which one to use based on thread safety. And people might still use the single-threaded version and miss opportunities to multithread because they might also be unsure whether the comparator is thread-safe, or whether it will always remain as such in the future.

There's a whole lot of brainpower that can be involved in just rationalizing about the thread safety of things without throwing locks everywhere which can go away if we just had hard guarantees that functions won't cause side effects for now and the future. And there's fear: practical fear, because anyone who has had to debug a race condition a few too many times would probably be hesitant about multithreading anything that they can't be 110% sure is thread-safe and will remain as such. Even for the most paranoid (of which I am probably at least borderline), the pure function provides that sense of relief and confidence that we can safely call it in parallel.

And that's one of the main cases where I see it as so beneficial if you can get a hard guarantee that such functions are thread-safe which you get with pure functional languages. The other is that functional languages often promote creating functions free of side effects in the first place. For example, they might provide you with persistent data structures where it's reasonably quite efficient to input a massive data structure and then output a brand new one with only a small part of it changed from the original without touching the original. Those working without such data structures might want to modify them directly and lose some thread safety along the way.

Side Effects

That said, I disagree with one part with all due respect to my functional friends (who I think are super cool):

[...] because their paradigm avoids mutable state.

It's not necessarily immutability that makes concurrency so practical as I see it. It's functions that avoid causing side effects. If a function inputs an array to sort, copies it, and then mutates the copy to sort its contents and outputs the copy, it's still just as thread-safe as one working with some immutable array type even if you're passing the same input array to it from multiple threads. So I think there's still a place for mutable types in creating very concurrency-friendly code, so to speak, though there are a lot of additional benefits to immutable types, including persistent data structures which I use not so much for their immutable properties but to eliminate the expense of having to deep copy everything in order to create functions free of side effects.

And there's often overhead to making functions free of side effects in the form of shuffling and copying some additional data, maybe an extra level of indirection, and possibly some GC on parts of a persistent data structure, but I look at one my buddies who has a 32-core machine and I'm thinking the exchange is probably worth it if we can more confidently do more things in parallel.

  • 1
    "Mutable state" is always meant to mean state at the application level, not the procedure level. Eliminating pointers and passing parameters as copy values is one of the techniques baked into FP. But any useful function has to mutate state at some level - the point of functional programming is to ensure that mutable state which belongs to the caller doesn't enter the procedure, and mutations don't exit the procedure except by the return values! But there are few programs that can do much work without mutating state at all, and the errors always creep in again at the interface. – Steve Jan 30 '18 at 14:52
  • 1
    To be honest, most modern languages permit a functional style of programming to be used (with a bit of discipline), and of course there are languages dedicated to functional patterns. But it is a less computationally efficient pattern, and is popularly over-hyped as a solution to all ills much as object orientation was in the 90s. Most programs are not bound by CPU-intensive computations that would benefit from parallelisation, and of those that are, it is often because of the difficulty of reasoning about, designing, and implementing the program in a manner amenable to parallel execution. – Steve Jan 30 '18 at 16:35
  • 1
    Most programs that deal with mutable state, do so because they have to for one reason or another. And most programs are not incorrect because they use shared state or update it anomalously - it is usually because they receive unexpected garbage as input (which determines a garbage output), or because they operate wrongly on their inputs (wrongly in the sense of the purpose to be achieved). Functional patterns do little to address this. – Steve Jan 30 '18 at 16:36
  • 1
    @Steve I might at least halfway agree with you since I'm on that side of just exploring ways to do things in a more thread-safe way from languages like C or C++, and I don't really think we need to go full-blown pure functional to do it. But I find some of the concepts in FP useful at least. I just ended up writing an answer on how I find PDS useful here, and the biggest benefit I find about PDS is actually not thread-safety, but things like instancing, non-destructive editing, exception safety, simple undos, etc: – user204677 Jan 30 '18 at 17:31
  • 1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.