[boost] Re: Lazy Metaprogramming Library

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

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

Seconded.

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

Nifty.

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com