Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-10 08:24:07

>From: "Andrei Alexandrescu" <andrewalex_at_[hidden]>

> "Terje Slettebø" <tslettebo_at_[hidden]> wrote in message
> news:0b8101c23fe6$5a6bfe10$60fb5dd5_at_pc...
> > Ease of understanding is also dependent on what you are used to. It's
not
> as
> > if Loki was easy to read, once I started to learn about that, either. A
> more
> > fruitful path might be if someone are reasonably fluent in both kinds of
> > libraries, to read and write code for various tasks, and see what was
> found
> > more readable.
> >
> > I have learned to read Loki's typelist code. Still, I find, when writing
> new
> > algorithms for it, that you tend to get lot of different
specialisations,
> > that tend to, well, specialise the code. :) That is, you get a specific
> > solution to something, that may not generalise well. Also, the code
tends
> to
> > be spread out, like this, which I think may make it harder to read, than
> if
> > it was in one place.
>
> That's a good argument. However, it should be noted that all you really
have
> to absorb to start using Loki's typelists is this:
>
> template <class H, class T>
> struct Typelist
> {
>     typedef H Head;
>     typedef T Tail;
> };

I know.

I've used this myself, in my programs, generating classes and hierarchies,
removing lot of source-code duplication that way, just by using this
template, and the creation macros for convenience.

> Then, you can naturally use C++'s template engine, which supposedly you
> already know, to work for you. That's why I'm saying that the
dot-typelists
> are closest to the way C++'s metaprogramming facilities work.
Dot-typelists
> have a complexity/benefits ratio that's, in my opinion, unbeatable.

It's not just about dot-typelists. By the way, wouldn't perhaps something
like cons-lists (or simply lists) be a more appropriate term? From what I
understand, in FP, dot-lists refer to lists that are _not_ terminated by
nil, such as the NullType counterpart in Loki. According to that definition,
e.g. Loki's typelists are not dot-typelists. Or did I miss something?

Anyway, I assume you mean lists using the typelist template above here,
terminated by NullType.

Well, such lists exist in MPL, too. So what I said above here, in the
previous posting, was not really the structure of the containers, but rather
how you organize the code. Let's take a concrete example, since you've asked
about that. :) I think that's fair, too, and may make the discussion more
concrete.

Take one of the simplest algorithms, factorial. The algorithm is like this
(to have something to compare to):

template<class Value>
Value factorial(Value value)
{
  if(value==0)
    return 1;
  else
    return value*factorial(value-1);
}

Using MPL, you might write it like as follows. Explanation for the apparent
increase in complexity, follows below here. It is to get the same generic
quality as the run-time version.

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<prev<Value> > >
  >::type type;
}

That's it, 9 lines of code (7 without braces), one template, two typedefs,
done. :)

The computation is actually a one-liner, but the typedef is spread out, for
readability.

Actually, the function above uses some components and properties not found
in MPL, but which might be included.

Don't be distracted by the number of metafunctions used in it. That's what
gives it its power, its genericity.

It could have been written simpler, using "*", "-", etc., if you assumed the
value passed in was int, or int_c, or something like that. However, with the
above form, it may be used to compute the factorial of any value type, such
as integral_c, fixed_c and rational_c.

For example, if you create a new value type, like double_prec, you can use
it in the above function, unchanged. :)

Just to explain the above a little. "value" is invented by yours truly, :)
so don't be surprised if you don't recognize it from MPL. It creates a new
value, based on the type passed in. So if T=int_c<...>, then
"value<T,N>::type" creates int_c<N>. It's a way to create generic constants,
without having to know the type passed in.

This uses the same "rebind" method used in MPL, and with the help of Mat
Marcus, I've got this to work on MSVC 6, too. The "T::template apply<N>"
syntax gave an ICE without it.

The absence of "::type" in the factorial function, is another change to MPL.
The above function assumes that the metafunctions evaluate their own
arguments (apply "::type" to them). This is what the first typedef does for
the factorial function, too.

Enough of that version. Let's look at the typical way it might be done using
template specialisations. Feel free to make another version, here, Andrei.
After all, this is your part of the argument. :)

Let's make one that works on int, only, first. Then we'll try to expand it.
("try" being the operating word, here. :) ).

template<int N>
struct factorial
{
  static const int value=N*factorial<N-1>::value;
};

template<>
struct factorial<0>
{
  static const int value=1;
};

Nice and small. Two lines of computation, which is the case for the function
above, too. 10 lines of code (6 without braces), one template, with one
specialisation, and two static consts.

It's comparable in complexity to the MPL version (at least if you know MPL,
as well as C++. :) ). However, here the code is spread into two template
definitions: the primary template, and the specialisation.

For such a simple function, it's only one specialisation. However, for more
complex functions, you may end up with a lot of specialisations, and
external helper-templates, to do the computation. This spreads out the code,
and may make it hard to understand.

But it doesn't stop there. Let's try to extend the above function to handle
other value types, as well. You may change it to be able to handle any type
that has a "value" member (that includes integral_c and int_c):

Quite frankly, I have problems seeing how this could be done, without
something like the value<> template in the first function. Even if you do
that, unless you change the "*" and "-" to metafunctions, this won't work
for other value types, such as rational_c, which has the "numerator" and
"denominator" members.

At this point, you'd likely get problems with the total specialisation,
above here, as this can only detect _one_ kind of terminating value. Even
changing it to a partial specialisation won't help. Unless you find some
other way, it appears to me that you can't make a generic function this way.

Remember this is a very simple function. Consider if you were to write a
larger system with this.

When it comes to the request of showing how MPL may solve a real-life
problem, I think it's pertinent to mention that larger programs typically
consist of smaller parts. Therefore, unless you get the smaller parts to
work, the larger program won't work, either.

> In contrast, MPL puts a whole wrapper over what the compiler really does,
in
> an attempt, which in my opinion is only partially successful, to emulate
> STL's design.
>
> > Having learned MPL, as well, I disagree with that it should be harder to
> > learn, harder to use, and the client code harder to understand, than a
> > library like Loki's typelists. It may well be the other way around.
> >
> > Like I said, I think it has much to do with what you're familiar with.
>
> That doesn't, in and of itself, really say anything. Of course what's most
> familar is also easiest. I think that a newcomer, however, can be
> comfortable very soon with using dot-typelists than with an extremely
> complicated incomplete compile-time emulation of the STL.

I think it would be better to ask newcomers that. :) I don't think that is
given. As mentioned, it may well be the other way around.

Similar arguments have been used to argue for teaching C++ the C-first way,
as the standard library and STL was considered "advanced". When the truth is
that if you teach C++ as a high-level language, starting very early with the
standard library and STL, people tend to find it easier to learn good
programming that way, than having to suffer through low-level C, first.

I think it may be similar with MPL. It provides an additional abstraction,
so you don't have to write the explicit specialisations, etc., but can write
code in something that may be more familar, resembling run-time code.

> > > MPL has been out for a while and there still aren't examples that
> justify
> > > the presence of multiple containers, even from its own authors. I
> > > understand that MPL uses STL's design, and many say this is a
hallmark,
> > but that's
> > > not an argument by itself. As said in another post, they use very
> > different
> > > means and have very different ends. It's art for the sake of the art
if
> > it's
> > > not useful.
> >
> > I think the means and ends are similar.
> >
> > It's not clear to me what the differences would be, could you point me
to
> > the posting you refer to, or elaborate?
>
> I was referring to my post that emphasizes (1) that templates offer a
> different computational model than C++'s runtime virtual machine;

True.

> (2) that
> we use C++ compile-time programming for different tasks than C++ run-time
> programming.

That one depends.

I think it may be an advantage to have compile-time and run-time programming
that resembles each other. That way, the transition from one to the other
may be smoother. After all, fundamentally, the difference between
compile-time and run-time is binding time.

It's not functional programming versus imperative programming. That is about
how it's implemented, and you may use both ways, at both compile-time and
run-time.

> Two details: when I say "virtual machine" I mean it in the sense that
every
> language describes a virtual machine that executes programs written in it.

I know. It's the "virtual machine" that is specified in the C++ standard.
That is, a specification of the excution environment.

> I felt compelled to precise this because the term "virtual machine" has
been
> recently used in conjunction with Java's JVM. The other detail is that I
> intentionally mentioned "C++" - as opposed to other languages (such azs
> LISP), where compile-time and run-time programming are really hard to
> distinguish.

This is what I think libraries like MPL can give something similar to, for
C++.

As you know, Todd Veldhuizen refers to such a language, with more or less
the same support for compile-time and run-time programming, as a "two-level
language".

> Truly LISP's macros are sometimes of amazing power exactly
> because they use (almost) the same mechanisms as LISP's runtime virtual
> machine. In passing being said, macros are also one of the reasons for
which
> LISP programs are impenetrable but to a handful of gurus.
>
> My opinion is that C++ will never be there, simply because its template
> engine is very different, and much more scarce, than its runtime
> counterpart. That's why MPL seems to me like an interpreter written in awk
> or advanced threading in Visual Basic: wow, look, it can be done, how
> quaint - but man, you just get that feeling that the tool is totally
> inappropriate for the job. That's why I also wouldn't be keen of
> manipulating collections of 10,000 types at compile time in C++.

Well, as I understamd, MPL is being used in real-life. Dave Abrahams has
mentioned using it, for example.

However, this has also to do with the nature of metaprogramming, not MPL in
itself. In C++, metaprogramming is quite new, so the field may not be that
known.

> > Even if metaprogramming is implemented as functional programming, the
> > implementation shouldn't decide what are, or are not, useful
abstractions.
> > If that was the case, then we'd use assembly code, because after all,
> that's
> > how it's implemented.
>
> I don't understand how the above applies to the discussion.

I meant that even though templates work as functional programming, that
alone shouldn't mean that they can't be used to model things not possible in
FP, such as mutability. After all, an algorithm like Loki's Remove doesn't
remove anything from an existing typelist - it creates a new one. The same
is done in MPL.

> Anyhow, to me in the present the situation looks like this.
>
> It's been months. I've been glad to see that people realized that using
the
> "STL is cool and MPL is like STL, therefore MPL is cool" argument has some
> subtle circularity. The most fervent MPL sustainers couldn't come with a
> compelling example that justifies MPL's design. MPL's *author* couldn't
come
> with a compelling example that justifies MPL's design. So far opionios
seem
> to be (1) MPL is the library of 2050 arrived on today's laptops, and it
will
> be a matter of time until its vision will be fully understood and
> appreciated (2) it sounds like a really cool intellectual achievement (3)
"I
> don't know much so I won't say anything" and (4) a vocal minority, of
which
> I am part, who questions some of MPL's design decisions.

Perhaps my simple example above can shed some light on this.

Regards,

Terje