Re: [boost] Re: compile time member detection

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-11-15 21:55:00

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.)

> --On Saturday, November 15, 2003 4:32 PM -0500 Brian McNamara 
> >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.

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

   data RussellShackelford = ...
   data GrandmaOfRuss = ...

   instance Nameable RussellShackelford GrandmaOfRuss where
      name RussellShackelford = "Russell"

   instance Nameable RussellShackelford a where
      name RussellShackelford = "Russ"

   -- 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

   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 "+", 
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.  As a result, my
hunch is that the best way to deal with cases like this is just to
create (arguably artificial) entities as extra parameters to a
multi-sorted concept.  Personally, I prefer the solution above to a
solution which weighs down the language with yet-another-construct
designed to specifically handle rare cases like this.  I reserve the
right to change my mind in the future.  :)

> >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).

So, to summarize my opinion, then:

 - Monoid owns the operation named "multiply".

 - AbelianGroup owns the operation named "add".

 - Num owns the operation named "+".

 - Somewhere there is code which sums two Integer objects, and all of
   the operations above (with respect to Integers) end up pointing at
   this same piece of code.

This leaves open the question of "where" the "piece of code" ought to
live.  In the end, I think it really doesn't matter much, and my hunch
is that it ("it" being "the best choice for where the primitive piece
of code ought to live") will vary from situation to situation.

What do you think?  Is this a reasonable way to think about things?

> 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).

I hope that the way I have explained it makes it clear that one "piece
of code" may go by many "names".  Each "name" is owned by a particular
concept, but the operation itself may be associated with a number of
names (just as the single person Mr. Shackelford is associated with a 
number of names).

It may already be clear, but note that the concepts/names also "own" the
associated semantics.  Consider:

   class Bag collection element where
      -- pick returns some element in the collection (or Nothing if the
      --    collection is empty)
      pick :: collection -> Maybe element

   class OrderedCollection collection element where
      -- return first element, or Nothing if empty
      first :: collection -> Maybe element

   firstOfList :: [a] -> Maybe a
   firstOfList []   = Nothing
   firstOfList x:_  = Just x

   instance Bag [a] a where
      pick = firstOfList

   instance OrderedCollection [a] a where
      first = firstOfList

Now if I have a list "l", note that "pick l" could in theory return any
element of the list, whereas "first l" is guaranteed to return the first
element.  In practice, both behave exactly the same, as they share the
same implementation.  The point I want to illustrate is that the
operation names (which have a one-to-one corerspondence with the
concepts) are the things associated with the semantics.  It is in this
sense that I think it is reasonable to speak of "ownership".  (Note that
in this example, none of the concepts "owns" the function
firstOfList--the "piece of code which actually does the work".)

> >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).

I hope so.

> >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.

Agreed.

> >>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]

Ah, I see.  I don't know.

-- 
-Brian McNamara (lorgon_at_[hidden])