Lazy Metaprogramming Library
Lazy Metaprogramming Library ============================ Vesa Karvonen vesa_karvonen@hotmail.com 30. October 2004 This is a minimal proof-of-concept library that shows how one can implement lazy template metaprograms. Problem ------- Most contemporary template metaprogramming libraries are strict, which means that the result of a metafunction call is evaluated completely once the metafunction is invoked. Furthermore, metafunctions are written so that the arguments they receive are assumed to be completely evaluated. In addition to strictly evaluated function calls, most strict programming languages provide lazy control structures, such as `if' and `while', that evaluate their subexpressions only when needed. In contemporary template metaprogramming libraries, there usually is no clear separation between lazy control structures and strict metafunctions, which can make programming quite confusing and burdensome. Basically, a programmer using a contemporary template metaprogramming library has to explicitly annotate the evaluation order of the metacode by carefully selecting when to invoke and when not to invoke a metafunction. The invocations can not simply be completely left out, because strict metafunction do not accept uninvoked arguments. Solution -------- The metaprogramming style used in this library is different. Metafunctions and data structures (type lists) in this library are designed to be lazy. In particular, metafunctions assume that the arguments they receive are only delayed promises to compute the actual argument once explicitly invoked. This change of style eliminates the need to constantly think about evaluation order. Metafunction invocations are only needed when a value explicitly needs to be examined. For example, the metafunction `HEAD<l>' evaluates to the head of the given list `l'. In order to do that, `HEAD' needs to explicitly invoke the parameter `l' to expose the list constructor `CONS' for pattern matching. However, and most importantly, callers of `HEAD' do not need to invoke the parameter. In theory, the style used in this library could be the ideal way to implement template metaprograms, because the C++ standard almost requires template instantiations to be cached, which means that delayed promises are actually computed only once, saving CPU time. In functional programming terms, C++ implementations are almost required to perform memoization or graph reduction. In practice, however, the representation of type information may take a lot of memory and access to the instantiation cache isn't necessarily implemented efficiently. This can make lazy metaprograms less efficient in terms of time and space than their strict counterparts. Contents of the package ----------------------- The `inc/lazy_mpl' directory contains the library implementation. Only a minimal core plus a couple of higher-order functions on lists are provided. The `test' directory contains a couple of ad hoc tests demonstrating the lazy programming style and the use of lazy lists. To get most out of the code, you should take a look at the implementation of the higher-order list manipulation metafunctions `MAP', `FOLD[R|L]', `APPEND', `TAKE', `DROP', `ITERATE', `FILTER', and `ZIP_WITH'. As you can hopefully see, they are very cleanly expressed. That is how lazy metaprogramming would look like to a casually user. Future work ----------- This library is only a proof-of-concept. The intention is to show that lazy template metaprogramming is possible and can yield correct and highly readable metaprograms. The metafunctions in this library are written for clarity rather than optimized for heavy use. In particular, many of the provided metafunctions are strict in one ore more parameters, which means that those parameters are always invoked as a result of invoking the metafunction. An optimization technique called ``strictness analysis'' could be used to systematically optimize the metafunctions. The optimization would not change the way the metafunctions are used, but would change how they are evaluated internally. In some cases the optimization could be significant. Another practical issue would be to implement some sort of lambda mechanism, which would make the use of higher-order metafunctions more convenient. Copyright --------- (C) Copyright Vesa Karvonen 2004. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE.) _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.com/
From: "Vesa Karvonen" <vesa_karvonen@hotmail.com>
Lazy Metaprogramming Library
This is a minimal proof-of-concept library that shows how one can implement lazy template metaprograms.
Solution --------
The metaprogramming style used in this library is different. Metafunctions and data structures (type lists) in this library are designed to be lazy. In particular, metafunctions assume that the arguments they receive are only delayed promises to compute the actual argument once explicitly invoked. This change of style eliminates the need to constantly think about evaluation order.
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 - 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. You might want to have a look at that thread (if you haven't), and see if and how it relates to your proposal, and how your library addresses the concerns there. Your algorithms, such as: template<class l> struct SIEVE : CONS<HEAD<l>, SIEVE<FILTER<NOT_DIVISIBLE_BY<HEAD<l> >, TAIL<l> > > > {}; look similar to 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. However, factorial<> itself is lazy, and that simplifies its design. Without it, you'd either need to split it in two classes, to avoid over-eager evaluation and consequently infinite compile-time recursion, or you'd need an eval<>/lazy<> construct that takes a metafunction invocation and evaluates its arguments. One argument I used was that having metafunctions "evaluate their own arguments" follows the same way as run-time functions, which also evaluates their own arguments, so to speak, implicitly. One thing, though: Why the very non-Boost style identifiers (lower case template parameters, and upper case template names), such as: template<class t> struct QUOTE { typedef t type; }; Writing pp-code (using uppercase characters) a hard habit to break? ;) Come to think of it, the "Generative Programming" book had the same convention of upper case names for metafunctions. Regards, Terje
Vesa Karvonen wrote:
Lazy Metaprogramming Library ============================
Vesa Karvonen vesa_karvonen@hotmail.com 30. October 2004
This is awesome! I have been working on something very similar to this; looks like I'm not alone in the lazy evaluation idea. My library goes a bit farther than proof-of-concept by actually trying to use it in a real-world case. I have run into a significant problem however: the template nesting limitation. I have not yet seen a way to make Lazy TMP scale for any real problems. Say we have a list: typedef cons< A, cons< B, cons <C, nil > > > list_t; In this case, we have 3 cons cells. I can do operations on it like: typedef nth< I<1>, list_t > nth_result; When nth_result is evaulated, the resulting type will be B. typedef nth_result::eval nth_eval; // nth_eval is B But nth is a fairly trival function: #define FUN(n, _name) \ template<BOOST_PP_ENUM_PARAMS(n, typename _p) > \ struct _name { #define BEGIN typedef typename #define END ::eval eval; }; // _p0 = index // _p1 = {list} FUN(2, nth) BEGIN if_< _p1, if_< equals< _p0, I<0> >, car< _p1 >, nth< sub< L2< _p0, I<1> > >, cdr< _p1 > > >, nil > END Yes, the above code is actually C++! The magic of lazy evaulation lets us write such elegant stuff. The thing is, even with this little example, the compiler will have to slog though many many nested types (espically brutal is the car and cdr). This usually results in the compiler running out of memory pretty quickly for lists that are only 10 elements. I've looked at your approach and it looks promising, but I'm not sure it will aleviate this problem. Is there something special about inheritance that makes the compiler happier in that it doesn't eat up its memory as fast? I'm starting to think that C++ was never really meant to do this kind of thing, and therefore is a lost cause? BTW, I'm cleaning up my library for others to look at, but I can send it to you in its current state if you don't mind the mess. It works for VC7.1 and (believe it or not) EVC4. I'm sure with a bit of tweaking it will work fine on g++; the hard part was working around partial and full specializations not working right on evc4. Frank Laub
Frank Laub <fried@franklaub.com> writes:
I've looked at your approach and it looks promising, but I'm not sure it will aleviate this problem. Is there something special about inheritance that makes the compiler happier in that it doesn't eat up its memory as fast?
No, in fact, deep inheritance actually makes current EDG compilers' compile times explode (as you'll see in the performance appendix to http://www.boost-consulting.com/metaprogramming-book.html). EDG has fixed that problem, but it won't help any real users for some time to come.
I'm starting to think that C++ was never really meant to do this kind of thing
Well, that much is old news!!
and therefore is a lost cause?
Don't give up so soon ;-) -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
participants (4)
-
David Abrahams -
Frank Laub -
Terje Slettebø -
Vesa Karvonen