|
|
Proto : |
Subject: Re: [proto] So I heard proto make AST ...
From: Joel.Falcou_at_[hidden]
Date: 2010-08-10 14:52:17
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
> proto_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/proto
>
Proto list run by eric at boostpro.com