Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-15 17:04:32

>From: "Paul Mensonides" <pmenso57_at_[hidden]>

I'll get to your other postings, too.

>From: "Terje Slettebø" <tslettebo_at_[hidden]>

Adding a quote from another posting, to put this in context.

>The STL uses the above primary in the
>service of sequence abstraction.  That is what I meant, but that is not
what I'm
>disagreeing with.  For example, with your compile-time exponentiation
>metafunction, I think that having the arithmetic functions "evaluate" the
>arguments themselves is a good idea, and I have no disagreement with its
>design--other than it doesn't apply well to half compile-time arguments and
half
>runtime arguments. (see "Generative Programming" - Czarnecki & Eisenecker).

>The most relevant problem with the example is that it has nothing to do
with
>sequences or containers--which is the primary thing that Andrei and I are
>debating.  Of course, there are two other problems.  This little factorial
>allows you to calculate a factorial of two compile-time constants:
(pseudo-code
>follows)

>pow( constant, constant )

>What about these:

>pow( constant, runtime-value )
>pow( runtime-value, constant )

I understand what you mean, now. I have "Generative Programming", but I've
only read some in it, so far. I've had it for a while, but I've been saving
it for when I can read it at a more leisuredly pace, as I recognized it as
an important book.

However, since you referred to it here, I looked this up, and as you said,
there was precisely, even a "power" (!) example there, where you could do as
you say above here.

When I first read the posting, I thought you meant somehow getting the
result at compile-time. However, I understand now that this is about
possibly partial evaluation. That is compile-time only, run-time only, or
some compile-time and some run-time. Sorry for not checking this out before
replying. Anyway, I've checked it out now, then.

The way it's done in the book is cool. :) This bridges compile-time and
run-time programming, creating a contiuum between them. Instead of having
two different syntaxes in the program, you can use the same for both. Nice.
:)

To take your examples again, here:

>pow( constant, runtime-value )
>pow( runtime-value, constant )

The first one isn't a very interesting case, as you can't really do anything
at compile-time, such as unrolling the loop, as the loop count is unknown at
compile-time. So here you could just as well use the run-time version.

The second version, however, lets you unroll the loop, as you say.

You can also have this case:

pow( runtime-value, runtime-value )

Which could then call std::pow, or possibly a specialisation for integral
exponents.

This is a good idea. I think MPL (or a library using MPL) definitely could
have use for a collection of run-time routines. It could increase the
usefulness of metaprogramming, by extending it to partial evaluation, as
well, thus letting the boundary between compile-time and run-time be
variable.

Several libraries uses such techniques for increased efficiency, as you
said, by evaluating what can be evaluated at compile-time, doing the rest at
run-time. For example uBLAS.

I looked into how this could be done with MPL. Also, if having the
metafunctions evaluate their own arguments would have any effect on this.
However, in this case, it won't matter, as the pow() function is passed a
value, not a type. By the time you've determined if the value is a
compile-time value or run-time value, you'll know whether or not you may
apply "::type" to the type.

I've tested this out, making such a pow() function, that works like this. :)

I've attached an archive with the necessary files, and a test, with this
posting. Any changed files are included, and they are #include'ed from the
current directory (the archive directory), so no changes are needed to MPL.
I've tested it on Intel C++ 6.0, and it works just fine. I've also verified
that the resulting assembly code is as expected.

I've also tried it on g++ 2.95.3, but it doesn't work there. It purposely
doesn't use partial specialisation, anywhere.

"Generative Programming" uses overloading, to select between compile-time,
run-time, or a combination. However, as there may be more than one kind of
compile-time type, and it's extensible, and that you may use any
non-compile-time type, as well, this approach isn't extensible enough.

Therefore, the routine relies on detecting a compile-time tag (nested
typedef) for the types passed to it, and if present, it knows the type is
compile-time. The detection routine is the one you've made, and it's used
below here (the "has_ct_tag" metafunction). For simplicity, it doesn't check
that the "ct_tag" nested typedef is the correct type, too, although that
could be done, as well.

I've also put the pow() function in the boost::mpl::runtime namespace, to
avoid name-collision with the compile-time components.

The core of the pow() function is this:

--- Start ---

////////////////////////////////////////////////////////////////////////////
///
// runtime_pow_impl
////////////////////////////////////////////////////////////////////////////
///

template<class Base,class Exp>
struct runtime_pow_impl
{
  typedef typename if_<
    has_ct_tag<Exp>,               // Exp==constant?
    typename if_<
      has_ct_tag<Base>,            // Base==constant?
      ::boost::mpl::pow<Base,Exp>, // pow(constant,constant)
      pow_exp_constant<Base,Exp>   // pow(runtime,constant)
    >::type,
    runtime_pow<Base,Exp>          // pow(runtime,runtime)
  >::type type;
};

////////////////////////////////////////////////////////////////////////////
///
// pow
////////////////////////////////////////////////////////////////////////////
///

template<class Base,class Exp>
inline typename aux::runtime_pow_impl<Base,Exp>::type::type::type pow(Base
base,Exp exp)
{
  return aux::runtime_pow_impl<Base,Exp>::type::result(base,exp);
}

--- End ---

It's used like this (from the included example program):

--- Start ---

const int base=10;
const int exponent=3;

int main()
{
int_c<base> base_const;
int_c<exponent> exponent_const;

int result_pow=runtime::pow(base_const,exponent_const);    //
pow(constant,constant) - result=1000
int result_exp_constant=runtime::pow(base,exponent_const); //
pow(runtime,constant)  - result=base*base*base=1000
int result_runtime_pow=runtime::pow(base,exponent);        //
pow(runtime,runtime)   - result=std::pow(base,exponent)=1000

std::cout << result_pow << '\n';
std::cout << result_exp_constant << '\n';
std::cout << result_runtime_pow << '\n';
}

--- End ---

By the way, even though there's an SGI STL extension "power", then with
other functions, such as its inverse, "log", "sqrt", etc, it may be more
consistent with "pow".

Another thing is that, here, the type abstraction would mean that you could
call such functions using floating point compile-time values, something you
wouldn't otherwise be able to do, without writing separate special versions
for each kind of compile-time value. The pow() function is completely
generic, so it works for any type, compile-time or run-time.

Regarding the pow(runtime,constant) case. The utility for the loop
unrolling, in this case, is perhaps questionable, as some compilers (such as
Intel C++), unroll loops, anyway, if it knows the loop count at compile
time. Still, it's good to know that this can be done. For more complex
evaluations, such as expression templates, the compiler's loop unrolling is
not enough.

To Andrei: If you reacted to the factorial routine, you have seen nothing,
yet. :) Take a look at this. :) Particularly "runtime_pow.hpp".

Regards,

Terje