Re: Fusion-ifying proto parse trees

Joel de Guzman wrote:
> David Abrahams wrote:

> > Just to be provocative, I'll even go further and claim that flattening
> > is evil :).  For the maximum performance in most linear fusion
> > algorithms, you actually want to impose a tree structure on flat data.
> > That is, divide the sequence in two (for example), do your algorithm
> > on the first half, and then continue on the second half, recursively.
> > Among other things, this approach makes the most of the compiler's
> > inherent inlining depth limitations.
>
> Good points! I am not sure though how to put your theories into
> practice. In the real world ET trees are almost flat, heavily
> lopsided trees. Take (a >> b >> c >> d), for example. That ET
> gives you a tree like this:
>
>     seq(seq(seq(a, b), c), d)
>
> which is almost like a reverse cons list.

Just to clarify:

Actually, "flattening" is a bit of a misnomer. I think the correct
word is "collapse". For example:

    a + b + c * d

gives us:

    +
   / \
  a   +       plus(a, plus(b, multiply(c, d)))
     / \
    b   *
       / \
      c   d

If in our language, we know that + is *associative*, we can use
that knowledge to collapse the + nodes from binary to n-ary:

     +
   / | \
  a  b  *     plus(a, b, multiply(c, d))
       / \
      c   d

Regards,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642