How do we feel about state machines?

xilnocas 2018-01-23 21:27:13 UTC #1

A while ago I released a draft blog post and got a lot of good feedback on it (big thanks to everyone who helped out!)

My big takeaway was that trying to explain a concrete programming technique (keeping models accessible to view functions but opaque to update functions) while dancing around the broader philosophy behind why one would want to do this was a big mistake. I now think it’s a better idea to start with a post introducing this philosophy, then follow up with concrete techniques for making it work.

The tl;dr of such a post would be this: state machines are a powerful mental model for Elm applications. Once you start thinking about (and drawing out!) the state machine underneath your app, lots of good things happen:

Since you’re explicitly specifying application states, impossible states are impossible by definition
It becomes easy to see why “components” (eg. init/update/view triplets) are are bad abstractions:
- their state machines know too little about the context of the app they’re in, so they need some complicated message passing mechanism to bubble information up (the so-called OutMsg pattern)
- they needlessly couple state machines to particular chunks of DOM
Better alternative abstractions become apparent, namely small, app-specific state machines for business logic, and reusable “config-only” views
Armed with the above abstractions, the scaling advice from @evancz and @rtfeldman becomes even more powerful

This perspective has made me personally much more productive with Elm, but because it implies a substantial shift from how we currently talk about Elm apps, I want to get everyone’s input before making too many noises about it in public.

There are movements in the broader frontend world indicating that folks are open to the idea of state machines. In particular, DavidKPiano’s ReactRally talk and this blog post from Adam Solove seem to have been well-received. Take a look at those resources and let me know what you think!

Some open questions:

How should we approach explaining state machines to beginners?
Do we need the word “state machine” at all?
Are there any potentially big risks I’m not seeing?

evancz 2018-01-24 01:49:54 UTC #2

I think the question “How do we explain state machines to beginners?” is a mistake.

The learning path of “start with abstract ideas and then do something practical” appeals to a small fraction of people. Often people who like to write about ideas. But in practice, very very few people learn like this. This is kind of the whole thesis of Elm when compared to Haskell’s pedagogy. In Elm it is like “Look at this program” and then “mess with it” as a way of getting started. In other places it is “Learn these 9 complex sounding things” and then you can do Hello World.

So while I personally find that the analogy of “coupling two state machines is way more complex than just designing one that handles more transitions” is pretty helpful, I do not think it follows that this is a general purpose learning pathway. It may be helpful for intermediate folks and/or folks who have a pretty good background with state machines. I know that some of my peers who took “Introduction to the Theory of Computation” did not really care about this stuff, so this analogy would not be useful even to them. So even folks with the background on paper will only sometimes find this useful.

In other words, for this to be a generally useful learning pathway, I think it has to be common knowledge. It’s not. If you want to make resources for learning about state machines, that’s great! That is great to understand! But I think that should be separate from learning Elm.

evancz 2018-01-24 02:10:27 UTC #3

As an aside, I did a talk called Accidentally Concurrent back in 2015 that covers why thinking of components (i.e. objects) leads to crazy results. I’d consider it a more general version of this “state machines” perspective.

This talk captures some of the most important insights I’ve had about program structure, but I consider this talk a failure. I think I presented things well, but no one has ever mentioned this talk to me. My lesson was that this path is not gonna work. Not enough folks know about concurrency yet.

I did a lot of reading about FRP, reactive programming, synchronous programming, message-passing concurrency, and the actor model. I also used OO languages for many years. Synthesizing that reading and experience is possible, but I think it is inherently too abstract to connect with people.

I decided to wait until more folks have done concurrent programming to try this route again. In the meantime, I say things different ways that have more direct connections to the problems people face and the experiences they’ve had.

opvasger 2018-01-24 07:06:17 UTC #4

I’ve seen the “Accidentally Concurrent” talk a couple of times and despite getting a little lost in some of the code-examples, I really value the points on “heirarchy /= modularity”, and how immutability is good; This is something I’ve struggled explaining to friends and colleagues who swear by object-orientation. But I digress…

opvasger 2018-01-24 07:13:22 UTC #5

You mention how model/update/view-triplets is an anti-pattern; Can you point me to any good sources on why this is the case? I thought this was idiomatic to the Elm architecture?

rupert 2018-01-24 10:09:27 UTC #6

This is how I approach designing applications in Elm. I draw the states that the application can be in on a piece of paper, and link them together with the possible transitions. Usually, but not always, each state is correlated with a particular view, and I might make a rough sketch of the views on my picture.

I then sketch out the data model that needs to exist for each state to support the view for that state, or to capture other state like a timeout or animation state that needs to be associated with it.

I like doing this on paper because I can scribble pictures and words quickly, and don’t need to worry too much about the correctness of it with respect to compilation. I will typically do 2 or 3 iterations of this until I feel that I have a good model of my application.

Then I code up the state machine. You may have seen it already, but this is my current approach to doing that: https://gist.github.com/rupertlssmith/88946c8d207d7ad64daf4360fef1ac42

What I like about state machines:

Each state only has the model that is needed for that state. This is much cleaner than having lots of Maybes or Bools in the Model to capture what the current state is and make fields in the model optional. It is better for making impossible states impossible.
It removes a lot of Maybe.map and Maybe.withDefault from the code, making it shorter and more readable. It removes many places in your code where you have a Maybe but you already know that it must be Just x at that point, but have to cater for the Nothing branch anyway.
You always know what state you are working in when writing code, and the compiler and tagged union type describing the state reinforce this.
Using phantom types, the compiler can also check that only legal transitions are being made.
State transitions are written as functions, making stepping through the state machine very explicit and connecting the code back to my paper drawing and mental model of the application.

xilnocas 2018-01-24 16:16:36 UTC #7

These two talks make the point well:

The Life of a File from Evan
Scaling Elm Apps from Richard

They’re the scaling advice I alluded to in the OP

Unfortunately, this advice seems not to have permeated the community yet. There are lots of packages lying around that stick to the strict init/update/view structure, when they’d be better served with a different API.

Edit: a previous version of this comment made exactly the opposite point from the one I intended to make Hopefully this is more clear

xilnocas 2018-01-24 16:23:56 UTC #8

Thanks for the reply, this is what I needed to hear! I can definitely separate things into “learning state machines” and “elm-specific insights that I happened upon by thinking about state machines”, and explain the latter in ways that the whole community will understand.

rupert 2018-01-24 16:35:20 UTC #9

Not sure what you mean by this? But I don’t think anything about state machines over-rules any of the advice given on those links.

State machine are simply one way of structuring your Model to help with eliminating impossible states, that is all. State machines are unrelated to the application scaling issue, except that I think they make it easier to understand and reason about larger applications.

There are other techniques for eliminating impossible states, it all depends on the data model you are working with. I would not promote state machines as some kind of cure-all for structuring and scaling Elm applications, just something that you might use where appropriate.

xilnocas 2018-01-24 19:00:53 UTC #10

Apologies, I completely mistyped: I was bemoaning the fact that lots of packages stick to the init/update/view structure, when they should really be following evan’s advice instead. Hopefully my edit to the comment makes my view more clear

Like I alluded to in the OP, I think the state machine perspective actually reinforces the scaling advice that evan and others give, because it gives me some more intuition about where clean abstraction boundaries might lie.

rupert 2018-01-24 22:28:02 UTC #11

Ok, makes sense.

Would love to see an example of what you mean by this in code.

michaeljones 2018-01-25 12:02:45 UTC #12

Something that mislead me was that an early github page documenting the elm architecture through a series of small examples seemed to aggressively use the triplet approach. I think the misunderstanding turned out to be that it was using small triplets because it was just a little example and it was combining them to show that that can be done reasonably easily when needed.

The trouble was how you extrapolate from that example to a larger code base. It turns out that it was wrong to think ‘this small example is built from combining a few small triplets so I’ll build bigger projects from combining lots of small triplets’. The correct approach was to think ‘this small example was built from a few small triplets so I’ll build bigger projects by combining a few really big triplets.’

Unfortunately I certainly went the wrong way for a long time and all the while thought ‘gosh, this is what the official elm guide wanted me to do.’

The trouble was worsened by drawing parallels with React and trying to see a triplet as a React component and then breaking down a larger Elm app in the same way that you’d break down a React app.

davidkpiano 2018-01-25 16:57:59 UTC #13

Hey @xilnocas, thanks for the mention! I’m excited to see the broader conversation around state machines and statecharts.

I’m somewhat new to Elm (made a few experiments before and begged for CSS variables to be included in Elm’s virtual DOM…cough), but I’d like to answer the questions posed in a general context.

How should we approach explaining state machines to beginners?

I don’t think this question is a mistake. I think it’s an extremely valuable endeavor, but instead of approaching it as “learn about deterministic finite automata” and other CS-related concepts, it’s better to approach it from “instead of developing an app bottom-up, think about the overall logic and plan it out, top-down”.

Elm’s code might look succinct, but there’s nothing easier than pencil and paper - and this is a great, intuitive way to learn what state machines are. Even people who have absolutely no experience in coding will be able to draw circles, arrows, and labels that explain “If we’re here, and we do this, then we go here”. In fact, this is how designers intuitively think - user flows are state machines!

Do we need the word “state machine” at all?

Sure. There’s lots of great references and learning material available by putting a name (“state machine” or “automata”) to an abstract but intuitive pattern of modeling application logic.

Are there any potentially big risks I’m not seeing?

Oh yes - state explosion, representing simultaneous states in a (supposedly) deterministic way, dealing with side-effects and temporal states, knowing how to organize multiple states, state history, etc. etc.

However, those are all solved with the notion of statecharts, which are an extension of (and fully compatible with) finite state machines (they’re essentially hierarchical finite state machines).

Note: statecharts are not easy to implement (xstate is my in-progress implementation) but the idea is the same: you have a pure transition function which takes the current state, action, and returns the next state. If you squint, Elm’s architecture naturally models this pattern (except not in as structured a way as a formal statechart definition).

We need to approach and teach state machines and statecharts from the perspective of designing complex user interfaces and applications, instead of from a heavily theoretical computer science approach. I fully intend to experiment on bringing the statechart formalism to Elm and seeing how Elm apps can be modeled with such an approach.

Also important to note that it’s not just a different way to code. It’s a way to have your application logic fully declarative so that you can easily visualize and automatically generate full integration tests for your entire app, and also make it easy to refactor, since a “feature” is just a node in a directed graph.

rupert 2018-01-26 15:10:47 UTC #14

You got me thinking about something - I am using a Model/Msg/init/update pattern to encapsulated a module with state.

First off, some people are saying TEA is a state machine. But it isn’t quite, the update function is like msg, model -> model. The msg is an event, like making a state transition, and the model is the state. But its not a state machine as such, unless the model is structured as a finite set of states, and with a sub-set of the cross product of states defining the possible transitions between them. That is what makes a state machine.

I was also using an out message with my module, as there are certain conditions it needs to signal back to the consumer of the module (logged in, logged out and failed to authenticate). The out message captured these as events (or transitions). Not all updates produce an event (Maybe outmsg), only those that make the transition into these states.

I have now changed to modelling them instead as states. The state machine is returned from the update function (msg, model -> model) inside the model in the usual way, but there is now no need to have a separate out message. The consumer of this update method gets handed back the state, and it can pattern match on the state machine to know what state it is in (logged in, logged out and tried-to-log-in-but-failed state).

Something else interesting happens with this. The consumer of the stateful module now needs less state itself, since it now has the state information it needs - it just needs to render the correct UI for each of these states. When it was working with out messages, it had to interpret them as events and maintain its own understanding of what the state is.

Does that make sense? I’ve been able to get rid of out messages and duplicate less state this way. Its feels less reactive and more declarative.

Code is here: https://github.com/the-sett/auth-elm/tree/state-machine

MarkHamburg 2018-01-30 16:29:32 UTC #15

First, let me say that login is a prime example of where state machines matter when thinking about making impossible states impossible. It goes right along with the examples you can find in multiple ML videos from Jane Street about representing connection state. That said, there’s a bigger issue to address in that often the rest of the state in a program isn’t meaningful when not logged in. If you just put the authentication model next to everything else then you need to explain what it means to have data when not logged in. Or in the case of your example, what does it mean when the top level username and password field are out of sync with the auth model?

Second, I have not read all of the code in detail, so maybe I’ve missed something but there were a couple of issues with your code that leapt out at me beyond the general issue touched on above:

• In Auth.elm looks to me like state could just be represented as derived data from innerModel — it gets rebuilt cheaply when inserting a new innerModel — so why not make it a function of the model rather than storing it as a value which isn’t forced to be in sync?

• You have a potential async response problem with token refreshes since a refresh for an old login will overwrite the current login. This is a common subtlety in async message handling that I see code often miss. (Just because I got a response, is it still the response I’m looking for?)

Both of those points are readily addressable, so I don’t view them as big deals. Maintenance of the derived state information is at least encapsulated in the Auth model code. But I probably would look at the refresh async logic since it’s just the sort of lurking bug that because it is timing dependent will be a pain to reproduce.

But returning to the first point about overall model correctness, this problem is a great example of the tensions in factoring code. If there is a bunch of state that should only exist when logged in, how is that best represented? And if the logic managing that state needs to do some final clean up before logging out, how do we orchestrate that clean up with transitioning the overall state? The program with navigation pattern could resolve the first problem by creating a program with authentication wrapper which would both init the app state with the credentials and refresh them when the auth token changes, but that still leaves the need for a way for the app state to do whatever cleanup it needs to do and signal a logout. And building programs up via wrappers like this isn’t exactly encourages. So, I think — modulo the issues raised above — you’ve done a great job encapsulating why and how an isolated state machine can be useful which then feeds into the question of how that sort of construction can best be used in a program that strives to use the type system to eliminate impossible states.

Mark

rupert 2018-01-30 20:36:39 UTC #16

Good spot, thanks. I was so busy thinking that needed to return state with the model, that I overlooked the possibility of producing it on demand from the model and exporting a function on the Auth module to do that, which is neater and avoids the small amount of duplicated state.

Yes, I need some sort of correlation id to link together the request and response.

Although, in this case it may not matter. The reason for having a refresh token, is that the refresh token is fully checked against the database each time, so if an account were locked refresh would not happen. The JWT token, once issued, relies on the signature to prove its validity, and is not checked against the database each time. You cannot revoke such stateless tokens, which is why they are kept short lived and used in conjunction with a periodic refresh. Any of many in-flight refreshes can put it back into the logged in state and it will work fine with that.

rupert 2018-01-30 20:42:38 UTC #17

Yes, the username and password in the Top.elm module should only exist when in the logging in, or failed auth states, and not in the logged in state. I got a little lazy there with eliminating impossible states.

Perhaps I should make space for them inside the Auth model instead? That way the top model doesn’t need to maintain its own understanding of the Auth state.

Thanks again for your input and ideas.