Path: utzoo!utgpu!watmath!watdragon!akwright
From: akwright@watdragon.waterloo.edu (Andrew K. Wright)
Newsgroups: comp.lang.c++
Subject: Re: generic arithmetic question
Summary: a solution
Message-ID: <9608@watdragon.waterloo.edu>
Date: 11 Nov 88 15:17:46 GMT
References: <3243@tekcrl.CRL.TEK.COM> <8407@alice.UUCP>
Reply-To: akwright@watdragon.waterloo.edu (Andrew K. Wright)
Organization: U. of Waterloo, Ontario
Lines: 81

In article <8407@alice.UUCP> bs@alice.UUCP (Bjarne Stroustrup) writes:
>
>***> ``soiffer@tekcrl.CRL.TEK.COM (Neil Soiffer)'' presents one of my
>	favorite problems. Unfortunately, I don't have a really good
>	solution, but I'll comment on it never the less. My comments
>	are marked with ***>. The plain text is Neil's. Like Neil,
>	I'd be most interested if someone could come up with a really
>	good solution that fitted into the C++ framework.
>
>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).

At the risk of preaching in the camp of the converted, I will present
a non-object-oriented solution to this problem.  This solution uses
parametric polymorphism, rather than inheritance, to obtain reusability.

The solution involves writing the operations of your generic arithmetic
package as polymorphic operations.  These operations do not belong to a
class; in fact, no operations in the language system belong to a class.

We introduce two new types of formal parameters, alreadly familiar
in formal logic.  Universal parameters will be written in uppercase,
and may be bound to an actual parameter of any type.
	*: [ a:T, b:T ] => T
specifies that * is an operation which takes two parameters of any
identical type, and returns a result of the same type.  But this is
not sufficient to write the body of *.  Existential parameters are
introduced with the keyword "exists".  No actual parameter is supplied
by the user for the existential parameter; it is searched for by
name by the compiler at the call site of the operation.
	*: [ a:T, b:T, exists +:[T,T]=>T ] => T
This definition of * take two actual parameters of the same type,
returns a result of that same type, but requires that where it is
called there exist a definition of + for those types.  Now you can
imagine writing the body of * as an loop doing additions.

Here is an implementation of a function called "exponentiation",
which operates not by repeated squaring, but by repeated multiplication
(a slight generalization of your problem).
"exponentiation" will take two parameters, a something and an integer,
and raise something to the integer power.  in order to operate,
"exponentiation" requires that * (multiply) exist in the calling
environment.
	exponentiation: [ a:T, b:int, exists *: [T,T]=>T ] => T
	{
		x:T;
		x = a;
		while( --b > 0 )
			x = x * a;
		return x;
	}
Now exponentiation will operate on all your builtin numeric types, because
they all define *.  If you introduce a new type which you wish to
exponentiate, all you have to do is define * for your new type.

Now here is one crucial advantage to this approach: if you wish
to use exponentiate on an existing type, you do not have to modify
that type, you simply introduce a * for that type.   For example
if I wish to apply exponentiate to strings, i need only define *
for strings.
	*: [a:string, b:string] => string    { return concat(a,b); }
	exponentiate( "abc", 3 )   \\ returns "abcabcabc"

For more information, please see
"Polymorphism in the Compiled Language ForceOne", Cormack and Wright,
Proc. of the 20th Annual Hawaii Int. Conf. on System Sciences, 1987.
This paper is a bit dated; we should be publishing some more up-to-date
stuff soon.
---------
Andrew K. Wright      akwright@watmath.waterloo.edu
CS Dept., University of Waterloo.
-- 
Andrew K. Wright      akwright@watmath.waterloo.edu
CS Dept., University of Waterloo.