Proto for Boost mailing list page: [proto] Visitor Design Pattern (was: Thoughts on traversing proto expressions and reusing grammar)

Subject: [proto] Visitor Design Pattern (was: Thoughts on traversing proto expressions and reusing grammar)
From: Eric Niebler (eric_at_[hidden])
Date: 2010-10-21 13:59:32

I spent some time last night thinking about the visitor design pattern
and how it relates to Thomas' code.

The visitor is characterized by two things:

- Externally adding behaviors to a hierarchy by parameterizing
operations with an object that encapsulates the desired new behavior,
called the visitor.
- Dispatching twice: once on the object in the hierarchy, and again on
the type of the visitor.

In the classic visitor pattern, we're talking about an OO hierarchy with
two abstract bases: Element and Visitor. Element has a virtual Accept
member that takes a Visitor&. Visitor has many virtual Visit overloads
that accept specific Element subclasses. The "first dispatch" is based
on the dynamic type of the Element object. The second dispatch is based
on the dynamic type of the Visitor object (and the now-known static type
of the Element subclass).

In Thomas' and my openly extensible Proto algorithm framework, we also
externally add behaviors. The behaviors are encapsulated in a type which
is a collection of Proto transforms, which I've called Actions. The way
it works is this: A Proto grammar is made up of rules. An expression
matches a rule, the rule is used to index into the Actions, the right
transform is found and applied.

So my question is: what in this model corresponds to "Element" and what
to "Visitor"? What corresponds to the first dispatch, and what
corresponds to the second. Here's what I think:

1) "Element" is the Proto expression type(?).

1a) The "Element" hierarchy is ???

2) "The first dispatch" is to find the rule in a grammar that the
expression matches.

3) "The dynamic type of Element" is the rule that the expression matches.

4) "Visitor" the collection of Proto transforms.

4a) The "Visitor" hierarchy is ???

5) "The second dispatch" is to look up the right transform in the
collection with the rule.

5) "The dynamic type of Visitor" is the found transform.

Thoughts? Some of these are rather tenuous, like (3). I guess it's
/possible/ that a rule is the meta-dynamic-type of an expression. But
this is not a connection that folks are likely to make themselves, nor
is it particularly enlightening. It's more natural to think of a rule as
a schema that describes a set of valid expressions. If an XML document
is a "variable", is the XML schema its "type"? I don't know. And I'm
having a terrible time wrapping my head around the notion of
meta-super-/sub-classes and what that could mean (see (1a) and (4a)).
Nowhere are we sub-typing an expression or a grammar, but I could be
thinking at the wrong meta level. This is hard.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com