Re: small integers

[Rob_MacLachlan@LISP-PMAX1.SLISP.CS.CMU.EDU]

    Date: Thu, 08 Oct 92 13:57:43 EDT
    From: "David A. Moon" <moon@cambridge.apple.com>
    To: Rob_MacLachlan@LISP-PMAX1.SLISP.CS.CMU.EDU
    Subject: Re: small integers
    Cc: info-dylan@cambridge.apple.com
    
    > ....
    > Small/extended integer proposal:
    > 
    > There shall be two disjoint subclasses of <integer>:
    >     <small-integer>
    >     <extended-integer>
    > ....
    > Note that a <small-integer> and an <extended-integer> may have the same
    > numeric value (such as 5).  In such a case, the class distinction
    > serves to control the over/underflow behavior.  AS may be used to
    > convert between integer classes:
    >     (as <small-integer> some-integer) 
    >     (as <extended-integer> some-integer) 

    The specific aspect I object to is having two non-id?,
    non-operationally-equivalent integers with the same mathematical value.

Well, that does sound sort of bad.  But we already do have
non-operationally-equivalent *numbers* with the same mathematical value:
   (= 0.5 1/2)
   (= 2.0 2)

[b.t.w., I now agree with Scott that it is a bad idea to have extended and
small integers read/print the same way.  However, this is outside the scope
of the current language, since READ and PRINT are part of the unspecified
environment.]

The only reason that we support floats in addition to rationals is that
they are more efficient.  It is widely observed that novice programmers are
confused by distinction between integers and floats --- and they are even
more confused when they discover the difference between floats and real
numbers.

    [this] violates the principle that correct programs should be
    easy to write and the burden of micro-optimization should be on
    programmers who need to do micro-optimization, not on all programmers.

By the above argument, we should eliminate floats, and have 3.14 read as a
rational.  In fairness, you did in fact argue against having floats, but I
think that fractional numbers are a such an important and familiar
concept that they must be supported somehow.

    It seems to me that what you are really aiming for is a way for the
    compiler to infer that the results of certain operations will lie
    within the <small-integer> subrange of <integer>, given information
    about the integer subrange of the arguments[...].  Is it really
    necessary to give up any hope of being able to do such inference within
    the existing semantics of Dylan (possibly with addition of
    finer-grained type specifiers for integer subranges)?  If so, what is
    the evidence?

Given a way to specify integer subranges of arguments, it would be possible
to do as you say (and which CMU CL does.)  The problem is that this
requires the programmer to effectively encode a proof that overflow doesn't
happen.  Admittedly, programmers really ought to be thinking about the
possibility of overflow, but it is definitely harder to code a proof of
non-overflow than to just trust that it doesn't happen and fix it when it
does.

This argument is based on the belief that integers are used primarily as
array indices and loop counters.  Sometimes you really do want extended
integers (such as in rational arithmetic.)  But then the programmer really
knows that they want extended integers.  [b.t.w., this was the reason I
proposed that NUMERATOR, etc. would always return an <extended-integer>.]

    It seems to me that you're making the language significantly more
    complicated and hard to understand, just to make compiler optimization
    a little easier.  Can't we find a less semantically violent way to
    enable the desired compiler optimization?

I feel that I am wearing my "lisp programmer" hat when I advocate this, and
not my "compiler implementor" hat.  Python does the sort of
result-type-proving that you suggest; it isn't terribly hard to implement,
but, from a programmer's perspective, it just doesn't work all that well.

I also feel that the small/extended split is well precedented by C and other
general-purpose programming languages that Dylan hopes to compete with.  In
normal programming languages, extended arithmetic requires an extended
arithmetic library, and extended-5 /= 5.

Note that I deliberately made two proposals, one proposing the overflow
semantics of <small-integer> and the other proposing that <small-integer>
should be the default for literals, sequence lengths, etc.  Adopting the
first proposal and not the second would hide <small-integer> from novice
users, at the cost of requiring explicit coercions to small integers.  If
so, small <extended-integer>s would probably need a distinct immediate
representation to avoid spurious consing.

  Rob