[boost] Re: Lazy Metaprogramming Library

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2004-11-16 22:04:13

David Abrahams
>Terje Slettebø:
>
> >> Yes, that is exactly what I mean above. *Systematic* use of lazy
> >> template metaprogramming would yield the following (unoptimized)
> >> factorial function:
> >>
> >>   template<class n>
> >>   struct FACT
> >>     : IF<IS_0<n>,
> >>          INT<0>,
> >>          TIMES<n, FACT<PRED<n> > > > {};
> >
> > Elegant, indeed.
>
>But it doesn't work ;-)

Yes, the code snippets in my message have several typos. Like I
recall seeing certain B.S. saying in a USENET posting, I don't
(always) compile my e-mails. :)

However, I have written a complete walkthrough of the factorial
example that you can find in the library I just updated:

  http://groups.yahoo.com/group/boost/files/LazyMPL/

[...]
>In fact it would look almost the same in MPL, though ;-)
>
>    template<class n>
>    struct fact
>      : if_<equal_to<n, int_<0> >,
>           int_<1>,                // <== here's the fix ;-)
>           multiplies<n, fact<typename prior<n>::type> > > {};

Yes, I realize that MPL contains *lots* of "glue" to make Strict TMP
(strict template metaprogramming) as pleasant as possible.

However, are you sure that the above works? It seems to me that you
are missing at least an invocation... ;--)

>The one typename appears there because prior can work on iterators as
>well as numeric types.  We can kill it this way:
>
>    template<class n>
>    struct fact
>      : if_<equal_to<n, int_<0> >,
>           int_<1>,
>           multiplies<n, fact<minus<n, int_<1> > > > > {};
>
>And this particular case is especially friendly to MPL.
                              ^^^^^^^^^^^^^^^^^^^^^^^^^^
>Some of those advantages are lost when you're not manipulating
>numeric values.

I'm not sure what mean here. Please elaborate.

> >> As you can see, all explicit invocations are eliminated. I think
> >> that there is a huge difference between applying laziness in an
> >> essentially ad hoc manner (little here and little there) rather than
> >> applying it systematically (all metafunctions are lazy).
>
>Agreed, in the general case.

Yes, like I said earlier, the factorial function isn't a
particularly good example---for several reasons. (However, the
factorial function does have the virtue of being a simple case to
understand and discuss.)

> >>   template<long n>
> >>   struct FACT<INT<n> >                          // #1.A
> >>     : INT<(n * FACT<(n-1)>::eval::value)> {};
>                        ^^^^^
>I don't think so.  You can only pass a type here.

[Again, this is fixed in the example that you can find in the
updated library.]

>MPL isn't afraid of specializations, FWIW.  There's nothing going
>on in the above example that couldn't be done with MPL so far.

Also note that Lazy TMP (lazy template metaprogramming) can be done
without pattern matching. I've used pattern matching in the
proof-of-concept library, because it can sometimes be simpler and
I have no interest to avoid pattern matching just because some
compiler might not support it properly. (Of course, pattern matching
is something that should be avoided when one is designing generic
operations. Explicitly naming a specific (type) constructor in a
pattern can make the code dependent on a particular representation.)

>This FACT isn't generic (doesn't work for LONG<3>, for example; I
>assume you have LONG).

No. The library only has the INT-template, whose template argument
is a long. Designing a complete numeric tower hasn't been a priority
so far. (Actually, I think that supporting several primitive integer
types may be an unnecessary overkill anyway, but this is something I
have no interest to discuss at this point. It would be a red-herring,
IMO. The issue is orthogonal to the issues of Lazy TMP vs Strict TMP.)

> > [...] concept of using both strict and non-strict
> > parameters in the same algorithm. :)
> > Just when I thought I had grokked metaprogramming. ;)
>It's just an FP thing.  Has nothing to do with TMP, really.

Yes, that is basically true. (While speaking of the concept of
strictness, that is.)

However, issues related to strictness and laziness are particularly
important when it comes to template metaprogramming. The C++
template mechanism is both too lazy and too strict. It is too lazy in
the sense that a metafunction has to be explicitly invoked to get
the final value of a computation. It is too strict in the sense that
once a metafunction is invoked, all the invocations in the body of
the metafunction (or specialization) are evaluated immediately.

> >> #1.A and #1.B) The explicit invocation of the `l' parameter
>
>The only explicit invocation of `l' I can see is in #1.  Maybe that's
>what you meant.

[Yes. #1 referred to the invocation and #1.A/#1.B referred to points
where the information revealed by the invocation was used.]

-Vesa Karvonen

_________________________________________________________________
Don't just search. Find. Check out the new MSN Search! 
http://search.msn.click-url.com/go/onm00200636ave/direct/01/