Graph Oriented Programming

What we present here is an implementation technique for graph based execution languages. The technique presented here is based on runtime interpretation of a graph. Other techniques for graph execution are based on message queues or code generation.

This section will explain the strategy on how graph execution can be implemented on top of an OO programming language. For those who are familiar with design patterns, it's a combination of the command pattern and the chain of responsibility pattern.

We'll start off with the simplest possible model and then extend it bit by bit.

The graph structure

First of all, the structure of the graph is represented with the classes Node and Transition. A transition has a direction so the nodes have leaving- and arriving transitions.

Figure 4.2. Node and Transition classes

Node and Transition classes

A node is a command and has an execute method. Subclasses of Node are supposed to override the execute method to implement some specific behaviour for that node type.

An execution

The execution model that we defined on this graph structure might look similar to finite state machines or UML state diagrams. In fact Graph Oriented Programming can be used to implement those kinds of behaviours, but it also can do much more.

An execution (also known as a token) is represented with a class called Execution. An execution has a reference to the current node.

Figure 4.3. The Execution class

The Execution class

Transitions are able to pass the execution from a source node to a destination node with the method take.

Figure 4.4. The Transition take method

The Transition take method

When an execution arrives in a node, that node is executed. The Node's execute method is also responsible for propagating the execution. Propagating the execution means that a node can pass the execution that arrived in the node over one of its leaving transitions to the next node.

Figure 4.5. The Node execute method

The Node execute method

When a node's execute method does not propagate the execution, it behaves as a wait state. Also when a new execution is created, it is initialized in some start node and then waits for an event.

An event is given to an execution and it can trigger the execution to start moving. If the event given to an execution relates to a leaving transition of the current node, the execution takes that transition. The execution then will continue to propagate until it enters another node that behaves as a wait state.

Figure 4.6. The Execution event method

The Execution event method

A process language

So now we can already see that the two main features are supported : wait states and a graphical representation. During wait states, an Execution just points to a node in the graph. Both the process graph and the Execution can be persisted: E.g. to a relational database with an O/R mapper like hibernate or by serializing the object graph to a file. Also you can see that the nodes and transitions form a graph and hence there is a direct coupling with a graphical representation.

A process language is nothing more than a set of Node-implementations. Each Node-implementation corresponds with a process construct. The exact behaviour of the process construct is implemented by overriding the execute method.

Here we show an example process language with 4 process constructs: a start state, a decision, a task and an end state. This example is unrelated to the jPDL process language.

Figure 4.7. An example process language

An example process language

Concrete node objects can now be used to create process graphs in our example process language.

Figure 4.8. An example process

An example process

When creating a new execution for this process, we start by positioning the execution in the start node. So as long as the execution does not receive an event, the execution will remain positioned in the start state.

Figure 4.9. A new execution

A new execution

Now let's look at what happens when an event is fired. In this initial situation, we fire the default event that will correspond with the default transition.

That is done by invoking the event method on the execution object. The event method will propagate find the default leaving transition and pass the execution over the transition by invoking the take method on the transition and passing itself in as a parameter.

The transition will pass on the execution to the decision node and invoke the execute method. Let's assume the decision's execute implementation performs a calculation and decides to propagate the execution by sending the 'yes'-event to the execution. That will cause the execution to continue over the 'yes' transition and the execution will arrive in the task 'doubleCheck'.

Let's assume that the execute implementation of the doubleCheck's task node is adds an entry into the checker's task list and then waits for the checker's input by not propagating the execution further.

Now, the execution will remain positioned in the doubleCheck task node. All nested invocations will start to return until the original event method returns.

Figure 4.10. An execution in the 'doubleCheck' wait state

An execution in the 'doubleCheck' wait state

Actions

In some application domains there must be a way to include the execution of programming logic without introducing a node for it. In Business Process Management for example this is a very important aspect. The business analyst is in charge of the graphical representation and the developer is responsible for making it executable. It is not acceptable if the developer must change the graphical diagram to include a technical detail in which the business analyst is not interested.

An Action is also a commands with an execute method. Actions can be associated with events.

There are 2 basic events fired by the Node class while an execution is executing: node-leave and node-enter. Along with the events that cause transitions to be taken this gives already a good freedom of injecting programming logic into the execution of a graph.

Figure 4.11. Actions that are normally hidden from the graphical view

Actions that are normally hidden from the graphical view

Each event can be associated with a list of actions. All the actions will be executed with the event fires.

Synchronous execution

The default propagation of execution is synchronous. In the section called “Asynchronous continuations” we'll see how this default behaviour can be changed.

An execution starts when an event is send to the execution. That execution will start to propagate over a transition and enters a node. If the node decides to propagate the execution, the take method is invoked on a leaving transition and the execution propagates further. By default, all of these propagations are done as nested method calls. Which means that the original event-method will only return when the execution has entered a new wait state. So the execution can have travelled over multiple nodes during one invocation of the event-method.

Typically, a signal method is invoked inside of a transaction. This implies that in one transaction, the execution can potentially move over multiple nodes on the process graph. That results in significant performance benefits over systems that need one transaction per node.

Another benefit of synchronous execution is more options for exception handling. If all nodes are executed synchonously, all propagations of executions will be nested method invocations. The caller that invoked the signal method will know that a new wait state has been reached without problems when the signal method returns.

Code example

In order for people to get acquinted with the principles of Graph Oriented Programming, we have developed these 4 classes in less then 130 lines of code. You can just read the code to get an idea or you can actually start playing with them and implement your own node types.

Here's the example code:

You can also download the whole (297KB) source project and start playing with it yourself. It includes an eclipse project so just importing it in your eclipse as a project should get you going. Also there are a set of tests that show basic process execution and the advanced graph execution concepts covered in the next section.