BigBinary Blog

We write about Ruby on Rails, React.js, React Native, remote work, open source, engineering and design.

Visitor pattern and double dispatch in ruby

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.

Neeraj Singh in Rails
July 7, 2013
Share

Subscribe to our newsletter