[boost] Lazy Metaprogramming Library

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2004-10-30 14:00:26

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

                                                       Vesa Karvonen
                                           vesa_karvonen_at_[hidden]
                                                    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/