Progress report: XML/PNML

Michelle Osmond

XML (Extensible Markup Language)

XML is a language for structuring data. It's actually a meta-language, a language that provides a framework (a collection of protocols and syntaxes) for creating new languages, which may be customised for particular types of data and needs. Eg, XML languages which support a specific manufacturer's product database, general chemical structures (CML), mathematical formulae (MathML), musical notation. Probably the most popular XML language is XHTML, which is a cleaned-up version of HTML (webpage language) that meets XML's stricter requirements (look at the source if you're interested - mostly it's pretty much the same as HTML). Obviously we're interested in Petri Net Markup Language (PNML).

These various languages are developed by the communities who will use them. A lot of effort goes into working out what the language will contain, and how it will be structured. It's a bit like working out an object diagram to represent data. Some relevant points are:

The language should be as useful in as many areas as possible. Hence PNML is intended to be used to (ultimately) represent all types of Petri nets.
It is often intended as an interchange format, so the same data file can be used in different applications. Preferably, no data should be lost while the file is processed. As an example, in Chemical Markup Language, a single CML file may contain info on a molecule's structure, as well as several types of spectral information. A program which reads in and modifies the structure must not lose the spectral information when it saves the file, simply because it does not understand it!
The language is usually expected to be extended. This is a bit like subclassing - you get a version of the language with more features than the original. You declare which version of the language you're using at the top of the file.
An XML language isn't meant to be only used as a storage and transfer medium - it's designed as a sensible data model that can be used internally in programs.

XML files are plain text, and certainly aren't a compact representation of data. This isn't considered to be a concern though - we're still talking about kilobyte sizes (usually), and text zips well. The big advantage of text is that they're both human- and machine-readable. You can edit them in Notepad, emacs, a text html editor or any other text editor. If you open up a valid xml file in Internet Explorer, it'll give you a nice collapsible tree that may make the file easier to visualise. The latest Mozilla also deals with XML well.

A Schema or DTD is a strict description of the syntax of the XML-language. We shouldn't need to worry too much about these, apart from for reference, or if we choose to extend the language.

XSLT is an XML transformation language, which is often used as a clever stylesheet/formatting language to manipulate XML files for display, eg searching through and only displaying certain elements, or displaying things in a particular way. This may be useful to us, as JDOM seems to support some XSLT, but I'd have to look into it further. Also, the transformation capabilities could be useful in flattening nets.

PNML (Petri Net Markup Language)

PNML has been in development for a few years. These are the basic elements:
Places - A place, which has a unique id and an initial marking.
Transitions - A transition, which has a unique id.
Arcs - An arc connecting a place and a transition. It refers to their unique id's.
Nets - Encloses Places, Transitions, and Arcs to define a Net.

Each of these elements may also contain additional information, such as a Name, a Label, and Graphics information (eg X,Y position or offset).

What's missing: the Stochastic bit. As far as I can see, there hasn't been a GSPN language defined yet. Basically, it's the transition information we need.

Example, taken straight from the PNML page:

<pnml xmlns="http://www.informatik.hu-berlin.de/top/pnml">
  <net id="n1" type="ptNet">
    <name>
      <value>1-safe circle</value>
    </name>
    <place id="p1">
      <name>
        <graphics><offset page="1" x="0" y="22" /></graphics>
        <value>p1</value>
      </name>
      <initialMarking>
        <graphics><offset page="1" x="-20" y="10" /></graphics>
        <value>1</value>
      </initialMarking>
      <graphics><position page="1" x="50" y="150" /></graphics>
    </place>
    <place id="p2">
      <name>
        <graphics><offset page="1" x="-1" y="20" /></graphics>
        <value>p2</value>
      </name>
      <initialMarking>
        <graphics><offset page="1" x="24" y="5" /></graphics>
        <value>0</value>
      </initialMarking>
      <graphics><position page="1" x="250" y="150" /></graphics>
    </place>
    <transition id="t1">
      <name>
        <graphics><offset page="1" x="0" y="26" /></graphics>
        <value>t1</value>
      </name>
      <graphics><position page="1" x="150" y="50" /></graphics>
    </transition>
    <transition id="t2">
      <name>
        <graphics><offset page="1" x="-1" y="22" /></graphics>
        <value>t2</value>
      </name>
      <graphics><position page="1" x="150" y="250" /></graphics>
    </transition>
    <arc id="a1" source="p1" target="t1">
      <inscription>
        <graphics><offset page="1" x="20" y="0" /></graphics>
        <value>1</value>
      </inscription>
      <graphics><position page="1" x="100" y="100" /></graphics>
    </arc>
    <arc id="a2" source="t1" target="p2">
      <inscription>
        <graphics><offset page="1" x="20" y="0" /></graphics>
        <value>1</value>
      </inscription>
      <graphics><position page="1" x="200" y="100" /></graphics>
    </arc>
    <arc id="a3" source="p2" target="t2">
      <inscription>
        <graphics><offset page="1" x="20" y="0" /></graphics>
        <value>1</value>
      </inscription>
      <graphics><position page="1" x="200" y="200" /></graphics>
    </arc>
    <arc id="a4" source="t2" target="p1">
      <inscription>
        <graphics><offset page="1" x="20" y="0" /></graphics>
        <value>1</value>
      </inscription>
      <graphics><position page="1" x="100" y="200" /></graphics>
    </arc>
  </net>
</pnml>

In addition, there are two methods to introduce abstraction to the net: this does not change the net, and any file using these methods can be 'flattened' into a more basic form.

Pages: This is the older structure. It basically sections off a part of the net, and encloses it in a page element. You can then define nodes (places/transitions) which connect from one page to another. These nodes (reference places and reference transitions, which are like pointers) can only refer to one other off-page node: you can't have multiple occurrences of the same page in one net.
Modules: This is a new definition (June 2001) - presumably it was just too late for last year's projects students to use. It seems to correspond directly to the subnet concept. As it's relatively new, there probably (?) aren't that many programs around that can read/use the format yet. It considers a module (subnet) as consisting of an implementation and an interface. The interface contains import nodes and export nodes: import/export do not correspond to input and output here; rather they describe the 'actual' location of the node(s).
Export nodes are contained in the module, but may be accessed by the external environment.
Import nodes are in the external environment, but may be accessed within the module: they act like parameters to the module.
(Example from paper, A Universal Module Concept for Petri Nets. An Implementation-Oriented Approach)
```
<module name="M1">
      <interface>
         <importPlace id="p1"/>
         <exportPlace id="p2" ref="y"/>
      </interface>
      <referencePlace id="x" ref="p1"/>
      <transition id="t1"/>
      <transition id="t2"/>
      <place id="y"/>
      <arc source="x" target="t1"/>
      <arc source="t1" target="y"/>
      <arc source="y" target="t2"/>
      <arc source="t2" target="x"/>
</module>
```
Once defined, modules may be instantiated within a net, as many times as you like. When you create an instance of a module, you have to pass it parameters - tell it which nodes in the net correspond to its import nodes. Modules can even be nested within modules.
Again, pinched an example:
```
<net id="n1">
      <place id="p">
         <initialMarking>
            <value>1</value>
         </initialMarking>
      </place>
      <instance id="m1" ref=URI#M1>
         <importPlace parameter="p1" ref="p"/>
      </instance>
      <instance id="m2" ref=URI#M1>
         <importPlace parameter="p1" instance="m1" ref="p2"/>
      </instance>
      <instance id="m3" ref=URI#M1>
         <importPlace parameter="p1" instance="m2" ref="p2"/>
      </instance>
</net>
```
A procedure is provided to flatten a modular net into a more basic net.

The previous instantiated modules are equivalent to this. We'll want to provide a flattening function - both for analysis modules which won't want to be dealing with subnets, and for export (eg so that it can be used in another tool that doesn't understand the subnet system). Possibly this could be done neatly/properly with XSLT, which is designed to translate one XML format to another: depends on JDOM's implementation of it and whether someone wants to learn XSLT.
Notice the way the module is referenced: ref=URI#M1. URI is a Uniform Resource Indicator - bit like a URL. That means the module can be located in the same file, another file, another computer on the network or even on the internet. It would therefore be possible, for example, to set up an online library of modules for public use. Might be an interesting extension to the module-loading code to internet-enable it if we have time!

Problems

Arcs - one of the possible extensions is to allow for inhibitor arcs in the simulator (but not in any of the other analysis modules as it's too hard). The following is only relevant if we decide to do this extension of course! It's actually possible with the implemented PNML: however it is not in the basic PNML definition, but one of the extensions (PNTD's). Mainly we'd be using the PNTD for a normal Petri Net, and we'd do this by declaring our nets to be of type "ptNet". For a net with inhibitor arcs, we'd need to use the type "ptNetArcTyped", which allows all the functionality of the ptNet type, with the addition of one "type" attribute of the "arc" element, which may take values "normal","read","inhibitor", or "reset". We might want to look into what these other types of arc are, and if we want to try implementing them too.
Actually, this isn't a real problem - more something to consider. If we use the JDOM, we won't need to do any extra code to allow our program to read in the special arc attributes - they'll be stored in the DOM regardless, and we can just extract them when we need them, the same way we extract everything else. If nothing else, we could use this example (whether we implement it or not) as an illustration of the extensibility of the program with respect to supporting new types of net with add-in modules.

As mentioned before, there doesn't seem to be an extension to PNML for supporting Stochastic Petri Nets. This one is a real problem. I believe what we would be missing is the transitions - whether they are immediate/timed, and their weighting/rate of decay of the exponential distribution. We'd have to extend the PNML ourselves to store this information - deciding what elements to add. There are several possible ways of doing this:

Using the existing element <toolspecific> tag. This is a predefined element in PNML which is intended to be used by program authors to store any data they want. However, only their program will be able to make sense of it - any other programs will ignore it. Using this element is not recommended by the PNML people, and it may be a left-over fix from before a better solution (namespaces) were decided on - PNML is quite old for an XML language. An example implementation could be something like:
(i'm pretending our tool is called Medusa because we don't have a name for it yet...)
```
	           <transition id="t1"> 
	             ...
		        <toolspecific tool="Medusa" version="1.2">
			      <type>immediate</type>
			      <weight>4.3</weight>
			</toolspecific>
		   </transition>
```
Defining a new petri net type using a PNTD. This would be the most proper way to do it, but I don't think we're entitled to! I think it's the sort of thing that should be discussed and defined by proper academics ;) Probably...
Using a namespace to separate out our own custom elements (actually our own XML language). You define a namespace by declaring a unique identifier (usually a webpage, eg the webpage of our project) usually along the lines of <pnml xmlns:medusa="http://www.doc.ic.ac.uk/~mo197" ... > at the top of the document. Once we've declared this, any elements which start with medusa: are interpreted as belonging to that namespace - ie, are not interpreted as PNML (as they aren't!). Then we'd be free to add whatever new elements we like, eg:
```
	           <transition id="t1"> 
	             ...
	                <medusa:type>immediate</medusa:type>
			<medusa:weight>4.3</medusa:weight>
		   </transition>
	   
```