Patterns in Jep

Jep uses several design patterns to structure the code and provide a flexible and extensible framework for parsing and evaluating mathematical expressions.

Jep: Facade

The main Jep class is an example of the Facade pattern. It

"provides a simple interface to a complex system of classes".

The Jep class provides a Facade to the various components including the Parser, Evaluator, VariableTable FunctionTable, OperatorTableI, PrintVisitor, factory classes VariableFactory, NodeFactory, NumberFactory and any additional components implementing JepComponent.

Several other classes also exhibit the Facade pattern, for example the StandardParser and ConfigurableParser classes both serve as the front end to a system of classes that parse expressions.

Evaluator, Parser: Strategy

Many components, like the Evaluator use the Strategy pattern,

a behavioral design pattern that lets you define a family of algorithms, put each of them into a separate class, and make their objects interchangeable.

There are several different evaluators: FastEvaluator, RealEvaluator, StandardEvaluator, Unchecked Evalator each implements the Evaluator interface:

    public interface Evaluator extends JepComponent {
        Object evaluate(Node node) throws EvaluationException;
        Object eval(Node node) throws EvaluationException;
    }

The first method is the main entry point, called from the Jep class and the second method is a callback used by functions implementing the CallbackEvaluationI interface. In terms of the strategy pattern the Jep class forms the Context. The client calls the jep.evaluate(Node) method which in turn calls the evaluator.evaluate(Node) method of the concrete implementation.

Parsing can also be considered as an example of the strategy pattern. The Parser interface defines a Node parse(Reader) methods which concrete implementations like the StandardParser or ConfigurableParser implements. use the

Node: Composite

The central object in Jep is a tree of Nodes that represents a mathematical expression. This is an example of the Composite pattern,

"a structural design pattern that lets you compose objects into tree structures and then work with these structures as if they were individual objects."

There are four main types of nodes: ASTConstant, ASTOpNode, ASTVarNode, ASTFunNode as well the SimpleNode that provides a base class for these classes. Expressions are referred to using the root node of the tree using the Node interface.

NodeFactory, VariableFactory, NumberFactory: Abstract Factory

Node trees are built by the Parser using the NodeFactory class to construct individual nodes. This is an example of the Abstract Factory pattern,

"a creational design pattern that lets you produce families of related objects without specifying their concrete classes."

Here the NodeFactory has Factory methods to create each type of node. Only one subclass of NodeFactory is used in Jep, the LineNumberingNodeFactory that adds line and column numbers to the nodes.

Two other Abstract Factory classes are used in Jep: VariableFactory and NumberFactory. Subclasses of the VariableFactory can be used to create Variables of different types, for example the BoundVariableFactory creates Jep BoundVariables that are bound to other java variables, like fields in a class.

ConfigurableParser: Builder

The ConfigurableParser can be considered as an example of the Builder pattern:

"a creational design pattern that lets you construct complex objects step by step. The pattern allows you to produce different types and representations of an object using the same construction code."

Here a Parser is constructed by adding:

A Tokenizer to break the input string into tokens.
Various TokenMatcher objects that match different types of tokens.
A TokenFilter to filter out unwanted tokens like removing whitespace.
A GrammarParser to parse the tokens and builds a Node tree.
Various GrammarMatch objects that match particular sequences of tokens like arrays or function calls.

These can be set up to produce a parsers that recognize many different syntaxes for mathematical expressions.

One particular subclass the StandardConfigurableParser is an example of the Director pattern that

"A structural pattern that defines the order in which to call the construction steps, so you can create and reuse specific configurations of products."

In this case it sets up a ConfigurableParser with the default grammar for Jep.

TokenMatcher: Factory Method

TokenMatcher is another example of the Factory Method pattern,

"a creational design pattern that provides an interface for creating objects in a superclass, but allows subclasses to alter the type of objects that will be created."

Each class that implements TokenMatcher has an Token match(String s) factory method that returns different types of Token if the start of the string matches a pattern, or null if it does not match. Many of these use regular expressions to match the tokens and RegExpTokenMatch serves as a base class for these matchers, its match(String) method checks the input against the pattern if it matches calls the Token buildToken(String) factory methods specified by the TokenBuilder interface.

TokenMatcher, GrammarMatcher: Chain of Responsibility

The TokenMatcher and GrammarMatcher classes can be considered examples of the Chain of Responsibility pattern.

"a behavioral design pattern that lets you pass requests along a chain of handlers. Upon receiving a request, each handler decides either to process the request or to pass it to the next handler in the chain.

Each matcher is responsible for matching a particular type of input. If it succeeds, it return a Token or Node respectively, otherwise it returns false, and the next matcher in the chain is tried.

Rather than each matcher having a link to the next item in the chain, needed for a strict implementation of a chain of responsibility, the matchers are stored in a list, and a simple loop is used to match each in turn:

    for (TokenMatcher tm:matchers) {
        Token t = tm.match(substr);
        if (t!=null)
            return t;
    }
    return null;

A consequence of this structure is that the order that TokenMatchers are added to the parser is very important. Earlier rules are tried before later rules, and if the earlier rule succeeds the later rule is never tested.

OperatorToken: Prototype

"a creational design pattern that lets you copy existing objects without making your code dependent on their classes." Prototype

For most types of token the TokenMatcher creates a new instance of the Token class. However, the OperatorTokenMatcher uses the Prototype pattern to create a new instance of OperatorTokens. During initilisation, the OperatorTokenMatcher creates a SortedMap<String,OperatorToken> with one entry for each type of operator.

When the OperatorTokenMatcher matches a token, it looks up the operator in the map and returns a copy of the OperatorToken using its OperatorToken.clone() method. This new object can have context specific properties, like line and column numbers but inherits most properties from the prototype.

The Flyweight pattern, could have been used here to reduce the memory footprint, but OperatorToken is a small object not justifying and the overhead of the Flyweight pattern.

The Visitor pattern

Many different classes that perform operations, like evaluation or printing, on the tree of nodes are example of the Visitor pattern,

a behavioral design pattern that lets you separate algorithms from the objects on which they operate.

Here the algorithms, like evaluation, operate on trees of Nodes. The ParserVisitor interface defines four methods that each Visitor must implements.

    Object visit(ASTConstant node, Object data) throws JepException;
    Object visit(ASTVarNode node,  Object data) throws JepException;
    Object visit(ASTOpNode node,   Object data) throws JepException;
    Object visit(ASTFunNode node,  Object data) throws JepException;

Each type of node has a method Object jjtAccept(ParserVisitor visitor, Object data) that simple calls the appropriate visit method.

    public Object jjtAccept(ParserVisitor visitor, Object data)  throws JepException
    {
       return visitor.visit(this, data);
    }

When a visitor wants to process a node, it calls the jjtAccept method on that node, which in-turn calls the appropriate visit method. This pattern effectively performs double-dispatch: the appropriate visit method is called depending on the type of node and the visitor.

StandardEvaluator

For example the StandardEvaluator evaluates equations using code like:

    public Object evaluate(Node node) throws EvaluationException {
        stack.clear();
        node.jjtAccept(this, null); // this is the StandardEvaluator
        return stack.pop();
    }

With visit methods for handling each type of node

    public Object visitConstant(Node node) throws EvaluationException {
        Object o = node.getValue();
        stack.push(o);
        return null;
    }
    public Object visit(ASTVarNode node, Object data) throws EvaluationException {
        Variable var = node.getVar();
        Object o = var.getValue();
        stack.push(o);
        return null;
    }
    // Behaviour is the same for operators and functions    
    public Object visit(ASTFunNode node, Object data) throws EvaluationException {
        visitFun(node);
        return null;
    }
    public Object visit(ASTOpNode node, Object data) throws EvaluationException {
        visitFun(node);
        return null;
    }
    void visitFun(Node node) throws EvaluationException {
        PostfixMathCommandI pfmc = node.getPFMC();
         // loop through and evaluate each child
         for(Node child : node.children()) {
            // recursive call to visitor for each child
            // pushing results onto the stack
             child.jjtAccept(this, null);   
         }
         // run the function
         pfmc.setCurNumberOfParameters(nchild);
         pfmc.run(stack); // result left on stack
        return null;
    }

Other Visitors

This pattern allows other classes that want to operate on the node tree to be implemented by simply implementing the visit methods and an initial call jjtAccept(this,root) on the root of the tree.

Two classes DoNothingVisitor and DeepCopyVisitor make it easier to define visitors. DoNothingVisitor visits each node of the tree in a depth first order, but does nothing. Sub-classes only need to implement some of the visit methods. Visitors that want to return a modified tree of nodes can subclass DeepCopyVisitor who's default visit methods produce a copy of each node.

Other visitors include the PrintVisitor, the SubstitutionVisitor that can perform substitutions on expression trees. and the TestingVisitor that tests each node using a Predicate<Node>, return true if every node passes.

Visitor Alternatives, Pattern Matching

With its double indirection, the visitor pattern is slower than the less elegant alternative of using instanceof and casting.

    if(node instanceof ASTConstant)
        return visit((ASTConstant) node,data);
    if(node instanceof ASTVarNode)
        return visit((ASTVarNode) node,data);
    if(node instanceof ASTOpNode)
        return visit((ASTOpNode) node,data);
    if(node instanceof ASTFunNode)
        return visit((ASTFunNode) node,data);

Since Java 14 it can be expressed slightly more elegantly using JEP 305: Pattern Matching for instanceof.

    if(node instanceof ASTConstant cn)
        return visit(cn,data);
    if(node instanceof ASTVarNode vn)
        return visit(vn,data);
    if(node instanceof ASTOpNode on)
        return visit(on,data);
    if(node instanceof ASTFunNode fn)
        return visit(fn,data);

and since Java 17 even more succinctly using JEP 441: Pattern Matching for switch.

    return switch(node) {
        case ASTConstant cn -> visit(cn,data);
        case ASTVarNode  vn -> visit(vn,data);
        case ASTOpNode   on -> visit(on,data);
        case ASTFunNode  fn -> visit(fn,data);
        default ->
            throw new JepException("Illegal Node Type Encountered");
    };

Pattern matching is described in JEP 441 as generally more transparent and straightforward than the visitor pattern. Together with the algebraic data type Records and Sealed Classes it allows a more Data-Oriented Programming style.

A still faster method used in the FastEvaluator uses the ID of each node set at parse time.

    switch (node.getId()) {
        case JccParserTreeConstants.JJTOPNODE:
            return visitFun(node);
        case JccParserTreeConstants.JJTVARNODE:
            return visitVar(node);
        case JccParserTreeConstants.JJTFUNNODE:
            return visitFun(node);
        case JccParserTreeConstants.JJTCONSTANT:
            return visitConstant(node);
}

For very large trees, the recursive algorithm used by visitors may yield a StackOverflowError. The PrefixTreeWalker and PostfixTreeWalker using a non recursive tree transversal algorithm that overcomes this problem. They define visit methods similar to the above, which subclasses can override.

GenericVisitor

The ParserVisitor returns an Object and takes and Object data as context data, this means that arguments and results will often need to be cast to an appropriate type.

This casting can be eliminated using Generics.

Generics enable types (classes and interfaces) to be parameters when defining classes, interfaces and methods. Much like the more familiar formal parameters used in method declarations, type parameters provide a way for you to re-use the same code with different inputs.

For example the GenericVisitor has three type parameters, <R> the return type, <D> type of context data and <E> the type of exceptions that can be thrown. Implementing classes specify all three types. For instance the TestingVisitor is specified with a Boolean return type, Predicate<Node> context type, and JepException exception type:

    public class TestingVisitor implements
        GenericVisitor<Boolean,Predicate<Node>,JepException> { ... }

So its visit methods has a return type of Boolean and context type Predicate<Node> meaning we can simply apply the predicate to the node, without the need for casting.

    public Boolean visit(ASTConstant node, Predicate<Node> pred) throws JepException {
        return pred.test(node);
    }

Other Patterns

PublishingVariable: Observer

In previous versions of Jep, Variable and VariableTable implemented the deprecated java.util.Observable class. Since Jep 4.1 this has been removed and replaced with PublishingVariable package. Classes in the package implement the Observer pattern,

a behavioral design pattern that lets you define a subscription mechanism to notify multiple objects about any events that happen to the object they’re observing.

Here both PublishingVariable and PublishingVariableTable allow classes to subscribe to changes to individual variables or the whole table. A typical subscriber class would extend VariableTableSubscriber and implement methods called when variables change.

     var vt = new PublishingVariableTable();
     var vts = new VariableTableSubscriber() {
         @Override
         protected void variableChanged(String name, Object oldValue, Object newValue) {
             System.out.println("variableChanged " + name + " " + newValue);
         }
     
         @Override
         protected void variableAdded(String name, Object value) {
             System.out.println("variableAdded " + name + " " + value);
         }
     };
     vt.subscribe(vts);
     Jep jep = new Jep(vt, new PublishingVariableFactory());
     jep.setVariable("x", 5.0);     // trigger messages
     Node n = jep.parse("y=x^2");   // trigger messages
     jep.evaluate(n);               // trigger messages

Decorator pattern

The Decorator pattern is

"a structural design pattern that lets you attach new behaviors to objects by placing them inside special wrapper objects, called decorators."

There are a few sub-classes of VariableTable that add features to the table: CaseInsensitiveVariableTable that ignores the case of variables; and PublishingVariableTable subscribers to observe changes to variables. It might be useful to create a VariableTable that has both features. This can by following the Decorator pattern similar to that found in the java.io package various Reader classes can take other Readers as arguments to their constructors

    BufferedReader in = new BufferedReader(new FileReader("foo.in"));

In Jep, the public VariableTable(VariableTable tbl) constructor is a copy constructor so we need a different syntax. Both classes extend the DecoratingVariableTable that has three protected constructors:

protected DecoratingVariableTable() a non decorating default constructor
protected DecoratingVariableTable(VariableTable tbl) a copy constructor
protected DecoratingVariableTable(VariableTable tbl, boolean flag) a decorating constructor.

That are used by the sub-classes to create a new table that decorates and existing table. Both sub-classes have static factory methods to created decorator instances: CaseInsensitiveVariableTable.decoratorInstance(VariableTable) and PublishingVariableTable.decoratorInstance(VariableTable).

These can be used to create a new table that has both features:

    PublishingVariableTable vt = 
        PublishingVariableTable.decoratorInstance(
            CaseInsensitiveVariableTable.decoratorInstance(
                new StandardVariableTable());

The DecoratingVariableTable delegates all methods to the base VariableTable if set, otherwise superclass methods are called. For example

    public Variable addVariable(String name,Object value) throws JepException {
        return base != null
            ? base.addVariable(name, value)
            : super.addVariable(name, value);
    }

If a subclass need to add special behaviour, it can override the method and call the base method to get the default behaviour. For example the PublishingVariableTable overrides the addVariable method to first add a variable to the base table and then notify subscribers that variable has been added.

Other example of the Decorator pattern in Jep include the NullWrappedFunctionTable

The classes in the Overloaded Functions package expands on the Decorator pattern to allow function to be overloaded with a pair of functions depending on a predicate. For example we could define an atan function that can take one or two arguments, with one argument it behaves like the standard atan and with two arguments it behaves like the atan2 function.

    UnaryFunction uf = new ArcTangent();
    BinaryFunction bf =new ArcTangent2();
    AlternateFunctions af = new AlternateFunctions(uf, bf);
    jep.addFunction("atan",af);
    jep.reinitializeComponents();

When the Object evaluate(Node node, Evaluator pv) method is called it delegates to either of the component functions based on the number of arguments.

Adapter pattern

The Adapter pattern is

"a structural design pattern that allows objects with incompatible interfaces to work together."

The UnaryFunction and BinaryFunction and NaryBinaryFunction classes with static factory methods to adapt Function, BiFunction, to PostfixMathCommandI objects that can be used as functions in Jep.

    public static UnaryFunction instanceOf(final Function<Object,? super Object> fun) {
    return new UnaryFunction() {
        private static final long serialVersionUID = 400L;

        @Override
        public Object eval(Object l) {
            return fun.apply(l);
        }};
    }

Singleton pattern

The Singleton pattern is

"a creational design pattern that lets you ensure that a class has only one instance, while providing a global access point to this instance."

In Jep there are only a few uses of the singleton pattern as we don't want to limit use cases say a multiple thread environment. One use of the pattern is the NullPrintVisitor a do-nothing PrintVisitor. The same instance can be used in multiple threads. The NullParser also provides a singleton instance.

Jep Java

Advanced Features