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

class IntegerNode
  def initialize(value)
    @value = value
  end

  def double
    @value * 2
  end
end

class Ast
  def initialize
    @nodes = []
    @nodes << IntegerNode.new(2)
    @nodes << IntegerNode.new(3)
  end

  def print_double
    @nodes.each do |node|
      puts node.double
    end
  end
end

ast = Ast.new
ast.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.

node.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.

class Node
   def double(Integer value); value *2; end
   def double(String value); Integer.parseInt(value) * 2; end
end

node.double(2)
node.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.

class Node
  def accept value
   method_name = "visit_#{value.class}"
   send method_name
  end

  def visit_Integer value
   value * 2
  end

  def visit_String value
    value.to_i * 2
  end
end

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.

class Node
  def accept visitor
    raise NotImpelementedError.new
  end
end

module Visitable
  def accept visitor
    visitor.visit self
  end
end

class IntegerNode < Node
  include Visitable

  attr_reader :value
  def initialize value
    @value = value
  end
end

class Ast < Node
  def initialize
    @nodes = []
    @nodes << IntegerNode.new(2)
    @nodes << IntegerNode.new(3)
  end

  def accept visitor
    @nodes.each do |node|
      node.accept visitor
    end
  end
end

class DoublerVisitor
  def visit subject
    puts subject.value * 2
  end
end

class TriplerVisitor
  def visit subject
    puts subject.value * 3
  end
end

ast = Ast.new
puts "Doubler:"
ast.accept DoublerVisitor.new
puts "Tripler:"
ast.accept TriplerVisitor.new

# =>
Doubler:
4
6
Tripler:
6
9

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.

class Node
  def accept visitor
    raise NotImpelementedError.new
  end
end

module Visitable
  def accept visitor
    visitor.visit(self)
  end
end

class IntegerNode < Node
  include Visitable

  attr_reader :value
  def initialize value
    @value = value
  end
end

class StringNode < Node
  include Visitable

  attr_reader :value
  def initialize value
    @value = value
  end
end

class Ast < Node
  def initialize
    @nodes = []
    @nodes << IntegerNode.new(2)
    @nodes << StringNode.new("3")
  end

  def accept visitor
    @nodes.each do |node|
      node.accept visitor
    end
  end
end

class BaseVisitor
  def visit subject
    method_name = "visit_#{subject.class}".intern
    send(method_name, subject )
  end
end

class DoublerVisitor < BaseVisitor
  def visit_IntegerNode subject
    puts subject.value * 2
  end

  def visit_StringNode subject
    puts subject.value.to_i * 2
  end
end

class TriplerVisitor < BaseVisitor
  def visit_IntegerNode subject
    puts subject.value * 3
  end

  def visit_StringNode subject
    puts subject.value.to_i * 3
  end
end

ast = Ast.new
puts "Doubler:"
ast.accept DoublerVisitor.new
puts "Tripler:"
ast.accept TriplerVisitor.new

# =>
Doubler:
4
6
Tripler:
6
9

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.