Re: [boost] Re: MPL containers and algorithms

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-08-15 23:39:54

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

> 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.

It has some interesting stuff in it.

> 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.

Yes.  This shows in very good (and simple in this case) that metaprogramming is
not entirely self-contained.  It is two languages that are still one language.
A great deal of metaprogramming exists for the sole purpose of optimizing
runtime performance, so you can't view metaprogramming as an entirely separate
world.

> 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.

Cool.  Yeah, I was talking about partial evaluation through recursive inlining.

> 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.
> :)

That bridge has always been there, it is just generally forgotten.  It is easy
to think of template metaprogramming as an entirely separate language, but it is
not.  I think this is partially where Andrei and I are coming from--using the
runtime language facilities together with the compile-time facilities.

> 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.

Yes.

> 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.

Yes, the only major annoyance, IMO, is the use of some type of integer<10> flag
to show that it is a constant value.  The preprocessor can be put to work here
to detect integer literals directly as long as the numbers are in a given range.

> 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.

I agree.

> 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.

Yes, and in that case very effectively.

> 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. :)

Cool.  I'm glad that I pointed it out.  This type of thing makes metaprogramming
even more interesting <-- though I personally don't really care about the type
abstraction. :)

> 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.

It would be a pretty poor optimizer if it didn't inline the recursive template
instantiations. :)

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

I'm not too familiar with g++, so I can't give you any pointers on what is
wrong.  Sorry.

> "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.

It doesn't really need to if the nested name is relatively unique.

[...]

> 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.

Personally, I don't think that exponentiation of floating-point values at
compile time is very general purpose.  However, knock yourself out; it's your
perogative. :)

> 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.

More importantly, you have near explicit control over it.

Paul Mensonides