Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2004-11-16 20:27:42

Terje Slettebø <tslettebo_at_[hidden]> writes:

>> 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 ;-)

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> > > {};

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

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

> Absolutely, it's a fundamental difference, and crucial for the
> interoperability of the components of the library. That's another reason I
> didn't pursue this further at the time, as it would require a fundamental
> change of all of MPL (unless one made one's own library - or proof of
> concept, as you've done).
>> An *optimized* version of the factorial function could look
>> like this (I haven't compiled the code):
>> template<class n>
>> struct FACT
>> : FACT<typename n::eval> {}; // #1, #2
>> 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.

>> template<>
>> struct FACT<INT<0> > // #1.B
>> : INT<1> {};
> This is quite similar to how Loki does this, as well: using
> specialisations for decisions, or pattern matching (the latter being
> another common thing in FP languages).

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.

[Note that I'm not defending the MPL approach here; I'm just trying to
make sure perceptions are accurate. I like the idea of full laziness]

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

> Also, after reading the above a few times, it made complete sense. It just
> took a moment to grok this 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.

>> Let's then look at an optimized version of APPEND:
>> template<class l, class r>
>> struct APPEND
>> : APPEND<typename l::eval, r> {}; // #1
>> template<class lh, class lt, class r>
>> struct APPEND<CONS<lh, lt>, r> // #1.A
>> : CONS<lh, APPEND<typename lt::eval, r> > {};
>> template<class r>
>> struct APPEND<NIL, r> // #1.B
>> : r {}; // #2
>> Notes:
>> #1) Only the `l' parameter is forced (or explicitly invoked).
>> It would be an error to invoke the `r' parameter.
>> #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.

>> reveals
>> the substructure of the `l' parameter for pattern matching. (Note: I
>> use pattern matching for simplicity. Lazy metaprogramming should be
>> doable without pattern matching. I also have no more sympathy for
>> lousy compiler implementers. RANT: How many years does it take to
>> correctly implement a language (C preprocessor) described in about
>> 20 pages of prose? For some it seems to take more than a decade.)


>> #2) Yes, the template really inherits from `r'. The way the lazy
>> metaprogramming library is designed is to require "foreign" types to
>> be explicitly BOX<>:ed.

Of course.

>> IMO, the minimal cost (notation, readability) of
>> boxing (which can mostly be hidden anyway) is insignificant compared
>> to the semantic simplicity offered. Essentially, we can now read a
>> structure definition as an equation:
>> f p = expression // Haskell
>> template<class p> struct f : expression // Lazy C++ metaprogram
> Yeah.


Dave Abrahams
Boost Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at