RSS

Software Language Engineering: The Visitor Pattern

15 Dec

This may feel like a slight detour; but believe me, it’s a necessary one. If you are already fully familiar with the Visitor pattern, you are free to skip this section.

The Visitor pattern is hardly the only way to handle grammar parsing; but I’ve been trying to find a better one for a couple of weeks now, and without much success. Thus, I must recommend it.

The Visitor pattern functions as a way to operate on a structure of objects, like our Abstract Syntax Tree, while evading the encapsulation of the algorithm within those objects. It is an approach from the outside, it visits; thus, the name. Unlike most design patterns, you can actually implement the approach, for most purposes, in a single package. I’ll explain how to do than in the second part of this addition.

1. The Recursive Nature of the Visitor Pattern

First, a word on the unusual structure.

Every visitable object is referred to as an “element”; and every element has an inherent method which receives a single visitor object as its parameter. Additionally, every visitor object has a method which receives an element as its singular parameter.

This may sound rather circular, but the meat of the work is done by the visitor’s method. When visit is called, with a specific instance of the element as its parameter type, a window opens to perform specific operations on the available materials (fields and methods) in the element. This window does not require any specific change to the element’s code.

So when is this visit method called? Every time the element’s inherent visitor-receiving method is called. Is this roundabout?

No. The visitor-receiving method may be called again, on other, related, objects, by the visitor’s element-receiving method. You can exit the circle any time you would like.

For the sake of clarity, imagine that the element’s method is called receive(Visitor visitor), and the visitor’s method is called visit(Element element). I’ll give you a more tangible example.

1.1. The Visitor Pattern at Work

Suppose we have an object structure describing a bicycle. Each bicycle part is an extension of BicycleElement, which implements our accept method. The parts include a number of tires, two pedals, a handbrake, a chain, a seat, and a frame. Each of these elements is interchangeable and has a score of properties that belong to it alone.

Putting together such a class structure is trivial for a Java programmer; but what if we want to inventory the parts of a bike? Display their features on an output stream (for simplicity, System.out), as an example? At the same time, this analysis software must remain separate from the software describing the part, in the name of the open/closed principle and the single responsibility principle. At least, if you’re a principled programmer, with the least bit of concern for the next person to touch your code, you want to follow those.

The problem is solved through double-dispatch. Your analysis class, let’s call it Analyzer, might have a set of Visitors that expect to receive each category of BicycleElement. Once your CompleteBikeElement is prepared, Analyzer would call its accept method with a class of Visitor. The accept method would call the visit method with itself (and all properties exposed), and the visit method would display the properties of the BicycleElement.

Naturally, you might be wondering how you would get the properties of every BicycleElement when only the CompleteBikeElement was passed to the Visitor. That’s where receive comes in. CompleteBikeElement has total access to each of its parts, and can easily pass a visitor (maybe the same one) to each of them.

2. Implementing a Visitor Pattern in a single package

I’ve implemented this in the SLE git under oberlin.builder.visitor.

You only need three classes; Element, Visitor, and VisitHandler. In fact, you arguably only strictly need Element and Visitor. Their code is fairly straightforward, remembering that they are all abstract.

Element:

package oberlin.builder.visitor;

public interface Element {
    public void accept(Visitor visitor);
}

Visitor (feel free to be a little creative with this one):

package oberlin.builder.visitor;

import java.util.Map;

public interface Visitor {
    public default void visit(Element element) {
        getHandlerMap().get(element.getClass()).handle(element);
    }
    
    public Map<Class<? extends Element>, VisitHandler> getHandlerMap();
    
    public default void addVisitHandler(Class<? extends Element> elementClass, VisitHandler handler) {
        getHandlerMap().put(elementClass, handler);
    }
    
    public default VisitHandler getVisitHandler(Class<? extends Element> elementClass) {
        return getHandlerMap().get(elementClass);
    }
}

VisitHandler:

package oberlin.builder.visitor;

public abstract class VisitHandler {
    public abstract void handle(Element element);
}

Done. Now, as an aside to get the point across, let’s build that little bicycle project I was talking about.

2.1. Using the Visitor Package

Let’s start with our bike parts. For the sake of brevity, I’m leaving out package and import statements as they’re fairly self-explanatory.

public class ChainElement implements Element {

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }

}

public class FrameElement implements Element {

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }

}

public class HandlebarElement implements Element {

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }

}

public class PedalElement implements Element {

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }

}

public class SeatElement implements Element {

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }

}

public class TireElement implements Element {

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }

}

They could be anything, of course; in this instance, we’re leaving the actual work to Visitor, and how it gets there to Element. It might even be wise to make it a Java 8 Default Method.

Lastly, the complete bike:

package bicycle;

import oberlin.builder.visitor.Element;
import oberlin.builder.visitor.Visitor;

import java.util.*;

public class CompleteBikeElement implements Element {
    
    private FrameElement frame = new FrameElement();
    private SeatElement seat = new SeatElement();
    private PedalElement leftPedal = new PedalElement();
    private PedalElement rightPedal = new PedalElement();
    private TireElement frontTire = new TireElement();
    private TireElement backTire = new TireElement();
    private HandlebarElement handle = new HandlebarElement();
    private ChainElement chain = new ChainElement();
    
    @Override
    public void accept(Visitor visitor) {
        frame.accept(visitor);
        seat.accept(visitor);
        leftPedal.accept(visitor);
        rightPedal.accept(visitor);
        frontTire.accept(visitor);
        backTire.accept(visitor);
        handle.accept(visitor);
        chain.accept(visitor);
    }

}

So, what does our visitor look like?

package bicycle;

import java.util.HashMap;
import java.util.Map;

import oberlin.builder.visitor.Element;
import oberlin.builder.visitor.VisitHandler;
import oberlin.builder.visitor.Visitor;

public class BikeVisitor implements Visitor {
    @SuppressWarnings("serial")
    Map<Class<? extends Element>, VisitHandler> map = new HashMap<Class<? extends Element>, VisitHandler>();
    {
        map.put(TireElement.class, new VisitHandler() {
            public void handle(Element element) {
                System.out.println("[Tire qualities]");
            }
        });
        map.put(FrameElement.class, new VisitHandler() {
            public void handle(Element element) {
                System.out.println("[Frame properties]");
            }
        });
        map.put(ChainElement.class, new VisitHandler() {
            public void handle(Element element) {
                System.out.println("[Chain manufacturing data]");
            }
        });
        map.put(SeatElement.class, new VisitHandler() {
            public void handle(Element element) {
                System.out.println("[Seat qualities]");
            }
        });
        map.put(PedalElement.class, new VisitHandler() {
            public void handle(Element element) {
                System.out.println("[Pedal qualities]");
            }
        });
        map.put(HandlebarElement.class, new VisitHandler() {
            public void handle(Element element) {
                System.out.println("[Handlebar qualities]");
            };
        });
    }

    @Override
    public Map<Class<? extends Element>, VisitHandler> getHandlerMap() {
        return map;
    }
}

And lastly, our analysis program, which doesn’t even need to be in the same package. (Well, it is, but it doesn’t have to be.)

package bicycle;

public class Analysis {

    public static void main(String[] args) {
        CompleteBikeElement bike = new CompleteBikeElement();
        bike.accept(new BikeVisitor());
    }

}

As you can see, the analysis itself doesn’t have to do much. In the past, a different visitor was implemented for each element, which is still occasionally useful. In this instance, to cut down on the number of classes, I simply cross-reference the class of the element on a map, and retrieve the functional interface with the material to operate on that specific type of element. It’s better practice than using instanceof, not because instanceof is slow, but because it’s usually a red light that you’re overlooking a feature of object-oriented languages. This is also referred to as a “bad code smell“. (Map may also be slightly faster, working it out in my head; but I haven’t done any benchmarking.)

The result?

[Frame properties]
[Seat qualities]
[Pedal qualities]
[Pedal qualities]
[Tire qualities]
[Tire qualities]
[Handlebar qualities]
[Chain manufacturing data]

Of course, any element could have broken itself down further, and may continue to. This is a very flexible pattern, and understanding double-dispatching can lead to some very efficient architectures. When you understand how it works, you’re ready to continue!

A Final Note

Speaking of bad code smell, it is also worth noting that double-dispatching is never to be used unless it is truly necessary. Extensive double-dispatching (or triple-dispatching, or—no. It hurts to think about.) can be very bad code smell in itself. If you’re even a little speculative, you may have noticed that excessively open Visitor patterns are asking for trouble.

Uncontrolled dynamic dispatching is like having your fingers tangled in string, or trying to untie a massive wad of Christmas lights before the holiday because someone put them in a box instead of twist-tying them properly. Dynamic dispatching is the box; used improperly, it promises that a year later, you will be dealing with a massive wad of tied up Labyrinthian code, and you’ll have zero fun untying it. BECAUSE REALLY, WHY DID YOU PUT THE CHRISTMAS LIGHTS IN AN EFFING BOX, MOM!?!?

Advertisements
 
 

Tags: , , , , , , , , , ,

One response to “Software Language Engineering: The Visitor Pattern

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: