Thanks Joel,

This is food for thought!

On Aug 10, 2010, at 2:47 AM, joel falcou wrote:
On 10/08/10 05:24, Gordon Woodhull wrote:

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

I just committed an example which does this part.  See end of message.

-> traversing the AST value at run-time to apply function onto tree node

This requires a Fusion/BGL interface, which I haven't thought out yet. Probably just means moving a parameter from the <> to () as usual. :-D

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

Yes, I imagine that's the most common use case. How hard can that Fusion/BGL interface be?

- turning the AST into a DAG

Yay!

Stjepan Rajko and I talked about doing this in order to allow Proto expressions to define graph metadata.

Maybe you'd kind of cut and paste the Proto tree into an mpl graph while looking for vertices with duplicate IDs. Should work just as well on graphs with cycles.

This way you'd end up with sort of a graph metadata overlay over the Proto tree. Each vertex would contain metadata instructions for how to get to the corresponding Proto node in the expression, and each edge would be vertex+child#. No extra runtime data needed, if I'm not mistaken.

You could also imagine doing this with a Fusion graph somehow, if you wanted to add runtime data... but I don't grok the Fusion/Proto allocation/reference magic yet, so I'm not quite sure what I'm saying.

- 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

Postorder traversal? I guess the trick is in what you produce: annotating the existing nodes, easy, vs building something new, maybe not so.

- 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.

Again, DFS with a Fusion/BGL interface.

- 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.

Haha, I haven't thought about graph pattern matching for a while, though that's where I started with graphs 15 years ago.

Special-purpose Proto grammars/transforms are probably the best way to modify Proto expressions, but like you say, we never know. Maybe something cool could be done with graph transformations of fusionish graph data.

Let me see if I am starting to understand the Proto/Fusion memory model. You end up with the original expression as one object, and then a bunch of new AST nodes holding references into the original expression, right?

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.

Cool.  Visitors are way more powerful.

If you go with iterators you end up creating different iterator types for every kind of traversal. But then they don't muck with your control flow. Here is a good message describing that approach, from one of the boost::tree discussions. (There have been a few valiant attempts.)
http://lists.boost.org/Archives/boost/2005/03/83203.php


So, here's how far I got tonight: there's
sandbox/metagraph/libs/metagraph/example/proto_adaptor.cpp
which does compile-time traversal of the Proto expression _1*12/_2, printing this nice error message showing that the preorder traversal worked (in reverse order):

proto_adaptor.cpp:132: error: No match for 'assertion_failed(
        mpl_::failed ************ boost::mpl::equal<
            boost::mpl::v_item<
boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_::term<placeholder<2> >, 0
l>
              , boost::mpl::v_item<
boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_::term<const int &>, 0
l>
                  , boost::mpl::v_item<
boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_::term<placeholder
<1> >, 0l>
                      , boost::mpl::v_item<
                            boost::proto::exprns_::expr<
                                boost::proto::tag::multiplies
                              , boost::proto::argsns_::list2<
const boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_
::term<placeholder<1> >, 0l> &
, boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_::term
<const int &>, 0l>
                                >, 2l
                            >, boost::mpl::v_item<
                                boost::proto::exprns_::expr<
                                    boost::proto::tag::divides
                                  , boost::proto::argsns_::list2<
const boost::proto::exprns_::expr< boost::proto::tag::multiplies , boost::proto::argsns_::list2< const boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::pr
oto::argsns_::term<placeholder<1> >, 0l> &
, boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::a
rgsns_::term<const int &>, 0l>
                                            >, 2l
> &, const boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto
::argsns_::term<placeholder<2> >, 0l> &
                                    >, 2l
                                >, boost::mpl::vector<mpl_::na>, 0
                            >, 0
                        >, 0
                    >, 0
                >, 0
>, void, boost::is_same<mpl_::arg<-0x00000000000000001>, mpl_::arg<-0x00000000000000001> >
        >::************
    )'


Cheers!
Gordon

_______________________________________________
proto mailing list
proto@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/proto

Reply via email to