Re: [boost] Boost.Preprocessor: A prototype pow(N,2) max directiteration WHILE.

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-01-15 05:12:49

David Abrahams:
>Vesa Karvonen:
> > BTW, the same "acceleration" technique can be used with templates to
> > overcome template recursion depth limitations. Probably most people
> > know about it already, though I haven't explicitly checked. > (Plain 
>unrolling is not as effective: Theta(k*n) < Theta(pow(k,n)).)
>
>Well, if I understand your suggestion correctly, it's one thing I
>thought of.  Basically you're doing "tree unrolling" instead of
>"linear unrolling", right?  In the TMP case you don't have the
>advantage of auto-detecting the depth limit, though ;-)

You are right, top-down "tree unrolling" isn't probably practical. However, 
I think that it should be possible to do the "tree unrolling" in a bottom-up 
style rather than top-down fashion. In other words, the "iteration tree" 
would look something like this:

  0 ->  1   ->   4    -> ...
       / \     /   \
      2   3   5     8
             / \   / \
            6   7 9   10

Above, each node represents a single iteration and the numbering represents 
the order in which the iterations would be done. (The numbering might also 
look different - take it as a hint rather than the only/correct/best 
choice.) The idea is that from one "top-level" iteration to another, the 
template would try iterating bigger and bigger [sub-]trees. I really 
seriously Do Not have the time to [try to] implement such a 
while_<pred,op,state> template, but out of interest I probably will, unless 
someone else demonstrates it earlier.

> > IMO, it is not a very good argument to say that more powerful tools
> > are unnecessary
>I am not making that argument.

Sorry, I guess my interpretation of your argument was too quick.

>Ever thought about writing Yacc with just the preprocessor (<wink>, I
>think)?

I have been thinking about making a lexical analyzer generator (using a 
syntax for regular expressions and using the preprocessor or run-time 
(initialization) code to generate the transition tables (once)), which is a 
lot easier to implement than a parser generator. I'd rather start with a 
simpler task, as getting something nearly as complicated done with the 
preprocessor is enough of a challenge.

-Vesa Karvonen

_________________________________________________________________
The new MSN 8: smart spam protection and 2 months FREE*  
http://join.msn.com/?page=features/junkmail