Re: [boost] Meta function variants of mpl::apply_if neccesary?

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-09-19 09:59:07

>From: "Iain K.Hanson" <iain.hanson_at_[hidden]>

> [mailto:boost-bounces_at_[hidden]]On Behalf Of Terje Slettebø
>
> > > I can certainly acknowledge that. In fact, I've suggested
> > > that all metafunctions evaluate their own arguments.
> > > [Addition: I see you suggest the same below here. :) ]
> > > Similar to how apply_if evaluates the selected argument,
> as you say.

>Some of the issues are discussed in the paper by Dave A and Aleksey where
>they discuss the difference between Metafunctions and MataFunction classes.

Yes. The MPL paper uses if_ and apply_if to avoid premature instantiation.
However, in many cases, as has been show with concrete examples in this
thread, that is not enough to avoid having to split a function into several
templates, or using something like the "eval" template.

>As you point out, factorial needs eager template instanciation or the
>recursion
>does not happen. Other Functions such as with if_ and apply_if you often do
>not
>want both branches fully instanciated.

What may be confusing, here, is that if_ and apply_if works differently than
the other metafunctions, as described in a posting I just sent.

Unlike the other metafunction, they may "pass through" their arguments (only
evaluating the condition). Thus, it doesn't need to instantiate both
branches, and in fact if it did, it would lead to infinite recursion, and
the factorial example wouldn't work.

In fact, the problem with the _current_ version of MPL is that it easily
leads to unconditional evaluation of parts of both branches, leading to
infinite recursion, unless you split the metafunction up.

With the current definition of MPL, an attempt at writing the factorial may
be like this:

template<class V>
struct factorial
{
  typedef typename apply_if<equal_to<Value,value<Value,0>::type>,
    value<Value,1>,
    mul<Value,factorial<prior<Value>::type>::type> // ***
  >::type type;
}

Let's examine what happens, here. On evaluating the apply_if, it, among
other things, instantiates "factorial<prior<Value>::type>::type". It has to,
as "type" is a member of factorial<...>, so in order to get the member, it
has to instantiate the factorial<...> template. Always. What does this lead
to? Infinite recursion.

The proposed solution doesn't involve instantiating both branches, on the
contrary. It involves evaluating (possibly instantiating) the arguments to
metafunctions, so that you _avoid_ a partial instantiation of both branches,
as shown above, and instead it just evaluates as much as it has to, in other
words, just one of the branches.

Thus, the proposed solution is in fact an attempt at avoiding the eager
template instantiation that typically happens in the way MPL currently
works. So it's the other way around from what you say, here.

Consider the factorial, using the proposed solution (repeated here for
convenience):

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;
}

As you can see, as it doesn't have any "::type" in the apply_if-part, it
doesn't instantiate more than needed, which means that it works correctly.
It performs recursion until the terminating condition stops it.

>mpl has chosen the least abstract
>form
>which will offer the least suprise to newcommers.

Could you elaborate on this, why you think so? It seems to me it's the other
way around. With the current MPL, you either have to split the metafunction
up into several templates, to avoid premature instantiation, or use
something like the "eva" metafunction at strategic places. However, both
these ways could well make MPL _harder_ to use, not easier, than if the
metafunctions evaluate their own arguments, and you don't have to think
about it.

Metaprogramming is hard enough as it is, and if we can leave details such as
evaluation of expressions, to the compiler, then at least we don't make it
harder. :)

This is not just theory - I've used MPL in practice, implementing
metafunctions like the above. It's typically only when you start to use it
(like Jaap, too), that you find the problems mentioned here. Such infinite
recursion tends to be furiously hard to debug, too, before you understand
what is happening.

>The downside is that as
>you
>become a more advanced user, there is more to bite you in the backside ;-)
>but then since when has that been new for C++ users!

Well, much of modern use of C++ does actually make C++ a safer language to
use. For example the "Accelerated C++" book takes this approach to teaching
it. I think that should be the case for metaprogramming, as well.

Regards,

Terje