[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Generic Arithmetic

   Date: Mon, 13 May 1996 12:22:29 -0400 (EDT)
   From: david carlton <carlton@math.mit.edu>

   On Fri, 10 May 1996 18:15:44 -0400, Matthias Blume <blume@CS.Princeton.EDU> said:

   > But then: why generic arithmetic?  I know, it's kinda cute.  But is
   > it worth it?  Don't we know most of the time in advance that a given
   > variable will always hold a small integer?  Or a real?  Is the
   > trouble of automatically injecting into and projecting from a
   > universal number type (with the associated run-time checks) really
   > worth it?

   For me, lots of time, it is.  I'm a mathematician, and these days most
   of the time that I'm programming I'm implementing algorithms that
   would work largely or entirely without change over much larger classes
   of "numbers" than rationals or reals or whatever.

Changing the arithmetic which the procedures +, *, etc. use is a bad
idea because programs use properties guaranteed by R4RS which are
derived from the ring of integers.  If you change the ring, stuff
breaks.  Let us suppose you are interested in computing in Z mod 3,
the function:

 (lambda (x) (modulo (+ (expt x 3) (expt x 5) 1) 3))

is *NOT* equivalent to:

 (lambda (x) (modulo (+ (expt x 2) 1) 3))

If you changed all arithmetic to be mod 3, then you run the risk of
performing invalid reductions like:

 (expt a (+ 2 1)) ==> (expt a 0) ==> 1

Supposedly, a well-known symbolic mathematics program used to have
this bug.

An example of larger class of "numbers" is quaternions.  Introducing
quaternions means that * will not always be commutative and / will be
an inverse of only one handedness of *.

   And when I say "would work" in
   the above, I'm not talking about some sort of abstract possibility; I
   mean that it happens all the time that I wish that I could run some of
   my code in a more generic number system, that I didn't have to go
   running to Maple (which I can't stand) every time that I want to allow
   the possibility of dealing with polynomials, say, rather than rational

There is a simple way to do just what you want, portably, in R4RS
Scheme.  Just change the names of calls to arithmetic procedures in
your code to versions with "gen:" prepended.  This gives you control
over which operations are performed with the new number system, and
which are done using integers.

If this is not what you had in mind, then are you are expecting GCD to
be automatically extended from an extended definition of REMAINDER?
This won't necessarily work, because GCD for integers can be
implemented without using REMAINDER.