(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.
From my experience, the world of metaprogramming is full of cases of independent discovery (myself, I started trying to generalise Loki, using
Great minds think alike, I guess. :) 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