13 ms·

Traditional programming languages and imperative thinking don't lend themselves to writing state machines, so its not really that surprising that they're under

by s4vi0r 9y ago

Traditional programming languages and imperative thinking don't lend themselves to writing state machines, so its not really that surprising that they're under utilized. Its kind of frustrating constantly reading posts where people shit on functional programm(ers|ing) for being too ivory tower-y or whatever, when its kind of hard not to be when a lot of the older FP guys have spent the last like 20-30 years going "yo this is dope you guys should really be doing this" and getting largely ignored. State machines are super commonly used in languages where you can (easily) construct ADTs and pattern match on them.

vvanders 9y ago
Plenty of imperative domain spaces use state machines, gamedev and the like come to mind in particular.
- pdelbarba 9y ago
  Similarly with embedded development. We use them for just about everything from communications to scheduling. I think the subtext here is that state machines are just rarely used for web/mobile...
  - DCoder 9y ago
    One simplistic state machine in web/mobile is mouse/swipe motion handling – mousedown transitions into "in motion" state, mousemove tracks that state, mouseup transitions into "finished motion" state, runs event handlers, and transitions again into "idle" state.
  - vvanders 9y ago
    Yup, I'm in the middle of writing a packet radio protocol and it's mostly just nested state machines.
- jjjensen90 9y ago
  Definitely true for gamedev in my experience. I don't think I've worked in a game code base of nontrivial size without seeing some implementation of state machines.
  - PeterisP 9y ago
    The "some implementation" probably is part of the problem - if there was a good generic implementation included in the standard library so that it could and would be used in language tutorials (especially in languages where rolling nice state machine code is tricky), then developers would use them much more.
    - vvanders 9y ago
      The problem with that is each system has slightly different requirements. Scripting state machines vs animation state machines are going to have very different constraints and end-goals. [edit] For example here is UE3's anim tree[1] editor vs Kismet[2]. [1] https://docs.unrealengine.com/udk/Three/AnimTreeEditorUserGuide.html https://docs.unrealengine.com/udk/Three/AnimTreeEditorUserGu... [2] https://docs.unrealengine.com/udk/Three/KismetUserGuide.html https://docs.unrealengine.com/udk/Three/KismetUserGuide.html
sevensor 9y ago
> State machines are super commonly used in languages where you can (easily) construct ADTs and pattern match on them. I had the opportunity to use F# for the first time last month, and I experienced this first hand -- it was far easier to write a procedure as a sum type with transition functions than it would have been to write it procedurally. And with all the advantages of having the states of the system and their transitions laid out explicitly, why fight it?
- NicoJuicy 9y ago
  Github?
  - sevensor 9y ago
    Unfortunately no -- NDA / work-for-hire. Customer requested .NET but didn't care which language. We usually write Python, F# felt friendlier than C#. State classes looked like: type InitialState = {a : int; b : string} type IntermediateState = {a : int; b: string; c: string list} type FinishedState = {a: int; b: string} type ErrorState = {a: int; b: string; message: string} type State = | UninitializedState | InitialState of InitialState | IntermediateState of IntermediateState | FinishedState of FinishedState | ErrorState of ErrorState | FinalState And transition functions: let initialize (args : string list) (s:UninitializedState) : State = // create an initial state from args, not actually like this InitialState {a= 5; b="hello"} I probably put too many types into my function signatures, but I'm new to this style.
seanmcdirmid 9y ago
What? No, that isn’t true at all. State machines come before the FP/IP divide even existed. State machines are also intrinsically stateful, that should be obvious.
- tytytytytytytyt 9y ago
  > State machines are also intrinsically stateful, that should be obvious. So are lots of data types, but those are still useful in FP.
  - seanmcdirmid 9y ago
    Yes, that should be obvious also. State machines have no strong relationship with FP. I'm not sure where this claim even comes from!
    - noblethrasher 9y ago
      In 's4vi0r’s defense, “FP” usually means ML-style FP, which does happen to be pretty biased towards creating stack-based FSMs since it has literal syntax for stacks (list literals), states (discriminated unions + tuples), and transitions (pattern matching).
      - coldtea 9y ago
        >“FP” usually means ML-style FP Only after sometime around 2010. Before that it was mostly Lisp and Scheme. Sometime around then, the trend around Haskell, purity, and co overtook them as what people mean when they talk about FP.
    - throwaway010317 9y ago
      This comment reminds me of something I read recently on Yaron Minsky's twitter: "An odd habit of functional programmers: when confronted with a nice, but clearly imperative way of structuring a program, they will often declare that this technique is in fact functional." (https://twitter.com/yminsky/status/950883335324225541 https://twitter.com/yminsky/status/950883335324225541) and then "Case in point: structuring a program as an imperative, deterministic state machine, where the state is determined fully by the state machine logic plus the sequence of transactions." (https://twitter.com/yminsky/status/950883598189686784 https://twitter.com/yminsky/status/950883598189686784)
gopalv 9y ago
> Traditional programming languages and imperative thinking don't lend themselves to writing state machines That's probably not the problem - imperative development can start off from a level of complexity where state machines don't look relevant. Six weeks down the line, the whole codebase has overtaken the complexity of a state machine, though each of the development bugs were simple fixes to the original branching code. The standard web-app wizard is where I've run into this again and again. Every web-app is stateful enough to maintain DB state sync'd & ticking over from a user-click, which makes it really easy to work out whether all clicks go somewhere useful. However this makes sense only when you have around 7+ states and transitions between them (particularly the "go back" one). Until then, the regular if/else branch scenarios work out just fine ... but then when you're near the 20-30 state range, it all falls apart.
- xyhopguy 9y ago
  > (particularly the "go back" one). Holy shit, once I built a web app for some biologists that wanted a "designer wizard." First I implemented a really shitty buggy wizard. Then I refactored it all into a state machine...........
- spdionis 9y ago
  That's also why state machines are common in GUI frameworks, as noted by a sibling comment above.
Animats 9y ago
Traditional programming languages and imperative thinking don't lend themselves to writing state machines. Linden Scripting Language, used for Second Life, has explicit state machines as a first-class programming construct. Programs are divided into state sections, using a keyword "state". Each state has its own local functions.
simonh 9y ago
>the older FP guys have spent the last like 20-30 years going "yo this is dope you guys should really be doing this" and getting largely ignored I've not been ignoring them. I tried at least three different Haskell tutorials and articles explaining how cool it is. The problem was the author would show some code sand say 'see how easy it is to do this, and this, and this!', but I'd look at the code and have no idea whatever what it was doing or how it was doing it, and the guide/tutorial wouldn't tell me. After a few tries, I just gave up. Maybe there's a canonical newbie's tutorial that takes you through the shift from imperative/procedural thinking?
- oblio 9y ago
  Heh, very often their problem domain is also an issue. "We're going to write a compiler in our shiny FP language". "We're going to implement a Fourier transform". Nah, thanks, could you show me instead how I can get the Employee record from an XML file, stick it in a PostgreSQL database and also send it down the wire through a REST API as JSON?
  - PeterisP 9y ago
    Haskell code for that looks quite nice as well - however, it's less about a language per se but rather about availability of libraries and how mature / well-built their API is. For quite a few FP languages the ecosystem is there and you can do all these problem domains nicely, they just tend to be skipped in tutorials as they rely on non-core third party libraries (sometimes with multiple nice but very different alternatives). Perhaps a "batteries-included" stance of Ruby(+Rails) and Python would simplify that, but it's more of a political issue.
    - oblio 9y ago
      > It's less about a language per se but rather about availability of libraries and how mature / well-built their API is. In the real world, those matter just as much as the language. They usually matter even more :) Look at what Rust is doing - I think at least half of their effort is spent towards building up a large collection of high quality, well maintained (i.e. feature requests implemented, bugs fixed quickly) and well documented libraries.
arkh 9y ago
As a whole, a database-backed CGI server can be considered a state machine.
bmarkovic 9y ago
State machines are still and by far most commonly used in C, where, lo and behold, most low-level and embedded programming is still done. And function pointers make up for pretty much the only fundamentally useful aspect of FPs regarding FSMs which is functions as first-class objects. Everything else pretty much just substitutes one convenience for another. A pretty good case can be made about how the State Pattern makes traditional OOP indispensable in FSM design, and I'm sure that in OO languages with functions as first class objects (like Python, Lua or Javascript) people can showcase elegant designs that to them far surpass both classically OO or classically FP designs etc. etc.
- naasking 9y ago
  > And function pointers make up for pretty much the only fundamentally useful aspect of FPs regarding FSMs which is functions as first-class objects. I'd argue sums and pattern matching are almost as important given the simplicity of expression.
jcelerier 9y ago
> Traditional programming languages and imperative thinking don't lend themselves to writing state machines, pretty sure most C introduction books cover various implementations of state machines. In "traditional" desktop WIMP GUI software it's a fairly common paradgim ; a bunch of frameworks such as StateCharts with SCXML even allow you to design the state machine graphically and have it compiled to C++ or Java code.
dragonwriter 9y ago
I don't think there is a conflict between imperative thinking and state machines, but I do agree that lots of programming languages neither provide built-in features for expressing state machines nor support expressing them particularly elegantly, and that the superior support for general abstraction in certain functional languages reduce the friction of use. It's pretty easy to imagine, though, a class based OOP language where each class was also an HSM, with methods defined per state and identifying transitions (as well as states and their entry and exit behavior being explicitly defined.)
jstimpfle 9y ago
> a lot of the older FP guys have spent the last like 20-30 years going "yo this is dope you guys should really be doing this" many of "the older FP guys" actually think "it's cool, it's mathematical. But it's not practical."
0xcde4c3db 9y ago
State machines are one of the most traditional programming constructs there is, and most people I've seen champion or use them are the types who would rather program in assembly than Haskell. Heck, some "imperative thinking" programmers consider state machines only slightly more exotic than a for loop, and would be similarly dismayed if a colleague didn't know how to write one.

by s4vi0r 9y ago

vvanders 9y ago

Plenty of imperative domain spaces use state machines, gamedev and the like come to mind in particular.

pdelbarba 9y ago
Similarly with embedded development. We use them for just about everything from communications to scheduling. I think the subtext here is that state machines are just rarely used for web/mobile...
- DCoder 9y ago
  One simplistic state machine in web/mobile is mouse/swipe motion handling – mousedown transitions into "in motion" state, mousemove tracks that state, mouseup transitions into "finished motion" state, runs event handlers, and transitions again into "idle" state.
- vvanders 9y ago
  Yup, I'm in the middle of writing a packet radio protocol and it's mostly just nested state machines.
jjjensen90 9y ago
Definitely true for gamedev in my experience. I don't think I've worked in a game code base of nontrivial size without seeing some implementation of state machines.
- PeterisP 9y ago
  The "some implementation" probably is part of the problem - if there was a good generic implementation included in the standard library so that it could and would be used in language tutorials (especially in languages where rolling nice state machine code is tricky), then developers would use them much more.
  - vvanders 9y ago
    The problem with that is each system has slightly different requirements. Scripting state machines vs animation state machines are going to have very different constraints and end-goals. [edit] For example here is UE3's anim tree[1] editor vs Kismet[2]. [1] https://docs.unrealengine.com/udk/Three/AnimTreeEditorUserGuide.html https://docs.unrealengine.com/udk/Three/AnimTreeEditorUserGu... [2] https://docs.unrealengine.com/udk/Three/KismetUserGuide.html https://docs.unrealengine.com/udk/Three/KismetUserGuide.html

sevensor 9y ago

> State machines are super commonly used in languages where you can (easily) construct ADTs and pattern match on them. I had the opportunity to use F# for the first time last month, and I experienced this first hand -- it was far easier to write a procedure as a sum type with transition functions than it would have been to write it procedurally. And with all the advantages of having the states of the system and their transitions laid out explicitly, why fight it?

NicoJuicy 9y ago
Github?
- sevensor 9y ago
  Unfortunately no -- NDA / work-for-hire. Customer requested .NET but didn't care which language. We usually write Python, F# felt friendlier than C#. State classes looked like: type InitialState = {a : int; b : string} type IntermediateState = {a : int; b: string; c: string list} type FinishedState = {a: int; b: string} type ErrorState = {a: int; b: string; message: string} type State = | UninitializedState | InitialState of InitialState | IntermediateState of IntermediateState | FinishedState of FinishedState | ErrorState of ErrorState | FinalState And transition functions: let initialize (args : string list) (s:UninitializedState) : State = // create an initial state from args, not actually like this InitialState {a= 5; b="hello"} I probably put too many types into my function signatures, but I'm new to this style.

seanmcdirmid 9y ago

What? No, that isn’t true at all. State machines come before the FP/IP divide even existed. State machines are also intrinsically stateful, that should be obvious.

tytytytytytytyt 9y ago
> State machines are also intrinsically stateful, that should be obvious. So are lots of data types, but those are still useful in FP.
- seanmcdirmid 9y ago
  Yes, that should be obvious also. State machines have no strong relationship with FP. I'm not sure where this claim even comes from!
  - noblethrasher 9y ago
    In 's4vi0r’s defense, “FP” usually means ML-style FP, which does happen to be pretty biased towards creating stack-based FSMs since it has literal syntax for stacks (list literals), states (discriminated unions + tuples), and transitions (pattern matching).
    - coldtea 9y ago
      >“FP” usually means ML-style FP Only after sometime around 2010. Before that it was mostly Lisp and Scheme. Sometime around then, the trend around Haskell, purity, and co overtook them as what people mean when they talk about FP.
  - throwaway010317 9y ago
    This comment reminds me of something I read recently on Yaron Minsky's twitter: "An odd habit of functional programmers: when confronted with a nice, but clearly imperative way of structuring a program, they will often declare that this technique is in fact functional." (https://twitter.com/yminsky/status/950883335324225541 https://twitter.com/yminsky/status/950883335324225541) and then "Case in point: structuring a program as an imperative, deterministic state machine, where the state is determined fully by the state machine logic plus the sequence of transactions." (https://twitter.com/yminsky/status/950883598189686784 https://twitter.com/yminsky/status/950883598189686784)

gopalv 9y ago

> Traditional programming languages and imperative thinking don't lend themselves to writing state machines That's probably not the problem - imperative development can start off from a level of complexity where state machines don't look relevant. Six weeks down the line, the whole codebase has overtaken the complexity of a state machine, though each of the development bugs were simple fixes to the original branching code. The standard web-app wizard is where I've run into this again and again. Every web-app is stateful enough to maintain DB state sync'd & ticking over from a user-click, which makes it really easy to work out whether all clicks go somewhere useful. However this makes sense only when you have around 7+ states and transitions between them (particularly the "go back" one). Until then, the regular if/else branch scenarios work out just fine ... but then when you're near the 20-30 state range, it all falls apart.

xyhopguy 9y ago
> (particularly the "go back" one). Holy shit, once I built a web app for some biologists that wanted a "designer wizard." First I implemented a really shitty buggy wizard. Then I refactored it all into a state machine...........
spdionis 9y ago
That's also why state machines are common in GUI frameworks, as noted by a sibling comment above.

Animats 9y ago

Traditional programming languages and imperative thinking don't lend themselves to writing state machines. Linden Scripting Language, used for Second Life, has explicit state machines as a first-class programming construct. Programs are divided into state sections, using a keyword "state". Each state has its own local functions.

simonh 9y ago

>the older FP guys have spent the last like 20-30 years going "yo this is dope you guys should really be doing this" and getting largely ignored I've not been ignoring them. I tried at least three different Haskell tutorials and articles explaining how cool it is. The problem was the author would show some code sand say 'see how easy it is to do this, and this, and this!', but I'd look at the code and have no idea whatever what it was doing or how it was doing it, and the guide/tutorial wouldn't tell me. After a few tries, I just gave up. Maybe there's a canonical newbie's tutorial that takes you through the shift from imperative/procedural thinking?

oblio 9y ago
Heh, very often their problem domain is also an issue. "We're going to write a compiler in our shiny FP language". "We're going to implement a Fourier transform". Nah, thanks, could you show me instead how I can get the Employee record from an XML file, stick it in a PostgreSQL database and also send it down the wire through a REST API as JSON?
- PeterisP 9y ago
  Haskell code for that looks quite nice as well - however, it's less about a language per se but rather about availability of libraries and how mature / well-built their API is. For quite a few FP languages the ecosystem is there and you can do all these problem domains nicely, they just tend to be skipped in tutorials as they rely on non-core third party libraries (sometimes with multiple nice but very different alternatives). Perhaps a "batteries-included" stance of Ruby(+Rails) and Python would simplify that, but it's more of a political issue.
  - oblio 9y ago
    > It's less about a language per se but rather about availability of libraries and how mature / well-built their API is. In the real world, those matter just as much as the language. They usually matter even more :) Look at what Rust is doing - I think at least half of their effort is spent towards building up a large collection of high quality, well maintained (i.e. feature requests implemented, bugs fixed quickly) and well documented libraries.

arkh 9y ago

As a whole, a database-backed CGI server can be considered a state machine.

bmarkovic 9y ago

State machines are still and by far most commonly used in C, where, lo and behold, most low-level and embedded programming is still done. And function pointers make up for pretty much the only fundamentally useful aspect of FPs regarding FSMs which is functions as first-class objects. Everything else pretty much just substitutes one convenience for another. A pretty good case can be made about how the State Pattern makes traditional OOP indispensable in FSM design, and I'm sure that in OO languages with functions as first class objects (like Python, Lua or Javascript) people can showcase elegant designs that to them far surpass both classically OO or classically FP designs etc. etc.

naasking 9y ago
> And function pointers make up for pretty much the only fundamentally useful aspect of FPs regarding FSMs which is functions as first-class objects. I'd argue sums and pattern matching are almost as important given the simplicity of expression.

jcelerier 9y ago

> Traditional programming languages and imperative thinking don't lend themselves to writing state machines, pretty sure most C introduction books cover various implementations of state machines. In "traditional" desktop WIMP GUI software it's a fairly common paradgim ; a bunch of frameworks such as StateCharts with SCXML even allow you to design the state machine graphically and have it compiled to C++ or Java code.

dragonwriter 9y ago

I don't think there is a conflict between imperative thinking and state machines, but I do agree that lots of programming languages neither provide built-in features for expressing state machines nor support expressing them particularly elegantly, and that the superior support for general abstraction in certain functional languages reduce the friction of use. It's pretty easy to imagine, though, a class based OOP language where each class was also an HSM, with methods defined per state and identifying transitions (as well as states and their entry and exit behavior being explicitly defined.)

jstimpfle 9y ago

> a lot of the older FP guys have spent the last like 20-30 years going "yo this is dope you guys should really be doing this" many of "the older FP guys" actually think "it's cool, it's mathematical. But it's not practical."

0xcde4c3db 9y ago

State machines are one of the most traditional programming constructs there is, and most people I've seen champion or use them are the types who would rather program in assembly than Haskell. Heck, some "imperative thinking" programmers consider state machines only slightly more exotic than a for loop, and would be similarly dismayed if a colleague didn't know how to write one.