Re: [boost] Lazy Metaprogramming Library

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2004-11-01 19:36:01

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.

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

The above is from an old version of the library. You might want to
get the latest snapshot, which has a couple of important
improvements. You can find the latest snapshot at:

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

...

>   http://thread.gmane.org/gmane.comp.lib.boost.devel/73829).
>
>However, as shown in the posting by Aleksey, it was considered and
>reconsidered during MPL development, but dropped, due to not at
>least problems with passing nullary metafunctions to functions,
>without evaluating them in the passing.

Hmm... From a cursory reading of the thread, it seems to me that
there are some similar ideas, but crucially, what seems to be
missing is a "holistic" treatment of laziness. I think that is quite
understandable given that (implementation of) lazy functional
programming (languages) isn't something that C++ programmers
generally think about. Basically, all the examples in the thread
seem to mix and match strict and lazy evaluation:

>[...] my example in the above thread:
>
>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> > > > {};

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

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

#1) The crucial note to make of the above code is the explicit
    invocation ::eval used in the non-specialized version of the
    FACT-template. The purpose is to reveal the INT<> constructor
    for pattern matching (#1.A and #1.B).

#2) I use the name `eval' instead of `type', because `eval'
    describes the intention more clearly: `::eval' forces the
    evaluation of a parameter. [The name `type' is used with
    boxing (BOX<t>::type == t and BOX<t>::eval == BOX<t>).
    (Boxing is also mentioned later in this message.)]

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

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

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

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

...

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.

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

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

Some reasons:
* I don't like trailing underscores, e.g. `if_' and `int_'.
* I had the idea of making a lazy metaprogramming library while I
  implemented a template metalanguage interpreter (similar to
    http://lists.boost.org/MailArchives/boost/msg36510.php, but
  with some fresh ideas). In the language I used upper case
  identifiers for "keywords" of the language and lower case
  identifiers for everything else. When I started implementing
  the lazy library, I ended up using upper case identifiers (and
  haven't bothered to rename globally).

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

>Come to think of it, the "Generative Programming" book had the
>same convention of upper case names for metafunctions.

The GP book used upper case identifiers for control structures like
IF, WHILE, FOR, etc... and for the "keyword" like names such as RET.

-Vesa Karvonen

_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE! 
http://messenger.msn.com/