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

*To*: info-dylan@CAMBRIDGE.APPLE.COM*Subject*: small integers*From*: Rob_MacLachlan@LISP-PMAX1.SLISP.CS.CMU.EDU*Date*: Wed, 07 Oct 92 17:57:37 -0400

It isn't really clear from the book, but the Dylan <integer> class evidently supports extended-precision arithmetic. Since small integers are ubiquitous, good small-integer preformance is crucial for all manner of applications. There must be some way of informing the compiler that arimthmetic operands are small integers and that the result will be a small integer. Suppose <integer> has a subclass <small-integer>. We could then use this type to declare arithmetic operands: (bind (((x <small-integer>) stuff) ((y <small-integer>) more-stuff)) (+ x y)) This helps the compiler somewhat, but leaves open the possibility of integer overflow. What happens when <small-integer> arithmetic overflows? In most Lisp implementations (such as Common Lisp), the answer is that a non-small integer results. Declarations are necessary on each intermediate result, so (x+y)*3 becomes: (bind (((x <small-integer>) stuff) ((y <small-integer>) more-stuff) ((t1 <small-integer>) (+ x y)) ((t2 <small-integer>) (* t1 3))) t2) This sort of stuff certainly makes C & FORTRAN look like higher-level languages than Lisp. I am proposing a set of related changes, divided into two proposals. Rob MacLachlan (ram@cs.cmu.edu) ________________________________________________________________ Small/extended integer proposal: There shall be two disjoint subclasses of <integer>: <small-integer> <extended-integer> The result of <small-integer> OP <small-integer> is always a <small-integer>. If over or underflow results, then an error should be signalled. <extended-integer>s are more "contagious" than <small-integer>s. The result of <small-integer> OP <extended-integer> is always <extended-integer>. Over/underflow results in a quiet transition to extended precision arithmetic. Numeric operations on non-integers with integer results (truncate,floor,ceiling,round,/-variants,numerator,denominator, probably real-part, imag-part) always return <extended-integer>s. 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) Advantages of this proposal: -- The <small-integer> type allows the use of efficient hardware-supported arithmetic without first checking argument types. -- Considering <small-integer> overflow to be an exception allows more compact and efficient overflow handling to be compiled. Delivered applications might omit overflow checking entirely. -- Considering <small-integer> overflow to be an exception allows complex (nested) integer arithmetic expressions to be written much more more naturally, since type assertions are not needed on intermediate results. -- Extended integer support as been pulled out into a separate class which one could consider to be an optional library. Disadvantages of this proposal: -- Two more classes. -- Conceptual complexity in understanding the distinction between the two classes. -- Using the class to encode the extensibility attribute may be sort of a bad pun, since it seems to clash somewhat with the normal conception of subtype relations on integer types. This is because the conflicting demands of inheritance and subtypeness. ________________________________________________________________ Small integer integration proposal: -- Sequence keys, array indices and collection sizes are implicitly coerced to <small-integer>. If an <extended-integer> argument is too large to be a <small-integer>, then an error should be signalled. -- Any integer literal which can be represented as <small-integer> is small. Paraphrase: <small-integer> is the default integer class. The obvious coding of integer algorithms do not automatically extend into bignums. You would write extended FACTORIAL like this: (define factorial (method (n) (if (= n 0) (as <extended-integer> 1) (* n (factorial (- n 1)))))) small-integer factorial could be written: (define small-factorial (method ((n <small-integer>)) (if (= n 0) 1 (* n (small-factorial (- n 1)))))) [efficient compilation would require recursive type inference or a way to declare the type of the recursive call or of all calls to small-factorial.] Advantages of this proposal: -- Small integer arithmetic is the default, so efficient proramming comes more naturally. Disadvantages of this proposal: -- Small integer arithmetic is the default, so extended integer use require awareness additional code and awareness of the distinction between small and extended integers. ________________________________________________________________

**Follow-Ups**:**Re: small integers***From:*Scott_Fahlman@SEF-PMAX.SLISP.CS.CMU.EDU

- Prev by Date:
**Re: dylan scientific/multimedia** - Next by Date:
**REQUIRED FILES for GAMBIT implementation of THOMAS** - Previous by thread:
**Re: floating-point efficiency: Lisp vs. Fortran (FYI)** - Next by thread:
**Re: small integers** - Index(es):