@monoidmusician it's okay if you're not sure what I mean because I'm not either. I started writing a blog post about it ages ago, got sidetracked, and forgot most of the details I'd intended to write down.
but, this might help: imperative programs without recursion, if they're limited to making control-flow decisions based on input that you can think of like an external stream of events, are equivalent to DFAs. to get NFAs, imagine JavaScript or whatever extended for non-determinism with operations for "fail the current thread" and "try both of these branches in separate threads".
but when threads that previously split reach a common state again, if you can merge their local variables using a semiring-style + operator, then you can merge the threads back into one. as long as the program isn't recursive, that means the maximum number of threads is linear in the length of the program, and the worst-case memory usage for a given program is constant.
https://swtch.com/~rsc/regexp/regexp2.html introduces a bytecode virtual machine for regex matching with these non-determinism operators, and talks about bounds on thread counts and state size. I guess I'm wondering, what if that VM was closer to a full programming language?
"A Play on Regular Expressions" (https://sebfisch.github.io/haskell-regexp/) is the paper that introduced me to two other relevant facts: if you extend a regex matcher with recursion, you get a context-free matcher; and a lot of the usual behaviors of regex engines can be expressed by parameterizing matching over a semiring used as match state. then I figured out that unusual behaviors can also be expressed with semirings: https://jamey.thesharps.us/2023/07/04/breaking-ciphers-with-regular-expressions/
I think there is a way to synthesize all these things into a new programming language with first-class non-determinism in which everything looks like a parsing problem. I don't know if that's useful, but I think it's at least novel?
