From: graham@maths.su.oz.au (Graham Matthews)
Subject: Method Dispatching
Organization: School of Mathematics and Statistics, University of Sydney
Date: Sun, 23 Aug 1992 04:56:22 GMT

I have recently been working on some object based extensions 
to an algebraic programming language I have implemented.
I decided to do an example - to write a class for the Rational 
field and its elements. This article talks of a problem I
have encountered in doing so - a problem which is perhaps 
pervasive in object oriented programming, even if not explicitly
so.

Lets say we want to represent our rational field elements
as pairs <a,b>, a giving the enumerator, b the denominator
in the standard way.

Say we want to implement rational multiplication, and the 
ability to index a rational to extract the enumerator and
denominator. i.e: we want to be able to write

	a * b

where a and b are elements of the rational field, and

	a[1]
	a[2]

where a is an element of the rational field.

So we have two generic "function" (imagine operators as
functions) signatures,

	*	:	ratelt, ratelt -> ratelt
	[]	:	ratelt, integer -> integer

So now I envisage writing a class (type) to implement these 
function signatures. So I write,

	class ratelt

		representation: Tuple< integer, integer >;

		* := 
			function( a, b )
				return < a[1] * b[1], a[2] * b[2] >;
			end function;

		[] :=
			function( a, i )
				return a[i];
			end function;

	end class;

NOTE: 
i) the "representation : Tuple.." is meant to indicate how
instances of this class are to be represented. The problem
of how to indicate this forms the basis of my problem, so
read on.
ii) the notation <..> constructs a tuple.
iii) I have cast the example in terms of generic functions
a la CLOS, but the examples could be easily re-written
in other notations and my point would remain the same.

Ok so far this seems fine, but there is a problem with it
which is demonstrated by the following example. Say I now
have two rational field elements, a and b, and I write,

	temp := a * b;

Lets trace what happens here :-

a) the function binder takes the types of a and b and looks for
a function with the name "*" and the argument specification
"ratelt, ratelt". The function binder returns successfully
with the function "*" in class ratelt as the target function.

b) function "*" in class ratelt is invoked. The first thing it
does is the operation "a[1]".

c) the function binder takes the types of a and 1 and looks for
a function with the name "[]" and the argument specification
"ratelt, integer". The function binder returns successfully with
the function "[]" in class ratelt as the target function.

d) the function "[]" in class ratelt is invoked. The first thing
it does is the operation "a[i]".

e) the function binder takes the types of a and 1 and looks for
a function with the name "[]" and the argument specification
"ratelt, integer". The function binder returns successfully with
the function "[]" in class ratelt as the target function.

f) the function "[]" in class ratelt is invoked. The first thing
it does is the operation "a[i]".

...

NOTE the infinite loop here.

Now this loop is caused by the fact that in step c) what we really
want to do is use our *representation* and look for a function with
the name "[]" and argument specification "tuple, integer"! The
function binder would pick up tuple indexing as system supplied
and at just do it (the system I work with supplies tuples as a
fundamental data structure).

So the question is how can the function binder know when it is time
to use the representation and forget the typing information. The
answer is not at all clear. Clearly you don't want to do that all the
time as otherwise the original "temp := a * b" would never get to
the function "*" in class ratelt. If we used the representation
immediatley we would try to multiply two tuples. At some point in
this lookup chain we want to change to the representation and forget
the type. Where is this point?

You may ask how this problem is handled in an object oriented language
and the answer is that it is left to the programmer, although not 
obviously so. A programmer would write the ratelt class as follows,

	class ratelt

		val : Tuple< integer, integer >;

		* := 
			function( a, b )
				return < a[1] * b[1], a[2] * b[2] >;
			end function;

		[] :=
			function( a, i )
				return a.val[i];
			end function;

	end class;

NOTE: once again the notation for "val : Tuple..." will vary from
language to language but my point remains the same.

In the "[]" function the programmer uses "a.val" instead
of "a". "val" is basically a name for the representation of a ratelt
and the programmer is forced to explicitly note where he/she wishes
to start using the representation rather than the type information
(it is not of course presented in such terms in the object oriented 
literature, but this is what is happening).

While I do not like forcing the programmer to deal with the change 
to a representation based lookup I see no way to avoid it as I cannot
see an (efficient) algorithm whereby the system can do it automatically.
I can see an inefficient algorithm I think.

You may wonder why I am asking this question, well I am asking it
because I am interested in partial re-use of class methods. I really
want to write my ratelt class as follows,

	class ratelt

		representation : Tuple< integer, integer >;

		* := 
			function( a, b )
				return < a[1] * b[1], a[2] * b[2] >;
			end function;

		[] := given by Tuple.[]

	end class;

Or something like that (ideally in fact I just want the system
to figure out how [] is implemented since it knows the element
representation). I want to re-use tuple.[] much more obviously 
than having to have a name for the representation (ie. a variable
in the class) and go through that.
	
Comments?

graham
--
Graham Matthews                 And it's true we are immune
Pure Math, Uni.Sydney, Oz       When fact is fiction and T.V. is reality
graham@maths.su.oz.au