I'm on a tiny mobile, but my idéa was to have such algo as proto transforms & grammar
> On 8/10/2010 4:48 AM, Gordon Woodhull wrote: >> Thanks Joel, >> >> This is food for thought! > > Indeed, but I'm struggling to keep up because I don't really know what > you guys are after. > >> 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, > > There is! I think. What is the goal? To be able to apply graph > algorithms to Proto expressions? Why, exactly? Turning an expression > tree into a graph seems like a step backward to me. Trees are easier to > process than graphs, IIUC. Where have I gone astray? > >>>> 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 > > Above and beyond what you get by using Proto grammars+transforms? > >> I just committed an example which does this part. See end of message. > > Committed where? > >>> -> traversing the AST value at run-time to apply function onto tree >>> node > > Again, this is what Proto grammars+transforms are for. If they're not > doing the job, let's talk about why. > >> 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 > > IIUC, BGL has a homogeneous interface, like the STL. I don't think you > can get it to play well with Fusion, or Proto for that matter. > >>> 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? > > I can do this easily with a Proto grammar w/ transform. > >>> - turning the AST into a DAG >> >> Yay! > > Use case? > >> 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. > > I can speak to Proto's allocation/reference magic. There is no (dynamic) > allocation. By default, everything is held by reference, even > intermediate temporary expressions. The default can be changed and > things can be held by value. There's also a deep_copy function to turn > references into values. > > Proto is not built on top of Fusion. There is an adaptor layer, but it > doesn't fit too well at the moment; heterogeneous trees are hard until > Fusion gets complete segmented iteration support, and I'm not 100% > convinced that's the way forward (see iterators vs. visitors). > >>> - 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. > > Just as trees are a special case of graphs, tree algorithms are probably > a better fit for expression manipulation than graph algorithms. > >> 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? > > That's one possibility, but object lifetime can be an issue. > >>> 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. > > Even in STL-land, sequential iteration over tree-like things feels like > putting on shoes that are too small. The problem gets much worse once > you allow for heterogeneous trees. Even if all Fusion algorithms had > segmented variants, you'd *still* want additional algorithm that don't > force you to ignore the very tree structure that make trees interesting > and useful. > >> 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): > > A pre-order traversal, pushing each visited node into an mpl vector? How > about: > > #include <iostream> > #include <typeinfo> > #include <boost/proto/proto.hpp> > #include <boost/mpl/vector.hpp> > #include <boost/mpl/push_back.hpp> > #include <boost/mpl/for_each.hpp> > namespace proto = boost::proto; > namespace mpl = boost::mpl; > using proto::_; > > template<typename T> struct wrap {}; > > struct PreOrder > : proto::or_< > proto::when< > proto::terminal<_> > , mpl::push_back<proto::_state, wrap<_>()>() > > > , proto::otherwise< > proto::fold< > _ > , mpl::push_back<proto::_state, wrap<_>()>() > , PreOrder > > > > > > > {}; > > struct print_name > { > template<typename T> > void operator()(wrap<T> const &) const > { > std::cout << typeid(T).name() << "\n\n"; > } > }; > > template<typename Vector> > void static_print(Vector) > { > mpl::for_each<Vector>(print_name()); > } > > template<int I> struct placeholder {}; > proto::terminal< placeholder< 1 > >::type const _1 = {{}}; > proto::terminal< placeholder< 2 > >::type const _2 = {{}}; > > int main() > { > static_print( PreOrder()(_1*12/_2, mpl::vector<>() ) ); > } > > This prints the following, which is the same as yours, except in the > correct order. ;-) > > struct boost::proto::exprns_::expr<struct > boost::proto::tag::divides,struct boost::proto::argsns_::list2<struct > boost::proto::exprns_::expr<struct boost::proto::tag::multiplies,struct > boost::proto::argsns_::list2<struct boost::proto::exprns_::expr<struct > boost::proto::tag::terminal,struct boost::proto::argsns_::term<struct > placeholder<1> >,0> const &,struct boost::proto::exprns_::expr<struct > boost::proto::tag::terminal,struct boost::proto::argsns_::term<int const > &>,0> >,2> const &,struct boost::proto::exprns_::expr<struct > boost::proto::tag::terminal,struct boost::proto::argsns_::term<struct > placeholder<2> >,0> const &>,2> > > struct boost::proto::exprns_::expr<struct > boost::proto::tag::multiplies,struct boost::proto::argsns_::list2<struct > boost::proto::exprns_::expr<struct boost::proto::tag::terminal,struct > boost::proto::argsns_::term<struct placeholder<1> >,0> const &,struct > boost::proto::exprns_::expr<struct boost::proto::tag::terminal,struct > boost::proto::argsns_::term<int const &>,0> >,2> > > struct boost::proto::exprns_::expr<struct > boost::proto::tag::terminal,struct boost::proto::argsns_::term<struct > placeholder<1> >,0> > > struct boost::proto::exprns_::expr<struct > boost::proto::tag::terminal,struct boost::proto::argsns_::term<int const > &>,0> > > struct boost::proto::exprns_::expr<struct > boost::proto::tag::terminal,struct boost::proto::argsns_::term<struct > placeholder<2> >,0> > > HTH, > > -- > Eric Niebler > BoostPro Computing > http://www.boostpro.com > _______________________________________________ > proto mailing list > [email protected] > http://lists.boost.org/mailman/listinfo.cgi/proto > _______________________________________________ proto mailing list [email protected] http://lists.boost.org/mailman/listinfo.cgi/proto
