stackdump

Petri nets are a mathematical tool used to model and analyze systems that involve concurrency, synchronization, and resource sharing. They are useful in a variety of fields, including computer science, engineering, and biology.

One way to view Petri nets is to think of them as a way of accounting for the number of possible ways a user can interact with a system over time. Recall that a Petri net consists of a set of places and a set of transitions. Each place represents a resource or state of the system, while each transition represents a change or event that can occur in the system. A Petri net describes the rules for how these changes can occur and how resources can be shared between transitions.

Consider this Petri-Net composed of actions only.

The gamepad model provides a ‘virtual gamepad’ with buttons. Just like a gamepad in the real world, this model doesn’t have a ‘state’ of it’s own, thus this Petri-net also has no places or connections between actions.

Consider a simple move from a Head-to-Head fighting game. When a player is mashing buttons randomly, sometimes you get lucky and construct a combination move. For example an Upper-Cut could be [ Down, Up, A ]

By adding some state to the model, (and transitions and guards) we can refine the Petri-Net to detect our combo move.

In the above diagram, we have declared ‘noop’ i.e. ‘no-operations’ state, and rules to disallow any other buttons that we do not use in this sequence.

Additionally, we add two interstitial states that enforce that we perform the moves in the proper order.

When we use Petri nets for programming, a programmer can represent the program's states in an explicit manner. This allows the developer and users alike to visualize the flow of the program and the dependencies between different parts of the program. By breaking down the program into smaller components, the programmer can better understand the behavior of the system and how different parts of the program interact with each other.

Now let’s consider a more elaborate move sequence: The Konami Code

(NOTE: when playing with two players, we have added […‘select’, ‘start’]

Petri nets provides a way for programmers to decompose the state of a program and reason about its behavior in a structured and systematic way.

For example, we can think about the overall complexity of these two models, by comparing the code used to generate them.

First let’s see our general solution for any string of non-repeating moves:

Now compare with this code written specifically to model the konami code:

The first sequence is much easier to compose, since we need only to string the required moves together. The Konami code essentially has to be composed directly as a ‘program’ itself. The simpler model is easer to compose, and to generalize for all non-repeating sequences.

There is also a trade-off at play: We could compose the Konami code in a similar manner, but we would have to expand the model to have a state for every move in the sequence.

Conclusion

Petri nets can be thought of as a form of programming synthesis because they provide a way to describe a program's behavior without specifying its implementation. Instead of directly writing code, a programmer can use Petri nets to model the system's state and transitions. This can be useful in situations where the programmer needs to quickly prototype or explore different design choices.

By comparing these examples, we have demonstrated that Petri-nets can model deterministic and non-deterministic automata depending on how state is used. Furthermore, we have seen that the more a programmer can refine and constrain models, the less complex, and more general our code can become. Ultimately, there is always a trade-off cost between interoperability, code size, and memory usage. Explicitly modeling these properties gives the programmer a very sharp tool for reasoning about them up front.

See a live-demo of these models, or view the source models on github.