Composable state machines?

[mohamed--abdel-maksoud]

So what's the feature?
Composable state machines

Is this related to a problem? If so, what?
Problem: specifying larger state machines becomes tedious if a state is not hierarchical.

Describe the solution you'd like
I'd like to see if there is a pattern to compose state machines. E.g. create a machine M which consists of 2 sub-machines M1 and M2, and it automatically inherit their internal states and transitions.

Describe alternatives you've considered
None.

Additional context as you see fit
None.

[StoneCypher]

In response

Sorry, I thought I replied to this already. I came back to add more to it and there was nothing there. Started writing this response again yester-tag.

I legitimately apologize for a month-long delay in response. It's been a fucked up month. For example, (points at every single thing in the entire world, in order, but especially things starting with the letter T.)

 

 

Overview

The problem with composition is that it requires a shared understanding of how things work. Superficially that might seem like a silly thing to complain about, but, stick with me.

I'll grant defacto that "composition" isn't a strictly defined term. But as I know it, it's generally used by two camps: the object oriented crowd, and the functional programming crowd. As such I tend to see it through one of two lenses:

1. the functional, ie
   • foo.map(bar).filter(baz) or
   • &foo/0 |> bar/1 |> baz/1 |> quux/1 or
   • Functor[foo].lift(bar andThen baz) or
   • foo = bar . baz . quux or
   • (+%:)/ foo bar or
   • (-> foo bar baz) or
   • foo bar + baz * quux - or
   • if you're in Hell, foo = R.compose(deez, nuts, in_Ramdas_mouth) or whatever
2. the object oriented, ie
   • class Foo { private: bar Job, baz OtherJob, quux FinalJob };

I define these because composition isn't the only way to combine things, and I personally use other strategies to solve the same problem.

Please take an air sickness pill and have a barf bag ready before reading the following paragraph. Do not read while on any form of rug or carpet, or while in a school in a coming-of-age Stephen King film. You have been warned.

Imagine briefly that for some reason you have decided to write some advanced Perl. One of the curious things about Perl is that it is so old and so flexible and has such an old package manager that it did not ship with an object orientation system, so the users decided to cook their own, c-with-classes style. Yeah, and, ... there are many competing incompatible implementations. 15 years after the fighting died down, the language shipped its own, but that's also incompatible and by then nobody wanted to switch to it, so you have the language one, perlobj, moose, mouse, moo, and mo, among others. (No, I'm not making that up. Yes, that's really their big winner list. No, there isn't one called m. Yes, there should be one called m. No, I will not dirty my hands with Perl to fix this. Yes, on the frogurt, you get your choice of toppings. No; the toppings contain sodium benzoate.)

So then you pick one. Great. Next you go out into the cpan world to install your support libraries, and, ... wait, this one needs mouse? But I'm on mo. Okay. Switch to mouse, and ... wait, the other one I'm already using needed mo? Fuck. And this third one I want needs perlobj ...

If I try to pick a composition modality, I exclude the other modalities. (This is facetious fundamentally, because I end up excluding all but one of them anyway, but, ... the point stands. And besides, there are very probably approaches I haven't yet thought of.)

 

 

Let's put an example on the ground

To me, the defacto example of composability in state machines is the traffic grid. Ideally, a city would be describable with three levels of instantiation:

1. A machine that describes a single light
2. A machine that describes a local intersection
3. A machine that describes the overarching street grid

Let's also consider a city with a nightmare street grid. 1 and 2 would both be highly re-usable. 1 would have occasional one-offs; 2 would have frequent one-offs.

 

 

Pics or it didn't happen

Here are some one-off intersections:

 

 

Why composition would help here

Well, to start with, despite that snarky image, something like 80% of intersections in most cities are of one of the five primary types (four-way, four-way with four green arrows, four-way with two green arrows; three-way T intersection; three-way Y intersection,) and almost 95% of lights are of one of the three basic types (three-color, three-color with arrow, three-color with arrow and timed blinking red.) So just being able to re-use those, especially with rotation handled or unimportant, makes an enormous difference to describing, tooling, and debugging the grid.

 

 

Why composition would hurt here

It depends on if we're talking about

1. What I called functional composition
2. What I called object oriented composition
3. Some other thing I haven't talked about

Are there other things? Sure, talk to someone from Prolog or Mozart-Oz or CSS Twitter. Hold your nose and look inside Fortress. Investigate C macros as they were used in the 90s. Or, hell, just go hang out with a large group of Haskell programmers (ha) and ask whether, in increasing order of argument bomb size, events, J-style hooks, Intercal COME FROM, aspects, constraints, and reflection are kinds of composition.

But they're not important now, because those are Martians, and we're fighting human battles. Also, it's animal cruelty to make Haskell people argue about INTERCAL. Their instincts lock and they can never stop, and they die of starvation. No matter how entertaining it is, etc, etc.

(Also, it's funny because I'm'a end up arguing for something not terribly unlike one of those.)

 

ÞE OLDE OBJECTTE ORIENTATIONNE

Let's address OO composition first, because it's simpler. These are the "composition is superior to inheritance" people. 75% of the time, they're right 100% of the time.

class Foo { 
  private: 
    bar Job;
    baz OtherJob;
    quux FinalJob;
};

There are times you want FinalJob in Foo's interface, and there are times you don't. Composition is for the times you don't, which is (checks watch) usually.

If this is what you want, you can do this right now. Stuff's been in place for about three years. I wouldn't recommend it; it's gonna be clunky as fuck. But it'll work.

What you would do is define your data type to include other state machines, then have hooks on your transitions (or whatever) that managed those data members.

Writing this without checking it:

type ExData = {
  member: Machine
};

const InnerMachine = sm`BEENTHERE 'swap' <-> 'swap' DONETHAT`;  // starts in BEENTHERE

const OuterMachine: Machine<ExData> = Machine.from('foo => bar;', { data: { member: InnerMachine } });

OuterMachine.hook_any_transition( () => ({ pass: true, data: (data as any).member.do('swap') }) );

If you are from one of the programming language communities that asserts the value of member composition over inheritance (typically the extended C family and the Java family) - if this is your Northern Style gung-fu - then you may recognize that what I am essentially recommending is dependency injection using the templating type system.

Yes. I fucking support DI. (dramatic defensive stance; leaves whirling around me for no reason.)

Is this grim and terrible? Yes. Is it workable? Sort of. This provides the classical object orientation approach to composition: members communicating with a host in a pseudo-functional protocol (from the perspective of an objective-c / smalltalk / erlang programmer.)

But the notation is gross, and managing that many instances is inconvenient. Also, this loses one of the primary purposes of the state machine: singular unified state. You can argue that as long as it and its members are all resolved, there's a heirarchical state, which is essentially equivalent to an HFSM, but in the meantime, actually working with it is cumbersome as fuck, and as far as I'm concerned that's a deal breaker.

If you are trapped in a sewer, and composed FSL machines are your only way out, and you can't find Splinter, this'll do, pig; this'll do.

I could see this being good enough if you're in a light-compositional approach with a shit-ton of snap-together pieces, because the snap-together junk is the same job, so the overhead is applied and essentially zeroed. By example, if you did a half dozen levels of FSM to engage monster behavior, like "coward" "brave" "psychopath", "vegetarian" "omnivore" "carnivore", "fears_elements" "normal" "loves_elements", "no_tracking" "sight_tracking" "scent_tracking", etc, then this could actually be sort of useful, and I might not hate seeing it.

If you aren't using the state machine - if instead you're writing software that uses the state machine for you - then this might be the right way to go.

 

Þ NEWWE FUNKTYONALLE

It's funny because functional is either older because lisp or older because math, but, i trigress.

This is a lot harder. I'm not entirely sure I think this is practical. I've been thinking about it for a very long time, because I want it, but like

Uniform transformations over machines? I'm genuinely not entirely sure what that would even mean. I can think of a few ways in a stretch you could do something like .forEach, but, no matter what I think of, it seems like it's always better handled in the eventing protocol or the data typesystem. What the fuck is filter on a machine? Reduce? Piping is just the input tape.

But ask yourself. Given the simplistic traffic light machine

Off 'enable' => Red 'next' => Green 'next' => Yellow 'next' => Red;
[Red Yellow Green] 'disable' ~> Off;

What would compose even mean? Would you be composing the actions? The transitions? The states themselves?

What is the conceptual meaning of:

1. compose('next', 'enable') // the actions
2. compose('Green => Yellow', 'Off => Red') // the transitions
3. compose('Red', 'Green') // the states themselves

So ... I guess I think functional-style composition is out. Because I don't know what the hell it means. If you can help me think that through, I'm happy to consider changing, on this point.

 

ÞE OBSCURANTUM APOXADORIA

sorry, I got stuck in the joke, this means "weird shit that isn't c-like or lisp-like"

But you said Prolog and Java Aspects

Yes, and one makes me proud, and the other makes me ashamed. (I miss prolog. Such a beautiful, easy in concept, screamingly difficult in practice language. It took me a week to really understand cut/1.)

There's a straight zillion of these, right? But somehow, in defiance of the central concept of ranking, they all suck worse than the rest of them. Every single one. Especially the ones you learned about on IRC.

• Prolog
  • There's a decent argument that Prolog is pure composition - it depends a little on what you think a Horn Clause really is, and this is a surprisingly (to me) touchy subject - but if you're on the "it isn't" team, pack or function_expansion fairly clearly are
• Mozart-Oz
  • I literally never want to talk about this again, so, just look up why they replaced Oz1 with Oz2
• CSS
  • I would argue that Houdini is fairly clearly composition, and that CSS variables can be used that way
  • CSS is beginning to implement what normal people would call inheritance (it already used that word for something else though)
• Fortress
  • so they do this wild thing where functions compose in a matrix
  • no, that does not mean "functions return values which are arranged in a matrix"
  • they use a mathematical matrix to describe the order in which functions compose, because then you can snap numbers into it to get an affine on which functions actually get run
  • if you know what knuth's algorithm x is, think in terms of raising and lowering loops, except it's handlers
  • my head hurts
  • i am reasonably confident that the reason they implemented it is it's scp-3027, or maybe just a different instance of 3022 (how are you even going to tell them apart)
• C macros as they were used in the 90s
  • ah, the ## macro macro
  • First, find someone who recognizes the name "CodeWarrior"
  • Next, see if the phrase "signed char string" makes them sad
    • If yes, this is a person you can ask why this is a very bad idea
    • If no, you're going to have to call it the token pasting operator, and when someone's done looking it up on MSDN, they will incorrectly tell you that this looks useful and interesting, rather than like a reality ending nightmare bomb
    • If someone tries to argue, and says "the lazy p optimization," or tries to talk about guides or slots, it is already too late for you; call in the airstrike and pray you've saved your team
• Ask Haskell programmers whether, in increasing order of argument bomb size,
  • events
    • there exist these nightmare composition systems in events, where you throw a result out into the air and expect some unknown thing to catch it by name. they're made by old smalltalk people and they are a form of, as weird al would say, jumping into a swimming pool filled with double edged razor blades, except as code. It's a surprisingly literal metaphor
    • I would like to support eventEmitter and figure out an eventConsumer, which would be this, but there are other higher priorities to me unless someone expresses a personal need
  • J-style hooks
    • J is the only programming language where you can say "I want to run a train on it" and not be making a sex joke
    • It's probably for the best that this knowledge generally be left unknown, but, the answer to composition in J is running trains on things
    • In J, you run a train on something to compose something new from existing functions. I am not joking
    • It's usually the child of an existing object
    • The language's author appears to have been completely and entirely blindsided by how this gets read, even though he created his language on the internet
    • This appears to be rule negative thirty four?
    • Anyway, what J calls trains I call "the input and output tape hooks"
  • Intercal COME FROM
    • It's intercal, and yet, it's one of the most reasonable and practical atypical methods for composition
      • That makes my soul hurt, as well as my soul's soul
    • It is literally the inverse of GOTO. You assert that your line of code will be run on entry to the line at the other end
      • But, you know. From the other end
      • It's basically a line-numbered hook. Stop laughing. No, it's intercal, go back to laughing. Now stop laughing again. Now think about it again. Good, you're laughing.
        • You're only allowed to say this if you know how to pronounce the acronym.
    • I guess I would argue that from hooks and transition hooks are essentially equivalent to this, but they don't really make sense as composition mechanisms by this point in the discussion
      • Halt! My foreshadowing sense is tingling
  • aspects
    • It's like Java decided to have a more-most-annoying feature
    • If I have to explain how this is composition, every educational system, even the ones that aren't about computers, have failed
    • There is a system for aspects on the table, called "named hooks", but I'm not done thinking it through
    • These are actually a crazy powerful (in my eyes) mechanism to parameterize machines from the outside
  • constraints
    • Boy, this one's an argument, isn't it
      *

      .foo { display: block; }
      .bar { height: 10em; }
      .baz { width: 10em; }
      .quux { background-color: red; }

      <p class="foo bar baz quux">hello</p>

    • I would argue that's clearly composition, and that the language is the best designed language for composition that has ever existed
    • It's not clear how this would apply to state machines, since there are no identity mechanisms to compose or name types to align
  • reflection
    • in some languages without direct composition, but with reflection, people just do it themselves by manually pulling the function instance by name and arity
    • go example
    • php example

Or, in short, "it depends on what you mean by composition"

 

 

Shut up and be practical, old man

Yeah, I'm trying.

The thing is, the thing I actually think you ought to do is a little weird, so first I have to display why the rest of it is wrong-socks, and it's a big long field of wheat to go a-harvestin' in.

The thing I resent the most about all the approaches prior mentioned is the loss of sole state. Almost no matter how you mung it, if you're making a four intersection grid, and each intersection has four lights, you have 21 machines, and it's not the state, but rather state.machine[state.machine[state]] that you want. And so every time I do that, in my head, at the end I end up throwing together some function to weld that back into a sole name. Like maybe you got intersection #2 then light #0, right? so that's going to come out light_2_0_red or whatever.

And so like.

If you're going to write a function like that anyway, ... wwwwwwwwwwwwwhy not write it before defining the machine, instead of after?

Then you get a single solo machine, no welding, no deferring, no implements, no references, no handles, no nothing.

You can make the thing using standard JS transformations, you can represent the external dataset as actual data, you can regenerate it easily, etc.

It's a whole new ballgame.

In my head, the easiest way to make the transition was to think about it like I was generating a map instead of measuring one, then to make it "generate" the real thing. Once I thought about it that way, it was actually really straightforward.

const intersections: IntersectionType = [
  `5th_highland`: { name: north: `6th_highland`, east: `5th_margrove`, ... },
  ...
];

const intersection_to_fsl(name: string, intersection: IntersectionType): string {
  let res = '';
  if (intersection.north) { res += `${intersection.name} -> ${intersection.north};`;
}

const grid = sm`${intersections.map( 
  (key: string, val: IntersectionType) => 
    intersection_to_fsl(key, val)
).join()}`;

And you can just make an increasing-index singleton to handle instances easily, etc.

It's actually super simple: just look at this through the Unix lens.

One of your primary interfaces with the machine language is strings. This can be handled with string production.

If the language needs to be modified, I'll do it, and a lot of the mechanisms I described are in there already, or under development

But I suspect you'll find that string production is the easiest approach, if you give it a go

 

 

In closing

If you agree, please close this ticket. If not, let's have a discussion

[StoneCypher]

I just realized that if I had called it atomic state then I would have been able to make a bunch of really dumb jokes that are currently unavailable

However I am not willing to edit asterisk the post

[StoneCypher]

@mohamed--abdel-maksoud - please let me know if this resolves your question, and whether I can close this issue

If I don't hear back in a couple weeks I'll close it, and if that's wrong, feel free to re-open with new commentary

[mohamed--abdel-maksoud]

@StoneCypher terribly sorry for the late reply. I read your amazing, poetic response and admired it, then life happened and I forgot to respond here.

Yes, I'm convinced with the solution you proposed. Pre-Generating the compound state to flatten it into a single machine is the simplest way to go (and I'm all for not over-complicating things unnecessarily.) It does need a post-processing (to turn flattened state into properly-structured ones) but the transformation is deterministic.

Thanks again for your response and I suggest you turn it into an article or blog somewhere.

All best!