Xstate: Add support for extended state

[bedeho]

Avoid combinatorial explosion of states.

[davidkpiano]

Combinatorial explosion of states is already mitigated with hierarchical states, unless you mean something else?

[bedeho]

Hierarchical states solve a different problem, namely shared event handling for groups of states. The combinatorial explosion problem still very much persists.

https://en.wikipedia.org/wiki/UML_state_machine#Extended_states

One possible interpretation of state for software systems is that each state represents one distinct set of valid values of the whole program memory. Even for simple programs with only a few elementary variables, this interpretation leads to an astronomical number of states. For example, a single 32-bit integer could contribute to over 4 billion different states. Clearly, this interpretation is not practical, so program variables are commonly dissociated from states.

As you see, the UML statechart standard has _both_ orthogonal and composite states, and extended state, they are not redundant.

[davidkpiano]

For the API design, what are your thoughts on machine.transition(state, action) having state represent both qualitative and quantitative (extended) states? Simple light example:

const lightMachine = Machine({
  key: 'light', // <-- this is where the machine looks for the finite state
  initial: 'green',
  states: {
    green: {
      on: {
        TIMER: {
          // guard conditions
          green: ({ elapsed }) => elapsed < 100,
          yellow: ({ elapsed }) => elapsed >= 100 && elapsed < 200
        }
      }
    },
    yellow: {}
  }
});

Usage:

const currentState = {
  light: 'green',
  elapsed: 101
};

// Either this...
const nextState = machine.transition(currentState, 'TIMER');
// => State {
//   value: { light: 'yellow', elapsed: 101 }
//   ...
// }

// Or this (extended state passed in as 3rd argument)
const nextState = machine.transition('green', 'TIMER', { elapsed: 101 });
// => State {
//   value: 'yellow',
//   data: { elapsed: 101 }
//   ...
// }

Which would you prefer? I see advantages to both, but am curious of your thoughts. The first way would change the API significantly, so I'm leaning towards the second way (keeping finite state and extended state separate, so that the developer can use it as they wish)

[davidkpiano]

I'm leaning towards the 2nd one (that is, making 'data' explicit) since the idea of "extended state" (i.e., data) is separate as well in SCXML: https://www.w3.org/TR/scxml/#data

[bedeho]

Second one seems like a good bet.

[davidkpiano]

Thanks for the input, @bedeho. Here's what the V2 structure will look like with the handlers by the way, which take in the extendedState and the action as arguments:

  const lightMachine = Machine({
    key: 'light',
    initial: 'green',
    states: {
      green: {
        on: {
          TIMER: {
            green: {
              cond: ({ elapsed }) => elapsed < 100
            },
            yellow: {
              cond: ({ elapsed }) => elapsed >= 100 && elapsed < 200,
              onTransition: handleGreenYellowTransition
            }
          }
        },
        onEntry: handleGreenEntry,
        onExit: handleGreenExit
      },
      yellow: {}
    }
  });

[lmatteis]

As I pointed out here https://github.com/davidkpiano/xstate/issues/10#issuecomment-352192598 I don't think conditions and extended state should be dealt by xstate. Extended state can be managed by an actual state/data-management library like React's setState() or Redux, as well as conditional logic.

Thoughts?

edit here's a quote from wiki page https://en.wikipedia.org/wiki/UML_state_machine#Guard_conditions:

Indeed, abuse of extended state variables and guards is the primary mechanism of architectural decay in designs based on state machines. Usually, in the day-to-day battle, it seems very tempting, especially to programmers new to state machine formalism, to add yet another extended state variable and yet another guard condition (another IF or an ELSE) rather than to factor out the related behavior into a new qualitative aspect of the system—the state. From experience in the trenches, the likelihood of such an architectural decay is directly proportional to the overhead (actual or perceived) involved in adding or removing states (which relates to the actual strategy used for implementing UML state machines.)

[davidkpiano]

I agree @lmatteis, which is why:

• Extended state wasn't even considered in v1.0, nor was guard conditions/events until now
• xstate will encourage constant strings for guards/events, instead of inline functions (all the docs will be string-first)
• xstate will _never_ manipulate external state.

I agree that it should be discouraged, but we shouldn't make it impossible either.

[bedeho]

That quote merely points out that extended state variable mechanism can be abused, which I agree with, but not sure how that relates to your point.

If the goal of this lib is to use it to manage complex application state, then this feature will be required. I don't understand what it would mean for a third party to manage the extended state, but I have never seen anything like that. A good reference library is the standard boost statechart library. It is the most mature and well developed state chart library I have found for C++, and its part of the boost standard library.

http://www.boost.org/doc/libs/1_61_0/libs/statechart/doc/index.html#Overview

This is how they deal with extended states & state guards

http://www.boost.org/doc/libs/1_61_0/libs/statechart/doc/tutorial.html#StateLocalStorage

[lmatteis]

I don't understand what it would mean for a third party to manage the extended state, but I have never seen anything like that.

That's because you're probably using a Statechart library (such as the ones you linked) that manages everything for you. These libraries have their own internal state where you can define guard variables. Not to mention the ability to also specify function implementation that changes such state - thus making them imperative.

On the other hand, I think xstate is trying to be completely pure and declarative. Meaning that it has no way to modify external state. Thus it is made to be used with a third-party library that does state-management, otherwise how else would you build anything with it?

In other words, you need a place to store and update the result of .transition(), and an event system to trigger such transitions. Not to mention a system that only calls .transition() given a condition (guards). Also probably a place to store other data (extended state), such as a database or a localStorage or something else.

Redux for instance has all of these, but the cool thing about keeping xstate agnostic about these decisions is that developers can choose whatever solution they please.

[davidkpiano]

@lmatteis Correct, xstate will remain pure and declarative (aside from some memoization for performance purposes).

The introduction of handling external state, whether via guards or effects (onEntry, onExit) does not change this. xstate will only report what effects will occur on a state transition, and/or what the transition will be given some extended state.

[davidkpiano]

Extended state is now supported within the context of guard transitions (cond): http://davidkpiano.github.io/xstate/docs/#/guides/guards