# colored-petri-nets

This is a library to describe colored Petri nets and CPN++, an enhanced version of colored Petri nets for modeling programs.

© Felix Freiberger, 2018-2019, Saarland University


## A Word of Caution

This library is quite experimental. For now, there is no proper documentation, and the API shouldn't be considered stable.


## Petri Net Semantics

In this library, the colors of tokens in the nets are simple JavaScript values, consisting of booleans, integers, arrays and objects. For example, these are valid colors:

- `true`
- `42`
- `"Hello World!`
- `[42, []]`
- `{ object: {}, array: [] }`

Transitions work by having patterns on incoming flows and expressions on outgoing flows. A transition is enabled if

- all incoming flows can find a token that _matches_ the pattern,
- the incoming flows produce bindings that are _compatible_ and
- the resulting binding fulfills the guard.

If a transition is executed, the outgoing flows produce tokens corresponding to their expressions, which may reference the binding.

As an example, a transition with two inflows with the patterns `[ x ]` and `x`, the guard `x > 10` and an outflow with the expression `(x + 1) * 2` behaves like this:

- If the inflows try to read `5` and `5`, respectively, the transition is not enabled, because the first pattern expects an array.
- If the inflows try to read `[ 4 ]` and `5`, respectively, the transition is not enabled, because the bindings are not compatible.
- If the inflows try to read `[ 5 ]` and `5`, respectively, the transition is not enabled, because the binding does not satisfy the guard.
If the inflows try to read `[ 20 ]` and `20`, respectively, the transition is enabled, and the outflow produces a token colored `42`.

The syntax for patterns and expressions is inspired by JavaScript. Here are examples of valid patterns:

- `x`
- `_` (a wildcard, drops the value)
- `[]`
- `[a, b, c]`
- `[a, b, [c, d]]`
- `[a, , c]` (equivalent to `[a, _, c]`)
- `[a, b, _]`
- `{}`
- `{ a: a, b: c }`
- `{ a, b }`
- `{ a }`
- `[a, { b : c, d: [e, f] }]`
- `{ one, two, ...rest }` (`rest` will be an object with all properties except `one` and `two`)
- `{ ...obj }` (equivalent to `obj` except it rejects non-objects)
- `[ one, two, ...rest ]` (`rest` will be an array with the all remaining items)
- `[ ...arr ]` (equivalent to `arr` except it rejects non-arrays)

Here are examples of valid expressions:

- `var`
- `1337`
- `true`
- `"hello world"`
- `"hello \"world"`
- `"back\\slash"`
- `1 + 28`
- `1 - 28`
- `"hello" + " " + "world"`
- `3 * 9`
- `a * ( b + c)`
- `1 > 2`
- `2 >= 2`
- `2 <= 1`
- `2 < 1`
- `2 == 1`
- `2 != 1`
- `a || b`
- `a && b`
- `!a`
- `[]`
- `[ 42, 1337-1336 ]`
- `[1, 1, 0].length`
- `[9, 8] @ [7] @ [6, 5]` (array concatenation)
- `{}`
- `{a:7,  b : x, c }`
- `{ a, ...b, c }`
- `{ a: 1, ...x, b: 2, ...y, a: 2 }`
- `{ x, y }.y.z`
- `true ? 42 : 1337`
- `eval(a + b, vars)` (evaluates `a + b` in the binding expressed by the object `vars`)


## An Example

The following Petri net computes the first 10 numbers of the Fibonacci sequence and puts a token with an array of them in the place `done`:

```
{
    "places": [
        {
            "key": "calc",
            "displayName": "calculate Fibonacci sequence",
            "extensions": {}
        },
        {
            "key": "done",
            "displayName": "calculation finished",
            "extensions": {}
        }
    ],
    "transitions": [
        {
            "key": "add-fib",
            "displayName": "add one fibonacci number",
            "guard": "list.length < 10",
            "inFlows": [
                {
                    "source": "calc",
                    "pattern": "{ a, b, list }"
                }
            ],
            "outFlows": [
                {
                    "target": "calc",
                    "expression": "{ a: b, b: a + b, list: list @ [a] }"
                }
            ],
            "extensions": {}
        },
        {
            "key": "exit",
            "displayName": "exit the main loop",
            "guard": "list.length == 10",
            "inFlows": [
                {
                    "source": "calc",
                    "pattern": "{ list }"
                }
            ],
            "outFlows": [
                {
                    "target": "done",
                    "expression": "list"
                }
            ],
            "extensions": {}
        }
    ],
    "initialMarking": {
        "tokens": {
            "calc": [
                {
                    "color": {
                        "a": 0,
                        "b": 1,
                        "list": []
                    }
                }
            ]
        },
        "extensions": {}
    }
}
```

More specifially, the above is the JSON object representation of the net. The following code parses this to a JavaScript object, converts it to a real `PetriNet` instance, then uses the API to query the behavior of the net:

```
const { PetriNet } = require('@pseuco/colored-petri-nets');

const fs = require('fs');

const netString = fs.readFileSync('net.json');
const netObject = JSON.parse(netString);

// build an actual PetriNet object from the plain object representation.
const net = PetriNet.fromObject(netObject);

let marking = net.initialMarking;

while (true) {
    console.log(JSON.stringify(marking.toObject()));

    let successors = marking.enabledMoves();
    if (successors.length > 1) throw new Error("Found nondeterminism!");
    if (successors.length < 1) {
        console.log("Terminated.");
        return;
    }

    console.log(` ↓ ${successors[0].transition.displayName}`);

    marking = successors[0].marking;
}
```