In article <2qoc4sINNooq@life.ai.mit.edu> gillett@rice-chex.ai.mit.edu (Walter E. Gillett) writes:
>Hi, Folks
>    One of the developers at my company recently came to me with approximately
>this situation:
>
>class Node {};
>class Graph { public:   virtual void DoIt( Node& );};
>
>class MyNode: public Node {};
>class MyGraph: public Graph
>{
>public:
>    //void DoIt( MyNode& );  // This is what he wants but he can't have it!
>    /*
>     * Instead he has to override DoIt with the same signature as the base-
>     * class and then check at run-time to insure he's really gotten an arg
>     * of type MyNode rather than any old Node.
>     */
>    virtual void DoIt( Node& );
>};
>
>What's the problem here?  The developer in question believes that his class
>hierarchy correctly represents the problem at hand.

 Guess he must be wrong.
>
>* Is there a way of handling this hierarchy more gracefully?  If not,

 Design faults cant be fixed by tricks.

>* is there a way of recasting this hierarchy to avoid the problem?  If not,

 The problem is in the design.

>* is there a class of problems for which multi-methods are REQUIRED and that
>  C++ can't really handle gracefully?

 No problems require multi-methods. Multi-methods dont exist. :-)

 What is needed here is probably templates.

 C++ style virtual function polymorphism cannot handle
multi-methods. No object oriented language can without giving
up something. In the case of CLOS, (I believe), and Cecil,
what is given up is encapsulation.

 Its a consequence of object orientation. Virtual
functions only work for ONE argument. That is the requirement
for linearity. That is, if you have n classes you can
put n functions into them, 1 per class.

 To dispatch on two arguments requires a matrix
of methods. Its clearly impossible to squeeze all those methods
INTO the classes.

 So they have to be outside the classes and ALSO have
access to the private implementation details. In other
words, encapsulation is lost.

 C++ enforces encapsulation. So multi-methods are impossible.

 Other systems (SML, I think) give up late binding
instead. You can do this (roughly) in C++ using templates,
ordinary function overloading, or you can cheat using RTTI
and casting.

 I've not yet found a problem not requiring external
interfacing that C++ cant handle without cheating. It is, however,
extremely hard sometimes to get the design right.

 If you have a discrete set of types, you SHOULD be using
switches. Inheritance is for subtyping -- the base abstraction
must admit infinite (arbitrary) implementations (derived classes).
In this case vectored dispatch works.

 In general, when you have virtual function polymorphism,
and need to implement a relationship or other n-ary function,
you must mediate the dispatches with a concrete "universal"
class that acts as a 'buffer'.

 For example: I have an abstraction that represents
a graphic image. The virtual functions of interest
are 'getpixel' and 'setpixel'. There is no way to copy
an image without a conrete type 'pixel' to mediate
the transfer.

--
        JOHN (MAX) SKALLER,         INTERNET:maxtal@suphys.physics.su.oz.au
 Maxtal Pty Ltd,      CSERVE:10236.1703
        6 MacKay St ASHFIELD,     Mem: SA IT/9/22,SC22/WG21
        NSW 2131, AUSTRALIA

Walter E. Gillett (gillett@rice-chex.ai.mit.edu) wrote:
: Hi, Folks
:     One of the developers at my company recently came to me with approximately
: this situation:

: class Node {};
: class Graph
: {
: public:
:     virtual void DoIt( Node& );
: };


: class MyNode: public Node {};
: class MyGraph: public Graph
: {
: public:
:     //void DoIt( MyNode& );  // This is what he wants but he can't have it!

:     /*
:      * Instead he has to override DoIt with the same signature as the base-
:      * class and then check at run-time to insure he's really gotten an arg
:      * of type MyNode rather than any old Node.
:      */
:     virtual void DoIt( Node& );
: };


: In words, class Node and Graph form an interrelated group of classes that must
: be subclassed and used en masse.  It is illegal to pass a generic Node to
: MyGraph::Doit().  But runtime checks are unpleasant and no checks at all would
: be quite dangerous!  In CLOS (Common Lisp Object System) I'd use a multi-method
: and essentially have a function that's virtual on both the object's class and
: the function's first argument.  But C++ doesn't work that way.  So...

: What's the problem here?  The developer in question believes that his class
: hierarchy correctly represents the problem at hand.

: * Is there a way of handling this hierarchy more gracefully?  If not,
: * is there a way of recasting this hierarchy to avoid the problem?  If not,
: * is there a class of problems for which multi-methods are REQUIRED and that
:   C++ can't really handle gracefully?

: I'll be awaiting the net's erudite responses with enthusiastic anticipation!
: ;-)

I believe that your problem is discussed in Jim Coplien's excellent book,
introduces the Liskov substitution principle: If for each object o1 of
type S there is an object o2 of type T such that for all programs P
defined in terms of T, the behavior of P is unchanged when o1 is
substituted for o2, then S is a subtype of T.  I hope this is a good
starting point for you.

--Shawn

If Graph is designed to "DoIt" (used as verb) for any Node, MyGraph as a
subclass of Graph should not say that it can only "DoIt" for MyNode.

If your developers find that they have to restrict "DoIt" in subclasses, then,
their  superclass Graph is designed wrong. I.e., for any object G of Graph, and
any  object N of Node, G.DoIt(N) does not hold!

You have to specify that the input type of "DoIt" is a dependent type of Graph:

 class Graph < class NodeType :Node >
 {   public:
  virtual void DoIt (NodeType&);
 }

And MyNode as:

 class MyNode: public Node < class NodeType: MyNode >;

Note that the above code is not a C++ template. It is Cluster's parameterized
class presented in C++-alike syntax. Dynamic genericity is supported in
Cluster.

If your project will not use polymorphism on class Graph, you can use C++
template for Graph. It's fine.

Otherwise, you have to use languages (if you chose static typed language) that
support dynamic genericity. Cluster or BETA.

Run time type check is necessary only for reverse assignment.

I have discussed this in "Who Win the War of Co. Vs. Contra?". The conclusion
is neither. Covariance is not the natual requirement, because by covaraince you
will define something that a subclass cannot do while the superclass class can,
which is against the law of inheritance. The winner is novariance with
covariant constraints, which enables you to detail the specification in your
subclass. The specification of Node in subclass MyGraph get more revealed, not
narrowed!

David Shang

Hi, Folks
    One of the developers at my company recently came to me with approximately
this situation:

class Node {};
class Graph
{
public:
    virtual void DoIt( Node& );
};


class MyNode: public Node {};
class MyGraph: public Graph
{
public:
    //void DoIt( MyNode& );  // This is what he wants but he can't have it!

    /*
     * Instead he has to override DoIt with the same signature as the base-
     * class and then check at run-time to insure he's really gotten an arg
     * of type MyNode rather than any old Node.
     */
    virtual void DoIt( Node& );
};


In words, class Node and Graph form an interrelated group of classes that must
be subclassed and used en masse.  It is illegal to pass a generic Node to
MyGraph::Doit().  But runtime checks are unpleasant and no checks at all would
be quite dangerous!  In CLOS (Common Lisp Object System) I'd use a multi-method
and essentially have a function that's virtual on both the object's class and
the function's first argument.  But C++ doesn't work that way.  So...

What's the problem here?  The developer in question believes that his class
hierarchy correctly represents the problem at hand.

* Is there a way of handling this hierarchy more gracefully?  If not,
* is there a way of recasting this hierarchy to avoid the problem?  If not,
* is there a class of problems for which multi-methods are REQUIRED and that
  C++ can't really handle gracefully?

I'll be awaiting the net's erudite responses with enthusiastic anticipation!
;-)
---------------------------------------------------------------
Joe Shapiro (NOT Walter Gillett, though I'm using his account!)
Please send replies to:                        joe@ConSolve.COM

In article <2qoc4sINNooq@life.ai.mit.edu>, you write:
|> Hi, Folks
|>     One of the developers at my company recently came to me with approximately
|> this situation:
|>
|> class Node {};
|> class Graph
|> {
|> public:
|>     virtual void DoIt( Node& );
|> };
|>
|>
|> class MyNode: public Node {};
|> class MyGraph: public Graph
|> {
|> public:
|>     //void DoIt( MyNode& );  // This is what he wants but he can't have it!
|>
|>     /*
|>      * Instead he has to override DoIt with the same signature as the base-
|>      * class and then check at run-time to insure he's really gotten an arg
|>      * of type MyNode rather than any old Node.
|>      */
|>     virtual void DoIt( Node& );
|> };
|>
|>
|> In words, class Node and Graph form an interrelated group of classes that must
|> be subclassed and used en masse.  It is illegal to pass a generic Node to
|> MyGraph::Doit().  But runtime checks are unpleasant and no checks at all would
|> be quite dangerous!  In CLOS (Common Lisp Object System) I'd use a multi-method
|> and essentially have a function that's virtual on both the object's class and
|> the function's first argument.  But C++ doesn't work that way.  So...

Let's separate two issues:

    -- TYPE CHECKING: there is no way to type-check these kinds
       of parallel class hierarchies in OOP statically; runtime
       checking is all you can do.  Note that with parallel
       class hierarchies in CLOS, all you would get is runtime
       checking as well; if you try to use a Node with an
       incompatible Graph, you'll simply get a runtime error.

    -- MULTIMETHODS: multimethods can be simulated quite
       easily with C++ (think about it for a moment...), giving you the
       same behavior you get with CLOS, including the potential runtime
       errors.

|> What's the problem here?

The problem is inherent in OOP--it can't handle such cases,
nor is it clear that it should.

|> The developer in question believes that his class
|> hierarchy correctly represents the problem at hand.

I'm not so sure about that.  What is the point of building parallel
class hierarchies if you can't substitute objects with identical
interfaces for one another?

Presumably, the reason for this design is that you want to write
graph functions that can be used with many different Graph and
Node types, as long as they are compatible and as long as each
has the proper interface:

    void search(Graph *graph,Node *node) {
 assert_type_compatible(graph,node);
 ...
 graph->DoIt(*node);
 ...
    }

    doit() {
 MyGraph g; MyNode n;
 search(&g,&n);
    }

Well, if you use inheritance, you need the runtime check.  But you can
express these relationships using template classes so that everything
will check at compile time:

    template<class Graph,class Node>
    void search(Graph *graph,Node *node) {
 // no runtime check required
 ...
 graph->DoIt(*node);
 ...
    }

    class MyNode {};
    class MyGraph { public: void DoIt(MyNode&); };

    doit() {
 MyGraph g; MyNode n;
 search(&g,&n);
    }

Note that the inheritance is gone.

|> * Is there a way of handling this hierarchy more gracefully?  If not,
|> * is there a way of recasting this hierarchy to avoid the problem?  If not,
|> * is there a class of problems for which multi-methods are REQUIRED and that
|>   C++ can't really handle gracefully?

Again, if it's multi-methods you want, you can easily have them, but
the problem is not related to multi-methods, since you can't do the
static type checking even with multi-methods.

Using template classes and functions for expressing these kinds of type
relationships in C++ works but is, unfortunately, a little obscure and
requires a lot of contortions to avoid code-bloat.

Languages like SML and Ada provide much better facilities for
implementing such groups of related data types and reusing code
based on them.  In SML:

    signature GRAPH =
 sig
     (* define an abstract GRAPH structure consisting
        of two related datatypes, node and graph,
        and operations on them *)

     type node;
     type graph;
     val is_first_node: graph * node -> bool;
 end;

    functor GraphSearch(G: GRAPH) =
 struct
     (* define a search function that works with
        any GRAPH structure, that is, with any set of
        related node and graph types *)

     fun search(g: G.graph,n: G.node) =
  let in
      G.is_first_node(g,n)
  end;
 end;

    structure MyGraph: GRAPH =
 struct
     (* an example implementation of a GRAPH structure *)

     type node = int * int list;
     type graph = node list;
     fun is_first_node(g,n) = hd(g)=n;
 end;

Alas, unless you want to switch to SML, you have to make do with
templates in C++.

    Thomas.

PS: such questions should probably go to comp.object and comp.lang.c++,
but not comp.std.c++