[RZ at MC: Rational and complex numbers]

[David A. Moon <Moon%SCRC-TENEX%MIT-MC@SU-DSN>]

Here's a clarification from Rich Zippel of his feelings about rational
and complex numbers.  I am simply forwarding this to the group for
informational purposes; I am not advocating doing anything about it
at this time.  My feeling is that he is talking at a much higher level
than the Common Lisp language deals with.  A system for modeling
general rings, fields, and other algebras would be a valuable thing to
have, but has little to do with the implementation of ordinary arithmetic in Lisp
except that the ordinary numbers would be a subset of the data types in
which the algebra system would deal.  Then we must address the question
of whether rational numbers are valuable enough in their own right (rather than
as one particular algebra) that they belong in the language.  The impression
I get is that a number of people have felt that they would far rather use
rational numbers than floating-point numbers for certain kinds of computations
(e.g. IC layout).

Date: Wed, 22 Jun 1983 18:08:00 -0000
From: Richard E. Zippel <RZ at MIT-MC>
Subject: Rational and complex numbers
To: Carl W. Hoffman <CWH at SCRC-TENEX>
Cc: Moon at SCRC-TENEX, rz at mit-mc

    Your second message on this topic completed what you said in your first
    message.  I think you should have sent them both together.  Were you really
    trying to say that the design of rationals as proposed for Common Lisp should
    not be used, or that better designs were possible?  Why don't you make an
    alternate proposal?
What I was trying to say, was that the current design of rationals in Common
Lisp is inadequate and not sufficiently visionary.  I personally think that
not having a rational number system in Common Lisp is better than having one
which will have to be removed at some later date when we understand the
problem more fully.  In particular I am afraid that we won't produce a new
system, or will resist the introduction of such a system because of the
investment that had been made in the current system.

Making a good alternate proposal is a major research undertaking.  Let
me mention some of the issues and some ideas that should be pursued.
You are trying to allow users to use algebraic structures based on the
integers.  There are three issues here:

(1) Creation of algrebaic types
(2) The gathering together of the appropriate algorithms/code for
    different types created by the user
(3) A theory of coercion.

(1) Creation of algebraic types: 

    There are several mechanisms that might be used to create new
    structures. The following list some of the most important that should be
    provided by the system.
    
    (a) quotient structures: This is how rational numbers are constructed.
    The numerators and denominators need not come from the same domain, but
    the denominators must be a subset of the numerators.  This allows you to
    deal with localization, farey sequenced and other mathematical
    structures.
    
    (b) Polynomials: You might think that adding algebraic numbers would be
    the next construction mechanism, but it is best to build it on top of
    polynomials.  The coefficients must be the elements of some algebraic
    structure, the exponents are integers. 
    
    (c) Modular structures.  Some domain, were an element different from
    zero is now assumed to be zero.  E.g., integers mod 5, gaussian
    integers.  The guassian integers are polyonomials in X where we have
    assumed X^2 + 1 is zero.  This allows more complex structures like
    algebraic functions.
    
    (d) Matrices, vector spaces, etc.
     
    With these constructors most interesting mathematic data structures can
    be built.

(2) Getting the code together.

    Now that you can build arbitrarily complex structures you are faced with the
    problem of making sure the right algorithm is associated with a
    particular operation.  This is one of the purposes of the Capsule paper.
    It describes some mechanisms that allow the creation of an algebraic
    structure to control the particular algorithms that are used for
    operations like plus and times.  I could go into more detail here later
    if its interesting.

(3)  Coercion
 
    Coercion is the process of make semantic identification of an abstract
    mathematical object.  Let describe what I've been calling a
    ``computational structure'' which is one way to deal with some of the
    problems of coercion.  Computational structures consist of a set of 
    domains which are in use (Z and Q are examples, there may be several Z's
    and Q's), and maps between the these domains.  There may be more than
    one map between two domains.  Certain of these maps are labeled as being
    canonical maps.  When an operation like (+ A B) occurs, the following
    things happen:  If A and B come from the same domain, then the +
    operation of that domain is used (that's the easy case, and the only one
    I believe should be implemented in Common Lisp now).  If A and B are of
    different domains, then these two domains are located in the
    computational structure, and the canonical maps are followed to find a
    domain in which both elements can be considered.  These elements are
    coerced into this new domain using the canonical maps, and the the
    operation is executed in the new domain.  Notice that the new domain
    need not be the domain of A or B but can be a third domain.
    
    There are a lot of complications with the scheme just described, but
    some variation of it is probably OK.  
    
This should give you some idea the issues I'm worried about.  [For Dave:
Carl and I have spoken about this to some length already, so he can
probably fill in many of the details.]

    It seems to me that you are asking for ways to represent 3*pi, 3*sqrt(2),
    etc., and, when divided by 4, have these yield (3/4)*pi, (3/4)*sqrt(2), etc.
    I would say that this has more to do with representing all of R (or with
    representing extensions of Z) than with the injections of Z into Q.

    Even if no changes are made to the current design (which is what I expect will
    happen), don't you feel that the advantages of having simple-minded rationals
    available in Common Lisp will outweigh the disadvantages?  You don't have to
    use them if you don't want to.
If you think this is clear enough and worth saving you might want to
forward this to Common-Lisp.