[Boost-users] Re: C++ Template Metaprogramming - factorial example

From: Brad Austin (artax_at_[hidden])
Date: 2005-01-24 03:48:25

I wrote:
> I recently purchased David Abrahams' and Aleksey Gurtovoy's new book
> on the MPL, "C++ Template Metaprogramming" (obviously recently since
> it's only been out a couple of weeks), and am working through some of
> the examples.  I'm having trouble with the factorial example in section
> 8.3.1, page 160:
>
>     #include <boost/mpl/int.hpp>
>     #include <boost/mpl/multiplies.hpp>
>     #include <boost/mpl/equal.hpp>
>     #include <boost/mpl/eval_if.hpp>
>     #include <boost/mpl/prior.hpp>
>     #include <boost/static_assert.hpp>
>
>     namespace mpl = boost::mpl;
>
>     template <class N>
>     struct factorial
>       : mpl::eval_if<
>             mpl::equal_to<N,mpl::int_<0> >  // check N == 0
>           , mpl::int_<1>                    // 0! == 1
>           , mpl::multiplies<                // N! == N * (N-1)!
>                 N
>               , factorial<typename mpl::prior<N>::type>
>             >
>         >
>     {
>         BOOST_STATIC_ASSERT(N::value >= 0); // for nonnegative N
>     };
>
> There's a minor issue in that equal.hpp is (apparently) mistakenly
> included instead of equal_to.hpp, but even after fixing that, I can't
> get this to compile in the form in which it's written.  Should it, or
> is it broken?

After spending some more time on this I now believe the code is broken.
There's some uncertainty because mpl::multiplies<> has apparently been
either renamed or replaced with mpl::times<>, and only the latter is
documented in the MPL Reference Manual, so I'm not certain whether or
not the two behave identically.  However changing "multiplies" to
"times" didn't seem to make any difference in terms of the compilation
errors, so in the analysis that follows I'm making the assumption that
if there is any difference, it isn't doesn't change anything relevant
to the problem at hand.

According to the MPL Reference Manual, in an expression of the form
mpl::times<T1,T2>, T1 and T2 must meet the requirements of an integral
constant, not merely the weaker requirements of a nullary metafunction.
In this case T2 is an expression of the form factorial<T3>, so for this
to be vaild factorial<> must model an integral constant, not merely a
metafunction *returning* an integral constant.  However factorial<>
derives from an expression of the form mpl::eval_if<T4,T5,T6>, and
doesn't add any nested types or a value of its own.  Therefore
factorial<> only models an integral constant if mpl::eval_if<T4,T5,T6>
does, which it doesn't.  mpl::eval_if<T4,T5,T6>::type models an integral
constant (provided T5:type and T6::type do), but mpl::eval_if<T4,T5,T6>
is merely a metafunction returning that constant.

Also, the first argument to eval_if is supposed to be an integral
constant, and T4 is an expression of the form mpl::equal_to<T7,T8>,
which again is just a nullary function, not an integral constant.  So
technically this would appear to be wrong, even though eval_if doesn't
seem to mind in this case.

FWIW, here's the final version of factorial<> I came up with.  This
version models an integral constant, and accepts for its argument either
an integral constant or a nullary metafunction returning an integral
constant:

    template <class N>
    struct factorial
      : mpl::if_<
            typename mpl::equal_to< typename N::type, mpl::int_<0> >::type,
            mpl::int_<1>,
            mpl::times<
                typename N::type
              , factorial< typename mpl::prior<typename N::type>::type >
            >
        >::type::type
    {};

Anyway, is this mailing list an appropriate place to bring up issues like
this?  I know David and Aleksey are members, but I'm not clear on whether
their book qualifies as an official Boost product.