Re: [Boost-users] [Proto] proto::reverse_fold_tree

Subject: Re: [Boost-users] [Proto] proto::reverse_fold_tree
From: Eric Niebler (eric_at_[hidden])
Date: 2009-02-02 14:11:29

Dave Jenkins wrote:
> 
> "Kim Kuen Tang" <kuentang_at_[hidden]> wrote in message 
> news:498587FA.4050404_at_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<a,b> 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<a,b>, 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_tree.html

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