[comp.lang.c++] conceptual problem with related classes derived in parallel

sherouse@godot.radonc.unc.edu (George W. Sherouse) (09/27/89)

Consider a class used for maintaining dynamically-allocated lists of
things.

class element
{
protected:
    data_type data;
public:
    virtual data_type data_accessor();
};

class list_of_elements
{
protected:
    element* list;
public:
    add_element_to_list(element);		<- uses malloc/realloc
};

Suppose then we derive a new class of element from element

class new_element: public element
{
protected:
    other_data_type other_data;
};

and a derived class of list_of_element to maintain the new elements

class list_of_new_element: public list_of_element
{
...
protected:
    new_element_manipulator();
};

Or, schematically:

	list         -- points to ->        element
         |                                     |
       derive                               derive
	 v                                     v
      new_list  -- would like to access -> new_element

The intent here is to reuse list maintenance code from the base
list_of_element class in the derived list_of_new_element class which
operates on the dervived data class new_element.  The scheme above
does not work because for either class of list this->list[n] is always
an instance of the base element class.  Without a cast,
new_list_manipulator will not be able to access other_data.
Similarly, add_element_to_list will not be able to divine the correct
size for the elements.

A number of solutions come to mind, but none particularly satisfying
from a philosophical point of view.

- casts would do the trick, but that would require that all of the
methods of list_of_elements be reimplemented for each derived class.

- one could leave the pointer to element out of the base class and
only introduce the pointer to derived classes of element at
appropriate levels in the list hierarchy.  This also requires
re-implementation of essentially identical list maintenance code in
derived classes.

- define the base class of element to have all possible values for all
possible derived classes of element.  Yuck.  This requires that the
base class be redefined in order to add new derived classes.

- give up and create a family of mostly-identical list classes that
share code by using non-method friend procedures - the moral
equivalent of goto.

This same problem in a number of different guises has cropped up in
different parts of a project we are working on.  Are we missing
something obvious here?  Are we missing something subtle?  It appears
that what we are really looking for is support for virtual data types.
Any help out there?

- George

sherouse@godot.radonc.unc.edu (George W. Sherouse) (10/02/89)

Consider a class used for maintaining dynamically-allocated lists of
things.

class element
{
protected:
    data_type data;
public:
    virtual data_type data_accessor();
};

class list_of_elements
{
protected:
    element* list;
public:
    add_element_to_list(element);		<- manages dynamic memory
};

Suppose then we derive a new class of element from element

class new_element: public element
{
protected:
    other_data_type other_data;
};

and a derived class of list_of_element to maintain the new elements

class list_of_new_element: public list_of_element
{
...
protected:
    new_element_manipulator();
};

Or, schematically:

	list         -- points to ->        element
         |                                     |
       derive                               derive
	 v                                     v
      new_list  -- would like to access -> new_element

The intent here is to reuse list maintenance code from the base
list_of_element class in the derived list_of_new_element class which
operates on the dervived data class new_element.  The scheme above
does not work because for either class of list this->list[n] is always
an instance of the base element class.  Without a cast,
new_list_manipulator will not be able to access other_data.
Similarly, add_element_to_list will not be able to divine the correct
size for the elements.

A number of solutions come to mind, but none particularly satisfying
from a philosophical point of view.

- casts would do the trick, but that would require that all of the
methods of list_of_elements be reimplemented for each derived class.

- one could leave the pointer to element out of the base class and
only introduce the pointer to derived classes of element at
appropriate levels in the list hierarchy.  This also requires
re-implementation of essentially identical list maintenance code in
derived classes.

- define the base class of element to have all possible values for all
possible derived classes of element.  Yuck.  This requires that the
base class be redefined in order to add new derived classes.

- give up and create a family of mostly-identical list classes that
share code by using non-method friend procedures - the moral
equivalent of goto.

This same problem in a number of different guises has cropped up in
different parts of a project we are working on.  Are we missing
something obvious here?  Are we missing something subtle?  It appears
that what we are really looking for is support for virtual data types.
Any help out there?

- George

ttwang@polyslo.CalPoly.EDU (Thomas Wang) (10/02/89)

sherouse@godot.radonc.unc.edu (George W. Sherouse) writes:

>Consider a class used for maintaining dynamically-allocated lists of
>things.

>class element
>{
>protected:
>    data_type data;
>public:
>    virtual data_type data_accessor();
>};

>	list         -- points to ->        element
>         |                                     |
>       derive                               derive
>	 v                                     v
>      new_list  -- would like to access -> new_element

The problem with your code is that you only provided a data accessor
function in the 'element' class.  The central concept of object oriented
programming is 'what do you do with an object', not how do you access them.

I used to write this type of classes:

class int_type
{
  int the_int;
public:
  int get_int();
  void set_int(int);
};

until I realize that I should do this:

class int_type 
{
  int the_int;
public:
  int_type();
  ~int_type();
  void print();
  void plus(int);
  void minus(int);
  void multiply(int);
};

>This same problem in a number of different guises has cropped up in
>different parts of a project we are working on.  Are we missing
>something obvious here?  Are we missing something subtle?  It appears
>that what we are really looking for is support for virtual data types.
>Any help out there?

If one knows what to do with a class, then virtual functions can replace
the need of virtual data objects.

>- George

 -Thomas Wang (Ah so desu ka!)

                                                     ttwang@polyslo.calpoly.edu

dld@F.GP.CS.CMU.EDU (David Detlefs) (10/02/89)

George Sherouse writes, paraphrased:

> I want to write a "list" class once, and reuse the code for lists of
> various things. Inheritance doesn't seem to work.  What am I doing wrong?

Congratulations!  You have reached a state of object-oriented
enlightenment in which you realize that inheritance is not the
solution to all software organization problems.  This is a good thing.
Only zealots would claim otherwise.

What you really want here is a "parameterized type."  In some future
version of C++ you will be able to write something like

template <class T> class list<T> {
  protected:
    T* elems;
  public:
    void add_elem(T elem);
}

Which you could then use by simply writing

list<A> or list<B> as a type in your code.  In your example, there was
no obvious reason why "element" and "new_element" were related by
inheritance, other than that you thought they should be in order to
make the list work.  In this scheme, you can leave them as unrelated
types, unless there really is a good reason to derive new_element from
element.

As I said, Parameterized types are a future feature, but for the time
being, you can get the same effect by writing list<T> as a
preprocessor macro (or 2 macros, one for the declaration and one for
the definition).  See Stroustrup p. 210.

Hope this helps.

Dave




--
Dave Detlefs			Any correlation between my employer's opinion
Carnegie-Mellon CS		and my own is statistical rather than causal,
dld@cs.cmu.edu			except in those cases where I have helped to
				form my employer's opinion.  (Null disclaimer.)

sherouse@godot.radonc.unc.edu (George W. Sherouse) (10/02/89)

[ I am sorry if you have seen this more than once.  We have been
experiencing local lapses in net service...]

Consider a class used for maintaining dynamically-allocated lists of
things.

class element
{
protected:
    data_type data;
public:
    virtual data_type data_accessor();
};

class list_of_elements
{
protected:
    element* list;
public:
    add_element_to_list(element);		<- uses malloc/realloc
};

Suppose then we derive a new class of element from element

class new_element: public element
{
protected:
    other_data_type other_data;
};

and a derived class of list_of_element to maintain the new elements

class list_of_new_element: public list_of_element
{
...
protected:
    new_element_manipulator();
};

Or, schematically:

	list         -- points to ->        element
         |                                     |
       derive                               derive
	 v                                     v
      new_list  -- would like to access -> new_element

The intent here is to reuse list maintenance code from the base
list_of_element class in the derived list_of_new_element class which
operates on the dervived data class new_element.  The scheme above
does not work because for either class of list this->list[n] is always
an instance of the base element class.  Without a cast,
new_list_manipulator will not be able to access other_data.
Similarly, add_element_to_list will not be able to divine the correct
size for the elements.

A number of solutions come to mind, but none particularly satisfying
from a philosophical point of view.

- casts would do the trick, but that would require that all of the
methods of list_of_elements be reimplemented for each derived class.

- one could leave the pointer to element out of the base class and
only introduce the pointer to derived classes of element at
appropriate levels in the list hierarchy.  This also requires
re-implementation of essentially identical list maintenance code in
derived classes.

- define the base class of element to have all possible values for all
possible derived classes of element.  Yuck.  This requires that the
base class be redefined in order to add new derived classes.

- give up and create a family of mostly-identical list classes that
share code by using non-method friend procedures - the moral
equivalent of goto.

This same problem in a number of different guises has cropped up in
different parts of a project we are working on.  Are we missing
something obvious here?  Are we missing something subtle?  It appears
that what we are really looking for is support for virtual data types.
Any help out there?

- George

ttwang@polyslo.CalPoly.EDU (Thomas Wang) (10/03/89)

If what you want is the ability to insert any class of objects into the
list, and at the same time maintain some sort of code re-use, I have some
sort of solution for you.

You must have one single base class that does nothing except building up
a framework for future inheritance.

class god_t
{
private:
  static char* original_name;
protected:
  char* my_name; // the name of the class
public:
  god_t();
  char* class_name() { return my_name; }
  virtual char knows(char*);
};
god_t::god_t()
{
  my_name = original_name = "god_t";
}
virtual char god_t::knows(char* name)
{
  return original_name == name;
}
class int_t: public god_t
{
private:
  static char* original_name;
public:
  int_t();
  virtual char knows(char*);
...
};
int_t::int_t()
{
  my_name = original_name = "int_t";
}
virtual char int_t::knows(char* name)
{
  return (original_name == name) || god_t::knows(name);
}

Now that you always know what class an object is, so you can safely
typecast in an if statement:

god_t* node;
...
if (node->knows(chocolate_t::original_name))
  ((chocolate*) node) ->eat_chocolate();
else
  cout << "cannot eat a non-chocolate object\n";

eat_chocolate() should be a virtual function.


 -Thomas Wang ("This is a fantastic comedy that Ataru and his wife Lum, an
                invader from space, cause excitement involving their neighbors."
                  - from a badly translated Urusei Yatsura poster)

                                                     ttwang@polyslo.calpoly.edu

ttwang@polyslo.CalPoly.EDU (Thomas Wang) (10/03/89)

ttwang@polyslo.CalPoly.EDU (Thomas Wang) writes:
>If what you want is the ability to insert any class of objects into the
>list, and at the same time maintain some sort of code re-use, I have some
>sort of solution for you.

My original reply had some code bugs, so here is the correction:

class god_t
{
private:
  static char id;
protected:
  char* my_id; // the id pointer of the class
public:
  god_t();
  char id_equal(char& the_id) { return my_id == &the_id; }
  virtual char knows(char&);
};
god_t::god_t()
{ my_id = &id; }
virtual char god_t::knows(char& the_id)
{ return &the_id == &id; }
class int_t: public god_t
{
private:
  static char id;
public:
  int_t();
  virtual char knows(char&);
...
};
int_t::int_t()
{ my_id = &id; }
virtual char int_t::knows(char& the_id)
{ return (&the_id == &id) || god_t::knows(the_id); }

Now that you always know what class an object is, so you can safely
typecast in an if statement:

god_t* node;
...
if (node->knows(chocolate_t::id)) // node is a derived class of chocolate_t
  ((chocolate*) node) ->eat_chocolate();
else
  cout << "cannot eat a non-chocolate object\n";

...
if (node->id_equal(chocolate_t::id)) // node is exactly class chocolate_t
  cout << "I am class chocolate_t\n";
else
  cout << "I am not class chocolate_t\n";

eat_chocolate() should be a virtual function.


 -Thomas Wang ("This is a fantastic comedy that Ataru and his wife Lum, an
                invader from space, cause excitement involving their neighbors."
                  - from a badly translated Urusei Yatsura poster)

                                                     ttwang@polyslo.calpoly.edu

jlk@daimi.dk (Jorgen Lindskov Knudsen) (10/03/89)

In article <1071@godot.radonc.unc.edu> George W. Sherouse writes:
>
>Consider a class used for maintaining dynamically-allocated lists of
>things.
>
... Various class definitions deleted ...
>Or, schematically:
>
>	list         -- points to ->        element
>         |                                     |
>       derive                               derive
>	 v                                     v
>      new_list  -- would like to access -> new_element
>
>The intent here is to reuse list maintenance code from the base
>list_of_element class in the derived list_of_new_element class which
>operates on the dervived data class new_element.  The scheme above
>does not work because for either class of list this->list[n] is always
>an instance of the base element class.  Without a cast,
>new_list_manipulator will not be able to access other_data.
>Similarly, add_element_to_list will not be able to divine the correct
>size for the elements.
>
>A number of solutions come to mind, but none particularly satisfying
>from a philosophical point of view.
>
... stuff deleted ...
>This same problem in a number of different guises has cropped up in
>different parts of a project we are working on.  Are we missing
>something obvious here?  Are we missing something subtle?  It appears
>that what we are really looking for is support for virtual data types.
>Any help out there?

And in article <DLD.89Oct2113011@F.GP.CS.CMU.EDU> David Detlefs writes:

>Congratulations!  You have reached a state of object-oriented
>enlightenment in which you realize that inheritance is not the
>solution to all software organization problems.  This is a good thing.
>Only zealots would claim otherwise.
>
>What you really want here is a "parameterized type."  In some future
>version of C++ you will be able to write something like
>
>template <class T> class list<T> {
>  protected:
>    T* elems;
>  public:
>    void add_elem(T elem);
>}
>
>Which you could then use by simply writing
>
>list<A> or list<B> as a type in your code.  In your example, there was
>no obvious reason why "element" and "new_element" were related by
>inheritance, other than that you thought they should be in order to
>make the list work.  In this scheme, you can leave them as unrelated
>types, unless there really is a good reason to derive new_element from
>element.
>
>As I said, Parameterized types are a future feature, but for the time
>being, you can get the same effect by writing list<T> as a
>preprocessor macro (or 2 macros, one for the declaration and one for
>the definition).  See Stroustrup p. 210.
>
>Hope this helps.

There is another side of this coin, namely that the generality of most
objetc-oriented languages of today isn't sufficient.  That is, the problem
pointed out by George W. Sherouse is indeed an object-oriented problem, but
without solutions in C++.  George W. Sherouse is also thinking in the right
direction, when he is seeking for virtual data types.

Solutions by means of parameterized types or macros can be usefull in many
respects, but if used to solve problems within the object-oriented framework,
they seem counterintuitive.  Just to name one significant problem, you might
consider the problem of parameterized types not being first-class citizens of
the language, implying than you are unable to create code that enables you to
manipulate the types on the level of the parameterized type, but is forced
allways to work on the level of the concrete type.

The BETA language (a tutorial is being held on that language on OOPSLA tpday)
supports the specification of virtual classes.  The language is documented
various places, e.g. in Wegner & Shriver (Eds.): Research Directions in
Object-Oriented Programming, MIT Press, 1987.  The solution to your problem
would in Beta be (except for minor syntactical issues):

element: class (# data: @data_type; 
		  data_accessor: virtual proc (# ... #):
	       #)

new_element: class (# other_data: @other_data_type #);

list_of_elements: class (# element_type: virtual class element;
			   list: ^element_type;
			   add_element_to_list: proc(e: element_type) (# ... #)
			#)

list_of_new_elements: list_of_elements class (#
			   element_type: extended class new_element;
			   new_element_manipulator: proc() (# ... #);
			#)

Now, list_of_new_elements will be hold new_element objects, and
new_element_manipulator will be able to securely access other_data (strongly
typed).

For further information on virtual classes, see the paper by Ole Lehrmann
Madsen and Birger Moller-Pedersen: Virtual Classes: a Powerfull Mechanism in
Object-Oriented Programming, OOPSLA'89 (will be presented on Friday).
-- 
---> Jorgen Lindskov Knudsen / jlknudsen@daimi.dk
---> Computer Science Department, Aarhus University
---> Ny Munkegade 116, DK-8000 Aarhus C, DENMARK
---> Phone: +45 86 12 71 88 / telefax: +45 86 13 57 25 / telex: 64767 aausci dk


---> Jorgen Lindskov Knudsen / jlknudsen@daimi.dk
---> Computer Science Department, Aarhus University
---> Ny Munkegade 116, DK-8000 Aarhus C, DENMARK
---> Phone: +45 86 12 71 88 / telefax: +45 86 13 57 25 / telex: 64767 aausci dk