Proto for Boost mailing list page: Re: [proto] Visitor Design Pattern

Subject: Re: [proto] Visitor Design Pattern
From: Joel de Guzman (joel_at_[hidden])
Date: 2010-10-21 21:41:14

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:

  http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf

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.

Regards,
-- 
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net