Visitor pattern

[Bernhard Brodowsky]

Hi,
I heard many times that the visitor pattern is useless in Ruby and
similar things.
However, I'm just writing an interpreter for a small imperative
language. I finished the parser and am just beginning to think about how
to implement the interpreter.
I just thought that it's a perfect place to use the visitor pattern, the
abstract syntax tree is the object structure to be "visited" and the
interpreter is a visitor.
This would have another advantage, namely that I can easily add more
visitors, like for example a pretty printer or something to compare ASTs
(useful for unit tests)
I could just add this functionality to the elements of the AST directly,
but somehow, I don't like this because I always have to search my ~30
classes that represent syntax units and implement one method in each of
them. Instead, it's much more comfortable to just write one new class.

What do you think about that? Is it really that bad to use the visitor
pattern in Ruby? And if yes, what is the reason for this?

 

[Caleb Clausen]

Hi,
I heard many times that the visitor pattern is useless in Ruby and
similar things.
However, I'm just writing an interpreter for a small imperative
language. I finished the parser and am just beginning to think about how
to implement the interpreter.
I just thought that it's a perfect place to use the visitor pattern, the
abstract syntax tree is the object structure to be "visited" and the
interpreter is a visitor.
This would have another advantage, namely that I can easily add more
visitors, like for example a pretty printer or something to compare ASTs
(useful for unit tests)
I could just add this functionality to the elements of the AST directly,
but somehow, I don't like this because I always have to search my ~30
classes that represent syntax units and implement one method in each of
them. Instead, it's much more comfortable to just write one new class.

What do you think about that? Is it really that bad to use the visitor
pattern in Ruby? And if yes, what is the reason for this?

Personally, I prefer to write 30 different SyntaxNode#visit methods
(or whatever you call them). But it's really a matter of taste.

If you create an actual visitor class (or method), I think you'll find
at the core of it a big ugly case statement. I like case statements
more than most people, but when they get bigger than a page, I get
nervous.

(The ideal solution would be to have a set of pattern-matching rules
and actions to be taken when those patterns are found in the tree. The
patterns would be more complicated than simply node classes; they
could depend on properties of the nodes. This starts to look a lot
like haskell or maybe antlr. I've tried hard to get this to work in
ruby, and successfully done the pattern-matching part but getting
actions to work as well turned out to be surprisingly difficult.
AFAIK, no one else has done any better.)

 

[Bernhard Brodowsky]

Personally, I prefer to write 30 different SyntaxNode#visit methods
(or whatever you call them). But it's really a matter of taste.

If you create an actual visitor class (or method), I think you'll find
at the core of it a big ugly case statement. I like case statements
more than most people, but when they get bigger than a page, I get
nervous.

Ok, of course, this would be quite terrible, but I think you can do it
better. You just implement the accept methods slightly different. The
accept method in Plus calls the method visit_plus on the visitor, the
accept method in Or calls the method visit_or on the visitor and so one.
Like that you can get around case statements, I think. You just have to
write many methods in the visitor.

But right now I think, I still won't use the visitor pattern since the
visitor pattern is good to add new operations, but bad to add new
elements. And while I'll only add few operations like pretty printing or
something similar, I think I will introduce many new elements.

(The ideal solution would be to have a set of pattern-matching rules
and actions to be taken when those patterns are found in the tree. The
patterns would be more complicated than simply node classes; they
could depend on properties of the nodes. This starts to look a lot
like haskell or maybe antlr. I've tried hard to get this to work in
ruby, and successfully done the pattern-matching part but getting
actions to work as well turned out to be surprisingly difficult.
AFAIK, no one else has done any better.)

Ok, it seems you have a lot of experience with real interpreters. Of
course, it would be cool to do something like Haskell, but I think for
my purposes, the model with the different node classes is sufficient.
It's only my first interpreter for a very small language.
But isn't this pretty orthogonal, anyway? I mean, you could just use
some additional conditionals in the node classes as well as in the
visitor to implement this, or do I misunderstand this?

 

[David Masover]

Hi,
I heard many times that the visitor pattern is useless in Ruby and
similar things.

At a glance, it seems to me that the visitor pattern is born directly out of
two things: A staticly-typed language, and the lack of proper closures.

This would have another advantage, namely that I can easily add more
visitors, like for example a pretty printer or something to compare ASTs
(useful for unit tests)
I could just add this functionality to the elements of the AST directly,
but somehow, I don't like this because I always have to search my ~30
classes that represent syntax units and implement one method in each of
them. Instead, it's much more comfortable to just write one new class.

Well, it seems like a lot of this would be re-usable, hopefully through
inheritance. In fact, if your unit tests are just comparing whether two ASTs
are identical, I bet you can figure out a completely generic way to do that,
as a single method on your base class.

And yes, it's going to be a ginormous case statement anyway. I'd much rather
use polymorphism than case statements any day.

What do you think about that? Is it really that bad to use the visitor
pattern in Ruby? And if yes, what is the reason for this?

I suspect it's bad in the same way that this is bad:

i = 0
while i < array.length
puts array
i += 1
end

That is, I bet it'd work fine, and there may well be some cases where it makes
sense -- for instance, sometimes you really do need an index that you can
arbitrarily manipulate (that is, sometimes even each_with_index isn't good
enough) -- but it just seems like a weird approach, and not very idiomatic.

In particular, I assume your "visitor" would be examining the type (class) of
each object? In anything other than a pretty-printer, aside from being a big
nasty case statement, it's also the opposite of duck-typing.

I could be wrong. I think Ruby's enumerables are better than Java's iterators
most of the time, but Ruby's enumerators are basically Java's iterators, and
they are sometimes ridiculously useful.

 

[Brian Candler]

And yes, it's going to be a ginormous case statement anyway. I'd much
rather
use polymorphism than case statements any day.

The problem then is that you're mixing the data structure with the
actions you want to perform using it, like mixing a model with a
controller.

I'm finding myself more attracted to having data structures entirely
separate from functions which act on that data, because you never have
to reconcile this dichotomy.

e.g. in Erlang you could just write:

-module(visit).
-export([eval/1]).

eval({badd, S1, S2}) ->
eval(S1) + eval(S2);
eval({bmul, S1, S2}) ->
eval(S1) * eval(S2);
eval({int, V}) ->
V.


Eshell V5.6.5 (abort with ^G)
1> c(visit).
{ok,visit}
2> %% Tree for 2 + 3 * 4
2> Tree = { badd, {int, 2}, { bmul, {int, 3}, {int, 4} } }.
{badd,{int,2},{bmul,{int,3},{int,4}}}
3> visit:eval(Tree).
14

Essentially you still have the big fat case statement, but it's written
as a function with pattern-matched entry points. All the logic for
evaluating the tree is in one place.

For someone used to Ruby, Erlang syntax is still annoying though :-(

 

[Kaspar Schiess]

And yes, it's going to be a ginormous case statement anyway. I'd much rather

use polymorphism than case statements any day.

I am experimenting with these topics in Ruby as well. I have a pattern
matcher on the trees that are output from my parser[1], but I find that
to be the wrong place to put the kind of thing in that would normally be
in a visitor.

I currently use that pattern matcher to construct a more stable AST, and
then I am using the visitor pattern for the very much unfinished second
part of that project[2]. The case statement is easily avoided by doing
dynamic dispatch based on the (class) name of the node. The way I see it
(currently) is that the node class is responsible for data manipulation
(identifier lookups, etc...) and the visitor acts on the data.

Dynamic dispatch mentioned above would look something like this:

def accept(visitor)
visitor.send( "visit_#{class.name.underscore}", self )
end

The big advantage of visitors in compiler/interpreter construction is
IMHO that the code relating to one topic is bundled in a single class.
Very often that code will relate to one level of abstraction. Having it
together is just neat.

Note that the dynamic dispatch (one of) the disadvantage of the visitor
pattern go away, namely that it is hard to add more nodes.

But maybe pattern matching would still be right on the level of the
constructed AST? I will have to consider that idea strongly.

(Maybe one of you wants to comment on the code at [1]?)

cheers,
kaspar

[1] http://github.com/kschiess/parslet
[2] http://github.com/kschiess/rooc