Re: [boost] Re: review request: container_traits

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-10-06 00:06:17

On Sun, Oct 05, 2003 at 05:03:00PM -0400, David Abrahams wrote:
> Brian McNamara <lorgon_at_[hidden]> writes:
> > On Sat, Oct 04, 2003 at 05:48:19PM -0400, David Abrahams wrote:
> >> Brian McNamara <lorgon_at_[hidden]> writes:
> > One solution, which I think is the solution you are suggesting, is to
> > make individual traits:
> >
> >    container_value_type<C>::type
> >    container_iterator_type<C>::type
> >    ... // etc for each "foo"
> >
> > This solves both of the problems above: each type is computed
> > "independently", and each trait is an MPL metafunction.  However the
> > weakness here is that now we have polluted the namespace with many
> > new names (rather than just one ("container_traits")), 
> 
> So use a nested namespace (?)
> 
> What I see above is a very complicated solution to a very simple
> problem.  I don't think there's any need to do something creative
> when we can do something that's already proven to work.

It may turn out that you are right, but I still have one more ace up my
sleeve.  (See below.)

> > and the conceptual-relatedness of the group of traits is no longer
> > expressed by a structural grouping in the code.
> 
> Which is good because it allows non-intrusive extension.  And there
> *will* be extensions.  We really shouldn't want the definition of
> container_traits to get progressively more bloated as they are added.

I will debate this point later in this message.

> > In order to have our cake and eat it too, I propose this:
> >
> >    container_traits<C>::value_type<>::type
> >    container_traits<C>::iterator_type<>::type
> >    ... // etc for each foo
> >
> > Now we reap the advantages of both solutions.  That is
> >
> >  - we have conceptually grouped related traits into a single traits
> >    class (container_traits<C>)
> >
> >  - each individual trait is an MPL metafunction (e.g. 
> >    container_traits<C>::value_type<>)
> 
> That's a nullary metafunction, which isn't very useful if you want to
> use it in an MPL lambda expression.  Since C is already bound into it,
> you can't apply it to different containers.

When I originally proposed it, the nested templates had dummy template
parameters with default values.  This is, indeed, not very useful.

But it occurs to me that the nested templates' default values should be
"C", and the nested templates should use the value of their argument to
do the actual computation.  Thus:

   container_traits<C>::value_type<>::type

means 

   container_traits<C>::value_type<C>::type   // C is the default value

and furthermore

   container_traits<AnyType>::value_type<C>::type

computes the trait "value_type" for container C.

When it's done like that, then

   container_traits<C>::value_type<>

is a nullary metafunction, and

   mpl::lambda< container_traits<AnyType>::value_type<_1> >::type

is the corresponding unary metafunction (which takes the container as
an argument).

(Indeed, container_traits itself should have a default value for the
template parameter (something harmless like "void"), so that

   container_traits<>::yadda    // my proposed version

works just like

   container_traits::yadda      // namespace version

in the namespace version.  In other words, if you don't pass an argument
to container_traits, it degenerates into being equivalent to the
namespace version.)

So I think this gives us all of the desired "features".  Now, of course,
the question is, have we gained anything over just using a namespace?
That is, how is what-I-propose-above better than just

   // container_traits is just a namespace
   container_traits::value_type<C>::type

?  Well, I'll confess that I'm not completely sold that it is better.
But it does have a few potential advantages.  The one main advantage I
see is that it lets you pass a collection of related traits around.
That is, you can say

   foo< container_traits<SomeContainer> >

where foo is defined like

   template <class ContTraits>
   struct foo {
      typedef  ContTraits::value_type<>::type     A;
      typedef  ContTraits::iterator_type<>::type  B;
   };

When just using the namespace, you'd be forced to pass the container:

   foo< vector<int> >
   ...
   template <class Cont>
   struct foo {
      typedef container_traits::value_type<Cont>::type A;
      typedef container_traits::iterator_type<Cont>::type B;
   };

If what you actually want is the traits (rather than the container), the
namespace method forced you into passing the "wrong" kind of argument.
The question is, do you ever actually want to do this?  (In other words,
what is an actual example of a class like "foo" above?)  I can't think
of a reason offhand that this is useful, but my gut tells me it may be
useful for something.  I think my gut tells me this because I have
already seen how the corresponding "non-meta" functions can be useful:

   //    Analogy in non-meta C++, using FC++

   // for some type C where "value(c)" and "iterator(c)" are functoids
   // which compute some (presumably-interesting) functions of c
   f = lambda(C)[ make_pair[ lambda()[ value[C] ],
                             lambda()[ iterator[C] ] ] ]
   ... 
   f(c)  // pair of 0-ary funcs that compute value & iterator on demand

That is, my technique provides a way for inner meta-functions to
"capture" meta-values bound by outer meta-functions.

I suspect there may be other interesting capabilities hidden in this as
well.

Anyway, when it comes down to choosing between the namespace approach
and my approach, I guess you do a cost-benefit analysis.  My approach
clearly has more costs (in interface complexity and probably also
implementation) than the namespace approach.  I think theoretically
there may be benefits (which is why I'm bothering with this at all),
but in practice, I can't think of a practical situation where these
benefits would be useful (yet).  (Perhaps you can!)

So I won't try to win anyone over, but I at least wanted to get the idea
out there.  Maybe somewhere down the road this will prove useful in
practice.

Anyway, one other quick note to fulfill my earlier promise:

> > and the conceptual-relatedness of the group of traits is no longer
> > expressed by a structural grouping in the code.
> 
> Which is good 

I think I disagree...

> because it allows non-intrusive extension.  

... despite the fact that I agree with this (namespaces, unlike classes, 
are "open")...

> And there *will* be extensions.

... and despite the fact that I also agree with this.

> We really shouldn't want the definition of container_traits to get
> progressively more bloated as they are added. 

You're using the term "bloated", but I see it as "reification of the
concept".  If we add new "traits" to the Container concept, great.
IMO, all of the Container-trait-accessors (that is, these metafunctions) 
should be physically grouped together into one entity.  To be a model of
the Container concept, a class needs to implement the all of the
container interface (e.g. functions like begin() and end()), and it must
also 'work' with container_traits.

If we (as Boosters, library designers, whatever) decide to extend/refine
the Container concept to imply new traits attributes, then we must
either (1) add new Container-trait-accessors to container_traits or (2)
define a new entity (e.g. "extended_container_traits", which inherits
container_traits and adds some new stuff).  Either of these solutions is
fine; what's important is that it reifies the concept (or concept
hierarchy) in the code.  

Using the namespace approach, every time Joe-Library-Author decides he
really needs to know some new attribute about Containers (e.g.
insert_invalidates_iterators), he adds to his code

   namespace container_traits {
      template <class C>
      struct insert_invalidates_iterators { /* ... */ };
   }

and then uses this new trait in his algorithm.  And then he soon
discovers that his algorithm doesn't work on most containers, since the
authors of those container classes have never heard of this trait.
Perhaps Joe then starts specializing
container_traits::insert_invalidates_iterators for lots of containers.
(Whose job is it, really, to ensure all containers have this
attribute?  Joe's, or each container's author?) This quickly starts
getting messy.  Even moreso when Joe discovers that Jane-Library-Author
has been duplicating his work with a new attribute called
"insertion_invalidates_iterators", which Joe had never heard about
until the day her code came up for review.

The point is, IMO, for concepts to be useful, they must be reified, and
concept requirements must all be located together in one place.
(Regardless of whether people agree with this view, my experience is that
concept-reification is an inevitable part of every template library's 
evolution.  It's gonna happen eventually, so when standardizing efforts
start to happen (like the root of this whole container_traits thread),
you might as well go ahead and do it "right".)

All right, I'll stop.  I've been far too long-winded already, especially
since I don't think there's any useful short-term outcome for anything
that I've said.  Just food for thought.

-- 
-Brian McNamara (lorgon_at_[hidden])