Re: [boost] Lazy Metaprogramming Library
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/
(Sorry for the late reply. I find this very interesting)
From: "Vesa Karvonen" <vesa_karvonen@hotmail.com>
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
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Terje Slettebø
(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? ;)
Plenty.
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'm not exactly struggling with it. I'm simply not supporting any preprocessor that is buggy. The purpose of Chaos is to see how far that I can push it, to see how many techniques that I can create, etc., not to make a practical tool. That is only a side-effect of the underlying motivation, and that side-effect only happens to come into play on very good preprocessors.
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.
Unlikely. Boost is so full of workarounds for broken compilers (and preprocessors) that it doesn't really encourage vendors to fix their compilers much at all. Furthermore, most vendors lack a fundamental motivation: implementing the language according to the standard because it is the right thing to do from an ethical standpoint. With the preprocessor specifically, vendors have a low opinion of heavy preprocessor use based on years of invalidly attributed stigma. That opinion, in turn, significantly lowers their desire to fix their preprocessors. Paul Mensonides
From: "Paul Mensonides" <pmenso57@comcast.net>
(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? ;)
Plenty.
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'm not exactly struggling with it. I'm simply not supporting any preprocessor that is buggy.
Yes, sorry, bad wording. The above was meant rather tounge-in-cheek. I didn't really mean that either of you are "struggling" (or being bitter, for that matter, that was a joke), only that I understand that CPP conformance has also been an issue for CPP-libraries, similar to template implementation for template metaprogramming libraries. Regards, Terje
Terje Slettebø <tslettebo@broadpark.no> 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
participants (4)
-
David Abrahams -
Paul Mensonides -
Terje Slettebø -
Vesa Karvonen