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

Subject: Re: [proto] Visitor Design Pattern
From: Thomas Heller (thom.heller_at_[hidden])
Date: 2010-10-22 02:26:10

On Friday 22 October 2010 04:09:52 Joel de Guzman wrote:
> On 10/22/2010 10:01 AM, Eric Niebler wrote:
> >> 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.
> > 
> > You're not the first to bring up vW-grammars in relation to Proto.
> > Someone suggested them to implement EDSL type systems. I spent a good
> > amount of time reading about them, and could get my head around it. My
> > understanding is that they're powerfully descriptive, but that building
> > compilers with vW-grammars is very expensive. I don't really know. I
> > think I'd need to work with a domain expert to make that happen. Any
> > volunteers? :-)
> 
> Heh, people make it look needlessly complicated than it really is :-)
> Check out the doc I sent (Annex A). It's really, to my mind,
> generic languages -- abstraction of rules and templated grammars
> through metanotions and hyper-rules. I have this strong feeling that
> that's the intent of Thomas and your recent designs. Essentially,
> making the phoenix language a metanotion in itself that can be
> extended post-hoc through generic means.

Hmm. I don't understand these level-2 grammars either.
Heck, I am not even sure where the "parsing" part happens inside the 
expression template engine.
Thus I can not say if this really was my intent ;)

I was more trying to focus on how the language once parsed (whatever that 
means) into some kind of AST can be processed.

I think we agree upon how the AST of a proto expression looks like. 
Additionally, it is clear how to check the AST for validity.
What is left to determine is a general meaning of how to traverse this AST.
I think the notion of Semantic Actions (SA) is ill formed here as well. 
Since SAs are used during the parsing process. IMHO, this process is over 
once we retrieved the full AST.
To put it into the context of phoenix:
We have
template <typename Expr> struct actor { operator()(...) { ... return 
eval(*this, ...); } };

inside operator() we have the AST which is represented as a type with 
actor<Expr> and the *this object. By calling eval, we traverse the AST to 
evaluate it with one specific behavior (some notion of C++ behavior).

In traditional compilers this is done with the Visitor Pattern.
This last part is IMHO currently missing (not entirely) in proto. In proto, 
you define what happens if some rule matched, which of course more of a 
semantic action than a visitor.

My intention is to traverse the proto tree multiple times and apply various 
cool transformations to it, which ultimately lead to evaluation.
IMHO, this traversal can be best expressed in terms of the Visitor Pattern.
I understand however, that it is hard to get the right formal description 
for it for proto. This might have several reasons. One of which i can think 
of is that proto grammars are used as two kind of things: 
  1) Description of how the language looks like, i.e. what a valid 
expression is
  2) As the definition of a "dynamic" node type we would like to "visit" (to 
stay in the OOP parlance)