Preparing implementation of asynchronous transition

[geomagilles]

Implements a token'status

• free: token can be used to enable transition
• blocked: token has already be used to enable a transition (not yet fired)
• consumed: token was used to fire a transition

=> token are not removed anymore. Only their status is changing.

Add events:

• BEFORE_TOKEN_BLOCK
• AFTER_TOKEN_BLOCK

Engine's main step is divided in two steps:

• firingTransition: begin transition's work
• firedTransition: end transition's work

[florianv]

Thanks for the work. Tokens must be removed from the places when firing the transition, otherwise it breaks the semantic of the petrinet ?

[geomagilles]

Not sure what you mean. As you wrote, data model should reflect database implementation. In a real-world implementation (such as mine or http://www.tonymarston.net/php-mysql/workflow.html), token would not be deleted but marked as consumed. Moreover, it's interesting to keep blocked and consumed tokens as it allows to explicitly count the number of transition currently firing and fired.

On Wed, Jan 8, 2014 at 6:01 PM, Florian Voutzinos notifications@github.comwrote:

Thanks for the work. Tokens must be removed from the places when firing the transition, otherwise it breaks the semantic of the petrinet ?

— Reply to this email directly or view it on GitHubhttps://github.com/florianv/petrinet/pull/18#issuecomment-31853892 .

[florianv]

In the Petrinet definition, tokens must be removed from the places when the transition is fired. Keeping them breaks the definition.. I found this document : http://martinfowler.workflowpatterns.com/documentation/documents/vanderaalst98application.pdf . Page 26, they show how a workflow task can be represented by a Petrinet with commit and rollback functionnalities.

[geomagilles]

Hi, your document is interesting, but does not solve the difficulty here. Of course, we can delete the token once consumed. But we still need the 'blocked' status. Having a 'consumed' status is nothing more really than a soft-delete here, imho.

[florianv]

I don't understand why you need the blocked status. The tokens position determines if the transition can be fired or not. What we can do is adding a trigger on the transition that you can use to execute your task and provide a default implementation of "automatic trigger". That way if the execution fails you can still rollback and put the tokens in the places they were before it was executed or move the tokens only if the task succeeds.

PS: Counting the fired transitions can be done using the events. You can create a listener and log the fired transitions.

[geomagilles]

Is this something like this you have in mind?

[florianv]

Yes but with 'failure' going to the 'start' place to put the token back on it, for example. In fact ideally anyone could define a "task" as a small Petrinet like this. It would give a lot of flexibility because you can also specify retry strategies by creating loops inside the Petrinet.

Here p2 contains two tokens so the execution will be retried twice in case of failure.

[geomagilles]

Ok - then a few points:

• I guess the first thing to do is to implement trigger?
• in your mind, is this type of task definition has to be included in Petrinet framework? Or be implemented outside of it.
• do you know any Petri net able to model something like: try 3 times then does something else?

Le samedi 11 janvier 2014, Florian Voutzinos a écrit :

Yes but with 'failure' going to the 'start' place to put the token back on it, for example. In fact ideally anyone could define a "task" as a small Petrinet like this. It would give a lot of flexibility because you can also specify retry strategies by creating loops inside the Petrinet. [image: noname]https://f.cloud.github.com/assets/1586668/1893507/c8068b4c-7a9a-11e3-8277-c23e643fea6e.png

— Reply to this email directly or view it on GitHubhttps://github.com/florianv/petrinet/pull/18#issuecomment-32090764 .

http://leetix.com founder http://twitter.com/gillesbarbier http://linkedin.com/in/gillesbarbier skype: gilles.barbier mobile: +33 678 094 540

[florianv]

I think indeed it should be created in a library on top of this one. You can define a task being a small Petrinet like in the above example.

do you know any Petri net able to model something like: try 3 times then does something else?

In my above example it will try three times and then stop (the token disposition will be unchanged at the end).

PS: You might be interested in this discussion https://github.com/florianv/petrinet/issues/19

[geomagilles]

Right - let's suppose we implement tasks and most workflow-related stuffs in another library. It seems to me that we still need to enrich Petrinet:

• with an inhibitor arc (to be Turing complete eg. this would allow to implement strategy such as 'retry 3 times then do something else')
• with the ability to inject a way to implement conditional routing after a transition (eg. do different things according to user status: free or paying).

Do you agree?

[mdwheele]

I think it comes down to how true to the mathematical definition of Petri Net this package is intended to be. I feel like Florian wants to keep it pretty formal; leveraging a well-thought-out interface and event system to improve extensibility to cover additional use-cases.

Most of the functionality proposed by Marston falls within the realm of Petri net Extensions. All that said, my personal opinion is to keep this as close to the original intent as a formal implementation of a Petri net and implement extensions (high level Petri nets) on top to cover workflow-oriented user stories.

There are some extensions of the definition that are not backwards compatible. However, most workflow-oriented stories are able to be implemented using a colored Petri net. The great thing about this package, in particular, is that it's so easy to extend. The only changes I'd anticipate having to make are slight interface tweaks to the engine and toying with the event system a bit more; but I'm not even sure (at the moment) that it's entirely necessary.

I've got a project with basic activity-based workflow requirements coming up next sprint and will be focusing on development of an extension or simple wrapper around the library. Perhaps we could share notes? I'm more or less preparing at the moment. I'm also planning to implement a storage implementation using Doctrine2, which is proving useful already in determining changes that might need to be made to improve "the feel" of using the library as the core of an extended definition of P/T net.

The problem for me right now is whether or not it's worth implementing a colored Petri net extension on top of this library and then wrapping workflow domain-related functionality around that -OR- simply "getting it done" and focusing on a releasable package afterwards (which would essentially be the separation of workflow code and colored Petri net functionality). It's definitely something I want to work on over time, but I know there isn't time (this sprint) to "do it right".

[florianv]

I think it comes down to how true to the mathematical definition of Petri Net this package is intended to be. I feel like Florian wants to keep it pretty formal; leveraging a well-thought-out interface and event system to improve extensibility to cover additional use-cases.

Yes exactly I want to stick with the definition.

I previously tried to make a coloured Petrinet library (with arc expressions) but it was very difficult to find the enabled transitions, so I gave up and pushed a basic library.

[geomagilles]

Ok perhaps I missed something. How can you extend current project to implement (eg.) conditional routing ? You remove or add Arc on the fly using current events system?

[mdwheele]

Sorry I didn't respond until now. I was in meeting all day and am just now getting some "me time"; haha!

I don't think there's a need to add or remove Arcs on the fly. However, as an aside, I have done a bit of research to investigate possible uses for workflow engines built on colored petri net (CPN)-variants/extensions that have an analysis module as part of the engine to dynamically modify subsets of the P/T net membership based on different criteria. The best example might be optimizing workflows to eliminate "hotspots" where tokens tend to "pool" across different P/T net instances (workflow cases).

All that aside, I don't think implementing "conditional routing" is about adding / removing arcs based on conditions. Essentially it's really all about whether or not transitions are enabled. Transitions are what's driving tokens through the net. In a traditional implementation, transitions are enabled when there is a token for every input arc on the transition. The transition fires when this state occurs and thereby consumes input tokens and generates output tokens.

Under a "conditional-routing-enabled P/T net" -- I keep using quotes because a specific implementation can find itself somewhere in between a vanilla P/T net and some other extension (Colored, Hierarchical, etc) simply based on desired functionality -- what you really want is a set of assertions on the arc that must all evaluate to true in addition to there being a token for the pointed-to transition to be enabled. The combination of interactions of arcs to and from transitions with this "assertion behavior" is what gives you the conditional routing. It's just a different way of doing the same thing. These assertions are essentially what other papers will call "guards". They serve mostly the same purpose (if not exactly the same). Since most of the framework Florian has built uses type-hinted interfaces to tie everything together, it's easier to built alternate implementations of say, an Arc, which would have an additional "bag of Guards". The "bag of Guards" should be implemented outside this framework, is my understanding.

In addition to controlling when Transitions are enabled, we also want to have control over when the transitions are fired. This can be implemented similarly to how we'd extend the Arc's functionality; by providing an alternate or extended implementation for Transition that employs the use of different strategies for firing:

• An auto-fire strategy (which serves as the default of what you'd expect out of a P/T net)
• A "user intervention" strategy (which is a 'user pushing a button', etc)
• A "timed" strategy (which will fire after a duration has passed)
• A "system intervention" strategy (which would basically be an event listener for a specific application and would trigger on specified domain events) This particular strategy has NO place in ANY framework really. This would be the part of your documentation where you say, "And you can do other cool stuff with your app by implementing X interface and registering with the framework engine"

This functionality is the gist what is called a "Trigger" in most documentation you'll find.

Now... the contradictory argument! All of this added functionality is backward-compatible. What I mean by that is that you can have "default" implementations that are functionally equivalent to the current framework behavior. What's nice about this is that it makes implementation of a storage layer easier and more unified. However, easier is not always better and an argument could certainly be made to have the extended framework implement it's own storage implementation in addition to using this package's (when it is complete).

This was more of a brain-dump than I expected to sit down and right and it's late here so there are probably mistakes. I hope this helps. These would basically be my next few steps (might still be). I'm not sure if it's smarter to figure out the technicalities of this additional layer of functionality before thinking more on storage.

Obviously, even after extending this framework, there needs to be a third package that implements the domain-language of "what an activity-based workflow looks like" (tasks, inboxes, notifications, etc) and nicely packaged to be use in "happy developer's framework of choice".

[mdwheele]

Also, check out some of the notes in #19 as far as the proposed EventSubscriberInterface. These will be very handy for hooking application services into the engine.

It's looking like I'm going to have a good chunk of time at work Friday that I can legitimately focus on this package and future work with it as well as development of our "workflow domain". I'll make sure to keep my head poking around here and would be happy to help where I can.

Also, just out of curiosity, what tool are you two using to draw the P/T nets above. They look really nice and would help me illustrate some of the examples in my future work. At some point I'm going to have to explain what the heck a P/T net is and why it's useful to my team, haha. Pictures are always useful. Especially with more complicated workflows (which is the real beauty, in my opinion).

[florianv]

Since most of the framework Florian has built uses type-hinted interfaces to tie everything together, it's easier to built alternate implementations of say, an Arc, which would have an additional "bag of Guards". The "bag of Guards" should be implemented outside this framework, is my understanding.

Indeed, everything can be extended.

For the triggers, they could be added and default to the automatic one (but that's already out of scope of basic Petrinets I think).

Also, just out of curiosity, what tool are you two using to draw the P/T nets above.

http://romeo.rts-software.org/?page_id=3 Some testing patterns can be visualized with this software too: https://github.com/florianv/petrinet/tree/master/src/Petrinet/Tests/Fixtures/PetrinetProvider

[mdwheele]

Great! Thanks!

[geomagilles]

Thanks @mdwheele for your always complete responses. Mine are shorter as English is not my first language (and by taste probably also).

I agree about your comments but still do not understand the most important one for me : when you say we can extend Petrinet's Arc to add a "guard", do you still have in mind to use Petrinet lib itself or only its sources modified within a new project?

My point is that Petrinet does not use dependency injection techniques (such as Facade in Laravel), so there is no way to inject new class implementation within current Petrinet lib. Or do I miss something?

[mdwheele]

Sure thing! No problem. I personally have a hard time saying more with less so consider yourself lucky!

Here's a contrived example (and probably not entirely syntactically correct, :sweat_smile: ). It's nowhere near complete but might give some good hints towards how you can integrate external code to extend portions of this library. This process should be extendable (no pun intended) to be applied to other libraries as well, assuming they're written well-enough to be open for extension.

So, for the example, we're going to create an alternate "default implementation" for an Arc that might serve as a skeleton for extension to add Guards:

First, take a scan through the entire codebase and make sure you have a base understanding of how all the entities fit together. This takes a while. When I'm preparing to contribute or extend a package, I typically contribute a "code cleanup" where I read through the package line-by-line, helping to fix documentation, inconsistencies in structure, etc (Nothing special). However, I also use that time to learn the package. Take special care to note interfaces between those entities.

Starting out, we know that arcs interact with both places and transitions. Let's start with the place / transition integration.

• Place has no factory method or constructor argument to associate an Arc with it. So that may be a hint that it doesn't have dependency on Arc. We may come back to it. It is important to note, for now, that Place implements PlaceInterface.
• Arc's constructor has constructor dependencies on a PlaceInterface and a TransitionInterface. This is very important if you ever wanted to extend Place or Transition. Essentially, what this object is declaring is that, "As long as the object you pass into me functions as a Place (PlaceInterface) or a Transition (TransitionInterface) should, I can do what I need with them). This is also important for when we extend Arc somewhat... in that we just need to remember that a "basic" Arc follows this pattern. Our extension should, at least, follow this pattern as well. Also, note again that Arc implements ArcInterface. This is important.

So, we found out that Arc depends on PlaceInterface and TransitionInterface and elaborated a bit on why that's cool. The next step is to find places in the system that depend on Arc and because of what we've seen above, we can likely assume the dependency will actually be on ArcInterface. We know that transitions depend on Arcs because they need to know if tokens are on the place attached to the Arc to determine whether or not the Transition is activated. We'll start there.

...
/**
 * Transition class.
 *
 * @author Florian Voutzinos <florian@voutzinos.com>
 */
class Transition extends AbstractNode implements TransitionInterface
{
    /**
     * {@inheritdoc}
     */
    public function isEnabled()
    {
        if (empty($this->inputArcs)) {
            return false;
        }

        foreach ($this->inputArcs as $arc) {
            if ($arc->getPlace()->isEmpty()) {
                return false;
            }
        }

        return true;
    }
}

Transition doesn't have any "explicit" dependency on Arc according to this class. However, we see it reference a property called inputArcs. Time to check AbstractNode:

...
    /**
     * Adds an input arc.
     *
     * @param ArcInterface $arc The arc
     */
    public function addInputArc(ArcInterface $arc)
    {
        $this->inputArcs[] = $arc;
    }
...

Sure enough, AbstractNode contains an array of input and output arcs with constructor dependencies on an array of undefined type (though hinted in the docblock). The constructor calls a setter for adding a collection of arcs and that setter calls another setter for adding a singular arc, which is type-hinted for validation as a ... ArcInterface!! Sweet, so basically what we now know is that we can add input arcs to a transition as long as it implements ArcInterface.

Now, there might be other places that have a dependency on Arc that may need to also be checked, but from what I've seen the library is extendable in this way pretty much across the board. The only tweaks I foresee having to make to the basic library (if any at all) would be quality-of-life-related or perhaps small changes to make extension easier, but most of the work is done.

Here's what a "guarded Arc" might look like. You can either extend Arc directly (I believe it will still be type-hinted as ArcInterface). If not, implementing an entirely different object that follows the same interface is an option. Please forgive "slapped together pseudo nonsense"; this is where there's a lot of room for implementation-specific discussion and this probably won't be the "best way" to do it:

interface GuardInterface
{
    /**
     * Really bad name.  But this method determines whether or not the Guard passes.
     * @return bool
     */
    public function assert();
}

// Not particularly useful, but a Guard that always asserts true.  Essentially a Strategy Pattern implementation.
class AlwaysTrueGuard implements GuardInterface
{
    public function assert()
    {
        return true;
    }
}

// Going with the extended method.
namespace Your\Namespace\Petrinet\Extensions\Arc;  // Doesn't really matter what you namespace as, it'll just be outside the base library.

use Petrinet\Arc\Arc;

class GuardedArc extends Arc implements GuardInterface
{
    // Either a simple array of objects implementing GuardInterface with a validation strategy similar to Arc
    // or Guards can be similar to TokenBag... you'd make a GuardBag.  I'm going with simple array here.
    $guards = array();

    public function __construct(...) { /* Set up dependencies, etc.  You might pass in a collection of Guards at this point */ }

    // Implementing GuardInterface here as well gives you a clean way of asserting all Guards on the Arc are true.
    // This is essentially a Composite Pattern implementation.
    public function assert()
    {
        $flag = false;  // This is a quick-and-dirty way to do this.  Probably something "more efficient" out there.

        for ($guards as $guard) {
            $flag = $guard->assert();  // You may need to inject dependencies into *some* Guards to do awesome business rule checking.  But keep in mind that there has to be a common interface assert() method.
        }

        return $flag;
    }

    // ... More methods related to adding arrays of Guards and individual Guards.
}

... Implement more code when checking whether or not a Transition is enabled.  May that means extending Transition, maybe not.  But either way, everything's coded to an interface, so swapping isn't that bad.

So that's rough... but after this (assuming extending a class that implements an interface type-hints the child class to that interface... sorry I'm fuzzy this morning), you can do something like:

$p1 = new Place(...);
$p2 = new Place(...);
$t1 = new Transition(...);

$guards = array(...); // Array of arbitrary guards.

$arc1 = new GuardedArc($id = "Arc from P1 to T1", $direction = Arc::PLACE_TO_TRANSITION, $p1, $t1, $guards);
$arc2 = new GuardedArc($id = "Arc from T1 to P2", $direction = Arc::TRANSITION_TO_PLACE, $p2, $t1, $guards);

$petrinet = new Petrinet($id = "My First Guarded Net", array($p1, $p2), array($t1), array($arc1, $arc2));

... After beating your head against the wall, writing some awesome tests, and much work, it'll come together. 

I'll come back and do corrections on this perhaps, but consider them loose notes. I've probably made a mistake here or there, but I hope it gets the gist across.

[geomagilles]

Thanks ! Basically, you use Petrinet constructor's ability to receive PlaceInterface, TransitionInterface and ArcInterface instead of Place, Transition, Arc. Thats' great actually (I was looking myself at PetrinetBuilder that implements explicit new instances of Place, Transition and Arc).

So one way to improve PetrinetBuilder would be to inject a factory

    public function __construct($id, PetrinetFactoryInterface $factory)
    {
        $this->id = $id;
        $this->factory = $factory;
    }

Then

    $arc = $this->factory::createPlaceToTransitionArc($arcId, $place, $transition);

instead of

    $arc = new Arc($arcId, Arc::PLACE_TO_TRANSITION, $place, $transition);

Right ? In this way we can also provide a new implementation of PetrinetFactoryInterface to create extended Arc, Transition and Place

[florianv]

The thing is that the PetrinetBuilder uses the default implementations Arc, Transition etc.. (not the interfaces) and these are mutable classes. I don't want the interfaces to be mutable because it prevents people from altering the objects when they extend the engine (unless adding/removing tokens from the places but that's the role of the engine). So if you use custom classes, you have two choices:

• build Petrinets manually
• create your own Builder class

The second possibility is to create new interfaces "MutablePlace", "MutableTransition" that extends the base interfaces.

[mdwheele]

Sorry, I actually had a thought about PetrinetBuilder and forgot to write it down. PetrinetBuilder, to me, serves as this library's convenient facade to pull together P/T nets.

I think it'd be wise to implement builders according to the type of extended net your constraints require. In my case, I'm not sure I would even bother with a ColoredPetrinetBuilder or any other specific implementation. But that's because my interests (for the moment) lie more in development of the domain of a workflow engine. I'd probably find myself creating basic adapters to pull my extension of this library into the language of that domain instead of focusing (at least for now) on building a fully robust extension.

[geomagilles]

Ok - it's at last clear for me ;) @florianv feel free to close the pull request if you want. @mdwheele My interest is also to create a workflow engine on top of this (with guards and triggers). I will begin to build something based on the ideas discussed here. Let me know if you're interested. Thanks

[mdwheele]

Sure thing. Feel free to email me when a repository is up and I'll make sure to watch.