Immutable data in async systems

Question

I have a good idea of the benefits of using immutable data in my applications and I'm fairly comfortable with the idea of using these immutable structures in a simple synchronous programming environment.

There's a good example somewhere on Stack Overflow that describes managing state for a game by passing the state along in a series of recursive calls, something like this:

function update(state) {
  sleep(100)

  return update({
    ticks: state.ticks + 1,
    player: player
  })
}

We can do some arbitrary, side-effect free work in the body of the function, then we return a new state, rather than mutating the old one.

It seems fairly easy to translate this to a simple async model, in say Javascript.

function update(state) {
  const newState = {
    player,
    ticks: state.ticks + 1
  };

  setTimeout(update.bind(this, newState), 100);
}

However, as soon as we have more sources for asynchronous events, it seems to become a lot harder to manage to keep the state immutable and the functions pure.

If we add a click event to the example, we end up with code that looks like this.

window.addEventListener('click', function() {
  // I have no idea what the state is
  // because only our update loop knows about it
});

Now obviously, I don't want to mutate the state in this method, but I need to access state in order to create a new state, something like this.

window.addEventListener('click', function() {
  const state = getState();

  createState({
    player,
    clicks: clicks + 1
  });
});

But it would seem like this requires some kind of mutable state manager?

Alternatively, I suppose I could add the click event to a queue of actions to be processed within the update loop, something like:

window.addEventListener('click', function() {
  createAction('click', e);
});

function update(state, actions) {
  const newState = {
    player,
    ticks: state.ticks + 1,
    clicks: state.clicks + actions.clicks.length
  };

  setTimeout(update.bind(this, newState, []), 100);
}

Again, this doesn't feel particularly functional and relies on at least some mutable state somewhere along the way. These are probably naive approaches coming from someone who has mostly worked with mutable state and imperative object oriented programming.

What does the design for a system look like when there are multiple asynchronous event sources and we want everything to be immutable? Or at least, what's a good pattern for controlling mutability in a system like this?

Answer 1

In an attempt to directly answer your question:

"What does the design for a system look like when there are multiple asynchronous event sources and we want everything to be immutable? Or at least, what's a good pattern for controlling mutability in a system like this?"

The correct solution pattern for this design has, in the unix world, been the asynchronous FIFO message queues(AMQs), ever since System 5 anyways, while there is theoretically conditions under which race conditions and state indeterminacy could occur in practice it almost never does. In fact early research into reliability of AMQs determined that these errors arose not because of transmission lag but because of collision with synchronous interrupt requests as early AMQs were essentially just pipes implemented in the kernel space. The modern solution, in fact the Scala solution, is to implement the AMQ in shared protected memory thereby removing the slow and potentially hazardous kernel calls.

As it turns out if your total message bandwidth is less than the total channel capacity and your transmission distance is less than a light-second away - resistance/switching, your failure probability is cosmically low (like something on the order of 10^-24). There are all sorts of theoretical reasons why, but without a digression into quantum physics and information theory it cannot really be addressed concisely here, however no mathematical proof has yet been found to definitively prove that such is the case, it's all estimates and practice. But every flavor of unix has relied on those estimates for 30+ years now for reliable asynchronous communication.

If you are wondering how interrupt behavior can be introduced, the design pattern is either direct or secondary priority queueing, adding priority or ordering levels adds small overhead to a message manifest and is how synchronous and asynchronous calls can be composed.

The design pattern for preserving immutable start state with multiple mutable instructions is similar to state preserving patterns, you can use either historical or differencing queues. A historical queue stores the original state and an array of state changes, like an undo history. Whereas a differencing queue holds the initial state the and the sum of all changes (slightly smaller and faster, but not as big of a deal these days).

Finally, if you do need to deal with large or packetized messages traveling a large distance of a convoluted network or in and out of the kernel repeatedly the design pattern is to add origin address for callbacks and a timestamp as well as a little correction handling, which is why TCP/IP, SMQ, Netbios, etc all include these in their protocols, so should you need to do that you modify your prioritizing/ordering queue to be packet aware.

i realize this is a hasty treatment of a massive subject, which is why I'm happy respond back if there are any further questions or points that need to be clarified.

I hope I answered your question and didn't veer to far from what you were asking. :)

Post-Edit:

Here are some good examples of how and why to use these kind of kind of queue designs for distributed concurrent applications, they used for the heart of most FRP distributed design solutions:

https://docs.oracle.com/cd/E19798-01/821-1841/bncfh/index.html

https://blog.codepath.com/2013/01/06/asynchronous-processing-in-web-applications-part-2-developers-need-to-understand-message-queues/

http://www.enterpriseintegrationpatterns.com/patterns/messaging/ComposedMessagingMSMQ.html

http://soapatterns.org/design_patterns/asynchronous_queuing

http://www.rossbencina.com/code/programming-with-lightweight-asynchronous-messages-some-basic-patterns

http://www.asp.net/aspnet/overview/developing-apps-with-windows-azure/building-real-world-cloud-apps-with-windows-azure/queue-centric-work-pattern

http://spin.atomicobject.com/2014/08/18/asynchronous-ios-reactivecocoa/

http://fsharpforfunandprofit.com/posts/concurrency-reactive/

and a video from Martin Odersky...

https://www.typesafe.com/resources/video/martin-odersky---typesafe-reactive-platform

:)

Answer 2

You might be interested in taking a look at Redux. Redux takes a similar approach:

• It models the whole application state as a single immutable object.
• User actions are essentially messages that are dispatched to the store for arbitrary processing.
• Actions are handled by reducer functions in the form f(previousState, action) => newState. This is a more functional approach than your original version.
• The store runs the reducers and maintains a single immutable application state.

You're right that this isn't strictly immutable, as the store itself has a mutable reference to the current state. But as others have noted, this doesn't seem like an issue for most conceptions of immutable data.

In addition to UI actions, you might also have a tick action that fires in a loop - it's just another input event, processed by the same set of reducers.

Answer 3

Using Object.freeze, you can make an object immutable:

var o = {foo: "bar"};
Object.freeze(o);
o.abc = "xyz";
console.log(o);

Will yield {foo: "bar"}. Note that the attempt to set the new property on the frozen variable will fail silently.

In this case, after creating the new state object, freeze it before calling update routines or triggering events to prevent further modification.