[boost] Lazy Metaprogramming Library [UPDATE]

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2004-10-31 21:55:21

Hi,

I have made some optimizations (resulting in an order of magnitude (10x)
improvement in compile-time in some cases on GNU g++) to the library
and implemented a couple of new metafunctions. The latest snapshot can
now be downloaded from the Files Section (both zip and tar.bz for your
convenience):

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

Please note that the library is only a proof-of-concept made in about 2 
days.
It should be quite possible to provide a more comprehensive library of lazy
metafunctions and provide facilities like the lambda-facility of Boost MPL.
(Also, you shouldn't worry about the upper case naming used in the library.)

Lazy template metaprogramming, as shown by the lazy metaprogramming
library, eliminates the number one stumbling block of template
metaprogramming as described by every introduction or guide to template
metaprogramming (e.g. http://www.boost.org/libs/mpl/doc/#applyif and
Generative Programming section 10.11.1.3 Taking Advantage of Lazy
Behavior (particularly pages 441-443... "You should remember this when
writing static code" ;)).

In lazy template metaprogramming, invocations (::type) are only needed
when a value needs to be explicitly examined (e.g. to extract the head
of a list). Use of the typename-keyword can be practically eliminated and
forwarding (use of inheritance) is the usual way to implement functions.

Explicit invocations can (are) also be used for optimizing lazy 
metafunctions,
but optimizations are just optimizations. There is no need to optimize 
unless
the metaprogram executes too slowly. It is likely that user metacode can
rely on optimized library primitives for the most part.

Regards,
  Vesa Karvonen

<--- README-file --->

Lazy Metaprogramming Library
============================

                                                       Vesa Karvonen
                                           vesa_karvonen_at_[hidden]

  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, the separation
  between lazy control structures and strict metafunctions is often
  quite fuzzy, 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 metafunctions do not accept
  uninvoked arguments.

Solution
--------

  The metaprogramming style used in this library is different.
  Metafunctions and metadata 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 value of the 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
  actual parameter for `HEAD'. (Explicit invocations can also be
  used for optimization, but it isn't strictly necessary.)

  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 other words, C++ implementations are almost required to
  perform memoization. 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 few higher-order functions on lists are
  provided. The list functions imitate the Haskell 98 standard
  prelude functions. 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
  unoptimized implementations 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 casual user.

Future work
-----------

  This library is only a proof-of-concept. The intention is to show
  that lazy template metaprogramming is not only possible, but can
  yield both powerful and readable metaprograms.

  One important remaining issue would be to implement a lambda
  mechanism of some sort, which would make the use of higher-order
  metafunctions more convenient.

  Another issue would be to study how to best optimize lazy
  metafunctions. Many of the metafunctions in the library have been
  manually optimized by considering which of their arguments are
  strict (always invoked) and then making the implementation take
  advantage of the strictness by invoking the arguments early. The
  optimizations do not change the way the metafunctions are used
  (assuming the optimizations are correct), but can have a
  significant effect (order of magnitude) on performance. (I have
  not proven that the manually introduced optimizations are
  correct---I wouldn't be surprised if some of the optimization were
  incorrect.) Hopefully a good selection of optimized lazy
  metafunctions can practically eliminate the need for library users
  to manually optimize their code. At any rate, optimizations are
  only needed when a metaprogram evaluates too slowly.

Copyright
---------

  (C) Copyright Vesa Karvonen 2004.

  Distributed under the Boost Software License, Version 1.0.
  (See accompanying file LICENSE.)

_________________________________________________________________
Don't just search. Find. Check out the new MSN Search! 
http://search.msn.com/