undefined | Better HN

0 pointspjc506y ago0 comments

State machines are a surprisingly powerful tool. They do require you to capture all the possible states of the system; the combinational explosion of "X while Y but not while Z" can get a bit nasty, but that can often force a redesign simply to reduce the state space.

If all your logic is immutable apart from a small area around the state machine the state gets much easier to manage. You write everything as f(state, inputs) => next_state. You can at any point inspect or print the state of the state machine, and record its transitions so you have a clearer idea of how it got there if there was indeed a bug.

0 comments

8 comments · 4 top-level

lliamander6y ago· 2 in thread

> but that can often force a redesign simply to reduce the state space

I'm convinced that this idea, or something similar, is essentially what it means to write "algorithmic code".

At a certain level, all code is just an algorithm (i.e. logic + control). But when we talk about Algorithms that one my find in a book on such things, inevitably what you have is code that was written to avoid unnecessary states in order to enforce certain guarantees with regard to performance, security, fault-tolerance, or some other desirable property.

pjc50OP6y ago

To me, there's an "algorithm" vs "business logic" continuum, where algorithms operate on cleanly specified mathematical operands and the difficulty is .. mathematical, while business logic isn't conceptually complicated but can be very wordy.

A lot of the work in translating a business spec into algorithms is what JoeAltmaier did: enumerate all the cases. You end up with boxes labelled "on Thursdays when the user is in the US Virgin Islands and is using the compact UI", with conflicting assumptions from the postit notes taken from the meetings, and someone has to go and check what should happen in that box.

lliamander6y ago

I agree that there is a continuum. I would say it's based on how easy it is to generalize over the state space. Stuff like sorting, cryptography, and consensus algorithms are often quite amenable to clean generalizations (which is often why abstract algebra can be useful in those domains[0]).

There's also another axis which is the strength of the guarantees provided. Most interesting software, whether it is has many or few special cases, has strong guarantees that one is trying to make. Often in order to make stronger guarantees you have to add special case handling, but software which manages to have both strong guarantees and few special cases is the most interesting kind.

But even stuff that is littered with special cases, whether it's query engines, control systems, workflow engines, resource schedulers, or chat applications, I think can benefit from the type of algorithmic thinking which strives to make stronger guarantees with fewer special cases.

[0]https://news.ycombinator.com/item?id=22868840

heymijo6y ago· 2 in thread

Thank you, that's helpful.

Is a Mealy state machine implied in your description?

pjc50OP6y ago

I too have to look the Moore/Mealy distinction up every time, but yes.

The real trick is finding all the state machines you've built in your program without noticing. Or are contained in dependencies. Parsers, TCP, SSL. Authentication is a state machine that usually has two states but may have more; places like Amazon have "we know who you are but you've not entered your password this session", for example. Anything involving message delivery. Anything transactional.

auggierose6y ago

haven't heard that term in ages :-) pretty much not since my first computer science lecture given by Wilfried Brauer :-D

JoeAltmaier6y ago

Yes! This, so much this.

At the hardware level there are countable events (interrupt, reprogram the device, change the timer list, callback, call from callback, etc) that can be listed and all combinations dealt with.

I recall part of the solution was, scheduling callbacks. So there wasn't infinite recursion (call a timer expiration callback, have it re-start the timer, have it expire, call THAT callback and so on).

vikiomega96y ago

Great advice on immutability, separation of concerns/domain logic, and side effects. I think modern languages or tooling should somehow enforce this. I think a lot of code will be better off for it. Specific patterns/zen (like another comment below) is what helps.

j / k navigate · click thread line to collapse

0 comments

8 comments · 4 top-level

lliamander6y ago· 2 in thread

> but that can often force a redesign simply to reduce the state space

I'm convinced that this idea, or something similar, is essentially what it means to write "algorithmic code".

pjc50OP6y ago

lliamander6y ago

[0]https://news.ycombinator.com/item?id=22868840

heymijo6y ago· 2 in thread

Thank you, that's helpful.

Is a Mealy state machine implied in your description?

pjc50OP6y ago

I too have to look the Moore/Mealy distinction up every time, but yes.

auggierose6y ago

haven't heard that term in ages :-) pretty much not since my first computer science lecture given by Wilfried Brauer :-D

JoeAltmaier6y ago

Yes! This, so much this.

At the hardware level there are countable events (interrupt, reprogram the device, change the timer list, callback, call from callback, etc) that can be listed and all combinations dealt with.

vikiomega96y ago

j / k navigate · click thread line to collapse