Dave Jenkins wrote:

"Kim Kuen Tang" wrote in message news:498587FA.4050404@vodafone.de...

...

Hi all,

i want to use the function proto::reverse_fold_tree to build a heterogeneous list from the expression "((a*b+c)*d+e)*f". The resulting sequence only contains the two terminals 'a' and b'. So i am a little bit confused.

But using the function proto::fold_tree it produces correctly the sequence [f,e,d,c,b,a]. (Btw the two functions proto::fold_tree and proto::fold produce the same sequence [f,e,d,c,b,a], what is their difference? )

Hi Kim,

I think the basic problem is that fold_tree and reverse_fold_tree expect the child nodes type to be the same in the flattened sequence.

Right. Thanks Dave, you beat me to the punch again.

Your expression "((a*b+c)*d+e)*f" is mixing plus nodes and multiply nodes.

To show why fold_tree appears to work and reverse_fold_tree doesn't, consider the expression "a*b+c". With fold_tree it produces the correct sequence [c b a], but reverse_fold_tree produces the incorrect sequence [a b].

What's happening is FoldToListReverse processes the children of plus<> in reverse order, so it first pushes "c" on the sequence. Then it sees the <multiply> node and gets a mismatch against the original plus<> tag, So, it recursively calls FoldToListReverse. This clears the sequence to nil (throwing away "c"). Then it flattens multiply and pushes "a b" on the sequence, which is what you see displayed.

With FoldToList, it appears to work because it processes the children of plus<> in forward order. So it immediately recursively calls FoldToList because the tags <plus> and <multiply> tags don't match. But at this point, clearing the sequence doesn't matter. It processes multiply, pushing them on the sequence. Then it returns and pushes "c" on the sequence. That's why it appears to work.

You can see that both are broken if you try the expression "(a*b+c)*(do*e+f)". That displays [f e d] for reverse_fold_tree and [a b] for fold_tree.

I trust your analysis, although I haven't had time to look deeply into it myself. I'll merely add that it appears as if Kim is recursively invoking his transform, whereas the purpose of the fold_tree and reverse_fold_tree transforms is to do the recursion for you in the common case that you're only interested in folding sub-trees that all have the same node type. The docs show how fold_tree is implemented in terms of fold: http://boost-sandbox.sourceforge.net/libs/proto/doc/html/boost/proto/fold_tr... My suggestion is to copy the implementation of fold_tree and modify it to do what you want by ignoring node type or whatever. HTH, -- Eric Niebler BoostPro Computing http://www.boostpro.com

Joel Falcou wrote:

Dave Jenkins a écrit :

...

You can see that both are broken if you try the expression "(a*b+c)*(do*e+f)". That displays [f e d] for reverse_fold_tree and [a b] for fold_tree.

Then, is there anyway to implement a real Depth First or Breadth First traversal of the whole AST in Proto ?

Certainly, but not with any of Proto's "built-in" transforms. Generic tree traversal is a HUGE domain, and not something I can just whip out. ;-) Dan Marsden has been working on that problem for some time with his Boost.Traversal library. The Haskell folks have done lots of work in this area, too. Just Google "Scrap Your Boilerplate" and see how deep the rabbit hole goes. -- Eric Niebler BoostPro Computing http://www.boostpro.com

Joel Falcou wrote:

Eric Niebler a écrit :

...

Certainly, but not with any of Proto's "built-in" transforms. Generic tree traversal is a HUGE domain, and not something I can just whip out. ;-) Dan Marsden has been working on that problem for some time with his Boost.Traversal library. The Haskell folks have done lots of work in this area, too. Just Google "Scrap Your Boilerplate" and see how deep the rabbit hole goes.

Yeah I kinda digged into it last time I bothered you with my code snippet a few month ago. Well, what kind of approach can be take to get something simple going on ?

My advice to you would be the same as my advice to Kim. Much can be done with recursion and proto::fold. Copy the implementation from proto::fold_tree or proto::reverse_fold_tree and modify it as needed. http://boost-sandbox.sourceforge.net/libs/proto/doc/html/boost/proto/fold_tr... HTH, -- Eric Niebler BoostPro Computing http://www.boostpro.com

Kim Kuen Tang wrote:

Eric Niebler schrieb:

...

...

Ok, i have understood that child nodes must share a tag type with the parent node as indicated by the document

template struct recurse_if_ : <anip> {};

So my next step will be to define my own fold function. Thanks a lot to all the people here.

You shouldn't have to redefine fold. You'll need to redefine recurse_if_ as used by fold_tree. Good luck. -- Eric Niebler BoostPro Computing http://www.boostpro.com