Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-14 16:07:37

>From: "Matthew Hurd" <matt_at_[hidden]>

> From: "David Abrahams" <dave_at_[hidden]>
> >
> > Even if you don't buy the need for different sequences, the plain fact
is
> > that different sequences exist. It can be useful to be able to
> > interoperate with them.
>
> Could a tree such as that used in an expression template evaluator be
easily
> expressed with MPL and be suitably manipulated?  This might help the
> argument especially if it could interoperate with something like POOMA's
> PETE lib.  I'd see being able to specify, manipulate and subset expression
> trees with their proxies and typelists in a similar style as a good thing
> (TM).

This may not be that easy, using iterators. Trees are inherently recursive,
so they are usually much easier to traverse and manipulate, using recursive
algorithms, than iterative algorithms.

Here's an example of a compile-time expression tree, written in MPL:

#include <iostream>
#include <boost/mpl/apply.hpp>
#include <boost/mpl/int_c.hpp>
#include <boost/mpl/arithmetic/plus.hpp>
#include <boost/mpl/arithmetic/multiplies.hpp>

using namespace boost::mpl;

template<class E,class L,class R>
struct tree_node
{
  typedef E element;
  typedef L left;
  typedef R right;

  typedef typename apply2<
    element,
    typename left::type,
    typename right::type
  >::type type;
};

int main()
{
typedef tree_node<
  multiplies<>,
  tree_node<
    plus<>,
    int_c<1>,
    int_c<3>
  >,
  int_c<4>
> tree;

typedef tree::type result;

std::cout << result::value << '\n'; // value = (1+3)*4 = 16
}

This performs a recursive postorder traversal (evaluating the leaves before
the node itself), to evaluate the expression tree "tree". It contains
operations or values at the nodes. Here, it's defined like this:

             tree_node (multiplies)
              /                    \
tree_node(plus)    int_c<4>
     /             \
int_c<1>    int_c<3>

The whole traversal exists in tree_node, itself, the "type" typedef, so no
iterators are involved. For such a recursive structure, it makes the
travelsal simple.

It at least shows that MPL has a structure to facilitate writing such code.
Only the tree_node, itself, was needed. The rest already existed.

It would also be possible to write such a routine to produce run-time inline
evaluation of the tree.

Regards,

Terje