Re: [boost] Re: compile time member detection

From: Mat Marcus (mat-boost_at_[hidden])
Date: 2003-11-15 18:07:40

--On Saturday, November 15, 2003 4:32 PM -0500 Brian McNamara 
<lorgon_at_[hidden]> wrote:

[snip]

> It seems to me that, if we could partially specialize function
> templates, we would already be a great deal of the way there.
> "Specialization" in C++ can be used analogously to "instance" in
> Haskell.  One if the current problems in C++ is that only _class_
> templates can be _partially_ specialized, which means you often have
> to jump through the annoying hoop of having functions "forward" the
> work to a class helper.

There is definitely a need to dispatch to the appropriately 
specialized generic algorithm that is unambiguously most specific 
match. The current proposals address this, but as I mentioned earlier 
there was some pushback from the compiler vendors leading to at least 
one workaround proposal that in my mind resembles named conformance.

> The other thing we would "need" is specialization relative to concept
> constraints.  That is, in addition to
>
>    // forall T, T* models Clonable
>    template <class T>
>    struct Clonable<T*> { ... };
>

FYI: Current spelling of the concept declarations in the usage-pattern 
approach (although this) is likely to change:

concept Clonable {
    constraints(Clonable c) {
        clone(c);
    };
};

or equivalently using the so-called pseudo-signature approach (I 
currently prefer this approach):

concept Clonable {
    clone(Clonable)->Clonable
};

> we need to be able to say
>
>    // forall Clonable T, list<T> models Clonable
>    template <class T : Clonable>
>    struct Clonable<list<T> > { ... };
> Presumably the same "constraint mechanism" (that is, the imagined new
> syntax I used above of ": Clonable") can be used for normal templates
> (as opposed to specializations), too:
>
>    template <class T : Clonable>
>    void f( T x ) { ... clone(x) ... }
>    /* instead of the gorier
>          template <class T>
>          enable_if<isa<T,Clonable>,void>::type
>          f( T x ) { ... clone(x) ... }
>    */
>

Given the above, current spelling of f() would be
template <Clonable T>
void f(T x) { ... clone(x) ... };

>> > Put another way, it is rare in Haskell for an instance
>> > declaration to just define functions which "forward the work
>> > elsewhere".  Instead, what usually happens is that the instance
>> > declarations are the one and only place where the "work" is
>> > defined.
>>
>> IIUC, the above paragraph surprises me. I imagine that it is not
>> uncommon for operations in a generic program participate in
>> modeling  multiple concepts (possibly unrelated in the concept
>> taxonomy).
>
> Can you give an example (even a contrived one)?  I'm not sure I
> understand what you are saying.
>

Ok here's a contrived example using the pseudo-signature based syntax:

concept Monoid {
    identity () -> Monoid ;
    multiply (Monoid , Monoid) -> Monoid;
    // would like to put an equation here for assoc.,
    //but lets not get into semantic concepts yet
};

concept AbelianGroup {
    identity() -> AbelianGroup;
    add(AbelianGroup, AbelianGroup)->AbelianGroup;
    negate(AbelianGroup)->AbelianGroup;
};

class Integer {
  // irrelevant details;
};
Integer add(Integer, Integer);
Integer multiply(Integer, Integer);
Integer additive_identity();
Integer multiplicitive_identity();
Integer negate();

[snip]

>> The part about "instance definitions are meant to be _the_
>> definitions" still seems foreign. That is, I expect that an
>> arbitrary  operation may participate in modeling multiple concepts.
>> I am  reluctant to commit to letting an operation be "owned" by a
>> particular  instance definition. As I see it, such a notion of
>> ownership is one of  the overconstraints imposed by the
>> OOP/interface-based programming  paradigms. This puts me back on my
>> "inheritance/member functions  considered harmful" track.
>
> I'm not sure exactly what you mean by "owned".  (An example may help;
> see my earlier comment.)

In the example above I see Integer modeling Monoid in (two different 
ways one for + and one for *). Integer also models abelian group (just 
one way). Of course this requires some remapping/glue. The aim of this 
example is to show that the add() operation participates in two 
distinct concepts. Let's for the moment ignore the fact that the 
concept hierarchy could in fact be arranged so that abelian group was 
(eventually) derived from monoid. If that is too distracting I can 
contrive a better example.

> If I do grok what you're saying, I think I would say that the
> _type_class_, rather than the _instance_, "owns" the operation.  For
> example, the swap() operation is not "owned" by vectors, or by
> lists, or by other swappable types.  It is "owned" by the Swappable
> concept.  Various classes (types) will specialize the concept
> (declare instances of the type class) in order to both declare that
> they model the concept and to provide an implementation for the
> methods in the concept interface.

In my example I don't think that I want either Monoid or AbelianGroup 
to "own" the operation eventually specialized as add(Integer, Integer).

>
> (In principle, with a good concept framework/library, there's no
> reason  you'd ever have to create swap() member functions in classes
> like std::vector.  Rather, std::swap() would be specialized for
> vector<T> arguments, and this specialization would be the _only_
> place where the "code to do the work to efficiently swap vectors"
> would be written.  In practice, it might be useful to provide the
> member function as well (for whatever reason), but the current trend
> seems to be "down with member functions! up with free functions!"
> anyway, so.)

True. This could change if we a way is developed to invoke members and 
non-members uniformly.

>
>
>> >> What then are the dependencies?
>> >
>> >   Clonable     Foo
>> >        \       /
>> >      Client1Glue
>> >           |
>> >        Client2
>> >
>> > Looks ugly, eh?  Tough!  :)
>>
>> Just to recap, is the point that you are willing to accept this
>> ugliness in order to avoid accidental structural conformance?
>
> I am willing to accept this ugliness provided that it gives me a
> uniform way to both:
>  - avoid accidental structural conformance
> and
>  - enable separately-evolved libraries to be glued together
> (If it were _only_ useful to avoid accidental conformance, it would
> probably not be worth it.)
>
>
> I feel like most C++ programmers have become so accustomed to the
> "happy accident of structural conformance" that they think it is the
> common case.

Perhaps. But even with named conformance I believe that part of the 
power of the generic programming paradigm stems from the avoidance of 
trying to view each operation as pariticipating in only a single 
concept (e.g. it avoids some of the mistakes of the interface-based 
programming paradigm).

> It's not.  Aside from functionality named by (1)
> operators or (2) a handful of common names that have fallen into
> common usage (like "swap" and "clone"), the chances that
> some-random-library-
> is-going-to-just-happen-to-present-an-interface-which-exactly-
> structurally-conforms-to-the-concepts-you-developed-independently are
> nearly zero.

You make good arguments against structural conformance and I am still 
considering them.

> That is to say, we are now nearly at the point where we have
> exhausted our supply of "happy accidents".  Structural conformance
> is only working well now in C++ because everyone is using very basic
> concepts which have one "spelling" that everyone agrees upon.
> (Assignable? That's spelled operator=().  Swappable?  That's spelled
> swap().) Tomorrow's concepts will be more complex, and thus we will
> no longer find that "VendorX's graph library just happens to present
> the right interface to work out-of-the-box with my hand-crafted
> BreadthFirstSearchVisitor concept".  Glue code will have to be
> written.

Yes.

> The framework I am envisioning enables the problem to be
> solved (ugly, but ugly is better than nothing)

I'm also wondering whether we can do even better (than ugly).

> without refactoring or
> prior design omniscience (both of which would allow you to "do it
> pretty").

Of course. Key design criteria for concept-like features should 
include support for the open-closed principle and separate compilation 
of generic algorithms.

[snip]

>
>> Do the arguments about speed fade somewhat when we include headers
>> full of instance definitions?
>
> What "arguments about speed" are you referring to?

Howard Hinnant's amongst others:

    --On Friday, November 14, 2003 12:06 PM -0500 Howard Hinnant
    <hinnant_at_[hidden]> wrote:
    [snip
    Structural conformance worries me. :-)

    Two reasons:

    1.  Checking structural conformance will inevitably lead to slower
    compile times than checking named conformance simply because there
    is typically more to check structurally.  By how much, I have no
    experience.  But it worries me.
    [snip]

[snip more advocacy of named conformance and explicit dependencies]

Still thinking about those.

 - Mat