[Boost-users] [proto] generation of adaptive precision floating-point geometric predicates

Subject: [Boost-users] [proto] generation of adaptive precision floating-point geometric predicates
From: Andrew Durward (andrew.durward_at_[hidden])
Date: 2010-03-19 17:36:25

Hi all,
I'm exploring the possibility of using proto to transform an expression (at
compile time) into a sequence of terms whose sum represents an increasingly
accurate floating-point approximation of the result.  The underlying idea is
based on a paper by Shewchuk [1].

The central concept is that for any expression (a # b) where # is {+, -, *},
the result can be expressed as (x + y) where x is the floating-point
approximation of (a # b), and y is an error term whose value can also be
computed as a floating-point value.  

In toying with proto, I've been able to transform simple expressions
successfully but I can't seem to figure out how to define a grammar that
will handle arbitrary combinations of {+, -, *} recursively.  Here's what
I've got so far:

struct sum_approx{/* */};
struct sum_error{/* */};

struct diff_approx{/* */};
struct diff_error{/* */};

struct prod_approx{/* */};
struct prod_error{/* */};

struct Transform :
    proto::or_<
        proto::when<
            proto::plus< proto::terminal< _ >, proto::terminal< _ > >
          , fusion::cons<
                proto::_make_function(
                    sum_approx()
                  , proto::_left
                  , proto::_right
                )
              , fusion::cons<
                    proto::_make_function(
                        sum_error()
                      , proto::_left
                      , proto::_right
                    )
                >
            >()
        >
        // ... similar substitutions for minus and multiplies
    >
{};

So the expression (a + b) yields the sequence:
sum_approx(a,b)
sum_error(a,b)

Here's where I'm stuck.  In the case of the expression (a + b)*(c - d), the
addition and subtraction should be replaced by the appropriate sequences
before the multiplication gets expanded to yield the final sequence:
prod_approx( sum_approx(a,b), diff_approx(c,d) )
prod_error( sum_approx(a,b), diff_approx(c,d) )
prod_approx( sum_approx(a,b), diff_error(c,d) )
prod_error( sum_approx(a,b), diff_error(c,d) )
prod_approx( sum_error(a,b), diff_approx(c,d) )
prod_error( sum_error(a,b), diff_approx(c,d) )
prod_approx( sum_error(a,b), diff_error(c,d) )
prod_error( sum_error(a,b), diff_error(c,d) )

Obviously I need a recursive transform here but I'm not sure how to pass it
the sequences generated by both the left and right subtrees.

struct Transform :
    proto::or_<
        // ... as before
      , proto::when<
            proto::multiplies< Transform, Transform >
          , /* WHAT_GOES_HERE */<
                Transform( proto::_left )
              , Transform( proto::_right )
            >
        >
    >
{};

What exactly do I need here?  A metafunction to generate the proper
sequence?  What's the proper syntax to invoke it?

Can anybody point me in the right direction?

Thanks for any help,
andrew

[1] Shewchuk, Jonathon.  Robust Adaptive Floating-Point Geometric
Predicates.
http://www.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-predicates.p
s