How does functional programming handle the situation where the same object is referenced from multiple places?

Question

I am reading and hearing that people (also on this site) routinely praise the functional programming paradigm, emphasising how good it is to have everything immutable. Notably, people propose this approach even in traditionally imperative OO languages, like C#, Java or C++, not only in purely functional languages like Haskell that force this on the programmer.

I find it hard to understand, because I find mutability and side-effects... convenient. However, given how people currently condemn side effects and consider it a good practice to get rid of them wherever possible, I believe that if I want to be a competent programmer I have to start my jorney towards some better understanding of the paradigm... Hence my Q.

One place when I find problems with the functional paradigm is when an object is naturally referenced from multiple places. Let me describe it on two examples.

The first example will be my C# game I'm trying to make in my spare time. It's turn-based web game where both players have teams of 4 monsters and can send a monster from their team to the battlefield, where it will face the monster sent by the opposing player. Players can also recall monsters from the battlefield and replace them with another monster from their team (similarily to Pokemon).

In this setting, a single monster can be naturally referenced from at least 2 places: a player's team and the battlefield, which references two "active" monsters.

Now let's consider the situation when one monster is hit and looses 20 health points. Within the brackets of the imperative paradigm I modify this monster's health field to reflect this change - and this is what I'm doing now. However, this makes the Monster class mutable and the related functions (methods) impure, which I guess is considered a bad practice as of now.

Even though I gave myself the permission to have the code of this game in a lesser-than-ideal state in order to have any hopes of actually finishing it at some point of the future, I would like to know and understand how should it be written properly. Therefore: If this is a design flaw, how to fix it?

In the functional style, as I understand it, I'd instead make a copy of this Monster object, keeping it identical to the old one except for this one field; and the method suffer_hit would return this new object instead of modifying the old one in place. Then I'd likewise copy the Battlefield object, keeping all its fields the same except for this monster.

This comes with at least 2 difficulties:

1. The hierarchy can easily be much deeper than this simplified example of just Battlefield -> Monster. I'd have to do such copying of all fields except one and returning a new object all the way up this hierarchy. This would be boilerplate code which I find annoying especially since functional programming is supposed to reduce boilerplate.
2. A much more severe problem, however, is that this would lead to the data being out of sync. The field's active monster would see its health reduced; however, this same monster, referenced from its controlling player Team, would not. If I instead embraced the imperative style, every modification of data would be instantly visible from all other places of code and in such cases like this one I find it really convenient - but the way I'm getting things this is precisely what people say is wrong with the imperative style!
   • Now it would be possible to take care of this issue by taking a journey to the Team after each attack. This is extra work. However, what if a monster can suddenly be later referenced from even more places? What if I come with an ability that, for example, lets a monster focus on another monster that is not necessarily on the field (I'm actually considering such an ability)? Will I surely remember to take also a journey to focused monsters immediatelly after each attack? This seems to be a time bomb that will explode as the code gets more complex, so I think it is a no solution.

An idea for a better solution comes from my second example, when I hit the same problem. In the academia we were told to write an interpreter of a language of our own design in Haskell. (This is also how I was forced to start understanding what FP is). The problem showed up when I was implementing closures. Once again the same scope could now be referenced from multiple places: Through the variable that holds this scope and as the parent scope of any nested scopes! Obviously, if a change is made to this scope via any of the references pointing to it, this change must also be visible through all other references.

The solution I came with was to assign each scope an ID and hold a central dictionary of all scopes in the State monad. Now variables would only hold the ID of the scope they were bound to, rather than the scope itself, and nested scopes would also hold the ID of their parent scope.

I guess the same approach could be attempted in my monster battling game... Fields and teams do not reference monsters; they instead hold IDs of monsters that are saved in a central monster dictionary.

However, I can once again see a problem with this approach that prevent me from accepting it without hesistation as the solution to the issue:

It once again is a source of boilerplate code. It makes one-liners necessarily 3-liners: what previously was a one-line in-place modification of a single field now requires (a) Retrieving the object from the central dictionary (b) Making the change (c) Saving the new object to the central dictionary. Also, holding ids of objects and central dictionaries instead of having references increases complexity. Since FP is advertised to reduce complexity and boilerplate code, this hints I'm doing it wrong.

_{I was also going to write about asecond problem that seems much more severe: This approach introduces memory leaks. Objects that are unreachable will normally be garbage collected. However, objects held in a central dictionary cannot be garbage collected, even if no reachable object references this particular ID. And while theoretically careful programming can avoid memory leaks (we could take care to manually remove each object from the central dictionary once it is no longer needed), this is error prone and FP is advertised to increase the correctness of programs so once again this may not be the correct way.}

_{However, I found out in time that it rather seems to be a solved problem. Java provides WeakHashMap that could be used to solve this issue. C# provides a similar facility - ConditionalWeakTable - although according to the docs it is meant to be used by compilers. And in Haskell we have System.Mem.Weak.}

Is storing such dictionaries the correct functional solution to this problem or is there a simpler one that I'm failing to see? I imagine that the number of such dictionaries can easily grow and badly; so if these dictionares are supposed to also be immutable this can mean a lot of parameter-passing or, in languages that support that, monadic computations, since the dictionaries would be held in monads (but once again I'm reading that in purely functional languages as little code as possible should be monadic, while this dictionary solution would place almost all code inside of the State monad; which once again makes me doubt if this is the correct solution.)

After some consideration I think I'd add one more question: What are we gaining via constructing such dictionaries? That what's wrong with imperative programming is, according to many experts, that changes in some objects propagate to other pieces of code. To solve this issue objects are supposed to be immutable - precisely for this reason, if I understand correctly, that changes made to them should not be visible elsewhere. But now I'm concerned about other pieces of code operating on out-of-date data so I invent central dictionaries so that... once again changes in some pieces of code propagate to other pieces of code! Aren't we, therefore, back to the imperative style with all of its supposed drawbacks, but with added complexity?

Answer 1

How does Functional Programming handle an object referenced from multiple places? It invites you to revisit your model!

To explain... let's look at how networked games are sometimes written - with a central "golden source" copy of the game state, and a set of incoming client events that update that state, and then get broadcast back out to the other clients.

You can read about the fun that the Factorio team had with getting this to behave well in some situations; here's a short overview of their model:

The basic way that our multiplayer works is that all clients simulate the game state and they only receive and send the player input (called Input Actions). The server's main responsibility is proxying Input Actions and making sure all clients execute the same actions in the same tick.

Since the server needs to arbitrate when actions are executed, a player action moves something like this: Player action -> Game Client -> Network -> Server -> Network-> Game client. This means every player action is only executed once it makes a round trip though the network. This would make the game feel really laggy, that's why latency hiding was a mechanism added in the game almost since the introduction of multiplayer. Latency hiding works by simulating the player input, without considering the actions of other players and without considering the server's arbitrage.

In Factorio we have the Game State, this is the full state of the map, player, entitites, everything. It's simulated deterministically on all clients based on the actions received from the server. This is sacred and if it's ever different from the server or any other client, a desync occurs.

On top of the Game State we have the Latency State. This contains a small subset of the main state. Latency State is not sacred and it just represents how we think the game state will look like in the future based on the Input Actions the player performed.

The key thing is that the state of each object is immutable at the specific tick in the time line. Everything in the global multiplayer state must ultimately converge to a deterministic reality.

And - that might be the key to your question. Each entity's state is immutable for a given tick, and you keep track of the transition events that produces new instances over time.

If you think about it, the incoming event queue from the server has to have access to a central directory of entities, just so that it can apply its events.

In the end, your simple one-line mutator methods that you don't want to complicate are only simple because you're not really modeling time accurately. After all, if health can change in the middle of the processing loop, then earlier entities in this tick will see an old value, and later ones see a changed one. Managing this carefully means at the least differentiating current (immutable) and next (under construction) states, which are really just two ticks in the great time-line of ticks!

So, as a broad guide, consider breaking a monster's state into a number of small objects that relate to, say, location/velocity/physics, health/damage, assets. Construct an event to describe each mutation that might happen, and run your main loop as:

1. process inputs and generate corresponding events
2. generate internal events (eg due to object collisions etc)
3. apply events to current immutable monsters, to generate new monsters for next tick - mostly copying old unchanged state where possible, but creating new state objects where needed.
4. render and repeat for next tick.

Or something like that. I find thinking "how would I make this distributed?" is quite a good mental exercise, generally, for refining my understanding when I'm confused about where things live and how they should evolve.

Thanks to a note from @AaronM.Eshbach, highlighting that this is a similar problem domain to Event Sourcing and the CQRS pattern, where you are modeling changes to state in a distributed system as a series of immutable events over time. In this case, we're most likely trying to clean up a complex database app, by segregating (as the name suggests!) the mutator command handling from the query/view system. More complex of course, but more flexible.

Answer 2

You are still half in the imperative camp. Instead of thinking about a single object at a time think of your game in terms of a history of plays or events

p1 - send m1 to battlefield
p2 - send m2 to battlefield
m1 - attacks m2 (2 dam)
m2 - attacks m1 (10 dam)
p1 - retreats m1

etc

You can calculate the state of the game at any given point by chaining the actions together to produce an immutable state object. Each play is a function which takes a state object and returns a new state object