Visitor Pattern in Ruby

[Charles Comstock]

I recently wrote a small compiler in java in which we used the visitor
design pattern to walk an abstract syntax tree hiearchy. I was most
impressed with the ease with which a reflective visitor allowed me to
walk the tree. So recently having some free time I set about to
implement a similar visitor pattern for Ruby, which could easily be
dropped in as a module. I believe the code below does this in a
reasonably elegant fasion. I have examples of it's use posted at the
bottom of http://www.rubygarden.org/ruby?VisitorPattern I thought it
an interesting solution for implementing double-dispatch, while still
providing alot of power and flexability. I was curious considering
the existing design patterns in the ruby library (Observer, Singleton,
etc.) if there was any interest in including this design pattern as well?

Whether or not there is interest, I was curious what, if any thread
safety or exception handling anyone would suggest in this code, or if
it should simply be handled by visitor code that uses this library.
Thanks,
Charles Comstock

#file visitor.rb
module Visitable
def accept(visitor,&block)
for klass in self.class.ancestors do
break if (v = visitor.methods.include?("visit_#{klass}"))
end
if v
visitor.__send__("visit_#{klass}",self,&block)
else
visitor.default_visit(self,&block)
end
end
def Visitable.included(kls)
kls.module_eval <<-"end_eval"
def self.inherited(child)
child.module_eval "include Visitable"
end
end_eval
end
end

 

[Robert Klemme]

I recently wrote a small compiler in java in which we used the visitor
design pattern to walk an abstract syntax tree hiearchy. I was most
impressed with the ease with which a reflective visitor allowed me to
walk the tree. So recently having some free time I set about to
implement a similar visitor pattern for Ruby, which could easily be
dropped in as a module. I believe the code below does this in a
reasonably elegant fasion. I have examples of it's use posted at the
bottom of http://www.rubygarden.org/ruby?VisitorPattern I thought it
an interesting solution for implementing double-dispatch, while still
providing alot of power and flexability. I was curious considering
the existing design patterns in the ruby library (Observer, Singleton,
etc.) if there was any interest in including this design pattern as well?

Whether or not there is interest, I was curious what, if any thread
safety or exception handling anyone would suggest in this code, or if
it should simply be handled by visitor code that uses this library.

Yes, I'd leave thread safety completely out of this. You can't do it
properly here and most code that uses it won't need it.

The only problem I can see at the moment is with classes that are not in the
global scope:
=> "Foo::Bar"

This string is likely to make problems in a method name:
NameError: undefined local variable or method `visit_Foo' for X:Class
from (irb):5


Maybe you just map "::" to "_" or something similar.

An alternative approach could be to use the visitor to get a proc for the
current instance, like in

class Visitor
def visit(obj)
bl = nil

obj.class.ancestors.each do |cl|
bl ||= visitors[cl] # hash lookup
end

bl.call( obj ) if bl
end
end


Kind regards

robert

 

[Charles Comstock]

On Wed, 26 May 2004, Robert Klemme wrote:

[cut]

The only problem I can see at the moment is with classes that are not in the
global scope:

=> "Foo::Bar"

This string is likely to make problems in a method name:

NameError: undefined local variable or method `visit_Foo' for X:Class
from (irb):5


Maybe you just map "::" to "_" or something similar.

Shoot I completely forgot about that problem. Hmm that causes all
sorts of problems. I can't simply do a gsub(/::/,'_') because then
what would happen if you wrote:

class A::B
end

and

class A_B
end

They would be indistinguishable. I suppose you could just take that
into account and do something like split(/::/)[-1] and just assume you
don't have a naming collision. I would think that generally you would
be only interested in the class of the most immediate scope, but it
certainly allows for some ambiguity.

Speaking of which what is up with this:
irb(main):115:0> "a::b::c".intern
=> :"a::b::c"

Is that syntax documented?

An alternative approach could be to use the visitor to get a proc for the
current instance, like in

class Visitor
def visit(obj)
bl = nil

obj.class.ancestors.each do |cl|
bl ||= visitors[cl] # hash lookup
end

bl.call( obj ) if bl
end
end

Something like that would certainly work it just doesn't seem as nice a way to
define each visitor. Hmm I shall have to think on this.

Charlie

 

[Robert Klemme]

On Wed, 26 May 2004, Robert Klemme wrote:

[cut]

The only problem I can see at the moment is with classes that are not in the
global scope:

=> "Foo::Bar"

This string is likely to make problems in a method name:

NameError: undefined local variable or method `visit_Foo' for X:Class
from (irb):5


Maybe you just map "::" to "_" or something similar.

Shoot I completely forgot about that problem. Hmm that causes all
sorts of problems. I can't simply do a gsub(/::/,'_') because then
what would happen if you wrote:

class A::B
end

and

class A_B
end

They would be indistinguishable. I suppose you could just take that
into account and do something like split(/::/)[-1] and just assume you
don't have a naming collision. I would think that generally you would
be only interested in the class of the most immediate scope, but it
certainly allows for some ambiguity.

Speaking of which what is up with this:
irb(main):115:0> "a::b::c".intern
=> :"a::b::c"

Is that syntax documented?

That might work in your case. Hm...

An alternative approach could be to use the visitor to get a proc for the
current instance, like in

class Visitor
def visit(obj)
bl = nil

obj.class.ancestors.each do |cl|
bl ||= visitors[cl] # hash lookup
end

bl.call( obj ) if bl
end
end

Something like that would certainly work it just doesn't seem as nice a way to
define each visitor. Hmm I shall have to think on this.

Personally I'd prefer the mapping approach - it seems to be more OO to me.
But then, a maybe a more general approach would be in order:

#!/usr/bin/ruby

class MultipleDispatchMethod
def initialize(arity)
raise ArgumentError, "type count must be > 0" unless arity > 0

@arity = arity
@procs = {}
end

def arity; @arity; end

def define_dispatch(*types, &method)
raise ArgumentError, "Wrong number of types" unless types.size ==
arity

# allow for prototype based definition
types.map! {|tp| cl = tp.class; cl == Class || cl == Module ? tp : cl}

@procs[ types ] = method
end

def call(*args)
types = args.slice( 0, arity ).map{|c| c.class}
@procs[ types ].call( args )
end
end


# define method FooBar
FooBar = MultipleDispatchMethod.new( 2 )

FooBar.define_dispatch( String, Fixnum ) do |s,n,str|
( s + str ) * n
end

FooBar.define_dispatch( "hello", 5.3 ) do |s,f,str|
FooBar.call( s, f.to_i, str )
end

p FooBar.call( "a", 10, "b" )
p FooBar.call( "a", 10.45, "b" )

Of course the lookup could be made much smarter, so it tries super class
coombinations as well. But that would be far more costly, which is maybe
not such a good idea for a method call.

Kind regards

robert

 

[Charles Comstock]

On Wed, 26 May 2004, Robert Klemme wrote:

[cut]

The only problem I can see at the moment is with classes that are not in the
global scope:

module Foo; class Bar; end; end
=> nil
Foo::Bar
=> Foo::Bar
Foo::Bar.to_s
=> "Foo::Bar"

This string is likely to make problems in a method name:

class X
def visit_Foo::Bar
end
end
NameError: undefined local variable or method `visit_Foo' for X:Class
from (irb):5


Maybe you just map "::" to "_" or something similar.

Shoot I completely forgot about that problem. Hmm that causes all
sorts of problems. I can't simply do a gsub(/::/,'_') because then
what would happen if you wrote:

class A::B
end

and

class A_B
end

They would be indistinguishable. I suppose you could just take that
into account and do something like split(/::/)[-1] and just assume you
don't have a naming collision. I would think that generally you would
be only interested in the class of the most immediate scope, but it
certainly allows for some ambiguity.

Speaking of which what is up with this:
irb(main):115:0> "a::b::c".intern
=> :"a::b::c"

Is that syntax documented?

That might work in your case. Hm...

An alternative approach could be to use the visitor to get a proc for the
current instance, like in

class Visitor
def visit(obj)
bl = nil

obj.class.ancestors.each do |cl|
bl ||= visitors[cl] # hash lookup
end

bl.call( obj ) if bl
end
end

Something like that would certainly work it just doesn't seem as nice a way to
define each visitor. Hmm I shall have to think on this.

Personally I'd prefer the mapping approach - it seems to be more OO to me.
But then, a maybe a more general approach would be in order:

#!/usr/bin/ruby

class MultipleDispatchMethod
def initialize(arity)
raise ArgumentError, "type count must be > 0" unless arity > 0

@arity = arity
@procs = {}
end

def arity; @arity; end

def define_dispatch(*types, &method)
raise ArgumentError, "Wrong number of types" unless types.size ==
arity

# allow for prototype based definition
types.map! {|tp| cl = tp.class; cl == Class || cl == Module ? tp : cl}

@procs[ types ] = method
end

def call(*args)
types = args.slice( 0, arity ).map{|c| c.class}
@procs[ types ].call( args )
end
end


# define method FooBar
FooBar = MultipleDispatchMethod.new( 2 )

FooBar.define_dispatch( String, Fixnum ) do |s,n,str|
( s + str ) * n
end

FooBar.define_dispatch( "hello", 5.3 ) do |s,f,str|
FooBar.call( s, f.to_i, str )
end

p FooBar.call( "a", 10, "b" )
p FooBar.call( "a", 10.45, "b" )

Of course the lookup could be made much smarter, so it tries super class
coombinations as well. But that would be far more costly, which is maybe
not such a good idea for a method call.

If you don't check the superclass then the usefulness of the visitor pattern
drops significantly. The whole idea is to be able to walk a hiearchy and catch
different classes at different levels. I'm not trying to do multiple dispatch,
just double dispatch, so I only really need to walk the type hiearchy in one
dimension. That's not great for efficiency, but it's not horrible either.

The main problem with the proc based solution is I no longer can leverage
inheritance on the visitor side, only on the visitee side. In other words I
can't create a skeleton of a visitor and derive from it to add specific
functionality, unless I implement my own system of inheritence of the procs.
Which is slow and bad, and not really a solution.

While I can understand it wouldn't work effectively for cases where you were
walking one hiearchy that was inside a module and one that was outside with
similar names, I think the solution I presented works fine for 90% of the use
cases.

Charlie

 

[Robert Klemme]

If you don't check the superclass then the usefulness of the visitor pattern
drops significantly. The whole idea is to be able to walk a hiearchy and catch
different classes at different levels. I'm not trying to do multiple dispatch,
just double dispatch, so I only really need to walk the type hiearchy in one
dimension. That's not great for efficiency, but it's not horrible either.

Completely true.

The main problem with the proc based solution is I no longer can leverage
inheritance on the visitor side, only on the visitee side. In other words I
can't create a skeleton of a visitor and derive from it to add specific
functionality, unless I implement my own system of inheritence of the procs.
Which is slow and bad, and not really a solution.

Well, you could change it from an implicit block argument to an explicit
method argument and then you can throw in anything that implements call().

While I can understand it wouldn't work effectively for cases where you were
walking one hiearchy that was inside a module and one that was outside with
similar names, I think the solution I presented works fine for 90% of the use
cases.

Well, my code wasn't meant to be a replacement for yours. I just wanted to
see how a quick hack of MD could look like. I'm aware that these are
different pairs of shoes with differnt requirements. Although, from an
abstract perspective Visitor is a special case of Double Dispatch which in
turn is a special case of Multiple Dispatch.

Visitor has its merits but nevertheless I don't like it very much. On one
hand you retrofit functionality to a class hierarchy but on the other hand
you need this class hierarchy's collaboration to make it happen if you use
visitor. I find this a bit too intertwined. I prefer the "hash lookup with
class" approach. If you do that inside the visitor, you don't need the
visitee to call any visit_<klass> methods and your visitor code is
completely independend from the class hierarchy you want to visit. It seems
to me to be a better separation of concerns.

If you view it as a way of adding methods to a class, then it's clear that
you will need it more seldom in Ruby than in compiled languages, because you
can dynamically add methods by either defining new methods in a class,
defining singleton methods or including modules.

Another interesting article on the matter:
http://www-106.ibm.com/developerworks/java/library/j-diag0115.html

You can find a lot other interesting stuff about the matter here:
http://www.google.com/search?q="visitor+pattern"+site:ibm.com

Thanks for the nice and interesting discussion!

Kind regards

robert

 

[Charles Comstock]

Well, my code wasn't meant to be a replacement for yours. I just wanted to
see how a quick hack of MD could look like. I'm aware that these are
different pairs of shoes with differnt requirements. Although, from an
abstract perspective Visitor is a special case of Double Dispatch which in
turn is a special case of Multiple Dispatch.

Visitor has its merits but nevertheless I don't like it very much. On one
hand you retrofit functionality to a class hierarchy but on the other hand
you need this class hierarchy's collaboration to make it happen if you use
visitor. I find this a bit too intertwined. I prefer the "hash lookup with
class" approach. If you do that inside the visitor, you don't need the
visitee to call any visit_<klass> methods and your visitor code is
completely independend from the class hierarchy you want to visit. It seems
to me to be a better separation of concerns.

It was designed as far as I can tell for use with compilers, that is where it
mostly frequently appears. In that case I think it does a very good job as you
have a number of passes you need to perform across your AST which hopefully is
well structured into a nice class hiearchy. That way you can generate code for
a AddOp, a BinaryComputeIsh, or some such hiearchy like that, catching what you
need where. An AST is something that is well suited to a very deep class
hiearchy and so the Visitor excels at processing it. As for other applications,
I'm not sure if it's as effective there.

If you view it as a way of adding methods to a class, then it's clear that
you will need it more seldom in Ruby than in compiled languages, because you
can dynamically add methods by either defining new methods in a class,
defining singleton methods or including modules.

Right, I'm aware of that. Actually it is interesting that C# has something akin
to open class definitions to facilitate generated code. I haven't checked to
see if all file need to be present for the compile phase or if it can add
additional functionality later, would be interesting to see.

However when you can do that alot of the code winds up looking more like chain
of responsability then Visitor. Oh well I guess a number of the patterns are
all dependent on how you view them.

Thanks for the nice and interesting discussion!

No no, thank you

Charles Comstock

 

[Robert Klemme]

It was designed as far as I can tell for use with compilers, that is where it
mostly frequently appears. In that case I think it does a very good job as you
have a number of passes you need to perform across your AST which hopefully is
well structured into a nice class hiearchy. That way you can generate code for
a AddOp, a BinaryComputeIsh, or some such hiearchy like that, catching what you
need where. An AST is something that is well suited to a very deep class
hiearchy and so the Visitor excels at processing it. As for other applications,
I'm not sure if it's as effective there.

And, as a programming language is usually quite fixed and does not change
often, visitor's problems with changing class hierarchies don't show up
here. Plus if there are only relatively few passes, then there is not much
to change if the AST class hierarchy gets extended.

Right, I'm aware of that. Actually it is interesting that C# has something akin
to open class definitions to facilitate generated code. I haven't checked to
see if all file need to be present for the compile phase or if it can add
additional functionality later, would be interesting to see.

If you learn anything further about this C# feature, please let us know. We
just have to make sure there is something we can learn for Ruby in order to
not get too far off topic.

However when you can do that alot of the code winds up looking more like chain
of responsability then Visitor. Oh well I guess a number of the patterns are
all dependent on how you view them.

This happens to me all the time: a lot of those patterns look quite similar.
I guess that's because they use the same principles underneath. The most
important point seems to be to me, how tasks are delegated from one object
to other objects. But it's always about delegation. Interestingly enough,
things don't get easier for us when we look at them from such a broad
perspective. With some simple basic priciples very complex systems can be
built...

No no, thank you

You're welcome. We got to keep the NG attractive, to pull more and more
people over from ruby-talk.

Regards

robert

 

[Christoph]

module Visitable
def accept(visitor,&block)
for klass in self.class.ancestors do
break if (v = visitor.methods.include?("visit_#{klass}"))
end
if v
visitor.__send__("visit_#{klass}",self,&block)
else
visitor.default_visit(self,&block)
end
end

The following "included" redefinition is superfluous since any
child of a "Visitable" class is already "Visitable" - for example

---
module Visitable
def accept(visitor,&block)
for klass in self.class.ancestors do
break if (v = visitor.methods.include?("visit_#{klass}"))
end
if v
visitor.__send__("visit_#{klass}",self,&block)
else
visitor.default_visit(self,&block)
end
end
end

class A
include Visitable
end

class B < A
end

p A < Visitable # true
p B < Visitable # true
---

def Visitable.included(kls)
kls.module_eval <<-"end_eval"
def self.inherited(child)
child.module_eval "include Visitable"
end
end_eval
end
end

/Christoph

 

[Alan Chen]

It was designed as far as I can tell for use with compilers, that is where it
mostly frequently appears. In that case I think it does a very good job as you
have a number of passes you need to perform across your AST which hopefully is
well structured into a nice class hiearchy. That way you can generate code for
a AddOp, a BinaryComputeIsh, or some such hiearchy like that, catching what you
need where. An AST is something that is well suited to a very deep class
hiearchy and so the Visitor excels at processing it. As for other applications,
I'm not sure if it's as effective there.

Another place I've seen it used effectively is scene graph traversal.
The OpenSceneGraph project (http://www.openscenegraph.org) has a nice
C++ implementation for their purposes.

 

[Charles Comstock]

The following "included" redefinition is superfluous since any
child of a "Visitable" class is already "Visitable" - for example

---
module Visitable
def accept(visitor,&block)
for klass in self.class.ancestors do
break if (v = visitor.methods.include?("visit_#{klass}"))
end
if v
visitor.__send__("visit_#{klass}",self,&block)
else
visitor.default_visit(self,&block)
end
end
end

class A
include Visitable
end

class B < A
end

p A < Visitable # true
p B < Visitable # true

Your probably correct, originally the way I had to do it required a module eval
for the whole thing and so I needed that to force it to propegate down the
inheritance chain.

Charlie