Enhancing the FSM sub-language

[whitequark]

It looks like the existing FSM sub-language is not expressive enough (e.g. #195, #205). Right now it is implemented in a very minimal way: only the absolute necessary parts. Predictably, this does not cover some interesting cases.

1. Apart from act, oMigen had delayed_enter. I've never seen it actually used (looks like it is only used in misoc/cores/minicon and misoc/cores/lasmicon) and the implementation seems very wasteful, as it expands the entire delay into FSM states, which has a serious potential to bloat the FSM state register and prevent further optimizations.
2. Apart from ongoing, oMigen had before_entering, before_leaving, after_entering and after_leaving. The after_* methods worked fine, but before_* were prone to combinatorial loops, and IMO are more of an attractive nuisance than a good way to structure your code.
3. Right now, nMigen requires that a state would be defined in exactly one with m.State() block. (@RobertBaruch hit this in Allow multiple with m.State("..."): statements for the same state #195) This does not match oMigen, where any amount of fsm.act statements would work, and they would be appended in execution order. However, @emilazy correctly notes that this does not work the same way as switches (which are priority encoders, with earlier cases overriding later cases), and this could be confusing.
4. Right now, m.next can only be written, not accessed. (@RobertBaruch hit this in Consider being able to access FSM next #205) This does match oMigen, but could be useful in some cases. @emilazy notes that having a write-only property is confusing, however, we don't currently have anything like first-class enumerated signals, so it's not clear what m.next would even return; certainly it could not be a string.

[whitequark]

I'm not entirely sure how to improve the FSM sub-language in a principled way. I'm thinking that maybe some sort of higher-order facility abstracting over FSMs could be useful, OCaml's Menhir comes to mind.

[RobertBaruch]

Not a huge fan of programming in the future tense :) Issue #195 seems minor to me, and probably not worth it unless there's a compelling reason. #205 seems nicer to have, but also not entirely necessary (since I solved my use-case by abstracting out the actions I wanted to take into functions)...

[whitequark]

Not a huge fan of programming in the future tense :)

"Programming in the future tense"?

[RobertBaruch]

Odd -- I can't even Google that term, I thought it was more widely known. Anyway, "programming in the future tense" is writing code that could be useful hypothetically, but is not of immediate use. Future-tense code especially doesn't get the bugs shaken out of it through use, or doesn't get well thought-out because the use cases aren't entirely clear.

On the other hand, if you know the use-cases, then it isn't future-tense coding to address them.

[emilazy]

The normie term is YAGNI.

I like PL; I think all my programming is done in the future tense.

[RobertBaruch]

Oh right, YAGNI! In any case, it's nice to have examples lined up of how a new feature is/should be used. That's all I'm really trying to say (badly) -- the features come from the uses.

[whitequark]

In this specific case, I have long known that nMigen's FSM needs either enhancement or a layer on top of that to do things like constructing FSM-based streaming parsers in Yumewatari. You didn't have this context though.

As for "YAGNI", well, this works nicely with normal application code, but not when you're designing a programming language. If every feature is added in an ad-hoc way to cover the narrowest possible use case (as opposed to being explicitly fit into the big picture), you end up with something like PHP or Ruby. (Not to say those are bad languages, necessarily.)

[RobertBaruch]

It is true! In any case, aside from my observations of #195 and #205 I don't have much else useful to say. I'll keep writing code and if I hit something that would be nice to have, I'll add another issue.

[awygle]

As mentioned on Twitter, an additional enhancement that I found myself reaching for (although it may not actually be the best design) is a way to do something like this:

out = Signal()
with m.FSM(domain="pos", reset="RESET") as fsm:
    held_state = fsm.StateType() # pseudocode
    with m.State("A"):
        m.d.sync += out.eq(1)
        held_state = "B" # pseudocode
        m.next = "DELAY"
    with m.State("B"):
        m.d.sync += out.eq(0)
        held_state = "A"
        m.next = "DELAY"
    with m.State("DELAY"):
        m.next = held_state

As indicated in the example, I usually use this pattern for a generic "DELAY" state (a real use case would have a counter register as well, most likely) for use between "active" states, but it's sometimes useful in other situations as well.

This may be a Very Bad way to approach this problem but it is apparently not possible in nmigen today.

ETA: it's also odd to me that it's m.next = instead of fsm.next = to transition to the next state... could you explain why that is? What happens if there are multiple FSMs in one elaborate() method?

[whitequark]

an additional enhancement that I found myself reaching for

Aha, I see now what you want. There is a minor issue: such an FSM is inherently harder (sometimes impossible) to analyze and transform. Right now the state variable is a hidden, local detail; in your snippet, you could easily send it outside of that module, save to non-volatile memory, etc. That means that opportunistic transformations, like using one-hot instead of straight binary, are impossible, and the encoding should be considered stable and preserved forever across nMigen versions.

That's not necessarily bad, but it's a restriction that nMigen currently does not have to observe.

ETA: it's also odd to me that it's m.next = instead of fsm.next = to transition to the next state... could you explain why that is?

It's a quirk of the current syntax. There's no fundamental reason it's done like that. It should be improved.

What happens if there are multiple FSMs in one elaborate() method?

You can change the state of the innermost FSM (relative to the m.next = statement) only.

[awygle]

Writing a bit more nMigen now, I can see the utility of the after_entering method. I'd also love a way to more literately express "on simple boolean condition, transition to state", rather than intermixing it with the "while in this state do this" code. Hope that's comprehensible...