[HN Gopher] Polystate: Composable Finite State Machines
___________________________________________________________________
Polystate: Composable Finite State Machines
Author : goless
Score : 101 points
Date : 2025-06-23 01:47 UTC (21 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| goless wrote:
| 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.
| noelwelsh wrote:
| 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).
| loa_in_ wrote:
| 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.
| goless wrote:
| 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?
| noelwelsh wrote:
| 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.
| goless wrote:
| 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.
| goless wrote:
| From this perspective, do you think my previous
| description is accurate?
| TimorousBestie wrote:
| > 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.
| goless wrote:
| 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?
| goless wrote:
| 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.
| solomonb wrote:
| 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/
| goless wrote:
| 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...
| solomonb wrote:
| Right on, I'll take a look at your haskell code this week.
| crq-yml wrote:
| 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.
| goless wrote:
| 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.
| physix wrote:
| 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.
| goless wrote:
| 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.
| _0ffh wrote:
| 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.
| ur-whale wrote:
| > 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.
| noelwelsh wrote:
| There are examples in Scala in the "Indexed Data" chapter of my
| book-in-progress: https://scalawithcats.com/dist/scala-with-
| cats.pdf
| goless wrote:
| reddit:
| https://www.reddit.com/r/Zig/comments/1lhfbjk/polystate_comp...
| goless wrote:
| ziggit: https://ziggit.dev/t/polystate-composable-finite-state-
| machi...
| chrisweekly wrote:
| 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.
| goless wrote:
| Fixed, thanks for your reminder!!
| jasonthorsness wrote:
| 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.
| goless wrote:
| 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.
| irq-1 wrote:
| shouldn't the check pin example end with 'exit' rather than
| 'ready'? .{ Atm.checkPin, Atm.session,
| Atm.ready } } }),
|
| It was the diagram that made me think this.
| tcoff91 wrote:
| Looks kind of like a Zig version of XState, a typescript library
| that I really have enjoyed using.
| goless wrote:
| I don't know much about XState but it looks more like a
| dynamically interpreted execution state machine.
| astahlx wrote:
| How would you compare it to Rust Type States, for example:
| https://cliffle.com/blog/rust-typestate/ ?
| goless wrote:
| I need some time to get to this library.
| goless wrote:
| 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
| rapnie wrote:
| Thanks for that link. I submitted it separately, who knows it
| makes front page.
|
| https://news.ycombinator.com/item?id=44353478
___________________________________________________________________
(page generated 2025-06-23 23:01 UTC)