Cleaning up the Tower: Numbers in Scheme
Contents
1. of representatives of the residue class ring Z yZ is being chosen either non negative y gt 0 symmetric around zero y lt 0 or the integers y 0 The definition above implies Fa if y gt 0 xdivy lt 0 if y 0 4 5 if y lt 0 This simplicity is the reason why the definition can be extended literally to define div and mod for all rational x y Mathematically it even makes sense for all real x y For example xmod2z and xmod 2z both reduces x modulo 27 and 0 lt xmod27 lt 2m and T lt xmod 2n lt T Since div and mod offer both conventions which make sense the RRS procedures modulo remainder and quotient can easily be defined in terms of div and mod Of course it is also possible the other way around albeit with more effort Figures 2 and 3 show the definitions respectively 6 6 External Representations We discuss some of the issues regarding external representatives arising from our design proposal in this section External representations occur in several contexts e literals in program source code 116 define quotient nl n2 sign nl sign n2 div abs nl abs n2 define remainder nl n2 sign nl mod abs n1 abs n2 define modulo n1 n2 sign n2 mod sign n2 nl abs n2 Figure 2 Defining quotient remainder modulo in terms of div mod sign and abs define cond positive y let n div x y numerator x denomina2. right place for it Students find especially confusing that the seemingly simpler integral numblers cause problems while the more complicated floating point numbers do not The example illustrates the limited predictability of Scheme programs mixing exact and inexact numbers Figure 1 A real world example ordering etc Initially we consider the exact world only We show how to add inexact operations later We take the following abstract numerical tower as the basis for our numerical operations Q 2 Qio 2 Q2 2 Z 2 Z gt 0 2 Zyo In this chain Q denotes the rational numbers Q denotes the b ary fractions i e the set of rational numbers with denominator a power of b binary fractions for b 2 and decimal fractions for b 10 Z denotes the integers Z gt 9 denotes the non negative integers and Z gt o denotes the positive integers While this view of the rational numbers may appear arbitrary or the oretical at first glance it identifies and names the kinds of numbers that computer programs typically distinguish In particular positive and non negative integers are so frequent in any sort of program that we propose to name them in the core language itself To relate the tower elements to machine representations we use the following terminology borrowed from R RS Fixnums are the fixed width machine representation for integers denoted by fixnum Bignums are the arbitrary width exact representations
3. www scheme com csug index html 6 7 Marc Feeley Gambit C version 3 0 A portable implemen tation of Scheme 3 0 edition May 1998 http www iro umontreal ca gambit doc gambit c html Marc Feeley SRFI 4 Homogeneous numeric vector datatypes http srfi schemers org srfi 14 May 1999 James Gosling Bill Joy Guy Steele and Gilad Bracha The Java Language Specification Addison Wesley 2nd edition 2000 Haskell 98 a non strict purely functional language http www haskell org definition December 1998 8 9 10 11 William Kahan Branch cuts for complex elementary func tions or much ado about nothing s sign bit In A Iserles and M J D Powell editors The State of the Art in Numeri cal Analysis Clarendon Press 1987 12 13 14 15 16 17 18 19 20 William W Kahan and Joseph D Darcy How Java s floating point hurts everyone everywhere http www cs berkeley edu wkahan JAVAhurt pdf March 1998 Richard Kelsey William Clinger and Jonathan Rees Revised report on the algorithmic language Scheme Higher Order and Symbolic Computation 11 1 7 105 1998 Xavier Leroy The Objective Caml system release 3 08 Doc umentation and user s manual INRIA France July 2004 http pauillac inria fr caml International Standards Organization Programming language C 1999 ISO IEC 9899 Proc Conference on Programming Language Design
4. 0 7 would always denote 7 10 unless R RS compatibil ity is important see Section 5 whereas the IEEE 754 64 bit float closest to 0 7 would print as 0 7 52 which is equal to 3152519739159347 4503599627370496 We call this format the mantissa width tagged format From the point of view of communication the mantissa width tagged format is not so much an indicator for floating point but rather a source coding compression method for a frequently used subset of the rational numbers binary fractions The mantissa width tagged format for binary fractions achieves accuracy without loss of performance The mantissa width tagged format can be specified accurately in terms of the procedures round fraction and round of Sec tions 6 4 and 6 3 To be specific we propose procedures string gt rational and rational gt string serving the function of R RS s string gt number and number gt string that convert between internal and external representations of rational numbers Apart from the usual formats base 2 8 10 16 fractions via and decimal scientific e notation string gt rational understands the number syntax scientific mantissa and interprets it as round fraction 2 mantissa round scientific Rational gt string and string gt rational satisfy the 117 read write invariance property of RRS For each rational number x in the sense of rational the following holds string gt rational rational
5. Common Lisp stands out which takes a less principled but otherwise similar approach to Scheme We conjecture that programmers experience similar sur prises in Common Lisp as in Scheme However given Common Lisp s much tighter specification and as much fewer Common Lisp systems exist than Scheme systems these surprises may not matter as much in practice All in all we believe that Scheme is special enough to warrant a special design for its numerical operations 10 References 1 Robert G Burger and R Kent Dybvig Printing floating point numbers quickly and accurately In Proc of the ACM SIG PLAN 96 Conference on Programming Language Design and Implementation pages 108 116 Philadelphia PA USA May 1996 ACM Press William D Clinger How to read floating point numbers ac curately In PLDI 1990 16 pages 92 101 William D Clinger How to read floating point numbers ac curately In Kathryn S McKinley editor 20 Years of the ACM SIGPLAN Conference on Programming Language De sign and Implementation 1979 1999 A Selection ACM April 2004 SIGPLAN Notices 39 4 Joseph Darcy Adding IEEE 754 floating point support to Java Master s thesis University of California at Berkeley 1998 http www cs berkeley edu darcy Borneo spec html 2 3 4 5 PLT DrScheme Programming Environment Manual May 2004 Version 207 R Kent Dybvig Chez Scheme User s Guide Cadence Research Systems 1998 http
6. as those proposed in SRFI 4 8 are an appropriate mechanism for this 7 7 Mantissa width tagged format Reading the mantissa width tagged format proposed in Section 6 6 can be done efficiently using Clinger s method 3 2 Similarly printing the mantissa width tagged format using the min imum number of total digits can be reduced to Burger and Dybvig s efficient method for printing a binary fraction as an approximate decimal fraction 19 1 The most important difference is that the mantissa width may vary with the number being printed In effect the mantissa width tagged format can often be shorter as for ex ample in 1e9 1 239 Whether the system should really use the mantissa width tagged format in this case is a different matter 8 Related Work Some Scheme implementations targeted at high performance programs such as Chez Scheme 6 and Bigloo 17 offer spe cialized numerical operations for floating point numbers This un derlines the need for separating floating point arithmetic from the usual generic arithmetic for performance reason but does not really address the concerns raised in this paper The remaining numerical operations are unaffected in these systems Gambit C 7 offers a declaration which locally declares all RRS numerical operations to perform floating point arithmetic again for performance reasons The teaching languages of DrScheme 5 use exact arithmetic by default to spare beginning student
7. controlling their propagation as well as the rounding mode of floating point operations This is addressed in detail elsewhere for example in the recent work on floating point arithmetic in Java 4 Also we omit complex num bers and other advanced number representations such as algebraic numbers interval arithmetic cyclotomic fields etc from the dis cussion they are largely orthogonal to the subject of this paper Overview We identify the main problems with the R RS ap proach in Section 2 In Section 3 we present a new model for exact rational arithmetic and a set of typical machine representations for it Section 4 describes how to add inexact arithmetic to the model along with the design issues arising from this Section 5 explores design alternatives within our model In Section 6 details a possible set of exact numerical operations Some implementation issues are discussed in Section 7 Finally Section 8 lists some related work and Section 9 concludes 110 2 Problems with the R RS approach RORS specifies that the objects representing numbers in a Scheme system must be organized according to a subtype hierarchy called the numerical tower number gt complex 2 real D rational D integer Section 6 2 3 of RRS requires implementations to provide a co herent subset consistent with both the purposes of the implementa tion and the spirit of the Scheme language Moreover implemen tations may provide only a limi
8. inexact operations explictly we give up a potential source of code reuse Even if an algorithm works for both exact and inexact operations alike our proposal requires two different programs one calling the exact operations one calling the rounding operations We are proposing to pay this price be cause sensible algebraic and numerical algorithms seem to be dis tinct most of the time Of course practical implementations of the inexact operations will use a limited precision floating point representation for numbers This raises the question of how these representations relate to the other representations for rational numbers Do the floating point representations form a subset of the rational representations What about NaN and distinct 0 The issue of the special floating point objects is central to this issue We discuss and NaN sep arately from distinct 0 4 1 The case against rational and NaN The special objects and c are used in the floating point world as a mechanism to carry on with a computation in the presence of overflow They are usually the results of positive tiny and positive tiny ce which can happen without the programmer being aware of it In the exact world however the only way of obtaining infinity is a division by zero The question is whether the system should then signal an error or return a special object representing infinity An argument in favor of is th
9. input lambda x y if lt x y 1 1 Clearly the reason is that the comparison lt returns an exact result either t or This is especially pernicious given that comparisons are one place where the inaccuracies of floating point numbers may really hurt In effect the accuracy of the function s value is no greater than the accuracy of the input but in Scheme s type system the result is treated as entirely exact This seems to be why Bigloo 2 5c for instance has expt 2 50 0 but exact expt 2 50 t in violation of the standard Chicken 0 1082 which also does not sup port bignums has expt 2 50 1125899906842624 and exact expt 2 50 gt f 111 To ensure that an exact result is not dependent on inexact operations the programmer either has to do a careful analysis of the program in which case any run time checking is irrelevant or use exact comparison operations like the following define exact lt x y if and exact x exact y lt x y error 2 6 Exactness of numerical literals Section 6 2 4 of R RS states If the written representation of a number has no exactness prefix the constant may be either inexact or exact It is inexact if it contains a decimal point an exponent or a character in the place of a digit otherwise it is exact The consequence is often that the global behavior of a program is governed by the presence or absence of a single deci
10. property of num bers orthogonal to the representation type However numerical op erations will always convert rational arguments to float arguments if any other arguments are floats Comparisons between floats and rationals always convert the floats to rationals Unlike Scheme Common Lisp does at least give a recommendation for the min imum precision offered by the various floating point operations which we conjecture reduces the variance between different Com mon Lisp systems considerably However the basic arithmetic op erations are still overloaded and do not always respect the various algebraic laws Mathematica 20 provides an arbitrary precision floating point representation and applies a mechanism of decreasing precision during inexact computation In practice however this approach suffers from the same weaknesses as RRS When inexact numbers enter the computation it is usually time to design a new program Moreover the automatic decreasing of precision makes it difficult to run entire computations at a higher precision a stray 1 0 de fault precision instead of aN 1 50 high precision propagates its low precision uncontrollably usually ruining the calculation An alternative approach to preserve read write invariance and a number of the other issues raised in this paper would be to fix the floating point representation in the language specification once and for all as for example has been done in Java 9 In tha
11. rational equivalent of 0 read negative underflow A first approach might be 0 behaves like the smallest negative rational larger than any repre sentable float Unfortunately there is no such rational number Let f denote the largest representable negative float Then f 1 n nE 1 2 3 are not representable and increasingly close to f So there must be a gap between f and whichever rational num ber Z is choosen as the rational interpretation of 0 unless the definition reads Any Z for f lt Z lt 0 may be chosen as the rational interpretation of 0 an approach we do not pursue Whatever the choice a negative number equivalent Z of 0 will behave surprisingly different from the float 0 For example re peatedly squaring Z will soon exhaust memory and printing the square of Z will print unrecognizably unless one is willing to sacrifice Scheme s facility to print rationals without loss of infor mation Since alternatives a c and d are unattractive alternative b appears to us as the least disadvantagous there simply seems to be no place for 0 0 in the exact world of rational numbers 5 Relating exact and inexact arithmetic As the previous discussion has shown the special floating point values 0 and NaN have no place in the exact world they are not rational numbers Hence in the following we assume that it is an err
12. small to be represented is not detected it is simply rounded to zero 6 5 Div and mod Given an unlimited integer type it is a trivial matter to derive signed and unsigned integer types of finite range from it by mod ular reduction For example arithmetic using 32 bit signed two s complement behaves like computing with the residue classes mod 232 where the set 23 2 1 represents the residue classes Likewise unsigned 32 bit arithmetic also behaves like computin mod 232 but using a different set of representatives 0 2 1 Unfortunately the R RS operations quotient remainder and modulo are not ideal for this purpose In the following example remainder fails to transport the additive group structure of the in tegers over to the residues modulo 3 define r x remainder x 3 E 2 JAE S r2 r 3 gt 2 In fact modulo should have been used producing residues in 0 1 2 For modular reduction with symmetric residues i e in 1 0 1 in the example it is necessary to define a more compli cated reduction altogether Therefore we propose operations div and mod with Scheme coun terparts div and mod defined on all integers x y by the following properties x xdivy y xmody 3 0 lt xmody lt y ify gt 0 4 y 2 lt xmody lt y 2 ify lt 0 xdivy is integer and xdiv0 0 5 In other words the sign of the modulus y determines which system
13. towards is naturally related to floor and ceiling by x 1 2 and x 1 2 6 4 Binary and decimal fractions By providing a convenient function for rounding rationals into binary and decimal fractions programs can easily implement floating point operations of arbitrary precision in the absence of or in addition to proper floats Among others this provides a natu ral way of defining external representations for binary and decimal fractions accurately and portably A proposal is in Section 6 6 We propose that round fraction base mantissa round x maps the rational x into a number that has mantissa significant digits in its base ary expansion and where rounding has been performed by applying the procedure round mapping rationals into integers Figure 4 shows a possible implementation in R RS assuming the presence of bignum rational arithmetics 115 More explicitly round fraction bmp x should result either in 0 or in a number of the form sign x fo 1 amp n 1 o B 1 for b ary digits f9 m 1 0 b 1 o 40 and integer Clearly this only makes sense for integer b and m where b gt 2 and m gt 1 Now consider the case 4 0 Then 1 1 0 y lt 0 41 m 1 p lt b 10 0 p This implies 0 lt log f9 1 m 1 lt 1 from which follows llog l This is the primary reason for proposing that floor log abs b x computes the largest integer e such
14. 5 7 5 Floating point representation We have said nothing about the particular machine floating point representation a Scheme system may use or should be required to use by a standard This is a touchy issue requiring say a par ticular IEEE 754 representation would lead to completely repro ducible computations but depending on the hardware a program runs on results in an unacceptable loss in either accuracy or ef ficiency 4 12 and might pose a considerable obstacle for imple mentations on platforms not supporting this representation natively For this reason we would expect a standard to specify that the floating point operations use the widest floating point format the underlying hardware supports efficiently In practice this would probably mean IEEE 754 double extended on the Intel x87 or the 68xxx architecture and IEEE 754 double on say the PowerPC or the Alpha Of course implementations could also offer sets of floating point operations specific to a specific machine representation or with pa rameters e g multiprecision However as few programs seem to require this degree of control it should probably not be included into the core language by default 118 7 6 Floating point storage The choice of the storage format for large quantities of floating point numbers is independent of the choice of the format used for computations Uniform vectors that explicitly specify the floating point format used such
15. Cleaning up the Tower Numbers in Scheme Sebastian Egner Philips Research Laboratories sebastian egner philips com Abstract The R RS specification of numerical operations leads to unportable and intransparent behavior of programs Specifically the notion of exact inexact numbers and the misleading distinction between real and rational numbers are two primary sources of confu sion Consequently the way R RS organizes numbers is signifi cantly less useful than it could be Based on this diagnosis we pro pose to abandon the concept of exact inexact numbers from Scheme altogether In this paper we examine designs in which exact and in exact rounding operations are explicitly separated while there is no distinction between exact and inexact numbers Through examining alternatives and practical ramifications we arrive at an alternative proposal for the design of the numerical operations in Scheme 1 Introduction The set of numerical operations of a wide spectrum programming language ideally satisfies the following requirements efficiency The programming language s operations are reasonably efficient relative to the capabilities of the underlying machine In practice this means that a program can employ fixnum and floating point arithmetic where reduced precision is accept able accuracy A program computes with numbers without introducing error reproducibility The same program run on different language i
16. The case against rational 0 The purpose of distinguishing a positive zero 0 and a neg ative zero 0 in a floating point format is to retain the sign of numbers in the presence of underflow e g 0 positive huge Since comparisons must allow for tolerances there is no real harm done identifying 0 positive with the zero which is neither pos itive nor negative The use of signed zeros simplifies dealing with branch cuts 11 and generally helps obtaining meaningful numeri cal output In the exact world on the other hand there is no underflow only memory overflow Even worse adding one or even two signed zeros to the rational numbers completely destroys the rich clean and simple algebraic structure which the rational numbers do posses We briefly detail this mathematical fact The set Q of rational numbers equipped with the addition operation 113 form an abelian group This means the following C For all x y E Q x y y x A For all x y z E Q x y z x y z Z There is Z Q such that for all x Q Z x x I For all x Q there isay E Q x y Z Now take elements Z Z Q such that Z x x for all x Q and also Z x x for all x Q Then Z Z Z Z Z Z where the second equation holds by C Consequently there is only one element Z Q having property Z Therefore this element receives the special name 0 read zero Now i
17. and Im plementation 90 White Plains New York USA June 1990 ACM Manuel Serrano Bigloo A practical Scheme compiler User manual for version 2 6d April 2004 http www sop inria fr mimosa fp Bigloo doc bigloo html Guy Steele Common LISP The Language Digital Press Bedford MA 2nd edition 1990 Guy L Steele and Jon L White How to print floating point numbers accurately In PLDI 1990 16 pages 112 126 Stephen Wolfram The Mathematica Book Wolfram Media 5th edition 2003 120
18. at they provide neutral elements for the minimum and maximum i e min 00 max o0 Nevertheless an exact division by zero is virtually always a symp tom of a genuine programming error or of illegal input data and the introduction of infinity will only mask this error NaN not a number is the strongest form of delaying an er ror message NaN is a special object indicating that the result of an arithmetic operation is undefined one way it could emerge is NaN The advantage of returning NaN instead of raising an error is that the computation still continues postponing the interpretation of the results to a more convenient point in the program In this way NaN is quite useful in numerical computa tions The problem with NaN is that the program control structure will mostly not recognize the NaN case explicitly Assume we define comparisons with NaN always to result in f as IEEE 754 does then do x NaN x 1 gt x 10 will hang but do x NaN x 1 mot lt x 10 will stop which is counter intuitive and may be surprising While and NaN are quite useful for inexact computations there is a high price to pay when they are carried over into the exact world The rational numbers must be extended by the special ob jects and the usual algebraic laws will not hold for the extension anymore Moreover the special objects obscure exact programs by masking mistakes 4 2
19. ct as ainexact Define exact gt inexact and inexact gt exact as follows define exact gt inexact n 114 if float n n rational gt float n define inexact gt exact n cond float n float gt rational n number n n else error Note that number NaN f and number too f while float NaN t and float o gt t e Finally add operations on flonum with a float prefix Of course inexact exact exact gt inexact and inexact gt exact serve no purpose in this new organization of numbers and should disappear eventually The only problem is that of literals Alternative 1 would work most intuitively if unannotated numerical literals would always rep resent their rational counterparts exactly Unfortunately RORS re quires that the presence of a decimal point or an exponent forces a literal to denote an inexact and thus a floating point number Therefore a true conservative extension still requires that exact numerical literals carry a e prefix In any case all alternatives feature full reproducibility for exact computations and much improved transparency because the pro gram source code clearly shows when floating point arithmetic hap pens As for the example in Figure 1 In our design the program would always compute slowly However the program now behaves in a much more consistent and less confusing manner and the cause for the problems is much easier t
20. e examine the choices available in such a design and dis cuss their consequences and relative merits The choices concern the relationship between the rational numbers and the floating point numbers whether floating point numbers count as rationals and vice versa We also discuss the nature of and not a number and where they fit in our frame work All of the design alternatives we examine allow compromises between efficiency and accuracy similar to what R RS cur rently provides as well as improved transparency and re producibility Any program that does not contain calls to floating point operations always computes exactly and repro ducibly independent of the Scheme implementation it runs on Rounding conversions from rational to floating point numbers only occur at clearly identifiable places in a program e We identify some weaknesses in the R RS set of numerical operations as they pertain to the new design and describe pos sible approaches to addressing them This includes the defi nitions of quotient remainder and modulo the definitions of the rounding operations and dealing with external repre sentations We do not address all the issues concerning numbers that a future revision of the Scheme standard should address Specifically we do not discuss the relative merits of tying the Scheme standard to a specific floating point representation We do not touch the issue of offering abstractions for explicitly
21. ement the natural one to one correspondence between exact and inexact integers throughout an implementation dependent range More tellingly it also says If an exact inexact argument has no reasonably close inexact exact equivalent then a violation of an imple mentation restriction may be reported The may implies that implementations are free to use an arbi trarily inaccurate equivalent Moreover the meaning of reason ably close is similarly underspecified Table 1 shows that a call to inexact gt exact that works fine on one implementation may ac tually signal an error on another even if the argument is the same 2 3 No exact fixnum only arithmetic RRS specifies in Section 6 2 2 If two implementations produce exact results for a com putation that did not involve inexact intermediate results the two ultimate results will be mathematically equiva lent This makes it hard for a Scheme system to support only limited precision integers as it requires the system to mark results of over flows as inexact which in turn usually means some loss of effi ciency if boxing is involved in the construction of inexact numbers or a conversion to a different representation or additional loss of precision if an additional bit in the fixed size representation de notes inexactness 2 4 Numerical promotion loses information The idea of a numerical tower suggests that the more general number types contain the mo
22. erms of both space for storage of the representation and time for con verting back and forth between the numbers and their representa tion define floor log abs base x define log b x e b e offset let b e 1 be b if gt b etl x if b e x e e offset log b x e 1 b etl offset let abs x abs x if gt abs x 1 log base abs x 0 1 0 log base 1 abs x 0 1 1 define round fraction base mantissa round x if zero x 0 let k mantissa floor log abs base x 1 round x expt base k expt base k Figure 4 Floor log abs and round fraction as defined in Sections 6 3 and 6 4 implemented in RRS assuming ratio nal arithmetics Hence it is desirable to be able to use a shorter floating point in the true sense of using a point external representation for num bers preferably using the familiar decimal point format In that case read write invariance requires tagging the result explicitly as a floating point number Moreover to better support the exchange of external representations between different Scheme systems or to support distinguishing between several machine floating point formats used by a single Scheme system it is desirable to provide information about the nature of the floating point format used We suggest using a suffix indicating the length of the bi nary mantissa of the floating point format Thus In our pro posal
23. f we augment the set Q into Q by forcibly adding another algebraic zero as in Q QU where x x for all x Q and Q then either property C or property Z or both get lost This implies that property I at least suffers because the uniqueness of y which is in fact x gets lost This carries on like wildfire usually destroying nearly all algebraic properties at the same time associativity may survive More generally four different alternatives for dealing with 0 in the exact world can be identified a Augment the rational numbers by one or two objects behav ing like a zero Algorithmically this means that all exact operations must dispatch on these special objects and define some action b Identify both floating point values 0 and O with the ratio nal number 0 In other words exact operations treat 0 and 0 identically c Represent the floating point value 0 by some negative ra tional number say Z Conceptually exact operations first replace 0 by the rational number Z and then do their work d It is an error to apply an exact operation to 0 As explained above the semantic cost of adding one or more ze ros is quite high This is a strong argument against alternative a In the other extreme alternative d breaks the symmetry be tween positive and negative numbers The problem with alterna tive c is to find a sensible definition of the
24. for arbitrary integers named bignum Flonums are the fixed precision floating point machine representation for rational numbers named flonum Finally fractions are the tuple representations for ra tional numbers using bignum numerator and denominator called fraction The relationships between the tower elements and the machine rep resentations are as follows 1 The fixnum representation implements a subset of Z 2 The bignum representation implements Z only limited by available memory 3 The flonum representation implements a subset of Q2 pos sibly augmented by special objects like 0 and NaN which are not elements of Q 4 Human readable representations are typically decimal fractions elements of Qj9 at least conceptually 5 The fraction representation implements Q only limited by available memory We propose that the default operations on rational numbers that means the standard procedures lt etc are all exact Con ceptually they accept rational arguments and return rational results Of course implementations may take advantage of more efficient machine representations employing fixnums and flonums if pos 2What we denote as Q is not identical to the algebraic concept of field of p adic numbers 112 sible but conversion may only take place if no loss of information occurs in the process Thus the particular machine representation of a number is purely an efficiency
25. gt string x x Note that our is an exact comparison unlike the of RRS which is the reason R RS formulates this property in terms of eqv To summarize we suggest the following partly departing from RRS e Each external number representation without annotation de notes exactly the rational number the learned in high school interpretation would assign it That is 0 7 7 10 and 1 3e 2 13 1000 e The mantissa width tagged format specifies a binary fraction like a floating point number by decimal digits 0 715 11 16 and 0 7 52 3152519739159347 2 52 e The e and i prefixes go away Note that we expect the mantissa width tagged format to occur only rarely in numerical literals the programmer can simply specify a rational number and rely on the automatic conversion for float operations The R RS requirement that number gt string must use the mini mum number of digits for decimal point external representations must be adjusted for rat ional gt string as there might be several different representations for the same number For example 11 32 0 34 4 0 34375 Although the mantissa width tagged format is shorter the purely decimal format is arguably clearer Consequently we propose to require the minimum number of digits only within one particular number format but give the implemen tations the freedom to choose the format Nevertheless printing with the absolute minimum of characters is also pos
26. he two which introduces the need for trans parency Reproducibility is clearly desirable but also often in con flict with efficiency the most efficient method for performing a computation on one machine may be inefficient on another At least a programmer should be able to predict whether a program computes a reproducible result Moreover as many practical pro grams as possible should in fact run reproducibly RRS 13 provides for exact and inexact numbers with the idea that operations on exact numbers are accurate but potentially ineffi cient and operations on inexact numbers are efficient but introduce error The intention behind RRS is to hide the actual machine rep resentation of numbers and to allow the program or the program mer to look at a number object and determine whether it contains error In theory this would fulfill a reasonable transparency require ment In practice however the numerical operations in Scheme are anything but transparent For a trivial example exhibiting the poor reproducibility of RRS programs consider the value of the expression inexact gt exact 0 7 in various Scheme systems all of which are completely R RS compliant Table 1 shows that the results vary wildly Scheme 48 can even change its behavior at run time This is only one of a wide variety of problems a programmer faces who tries to predict the outcome of a computation on numbers in a Scheme program Clearly R RS provides for li
27. is or a suitable exception system 7 3 Coercion of constants If number literals containing a decimal point and without a mantissa width specification are interpreted as rationals and floating point operations accept rational arguments as in design al ternative 1 the implementation will typically need to convert the rational number to a floating point representation This may be a relatively expensive operation and a straightforward program may perform it often To reduce the cost an implementation could mem oize the floating point approximation of a rational number or per form a static analysis to determine what literals are used exclusively as arguments to floating point operations We conjecture that a sim ple analysis would be quite effective for most realistic programs 7 4 Fixnum arithmetic Many Scheme implementations already use fixnum arithmetic to optimize common case numerical operations However implemen tations might want to offer exclusively fixnum arithmetic to opti mize away the generic arithmetic dispatch and the overflow detec tion Doing this in the default set of numerical operations on exact numbers is already in violation of RRS See Section 2 Thus the best way of offering fixnum only operations would be through a set of separate procedures analogous to the floating point operations with their algebraic meaning defined as calculat ing mod 2 w 8 16 32 64 as proposed in Section 6
28. issue In practice this means the following e Each number object represents a unique precisely defined ra tional number Rational numbers have conceptually infinite precision e Different machine representations of the same rational num ber may coexist but they are all equivalent Processing time may differ of course e Rational numbers are treated exactly the same way as RORS currently treats exact integers and rationals e The exact operations satisfy all algebraic properties associa tivity commutativity distributivity total ordering etc of their mathematical counterparts 4 Adding inexact arithmetic Exact operations alone even combined with explicit rounding are not sufficiently efficient for many numerical computations There fore the language should provide access to the underlying floating point hardware if available through a default set of inexact opera tions For example float would accept two flonums and return a flonum By nature float sacrifices algebraic properties to gain efficient execution However by distinguishing exact and inexact operations explicitly the actual arithmetic used becomes a property of the program rather than a property of the numbers it processes Note that the arithmetic model remains a dynamic property in any language with exact and inexact numbers even if operations are required to accept only all exact or all inexact argument values By distinguishing exact and
29. m plementations will produce the same result transparency The programmer can tell when a result is the out come of inexact operations and thus contains error or when a computation is reproducible exactly In practice efficiency and accuracy are often in conflict Accu rate computations on non integral numbers are often but not al ways prohibitively expensive Fast floating point arithmetic intro duces error Thus a realistic programming language must choose a Permission to make digital or hard copies to republish to post on servers or to redis tribute to lists all or part of this work is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page To otherwise copy or redistribute requires prior specific permission Fifth Workshop on Scheme and Functional Programming September 22 2004 Snow bird Utah USA Copyright 2004 Sebastian Egner Richard A Kelsey Michael Sper ber Richard A Kelsey Ember Corporation kelsey s48 org 109 Michael Sperber sperber deinprogramm de Scheme 48 1 1 default mode 7 10 Petite Chez Scheme 6 0a 3152519739159347 Gambit C 3 0 4503599627370496 Scheme 48 1 1 after open floatnums SCM 5d9 1 Chicken 0 1082 can not be represented as an exact number Table 1 Value of inexact gt exact 0 7 in various RRS Scheme implementations compromise between t
30. mal point A program can become intolerably inaccurate through the presence of a decimal point or intolerably slow through the omission of one The example described in Figure 1 illustrates why this may be un fortunate 2 7 Meaning of standard procedures Some of the standard procedures defined in R RS only make sense for certain types of numbers e g gcd for exact integers or log for inexact real or complex numbers This is a temptation for implementations to fill in the gap and define things like gcd 2 0 6 0 in the obvious way violating the in tended meaning of standard procedures In the following example again run under MzScheme the greatest common divisor might be greater than expected gcd expt 2 40 gcd expt 2 40 expt 3 40 gt 1 expt 3 40 2048 0 2 8 Exchanging numbers between Scheme sys tems There is no guarantee that two R RS compliant Scheme systems can successfully exchange numerical data via the written represen tations provided by the standard procedures For exact integers there seems to be no problem provided the receiving system cov ers the range required by the sender The notation 1 2 already poses a problem because rationals are not mandatory The speci fication of number gt string and string gt number laudably caters to read write invariance but does so only for numbers written and read by the same Scheme system 3 Exact arithmetic The analysis in the previous
31. merical operations is attributing inexactness to the opera tions rather than the numbers We have designed the basis for such a set of numerical operations and identified design alternatives within its framework The most important property of our design is that the default numerical oper ations are always exact Floating point arithmetic is relegated to a separate set of operations Most of the choices available within the design concern the degree of separation between the inexact and ex act worlds However all of the alternatives we propose have more pleasant properties than what R RS currently requires in particu 119 lar greater transparency and full reproducibility for exact compu tations They also require similar if not less implementation effort We have also identified some weaknesses in the set of numerical operations offered by RRS and proposed alternatives Arguably the result is still strange in that it is unlike basically every other programming language We conjecture that this dif ference is good and necessary In particular most programming languages do not offer infinite precision integers and rational num bers at all which reduces the design space but comes with its own problems Limited precision of the various numerical types along with implicit coercion rules often cause programming errors and non reproducible behavior Of the languages that do support infinite precision integers and rationals only
32. ned for the non flonum rational numbers Programs use of float gt rational and rational gt float to convert ex plicitly All three alternatives could support a float predicate that an swers t for all flonum arguments including and NaN A rational predicate would probably behave differently in the dif ferent alternatives Whereas it would answer t to all numbers ex cept for and NaN in 1 and 2 it would naturally be a converse of float in 3 Probably a float not rational predicate that identifies and NaN would also be useful Alternatives 2 and 3 both also require distinct external represen tations for flonum and non flonum rationals If an external repre sentation denotes a flonum it may also be desirable to require rep resentation information to accurately determine the meaning of the literal More on the issue of external representation in Section 6 6 Alternatively all numerical literals denote rational numbers and the program must convert them to flonum representation explicitly via rational gt float Alternatives 1 and 2 can both be implemented as conservative extensions of RRS by the following measures e Support integers and rationals of arbitrary precision e Have all RRS numerical operations convert flonum argu ments to fraction before proceeding Or assert correctness by other means e Interpret inexact as float Specifically take inexact to mean float and exa
33. o explain than with R gt RS as is the remedy 6 Useful numerical operations In this section we disucss alternatives to R RS s default set of nu merical representations Any such design necessarily represents a subjective choice however It should be rich enough to be con venient e g having both lt and gt but leave less frequently used operations like gcd and 1cm to specialized libraries Here is pos sible list of exact operations to be present in the core language of a Scheme system rational decimal fraction binary fraction integer non negative integer positive integer Section 6 1 negative zero non negative positive compare sign x y Section 6 2 lt lt gt gt min max sign abs if sign x negative zero positive Section 6 2 alias expt floor ceiling truncate extend round Section 6 3 round fraction floor log abs Section 6 4 div mod Section 6 5 numerator denominator string gt rational rational gt string Section 6 6 3Of course fractional arithmetics requires a gcd operation internally but including rarely used operations in the default set carries a conceptual cost We discuss the major deviations from RRS 6 1 Numbers The type predicates rational decimal fraction binary fraction integer non negative integer positive integer reflect the abstract chain of numbers as introduced in Section 3 As mentioned already in Section 3 non negative and
34. or to apply an exact operation such as to or NaN whereas 0 are both treated as 0 by the exact operations At this point it is natural to ask whether the inexact numerical oper ations such as float float etc should accept all rational num bers or only those represented as flonum If the inexact operations only accept flonum arguments a Scheme system must provide at least a conversion operation rational gt float Similarly should the exact operations accept flonums unless they are special val ues In other words should the domains for exact and inexact operations be completely disjoint with explicit conversion at all times Three basic alternative kinds of type permeability seem to exist in this spectrum 1 The flonum representation is just another partial machine rep resentation for rational numbers plus special values and all numerical operations exact or inexact accept all rational numbers as arguments It is however an error to apply exact operations to and NaN 2 As in 1 flonum is just another partial representation of ratio nal numbers plus special values but inexact operations are only defined on flonum Programs make use of the rounding operation rat ional gt float to convert explicitly 3 The flonum representation is completely distinct from imple mentation of rationals In other words the exact operations are not defined on flonum and the inexact operations are un defi
35. positive in tegers are exposed because of their ubiquitous nature Concerning decimal and binary fractions refer to Section 6 4 6 2 Comparisons The additional comparison operations increase programming con venience With respect to R RS there are two major additions The compare procedure and the if sign special form dispatching on the sign of a rational number Compare has been included for efficiency All other comparisons can be expressed in terms of a single call to compare which can be implemented without allocating any intermediate objects at all If sign has been included because a frequent task in programming is distinguishing between the three possible results of a comparison 6 3 Rounding rationals to integers For rounding rationals into integers the procedures floor ceiling truncate extend and round provide the rounding modes towards 0 and towards the nearest integer The precise mathematical definitions of these functions are the ob vious ones with the exception of breaking ties in round which breaks ties towards even just like RRS and IEEE 754 All of these operations are useful and common in numerical pro grams Breaking ties towards even and towards zero is symmet ric in the sense that p x p x for all x where p denotes the rounding function Breaking ties towards appears naturally in div and mod as defined in Section 6 5 Finally observe that round ing with breaking ties
36. re specific ones In particular there is usually a mechanism converting number types automatically when required for an operation a process often called numeri cal promotion 15 Section 6 5 2 2 6 7 9 Section 5 6 In Scheme automatic conversion can occur both along the integer number axis and along the exact inexact axis Also information may get lost during any conversion of numbers even up the tower In MzScheme for example the following occurs expt 10 309 0 0 gt tinf 0 even though expt 10 309 has an exact representation as an in teger There are several reasons for loss of information Bignums can be arbitrarily large whereas fixed precision floating point formats are limited in range Exact rationals can have arbitrary precision whereas binary floating point formats even if they have arbitrary precision can only represent binary fractions where the denomina tor is a power of two In effect the intuition of the numerical tower as a chain of sub sets is invalid for all actual Scheme systems having a floating point representation or imposing limits on the number types 2 5 Lack of inexact control flow RRS defines in Section 6 2 2 which numbers are exact A number is exact if it was written as an exact constant or was derived from exact numbers using only exact op erations Unfortunately the following function is perfectly capable of return ing an exact result given inexact
37. s the confusion of programming with mixed exact and inexact floating point arithmetic Objective Caml 14 keeps the domains and types for floating point numbers completely separate from that of integers A program can not use them interchangeably it must explicit convert The floating point operations have names different from the integer operations for floating point addition etc Keeping the floating point numbers separate from the rest is easier in Objective Caml than it is in Scheme because Caml does not have built in rational numbers Hence there is no choice but the read 0 7 as a float Haskell 98 10 also has a sophisticated type hierarchy for its nu merical types including rational numbers and single and double precision floating point numbers It keeps the various numerical types separate but uses its type class mechanism to use a single set of operators for all numerical types and make parts of the nu merical domains look like subtype hierarchies Just like our pro posal Haskell mandates that a literal containing a decimal dots rep resents its corresponding rational number accurately Two methods fromInteger and fromRat ional overloaded over their respective result types negotiate between literals and the contexts that receive them Ambiguities concerning the numerical types are frequent which is why the default declaration can specify a strategy for resolving them Common Lisp 18 does not have inexactness as a
38. section suggests that the numerical tower of R RS is not a good model for numerical computations in a computer program at least not for all of them Moreover attribut ing exactness to numbers in the way RORS leads to inconsistencies In this section and the following two we examine the consequences of splitting operations along the exact inexact axis instead of the numbers The exact arithmetic operations satisfy strong algebraic properties such as associativity commutativity distributivity total A typical example of surprises with mixed exact inexact computation appeared in Sperber s Introductory Computing class Students had to write a procedure for visualizing the Mandelbrot set The task boils down to iterating the function z gt z c for different complex parameters c For visualization the procedure draw mandelbrot enumerates points in a rectangle defined by upper left corner width and height Many students observed that their program seemed to hang for some inputs but not for others This occurred when only literals without decimal point were used as operands for draw mande1lbrot in which case the program computes the iteration using exact fractions As the iteration progresses the internal representation of the fraction gets very large very quickly Putting a decimal point into one of the numerical literals or placing an exact gt inexact at almost any point in the program would fix things there is no recognizably
39. sible and even computationally inexpensive 7 Implementation Issues In this section we address the most important implementation is sues that arise with our proposal 7 1 Exact operations on flonums In design alternatives 1 and 2 numbers represented as flonums will be converted into fractions when an exact operation requires it This might lead to surprises in terms of time and memory con sumed because exact representations can and generally do grow quickly with arithmetic depth This is the price of exactness However if problems arise from exact operations on flonums they are easy to detect slow execution and have a specific remedy Re place exact operations by inexact operations and investigate numer ical stability RSRS on the other hand makes it much harder to identify and systematically fix this kind of problems because ex actness is not a static property of the program In other words the programmer must investigate the run time propagation of inexact ness in order to understand the algorithm actually being executed 7 2 Generic arithmetic The exact arithmetic operations need to dispatch on the represen tations of their arguments a typical implementation will at least use separate representations for fixnums bignums and true frac tions This is no different from the situation in R RS and a Scheme system can employ the same technique as before to perform the dispatch for example via exhaustive case analys
40. t case no tag ging is necessary The controversy around this approach suggests against it 12 Scheme has long been one of the few languages to specify that a round trip of conversion of a number to an external representation and back should preserve that number Hence it comes as little surprise that the most important publications about efficient and ac curate algorithms to achieve this purpose come from the Scheme community 3 2 19 1 9 Conclusion In Section 1 1 R RS says Scheme s model of arithmetic is designed to remain as independent as possible of the particular ways in which numbers are represented within a computer Thus the distinction between integer and real arithmetic so important to many programming languages does not ap pear in Scheme We have shown that the behavior of realistic programs is in fact very much dependent on the particular number representations cho sen by an implementation The distinction between integer and real arithmetic is important to many other languages because it is im portant to programs Following this design guideline RRS makes is very difficult to write portable programs employing inexact arith metic Inexact arithmetic is too underspecified to allow a program mer to predict what a particular program will do running in different Scheme implementations At the heart of the problem is the notion of inexact numbers itself a more useful basis for the design of a set of nu
41. ted range of numbers of any type As a minimal requirement exact integers must be present throughout the range of numbers that may be used for indexes of lists vectors and strings In addition Section 6 2 2 specifies that the representation of a num ber is flagged either exact or inexact and that operations should propagate inexactness as a contagious property Hence numbers in R RS are not just organized according to the numerical tower but also according to exactness The exact inexact distinction is claimed to be orthogonal to the dimension of type The rest of this section enumerates some of the most significant problems with the RRS specification 2 1 Not enough numbers Numbers are in short supply in RORS As quoted above the only numbers a Scheme system must support are indices for arrays lists and strings A Scheme system that supports only integers 0 255 can be perfectly conformant Of course the use of limited precision fixnum arithmetic can improve performance However we conjecture that the cost of allowing the standard arithmetic operations to only support limited precision the loss of algebraic laws transparency and reproducibility is greater than the benefit 2 2 Unspecified precision of inexact numbers RRS puts no constraints on the range or precision of inexact numbers In particular the description of exact gt inexact and inexact gt exact says These procedures impl
42. that b lt x for integer b b gt 2 and non zero rational x Note that e is negative if and only if x lt 1 Coming back to round fraction define for x 0 f p sue pome 1 e Iog x 2 Clearly this definition can only result in the form 1 if the rounding function p is well behaved For this reason we require that p w is integer and p u u lt 1 for all rational u This is the case for round floor ceiling truncate and extend In the case of round even the tighter bound p u u lt 1 2 holds For x 0 define 0 Under these conditions the following error bound holds x lt pox Proof jp xo pte peep pene agp ert p m e 1 promt x It remains to be shown that the conditions on p imply the form 1 Observe that a positive u is never rounded into a negative p u and vice versa This means that we only need to consider x gt 0 In this case b lt x lt pet by definition of e which implies prle lt xb lt b Applying p we obtain pri lt p xb 1 lt b because u lt p u lt fu Hence we have shown that has at most m non zero digits in its b ary expansion Note that round fraction ignores several details of actual floating point formats The exponent of round fraction is un limited in magnitude which means overflow and mantissa denor malization o 0 do not occur Also underflow the production of a number of magnitude too
43. tor y denominator x numerator y if negative n d quotient dn 1 d quotient n d zero y 0 negative y let n 2 numerator x denominator y d denominator x numerator y if lt n d quotient d n 2 d quotient n d 1 2 d define mod x y x div x y y Figure 3 Defining mod and div using RRS assuming exact rational arithmetics e the output of write and the input of read e numbers printed out for human readers e numbers printed for consumption by other non Scheme pro grams and read from other programs Since the number formats used for consumption by humans and non Scheme programs vary wildly and uncontrollably they are properly the subject of one or probably several libraries and be yond the scope of this paper We focus on literal syntax and on the syntax used by read and write In Scheme to preserve some of the desirable properties of the lan guage the literal syntax must be compatible with the format used by read and write The simple minded approach to the external representation issue is to just have one uniform external representation for all machine number formats each representation stands for a unique rational number and converting a number to its representation is an exact operation However many floating point numbers have quite long representations as fractions making this choice prohibitive in t
44. ttle reproducibility What is the cause of these problems RORS takes the stance that programs using exact arithmetic are essentially the same as pro grams using inexact arithmetic The procedures they use are the same after all only the numbers are different In reality pro grams using inexact arithmetic operations are inherently different from programs using only exact operations By blurring the dis tinction R RS complicates writing many programs dealing with numbers We know of no design approach which does successfully unite exact and inexact arithmetic into a common set of operations without sacrificing transparency and reproducibility In this paper we examine the specific problems with the numeri cal operations specified in R gt RS and consider alternative designs Specifically our contributions are the following e We identify the design fallacies concerning the numerical op erations specified in R RS and their practical consequences e We show how to design numerical operations around the idea that operations rather than numbers are exact or inexact The design has the following properties It uses a different numerical tower that is a more appro priate model for realistic program and which a Scheme system can realistically represent accurately All standard numerical operations operate exactly on ra tional numbers of infinite precision The floating point operations are separate procedures e W
Download Pdf Manuals
Related Search