Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-13 07:52:36

>From: "Paul Mensonides" <pmenso57_at_[hidden]>

> > Are you saying that you think it would be better with only FP constructs
in
> > MPL? That would mean no iterators (I guess), and it might mean that you
> > loose the familiarity from run-time programming. It would mean a large
> > change, when going from one to the other. This is just what MPL tries to
> > avoid, by instead presenting familiar constructs. This way, the
transition
> > may be smoother. This was also a point in the "Static Data Structures"
paper
> > that Doug mentioned.
>
> My only real disagreement with the MPL is the abstraction caused by the
> assumption of more than one sequence type being necessary.

Ok. Then we have sorted that out.

> As for the
> functional environment, C++ template metaprogramming *is* a function
> environment, therefore the most natural use of it is functional.  I don't
have a
> significant problem with the simulation of iterative constructs (i.e.
> imperatives), but it is still simulation, and the primary use IMO should
be
> functional.  It is C++ programmers job to understand the environment in
which
> they work, not the other way around.

Well, as mentioned, one of the primary algorithms used in MPL is, not
surprisingly, a functional one, iter_fold.

> >> > to the use of multiple sequence types?  IMO, the correlation to the
STL
> >> breaks down at this point.
> >>
> >> Sequences is just one thing. Combination of metafunctions, lambda (not
> found
> >> it STL, but found in Boost.Lambda), etc. are also similar.
>
> >The STL analogy applies specifically to sequences.
>
> > Well, look deeper: "plus", "minus", "multiplies", "divides", function
> > composition, etc. All parts of STL, as well. MPL resembles STL + BLL.
>
> These things I am not disagreeing with.  Just the assumption that more
than one
> sequence type is necessary <period>.  The STL uses the above primary in
the
> service of sequence abstraction.  That is what I meant, but that is not
what I'm
> disagreeing with.  For example, with your compile-time exponentiation
> metafunction

By the way, sorry for the confusion, here. I've called it "pow" (power) in
postings here, too, when I meant "factorial". It was a factorial example
that I posted to the list. The pow example is something we've discussed in
mail.

It's an exponential function, yes, but as std::pow works the same way, I
called it that. std::exp works differently (e^x), although it may be
considered a special case of it.

In case you didn't see the "factorial" example (I see that you say that in a
reply to David B. Held), it's in my first reply to Andrei.

Since the "pow" example has already been mentioned, here it is:

template<typename B,typename E>
struct pow
{
  // Evaluate the arguments. Might also use e.g. BOOST_MPL_EVAL(B,Base) for
these.

  typedef typename B::type Base;
  typedef typename E::type Exp;

    typedef typename if_<
        equal_to<Exp,value<Exp,0> >,
        value<Base,1>,
        multiplies<
            Base,
            pow<Base,prior<Exp> >
        >
    >::type type;
};

While I'm at fixing up stuff, here's some more errata:

- "factorial" could have used if_ (rather than apply_if), but it doesn't
make much difference, anyway. In this case, it would have returned a "lazy"
result, which had to be evaluated to be used. However, with this system,
since functions are required to do that, that would be ok. :)

- I used prev<>, rather than prior<>, which is the correct one. There's no
prev<>, I confused it with the "prev" and "next" members for bidirectional
iterators. Curiously enough, there are "prior" and "next" functions that
perform similar operations, but then it's called "prior", not "prev".

- And finally, I referred to Loki's Remove at one place, when there's no
such function. Well, there is, but not in Loki. :) There's some extensions
for Loki, here (http://sourceforge.net/projects/loki-exp), in the "answers"
branch of the CVS, including a Remove function (which removes a range from a
typelist), so I guess I thought of that. Loki's Erase could be used in the
example, instead.

> I think that having the arithmetic functions "evaluate" the
> arguments themselves is a good idea, and I have no disagreement with its
> design--other than it doesn't apply well to half compile-time arguments
and half
> runtime arguments. (see "Generative Programming" - Czarnecki &
Eisenecker).

Right. Well, you could also use some kind of detection, for this. When we
discussed this issue in mail, you sent me a metafunction that could detect a
"type" type member, which might then be used to select whether or not to
evaluate the arguments. Another way could be to use traits.

We get to that in another posting I send a reply to now, as well, as I'm
wondering if this wouldn't mean that you had to write it as a run-time
algorithm, anyway.

Richard Crossley (also at modern-cpp
(http://www.accu.org/moderncpp/public/), which loki-exp above here is part
of) pointed out some possible problems with mandatory evaluation of the
arguments, such as using the type traits. For example, should
is_fundamental<> also perform T::type its arguments? It would mean that, to
test for types without a "type" member, you'd need to wrap it in identity<>.
Or, you might use the above methods, to select whether or not to evaluate
the arguments.

One great advantage with the functions evaluating their arguments, is to
avoid having to split the code up, to not get premature instantiation (and
also to get rid of all those "::type" in the code. :) ). Without it, both
the "factorial" and "pow" examples might need to be split up, into using an
additional template, to avoid infinite recursion due to both branches of the
if_ being instantiated, rather than just one.

> >I don't mean that the MPL
> >has stuff that the STL doesn't or vice-versa.  I mean that the
fundamental
> >premise of the STL analogy is flawed with regard to sequences because the
> actual
> >reasons for that abstraction in the STL do not apply to template
> >metaprogramming.  The only thing that you really get out of it is
syntactic
> >sugar and limited similarity to STL code--which is not nearly as strong
of
> an
> >argument as you tend to make it (IMHO). :)
>
> > This had nothing to do with sequences at all, and that was deliberate.
> > Instead, it showed the power of abstraction in MPL, which lets you use
the
> > same algorithm for any type that satisfies the concepts. This is
_precisely_
> > the same way it is in STL.
> >
> > I suggest you look again.
>
> How many times to I have to reiterate this?  I _do not disagree_ with many
of
> the abstractions in the MPL.  I disagree with the supposed need of
multiple
> sequence types.

The reason I (and others, as I see from the thread) wondered, is that you in
the same posting said:

>The STL analogy applies specifically to sequences.

and in another:

>I think that many people are infatuated with
>the analogy to the STL and are thinking that this analogy will prove itself
down
>the road (instead of now).

However, it's now clear, from this and other postings, that it's the
sequence analogy to STL that you question.

> > I understand you here talk about sequences, specifically, and not MPL in
> > general. Where have I made this as such a big point, you say? I, and
others,
> > have said that the decoupling of sequences from algorithms may be useful
in
> > itself. In what way have I "tended to make this a strong argument"? I've
> > said that measurements could give us more info about this. And that's
> > something we have got now. I don't recognize my postings in what you
say,
> > here.
>
> You have repeatedly said that similarity to runtime code was a great
benefit.

Yes, and so have you. However, that was not specifically regarding
sequences. Indeed, the interface for MPL's sequence functions is different
to STL, taking a sequence, rather than a couple of iterators.

> Yes, many people have said the decoupling sequences and algorithms may be
> useful, but *no one has proven it* or shown an such example.  Even your
timing
> examples only proved what I have already been saying.

Examples have been given, such as generators. However, we get back to this
in other postings that I send now, so we can take the discussion there. I
have a few postings to catch up to. :)

Regards,

Terje