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/