From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Newsgroups: comp.object
Subject: Re: Passing functions as parameters in an OO environment
Date: 30 Sep 92 21:32:48 GMT
Article-I.D.: arolla.TMB.92Sep30173248
	<1992Sep23.104513.22660@ruby.comlab.ox.ac.uk>
	<1992Sep25.150611.24570@actrix.gen.nz>
	<TMB.92Sep28155404@arolla.idiap.ch>
	<MDAY.92Sep30100428@jukebox.lcs.mit.edu>
Reply-To: tmb@idiap.ch
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)
In-reply-to: mday@jukebox.lcs.mit.edu's message of 30 Sep 92 15:04:28 GMT

[My intention in these postings is not to "bash" OO programming.  It's
clearly a powerful and successful technique that has helped many
people solve lots of problems. However, I think it would also be good
not to fall into the trap of viewing it as "the only way" to achieve
data abstraction, and, hence, I think a discussion like the present
one is useful. But if nobody on comp.object is interested, I'll stop.]

In article <MDAY.92Sep30100428@jukebox.lcs.mit.edu> mday@jukebox.lcs.mit.edu (Mark Day) writes:

      tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

      [...] OOP is not the only way to program in terms of ADT's. OOP is
      one particular approach to programming in terms of ADT's, with its own
      strengths and limitations.

      What limitations, you will ask. Well, one of them is that it is
      difficult to represent a collection of related datatypes and
      operations on them simultaneously. For example, a definition of a
      "graph" may involve related "vertex" and "edge" types, and operations
      with the graph may have to operate on both "vertex" and "edge".
      However, in an OO setting, it is difficult to express the fact that
      only a "vertex" and an "edge" type that have been defined together can
      be used together. 

   While I agree with the first quoted sentence, I'm not sure I
   understand your justification and explanation following.  I think
   you're saying that (in your example) we have a situation like this:

   1. vertex is a type implemented by classes vc1 and vc2
   2. edge is a type implemented by classes ec1 and ec2
   3. ec1 and vc1 can be used together
   4. ec2 and vc2 can be used together
   5. ec1 is not compatible with vc2
   6. ec2 is not compatible with vc1

   If this is roughly your scenario, can you explain how you express
   these constraints in some other (non-OO) framework?

Sure. Essentially, constraints between abstract datatypes like these
can be expressed by a module system. One of the more powerful ones is
that of SML. Modules are called "structures". The interface to a
structure is called a "signature". It gives the names of entities
defined in a structure, together with their type relationships
(extended versions of ML also let you express semantic relationships
and invariants). So, for a GRAPH, this would look as follows:

signature GRAPH =
    sig
	type vertex
	type edge
	val is_incident : vertex * edge -> bool
	val make_edge : vertex * vertex -> edge
	...
    end;

This says that the concept of a GRAPH consists of two types, "vertex"
and "edge", and that there are a bunch of values (functions, in this
case) associated with those types. For example, "is_incident" is a
function taking a "vertex" and an "edge" as arguments (those same
types that were mentioned previously) and returns a boolean.

Now, this by itself is just notation. In fact, I think even the
Modula-2 module system probably lets you do pretty much the same
thing. By itself, this isn't very useful. What makes it useful is that
you can write rules about how to derive new collections of datatypes
and operations from old collections of datatypes.

To illustrate this with a more commonly known example, let us take the
example of a mathematical GROUP and a mathematical FIELD. In the above
notation, we can define them as shown below.

(I'm sorry if this SML code looks incomprehensible to you; for a
casual reading, you can simply skip the code. The important points
are: you can define interfaces to collections of datatypes and
operations, and you can write rules ("functors") that take such
collections and transform them in non-trivial ways, ways that could
not be expressed using inheritance. Note that everything below has
been type checked, but it is still completely generic, i.e., it
applies to anything that satisfies the GROUP signature, and it is
guaranteed to make a valid FIELD out of it).


signature GROUP =
   sig
       type element
       val equal : element * element -> bool
       val identity : element
       val multiply : element * element -> element
       val inverse : element -> element
   end;

signature FIELD =
   sig
       type element
       val equal : element * element -> bool
       val add : element * element -> element
       val multiply : element * element -> element
       val zero : element
       val one : element
       val additive_inverse : element -> element
       exception DivisionByZero
       val multiplicative_inverse : element -> element
   end;

functor MakeField(structure AdditiveGroup: GROUP
                  and MultiplicativeGroup: GROUP
		  sharing type AdditiveGroup.element =
		               MultiplicativeGroup.element): FIELD =
    struct
	type element = AdditiveGroup.element
	val equal = AdditiveGroup.equal
	val add = AdditiveGroup.multiply
	val multiply = MultiplicativeGroup.multiply
	val zero = AdditiveGroup.identity
	val one = AdditiveGroup.identity
	val additive_inverse = AdditiveGroup.inverse
	exception DivisionByZero
	val multiplicative_inverse =
	    fn x => if equal(x,zero) then
                        raise DivisionByZero
                    else
                        MultiplicativeGroup.inverse(x)
    end;

(Note that you could formulate some aspects of a module system like
this as "inheriting class-local class definitions". However, it isn't
clear to me that the resulting system would be as powerful or as
straightforward. Furthermore, in the above examples, there never
exists an object of type GRAPH, FIELD, or GROUP; hence, it doesn't
seem sensible to press their definition into the shape that might let
me instantiate them as an object.)

      Another limitation is that the only form of deriving
      one structure from another is inheritance, which allows you to add
      members but not remove them; a lot of mathematical relationships are
      more conveniently expressed by starting out with some complicated
      mathematical object and "forgetting" some of its structure.

   I don't think this is correct.  It's true that when a type S is
   intended to be a subtype of type T, the only way to ensure this is to
   have all the functionality of type T included in type S.  But if you
   want to define an entity as inheriting from some other entity (or
   collection of entities), the newly-defined entity doesn't have to be a
   subtype of any of the types of the entities from which it inherits.
   The net effect is that the newly-defined entity can be "like" the old
   entity/entities, but "missing" some of their baggage.  

   I know that in lots of OO languages the notions of subtyping and
   inheritance are tangled, but they are and should be distinct.
   Whatever the virtues or vices of inheritance may be, I think your
   complaint here is more based on being forced to express subtype
   relationships where you don't want to.

Well, the complaint is more general. I don't only want to derive one
type from another, but I want to derive one "structure" or "module"
from other "structures" or "modules".

Inheritance and subtyping really solve a different problem from these
module operations; inheritance and subtyping let you replace one
object by another object if that latter object has a "superset of the
functionality of the former object". Inheritance is the mechanism that
guarantees that the functionality of the subtype is a superset of that
of the base type, and subtyping is what expresses this relationship to
the type system.  I have no problem with inheritance and subtyping,
and I actually think they are so closely related that they _should_ be
intermingled.

The intermingling that bothers me in OO languages is the intermingling
of "module" facilities like those of SML with notions of inheritance.
Almost by accident, inheritance comes along with a facility which
happens to give you _limited_ forms of interface definitions (abstract
base classes in C++, the limited equivalent of signatures in SML),
_limited_ forms of packaging operations with data (namely, class scope
for those functions that happen to take class objects as their first
argument), and _limited_ forms of mapping between such packages.

In my mind, the success of OO technology is attributable to the fact
that these _limited_ data abstraction/module facilities are better
than having none at all. In fact, from a practical point of view, they
are not so limited, since maybe 90% of all abstractions don't need
anything more powerful since they really only involve a single type.

The fact that OO technology also happens to give you dynamic method
dispatch to me is an additional notational convenience, but a quite
separate facility from the abstraction facilities that come along with
OO. In fact, I think it is laudable that C++ separates the two and
gives you dynamic method dispatch only if you ask for it (via
"virtual").  The general consensus that not using "virtual methods" in
C++ means that you are not "really doing OO programming" underlines my
point: C++'s extensions without "virtual" are merely a limited form of
a module system; "virtual" is what makes the simple "C++ module
system" into OO technology.

What does all of this imply for OO programming and languages? There
are a number of complaints and confusions that constantly come up when
people program in OO languages, generally related to such questions as
"contravariance", "reverse assignment", "downcasting", and "should I
inherit or forward". I think these confusions are symptomatic of an
attempt to squeeze more powerful module facilities (like those of SML)
into the limited framework of classes. It can't work because a class
defines only a single datatype and operations on it (multimethods
don't solve this problem either).

In my programs (which I don't think are particularly atypical:
graphics, geometric algorithms, numerical code), I am in much greater
need of powerful facilities for data abstraction and static type
checking than the notational convenience of method dispatch. That's
why I prefer the powerful ADT/module facilities of a language like SML
to the more restricted ADT/module facilities of a language like C++,
even though C++ gives me virtual functions (NB: SML also has
first-class functions, which make the lack of virtual functions less
significant).

					Thomas.

PS: In case you were wondering, I write about half of my code in C++
and the other half in SML.
Newsgroups: comp.object