Links

JSN - The Overview

In this tutorial, I'm going to tell you about the JSN library: what it is and why it was made. But before I start, I'd like to present you a little introduction to Petri Nets, since Petri Nets were my main source of inspiration while working on the JSN library.

Petri Nets

Petri Nets are a mathematical formalism for modeling discrete systems and processes.

In another words, a Petri Net is a triple N = (P, T, F), where:

  • P and T are disjoint finite sets of places and transitions,
  • F is a set of arcs.

WTF

OK, just kidding.

Well, to be honest: Petri Nets are tuples composed of sets and subsets, and that was the way I was introduced to PNs. But I do realise, that it's not the best introduction for people, who don't care about mathematical formalism, and care about practical applications instead.

Perhaps the best way to introduce Petri Nets is to show some simple examples.

A simple example

The example below was taken from Wikipedia:

PetriNet

As you can see, a Petri Net (PN) is composed of:

  • places (those circles),
  • transitions (those rectangles),
  • and arcs, which connect places to transitions.

We have also tokens (those little dots that show up in places). The tokens plays an important role in PNs. Each PN has (or is in) some state. The state is simply the number of tokens in all places. The PN's state can change only in effect of firing a ready transition.

Now, we have to explain two important concepts: transition firing and ready transition.

Please take a look at the first transition in our net, the one in the bottom left of the image. This is only one arc that connects this transition to a place above it. There are no arcs connecting places to this transition. So, we can say that firing this transition won't consume any tokens, from any places. Yet, it will generate one token in the place this transition is connected to.

And since there are no tokens, that should be consumed, this transition is always ready to be fired.

Other transitions in this net are different. They all have some place, which is connected to them. So they are ready only when there are some tokens to be consumed (by firing the transitions). Those transitions can be both ready and not ready to be fired.


Some additional remarks on PNs:

  • there may be many ready transitions, yet only one of them can be fired at once,
  • the number of tokens before and after a transition is fired don't have to be constant.

The first elevator model

(All the models used here were taken from here).

Let's take a look at a net modelling a simple elevator system. The elevator can move between four floors.

Elevator1

As you can see, the net is a graph - a directed graph. This graph consists of two kinds of nodes: places, denoted by circles, and transitions, denoted by rectangles. Places are connected to transitions with (directed) arcs. You should also note, that arc always connect places to transitions: never places to places nor transitions to transitions.

The state of the PN is the state of all its places: it is the number of tokens in the places. Here, the state of the petri net is that there are three tokens in the place P1, and there are no tokens in the place P2. As you can see, it means, that the elevator is on the ground floor.

Now, please take a look at the transition A1. It is highlighted. That because this transition is ready. It means, that in the place P1 there are some tokens, which can be taken while firing the transition A1. When the transition A1 is fired, one token is taken from the place P1, and another one is provided to the place P2. As the result, after the transition A1 was fired, there are only two tokens in the place P1, and one token in the place P2. And, of course, the elevator in on the first floor.

Elevator1-after-fire

In general, the number of tokens in the net can change as a result of firing transitions. There are also nets with additional contraints: places can have limited capacities of the numbers of tokens, and arcs can have their weights (or counts) - the number of consumed/generated tokens.


To sum it up, let's just say that the Petri Nets are a tool used to model discreet systems and processes. Having such models, some analysis can be performed.

JSN

Now, imagine a Petri Net, where:

  • all tokens are JavaScript values,
  • all arc expressions are JavaScript functions.

Wait a minute... What is an arc expression? I'll try to explain it with a simple example.

Let's try to build a model of our elevator using the JSN library.

Let's note, that there are two actions available: the elevator moving up and down. So, 2 distinct transitions will be needed. So far it's the same as in the Petri Net model.

But tokens in JSN can hold more information than tokens in PNs. In PNs, tokens are simply some kind of atoms, that cannot hold more information besides the fact, that they are in some place. Thus, in the elevator model, the number of tokens in the place P2 was the number of the floor the elevator was on.

In the JSN library however, tokens can be ANY JavaScript values, so they can also be objects. Let's imagine such an object:

{ floor: 0 }

This object represents some information about the elevator: we can think, that the elevator is on the ground floor. So, we don't need any other place for our elevator model, when we use the JSN library: we can use the token's value to denote the floor the elevator is on! In other words, since the tokens in the JSN library are more complex than the tokens in PNs, we don't need so many places to model the same processes/systems.

Right now, our specification looks as follows:

{
  places: [
    { name: 'elevator', token: 0 }
  ],

  transitions: [
    { name: 'move-up' },
    { name: 'move-down' }
  ]
}

As we can see, we don't even need an object for the number of the floor the elevator is on. We can use the number itself.

Now, we need some arcs to connect the place to our transitions. Let's start with the arc for moving the elevator up:

{
  places: [
    { name: 'elevator', token: 0 }
  ],

  transitions: [
    { name: 'move-up' },
    { name: 'move-down' }
  ],

  arcs: [
    { place: 'elevator', transition: 'move-up',
      evaluate: {
        ready: (t) => t < 3,
        place: (t) => t + 1
      } }
  ]
}

As you can see, the arc is a connection between a single place and a single transition.

There are two interesting questions, which should be asked:

1) How can we know, that a transition is ready (or not)? 2) How can we know, what should change, after a ready transition is fired?

The answers to both questions are in the arc expressions.

The arcs expressions are JavaScript functions, that can take the token's value as an argument.

The ready function takes the value of the token in the place, and returns either true or false. In our case, it's a function, which returns true, if and only if the token's value is lower than 3. In another words, we cannot move the elevator higher than to the 3rd floor.

When the transition is fired, the token in the place is the result of the function place. As we can see, this function takes the value of the token, and returns the number increased by one. In another words, firing the transition moves the elevator one floor up.

Please note, that the arc is not directed anymore. It's caused by the fact, that firing transitions can affect the token's value in the place connected to the transition being fired. This difference comes from the fact, that tokens in JSN library are arbitrary JS values, and not merely some atoms, which either are or aren't present. The semantics of tokens is different, and thus we use places, transitions and arcs in a different way.

Of course, for moving the elevator down, we need another arc:

{
  places: [
    { name: 'elevator', token: 0 }
  ],

  transitions: [
    { name: 'move-up' },
    { name: 'move-down' }
  ],

  arcs: [
    { place: 'elevator', transition: 'move-up',
      evaluate: {
        ready: (t) => t < 3,
        place: (t) => t + 1
      } },

    { place: 'elevator', transition: 'move-down',
      evaluate: {
        ready: (t) => t > 0,
        place: (t) => t - 1
      } }
  ]
}

Well, I suppose that the second arc doesn't need any further explanations.

Differences between PNs and JSN

PNs are about using a mathematical formalism for modelling.

JSN is about using a (well-known) programming language for modelling.

Thus, PNs need a special methematical formalism for modelling hierarchical structures. JSN use the JavaScript features for the same purpose.


PNs are a directed graphs.

JSN models are JavaScript programs, which can be represented as an indirected graphs.

Why: the semantics of places, transitions and arcs is a little different in JSN models. In a JSN model, a transition connected to a place (with an arc) means, that firing that transition can affect the token in the place. Firing the transition no longer removes nor generates tokens, it rather affects the token in the place connected.

Two why's

Why did I develop the JSN library in the first place?

For two reasons:

  • because I didn't know about anything like that
  • because I wanted to make some simulation games, and I did realise, that PNs are a good modelling tool

Why JavaScript?

  • because I know it

I've been using JavaScript for years, and I know its technical capabilities. I knew that it could be used to develop such a library.

  • because it works in browsers and on mobile devices

I wanted to develop software, which doesn't require to be installed on the user's machine. A browser application, running on the client's machine, can be started by merely accessing an address in internet. It requires no installation.

Besides, JavaScript allows us to develop simple applications also for mobile devices, which gain more and more attention.

Copyright (C) Tomasz Primke 2015-2016