[boost] Re: Lazy Metaprogramming Library

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2004-11-17 00:23:01

Terje Slettebø:
[...]
>From my experience, the world of metaprogramming is full of cases of
>independent discovery [...]

...or rediscovery of things that the functional programming
community has known or had for a long time. Of course, there is
absolutely nothing wrong with that. Unfortunately, functional
programming still isn't something that would, for instance, be
taught to all computer science / software engineering students. For
instance, there is no compulsory course at the CS department of the
University of Helsinki that would introduce functional programming.
This is a shame, in *my* opinion.

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

Yes. It is always a good idea to really seek to understand the
issues rather than take a statement as true. However, I'm not
really surprised that it took quite a bit of time to discover Lazy
TMP (lazy template metaprogramming). (And the case for Lazy TMP is
still open, of course.) The concepts of lazy evaluation and purely
functional programming are not the kind of concepts one normally
thinks about when programming in C++.

>By the way, Aleksey has also mentioned that the functional influence on MPL
>is much inspired by you.

If Aleksey has said that, then I'll take it as a compliment. I
think that Aleksey has designed an impressive metaprogramming
library. I must say, however, that if I hadn't been talking about
functional programming a few years ago, then others would
have.

> > 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.
[...]
>It seems your search is similar to what lead you to your Order PP-library.
>:) (You also mention this later in the mail)

Search, yes. Although I didn't mention the Order metalanguage for C
preprocessor in my previous mail. (The documentation of Order is
still unfinished, which is the reason I'm not drawing more attention
towards it.)

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

Yes, indeed. When I started working on the proof-of-concept library,
I didn't immediately realize that one could, in principle, eliminate
all but just the invocations that are eplicitly needed. I also
didn't immediate understand that (with the aid of BOX<>) essentially
all metafunctions could use inheritance (or metafunction forwarding).
Although the idea of (systematically) Lazy TMP is simple (IMO),
the process of getting to the idea was not straightforward. All
the early articles and books (I've seen) on template metaprogramming
essentially used Strict TMP.

>I didn't pursue this further at the time, as it would require a
>fundamental change [...] (unless one made one's own [...] proof
>of concept, as you've done).

I find it imperative to try out new ideas by implementing them in a
smaller scale. Quite often it takes a lot of experimentation to
reach the simplest solution. [I'm rarely truly satisfied with any of
my own code.]

> >   template<class n> struct FACT [...]
> >   template<long n>  struct FACT<INT<n> > [...]
> >   template<>        struct FACT<INT<0> > [...]
>
>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 use of pattern matching (or specializations) isn't really
fundamental to Lazy TMP. In other words, Lazy TMP is orthogonal to
the use of pattern matching or nested value/type definitions. I'm
using pattern matching in the proof-of-library, because it can
sometimes make things easier (to implement and understand).

For example, the factorial function could be written like this:

template<class n>
struct FACT
  : INT<STRICT_FACT<n::value>::value> {};

Above, STRICT_FACT-would be a straightforward Strict TMP
implementation of the factorial function.

Also, the lazy CONS<>-constructor could be defined like this:

  template<class h, class t>
  struct CONS {
    typedef CONS<h,t> eval;
    typedef h head_type;
    typedef t tail_type;
  };

And lazy algorithms on lists would use the nested head_type and
tail_type definitions instead of pattern matching.

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

Good!

>Just when I thought I had grokked metaprogramming. ;)

As Dave already pointed out, this has more to do with functional
programming in general than template metaprogramming in particular.
Issues like this are often explained (at some level) in books that
introduce functional programming (particularly lazy functional
programming).

One interesting source for relevant information would be books and
articles on programming language semantics. Here is one book I've
read recently:

  http://www.cis.ksu.edu/~schmidt/text/densem.html

The book doesn't discuss lazy functional programming at length, but
it does discuss issues that relate to strictness.

> >   struct INFINITE_LIST_OF_ONES
> >     : APPEND<LIST<ONE>,
> >              INFINITE_LIST_OF_ONES> {};
[...]
> > 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...)

One could say so. What would essentially happen is that

  APPEND<LIST<ONE>, INFINITE_LIST_OF_ONES>

would be defined in terms of

  APPEND<LIST<ONE>, INFINITE_LIST_OF_ONES>

which doesn't work, because it isn't defined yet. One runtime
analogy would be something like

  T x = x;

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

Let's just say that I find the current situation unsatisfactory and
the only party that (IMO) really has the power to make things better
is the compiler vendors.

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

As Paul already replied, both Paul's Chaos library and my Order
metalanguage have been developed only with/for conforming (enough)
preprocessors so there has been no need to struggle with workarounds
--- a most liberating feeling I should say.

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

Well, I kind of hope so---it would at least open the door for new
possibilities in C and C++ programming---but I think that it is
unlikely to happen in the short term. Also, I'm not sure what the
best course of action would be in the *long* term (say 20 years from
now).

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

There are some similarities, yes, but it is important to distinguish
between the separate concepts. The Strict TMP identity-metafunction
is considerably different from the BOX<> of Lazy TMP. In particular,

  identity<T>::type == T

but

  BOX<T>::eval == BOX<T>

In other words, a BOX<T> evaluates to itself (BOX<T> is idempotent).

This is perhaps a bit confusing due to the fact that in Strict TMP
there is no concept of "evaluation" distinct from accessing a nested
type. In Lazy TMP, the boxed type can be accessed using an
invocation:

  BOX<T>::type == T

Of course, one can also implement an IDENTITY function in Lazy TMP.
It would obey the equations:

  IDENTITY<T>::eval == T

  IDENTITY<BOX<T> >::eval == BOX<T>

  IDENTITY<BOX<T> >::type == T

-Vesa Karvonen

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