Re: [proto] So I heard proto make AST ...
On Wednesday 11 August 2010 00:45:44 Eric Niebler wrote:
On 8/10/2010 3:52
PM, Thomas Heller wrote:
On Tue, Aug 10, 2010 at 8:56 PM, Eric Niebler
wrote:
Good. Now if you are saying that Proto's existing transforms
are
too low-level and that things like pre- and post-order traversals
should be first class Proto citizens ... no argument. Patch? :-)
I think i am a little bit responsible for that whole discussion as i
mentiones on IRC that proto transforms are hard for me.
The #boost
IRC channel? Perhaps I should spend time there.
You definitely should :)
So, why are they so hard. I am currently learning the principles of
compiler construction (lecture at university). We learn all those
fancy
algorithms to optimize the hell out of our codes. But these
algorithm
all rely on bottom-up, top-down and what-not traversals of
your AST.
proto transforms work a little bit different from these
tree traversals.
BUT they are very similiar, and probably as you
said, a little more low
level. Just my 2 cents ;)
And a good 2 cents. I never actually took a
compiler construction class.
Oops! But as I showed earlier in this thread,
pre-order traversal can be
expressed in terms of fold. Post-order is much
the same. But if I'm
going to go around claiming Proto is a
compiler-construction toolkit, it
should have the algorithms that people
would expect, not the ones I just
made up. :-P
Yeah, i already did some
traversals. But you have to think everytime: Did I make it right? Did I miss
some rule in my DSEL grammar?
IMHO, the important difference between a proto
transform and a proto expression traversal is that the transform has to
replicate your grammar, every time. And a traversal simply does not care if
your grammar is right or not. You just want to go over all elements of your
tree. The validity of your DSEL should have been checked one step before
(think of multi-pass compiler).
Joel Falcou showed a technique which, to
some extend is able to deal with the no-repetition part.
Let me give you an
example of a traversal which simply doesn't care if the expression given is
in the language or not (I will present you some transforms I have written
for phoenix3).
First, in pheonix, we want to know: What is the arity of our
expression, or sometimes a little weaker, do we have a nullary, or a n-ary
expression?
This is easily done with a proto transform, I agree.
For arity
calculation we have this transform (notice something? We have a transform
where a simple traversal would be sufficient):
struct
arity
: proto::or_
proto::whenproto::terminalproto::_, mpl::int_0()
,
proto::when
proto::function
proto::terminalfuncwrapargument
,
proto::terminalenv
, proto::_
, mpl::nextproto::_value(proto::_child2)()
, proto::otherwise
proto::fold
proto::_
, mpl::int_0()
, mpl::maxarity, proto::_state()
{};
Yet, very elegant (imho), it is quite
complex and not easily spotted what this code is doing.
With some kind of
post-order traversal and the appropriate visitor this might look simpler. I
have to admit though, i have no idea how such a traversal could look
like.
Eric, in one of your posts you mentioned the potential of phoenix3. I
think, this potential can be highly increased by having some kind of
traversal helper functions, just because I think people are more familiar
with the concepts of traversals and visitors (or, FWIW, iterators) than with
proto transforms. On the other hand, proto transform already are a powerful
tool, perhaps a little too powerful for some simple tasks. Perhaps we have
to educate people for a mind-shift to the direction of proto transforms.
And if you think Proto's transforms are hard now, be glad you weren't
using Proto v2 in 2006. shudder
___
proto mailing list
proto@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] So I heard proto make AST ...
On 11/08/10 17:52, Eric Niebler wrote: I don't exactly recall the details of Joel's technique. My experiments to separate transforms from grammars were largely unsuccessful because control flow often need pattern matching. I'd like to see alternate designs. Mine was just a post-order traversal by a visitor that could be specialized on node's tag Ah, but the control flow of this transform depends on pattern matching (i.e., the grammar) to dispatch to the correct handler. I'm interested to see what this arity calculation would look like with a tree traversal. Last time I tried, i ended up needing a meta-function that gave you the arity of any tag. Then you did a fold of max over the tree traversal. ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] So I heard proto make AST ...
This is kind of like Proto's evaluation contexts, IIUC. I'm not wild for them because often just the tag isn't enough information to find the right handler. But maybe it covers enough use cases and can be made easier to use. Right now, proto has an eval function that takes an expression and an evaluation context, but the user is responsible for the flow control. Maybe there should be a pre_order_eval and post_order_eval that takes on the control flow responsibilities. Yes but here each tag specialization leaves in its own function object and not as an operator()(). For sepcific need, we can specialize based on tag+type of visitor+type of visitee. Tags don't have arities. E.g. nothing prevents someone from creating an expression with tag::plus and 5 children. Yes but the same way proto operator has the expected behavior by defualt, one can expect they have expected arity. ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] So I heard proto make AST ...
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_::exprboost::proto::tag::terminal,
Re: [proto] So I heard proto make AST ...
On 8/10/2010 2:52 PM, joel.fal...@lri.fr wrote: Eric Niebler wrote: A pre-order traversal, pushing each visited node into an mpl vector? How about: snip I'm on a tiny mobile, but my idéa was to have such algo as proto transforms grammar Good. Now if you are saying that Proto's existing transforms are too low-level and that things like pre- and post-order traversals should be first class Proto citizens ... no argument. Patch? :-) -- Eric Niebler BoostPro Computing http://www.boostpro.com ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] So I heard proto make AST ...
On 7/27/2010 9:01 AM, joel falcou wrote: what about having some Tree related trasnform/function/meta-function then ? I'm often thinking : dang, this transform is basically a BFS for a node verifying meta-function foo and have to rewrite a BFS usign default_ and such, which is relatively easy. Now, sometimes it is dang, this code is basically splitting an AST into multiples AST everytime I found a bar tag or I need to do a DFS or even worse, I need to make the AST a DAG :E ... Do people think such stuff (maybe in proto::tree:: or smthg ?) be useful additions ? That would be awesome, Joel! -- Eric Niebler BoostPro Computing http://www.boostpro.com ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] So I heard proto make AST ...
On 27/07/10 15:08, Eric Niebler wrote: That would be awesome, Joel! I'll count on you for helping me making those looking nice :p What's the easiest ? getting a proto-tree branch or what ? ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] So I heard proto make AST ...
On 27/07/10 15:08, Eric Niebler wrote: That would be awesome, Joel! WHat's the easiest in term of code ? I can bring up some git repo or shoudl I work in some svn branches of proto somewhere at boost ? ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] So I heard proto make AST ...
I think you should talk to Gordon Woodhull. He's building a metagraph (among others) library, which I am going to use in msm for compile-time calculations and fsm analysis. This means there will be temporarily a metagraph library inside msm as proof of concept until there can be a review. Maybe he can adapt this library for proto analysis? Oh yeah, will save me some time indeed. Mayeb we shoudl invite him over here ? I just sent him a mail. BTW the metagraph library is in the sandbox, and a potential usage with msm was sent by Gordon on the devel list just at the end of the BoostCon. Christophe ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
