Re: [boost] Issues in call_traits, arithmetic_traits and MPL

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-06-04 08:24:55

----- Original Message -----
From: "Aleksey Gurtovoy" <alexy_at_[hidden]>
> Vesa Karvonen wrote:
[...]
> 'boost::mpl' library is indeed immature (and it's not an official boost
> library yet), but I wouldn't say that about the rest.

Ok. Has it been used outside the test code?

I highly recommend implementing some more interesting metastuff than
tests. While you are at it, concentrate on reducing the amount of explicit
typenames and templates. Also concentrate on removing as many temporary
types and values as much as possible. Almost all typenames and temporaries
can be removed with suitable metaprogramming facilities. This can make the
code more robust and easier to understand.

For example, the following technique can be used for eliminating
::template from most of the code:

    template<class metafun, class arg>
    struct call_1
    {
        typedef typename
          metafun::template code<arg>::type
            type;
    };

This way the MSVC++ workaround doesn't have to be inserted everywhere.

> > call_traits
> > ===========
> >
> > The call_traits<> is basically a mini-BLOB (antipattern).
> > Specifically the call_traits<> template is four functions in one.
[snip]
> How all this relates to 'call_traits<>'? Well, my point is that the fact
> that number of "functions" in traits class > 1 does not per se identify
a
> Blob antipattern (BTW, if you're wondering what Blob is about, here is a
> link - http://www.antipatterns.com/briefing/tsld024.htm).

I agree that there probably is a better matching antipattern or code smell
that describes this situation. This is the reason why I called it
"mini-BLOB". Nevertheless, the BLOB actually fits this situation in
certain respects:

"Symptoms:
[...]
- Single class with many attributes & operations

Consequences
- Lost OO advantage
- Too complex to reuse or test.
- Expensive to load"

The consequences are arguable, although since call_traits is much smaller
than typical Blobs, the consequences are not as severe. I've seen many
similar template metasystems that are much more closer to Blob than this.
I recall seeing some type traits code from some HUT (Helsinki University
of Technology) guy that could accurately be described as a Blob. Also I
would characterize the type traits in MC++D as a Blob.

> There are both technical and conceptual reasons why one would like to
> bind several traits together in one class (after all, they are closely
> related "functions",
> right?);

I agree that conceptual binding is often desirable. However, I disagree
that the services of call_traits<> would be specific to functions. I see
many usage contexts for value_type, reference and const_reference that
have as little to do with functions as is possible in a programming
language.

> basically, given the above 'iterator_traits<>' example, I think
> that the decision "to split or not to split" should be heavily
influenced
> by:
>
> 1) the most often encountered usage patterns (how often these traits are
> used together);

At least the param_type is often used without the other types. Because the
services of call_traits<> can and often are used by different clients,
then straight-forward application of ISP (Interface Segregation Principle)
suggests that the default should be to split the services into individual
classes.

> 2) fact of (not) having a common for all traits implementation's
variability
> point; clearly, in case of 'iterator_traits<>' such point exists ('T'
vs.
> 'T*' and 'T const*') and this is what makes splitting them into separate
> classes unfeasible; I believe that this applies to 'call_traits<>' as
well.

What do you mean by unfeasible? It is quite feasible to implement the
services of call_traits<> as separate classes. I will provide a sample
implementation in the near future. I promise that the compile-time
overhead of the sample implementation will be significantly smaller
(an order of magnitude) than the current Boost call_traits.

> So although I am not completely sure about (1) in application to
> 'call_traits<>', IMO the issue is not so black & white, and personally I
> tend to think that the current 'call_traits' approach is ok.

I agree that call_traits works, but it does not offer the same flexibility
and scaleability as a set of primitive metafunctions would offer.

> > It is preferable to have simple primitive template
> > metafunctions, because:
> >
> > 1. Such metafunctions can be made to use standard interfaces
> > rather than
> > the special case interface of call_traits.
>
> I am not sure I understand this one. Could you elaborate, please?

With a standard interface, I mean that a metafunction that returns a type
always contains a type of a strandardized name. For example:

    type_if<c,T,E>   ::type
    param_type<T>    ::type
    make_typelist<T> ::type

The standard interface is the "::type". This kind of standardization
eliminates the glue that is otherwise necessary to flexibly compose stuff
out of metafunctions.

For example, it is possible to make an extension of type_if<c,T,E> called
type_inner_if<c,T,E> that returns type_if<c,T,E>::type::type directly.
type_inner_if<> is clearly more robust on current compilers than
type_if<>::type::type. type_inner_if<> can also be used to eliminate many
typenames.

The delayed metafunction call is often necessary to avoid instantiation of
templates in metacode.

> > 2. Primitive metafunctions are easier to use, understand and
> > port (fact of
> > life). For instance, should one little thing fail to compile in call
> > traits, you might not be able to port the whole thing.
>
> Depends on (2) from the above list.

It is logically, practically and provably easier to port something that is
only one quarter of a particular system. It may be a little bit more work
to port each of the 4 functions, but the same porting technique usually,
but not necessarily always works.

For example, the param_type<> metafunction is in practice much easier to
port than the other call_traits<T> services. The reason for this is that
param_type<> never removes any qualifiers from T.

As what comes to useability and understandability, then it should be
sufficient to point out that they are closely related. It is much easier
to understand a metafunction such as param_type<> than call_traits<>. Due
to the standard interface, param_type<> can also be combined with other
metacode without glue, which clearly makes it arguably easier to use.

> > 3. Primitive metafunctions scale better in large scale
> > development (with a
> > BLOB you need to include everything whether or not you need
> > it). (In fact,
> > currently I only need param_type.)
>
> True, but it's not obvious that 'call_traits<>' is an example of Blob.

Including <boost/call_traits.hpp> increased my current compiling time by a
factor of about 2 (from 1 to 2.8 seconds). However, at this point my code
is not complete, so the hit is likely to become less significant (for a
single test).

For the nearly trivial services of param_type, I find an additional 1.8
seconds of compile time unacceptable. 1.8 seconds of distributed
compile-time fat can easily mean several minutes of additional
compile-time for projects that our company currently develops. We've been
previously burned by long compile-times (on the order of an hour). It has
taken considerable engineering effort to systematically reduce compile
times. In the light of past experiences, I have absolutely no desire to
write library code that has unnecessary dependencies that can easily be
eliminated.

> [snip]
>
> > The above metafunctions are clearly superior to use in
> > metacode than the
> > call_traits<> template. I can provide examples if you don't trust me.
>
> Of course we do trust each other experience. But examples are almost
never
> superfluous as they help other people to develop their own understanding
of
> the issues.

Like said earlier, the standardized interface eliminates the glue that is
otherwise necessary. This is especially handy in conditional metacode,
where you want to avoid template instantiation. For example:

    typedef typename
      type_inner_if
      < condition
      , param_type<T>
      , some_template_that_should_not_be_instantiated<T>
      >::type type;

In this particular case, the following code would be invalid:

    typedef typename
      type_if
      < condition
      , typename param_type<T>::type
      , typename some_template_that_should_not_be_instantiated<T>::type
      >::type type;

However, I wrote it so that you can see how the type_inner_if<> can be
used to eliminate a lot of template clutter (typename XXX::type).

> > arithmetic_traits
> > =================
> >
> > The boost/arithmetic_traits.hpp can be simplified by a factor of ~4.
[snip]
> Yes, comparing the amount of code required to implement the same
> functionality, something like that is clearly superior to "traditional"
> approach. But on the other hand, implementing something as simple as
> 'is_arithmetic' class template using type_lists & co. would impose a
> _huge_ compilation time penalty on the library users, at least given
> the current state of compiler technology,

Actually, I find that in most cases, the limiting factor in compile-time
is preprocessing-time. It is easy to prove that compile time is at least
linearly proportional to the amount of preprocessed source code. It is
sometimes possible to reduce preprocessing time by using precompiled
headers, but it doesn't always work (especially when you make
modifications frequently) and it is always compiler dependent. Automatic
precompiled header generation in MSVC actually often increases compile
times (yes, we've actually measured this) and can generate hundreds of
megabytes of files.

> as well as some of other
> undesirable effects we were trying to avoid (see
> http://groups.yahoo.com/group/boost/message/7813, for example).

Yes, I agree that unnecessary template recursion can have adverse effects.
However, it is not necessary to use typelists to avoid the 4x repetition
in this case. The key is to add the const and volatile qualifiers to the
type before performing the test. The code adding the qualifiers does not
have to be deeply recursive. I will provide a sample implementation in
the near future.

> > MPL
> > ===
> >
> > Technical Issues in Boost MPL:
> > - The current code is not completely ported to MSVC++, so I
> > can not use it.
>
> It wasn't ported, it was _written_ using MSVC :) (well, actually, using
> all the following: MSVC6.4, Comeau 4.2.44 and Metrowerks 6.1). All the
> tests compile fine on my machine (you need to specify something like
> /Zm1000 in MSVC's project settings, though). Could you give a specific
> description of the problems you are having?

The ::template syntax causes a lot of problems.

> > - The factory template uses O(N*N) tokens, which is not optimal. It is
> > possible to do with only O(N) tokens, which can significantly reduce
> > compilation times.
>
> I am not sure I understand. Could you give an example?

The code in mpl/list/factory.hpp:

    #define BOOST_MPL_LIST_FACTORY_SPEC(N)    \
     [...]                                    \
      BOOST_MPL_ENUMERATE_PARAMS(typename T)> \
     [...]                                    \
    BOOST_MPL_REPEAT_N(N , >::type)           \
     [...]

    BOOST_MPL_ENUMERATE_USER_MACROS(BOOST_MPL_, LIST_FACTORY_SPEC)

Generates O(N*N) tokens. If I understand the purpose of the code
correctly, it is used for generating lists.

It is possible to support convenient creation of typelists upto size N
using the optimal O(N) tokens.

> > - What is the purpose of the SequenceCategory and TraitsType template
> > parameters of list_node? I find that those complicate the
> > implementation significantly with little or no benefit over pure, cons
> > based, proper typelists. Can you give a concrete examples that would
> > demonstrate the superiority of the MPL technique?
>
> I think I can, but that's a topic for another email. I'll try to do it
> tomorrow (it's kind of late here now :).

I think that there is very little need for value lists, because you can
use a value wrapper type:

    template<int i>
    struct value_identity
    {
      enum {value = i};
    };

with pure typelists (holds only types). I've not had any problems with the
approach.

I also think that a simulated iterator approach is more like a hindrance
rather than a help. In pure functional programming, such as the C++
templates enable, the cons-interface:

    cons::type
    cons::next

is extremely robust and flexible. If necessary, both of the ::type and
::next can be computed using an arbitrarily complex metacode. You
might be interested in the following article:
http://linux.rice.edu/~rahul/hbaker/Iterator.html

> > - list_node<> doesn't check the validity of the template arguments. At
> > least NextNode has special requirements. This same problem
> > can be seen in many places.
>
> Right, for now boost::mpl doesn't perform any concept checking. It's on
> my to do list, but not in the top 10 items. If you think it's more
> important than that, I would be glad to accept your help :).

I'm interested in contributing to metaprogramming facilities of Boost.

> I don't like enum trick either. IMO it's ugly, error prone and clutters
> the code. Also, IMO the ability to specify a type of the constant is a
> good thing.

I agree that in normal run-time C++ the ability to specify a type is
generally a good thing. However, in the context of metaprogramming, it is
rarely necessary to have a specific type. Many excellent programs have
been written in programming languages that only offer a single infinite
precision integer type and a boolean type.

> > - The endline layout is a bad idea. It makes maintanance more
> > difficult. I can already pinpoint examples of broken code layout in
MPL.
> > See Code Complete, ISBN 1-55615-484-4, for details.
>
> I've read the book. I don't think that the 'boost::mpl' code you're
> referring to does have any of the "endline layout" problems. If it does,
> I would appreciate being enlightened.

Here is code snippet taken from MPL:

    template<typename T, class NextNode>
    struct make_node
        {
        typedef mpl::list_node< T
                              , NextNode
                              , list_sequence_tag
                              , list_traits<Tag>
                              > type;
        };

As you can see, it uses the endline layout.

One of the problems with endline layout is that it is hard to apply
consistently. Here is an example snippet that doesn't use endline layout:

template<class Sequence, typename T>
struct push_front
    : push_front_algorithm_traits<
            typename mpl::sequence_traits<Sequence>::sequence_category
            >::template algorithm<Sequence, T>
    {
    };

With endline layout, you'd end up with extremely long lines.

Another problem is that endline layout breaks easily when code is modified
(e.g. identifiers renamed shorter or longer or while adding typename or
template keywords while bug-fixing). Such changes can change the length of
the line that controls the indentation of the rest of the lines.
Maintaining endline layout takes a lot of time (without automated tools).

> > IMO Boost should
> > have a guideline that says that library authors are recommend not to
> > use endline layout, because it is not maintainable.
>
> May be. Depends on what do you mean by "endline layout".

Endline layout refers to a layout convention in which indentation is not,
in principle, invariant in respect to line length.

For example:

    if (an < expression) { do_something();
                           continue_doing_it(); }

Such a layout takes extra time to maintain and often breaks when code is
changed (maintained):

    if (a_longer_expression) { do_something();
                           continue_doing_it(); }

The same does not happen with other layout styles that remain invariant in
respect to code length. For example:

    if (an < expression)
    { do_something();
      continue_doing_it(); }

Transforms into:

    if (a_longer_expression)
    { do_something();
      continue_doing_it(); }

> > - MPL should be separated into multiple more cohesive libraries.
>
> Agree.
>
> > For example:
> >   - type traits (is_same, is_convertible, ...)
> >     - actually Boost already has this library and I don't see much
value
> > in duplicating the library.
>
> There is no duplication. 'boost::mpl' does use type traits library, and
> I don't know why you got the impression about duplicating of the
> functionality. The library has the 'mpl::same_as' predicate class (which
> uses the type traits 'is_same' class template as well), but that's a
> different story.

Yes, I was partially thinking of is_same & same_as. Also the logical.hpp
has functionality that is similar to (but not the same as) ice.hpp.

I can see now that you are using same_as<> as a predicate. Please note
that it is possible to make metafunction binders using member templates:

    template<class metafun, class bound>
    struct bind_1_of_2
    {
      template<class unbound>
      struct code
      {
        typedef typename
          call_2<meta_fun,bound,unbound>::type
            type;
      };
    };

I've used this technique previously in order to create a predicate for
partition out of a binary comparison function passed to a quicksort.