Re: [boost] Re: compile time member detection

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-11-15 16:32:54

On Sat, Nov 15, 2003 at 11:20:08AM -0800, Mat Marcus wrote:
> --On Saturday, November 15, 2003 5:57 AM -0500 Brian McNamara 
> >On Fri, Nov 14, 2003 at 03:16:50PM -0800, Mat Marcus wrote:
> >>--On Friday, November 14, 2003 2:29 PM -0500 Brian McNamara
> >>> - "Clonable and Foo were developed separately"
> >>>
> >>> Suppose they come from two different vendor libraries, and today
> >>> you decide to use those two libraries together.  You, the client
> >>> of these libraries, will have to write the instance declaration.
> >>> In the implementation you may have to "smooth over" the
> >>> interface: we can imagine that perhaps Foo natively provides a
> >>> "duplicate" method, so you have to write
> >>>   instance Clonable Foo where
> >>>      clone aFoo = aFoo.duplicate() // using C++ syntax to
> >>> illustrate idea
> >>>
> >>> Etc.  There are probably other scenarios, too.
> >>
> >>Yes, I've also been wanting this in C++. The ability to
> >>rename/remap  operations to allow achieve conformance seems highly
> >>desirable. But
> >
> >Well, you can already do this in C++ (using the age-old "any problem
> >in computer science can be solved by adding an extra layer of
> >indirection").
> 
> Let me restate. I've been wanting something like this as part of a 
> proposed C++ concept mechanism for C++ '0x. The current papers don't 

Gotcha.  You mentioned this before, but I should this in mind (what your
questions are really 'aiming at').

> yet appear to provide for a remapping facility.

I see.  

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.

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*> { ... };

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) ... } 
   */

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

> >I feel like I am being long-winded and I am not sure if I am
> 
> I don't feel that you are being long winded. I've been specifically 
> asking you to describe how things work in Haskell in practice and 
> you've been patiently responding. If folks are bored they can ask me 
> to stop asking you these questions. In any case, I'm finding your 
> posts useful and I appreciate that you are taking the time to write 
> them.

I'm glad.  I'm enjoying discussing it, because it's giving me a chance
to flesh out some of the ideas which have been sitting around idle in my
head.  I'm also filling in some of the gaps of my understanding.

> >communicating what I am trying to say.  I guess my point is, if you
> >find yourself having to "manually specify the identity map" (or any
> >"map", for that matter), then somewhere along the line you have
> >probably already  dropped the ball.  Instance definitions are meant
> >to be _the_ definitions, not just a common storehouse for a map to
> >the real definitions which are scattered elsewhere.
> 
> 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.)  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 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.)

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

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.  The framework I am envisioning enables the problem to be
solved (ugly, but ugly is better than nothing) without refactoring or
prior design omniscience (both of which would allow you to "do it
pretty").  Oh, and by the way, this framework also provides a nice way
to do "named" rather than "structural" conformance.  (The previous
sentence is just to emphasize that this "ugly solution" is _primarily_
intended to solve the otherwise-intractible problem of combining
independently-developed libraries, and only _secondarily_ intended to
provide a way to do named (instead of structural) conformance.)

> Do the arguments about speed fade somewhat when we include headers full
> of instance definitions? 

What "arguments about speed" are you referring to?

> >Really, the point is, this problem is _intrinsic_to_the_situation_.
> >This is not a side-effect of "declaring conformance using a
> >type-class like mechanism".  No.  It is a side-effect of "wanting to
> >use two independently developed libraries together when the
> >libraries do similar things but use different interfaces".  The only
> >way to avoid complex dependencies like this is to either (1)
> >refactor or (2) have had more foresight from the outset.
> 
> In the structural conformance world view, if both libraries happen to 
> conform structurally then I don't see client 2 depending on client 1 
> in any way. 

You're absolutely right; this is an advantage to the structural way of
doing things.  However,

> Of course in the structural conformance with remapping scenario we may
> meet similar problems. 

Right--you will.  The "remapping" is the "glue code".  Regardless of
whether you need to merely "massage the interfaces" (e.g. "remapping")
or you need to provide the functionality from scratch for the first
time (e.g. "here is the first implementation which implements the
concept for this type"), you run into the same structural/dependency
issues.

To summarize, the "dependency issue" is always there, conceptually.  It
just so happens that, in the specific case where we are lucky enough to
have structural conformance between two libraries, we can avoid having
the dependency explicitly manifest itself in the actual source code for
our software.  This runs the risk of "unhappy accidents" (e.g. the
template that was expecting types modeling Windows accidentally accepts
a Cowboy because Cowboy provided the necessary move() and draw()
methods).

Another way to think about it: People seem to always view these
"dependencies" as "extra" or "undesirable".  The dependencies are
certainly not "extra".  They are totally real dependencies.  There is a
semantic requirement: for example, the reason you cannot use an auto_ptr
in a vector is because even though it may syntactically appear to be an
Assignable, it does not have the right semantics.  (auto_ptr is
probably not the best example, it was just the first thing that sprang
to mind.)

C++'s structural conformance model for templates has allowed us to
"sweep the dependencies under the rug".  The dependencies are still
there, but we have become so accustomed to not seeing them that,
psychologically, we are prone to imagining that they are not there.
They are there, they are just hiding behind the veneer of structural
conformance.

As for "undesirable": nobody likes dependencies.  They create structure
and management problems for our software.  Nevertheless, I don't think
the best overall solution strategy is to try to make the real
dependencies disappear in a flash of smoke and mirrors.  The best
strategy is to come up with better tools and language constructs which
will make managing these dependencies as lightweight and as
straightforward as possible.  Making the dependencies manifest will also
provide benefits (such as better error messages when trying to
instantiate templates which types that don't model the required
concepts).

> I am still trying to improve my understanding of how concept-like 
> features work in other languages to guide my opinion on how they 
> should look in C++ '0x. Incidentally, even today I find 
> boost::function_requires and the concept archetypes to be rather 
> useful.

Since you happened to mention archetypes here, let me again try to drive
home the "static v dynamic typing analogy".

Dynamic typing advocates say they don't need type systems because type
errors are not a practical problem.  Why not?  Because dynamic typers
are more accustomed to writing suites of unit tests.  These unit tests
not only test the (content-)functionality of their programs, but they
also have the side-effect of flushing out "type errors".  As a result,
dyanmic typers don't see the need for static type systems, since they
already have tools in their tool-suite which find these errors anyway.

In that context, if you ask me "what is an archetype?" I will answer 
"it is the unit test designed to find the 'type errors' in C++ template
code".
(where 'type errors' means those kinds of errors that a real
concept system would uncover--the same kinds of errors uncovered by a
Haskell compiler when type-classes/instances/constraints are abused)

-- 
-Brian McNamara (lorgon_at_[hidden])