Re: small integers

[Scott_Fahlman@SEF-PMAX.SLISP.CS.CMU.EDU]

<< I think this kind of language-design thread should probably be on
dylan-builders, but since it started here, I won't be the one to move it. >>

Dave,

I just saw Rob's response to this go by, and I agree with most of that, so
I'll just add a point or two.
    
Regarding the interface to a 32-bit outside world: I agree with Rob that
this is best handled by some special 32-bit data types and operators
introduced specifically for this purpose.  (This specialized stuff is
sequestered in a specialized library, of course.)  We've had good success
with this in CMU CL.

Of course, if this 32-bit imported data is woven all through your program,
rather than being handled in a few specialized interface routines, then
maybe you have to get into real bignums after all, and take your
performance hit.  I don't think this would be common, but it is a good
argument against flushing bignums altogether.

    > 1. The current Dylan approach ... 
    
    This is not quite right.  The combination of the <small-integer> class (behavior 
    same as Common Lisp's fixnum type; not the same as Rob MacLachlan's proposed 
    <small-integer>), 

Well, when I said the *current* Dylan approach, I meant the one in the
book, without any <small-integer> class.  The situation with a
small-integer type added (as in Common Lisp) is what I was calling option
2, and is analyzed there.

    ... the pervasiveness of parameter specializers in the preferred Dylan 
    programming style, and type inference in the compiler should eliminate the need to 
    allow for bignum operands in most places where that is possible and the programmer 
    cares about efficiency.

Agreed, most type-checking at the external inputs to arithmetic expressions
can be eliminated without undue pain to the programmer.  However, for
nested expressions, you need operand-type checking for internal values if
some of those might have turned into bignums.

    It may still be necessary to check for overflow, but that 
    can certainly be open-coded with small cost, especially when the overflow causes a 
    type error rather than continuing the computation with bignums.  This is what 
    Pascal (at least on the Macintosh) does, so it can't be too expensive, although 
    there is a compiler option to turn off the overflow checking.
    
Well, that's the crux.  Checking for the overflow is not too bad -- free on
some architectures -- but what do you do when you find one?  What Rob and I
are arguing against is the Common Lisp answer: you automatically roll over
into a bignum unless the user has inserted a (THE FIXNUM ...) around the
operation.  Allowing for the bignum rollover in all the places it *might*
happen is too expensive in many cases, and putting THE around *every*
arithmetic op is too much hassle for the programmer.

So what we're arguing for is an easy, intuitive way to say that we don't
want to worry about bignum rollover (or bignum operands) in certain
programs or parts of programs.  Rob's proposal is one way to indicate this
policy; Jeff Piazza's proposal (separate function names, glued together by
a macro) is another way.  I like both of these suggestions a lot better
than the Common Lisp solution.

I can't tell from your message whether you agree with this.  At times you
seem to favor the "correct" Common Lisp approach, and at other times you
seem to accept the idea of an overflow error under certain conditions.  If
we agree that an overflow error is the right thing in some situations, the
only remaining question is how to indicate where we want this behavior.

    I think it's consistent with object orientation for the fourth version of + to have 
    a different name from the first version, since they really do different things 
    (real addition versus modulo 2^N addition).  Maybe it's been a mistake for Lisp 
    implementations to keep this operator an internal secret all these years, and we 
    should add such operations to Dylan.

This mod-2 addition is similar in spirit to the specialized 32-bit
operators that Rob and I were advocating above for foreign function
interfaces.  You also need something like this in order to implement bignum
arithmetic.  These operators will need to exist, and should probably be
standardized at some point, but they can be hidden away in a specialized
"low-level-tools" facility, where average programmers will never trip over
them.

    Of course it would be better not to hair up 
    the language if compiler optimization can do the job.  Also, as Rob MacLachlan 
    pointed out in a message today, compiler optimization is more general since the 
    same source code can be compiled two different ways depending on what the compiler 
    knows about the types involved.

Ummm... are you now advocating that we encode wraparound policy in the type
of the arguments?  Probably not, since you oppose this move elsewhere, but
then I don't understand your comment above.
    
    My question of whether it's feasible to eliminate the overflow checking through 
    compiler optimization most of the time hasn't been answered yet.  I already know 
    it's feasible to eliminate the type checking, so only the overflow checking 
    remains.
    
I think Rob and I both tried to address this.  If all you say about the
operands is that they are of type <short-float>, then +, -, and * must all
check for overflow and be prepared to handle whatever overflows are found,
one way or another.  This is true regardless of how smart your compiler is.

If the user says that both arguments are of type (integer 0 1024) --
assuming Dylan provides a language in which to state this sort of thing --
then a sufficiently smart compiler can often prove that no overflow will
occur.  But to do this consistently puts an unacceptable burden on the
programmer: if he's interested in efficiency, he must now think about
exactly how big his arguments are allowed to be, he must prove to himself
that overflow is impossible in certain places, and he must worry about
whether the compiler is smart enough to figure this out as well.  In
practice, people just say "fixnum" and then complain about how slow
arithmetic is in Lisp.  It's infinitely easier just to say, one way or
another, that you don't believe overflows will occur in a certain part of
the program, and that you want to get an error signal if you're wrong.

-- Scott

P.S. Can you show me what the "new" style is for implementing an iteration
loop without using SET! ?  I can think of several ways to do this, but all
are ugly and/or inefficient.