Skip to main content

Semantics of BPMN

Recently I have been involved with the standardization of BPMN. I find BPMN fascinating because it lies on the precise boundary between the IT world and the business world. Boundaries tend to be uncomfortable places to be around and BPMN is no exception.

My focus has been primarily on the semantics of BPMN. There have been many issues concerning the semantics of BPMN features. From a strictly programming language point of view BPMN seems to throw away most of the hard learned lessons of programming in the last 40 years: it is unstructured, full of gotos and no objects in sight.

But that is to forget the true purpose of BPMN, it is not a programming language. It is not even a scripting language, it is a language to help humans to manage their own activities. Even when BPMN is supported by automation, it is still primarily humans doing the work.

Anyway, the traditional approach to the semantics of languages like BPMN is Petri Nets. The merit of Petri nets is that they are quite simple to understand and quite simple to implement too.

However, BPMN has a bunch of features that are quite difficult to capture in petri nets without getting quite twisted. These are mostly due to the rich variety of merge behaviors supported by BPMN.

A classic one is the pass-through merge: where two streams are merged into one and all the tokens are forwarded. Simple, but combined with parallelism can get you very quickly into trouble:


And-Deadlock-1



This diagram, which shows an and-split forking off into three parallel branches, two of which are merged by a pass-through merge and the resulting pair merged back by an and-merge.

Interpreted as a petri net, three tokens originate from the split, two are merged onto the same 'wire' and the and-merge merges tokens on its two wires. This will result in a deadlock after the first successful firing of the and-merge because there is still a token left hanging about that is not collected by the and-merge.

The instinctive reaction of an IT person would be to say "don't do that"; but we are expecting business analysts to use BPMN, not programmers. And, this kind of situation can show up as easily in a large 400+ node diagram as a 3-node diagram.

One 'fix' is to allow annotations on the wires that go into an and-merge: specifically how many tokens that wire is supposed to accept. In my view, that is even worse because there may be no way of setting that count reliably, and further, it is low-level hacking of the worst kind: programming by numbers.

Here is another approach: instead of using petri nets, use graph rewriting semantics. In a graph rewriting approach, there are three kinds of nodes and wires: dormant, active and expired. The BPMN diagram becomes the initial graph which is rewritten until the entire graph is expired (or until only all the end-event nodes are active). This is how the pass-through is evaluated using graph rewriting:


And-Graph-2


The six stages show the evolution of the graph from a single active and-split ending up at the single active and-merge. The green is active, and the gray/purple signifies expired. (Normally you would remove expired entities but I have kept them for illustration.

Essentially, the pass-through node becomes a kind of 'cloner', and the dead-lock problem disappears! Neat!

I think that this may well end up to be the way that BPMN's semantics is defined. Given the experience of the G-machine (used in combinator approaches to functional programming languages) it's also not a bad way to implement BPMN automation.

Unless, of course, some problem shows up to make it unsuitable after all.

Popular posts from this blog

Existential Types are the flip side of generics

Generic types, as can now be seen in all the major programming languages have a flip side that has yet to be widely appreciated: existential types.

Variables whose types are generic may not be modified within a generic function (or class): they can be kept in variables, they can be passed to other functions (provided they too have been supplied to the generic function), but other than that they are opaque. Again, when a generic function (or class) is used, then the actual type binding for the generic must be provided – although that type may also be generic, in which case the enclosing entity must also be generic.

Existential types are often motivated by modules. A module can be seen to be equivalent to a record with its included functions: except that modules also typically encapsulate types too. Abstract data types are a closely related topic that also naturally connect to existential types (there is an old but still very relevant and readable article on the topic Abstract types have …

Concept Oriented Markup

I have long been frustrated with all the different text mark up languages and word processors that I have used. There are many reasons for this; but the biggest issue is that markups (including very powerful ones like TeX) are not targeted at the kind of stuff I write.

Nowadays, it seems archaic to still be thinking in terms of sections and chapters. The world is linked and that applies to the kind of technical writing that I do.

I believe that the issue is fundamental. A concept like "section" is inherently about the structure of a document. But, what I want to focus on are concepts like "example", "definition", and "function type".

A second problem is that, in a complex environment, the range of documentation that is available to an individual reader is actually composed of multiple sources. Javadoc exemplifies this: an individual library may be documented using Javadoc into a single HTML tree. However, most programmers require access to multiple…

Hook, Line and Sinker

It is well documented that people’s #1 fear is speaking in public! Effective and efficient public speaking is a whole topic in its own right; but a few simple tips might help to both improve your effectiveness and help to reduce the anxiety.

You may be called on to talk about your work at very short notice; or you may have a week’s notice; and you may be required to give a formal slide show or just a brief verbal update. Many, if not most of the issues, are the same.
The Hook
Newspaper editors call the first paragraph of an article ‘the hook’. Its meant to hook you into reading the rest of the piece. On the other hand, the classical ‘say what you are going to say, say it, and say what you said’ approach gives people plenty of time to switch off.

The hook may be playful, it may be controversial, but it must communicate why the listener should pay attention.
The Line
Its a conversation! Even if no one says anything they are listening and thinking; and maybe replying to you in their head. So, …