On 10/22/2010 1:59 AM, Eric Niebler wrote:
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.

I like it when we are talking on a conceptual level :-). I think part
of the difficulty is in combining two domains: language/parsing and OOP.
As much as I do not have any problems with "visitation", it's also
intersecting with the notion of "semantic actions". If we add yet one
more set of parlance: schemas and documents (which is not totally
unrelated -- schemas are basically just grammars), I'm afraid we'll
add more confusion.

I'd say stick to only one domain's parlance. Since proto is closer to
the language/parsing domain, I think we should stick to (semantic)actions,
rules, grammars etc. If you want to go "meta" on parsing, then you might
get some inspiration on 2-level grammars (inspired by van Wijngaarden
grammars) with the notion of hyper-rules, etc. This document:


gives a better glimpse into 2-level grammars (see Annex A).

  "Although the notation (also known as a van Wijngaarden grammar,
  or a W-grammar) is more powerful, it is more complicated and,
  as the authors of Algol 68 recognized, “may be difficult
  for the uninitiated reader”.

I'm not really sure how this relates to the current design, but
I think we should be getting closer to this domain and it deserves
some notice.

Joel de Guzman

proto mailing list

Reply via email to