Let’s say that we have an AST that holds integer nodes. We want to print double the value of all nodes. We can do something like this
Above solution works. Now let’s try to print triple the value. In order to do that we need to change class
IntegerNode has knowledge of how to print
triple value. Tomorrow if we have another node called
FloatNode then that node will have knowledge about how to
triple the value.
Nodes are merely storing information. And the representation of data should be separate from the data itself. So
FloatNode should not know about how to
Before we look at “double dispatch” let’s first look at “single dispatch”.
When we invoke a method in ruby we are using single dispatch. In single dispatch, method invocation is done based on a single criteria: class of the object. Most of the object oriented programming languages use
single dispatch system.
In the following case method
double is invoked solely based on the class of
As the name suggests in the case of
Double dispatch dispatching depends on two things: class of the object and the class of the input object.
Ruby inherently does not support “Double dispatch”. We will see how to get around that issue shortly. First let’s see an example in Java which support Double dispatch. Java supports
method overloading which allows two methods with same name to differ only in the type of argument it receives.
In the above case the method that would be invoked is decided based on two things: class of the object ( node ) and the class of the value (Integer or String). That’s why this is called
In ruby we can’t have two methods with same name and different signature because the second method would override the first method. In order to get around that limitation usually the method name has class name. Let’s try to write above java code in ruby.
If the above code is not very clear then don’t worry. We are going to look at visitor pattern in ruby and that will make the above code clearer.
Now let’s get back to the problem of traversing the AST. This time we are going to use “Double dispatch” so that node information is separate from representation information.
In visitor pattern
nodes define a method called
accept. That method accepts the visitor and then that method calls
visit on visitor passing itself as self.
Below is a concrete example of visitor pattern. You can see that
IntegerNode has method
accepts which takes an instance of
visitor as argument. And then
visit method of visitor is invoked.
Above code used only
IntegerNode. In the next example I have added
StringNode. Now notice how the
visit method changed. Now based on the class of the argument the method to dispatch is being decided.
Real world usage
You can read more about “double dispatch” in this article by Aaron Patterson.