Decision Trees and the Strategy Design Pattern

[djantzen]

Hi All, I am currently working out the object model for what is basically a ticket tracking system. The idea is to facilitate discussion between authors, editors and supervisors regarding documents. We have the tools already in place to create the documents and even different versions of documents, but what I'm developing now is a flexible object model to express a decision tree in such a way that if the policies of the group change down the road, altering the system to reflect the new procedures is as painless as swapping out a single module. This leads me to consider the Strategy design pattern.

Components:

• groups: every individual belongs to a group.
• user: a single person.
• workspace: an listing of active "tickets" under someone's care. May belong either to a group or to an individual.
• statuses: i.e. 'pending approval', 'approved', 'under editorial review', etc.

Here's an example decision tree:

        Someone creates a new document
            |    
            V
        The document goes a particular supervisor 
        determined by the topic of the document.
        Status: 'pending approval'.
                /                   \
               /                     \
The document gets rejected            The document gets approved
and returns to the workspace            and moves to the editors'
of the author for more work.            group workspace.
Status: 'pending approval'.            Status: 'approved'.
                                     /
                                    /
                        Document moves from editors' group workspace
                        to individual's workspace.
                        Status: 'under editorial review'.

And several more options below, but you get the idea I hope.

Now it seems to me that I just need a single object to encapsulate where in the system a given document is, and what its status is. But I want the interface for this thing to be simple, so to the user it just seems like an object moving along a track. Something like:

Ticket::new(String group, String username, String documentID); # other
+ values will come from the db
Ticket::save;
Ticket::move(String direction, int steps); # e.g., forward if okayed, 
                                           # back if not okay, sometim
+es even 
                                           # back to the beginning.

The hard part is that I want to be able to describe the decision tree, or track of possibilities, in a module that can be swapped at will. So I've got an idea to do something like:

package Track;
our %switch = (); # to be filled in by subclasses.
sub new { 
   my ($class) = @_; # don't have any args in mind yet.
   my $this = bless({}, $class); 
   return $this->init(); 
} 
sub move { AbstractMethod->throw("Not implemented in this class\n"); }
+ # raise exception unless 
                                                                    # 
+implemented by a subclass

package BasicTrack;
use base Track;
sub init {
    my ($this) = @_; 

    # Add anonymous subroutines to the hash of possible combinations
    # of status and location. I.e., if the status is 'pending
    # approval' while the document is sitting in the workspace of a
    # supervisor, and 'forward' is the command issued to Track::move,
    # then the subroutine ought to set the status to 'approved',
    # change group to 'editors'. Other subclasses can inherit
    # or override these as necessary, to avoid duplication of behavior
+.

    $Track::switch{case1} = sub { # do the stuff };
}

sub move {
    my ($this, $arg) = @_;
    # complicated set of switch statements to figure 
    # out which subroutine in %Track::switch to call.
    # This would be called from Ticket::move most likely.
}

Right now I'm thinking about having each Ticket object contain a reference to a Track object, although this could be implemented as class methods in Track as well. I'm not strongly attached to either approach, although the latter would make this more of a classic Model-View-Controller arrangement than an application of Strategy. Anyhow, in the event of a policy change, a subclass of BasicTrack, or an entirely new subclass of Track could be implemented, without altering the other components.

Is this sensible or nuts? Shortcomings and pitfalls? Many thanks in advance! fever

[dws]

I am currently working out the object model for what is basically a ticket tracking system.

What you're describing falls under the general heading of "workflow". There's a lot of literature scattered around that you can draw ideas from.

• This MSDN article talks about building workflow systems on top of SQL Server.
• Dragos Monolescu has a useful set of papers.
• A PDF of A Pattern Language for Workflow Systems is available in the PLoP97 conference proceedings.

[djantzen]

Yes, that's a better term for it. I kept wanting to call it "a ticket-tracking-like thingy" ;-) Thanks.

Monolescu's thesis looks like it addresses the issue directly, so that has booted Michael Moore and Rudy Rucker out of the top spot in my holiday reading list.

[pdcawley]

I reckon that what you're looking at here is the 'State' pattern rather than a 'Strategy'.

package Ticket;

use strict;
use warnings;

...

sub state {
    my $self = shift;
    $self->{state} ||= TicketState::New->new();
}

sub set_state {
    my $self = shift;
    my $new_state = shift;
    push @{$self->{statelog}}, $self->{state};
    $self->{state} = $new_state;
    return $self;
}

sub send_to_supervisor {
    my $self = shift;
    $self->state->send_ticket_to_supervisor(@_);
}

sub approve {
    my $self = shift;
    $self->state->approve_ticket($self, @_);
}

sub reject { 
    my $self = shift;
    $self->state->reject_ticket($self, @_);
}

package TicketState::New;

...


sub send_ticket_to_supervisor {
    my $self = shift;
    my $ticket = shift;
    
    my $supervisor = $SUPERVISORS{$ticket->topic}; # Deliberately naiv
+e
    $ticket->set_state(TicketState::PendingApproval->new);
    $supervisor->accept($ticket);
    return $ticket;
}

sub approve_ticket { die "You cannot approve a ticket in this state" }

sub reject_ticket { die "You cannot reject a ticket in this state" }

package TicketState::PendingApproval;

sub send_ticket_to_supervisor {
   die "Ticket was already sent to a supervisor!";
}

sub approve_ticket {
    my $self = shift;
    my($ticket, $supervisor) = @_;

    $ticket->set_state(TicketState::Approved->new
                          ->set_owner($supervisor));
    $supervisor->editorial_group->accept($ticket);
    return $ticket;
}

sub reject_ticket {
    my $self = shift;
    my($ticket, $supervisor) = @_;
    
    $ticket->set_state(TicketState::Rejected->new
                          ->set_owner($supervisor));
    $ticket->author->accept($ticket);
    return $ticket;
}

package TicketState::Rejected;

# Almost indistinguishable from TicketState::New
use base 'TicketState::New';

And so on.... Appropriate use of inheritance would mean that individual states would only have to know about the valid actions in that state, and their associated state transition rules, and it's easy to plug new states into the system. I've also found that when I use the State pattern it's easier to use meaningful names for actions without having to worry about whether an action is 'allowed' because the State system handles that for me -- I just move any state dependent behaviour into the appropriate state classes (or the approprate parent state object) and delegate happily.

One problem with the State pattern is that, until you're used to it, it can be hard to get a handle on the behaviour of the 'whole' system but I'd be tempted to argue that you should be reading your tests and use cases for that.

[djantzen]

State is definitely an important aspect of this, so I like the idea of maintaining that as a separate entity. I especially like the ability to store past states, as in some cases it may be necessary to step backward in the history of an entity in the system. I've been hoping to avoid hardcoding specific subroutines like send_ticket_to_supervisor, but on the other hand, the fact that those are in a distinct "logic" module means that different behavior could be achieved by overriding those methods or writing a new module.

Thanks for your thoughts pdcawley :)

[pdcawley]

The thing is, at some point you're going to have to code the 'what happens next' process. It may make sense though to add a do_next_thing method to your state class and then write:

sub TicketState::New::next_action { 'send_ticket_to_supervisor' }

sub TicketState::Pending::next_action { 'send_to_editorial_group' }

sub TicketState::do_next_thing {
    my $self = shift;
    my $action = $self->next_action;
    $self->$action(@_);
}

By doing things this way you get to give meaningful names to the individual actions handled by a state, but still have a simple dispatch system that simply calls $ticket->do_next_action on every ticket it dispatches.

If you're using the state simply to control the flow of an object through a system and you've not got other state dependent behaviour then you can probably get away with having a single state class and a handy dandy config file but I don't think I'd recommend starting out with one.

[theorbtwo]

My first question when seeing somthing like this is always (OK, it often isn't, but normaly should be) why aren't you using an existing system? It's by thinking about the problems with other WTDI that we come up with how the best way to do it is for our situation. If the reason is "a bad case of instutional NIH that I can't do anything about" or "for the fun of it" (in which I include "to learn"), that's one thing, but if the reason is "because I havn't looked at them", then that's somthing else. If there's some specific shortcoming, think about what caused that shortcoming very carefuly, so as to not duplicate it. At the same time, of course, you must be careful not to fall into an opposing trap.

I'll render another oppionion after reading your post -- perhaps.

---

Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).

[djantzen]

Good Question. What we're doing is very specific to our codebase and processes, and while our parent organization utilizes other systems for ticket-tracking in related but separate activities, they are not good candidates for our procedures. Given that our project already spans six languages and several hundred thousand lines of code, writing a few small modules and a couple of front-end CGIs for this one piece of functionality is preferable to trying to wire our API into someone else's (ill-suited) code. Overwhelmingly the useful functionality already exists in our codebase, and it's really just a matter of coordinating those elements, so I believe I can get this into working shape in probably under a thousand lines of code.

[pfaut]

You may want to look into Bricolage. Although it appears to do a lot more than you seem to be asking for, workflow is part of its feature set. Also, it is written in perl.

---
print map { my ($m)=1<<hex($_)&11?' ':'';
$m.=substr('AHJPacehklnorstu',hex($_),1) }
split //,'2fde0abe76c36c914586c';

[diotalevi]

I think you are mistaking your data for your code. Others have noted that this is a workflow process. In my day job I address this sort of problem with Lotus Workflow. The idea there is to write down the whole workflow process separate from your application and let the workflow engine do all the actual execution. (follow the link and do a brief scan of the product brief PDF to see the pretty pix). This isn't a new concept - it's just separating your data from your code.

I haven't seen anything in the perl world that even approaches LWF so that's a miss. If you can find a comfortable medium between writing an workflow engine and just hardcoding your workflow you'll be good. Anyhow, I just wanted to point out that you had the wrong orientation.

---

Fun Fun Fun in the Fluffy Chair

[djantzen]

To clarify, the data is the process definitions, or the rules that govern what happens under which circumstances. The code is spread between the workflow engine and process state tracking. That's definitely a helpful way of looking at it, although writing an engine to parse a custom rule-set is (I believe anyway) a very serious undertaking. But maybe that's why you're suggesting a compromise between a full workflow engine and hardcoding behavior? That feels right to me, especially since I strongly advocate the "build one to throw away" school of thought, and this is a first brush at something that will likely be reworked at some point.

I liked this quote from that IBM document: "Effective workflow processes have three basic components: data, process logic, and a directory of participants." (pg. 2)

Thanks diotalevi.

[diotalevi]

Yes well... for my paid work (which rarely involves perl) I have an fully functional Domino installation to fall back on where our directories are integrated with our Oracle HR databases. When I'm writing a workflow-enabled Domino application the who-when question is mostly separate from the how-what questions. So an Authorization to Spend/Buy/Sign form has a whole bunch of functionality related to it's function as a form. It's sort of like really smart paper - it does lots of fancy stuff but in the end it only goes where people send it.

When I add in Lotus Workflow then I describe the connections between the various states, what the person must do (a check list), what decisions the person must make, any timing related issues, etc. All of that is contingent on having a good directory. So it can tell that Ricky Ricardo/IT/SomeCompany is Marvin Martian/DSP/SomeCompany's manager, the team Marvin is on, etc etc. A basic implementation would have to use roles or titles or some way to flexibly define the workflow participants. In no uncertain terms let me stress that you don't ever put people's names into a process. You put things like "Workflow Development", "Corporate Auditor", "Global Purchasing Manager". The idea is that these labels are determined by your HR-bound directory so you maintain your process just by keeping your HR records up to date. Let me know if you want more information - this is my day off and I'm tired of typing this just now.

Update: Oh yes, I suggested a comprimize because a real workflow implementation is a decidedly non-trivial task and requires first-hand experience to get right.

---

Fun Fun Fun in the Fluffy Chair