Enhancing the FSM sub-language

[nmigen-issue-migration]

Issue by whitequark
Saturday Sep 14, 2019 at 21:22 GMT
Originally opened as m-labs/nmigen#206

---

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 I can has Cover? #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 Adds Value.matches #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.
5. Right now, m.next can only switch the state of the innermost FSM, not any outer FSM. This is a serious ergonomics problem with complex FSMs because while there is a cumbersome workaround, there's really no good reason for this restriction--it was an oversight.

[nmigen-issue-migration]

Comment by whitequark
Saturday Sep 14, 2019 at 21:23 GMT

---

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.

[nmigen-issue-migration]

Comment by RobertBaruch
Saturday Sep 14, 2019 at 22:47 GMT

---

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)...

[nmigen-issue-migration]

Comment by whitequark
Saturday Sep 14, 2019 at 22:48 GMT

---

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

"Programming in the future tense"?

[nmigen-issue-migration]

Comment by RobertBaruch
Saturday Sep 14, 2019 at 23:50 GMT

---

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.

[nmigen-issue-migration]

Comment by emilazy
Saturday Sep 14, 2019 at 23:59 GMT

---

The normie term is YAGNI.

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

[nmigen-issue-migration]

Comment by RobertBaruch
Sunday Sep 15, 2019 at 00:01 GMT

---

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.

[nmigen-issue-migration]

Comment by whitequark
Sunday Sep 15, 2019 at 00:06 GMT

---

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.)

[nmigen-issue-migration]

Comment by RobertBaruch
Sunday Sep 15, 2019 at 01:39 GMT

---

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.

[nmigen-issue-migration]

Comment by programmerjake
Sunday Sep 15, 2019 at 04:45 GMT

---

a minimal solution to allowing multiple cases is to allow something like:

with m.Case(1, 2, 3):
    do_stuff()

Edit:
turns out I misread the issue title :P

[nmigen-issue-migration]

Comment by awygle
Monday Dec 30, 2019 at 05:49 GMT

---

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?

[nmigen-issue-migration]

Comment by whitequark
Monday Dec 30, 2019 at 22:07 GMT

---

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.

[nmigen-issue-migration]

Comment by awygle
Monday Jan 20, 2020 at 07:08 GMT

---

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...

[anuejn]

Not directly related, but it would be nice if FSMs could be somehow outputted as dot files and rendered with graphviz :)

[anuejn]

Moreover, it came up, that nested FSMs should be supported.
Maybe also with support for flattening?