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
1class IntegerNode 2 def initialize(value) 3 @value = value 4 end 5 6 def double 7 @value * 2 8 end 9end 10 11class Ast 12 def initialize 13 @nodes = [] 14 @nodes << IntegerNode.new(2) 15 @nodes << IntegerNode.new(3) 16 end 17 18 def print_double 19 @nodes.each do |node| 20 puts node.double 21 end 22 end 23end 24 25ast = Ast.new 26ast.print_double # => 4 6
Above solution works. Now let's try to print triple the value. In order to do that we need to change class IntegerNode. And 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 double and triple the value.
Nodes are merely storing information. And the representation of data should be separate from the data itself. So IntegerNode and FloatNode should not know about how to double and triple.
To take the data representation code out of nodes we can make use of visitor pattern . Visitor pattern uses double dispatch .
Before we look at "double dispatch" let's first look at "single dispatch".
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 node.
1node.double
Double dispatch
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.
1class Node 2 def double(Integer value); value *2; end 3 def double(String value); Integer.parseInt(value) * 2; end 4end 5 6node.double(2) 7node.double("51")
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 Double dispatch.
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.
1class Node 2 def accept value 3 method_name = "visit_#{value.class}" 4 send method_name 5 end 6 7 def visit_Integer value 8 value * 2 9 end 10 11 def visit_String value 12 value.to_i * 2 13 end 14end
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.
Visitor pattern
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.
1class Node 2 def accept visitor 3 raise NotImpelementedError.new 4 end 5end 6 7module Visitable 8 def accept visitor 9 visitor.visit self 10 end 11end 12 13class IntegerNode < Node 14 include Visitable 15 16 attr_reader :value 17 def initialize value 18 @value = value 19 end 20end 21 22class Ast < Node 23 def initialize 24 @nodes = [] 25 @nodes << IntegerNode.new(2) 26 @nodes << IntegerNode.new(3) 27 end 28 29 def accept visitor 30 @nodes.each do |node| 31 node.accept visitor 32 end 33 end 34end 35 36class DoublerVisitor 37 def visit subject 38 puts subject.value * 2 39 end 40end 41 42class TriplerVisitor 43 def visit subject 44 puts subject.value * 3 45 end 46end 47 48ast = Ast.new 49puts "Doubler:" 50ast.accept DoublerVisitor.new 51puts "Tripler:" 52ast.accept TriplerVisitor.new 53 54# => 55Doubler: 564 576 58Tripler: 596 609
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.
1class Node 2 def accept visitor 3 raise NotImpelementedError.new 4 end 5end 6 7module Visitable 8 def accept visitor 9 visitor.visit(self) 10 end 11end 12 13class IntegerNode < Node 14 include Visitable 15 16 attr_reader :value 17 def initialize value 18 @value = value 19 end 20end 21 22class StringNode < Node 23 include Visitable 24 25 attr_reader :value 26 def initialize value 27 @value = value 28 end 29end 30 31class Ast < Node 32 def initialize 33 @nodes = [] 34 @nodes << IntegerNode.new(2) 35 @nodes << StringNode.new("3") 36 end 37 38 def accept visitor 39 @nodes.each do |node| 40 node.accept visitor 41 end 42 end 43end 44 45class BaseVisitor 46 def visit subject 47 method_name = "visit_#{subject.class}".intern 48 send(method_name, subject ) 49 end 50end 51 52class DoublerVisitor < BaseVisitor 53 def visit_IntegerNode subject 54 puts subject.value * 2 55 end 56 57 def visit_StringNode subject 58 puts subject.value.to_i * 2 59 end 60end 61 62class TriplerVisitor < BaseVisitor 63 def visit_IntegerNode subject 64 puts subject.value * 3 65 end 66 67 def visit_StringNode subject 68 puts subject.value.to_i * 3 69 end 70end 71 72ast = Ast.new 73puts "Doubler:" 74ast.accept DoublerVisitor.new 75puts "Tripler:" 76ast.accept TriplerVisitor.new 77 78# => 79Doubler: 804 816 82Tripler: 836 849
Real world usage
Arel uses visitor pattern to build query tailored to the specific database. You can see that it has a visitor class for sqlite3, mysql and Postgresql.