Path: utzoo!utgpu!attcan!uunet!tektronix!tekcrl!soiffer
From: soiffer@tekcrl.CRL.TEK.COM (Neil Soiffer)
Newsgroups: comp.lang.c++
Subject: generic arithmetic question
Message-ID: <3243@tekcrl.CRL.TEK.COM>
Date: 5 Nov 88 00:28:03 GMT
Reply-To: soiffer@tekcrl.CRL.TEK.COM (Neil Soiffer)
Organization: Tektronix, Inc., Beaverton,  OR.
Lines: 120
Keywords:

I am fairly new to c++ and would appreciate suggestions on how to write
a generic arithmetic package in c++.  By "generic", I mean I would
like to be able to write functions whose arguments can be of type "number"
and not a specific type like int, float, complex, rational, etc.
As a trivial example, I would like to be able to write a generic exponentiation
function that works by repeated squaring.  A generic class is useful not
only for writing general purpose generic arithmetic functions, but also for
writing programs where the specific type of the operands is unknown (eg, in a
calculator that reads many types of numbers).

The "obvious" solution to this problem is to write an abstract class
"number" and derive concrete classes (such as fixnum, rational, etc) from
it.  A solution along this line of thought is shown below:

------------------------------------------------

#include <stream.h>

class fixnum;	// forward ref
class rational;	// forward ref

class number {
public:
    virtual number& operator+(number&) {return *this;};	 // abstract function
    virtual number& operator+(fixnum&) {return *this;};	 // abstract function
    friend ostream& operator<<(ostream& s, number& num) {return num.print(s);};
protected:
    virtual ostream& print(ostream& s) {return s;};	 // abstract function
};


class fixnum: public number {
public:
    fixnum(int num) { n = num; };
private:
    int n;
    number& operator+(number& num) { return(num + *this); };  // double dispatch
    number& operator+(fixnum& num) { return *new fixnum(n + num.n); };
    ostream& print(ostream& s) {return s << n;};
};


void testfun(number &a, number &b)
{
    cout << a+b << "\n";
}

main()
{
    fixnum a = 3;
    fixnum b = 4;
    cout << "fix+fix: "; testfun(a, b);
}

--------------------------------------------------

The reason that there are two "+" functions is because in the first "+"
function, the type of the second argument is "number", and not "fixnum".
Thus, a double dispatch is used (Ingals refers to this as multiple-polymorphism
in his OOPSLA '86 paper).  Double dispatch can be avoided in languages that
provide a mechanism for multiple-polymorphism such as the Common Lisp Object
System (CLOS).  Double dispatch can also be used for handling arguments
whose types differ.

The solution presented above has at three problems with it.  The biggest
problem is that the class number must declare the abstract function
	virtual number& operator+(fixnum&)
In the general case, one such function must be declared for each derived
class's functions that use double dispatch (eg, +(number, fixnum),
*(number, fixnum), etc).  This violates an important condition for reuse
of inherited classes:  a base class should *never* need to know what its
derived classes are.

The second problem with the above solution is that even though the second
dispatch is written as an inline function, at least one more function call is
performed because of the vtable lookup (at least this is true of cfront 1.2.1).
Thus, this solution has a fairly high time overhead penalty.

The third problem with the above solution is that g++ (v1.27) won't
compile it.  The error messages are [including the spelling error]:
num.C:23: conficting specification deriving from virtual function `struct number
	 &number::operator + (struct number &)'
num.C:39: warning: excess elements in aggregate initializer


For those who are interested, Smalltalk does not use the double dispatch idea.
Smalltalk (by virtue of the language definition), does not have the modularity
problem mentioned above (function prototypes don't have to be declared).
Smalltalk's generic number code handles addition by using the following
two functions to check the type of the (second) argument:
    isMemberOf: aClass	true if self is an instance of 'aClass'
    isKindOf: aClass	true if self is an instance of 'aClass' or
			    any superclass of 'aClass'
Smalltalk's implementation uses these functions in a disciplined, modular
manner:  they are used only to check against the current class name (in
the above example, 'aClass' would be "fixnum").  A type check that uses
other than the current class's type hampers reusability because if a new type
is added (eg, 'gaussian integer'), then old code must be modified to
include the new type.

Smalltalk handles the addition of different types using the notion of
generality (to define the result type) and a method called "retry:coercing".
I'll let you guess what that does.

As I see it, the problem with c++ is that I can't specify the types of the
arguments precisely enough.  If we ignore type conversion possibilities,
the "+" operation in the above example really wants to have a signature:
    virtual T& operator+(T&, T&): T < number
Ie, "+" is a function on two arguments, both of exactly the same type and
that type is also the return type.  T must be a subtype of 'number'.
This would allow me to write just one function and avoid the second dispatch.

As mentioned way back at the beginning of this message, I'm interested
in any suggestions anyone has for a good solution.

	Neil Soiffer
	Textronix Computer Research Lab
	UUCP:  ...!tektronix!tekchips!soiffer
	ARPA:  soiffer%tekchips.tek.com@relay.cs.net
	CSNET: soiffer%tekchips.tek.com