[ruby-core:25672] Re: [Bug #2121] mathn/rational destroys Fixnum#/, Fixnum#quo and Bignum#/, Bignum#quo

On Sun, Sep 20, 2009 at 3:29 AM, brian ford <[e-mail]> wrote:
> Hi,
>
> On Sat, Sep 19, 2009 at 1:04 AM, Charles Oliver Nutter
> <[e-mail]> wrote:
>> On Sat, Sep 19, 2009 at 12:28 AM, Joel VanderWerf
>> <[e-mail]> wrote:
>>> Perhaps it should be the responsibility of users of numeric operators to
>>> #floor explicitly when that is the intent, rather than rely on the (mostly
>>> standard, sometimes convenient, but questionable) 1/2==0 behavior. Doing so
>>> would make it easier to adapt the code to float, rational, or other numeric
>>> types.
>>>
>>> In your proposal, would Rational(1,3) be the preferred notation, since
>>> 1/3==0? Or would there be something else, 1//3 or ...?
>>>
>>> I've always thought of mathn as a kind of alternate ruby, not just another
>>> core library, hence to be used with caution...
>>
>> I think Brian Ford expressed what I feel best...there should always be
>> another method or operator. Using another operator or method is an
>> explicit "buy-in" by the user--rather than a potential (at some
>> undetermined time in the future) that everything you know about
>> integral division in your program changes wildly. It should not be
>> possible for any library to undermine the basic mathematical
>> expectations of my program. Doing so, or expecting the user to do
>> extra work to guarantee the *common case*, is a recipe for serious
>> failure.
>
> There are a number of issues combined here, but I think they generally
> reduce to these:
>
> 1. How do you model the abstractions that are number systems in the
> abstractions that are classes and methods.
> 2. Should the behavior of mathn be acceptable in the core language.
>
> We seem to think of the basic mathematical operations +, -, *, / as
> being roughly equal. But of these four, division on the integers is
> distinct. The set of integers is closed under addition, subtraction,
> and multiplication. Given any two integers, you can add, subtract, or
> multiply them and get an integer. But the result of dividing one
> integer by another is not always an integer. The integers are not
> closed under division. In mathematics, whether a set is closed under
> an operation is a significant property.
>
> As such, there is nothing at all questionable about defining division
> on the integers to be essentially floor(real(a)/real(b)) (where
> real(x) returns the (mathematical) real number corresponding to the
> value x, because the integers are embedded in the reals and the reals
> are closed under division). You basically have five choices:
>
> 1. floor(real(a)/real(b))
> 2. ceil(real(a)/real(b))
> 3. round(real(a)/real(b)) where round may use floor or ceil
> 4. real(a)/real(b)
> 5. raise an exception
>
> In computer programming, there are a number of reasons for choosing 1,
> 2 or 3 but basically it is because that's the only way to get the
> "closest" integer (i.e. define division in a way that the integers are
> closed under the operation) . Convention has selected option 1.
> Numerous algorithms are implemented with the assumption that integral
> division is implement as option 1. It's not right or wrong, but the
> convention has certain advantages. In programming, we are typically
> implementing algorithms, not just "doing math" in some approximations
> of these abstractions called number systems. Any system for doing math
> takes serious steps to implement the real number system in as
> mathematically correct form as possible.
>
> My contention that we should always have two operators for integral
> division is a compromise between the need to implement algorithms and
> the desire to have concise "operator" notation for doing more
> math-oriented computation. Given that programming in Ruby is more
> about algorithms than it is about doing math, it's unreasonable to
> expect (a/b).floor instead of a / b. At the same time, math-oriented
> programs are not going to be happy with a.quo b. The reasons for
> options 1 and 4 above are not mutually exclusive nor can one override
> the other.

Actually in most languages which I've encountered, and that's quite a
few. Mixed mode arithmetic has been implemented by having some kind of
rules on how to 'overload' arithmetic operators based on the
arguments, not by having different operator syntax.

And those rules are usually based on doing conversions only when
necessary so as to preserve what information can be preserved given
the arguments,

So, for example

    integer op integer - normally produces an integer for all of the
'big four' + - * /
    integer op float    - normally produces a float, as does float op integer

As new numeric types are added, in languages which either include them
inherently or allow them to be added, this pattern is usually
followed.

Smalltalk has the concept of generality of a number class. More
general classes can represent more numbers, albeit with some potential
for adding 'fuzziness'  in the standard image Floats are the most
general, then Fractions, then equally LargePositiveIntegers and
LargeNegativeIntegers (which together serve the same role as Bignum in
Ruby), then SmallInteger (Ruby's Fixnum).

> The mathn library is clearly exploiting an implementation detail. Were
> Ruby implemented like Smalltalk (or Rubinius), mathn would have never
> been written as it is. The fact that it is even possible to load mathn
> results from the fact that countless critical algorithms in MRI are in
> the walled garden of C code. That's not true for your Ruby programs.
> Any algorithm you implement that relies on the very reasonable
> assumption of integral division will be broken by mathn.

The problem with mathn is that it introduces new numeric types, and
also changes the behavior of the existing types, particularly integer,
so that when mathn is included

   integer / integer produces a rational if the result can't be
reduced to an integer.

This is at odds with most languages and, as Charles points out, it
effectively changes the 'rules of physics' for other code which is
likely unaware that mathn has been introduced.

In Smalltalk, there is a standard Fraction class and integer division
does in fact return a Fraction rather than an Integer. But that's
known and expected by Smalltalk programmers.

>
> You can say, "but mathn is in the standard library, you have to
> require it to use it". But that ignores the fact that requiring the
> library fundamentally changes assumptions that are at the very core of
> writing algorithms. Essential computer programming and mathn can never
> coexist without jumping through hoops.

Yes this is a problem IMHO.  The difference between Ruby and Smalltalk
here is that one language starts out including Rationals/Fractions,
and the other treats them as an optional add on which, when added,
changes the rules.


> This is the point were some grandiose scheme like selector namespaces
> are suggested. But I think the simple solution of two distinct
> operators handily solves the problem of the messy facts of
> mathematical number systems implemented in very untheoretic (i.e.
> really real) silicon.
>
> As for which symbol to select, what about '/.' for real(a)/real(b).

Well, first the problem we are talking about is Rationals, not Floats,
and second, what happens as more numeric classes are introduced.

Another alternative would be to change mathn (or maybe make a new
alternative mathn for compatibility for programs already using mathn)
which

   1. Left 1 / 2 as producing the Integer 1
   2. Allowed explicit instantiation of Rationals
          * Rational.new(1,2)  # i.e. make the new method public.
          * Change Object#Rational to always return a Rational for an
integer argument, with a denominator of 1.
          * Integer#to_rational which could be implemented as:
                class Integer
                     def to_rational
                          Rational(self)
                     end
                 end

Then rational arithmetic could be implemented so that


     5 / 3  => 1
     5.to_rational / 3 => 5 / 3
     5 / 3.to_rational => 5 / 3

     (5.to_r / 3).to_i => 1

Which would be in-line with standard arithmetic in Ruby IMHO.

Note: it might be more ruby-like to name the coercion method to_r
instead of to_rational, but that might be confused by some as meaning
something else like to real, although I don't really thing that that
would be that much of an issue.


-- 
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale