Proto for Boost mailing list page: Re: [proto] So I heard proto make AST ...

Subject: Re: [proto] So I heard proto make AST ...
From: joel falcou (joel.falcou_at_[hidden])
Date: 2010-08-10 02:47:56

On 10/08/10 05:24, Gordon Woodhull wrote:
> Sorry for the slow response - been on vacation offline.
No problem ;)
> I wonder if Dan Marsden's Traversal library would solve this out of 
> the box? 
> http://boost-spirit.com/dl_docs/traversal/html/traversal/introduction.html 
>
Oh nice link, I didn't knew that :o
> The way I would solve it is to create an adapter that makes a Proto 
> tree look like a graph...  Like Boost.Graph, Metagraph is designed to 
> allow adapting any metadata that is already graphlike to have a graph 
> API.  (This wasn't the right approach for MSM because there's nothing 
> in those tables that immediately answers "what are the edges for this 
> vertex?")
>
> If there is interest, I could probably pull this together pretty 
> quickly, as Proto already has such an expressive API.  Then we'd 
> immediately have inefficient implementations of DFS & BFS and I could 
> see if there's a good way to factor out the color map stuff to make it 
> speedy.
We're looking at two challenge in Proto :
-> traversing the AST type at compile-time to apply meta-function onto 
tree node
-> traversing the AST value at run-time to apply function onto tree node

> The main API debate when it comes to traversals is "visitors or 
> iterators?"  Currently metagraph takes the visitor approach from 
> Boost.Graph, which are more general and expressive, but iterators are 
> often more convenient.  Any opinions here?  AFAIK we don't have 
> coroutines or continuations in C++ metaprogramming to make the 
> inversion of control easier.  ;-)
I can't say much but, for example here is my current use-cases:

- walkign through a proto AST to apply a visitor onto node/leaf : turn 
the AST on array into the same AST with pointer element before evaluation
- turning the AST into a DAG
- applying a visitor performing osme kind of reduction on the tree 
startign form the leaf to evaluate the value of the AST in a given point 
of evaluation
- for a given assign node (lhs = rhs) check if the lhs data address is 
somewhere in the terminal of rhs. This is basically our trickiest 
runtime algorithm in nt2 that helps us detetcing alias in expression 
without having ppl using alias(x) function.
- detecting pattern in the AST (like a+b*c) and repalce all of them, 
recurisvely into another (here by madd(a,b,c)). It's currently done with 
special grammar and it's maybe better to do it like this but we never know.

I'm from the old guard w/r to tree, so I'm mostly thinking in visitor. 
But if you care to show me how iterators can be used, I'm open to 
suggestion.