stackdump

Things I learned while programming as a Petri-net maximalist.

This blog post is NOT about LLMs!! The term Model is barely mentioned now-a-days without a prefix — as “Large Language Models” have reshaped the technical landscape.

A model is an abstract representation of a process that is composed of both behaviors (actions) and attributes (data). A good model allows for a system to be more predictable and easier to understand. A great model can also reduce the code complexity of a program.

Building Functional Models

Functional programming philosophy tells us that any problem can be solved via a reductionist approach: the developer decomposes a problem into functions, and then re-composes those functions into a solution.

This same paradigm is can be formally applied using petri-net models. First, we model the problem to be solved as a series of events. Then, by linking actions with input and output states, we compose these events into a full solution.

Net Analysis

Petri-nets are a formal analysis tool providing a formal foundation at design time, but we can also use them to make assertions about our program at runtime.

One useful attribute for analysis is reachability:

Given an input state, can the petri-net state machine be transformed into a target state?

Another testable property is boundedness:

Does this net model a closed system? Can a given place ever hold more than N tokens? Does the system ever create or destroy tokens?

The last property we hilight is liveness:

Can the network reach a state where no transformations are possible? under what conditions does the network reach this halting state?

Many of these properties can be analyzed through simulation. The petri-net itself is an executable schema. Pflow leverages this ability to interact with a model as a way to let users perform these checks simply by running model in a browser.

Conclusion

Building models into our code can improve design and the execution. Small models are comprehensible a user and developer alike. For a software developer, using a state machine for problem solving applies rigor at both design-time and program runtime. As a user, models can inform and educate about the state of a running process while interacting with a program. Check out the resources below how to use models in your code:

Visit https://pflow.xyz/docs-petri-net-101 to learn more about petri-nets, or try to compose one yourself using the editor https://pflow.xyz/editor.

Pflow.xyz is an SDK for constructing petri-net smart contracts.

This article explores some features of the PflowDSL – which is an internal DSL to build models embedded in solidity code.

This is an excerpt from a demo model deployed to sepolia-optimism testnet. The above model contains every term that the language allows for, here’s a translation to petri-net terminology.

  • cell()[place] declares a memory location in the ‘state’ of the model
  • func()[transition] declares a transformation that mutates state
  • arrow()[arc]connectes cell() –> func() or func() –> cell
  • guard()[inhibitor arc] an arrow used as a ‘if/unless’ precondition

Some additional attributes of the language:

Declarative Style: Using the DSL is essentially describing the structure of the Petri net (places, transitions, arcs) rather than providing step-by-step instructions on how to build it.

  • Functional Composition: The DSL uses functions like cell, func, arrow, and guard to define individual components and then connect them to form the complete net.
  • Data-Centric: The core data structures are places and transitions, and the functions operate on and modify these structures.

Syntax:

  • Function Calls as Building Blocks: The syntax of function calls in the DSL (cell(...), func(...)) visually resembles Lisp's s-expression syntax, where everything is enclosed in parentheses and the first element is typically the function name.
  • Minimal Syntax: The DSL keeps the syntax quite minimal, focusing on the essential elements needed to define the Petri net.

Altogether, the Pflow SDK provides a way to enrich the syntax of your contract using another derived App-specific language.

Notice that in animation below -

The labels of the model can be used to visualize the state of the contract —also including a red/green coloring to indicate the ‘fireable-ness’ of the transition.

In conclusion

Pflow.xyz, with its internal PflowDSL, offers a novel and expressive approach to building Petri-net smart contracts. By enabling a declarative, functional, and data-centric construction of complex state machines, it enhances the clarity and maintainability of your Solidity code.

Learn more about how to make these models! Explore the solidity API: in the pflow.xyz docs. Or, view source code for the demo on sepolia-optimism testnet block explorer.

We recently participated in Base’s on-chain Summer. full code on github: https://github.com/stackdump/on-chain-summer-2024

How it Started

Our intention for this hackathon was to build out an on-chain crafting game.

We didn’t develop it enough to submit for judging, but we did learn a few things about our design.

  1. Models have a limit of about 100 objects (places,transitions,arcs) for a single contract deployment.

  2. Nodes-as-a-service do not always have a suitable free tier.

  3. Our block-synching approach seemed to scale well enough on testnet.

  4. The onchain model structure can be improved.

Finding Limits

We discovered that models are limited to about 100 total objects including the types: Places, Transitions, Arcs.

Arcs (0.0279 KiB) are about 2-3x as ‘expensive’ in code as a Place (0.0956 KiB) or Transition (0.0872 KiB).

The Initial design we attempted was about 10 Kib (~48 Arc objects) over the limit for a smart contract max initcode size.

Block Synching

Tested free tier usage from these providers.

  • QuickNode – reliable nodes, limited to a single node per project
  • BlastApi – crypto native, supports mainnet/testnet for each project.

QuickNode seemed to provide the most credits in a free tier.

BlastAPI seems to be a crypto native approach to hosted nodes, requiring only a wallet to try it out.

In both cases our testnet api seemed to keep up during normal synching.

Block Synching

Our design utilized a postgres database image from supabase: https://github.com/supabase/postgres

Supabase/postgres comes pre-baked with pgnet and pgcron support.

These two features allows for the creation of a self-synching postgres db, where a cron runs pl/sql functions to import block data every 1 min.

We tested using a local image, and the free tier db-as-a-service from supabase.com. In both tests result success was limited by the API we were using, and the DB instance seemed to perform well enough during our week of testing.

Model Improvements

Upon realizing our space limits += 100 objects, we looked to code that could be removed, generally there was some overhead we could lower ~ 2KiB but the contract size growth was mostly related to the complexity of the design.

In the future we intend to investigate some of the multi-contract & library deployment patterns to attempt to create larger model designs.

Conclusion

Though we learned a lot, ultimately we felt that our project wasn’t developed enough to present for judging.

You can see the crafting system design we created below.

You can out the model here: https://pflow.dev/p/zb2rhnuKVVerJd9GA2H4VghgnVUxjUTajKhuaC7XJXjaVUzna/

Pflow.xyz uses petri-nets as a modeling language.

Petri-net structures can be considered a ‘Metamodel’. Using a Metamodel is like having a blueprint for making blueprints.

Here’s an analogy:

  1. Model: A recipe for making a chocolate cake.

  2. Metamodel: A guide on how to write recipes for any type of cake, not just chocolate.

Why is this useful?

Petri-nets have basic structures that are composable.

These structures follow a Metamodel (rules for composition), that form a basis to construct state-machines that describe an appliction-specific process.

This simplistic design is the secret sauce that allows for anyone to compose complex models using a visual editor that in turn can be converted to solidity.

Learn More: https://pflow.xyz/

I have been preparing to launch a Dapp pflow.xyz on Optimism Mainnet. This felt like an appropriate time to look back at at that first moment of inspiration.

I first conceived of this project 10 years ago (while taking a shower) – and immediately bought a domain name: bitwrap.io.

My original inspiration was bitcoin’s OP_RETURN though I was mining Litecoin at that time due to hash difficulty.

Some time before that I attended a meetup in La Jolla, Ca where Vitalik gave a remote presentation about Ethereum’s upcoming DAO – I was honored to get to ask him an embarrassingly simple question like “How do you make a DAO” – [I think we are collectively still working on that question].

I believe we are now seeing a slow motion revolution happen. A global inversion of the control of data as a public good. Rather than private companies having sole control of data flows, users can now opt-in to leaderless platforms that have incentivized reasons to exist, and to continue existing.

This opens a new space for ideas to intermix, and evolve in a way that could not happen before this web3 commons came into existence.

Even now 10 years later I’m continually inspired to build tools that hasten this inversion, and I can’t wait to see what we build next.

Information wants to flow & “Information wants to be free.” This is why I’m building pflow.xyz

(Verse 1) Back in '39, a young genius did find, A way to chart processes, leaving none behind. Carl Petri, just thirteen, with a vision so keen, Mapped out the flow of systems, a mathematical dream.

(Chorus) Dancing through the nets, where tokens freely roam, In places and transitions, they find their way home. A bipartite graph, so elegantly composed, Petri nets, where complexity is neatly enclosed.

(Verse 2) From chemistry to computing, his idea took flight, A universal language, turning complexity to light. Arcs and places, transitions in between, A ballet of tokens, in a machine's serene dream.

(Bridge) Non-deterministic, yet so precise, Modeling concurrency, cutting through like a knife. Enabled transitions, a firing sequence so bright, Petri nets illuminate, the theoretical night.

(Verse 3) With every token's journey, a story unfolds, A dance of possibilities, as the future holds. From discrete events to continuous flow, Petri nets capture dynamics, as they go.

(Chorus) Dancing through the nets, where tokens freely roam, In places and transitions, they find their way home. A graphical notation, for processes so wide, Petri nets, our faithful guide, with Carl by our side.

(Outro) So here's to Carl Petri, and his brilliant insight, A mathematical model, to bring complexity to light. Through places and transitions, our systems we compose, With Petri nets, the path of clarity brightly glows.

1. Workflow Model

Definition: The Workflow model represents the structured sequence of processes or activities aimed at accomplishing a specific task or goal. It defines the flow of tasks, decisions, and information in organizational processes or systems.

Core Components:

  • Activities: Discrete tasks or operations within the workflow.
  • Transitions: The movement or progression from one activity to another.
  • Actors: Entities (either human or automated) responsible for performing the activities.
  • Data: Information that flows through the workflow, being input, manipulated, or output by activities.
  • Triggers: Events or conditions that initiate or influence the flow of activities.

Usage Context: Used in business process management, software development, and automation systems to streamline and optimize processes.

2. Petri-Net Model

Definition: A Petri-net is a mathematical modeling language used for the description and analysis of systems characterized by concurrency, parallelism, synchronization, and nondeterminism. It extends beyond simple workflow models by providing a graphical and mathematical representation of distributed systems.

Core Components:

  • Places: Represent conditions or states of the system.
  • Transitions: Symbolize events that can change the state of the system.
  • Tokens: Denote the presence or absence of certain conditions. The distribution of tokens across places represents the current state of the system.
  • Arcs: Connect places to transitions (and vice versa), dictating the flow of tokens and thus the allowable transitions based on the current state.

Usage Context: Widely used in the fields of computer science and systems engineering for modeling complex systems, analyzing performance, and verifying system properties.

3. Elementary Nets (EN) Model

Definition: Elementary Nets (EN) are a simplified version of Petri-nets focused on the fundamental aspects of system behavior, particularly the notions of causality and conflict without considering complex data or hierarchical structures.

Core Components:

  • Conditions: Similar to places in Petri-nets, conditions represent the state of the system but are more binary in nature, indicating whether a condition is true or false.
  • Events: Analogous to transitions, events denote changes between conditions. An event occurs if and only if all its preconditions are true, and its occurrence results in the postconditions becoming true.
  • Arcs: Define the relationship between conditions and events, indicating which conditions must be true for an event to occur and which conditions become true after an event occurs.

Usage Context: ENs are used for modeling and analyzing simple systems or processes where the focus is on the presence or absence of conditions and the basic causality relationships between events. They serve as a foundational concept for understanding more complex Petri-net variants and are useful in educational settings or initial system design phases.

Each of these models serves different but complementary roles in analyzing and designing systems, from simple workflows to complex systems characterized by concurrent and parallel processes.

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.

Check out our github to learn more: https://github.com/pflow-xyz/