Path: utzoo!utgpu!watmath!att!dptg!rutgers!psuvax1!brutus.cs.uiuc.edu!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!hsi!wright
From: wright@hsi.UUCP (Gary Wright)
Newsgroups: comp.lang.c++
Subject: Re: When to make member functions?
Keywords: member functions, c++
Message-ID: <569@hsi86.hsi.UUCP>
Date: 30 Aug 89 15:25:29 GMT
References: <1267@pc.ecn.purdue.edu> <2506@fai.UUCP> <565@hsi86.hsi.UUCP> <1230@tukki.jyu.fi>
Reply-To: wright@hsi.com (Gary Wright)
Organization: Health Systems Intl., New Haven, CT.
Lines: 184

In article <1230@tukki.jyu.fi> markku@jytko.jyu.fi (Markku Sakkinen) SAKKINEN@FINJYU.bitnet (alternative) writes:
>In article <565@hsi86.hsi.UUCP> wright@hsi.com (Gary Wright) writes:
>-In article <2506@fai.UUCP> kurtl@fai.fai.com (Kurt Luoto) writes:
>->Since there are so many things that you can do with a graph, it seems silly
>->to encumber a simple graph class with all kinds of algorithmic functions.
>->On the other hand, in other OOP languages you have no choice. E.g. in Eiffel,
>->functions only exist as members of some class.  What is appropriate for C++?
>->(Honest, I am not trying to start any flame wars here.)
>-
>-1. Design an abstract graph class with no commitment to any 
>-   particular implementation.
>-2. Inherit from your abstract class, and define the implementation.
>-3. Inherit once more from a specific implementation of your graph
>-   class and add the computationally expensive algorithms at
>-   this step.  This step may also include adding state to the
>-   various nodes in the graph in order to implement some graph
>-   algorithms.
>-
>-This is an over-simplification but [...]
>- ...
>
>Recommendations 1 and 2 above make sense,
>but I think that recommendation 3 goes exactly the wrong way round.
>The original question was about functions that are independent
>of the particular realisation, i.e. written in terms of the general
>public interface of the abstract graph class.
>In my opinion, such functions should be _implemented_ in the abstract class.

I have a feeling that we are both using terminology in subtly different ways.
I also think that while I have multiple inheritance in mind, Markku does not.

I'll try to elaborate.  Disclaimer: I am more familiar with Eiffel and
it's inheritance mechanisms than with C++.  I will try to make things
clear enough but it is my general feeling that it may not be possible
to convert certain Eiffel techniques directly into C++.

Clearly, you could have any number of abstract graph classes.  Some
would not include any complex "algorithmic" queries of the underlying
graph, some would.  It is also clear that some algorithms to determine
characteristics of a graph can be "written in terms of the general
public interface of the abstract graph class."  

When designing the abstract graph class, you would like to include 
enough features so that any algorithm can be written in terms of this
interface.  This is the problem of determining the primitive operations
that an abstract graph class should provide.  Some algorithms
written in this way may be efficient, other may not.  For efficiency,
you may want an algorithm to know about the internal implementation of
the graph.

For simplicity, I will refer to the three classes I suggested in my 
previous posting as (1) abstract, (2) simple, (3) complex.

My understanding is that Markku is suggesting that functions that can
be written in terms of the abstract interface be included in (1) and as
such will also be come part of the abstract interface.  My problem with
this approach is that it prevents reuse of the abstract class.  What if
later on, I need to use a graph in some other application and it is not
necessary to have all the complicated graph algorithms?  

As mentioned above, some algorithms may need more than the primitive
graph structure in order to be implemented in an efficient way.  This
extra information should be in a separate class, not in (1) or direct
heirs of (1).  I would suggest using multiple inheritance and
deferred classes (abstract classes) to achieve this.  

I would go about creating my family of graph classes by first
defining a deferred graph class "GRAPH" that only contained the minimum number
of member functions, and none of the more complex "graph theoretic functions".

I would inherit from GRAPH and define the various functions in terms
of a specific implementation (i.e. FIXED_GRAPH, a graph with a fixed maximum
number of nodes and arcs).  This class will still be a basic graph class, 
but it would be fully implemented.

Now, let's assume I am interested in the shortest path between two nodes
of a graph.  Let's define the function as:

	short_path(start: NODE, finish: NODE): LIST[NODE];

Instead of including this function as part of GRAPH or FIXED_GRAPH, I'll
put it in a new class called GRAPH_QUERY.  This class will be a deferred
class, any of the graph primitives that my algorithm might need are deferred.
The function short_path() is defined in terms of the deferred primitives.
I will also need a weight associated with each arc of the graph, so I'll
create a class WEIGHTED_GRAPH by inheriting from FIXED_GRAPH, and 
providing a new implementation of arcs.  

Actually, I might want to use parameterized types here:
	
	class WEIGHTED_GRAPH exports
		...
		weight,
		...
	inherits
		FIXED_GRAPH[ WEIGHTED_ARC, NODE];
	features
		weight( arc: WEIGHTED_ARC) : INTEGER is do
			Result := arc.weight;	-- Result is the returned value
		end;
		...
	end -- WEIGHTED_GRAPH

So now for my final class, I use multiple inheritance to get the implementation
of a graph from WEIGHTED_GRAPH, and the implementation (e.g. Dijkstra's) for
short_path from GRAPH_QUERY.

	class FINAL_GRAPH exports
		...
		short_path,
		...
	inherits
		WEIGHTED_GRAPH;
		GRAPH_QUERY
	features
		...
	end -- FINAL_GRAPH

The idea is that WEIGHTED_GRAPH provides an implementation of
weight() that GRAPH_QUERY needs (i.e., weight() is deferred in
GRAPH_QUERY).  As long as there is only one parent that provides an
implementation of a particular function, it doesn't matter how many
parents provide a deferred version of it.

GRAPH_QUERY may actually contain a number of interesting algorithms
packaged together instead of having a separate class for each
algorithm.

>This is both conceptually logical and avoids code duplication.
>For safety's sake you could declare some or all of those functions
>virtual if you might some day want to write essentially more efficient
>versions of them for some specific cases.

I believe the best technique is to always declare functions virtual
and then to inline them when it is determined that that will improve
efficiency.  In Eiffel all functions are virtual.  An optimizing pass
can examine the text of a class and inline appropriate functions or
create static linkage if the function is never redefined, like
weight in my example which is just a simple assignment.

>
>My suggestion for the more general question (When to make functions
>members of classes and when not?) is much more a matter of taste.
>1. If a function needs to access private or protected members of the class,
>   make it a member function unless there are strong logical reasons
>   to the contrary (it must then be declared a friend, of course).
>   There is some more technical discussion about this in Stroustrup's
>   book (6.10).

I think that the use of multiple inheritance can remove the need for
using friend functions.

>2. If a function needs to access private or protected members of
>   _several_ classes, make it a friend of all those classes;
>   but if it is clearly most intimately connected with one class,
>   make it a member of that one a friend of the others.

Why not just create a new class through inheritance and add the desired
function to the class?  I think you are focusing too much on functions
and not enough on objects.  You really need to change the way you look
at a problem in order to really utilize OOP techniques.

>3. If a function needs no access to any private or protected class members,
>   make it an ordinary function unless there are strong logical reasons
>   for making it a member function of some class. (I think there are
>   such reasons in the graph example.)

This function should not be sitting around globally, it should also
be a member function of some class.  This class may be a deferred class
so that the function can be combined with other classes to build a more
complex class that you need for a specific application.

I understand that with single inheritance, many of these techniques can
not be used, and you do indeed need to use friend functions and the
like.  I think the graph example illustrates the power of multiple
inheritance very well.  My use of parameterized types is not possible in
C++ 2.0 (anyone know about g++?).  I don't know if deferred routines
can be combined with non-deferred routines using multiple inheritance
in C++.  Maybe someone else can comment on how to handle this in C++.

I apologize for the length of this posting.  I hope it was worth it.
-- 
Gary Wright 					...!uunet!hsi!wright
Health Systems International                    wright@hsi.com