[boost] Re: Lazy Metaprogramming Library

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2004-11-17 08:13:51

Frank Laub:
>Vesa Karvonen wrote:
> > Lazy Metaprogramming Library
[...]
>This is awesome!

Thanks! I noticed that you replied to my original post. Have you
fetched the latest version of the library from the files section?
(See later in this message.)

>I have been working on something very similar to this; looks like I'm
>not alone in the lazy evaluation idea.

I'm not surprised. It seems that similar ideas have occured to
several people over the years.

>My library goes a bit farther than proof-of-concept by actually trying
>to use it in a real-world case.

I'm currently looking for an interesting real world problem to solve
as an example of using Lazy TMP. If you (who is reading this e-mail)
have an idea of a good example, I'm all ears!

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

Yes, nesting can be a problem. The problem can be alleviated by
using optimizations guided by techniques that are called strictness
analysis. My proof-of-concept library contains such optimizations.

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

Here is an unoptimized implementation of the same metafunction (it's
called AT) from my library. No macros are involved here.

  template<class i, class l>
  struct AT
    : HEAD<DROP<i, l> > {};

  template<class n, class l>
  struct DROP
    : IF<IS_0<n>,
         l,
         DROP<PRED<n>,
              TAIL<l> > > {};

The DROP-metafunction, in particular, can be optimized using strictness
analysis. Here is how one might do it:

  template<class n, class l>
  struct DROP
    : DROP<INT<n::value>, typename l::eval>::eval {};

  template<long n, class h, class t>
  struct DROP<INT<n>, CONS<h, t> >
    : DROP<INT<n-1>, typename t::eval>::eval {};

  template<class h, class t>
  struct DROP<ZERO, CONS<h, t> >
    : CONS<h, t> {};

  template<class n>
  struct DROP<n, NIL>
    : NIL {};

[[Actually, the above optimized implementation is slightly too
  strict. It shouldn't matter a lot in practise, though. It is
  also possible to avoid the unwarranted strictness. Can you
  spot the invalid invocation?]]

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

Yes. This issue (the buildup of complex unevaluated expressions) is
explained in detail using "equational reasoning" in the factorial
function example that you can find in the library:

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

See the file `lazy_mpl/example/example_fact.cpp'.

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

The solution is not inheritance. Inheritance doesn't necessarily
reduce memory consumption. Inheritance is only used to reduce the
notational burden. Use of inheritance eliminates the need for the
kind of macros you seem to be using.

The key to making Lazy TMP viable (or at least approximately as
viable as Strict TMP) is to optimize lazy metafunctions using
strictness analysis when necessary. This is explained to some
extent in the factorial example and used throughout the
library. (I think the technique needs further explanations.) A
library of optimized higher-order functions should make Lazy TMP
quite useful to the casual template metaprogrammer.

>I'm starting to think that C++ was never really meant to do this kind
>of thing,

Well, it wasn't. You can take it as an axiom.

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

I can wait for the revised edition. (I'm too busy at the
moment working on several other things.)

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

Been there... Novadays I have very little sympathy for broken
compilers. It has been about 6 years since the C++ standard was
ratified. I personally find it quite revealing that most compilers
still don't implement the standard. I have very little interest to
spend my life working around compiler bugs.

-Vesa Karvonen

_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE! 
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/