The former parts of this series of articles analyzed several classic GoF patterns, Command and Strategy in the first one, Template and Observer in the second, Decorator and Chain of Responsibility in the third, showing how that they can be considered obsolete. In fact, when reviewed under a functional lens, it is evident that a few functions can implement the same semantic in a far less convoluted and more straightforward way. In this forth and last article I will try to do the same with 2 more patterns, the Interpreter and the Visitor ones.

The Interpreter pattern

The Interpreter pattern is commonly used when it is required to evaluate expressions written in a specific formalism. To give a practical example of how this works let’s try to implement an interpreter for reverse polish notation expressions. In this notation the operator follows its operands and then, assuming that each operator has a fixed number of operands, the operations precedence can be defined without using any parenthesis and evaluated using a stack. For example this expression

String expression = "7 3 - 2 1 + *";

can be evaluated in a sequence of step as it follows:

– put 7 on the stack
– put 3 on the stack
– take the last 2 values on the stack, subtract the second from the first (7-3) and put the result (4) on the stack
– put 2 on the stack
– put 1 on the stack
– take the last 2 values on the stack, add the second to the first (2+1) and put the result (3) on the stack
– take the last 2 values on the stack, multiply the second by the first (4*3) and put the result (12) on the stack

If the expression is well formed at the end of its evaluation there will be one single item in the stack corresponding to the result of the evaluation of that expression. The first necessary abstraction to implement the Interpreter pattern is a generic Expression that when interpreted returns its result, an int our case.

interface Expression {
    int interpret();
}

The simplest concrete implementation of this Expression is a just a Number, a wrapper of an int that when interpreted return the int itself.

public class Number implements Expression {
    private final int n;

    public Number(int n){
        this.n = n;
    }

    @Override
    public int interpret() {
        return n;
    }
}

We also need to provide the Expressions implementing the operations used in the expression to be evaluated. We will have an Add expression that will be created with a left and a right expressions and when interpreted will return the sum of the results of the evaluations of these expressions.

public class Add implements Expression{

    private final Expression leftExpression;
    private final Expression rightExpression;

    public Add(Expression leftExpression,Expression rightExpression ){
        this.leftExpression = leftExpression;
        this.rightExpression = rightExpression;
    }

    @Override
    public int interpret() {
        return leftExpression.interpret() + rightExpression.interpret();
    }
}

In the same way the Subtract expression will return the difference between the left and right expression

public class Subtract implements Expression{

    private final Expression leftExpression;
    private final Expression rightExpression;

    public Subtract(Expression leftExpression,Expression rightExpression ){
        this.leftExpression = leftExpression;
        this.rightExpression = rightExpression;
    }

    @Override
    public int interpret() {
        return leftExpression.interpret() - rightExpression.interpret();
    }
}

while the Product one will multiply them.

public class Product implements Expression{

    private final Expression leftExpression;
    private final Expression rightExpression;

    public Product(Expression leftExpression,Expression rightExpression ){
        this.leftExpression = leftExpression;
        this.rightExpression = rightExpression;
    }

    @Override
    public int interpret() {
        return leftExpression.interpret() * rightExpression.interpret();
    }
}

Moreover we need 2 helper methods, one checking if a given symbol represent on operator

public boolean isOperator(String s) {
    return s.equals("+") || s.equals("-") || s.equals("*");
}

and another one creating an Expression instance when passed with the operator symbol and its left and right operands.

public Expression getOperator(String operator, Expression left, Expression right) {
    switch (operator) {
        case "+":
            return new Add(left, right);
        case "-":
            return new Subtract(left, right);
        case "*":
            return new Product(left, right);
    }
    thorw new RuntimeException("Unknown operator: " + operator); 
}

At this point we’re ready to develop a method evaluating our reverse polish notation expression.

public static int evaluate(String expression) {
    Stack<Expression> stack = new Stack<>();
    for (String s : expression.split(" ")) {
        if (isOperator(s)) {
            Expression right = stack.pop();
            Expression left = stack.pop();
            stack.push(getOperator(s, left, right));
        } else {
            Expression i = new Number(Integer.parseInt(s));
            stack.push(i);
        }
    }
    return stack.pop().interpret();
}

Here we have an empty stack where we accumulate the results of the partial expression evaluations. The expression String is split in tokens and for each token we check if it is an operator. In this case it pops 2 expressions from the top of the stack, creates another expression applying the operation represented by the parsed symbol to those expressions and puts it back on the stack. Conversely it assumes that the token represents an int, wraps it into a Number expression and push it on the stack. To keep this example as simple as possible the error handling is not implemented and it’s assumed that the parsed expression is well-formed. If so when all the tokens have been iterated there will be one single Expression inside the stack that when interpreted will return the expression’s result.

Passing our original reverse polish notation expression to the evaluate method it will return 12 as expected.

assertEquals( 12, evaluate("7 3 - 2 1 + *") );

As usual it’s now time to check if we can achieve the same result in a more compact and natural way through a more functional approach. First of all we can notice that the definitions of the operators as implementations of the Expression interface is wastefully verbose. We could actually use lambdas to create a dictionary of those operation, or in other words a Map having as key a symbol and as value the IntBinaryOperator (a BinaryOperator working on primitive ints and thus allowing to avoid boxing and unboxing) executing the operation corresponding to that symbol.

static Map<String, IntBinaryOperator> opMap = new HashMap<>();

static {
    opMap.put("+", (a, b) -> a + b);
    opMap.put("*", (a, b) -> a * b);
    opMap.put("-", (a, b) -> a - b);
}

At this point it is straightforward to rewrite the former evaluate method in an easier way putting directly Integers instead of Expression on the evaluation Stack.

public static int evaluate(String expression) {
    Stack<Integer> stack = new Stack<>();
    for (String s : expression.split(" ")) {
        IntBinaryOperator op = opMap.get( s );
        if (op != null) {
            int right = stack.pop();
            int left = stack.pop();
            stack.push(op.applyAsInt( left, right ));
        } else {
            stack.push(Integer.parseInt(s));
        }
    }
    return stack.pop();
}

As we did before we start with an empty Stack and we split the original expression in tokens. If the traversed token is a key in the operations Map we apply the corresponding operation to the last 2 item on the stack. Otherwise we assume it is a number (once again we are not implementing any error check for brevity) and we put the number itself on the stack. If the expression is well-formed after having iterated all the tokes the stack will contain a single value that will be the result of the expression’s evaluation. We can check that passing our testing expression to this second implementation of the evaluate() method will return 12 as expected.

The Visitor pattern

In object-oriented programming the Visitor pattern is commonly used when it is required to add new operations to existing objects but it’s impossible (or not wanted for design reason) to modify the objects themselves and add the missing operations directly inside their implementation. To allow this each object of our domain must have a method accepting a Visitor and passing itself to the that Visitor and then have to implement an interface like the following.

interface Element {
    <T> T accept(Visitor<T> visitor);
}

At this point we can define a simple business domain and show how it could be visited by different Visitors with different purposes. For this example our domain model will be made by simple geometric shapes.

public static class Square implements Element {
    public final double side;

    public Square(double side) {
        this.side = side;
    }

    @Override
    public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}

public static class Circle implements Element {
    public final double radius;

    public Circle(double radius) {
        this.radius = radius;
    }

    @Override
    public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}

public static class Rectangle implements Element {
    public final double width;
    public final double height;

    public Rectangle( double width, double height ) {
        this.width = width;
        this.height = height;
    }

    @Override
    public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}

As anticipated all classes of our domain have to implement the Element interface. They do so all in the same way, by passing themselves to the visitor. We can then define a Visitor interface declaring an abstract method for each of the type of objects it will be required to visit.

interface Visitor<T> {
    T visit(Square element);
    T visit(Circle element);
    T visit(Rectangle element);
}

This is why, despite the accept() methods of all objects in our domain have exactly the same implementation, we cannot generalize them in a common abstract class, or even better move it directly into the Element interface as one of its default method. In fact the compile-time type of the object invoking the visitor is necessary to determine which one among the different overloaded versions of the visit method has to be invoked. It is now possible to create different concrete implementations of this Visitor interface. For instance we can have one computing the areas of the different shapes

public static class AreaVisitor implements Visitor<Double> {

    @Override
    public Double visit( Square element ) {
        return element.side * element.side;
    }

    @Override
    public Double visit( Circle element ) {
        return Math.PI * element.radius * element.radius;
    }

    @Override
    public Double visit( Rectangle element ) {
        return element.height * element.width;
    }
}

and another one that calculates their perimeters.

public static class PerimeterVisitor implements Visitor<Double> {

    @Override
    public Double visit( Square element ) {
        return 4 * element.side ;
    }

    @Override
    public Double visit( Circle element ) {
        return 2 * Math.PI * element.radius;
    }

    @Override
    public Double visit( Rectangle element ) {
        return ( 2 * element.height + 2 * element.width );
    }
}

We can finally put these visitors at work calculating the sum of the areas and perimeters of a List of shapes.

public static void main(String[] args) {
    List<Element> figures = Arrays.asList( new Circle( 4 ), new Square( 5 ), new Rectangle( 6, 7 ));

    double totalArea = 0.0;
    Visitor<Double> areaVisitor = new AreaVisitor();
    for (Element figure : figures) {
        totalArea += figure.accept( areaVisitor );
    }
    System.out.println("Total area = " + totalArea);

    double totalPerimeter = 0.0;
    Visitor<Double> perimeterVisitor = new PerimeterVisitor();
    for (Element figure : figures) {
        totalPerimeter += figure.accept( perimeterVisitor );
    }
    System.out.println("Total perimeter = " + totalPerimeter);
}

What deserves to be noticed here is what the Visitor actually does: it allows to define a different method for each type of object with which it is invoked. In functional programming there’s a more natural and more powerful idiom to achieve the same result: pattern matching. Actually for this use case it would have been enough to have a switch statement that works on class and I really wonder why this is not yet possible in Java while in Java 7 they added the possibility to switch on String that in my opinion it’s almost useless and also a bad practice in most circumstances. That said it is possible to implement a simple utility class that could allow us to have a similar feature as it follows.

public class LambdaVisitor<A> implements Function<Object, A> {
    private Map<Class<?>, Function<Object, A>> fMap = new HashMap<>();

    public <B> Acceptor<A, B> on(Class<B> clazz) {
        return new Acceptor<>(this, clazz);
    }

    @Override
    public A apply( Object o ) {
        return fMap.get(o.getClass()).apply( o );
    }

    static class Acceptor<A, B> {
        private final LambdaVisitor visitor;
        private final Class<B> clazz;

        Acceptor( LambdaVisitor<A> visitor, Class<B> clazz ) {
            this.visitor = visitor;
            this.clazz = clazz;
        }

        public LambdaVisitor<A> then(Function<B, A> f) {
            visitor.fMap.put( clazz, f );
            return visitor;
        }
    }
}

The LambdaVisitor class implements a Function then transforming a generic Object in a result of type A. The on() method of this utility class is the one through which we can define the behavior of this Function. It accepts a Class as argument and return an instance of its Acceptor inner class. This class has only one single method then() accepting a Function. In other words this function when applied to an instance of B, the Class passed to the on() method, produces a result of type A, the result that the LambdaVisitor function is expected to return. The pair Class, Function is registered on a Map contained in the LambdaVisitor. Finally the then() method returns the original LambdaVisitor instance thus allowing to fluently register another Function for a different class.

Let’s try to put this at work for our original task. For example, we can define a Function that when applied to one of the shape in our domain model returns its area.

static Function<Object, Double> areaCalculator = new LambdaVisitor<Double>()
        .on(Square.class).then( s -> s.side * s.side )
        .on(Circle.class).then( c -> Math.PI * c.radius * c.radius )
        .on(Rectangle.class).then( r -> r.height * r.width );

Here when this function is applied to a shape the LambdaVisitor selects the function defined for the class of that object and applies it to the object itself. For instance when it is passed with an instance of Square is selects the function

s -> s.side * s.side

and applies it to the that object in order to return the area of the Square. Note that thanks to type inference we don’t have to repeat the type Square into the declaration of the arguments of the lambda: the then() method already expects an instance of the same Class with which the on() method as been invoked. Similarly we can define a second function calculating the perimeters of the different shapes.

static Function<Object, Double> perimeterCalculator = new LambdaVisitor<Double>()
        .on(Square.class).then( s -> 4 * s.side )
        .on(Circle.class).then( c -> 2 * Math.PI * c.radius )
        .on(Rectangle.class).then( r -> 2 * r.height + 2 * r.width );

At this point it is straightforward to use these functions to calculate the sum of the areas and perimeters of all the shapes in the former List.

public static void main( String[] args ) {
    List<Object> figures = Arrays.asList( new Circle( 4 ), new Square( 5 ), new Rectangle( 6, 7 ) );

    double totalArea = figures.stream().map( areaCalculator ).reduce( 0.0, (v1, v2) -> v1 + v2 );
    System.out.println("Total area = " + totalArea);

    double totalPerimeter = figures.stream().map( perimeterCalculator ).reduce( 0.0, (v1, v2) -> v1 + v2 );
    System.out.println("Total perimeter = " + totalPerimeter);
}

In this series of 4 articles I hope I’ve demonstrated that many of the traditional GoF patterns can be made more compact and easy to use when reimplemented with functional idioms. All the code examples used through these articles are available here.

Gang of Four Patterns in a Functional Light: Part 4

About The Author
-

3 Comments

  • Art
    Reply

    In LambdaVisitor, you shouldn’t use Class as a Map key, because it breaks subclassing. This is one of the reasons the Java designers don’t let you switch on class. (Number.class != Integer.class, etc, even though Integer extends Number)

    • Ian Fairman
      Reply

      I agree that’s a problem, but not an insurmountable one. You could use the “computeIfAbsent” method on map to check if a visitor has been registered for a superclass when you call apply.

  • Ian Robertson
    Reply

    It’s important to note that the LambdaVisitor example looses one of the nice elements of the original Visitor Pattern, namely that you have a compile-time guarantee that your visitor is able to handle all types. You can still do that functionally, at the expense of the generality LambdaVisitor provides, with a method such as:

    public T ShapeVisitor shapeVisitor(Function squareFunc, Function circleFunc, Function rectFunc)

    Notably, this method can leverage LambdaVisitor behind the scenes to handle the type-dispatch plumbing that polymorphism provides in the traditional visitor pattern.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>