1. Record the state machine's status at the type level.
2. Achieve composable state machines through type composition.
Practical Effects of Polystate
1. Define the program's overall behavior through compositional declarations. This means we gain the ability to specify the program's overall behavior at the type level. This significantly improves the correctness of imperative program structures. This programming style also encourages us to redesign the program's state from the perspective of types and composition, thereby enhancing code composability.
2. Build complex state machines by composing simple states. For the first time, we can achieve semantic-level code reuse through type composition. In other words, we have found a way to express semantic-level code reuse at the type level. This approach achieves three effects simultaneously: conciseness, correctness, and safety.
3. Automatically generate state diagrams. Since the program's overall behavior is determined by declarations, polystate can automatically generate state diagrams. Users can intuitively understand the program's overall behavior through these diagrams.
I'm guessing you're not a native English speaker. Your descriptions could use some work. A few examples:
"For the first time, we can achieve semantic-level code reuse through type composition." is, to me, mostly meaningless. This almost certainly isn't the first time someone has done whatever it is you are claiming. What is *semantic-level" code reuse? Calling a library function is code reuse, and I expect that function to have the same semantics every time I call it. Why is type composition necessary to achieve this?
"Define the program's overall behavior through compositional declarations. This means we gain the ability to specify the program's overall behavior at the type level." How does the specifying behavior at the type level follow from composition? I can use composition, at the value level, just fine without types (e.g. in Javascript).
Yes, this effect can be achieved without using composite types. But if it is convenient and easy to achieve this effect through composite types, is it worth it?
I have to admit I'm not very interested in reading the code. I'm not likely to use this library so I'm more interested in a conceptual understanding than in the details that code requires.
Regarding composition, there are at least three ways to compose FSMs:
* Sequential: when one FSM finishes (reaches a final state) it transitions to the start state of another FSM.
* Parallel: two FSMs transition in parallel from the same input
* Nested: when a FSM reaches a certain state, another FSM starts responding to the input. When the second FSM reaches a final state, control returns to the original FSM.
It would help your description if you were clear about the kinds of composition your library supports. The terminology of FSMs is quite consistent and well defined, so I think you should be able to use it to describe what the library does.
The select, inside, and hover states here are all high-level states, and all require two state parameters. And these three states form a small state machine for handling mouse interactive selection.
Can I think of this way of using higher-order state machines as a kind of composition? A semantic composition.
You keep using the term "semantic composition", which does not have any meaning for me.
Take function composition, which is perhaps the best known example of composition. Let's say we have
f(x) = x + 1
g(x) = x * x
The composition (f o g) = g(f(x)) could be called a "semantic" composition because the result has the semantics of the two functions (it increments then doubles). So what does your use of the term actually mean?
In general I feel you need more precision in your description. There is standard terminology for finite state machines and for programming languages that I think you could use. Take, for example, your statement "all require two state parameters". I think these are not value level parameters, but type level parameters. This is an important difference, and you should mention it.
Going back to FSMs, there are several ways you can encode a FSM in a typed programming language. For example:
1. A FSM is a type constructor parameterized by the type of states. This means the FSM cannot transition to states that are not of the correct type, but it does not otherwise constrain transitions.
2. States themselves are type constructors parameterized by the type of states they can transition to. This adds more constraints (and requires more complex types) than the approach above.
Do you see the difference between these and hence the need for clarity and precision in descriptions?
Haha, thanks for your reply, I will improve my documentation to make the descriptions more accurate, and you may raise some issues to help this library better.
As for why semantic composition is used, the following example may be instructive：
yes_or_no(exit,a) This means confirm once before exiting
yes_or_no(yes_or_no(exit,a),a) Confirm twice before exiting
yes_or_no(yes_or_no(yes_or_no(exit,a),a),a) Confirm three times before exiting
This is very similar to the composition you describe.
If there is no name for this way of using state machines, then semantic composition seems appropriate.
Exceptionally, combining two states in a polystate may actually be combining two small state machines, and I think nested selects are sufficient to illustrate this.
Due to my submission yesterday, this diagram can no longer fully accurately express the current state machine, but it can probably be used as an approximate reference.
This sounds more like a product than a composition but I’m not sure. I think the parent is hinting to use established compcomp language. Sipser is a good read for this
It makes perfect sense if one considers the whole description and the field of computer sciences. It reads more like an overview that an explanation and I guess that's too be expected from any project in it's pre-mature stages of development. IMO it reads just fine, but it should delve deeper into the matter after the introduction.
I'm having trouble reading zig code, so I'm not sure how much overlap there is but I have done some work with mealy and moore encoded as co-algebras in haskell:
Yes, FSMs are underestimated in imperative programming. Of course this is probably because before type-safe state machines were available, manual coding was very error-prone.
I've seen them a lot in embedded programming, but I can't be sure if that observation holds in general or just for the environment in which I was working when I did embedded.
Typically it's done through source code generation or a runtime interpreter - state machine systems implementing a "DSL->source code" mechanism have been around for nearly as long as high level languages, and by taking this approach they have a lot of freedom to include compiler techniques of their choosing. If dynamism is called for then the diagram is typically kept in memory and interpreted at runtime.
Doing it through types is intellectually interesting and makes the result more integrated into the edit-compile loop instead of involving a step in the build process or a step of invoking an interpreter, but it might not change the practical state of the art.
In fact, I have introduced this in detail here. It is a kind of finite state machine programming, and everything that FSM can solve is suitable for it.
The automatic diagrams are great. Almost worth using a library like this just for that, since then you know the diagram actually reflects the implementation.
Note the README repeats a typo, twice, "ploystate" - the 1st two references to the package name. You'll def want to fix that pronto, it reduces confidence in quality of do s.
Polystate's Core Design Philosophy
1. Record the state machine's status at the type level.
2. Achieve composable state machines through type composition.
Practical Effects of Polystate
1. Define the program's overall behavior through compositional declarations. This means we gain the ability to specify the program's overall behavior at the type level. This significantly improves the correctness of imperative program structures. This programming style also encourages us to redesign the program's state from the perspective of types and composition, thereby enhancing code composability.
2. Build complex state machines by composing simple states. For the first time, we can achieve semantic-level code reuse through type composition. In other words, we have found a way to express semantic-level code reuse at the type level. This approach achieves three effects simultaneously: conciseness, correctness, and safety.
3. Automatically generate state diagrams. Since the program's overall behavior is determined by declarations, polystate can automatically generate state diagrams. Users can intuitively understand the program's overall behavior through these diagrams.
I'm guessing you're not a native English speaker. Your descriptions could use some work. A few examples:
"For the first time, we can achieve semantic-level code reuse through type composition." is, to me, mostly meaningless. This almost certainly isn't the first time someone has done whatever it is you are claiming. What is *semantic-level" code reuse? Calling a library function is code reuse, and I expect that function to have the same semantics every time I call it. Why is type composition necessary to achieve this?
"Define the program's overall behavior through compositional declarations. This means we gain the ability to specify the program's overall behavior at the type level." How does the specifying behavior at the type level follow from composition? I can use composition, at the value level, just fine without types (e.g. in Javascript).
Yes the expression may not be precise enough, but the example should be accurate enough.
1, https://github.com/sdzx-1/polystate?tab=readme-ov-file#2-imp...
This shows what composition means, and even complex nested selects are described quite precisely by type.
2, https://github.com/sdzx-1/polystate?tab=readme-ov-file#1-com...
Yes, this effect can be achieved without using composite types. But if it is convenient and easy to achieve this effect through composite types, is it worth it?
I have to admit I'm not very interested in reading the code. I'm not likely to use this library so I'm more interested in a conceptual understanding than in the details that code requires.
Regarding composition, there are at least three ways to compose FSMs:
* Sequential: when one FSM finishes (reaches a final state) it transitions to the start state of another FSM.
* Parallel: two FSMs transition in parallel from the same input
* Nested: when a FSM reaches a certain state, another FSM starts responding to the input. When the second FSM reaches a final state, control returns to the original FSM.
It would help your description if you were clear about the kinds of composition your library supports. The terminology of FSMs is quite consistent and well defined, so I think you should be able to use it to describe what the library does.
Is there a way to combine:
Higher order finite state machines that require other states as parameters to work.
https://github.com/sdzx-1/ray-game/blob/master/src/select.zi...
The select, inside, and hover states here are all high-level states, and all require two state parameters. And these three states form a small state machine for handling mouse interactive selection.
Can I think of this way of using higher-order state machines as a kind of composition? A semantic composition.
You keep using the term "semantic composition", which does not have any meaning for me.
Take function composition, which is perhaps the best known example of composition. Let's say we have
f(x) = x + 1
g(x) = x * x
The composition (f o g) = g(f(x)) could be called a "semantic" composition because the result has the semantics of the two functions (it increments then doubles). So what does your use of the term actually mean?
In general I feel you need more precision in your description. There is standard terminology for finite state machines and for programming languages that I think you could use. Take, for example, your statement "all require two state parameters". I think these are not value level parameters, but type level parameters. This is an important difference, and you should mention it.
Going back to FSMs, there are several ways you can encode a FSM in a typed programming language. For example:
1. A FSM is a type constructor parameterized by the type of states. This means the FSM cannot transition to states that are not of the correct type, but it does not otherwise constrain transitions.
2. States themselves are type constructors parameterized by the type of states they can transition to. This adds more constraints (and requires more complex types) than the approach above.
Do you see the difference between these and hence the need for clarity and precision in descriptions?
Haha, thanks for your reply, I will improve my documentation to make the descriptions more accurate, and you may raise some issues to help this library better.
As for why semantic composition is used, the following example may be instructive：
yes_or_no(exit,a) This means confirm once before exiting
yes_or_no(yes_or_no(exit,a),a) Confirm twice before exiting
yes_or_no(yes_or_no(yes_or_no(exit,a),a),a) Confirm three times before exiting
This is very similar to the composition you describe.
This is the actual code: https://github.com/sdzx-1/polystate-examples/blob/fecaffb5b7...
If there is no name for this way of using state machines, then semantic composition seems appropriate.
Exceptionally, combining two states in a polystate may actually be combining two small state machines, and I think nested selects are sufficient to illustrate this.
https://github.com/sdzx-1/ray-game/blob/9646bc3c0f1c11314aaf...
How do you understand such behavior?
https://github.com/sdzx-1/polystate/raw/master/data/graph.pn...
This is the state diagram combining two selects!
Due to my submission yesterday, this diagram can no longer fully accurately express the current state machine, but it can probably be used as an approximate reference.
This sounds more like a product than a composition but I’m not sure. I think the parent is hinting to use established compcomp language. Sipser is a good read for this
I'm not sure if this is a new form of state machine.
If you look at the code here you'll see that the select state uses some functions from the parameter state.
https://github.com/sdzx-1/ray-game/blob/master/src/select.zi...
So you can see that the select state itself is incomplete, and the parameter state completes it.
It doesn't seem to be any of the 3 described above.
Perhaps it is reasonable to call it semantic composition.
Here I must mention the great advantage of the Zig language: it has the expressiveness of a dynamic language and the type safety of a static language.
From this perspective, do you think my previous description is accurate?
> This almost certainly isn't the first time someone has done whatever it is you are claiming.
I’ve seen category theory papers on this and related topics, but I haven’t seen code in the wild. Have you?
IME this kind of finite state machine business code (as opposed to a FSM embedded in an algorithm somewhere) is written as a one-off each time.
E.g., https://arxiv.org/abs/1808.05415 comes to mind. David I. Spivak has also done some work on composition of systems that is relevant.
It makes perfect sense if one considers the whole description and the field of computer sciences. It reads more like an overview that an explanation and I guess that's too be expected from any project in it's pre-mature stages of development. IMO it reads just fine, but it should delve deeper into the matter after the introduction.
How to Properly Use Polystate?
The correct way to use polystate is: reason about program behavior through symbols, then transform these symbols into code.
https://github.com/sdzx-1/ray-game/blob/master/How-to-proper...
Hi everyone, I developed an interesting library Polystate: Composable Finite State Machines
Since I only have experience in haskell and zig, I'm curious if there are other languages or libraries with similar implementations?
I'm having trouble reading zig code, so I'm not sure how much overlap there is but I have done some work with mealy and moore encoded as co-algebras in haskell:
https://blog.cofree.coffee/2025-03-05-chat-bots-revisited/ https://github.com/cofree-coffee/cofree-bot
Also using the lens library to encode moore machines as polynomial functors: https://blog.cofree.coffee/2024-07-02-lensy-moore/
Thanks for your reply, I will try to understand your code carefully, which may take some time.
I have a raw haskell prototype of polystate here, maybe it will help you. https://github.com/sdzx-1/typed-gui/blob/main/examples/todoL...
Right on, I'll take a look at your haskell code this week.
We developed an Entity DBMS where the entities are FSMs.
https://medium.com/@paul_42036/entity-workflows-for-event-dr...
I believe that FSMs are a very powerful approach, even for building entire systems. So much so, that it forms a core part of our product.
Yes, FSMs are underestimated in imperative programming. Of course this is probably because before type-safe state machines were available, manual coding was very error-prone.
I've seen them a lot in embedded programming, but I can't be sure if that observation holds in general or just for the environment in which I was working when I did embedded.
It relies heavily on compile-time evaluation of zig to achieve this, and I'm not sure if the same effect can be achieved in other languages.
Typically it's done through source code generation or a runtime interpreter - state machine systems implementing a "DSL->source code" mechanism have been around for nearly as long as high level languages, and by taking this approach they have a lot of freedom to include compiler techniques of their choosing. If dynamism is called for then the diagram is typically kept in memory and interpreted at runtime.
Doing it through types is intellectually interesting and makes the result more integrated into the edit-compile loop instead of involving a step in the build process or a step of invoking an interpreter, but it might not change the practical state of the art.
Yes, but their expressiveness may vary. An important role of polystate is code reuse. It can express more complex states and still be type-safe.
There are examples in Scala in the "Indexed Data" chapter of my book-in-progress: https://scalawithcats.com/dist/scala-with-cats.pdf
I once wrote a library typed-fsm https://github.com/sdzx-1/typed-fsm
It has a completely type-safe finite state machine, and it does not require additional programming conventions.
It relies on a special monad: Mcbride Indexed Monad, which can model uncertainty in terms of type.
Are you using this monad here?
Here is a concrete ATM demo https://github.com/sdzx-1/typed-fsm/tree/main/examples/ATM
In fact, relying on this monad, we can achieve full type safety for multi-role communication.
https://github.com/sdzx-1/typed-session
> Hi everyone, I developed an interesting library Polystate
A short blurb on the github explaining what applications this may have and how you would use it to solve problems would be very helpful.
In fact, I have introduced this in detail here. It is a kind of finite state machine programming, and everything that FSM can solve is suitable for it.
Looks kind of like a Zig version of XState, a typescript library that I really have enjoyed using.
I don't know much about XState but it looks more like a dynamically interpreted execution state machine.
The automatic diagrams are great. Almost worth using a library like this just for that, since then you know the diagram actually reflects the implementation.
Yes, all my examples have state diagrams, they are automatically generated and are an effective way for me to understand the structure of the program.
shouldn't the check pin example end with 'exit' rather than 'ready'?
It was the diagram that made me think this.Haha, this is just a demo, written casually, you can change this to exit, and then as you expected, the program will exit directly.
Try modifying it yourself, you will fall in love with this way of programming.
How would you compare it to Rust Type States, for example: https://cliffle.com/blog/rust-typestate/ ?
I need some time to get to this library.
Sorry, I am not familiar with Rust. Although I try hard to understand this library, I cannot say that I understand it.
I have two questions here:
1. How to express uncertain state in type. In my example, it is implemented by union (enum) + Witness https://github.com/sdzx-1/polystate-examples/blob/fecaffb5b7...
2. I don't seem to see the possibility of combining state machines
Thanks for that link. I submitted it separately, who knows it makes front page.
https://news.ycombinator.com/item?id=44353478
Looks interesting.
Note the README repeats a typo, twice, "ploystate" - the 1st two references to the package name. You'll def want to fix that pronto, it reduces confidence in quality of do s.
Fixed, thanks for your reminder!!
reddit: https://www.reddit.com/r/Zig/comments/1lhfbjk/polystate_comp...
ziggit: https://ziggit.dev/t/polystate-composable-finite-state-machi...