Re: [boost] Re: compile time member detection

From: Mat Marcus (mat-boost_at_[hidden])
Date: 2003-11-15 23:54:50

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

> On Sat, Nov 15, 2003 at 03:07:40PM -0800, Mat Marcus wrote:
>> 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
>> };
>
> Hm.  I take it these proposals don't handle the multi-sorted case?
> (The syntax suggests to me that these proposals aren't expressive
> enough to talk about a number of interesting concepts.)

[Note: Just for the record it's probably a little early to refer to 
the papers as proposals although I may have slipped up earlier and 
done so myself. I believe that is was rather courageous of Bjarne and 
Gaby to put these ideas forward for discussion despite the unfinished 
nature and the rough edges.]

The papers do provide for multi-sorted concepts using 
parameterization. The current syntax (usage-pattern variation) is 
something like this:

template<class L, class R, class Result>
concept Add {
    constraints(L x, R y, Result r) {
         r = x+y;
    }
};

Pseudo-signature version:

template<class L, class R, class Result>
concept Add {
    +(L, R)->Result;
};

>> > 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();
> ...
>> 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.
>
> No, this is a good example.  I have seen it cited before but I had
> forgotten about it.

Interesting. I thought that I had just contrived it. I'd like to read 
more about this sort of thing if you have additional references.

>
> This reminds me of story my first CS prof used to tell students in
> order to explain the concept of indirection.  To explain the idea of
> two pointers, p1 and p2, which could both refer to the same object,
> o, he used the example of naming himself.  Everyone called him
> "Russ", except his grandmother, who always called him "Russell".
> It's a nice way to demonstrate the idea of two different names
> referring to the same object.
>
> Anyway, if I wanted to model something similar using concepts, I can
> imagine running into the same issue as with Monoid.  Namely something
> like:
>
>    concept Nameable {
>       name()->string
>    }
>    struct RussellShackelford {
>       string name() {
>          // what do we return?  "Russ"?  "Russell?"
>          // do we need two name() methods?
>       }
>    };
>
> Regardless of how well it actually models the problem domain, my "gut
> reaction" of how to solve this problem in software is to introduce
> another entity to play the role of "Who's asking?"  Something like
>
>    -- Switching back to Haskell because I need multi-sorted stuff
>    class Nameable thingBeingNamed whosAsking where
>       name :: thingBeingNamed -> string
>

Just for fun here's a version in the syntax of the papers:

template <class Thing, class Who>
concept Nameable {
    constraints(Thing thing, Who who){
        string s = name(thing, who);
    }
};

Alternatively:

template <class Thing, class Who>
concept Nameable {
    name(Thing, Who)->string;
};

>    data RussellShackelford = ...
>    data GrandmaOfRuss = ...
>
>    instance Nameable RussellShackelford GrandmaOfRuss where
>       name RussellShackelford = "Russell"
>
>    instance Nameable RussellShackelford a where
>       name RussellShackelford = "Russ"

Presumably a is some sort of predefined placeholder for a universal 
type?

>    -- Note that we need the Haskell "overlapping instances" extension
>    -- (which corresponds to the C++ notion of "most specialized
> version    -- of the template") to disambiguate the two.
>
> Similarly, my hunch is that the "best" (see below) way to deal with
> Integers being twice a Monoid is similar:
>
>    class Monoid t how where
>       identity_element :: t
>       multiply :: t -> t -> t

Ok, just to make sure that I understand what this means I'll try to 
rewrite this using pseudo-signature syntax as:
template <class T, class Tag>
concept Monoid {
    identity_element()->T;
    multiply(T,T)->T;
};

[Aside: wonder how metafunctiona callability would be expressed in the 
pseudo-signature based approach.]

>    data Integer = ...   -- whatever
>
>    -- Some tags which mean
>    --    Integer as monoid with respect to zero and plus
>    --    Integer as monoid with respect to one and multiply
>    data IAMWRTZAP = IAMWRTZAP   -- Excuse the horrid names
>    data IAMWRTOAM = IAMWRTOAM
>
>    instance Monoid Integer IAMWRTZAP where
>       identity_element = 0
>       multiply = (+)
>
>    instance Monoid Integer IAMWRTOAM where
>       identity_element = 1
>       multiply = (*)
>
> This example does illustrate issues with the idea of "ownership" of
> functionality.  The way I see it, "Num" still owns the operation
> "+",

Sorry, I am not familiar with "Num" -- unless you mean Integer?

> and Monoid still "owns" the operation "multiply".  Integer
> uses the same implementation code in both of these roles.  The way
> I've coded it above, "instance Num Integer" (presumably) contains
> the "real work" to add two Integers, whereas "instance Monoid
> Integer IAMWRTZAP" just "forwards" the work.  If Monoid had been
> defined prior to Num, it could have easily gone the other way, with
> "multiply" supplying the "primitive" definition, and "+" being
> defined in terms of "multiply". Both are equivalent.
>
> A couple paragraphs ago, I used the word "best".  I am not sure that
> this is actually the ideal way to represent this.  It might be better
> if there were some separate language construct which captured the
> idea/nuances of "roles".
> But language design is an exercise in
> trade-offs, and in my experience, examples where one type models one
> concept in two different ways are rare in practice.

[snip additional interesting discussion]

Despite my perhaps ill-chosen example, I am less interested in the 
case where one class models the same concept in two different ways 
than in the case where one function may participate in several 
unrelated concepts. And I speculate that the latter is not so rare. 
Here's a sketch of  another contrived example (I'm confident that as I 
explore this further I'll come up with better ones, but for now they 
escape me). There may exist concepts (unrelated in the concept 
hierarchy) from different libraries, such as ButtonPressedCallback and 
MenuItemSelectedCallback. In a perfect world these might both be 
replaced with a NullaryFunction concept. But in the real world I would 
expect to see such duplication. Now I may want to write a nullary 
function that could be used for a variety of purposes including 
playing the role of modelling each of the above concepts. I don't 
believe either of the concepts above should "own" my operation. 
Instead I want to think of those concepts as "roles" that my nullary 
function may take on (model). But as I read ahead I see that you may 
agree and that we were just using the word "own" in different ways. 
The thing which got me started on the whole "owned" track was this 
quote from an earlier email of yours:

    --On Saturday, November 15, 2003 5:57 AM -0500 Brian McNamara
    <lorgon_at_[hidden]> wrote:
    then no one would ever write begin()/end() functions/methods for
    user-defined data types like "list" or for builtin types like
    arrays. Instead people would _specialize_ the _existing_
    begin()/end() functions.

    That is, there is no reason to write your own function named foo()
    and then specialize FooConcept::foo() to call your foo().  You
    only specialize the existing name, since you are modeling the
    concept.

But I've probably spent way too much time on this small aspect of the 
discussion and  don't need to dwell on this any longer.

In summary, at this point I see named conformance as possibly 
advantageous, especially as it gives us a place to hang needed 
remapping functionality. I don't think that instance declarations are 
the right place for implementation code to live.  I am less interested 
in it from the preventing-accidental-structural-conformance 
perspective.  Maybe I'd rather see some support for equations/semantic 
concepts to help fill that role. No doubt there are many difficult 
questions down that road.

 - Mat