Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm to write an event correlator. A fundamental part of the system will be a decision tree that recognizes the origin of the fault basing on recorded states and log files.

Often many accidents will differ with minor details and many decisions taken will be made basing on fuzzy, incomplete or unreliable data, but most of these decisions can be written down as binary logic functions.

Thing is, there will be a lot of them. I expect at least 100 nodes in the decision tree, and I may underestimate the value by an order of magnitude. And on top of that, as new, unexpected patterns emerge, unforseen failures happen leaving new traces, or with extension of the system new failure modes become viable, the decision tree will have to be maintained.

(and it won't always be a pure tree structure - some faults of the same effect have two or more modes of appearance, some of these branching off into different modes, e.g. event A means failure X, event B means: check event C. If C is true, it's also failure X, but if not, it's failure Y. Although I can always normalize it into X1 and X2, which are technically identical but different from the tree point of view.) Also, the tree will be often fairly deeply nested so I'm afraid a simple series of nested if() will quickly slip out of control.

Now my question is, how to store / write / build that tree so that it could be compilable into something the machine can digest, but still maintainable for the developers?

Note this is for an embedded system, so heavyweight solutions like JBoss don't really fit unless they appear only on the compiler side, and the final system runs a compiled ruleset in something much more machine friendly.

(the system is written in C++, it also makes extensive use of JSON, and will run on an ARM9 CPU if that's of any help.)

A sample of the tree

share|improve this question
    
By "maintaining" do you mean the decision tree can be changed at run time (i.e. some sort of scripting required) or it's ok to modify the program's source code (i.e it is a matter of proper object model)? 100 or even 1000 nodes doesn't seem too much. –  lorus Jan 9 '13 at 13:25
    
@lorus: Modifying source is okay. Still, each node has unique meaning, which must be understandable - trivially readable by the developer, and each end result is a certain combination of these (usually logical AND), and its path should be easily readable and reasonably modifiable too. Note that 100 nodes isn't too much in a fairly flat multi-branched tree maybe 2-3 nodes deep. Not if its structure is resembling more a balanced binary tree. I wouldn't call a 7-level nested if() a maintainable structure... –  SF. Jan 9 '13 at 14:17
    
Well, this can be achieved with simple DSL, which can be implemented using e.g. macros. The only problem: a tree structure would be flattened by such DSL and will not be visually equivalent to the tree, which is a problem.The solution came in mind is some visual tool naturally representing trees or even graphs... –  lorus Jan 9 '13 at 14:43
    
The structure doesn't really have to be a tree from the developer's point of view - may be flattened into independent strings of clauses leading to conclusions, but multiple re-evaluating the same topmost conditions (often involving SELECTs etc) over each leaf isn't really acceptable, so the actual compiled result should be more tree-like. Yes, a DSL is the answer, now the question is what should it look like. Also, with flat strings of conditions we lose perspective on how clauses conflict, interact or leave us with dead ends (undefined leaves). (still, maybe visualizing that is possible?) –  SF. Jan 9 '13 at 14:50
1  
@SF: Ok, now I think I understand what your real problem is. I guess what you need is some kind of CASE tool which can maintain the tree in a graphical form, for example as UML activity diagrams . The tool should allow C++ code generation from those diagrams, so you have a single source for tree & code. I did something comparable some years ago in Rational Rose. Maybe that's oversized or over your budget, but if not, it is a fine tool for those kind of things. There are a lot of other tools available (en.wikipedia.org/wiki/List_of_Unified_Modeling_Language_tools), pick your choice. –  Doc Brown Jan 10 '13 at 15:20
show 4 more comments

2 Answers

Here is an idea for such a DSL. Say you have 6 input variables (your "events"). Lets assume those variables are binary (the idea can be generalized to non-binary variables). Now your DSL should contain statements like

(0|*|1|0|1|1) => Action_A()
(0|0|1|0|0|*) => Action_B()
(1|1|1|0|*|*) => Action_C()
default       => ActionDefault()

Each row contains a precondition (the part left to the =>), saying which input variable must have which value. The part right to the => is the action to be applied. A "*" means that the corresponding input variable can be either 0 or 1. The semantics can be compared to the pattern matching mechanics of awk, perl, or xslt.

How does this help you? Well, now you can do two things

  • write a simple validator which checks that all your preconditions are mutally exclusive. If you don't want or need a "default" action, you can let this out and instead let your validator additionally check that you did not miss a case.

  • write a code generator which translates that DSL into C++ code, which may then look similar to this:

    if(event_1==0 && event_3==1 && event_4==0 && event_5==1 && event_6==1)
        Action_A();
    

The validator will help you to keep things maintainable, and the generated C++ code should compile into something "machine friendly", as you required.

If your input variables are not binary (100 nodes by a depth of 2-3 decisions is not possible just by binary inputs), you will have to extend that DSL, it should be straightforward how to accomplish that. For example, use (0,1,4|*|*) for a precondition (event_1==0 || event_1==1||event_1==4).

EDIT: if you have many input variables and the requirement to check only a few of them, this could be adapted by using "named parameters", for example

    (var_1==[0,1,4]|var_3==0|var_25==[1-10]) => Action_A()

Of course, you could also code this directly in C++, which won't become much longer, but the advantage of using a small, formal DSL is that now you have a chance to write a validator for this.

share|improve this answer
1  
I agree that a DSL is the way to go, but I'd suggest using it to create a data graph, and then have code that knows how to traverse it (like a backward-chaining inference engine). This would enable you to unit-test your code and rules separately, as well as provide a (possibly easier) means to update your rules in the field. –  TMN Jan 9 '13 at 18:16
    
@TMN: I would be happy to see an example for that kind of DSL. Can you post one? Perhaps that kind of answer would help the OP a little bit more than mine. Of course, my approach is a simple one, maybe too simple, but more smarter approaches typically need more complex tools / parsers / engines to deal with, which can be a drawback. –  Doc Brown Jan 9 '13 at 18:47
    
That's an interesting idea but I'm afraid it won't help. My conditions in this DSL would be long, long lines with lots and lots of asterisks. If we found the problem originates in input modules, there's no point analyzing any of 50 or so output module conditions, and vice versa - although at any point in analysis these two origins the data may finally point to power supply, or timing, or... you get the idea. –  SF. Jan 10 '13 at 10:11
    
@SF: see my edit. And if this does not help you immediately, perhaps this idea could be adapted further? –  Doc Brown Jan 10 '13 at 10:46
add comment

I am no C++ developer, but I think the rule declarations DSL can be implemented purely in C++.

First, there is a request object, containing all input parameters (e.g. as a map). This object can also cache an already checked conditions, rule check trace, and possibly some intermediate data.

class Request {
public:
    template<T> Value<T> get(Parameter<T>); // Returns the given parameter value.
    /* Returns a 3-state status for the given condition:
       - not checked yet
       - condition succeed
       - condition failed */
    ConditionCheckStatus getCheckStatus(Condition);
    void setCheckStatus(Condition, bool); // Caches the condition check status.
}

Such object should be constructed once per request and should be passed to a topmost rule.

A conditions can be expressed using a Condition class subclasses. The Condition checks whether it's already evaluated. If not - then evaluates itself and caches the evaluation check status. To build a complex conditions it is good to override &, | and ! operators:

class Condition {
public:
    inline bool check(Request &request) {
        switch (request->getCheckStatus(this)) {
        case COND_SUCCESS:
            return true;
        case COND_FAILURE:
            return false;
        }
        bool result = this->checkCondition(request);
        request.setCheckStatus(this, result);
        return result;
    }
    inline Condition &operator & (Condition &other) {return *new AndCondition(*this, other)}
    inline Condition &operator | (Condition &other) {return *new OrCondition(*this, other)}
    inline Condition &operator ! () {return *new NotCondition(*this)}
protected:
    virtual bool checkCondition(Request &) = 0;
}

A concrete conditions can be declared as global constants and may be combined with logical operators to build a more complex ones.

The Parameter template can be used to access a Request parameters in a type-safe manner. A concrete parameters can be declared as global constants. Parameters can also override operators to construct Conditions like this:

// Declare a "counter" input parameter.
const Parameter<int> Counter;

// Construct a "more than once" condition.    
const Condition &MoreThanOnce = Counter > 1;

A ruleset can be declared using Rule objects (also declared as global constants).

const Rule FailIfMoreThanOnce(
    MoreThanOnce, /* The condition */
    Failure,      /* The rule invoked if condition succeed */
    OtherRule     /* The rule invoked if condition failed */);


// ... Other rule definitions

const Rule TopRule(SomeCondition1 | SomeCondition2, SomeRule1, SomeRule2);

A decision tree evaluation would look like this:

Request request;
// Fill the request.
bool result = TopRule.check(request);
// Handle the result.

Note that all Parameters, Conditions and Rules are stateless. The only mutable object is Request, which is constructed once per request and collects the evaluated data.

The rules, parameters and conditions may have a meaningful names, can be constructed using operators. There is almost none syntax overhead for their declaration. The even shorter declarations can be done using macros.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.