Question

At the office, we ve applied simple Domain Specific Languages (DSLs) to several problem domains we encountered.

Basically, we parse (lex/yacc) the custom script into an expression tree. Every node in the expression tree has an .evaluate() method that gets called recursively, until the program is done. Nice, and simple as pie. Which is a good thing, because I know next to nothing about parsing techniques, compiler construction and whatnot (good thing my coworkers know a thing or two).

Now here is the challenge: the implementation we are currently working on needs the ability to

stop at any position in the tree
persist all state
and restore state/positon at any given time in the future.

Persiting the actual state should not be too hard, but the position in the tree (or the "callstack") befuddles me. How would one go about implementing such a system? Storing the position in the tree using some sort of ID s for every node? Or is evaluating the tree itself the wrong approach, and should we somehow transform it into something linear?

I m guessing this is a rather common problem, but I don t know what to look for. Any help on the correct terminology, nudges in the right direction, keywords to search on, design patterns to look at etc... are most welcome!

(Doing this in Win32/Dephi, but hopefully we can keep this language agnostic)

Answer 1

The position in the tree can be specified using a list of child numbers. Your evaluates would look something like this (quickly written; not compiled/tested):

public class Context {
    private Context parent; // set in constructor
    private int child;  // with get/set
}

public ReturnType evaluate(Context context) 
    context.setChild(context.getChild() + 1);
    context = new Context(context); // push a new context for calls
    // do evaluation - when calling kids, pass context            
}

The above should track the context as a list of numbers that tell which child you re currently processing.

Rather than implement that in each node type, I d recommend writing a decorator (or a superclass using a template method) to do it for you, such as:

// decorator
public class ContextTrackerEvaluator<T> implements Evaluator<T> {
    private Evaluator realEvaluator;
    public ContextTrackerEvaluator(Evaluator realEvaluator) {
        this.realEvaluator = realEvaluator;
    }
    public T evaluate(Context context) {
        context.setChild(context.getChild() + 1);
        context = new Context(context); // push a new context for calls
        realEvaluator.evaluate(context);
    }
}

// OR superclass w/ template method
public class EvaluatorBase<T> {
    public final T evaluate(Context context) {
        context.setChild(context.getChild() + 1);
        context = new Context(context); // push a new context for calls
        doEvaluate(context);
    }
    // subclasses override doEvaluate to do their real work
    protected abstract T doEvaluate(Context context);
}

If you use the decorator, make sure you decorate every node...

That gives you access to the context list.

You can then add a "stop context" parameter that you can compare (so you d have two contexts passed in and you could compare them to see if they match.

Hope this helps! -- Scott

友情链接