3 ms·

Crem: Compositional Representable Executable Machines

63 points by ingve 4y ago

samsquire 4y ago
I am too trying to design a state machine representation/syntax that is data, not code. I find everyone's representation of state machines in code to be too complicated and hard to read. Here's mine, it represents async/await coordination between different threads. When an "fork" is run, the current task forks a task to another thread. What goes before the equals symbol is a case that must be matched before passing to the next one. The "atom(parameter)" syntax is a fact or a predicate. A list of facts is separated by space and each one must match before passing to the next batch of facts, separated by "|". A is a task. B is a task. Numbers are threads. Curly brackets represent parallel state machines. next_free_thread = 2 task(A) thread(1) assignment(A, 1) = running_on(A, 1) | paused(A, 1) running_on(A, 1) thread(1) assignment(A, 1) thread_free(next_free_thread) = fork(A, B) | send_task_to_thread(B, next_free_thread) | running_on(B, 2) paused(B, 1) running_on(A, 1) | { yield(B, returnvalue) | paused(B, 2) } { await(A, B, returnvalue) | paused(A, 1) } | send_returnvalue(B, A, returnvalue) The runtime for this state machine would read that syntax from a file, and it would have an API where you "fire" facts and retract them. Attach handlers to state lines and you have an easy to adapt state machine that is powerful.
- rwmj 4y ago
  You should definitely make your states hierarchical: https://www.sciencedirect.com/science/article/pii/0167642387900359 https://www.sciencedirect.com/science/article/pii/0167642387... https://statecharts.dev/what-is-a-statechart.html https://statecharts.dev/what-is-a-statechart.html That's a much better way to manage the complexity of large state machines. But I think the problem you're going to find with trying to make a "pure data" representation is how can you express a next state for a state machine if that next state depends on some decision made by running some code? You'll end up just expressing the code in an alternate language. (Maybe there's a way of doing it but I'm not seeing it ...) Here's a custom state machine representation we came up with a while back to express the state transitions of quite a complex protocol. It looks like code (in fact, the file is *.c) but it's not normal C. It works more like yacc in that the code fragments are disentangled from the state machine and output to another C file where there is a huge, generated switch statement, but no one has to write or maintain the switch statement. https://gitlab.com/nbdkit/libnbd/-/blob/424420a55bab1a8ec9acffe684e0bbd0dc4ec45d/generator/state_machine.ml#L262 https://gitlab.com/nbdkit/libnbd/-/blob/424420a55bab1a8ec9ac... https://gitlab.com/nbdkit/libnbd/-/blob/424420a55bab1a8ec9acffe684e0bbd0dc4ec45d/generator/states-newstyle.c#L113 https://gitlab.com/nbdkit/libnbd/-/blob/424420a55bab1a8ec9ac...

63 points by ingve 4y ago

I am too trying to design a state machine representation/syntax that is data, not code. I find everyone's representation of state machines in code to be too complicated and hard to read. Here's mine, it represents async/await coordination between different threads. When an "fork" is run, the current task forks a task to another thread. What goes before the equals symbol is a case that must be matched before passing to the next one. The "atom(parameter)" syntax is a fact or a predicate. A list of facts is separated by space and each one must match before passing to the next batch of facts, separated by "|". A is a task. B is a task. Numbers are threads. Curly brackets represent parallel state machines. next_free_thread = 2 task(A) thread(1) assignment(A, 1) = running_on(A, 1) | paused(A, 1) running_on(A, 1) thread(1) assignment(A, 1) thread_free(next_free_thread) = fork(A, B) | send_task_to_thread(B, next_free_thread) | running_on(B, 2) paused(B, 1) running_on(A, 1) | { yield(B, returnvalue) | paused(B, 2) } { await(A, B, returnvalue) | paused(A, 1) } | send_returnvalue(B, A, returnvalue) The runtime for this state machine would read that syntax from a file, and it would have an API where you "fire" facts and retract them. Attach handlers to state lines and you have an easy to adapt state machine that is powerful.

rwmj 4y ago
You should definitely make your states hierarchical: https://www.sciencedirect.com/science/article/pii/0167642387900359 https://www.sciencedirect.com/science/article/pii/0167642387... https://statecharts.dev/what-is-a-statechart.html https://statecharts.dev/what-is-a-statechart.html That's a much better way to manage the complexity of large state machines. But I think the problem you're going to find with trying to make a "pure data" representation is how can you express a next state for a state machine if that next state depends on some decision made by running some code? You'll end up just expressing the code in an alternate language. (Maybe there's a way of doing it but I'm not seeing it ...) Here's a custom state machine representation we came up with a while back to express the state transitions of quite a complex protocol. It looks like code (in fact, the file is *.c) but it's not normal C. It works more like yacc in that the code fragments are disentangled from the state machine and output to another C file where there is a huge, generated switch statement, but no one has to write or maintain the switch statement. https://gitlab.com/nbdkit/libnbd/-/blob/424420a55bab1a8ec9acffe684e0bbd0dc4ec45d/generator/state_machine.ml#L262 https://gitlab.com/nbdkit/libnbd/-/blob/424420a55bab1a8ec9ac... https://gitlab.com/nbdkit/libnbd/-/blob/424420a55bab1a8ec9acffe684e0bbd0dc4ec45d/generator/states-newstyle.c#L113 https://gitlab.com/nbdkit/libnbd/-/blob/424420a55bab1a8ec9ac...