Re: [boost] Lazy Metaprogramming Library

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2004-11-16 16:43:36

(Sorry for the late reply. I find this very interesting)

>From: "Vesa Karvonen" <vesa_karvonen_at_[hidden]>

Thanks for the comprehensive reply, it's much appreciated.

> Terje Slettebø:
> [...]
> >It's an interesting approach, and IIUC, one that has come up
> >before (see the "Meta function variants of mpl::apply_if
> >necessary?" thread a couple of years ago -
>
> BTW, I independently invented the equivalent of `apply_if' and
> described it publicly under the name `type_inner_if' (although I
> recall it wasn't the first name I gave to the metafunction):
>
>   http://lists.boost.org/MailArchives/boost/msg12815.php
>
> IIRC, MPL didn't have `apply_if' at the time.

Great minds think alike, I guess. :)

>From my experience, the world of metaprogramming is full of cases of
independent discovery (myself, I started trying to generalise Loki, using
predicates, and I started going in the direction of lambda, etc. and found
it went in the direction of MPL... so I abandoned it, as there was no use
creating something like MPL, when it already existed). Richard Crossley
mentioned in a mail (after him, Aleksey, and I had independently come up
with an eval<>/lazy<> construct), that there seems to be more or less only
one way to do metaprogramming. :) (eval<F<T> >::type -> F<T::type>::type)

That about using laziness consistently was what I guessed was the crux of
the issue. However, as Aleksey had considered it during the development of
MPL, I assumed that the reasons he gave against it were sufficient, so I
didn't pursue it further. However, from your posting and library, it seems
it could need a re-examination, because I do like the elegance, efficiency
and simplicity of use of a purely lazy approach (being lazy is good :) ),
and it's very in the spirit of functional programming languages (which
template metaprogramming may be considered, being purely functional), such a
Haskell.

I guess one thing one may learn from this all is that it doesn't matter who
tells you something is a bad idea, if you're not convinced yourself that it
is (which I wasn't). If I had pursued the idea, it might have been me who
had presented a proof-of-concept lazy metaprogramming library. (On the other
hand, like you, I've had other fish to fry, such as the concept traits
library.) Besides, making a proof-of-concept implementation (rather than
trying to convince others there was something to this), is something that
didn't occur to me at the time. It's a good idea.

I'm looking forward to explore your library, when I get a chance.

By the way, Aleksey has also mentioned that the functional influence on MPL
is much inspired by you.

> Ever since I first used template metaprogramming, I have been
> searching for a template metaprogramming "style" (a minimal and
> unambiquous set of rules to follow), that would make template
> metaprogramming as simple as ordinary programming. Most template
> metaprograms are fundamentally very simple (usually next to
> trivial), but the simplicity is hidden behind a ton of intricate
> syntax and evaluation order annotations.
>
> >Your algorithms, such as:
> >
> >template<class l>
> >struct SIEVE
> >   : CONS<HEAD<l>,
> >          SIEVE<FILTER<NOT_DIVISIBLE_BY<HEAD<l> >,
> >                       TAIL<l> > > > {};

It seems your search is similar to what lead you to your Order PP-library.
:) (You also mention this later in the mail)

> >template<class V>
> >struct factorial
> >{
> >   typedef typename V::type Value;
> >
> >   typedef typename apply_if<equal_to<Value,value<Value,0> >,
> >     value<Value,1>,
> >     mul<Value,factorial<prior<Value> > >
> >   >::type type;
> >};
> >
> >The reason there are still "::type" expressions in the above, is that it
> >relies on MPL metafunctions that aren't lazy. [...]
>
> 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.

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

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

> The factorial function is not a very good example in the sense that
> it is completely strict. In other words, the factorial function
> *always* needs to examine the substructure of *every* parameter it
> receives. There are, however, lazy metafunctions that have both
> strict and non-strict parameters. The APPEND<l, r> metafunction for
> concatenating two lists is one example of such a function. Let's
> first see the unoptimized version:
>
>   template<class l, class r>
>   struct APPEND
>     : IF<IS_NIL<l>,
>          r,
>          CONS<HEAD<l>,
>               APPEND<TAIL<l>, r> > > {};
>
> It is easy to see that APPEND is strict in the `l' parameter,
> because it is *always* examined by the conditional.

*packs some ice-bags on his head* Go on.:) No, really; I'm fine. ;)

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

> However, the `r'
> parameter never needs to be examined---and a correct implementation
> of APPEND must never force the evaluation of (explicitly invoke) the
> `r' parameter. Consider the following definition of an infinite
> list:
>
>   struct INFINITE_LIST_OF_ONES
>     : APPEND<LIST<ONE>,
>              INFINITE_LIST_OF_ONES> {};

Ah, yes: the lazy infinite list. That's one of the first things I thought
of, when I read your posting about a purely lazy metaprogramming language.

> If APPEND<l,r> would force the evaluation of the `r' parameter the
> above definition would not work correctly. (Can you see why?)

Oh, yes, you'd get an infinite recursion, wouldn't you? (I've experienced a
few of those in metaprogramming...)

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

Do I detect a hint of bitterness? ;)

I'm sure Paul Mensonides is struggling with similar things, his Chaos
library being only usable on the most conforming compilers (from what I
understand).

I guess some of the reason might been that it hasn't been much of a priority
for compiler vendors. It's rather unlikely that a huge number of customers
come to them, asking for better preprocessor support... :)

On the other hand, with PP-programming having been become more "mainstream",
being used quite a bit in Boost, for one thing, this might change.

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

Like using mpl::identity<>.

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

> The following snippet is from the (old) thread cited above:
>
> Aleksey Gurtovoy:
> >I considered and re-considered the idea a couple of times during
> >MPL development. It doesn't really work well; in particular, it
> >conflicts with the notion of nullary metafunctions, pretty much
> >making the library useless for manipulating the latter ones:
>
> [[ I wont quote more. Please lookup the message yourself. ]]
>
> Well, looking at the code that Aleksey shows, I see that laziness is
> *not* used systematically like in the lazy metaprogramming library.
> The rule is that a lazy metafunction may only invoke an parameter if
> it really has to. In particular, the following line (not the only
> line) of the push_back example
>
> Aleksey Gurtovoy:
> >                , typename T::type // apply0<T>::type
>
> would be (clearly) incorrect, because it invokes the parameter T.
> The push_back metafunction doesn't need to examine the substructure
> T and therefore should not force it to be evaluated. In other words,
> the push_back metafunction is not supposed to be strict in the T
> parameter.

Right.

> *NOTE*: The code in the cited thread is probably even more
> "confusing" than ordinary strict metacode that essentially contains
> evaluation order annotations. Please do not confuse the programming
> style used in the cited thread with the programming style used in the
> lazy metaprogramming library. They are very different. In particular,
> explicit invocations are used in the lazy metaprogramming style only
> for two purposes:
> 1) When a primitive metafunction *explicitly* has to examine the
>    substructure of an actual parameter (e.g. to check whether a list
>    is NIL or CONS<h, t> or to get the value of an integer or boolean
>    parameter).
> 2) *Optionally* for (safe) optimization based on strictness
>    analysis.

Thanks for the clarification.

> >One thing, though: Why the very non-Boost style identifiers (lower
> >case template parameters, and upper case template names), such as:
>
> The upper case naming is the last thing you should worry about. :)

Yeah. :)

> >Writing pp-code (using uppercase characters) a hard habit to break? ;)
>
> Not really. On the other hand, I rarely program in C++ these days,
> but when I do, I usually play with metaprogramming techniques.

Yeah, I was just kidding. :)

You should really write an article on this at "The C++ Source", that you
mentioned, if you get a chance. (You have quite a bit of material in this
this posting, already.)

Regards,

Terje