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

*To*: srfi-77@xxxxxxxxxxxxxxxxx*Subject*: Unifying the two generic arithmetic alternatives*From*: Andrew Wilcox <awilcox@xxxxxxxxxxxxxxxxx>*Date*: Mon, 14 Nov 2005 16:16:33 -0800 (PST)*Delivered-to*: srfi-77@xxxxxxxxxxxxxxxxx

Here's an idea that I hope will help unify the competing alternatives of R5RS-style Generic Arithmetic and Generic Exact Arithmetic. My proposal has contagious inexactness, while also offering generic procedures that perform the same operation across different types. I am indebted to your work on SRFI-77 and [Egner et al. 2004], which explained and clarified many of the issues for me. Confusion Around Exact/Inexact SRFI 77 uses the words "exact"/"inexact" for a variety of concepts: * Whether the result of a calculation is known exactly or not. * Whether an arithmetic operation is performed accurately or fast and approximately. * Certain number representations such as flonums are said to be "inexact" representations. * Whether or not a Scheme implementation is free to read a external representation such as "0.1" and store an approximation of the number. While all these concepts are related, I believe this ambiguity in language makes the issues harder to think and talk about. Thus I'd like to propose a different terminology -- at least for the second concept. In deference to EXACT? an INEXACT? in R5RS, I'll continue to call the first concept "exactness". For the second, I propose the term "accurate". Now I can say, "I'd like to be able to perform an accurate add on inexact arguments." You can disagree with me on whether such an operation should be supported or not. But at least I can *say* it! In contrast, using the current language of the SRFI, for me to say "I'd like to be able to perform an exact add on inexact arguments" sounds rather nonsensical. The third concept that "flonums are inexact" is misleading, in my opinion. Aside from the nonrationals INF and NaN, every floating point number represents some particular rational number. A floating point *operation* may choose a number close to but not the same as the true result, a Scheme implementation may feel free to print out an decimal approximation of a floating point number, but that doesn't make the floating point *number* not be some particular number. Harmful Generic Operators Some languages overload operators so that, for example, X + Y is a plus operation if X and Y are numbers, and a string concatenation if X and Y are strings. In dynamically typed languages this is a serious pain. In JavaScript, for example, you end up having to do things like var sum = (foo - 0) + (bar - 0) to ensure that you're getting an add operation instead of a string concatenation. R5RS is a pain in the same way because + can perform an accurate add or a fast approximate add, depending on its arguments. Both choices are wrong! Simply because I've happened to have accurate calculations up to this point in my program, doesn't mean I want to have a slow operation now! Simply because I've had approximate calculations up to now doesn't mean that now I want an approximate operation that's going to give me a *further* loss of precision! If I want an accurate add in R5RS, I have to coerce my arguments to exact numbers. But now I've lost the information of whether any of my arguments were inexact! If I want a fast add in R5RS, I have to coerce my arguments to inexact. And I can't just do it at the beginning of my calculation! Procedures in R5RS are permitted to return an exact number if they can prove that the exactness of the result is not affected by the inexactness of its arguments. So at any point along my calculation my value may turn into an exact one and suddenly I'm using SLOW arithmetic! Now, don't get me wrong. I like contagious inexactness. (I make a proposal for supporting contagious inexactness below). I'm delighted when a Scheme implementation returns an exact result for (* 0 X). However, I hope that I've made the strong point that *choosing* whether to do an accurate or approximate calculation on the basis of the exactness of the arguments is the *wrong* thing to do. Useful Generic Operators In contrast, generic operators are useful if they implement the SAME operation while accepting different types. For example, in Perl "." is a string concatenation operator. It always concatenates. But it accepts numbers, which it will convert to strings. 1 . 2 => "12" In practice this works well. I use this principle throughout my proposal. Accurate Add Let's construct a useful generic ACCURATE+ operator. ACCURATE+ accepts any kind of number, including flonums, but excepting NaN and INF because accurate calculations can not be performed with them. The procedure always performs an accurate (if perhaps slow) calculation. Note that a floating point number (aside from INF and NaN) represents one and precisely one rational number. Thus to perform an accurate calculation with a flonum, we simply use its actual value. I agree with [Egner et al. 2004] that flonum +0 and -0 should be treated as 0 in accurate calculations. The Scheme implementation is free to return any type representing the number, as long as the result is accurate. In practice a Scheme implementation will probably always just convert a flonum to a ratnum, and that's fine. But it's not required to do so by this proposal. If adding a flonum 1 to a flonum 2 has the accurate result of a flonum 3, the implementation is free to return a flonum 3. I talk about how to handle inexactness below. Fast Add FAST+ always performs a fast (if perhaps inaccurate) operation -- returning a flonum, or a complex number made up of flonums. Arguments which are too large or small to be represented as a flonum are converted to +/- 0/INF. Like ACCURATE+, FAST+ is a generic procedure that accepts any kind of number as an argument. Contagious Inexactness I propose supporting contagious exactness in an orthogonal way, which: * makes it useful in a wider variety of algorithms * doesn't force accurate/slow operations on the programmer * simplifies the standard In this proposal inexactness becomes an *independent* attribute of values. Thus EXACT? and INEXACT? test an inexactness bit in the type, and EXACT->INEXACT and INEXACT->EXACT return the value with the bit set or cleared. Note that INEXACT->EXACT and EXACT->INEXACT don't do any *conversions* in this proposal. To take an example of [Egner et al. 2004], (< x y) in this proposal returns an *inexact* boolean, if either X or Y is inexact. Inexactness thus propagates through the entire calculation, and is not lost when I do a comparison. Now I can use accurate operators without losing information about the inexactness of my result: (inexact? (accurate+ 3 #i4)) => #t Operations that use approximate calculations set the inexactness flag on their return value. (inexact? (fl/ 10 3)) => #t But Let It Be Optional I understand that many Scheme implementors want to minimize the number of bits of type information that they need to carry around, and others would like to minimize the complexity of flow analysis. Thus I propose that support for EXACT?, INEXACT? and contagious inexactness be optional in R6RS. Comparison with Generic Exact Arithmetic ACCURATE+ isn't *required* to make any conversions in the types of its arguments in the way that Generic Exact Arithmetic converts all arguments to "exact" representations. Unlike with Generic Exact Arithmetic, inexactness information is not lost when an accurate add is used. Comparison with R5RS-style Generic Arithmetic Like R5RS-style Generic Arithmetic, in my proposal inexactness is contagious. This is a natural reflection of the idea that if you perform an operation on inexact arguments, you're going to get an inexact result. My proposal avoids some of the limitations of R5RS: * Inexactness is truly contagious. * Programmers are not forced to lose exactness information to use accurate procedures. * Generic procedures always perform the same operation across arguments of different types. Comparison with Exact Arithmetic ACCURATE+ is similar to ex+, given that what SRFI-77 calls "exact operations" is what I call "accurate operations". The differences are that ACCURATE+ accepts any kind of number, including flonums (leaving out only NaN and the infinities), and that inexactness information is not lost when the programmer wishes to use an accurate operation. Incomplete Though It Is There are obviously many more issues that would need to be dealt with for a complete proposal. However, I'm running over 250 lines of text in my email message here already, so I'll toss it out now to be stomped on. Cheers, Andrew Wilcox

**Follow-Ups**:**Re: Unifying the two generic arithmetic alternatives***From:*Marcin 'Qrczak' Kowalczyk

**Re: Unifying the two generic arithmetic alternatives***From:*John.Cowan

**Re: Unifying the two generic arithmetic alternatives***From:*bear

- Prev by Date:
**(- 1.0 1.0) => 0 ; not +0.0 ?** - Next by Date:
**Re: Unifying the two generic arithmetic alternatives** - Previous by thread:
**(- 1.0 1.0) => 0 ; not +0.0 ?** - Next by thread:
**Re: Unifying the two generic arithmetic alternatives** - Index(es):