Hacker News new | comments | show | ask | jobs | submit login
Solving State Explosion with Petri-Nets and Vector Clocks (github.com)
86 points by orksliver on Mar 18, 2017 | hide | past | web | favorite | 11 comments



> The Problem: https://barrgroup.com/Embedded-Systems/How-To/State-Machines...

The article linked spends a lot of time looking at an event-based calculator in VBScript that evidently has a lot of bugs. This is used as a justification for doing what they do (whatever that is? I don't really get it).

My problem with this is the calculator program is very poorly written. One could probably get rid of most of the bugs by using a "single source of truth" state object that includes all state data necessary for all events to act correctly.

The calculator program is buggy because the programmer is apparently not thinking holistically, and is patching bugs as they are found by adding another little state variable here and there. The result is just what you'd expect.

But this is largely a solved problem. The React folks developed Flux[0] to get away from these kinds of situations.

I guess my point is I can't be bothered to go study what a bitwrap is all about given the problem it solves is moot when using good design techniques.

But if someone can explain the problem better, I'm all ears.

[0] https://facebook.github.io/flux/


> But if someone can explain the problem better, I'm all ears.

Assuming you mean it...

Here's a youtube video about the benefits and attributes of event-sourcing. https://www.youtube.com/watch?v=8JKjvY4etTY

Though the demo project is presented in the browser, I'm trying to demonstrate that I can model the game of Tic-Tac-Toe using a much smaller and comprehensible (I hope) graph.

Additionally - because these are mathematical graphs I'm speaking of - it means the 'program' that the graph represents - can be expressed as pure math ( which is nifty to say the least )

A classic DFA would have to represent all the permutations of the board like so: https://upload.wikimedia.org/wikipedia/commons/1/1f/Tic-tac-...


Ah, seeing the tic-tac-toe graph and comparing to yours gives a much better idea what you're trying to do. Interesting! Thanks.


Hi thanks for the feedback:

Just a few comments in response:

> event-based calculator in VBScript

It's mostly coffeescript

> My problem with this is the calculator program is very poorly written.

It's a demo - also the coffeescript is only there to show how the python server works. ( I'll update the docs to explain this better )

> One could probably get rid of most of the bugs by using a "single source of truth" state object that includes all state data necessary for all events to act correctly.

This is in fact what exists -- the "single source of truth" in his case is the python event store - My pooly written UI is only there to forward events server-side.

> But this is largely a solved problem. The React folks developed Flux[0] to get away from these kinds of situations.

Front end UI isn't my focus - building a quality event store is.

I'd love to find other state machine implementations that have similar properties.

Thanks for your post - I know everything is poorly documented - I'll take your criticism as a guide to fixing that.


Thanks for the reply. My comment was in reference to the Visual Basic Calculator program described here: (perhaps "VBScript" was not accurate)

https://barrgroup.com/Embedded-Systems/How-To/State-Machines...

That VB calculator is shown as an example of "The Problem" with event driven programming, but I just see it as an example of why poorly designed programs are hard to reason about and buggy.

I did not see the coffeescript / Python calculator.


Ah I see - maybe I should find a better article to demonstrate the 'State Explosion' Problem.

I thought you were referring to my live demo: https://bitwrap.github.io/#octothorpe


https://www.reddit.com/r/compsci/comments/5yktdo/tictactoe_s... <- Related post focusing only on the TicTacToe State machine.


"Cool! I'm doing DFAs with my fifth graders right now and I'm definitely showing them this." :)


Never heard of petri-nets before, but familiar with ES. Do you have some good references as an intro to petri-nets?


I'm afraid I've learned about them mostly by tinkering - the tool I use is: https://github.com/sarahtattersall/PIPE

I believe "Dining Philosophers" is the usual problem used to introduce the need and concept of Petri-Nets - googled for some examples I found:

http://www.cs.cmu.edu/afs/cs/academic/class/15671-f97/www/le...

Also here's the link to the PNML source used for tic-tac-toe: https://github.com/bitwrap/bitwrap-io/blob/master/bitwrap_io...





Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: