Splitting Numeric to separate Sum from Product

On Thu, Sep 08, 2011 at 01:22:20PM +1000, Ben Hutchison wrote:
> Would there be any problem in factoring out two super-trait
> typeclasses above Numeric, enabling addition and multiplication to be
> defined separately?

Hi Ben,

I became interested in improving scala.math.Numeric around November
2010 when I started trying to use it.

The problems I ran into with scala.math.Numeric related to:

* lack of speed
* lack of division/modulus
* lack of useful conversions

I have addressed these concerns as well as I can in an alternate
Numeric library (and compiler plugin) which are located on Github here:
https://github.com/azavea/numeric.

If you're interested in trying out your idea feel free to fork that
repo, make your changes, test them, and send me a pull request. When
doing so you should try to make sure that you are maintaining the
existing performance numbers (which I've worked very hard to get). :)

Ultimately, we may need a situation where we have both minimal type
classes relating to algebraic properties of different types (e.g.
groups, rings, fields, etc) as well as a type for essentially
"abstracting over everything you can you do with the AnyVal number
types". My use case is closer to the latter, but many people will also
want the former. Right now I don't think scala.math.Numeric addresses
either need very well.

I am not sure what the road map is for improving
com.scala.math.Numeric. Substantial changes to it will probably break
binary compatibility, so there is some reluctance to do that. It's also
true that since very few people seem to use Numeric currently there
isn't a lot of demand for these changes. Hopefully these kinds of
discussions and work on alternate implementations will generate more
interest.

Numeric doesn't support division or modulus, but scala also defines the traits scala.math.Fractional for division (implicit instances for Double, BigDecimal, etc.) and scala.math.Integral for integer division and modulus (implicit instances for Int, BigInt, etc.).
I think Numeric's main motivation was to unify the handling of basic numeric types (like BigDecimal, double, float, int, long, char, etc.) vs. modeling the algebraic structure of any type. It's design is nice and simple as you can easily add rationals into the mix or what-have-you. However, I think trying to expand it to vectors, strings, etc. probably better belongs in a separate library that tries to more accurately model algebraic structures. Numeric (and Fractional and Integral) is simple enough to be understandable by most people (vs. monoids, rings, fields, etc), while still providing a good amount of flexibility.
I mean, although you could create a simple Monoid supertrait of Numeric to handle your Vector case (and Strings, eg), chances are you are going to want to do a lot more with your vectors than just sum them. You'd probably want an entire library dedicated to dealing with them.
Moreover, matrices and vectors have the problem that their dimension is an integral part of what operations are defined. So even defining something as simple as Vector addition requires runtime checks with a Numeric-like Monoid trait. Since scala's Numeric instances seem to be wholly against runtime exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity, rather than an exception), I'm not sure if Vectors would mix well.
On Thu, Sep 8, 2011 at 9:20 AM, Erik Osheim <erik@plastic-idolatry.com> wrote:

On Thu, Sep 08, 2011 at 01:22:20PM +1000, Ben Hutchison wrote:
> Would there be any problem in factoring out two super-trait
> typeclasses above Numeric, enabling addition and multiplication to be
> defined separately?

Hi Ben,

I became interested in improving scala.math.Numeric around November
2010 when I started trying to use it.

The problems I ran into with scala.math.Numeric related to:

 * lack of speed
 * lack of division/modulus
 * lack of useful conversions

I have addressed these concerns as well as I can in an alternate
Numeric library (and compiler plugin) which are located on Github here:
https://github.com/azavea/numeric.

If you're interested in trying out your idea feel free to fork that
repo, make your changes, test them, and send me a pull request. When
doing so you should try to make sure that you are maintaining the
existing performance numbers (which I've worked very hard to get). :)

Ultimately, we may need a situation where we have both minimal type
classes relating to algebraic properties of different types (e.g.
groups, rings, fields, etc) as well as a type for essentially
"abstracting over everything you can you do with the AnyVal number
types". My use case is closer to the latter, but many people will also
want the former. Right now I don't think scala.math.Numeric addresses
either need very well.

I am not sure what the road map is for improving
com.scala.math.Numeric. Substantial changes to it will probably break
binary compatibility, so there is some reluctance to do that. It's also
true that since very few people seem to use Numeric currently there
isn't a lot of demand for these changes. Hopefully these kinds of
discussions and work on alternate implementations will generate more
interest.

On Thu, Sep 08, 2011 at 11:26:17AM -0400, Tom Switzer wrote:
> Numeric doesn't support division or modulus, but scala also defines the
> traits scala.math.Fractional for division (implicit instances for Double,
> BigDecimal, etc.) and scala.math.Integral for integer division and modulus
> (implicit instances for Int, BigInt, etc.).

But when trying to abstract an algorithm across Int/Double the lack of
any concept that something like division is defined on both is
crippling. This is *especially* true given that both Int and Double
define the / operator, so in practice your code for those cases will be
*identical*. I haven't met anyone who's tried to use Numeric for
anything serious and hasn't hit this problem.

I haven't talked to anyone who *needed* the Fractional/Integral
distinction (re division) whereas I myself (and most others who've used
Numeric) have had to give up because of the lack of division. To be
specific, my work involves processing large rasters of numbers
(integral or fractional). Not being able to write a function once that
will work with Int and Double is a deal-breaker.

Do you have a specific reason for *not* wanting division defined on
Numeric. I can understand wanting to have Integral/Fractional type
classes to limit which types can be used, but I can't understand
wanting to cripple Numeric.

> I think Numeric's main motivation was to unify the handling of basic numeric
> types (like BigDecimal, double, float, int, long, char, etc.)
> vs. modeling the algebraic structure of any type. It's design is nice and
> simple as you can easily add rationals into the mix or what-have-you.
> However, I think trying to expand it to vectors, strings, etc. probably
> better belongs in a separate library that tries to more accurately model
> algebraic structures. Numeric (and Fractional and Integral) is simple enough
> to be understandable by most people (vs. monoids, rings, fields, etc), while
> still providing a good amount of flexibility.

I agree that having a separate library for algebraic structures makes
sense. I don't agree that the current design is nice or simple, unless
you:

1. Already understand type classes
2. Don't need division
3. Don't want to be able to mix literals and generic types
4. Don't mind things being slow

My sense from your reply is that you feel like the current Numeric
trait in Scala is "fine" which I strongly disagree with. I do agree
that with Vectors, Matrices, etc. you will have all sorts of additional
concerns that will probably merit their own library (like Scalala or
similar).

Well, you have met at least one person (me). The main thing is that while double and int both define a "division" operator, they are not the same thing, and I honestly haven't run into the case where I wouldn't want to separate the 2 (though I assume you and I are working on fairly different projects).
I actually like the separation of Numeric and Fractional (keep in mind, Fractional inherits from Numeric). I use it these extensively in a geometry library I developed and its nice that when you see a function that only requires Numeric, as you know your answers will be exact with BigDecimal or Ints. When you see a Fractional requirement, you know you need to use Rational numbers to achieve an exact result. You could also use Double or BigDecimal, but then the results are not guaranteed to be exact. Since all my geometric objects are abstracted over the number type, being able to know what operations you can apply to them is nice.
In this library, many predicates and orderings can be defined using only addition & multiplication. For instance, I define an intersection ordering for pairs of lines. This ordering doesn't require division, but this would not be immediately obvious to someone seeing this for the first time, since finding and reporting the intersection DOES require division (unless you are using homogeneous coordinates). Having only a Numeric implicit required is a reassurance to a user of the library, since it means the ordering is correctly defined and exact for lines using Int, BigInt or BigDecimal (this wouldn't be the case if division were used).
The separation is also necessary for ints (I think), as integer division (in Scala) is not real division. I wouldn't want someone thinking they could use an Int when it will give an unknown/incorrect (as opposed to inaccurate) result. And, as noted above, it is nice to be able to see the wide range of operations available to you if you use Int (or BigInt), which may not always be obvious.

Hi Tom,

Thanks for your thoughtful reply and description of your use case. I'm
sorry if I came off as hostile but I couldn't tell if you actually
needed the current Numeric behavior or were just playing devil's
advocate.

First of all, is your library online? I have been working on my own
classes for complex and rational numbers and would love to see what
you've come up with. And please feel free to give me feedback on my own
Numeric project.

It does sound like our cases are different. In one of my cases, I am
dealing with large (e.g. 100M cells) grid of numbers (could be 64-bit
floating point, 32-bit integer, whatever) which represents some kind of
geographical data (e.g. elevation data, soil type, etc). I want to be
able to write operations which work no matter what the underlying data
type is, without having to convert the underlying data type, or
duplicate code.

Operations on this data might include division, for instance when
converting units, rescaling or normalizing data. In these cases,
maintaining exact precision is usually less important since the data is
usually already aggregated/sampled. Instead we are very focused on
performance, since we need to be able to do this processing at
"web-appropriate speeds".

Floor division and true division definitely are different operations,
but I think even the fact that we use the same operator symbol for both
shows that we consider them somewhat analogous. While abstracting
across integral/fractional types may be inappropriate in some contexts,
do you think it's *always* inappropriate and should be forbidden?

I strongly believe there needs to be some way to do this in Scala (as
there is in most dynamically typed languages, e.g. Clojure, Python,
Ruby, etc). Java completely lacks this ability and I think it is a
feather in Scala's cap that it is possible.

I wonder if there isn't a way to achieve the kind of "numeric precision
tracking" which you're doing in a better way, rather than using the
(current) properties of Fractional and Numeric? This could involve
creating additional type classes which group the types according
to which operations they can use while maintaining precision.

I suggest this because everyone has different ideas of how much
precision they need. In my case, I'm willing to be limited to the
precision of the underlying data type. In finance, I think most people
don't need to use Rational (because they don't need infinite precision
on fractions like 1/3, but only as much as they need) and are willing
to consider division on BigDecimal "precise enough". In your case, you
don't want to lose *any* precision. I don't think we can settle this
issue just one way, because everyone has their own requirements.

Hi,

I pretty much have the same problems as everyone wit Numeric here.

An example hereis the work to optimize Range/NumericRange Numeric where
Numeric has largely prevented me on making the "sum" method run in < 1ms
instead of > 35s for "1 to Int.MaxValue".

The bad thing is, that I can't start requiring Integral or Fractional
without breaking the API, which just provides me with a Numeric.

So I pretty much agree that we need a better types dealing with numbers.
Maybe it is possible to get additional people interested in that topic
(e. g. people from Scalala) on the same table, so see if there is common
ground which the standard libraries can provide to help interoperability
between different projects.

Seeing what Anti-XML does Scala devs generally seem to be willing to
break the ABI if people can demonstrate measurable and meaningful
benefits, so maybe there is a chance to get this into 2.11 if a workable
solution is available _before_ 2.10 ships?

Thanks and bye!

Simon

On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer wrote:
> Numeric (and Fractional and Integral) is simple enough
> to be understandable by most people (vs. monoids, rings, fields, etc), while
> still providing a good amount of flexibility.

Actually, the problem is precisely that Numeric is not simple enough.
I don't think its about adding "algebraic structure" or "monoids" into
the library. Rather, simply splitting the methods already there into
smaller, more focused units. I suspect that it can be done while
maintaining backwards compatibility.

Numeric defines Addition and Multiplication in one interface. Thats
unnecessary coupling: considering TraversableOnce.{sum, product}
(presently the main application/motivation of Numeric in the library),
sum requires you to pass a definition of multiplication, even though
it never uses it. Similarly, product requires Addition even though
it's never used.

chances are you are going to want
> to do a lot more with your vectors than just sum them. You'd probably want
> an entire library dedicated to dealing with them.

Indeed. Anyone can create such a library if they wish, using their
preferred design. But how and where will it integrate with the
standard library? The touchpoints may likely include sum and product,
and it makes sense for the standard lib to require the minimal
required interface from the provider of Numeric-like operations.

> Moreover, matrices and vectors have the problem that their dimension is an
> integral part of what operations are defined. So even defining something as
> simple as Vector addition requires runtime checks with a Numeric-like Monoid
> trait. Since scala's Numeric instances seem to be wholly against runtime
> exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,
> rather than an exception), I'm not sure if Vectors would mix well.

A counter example, from Stanford PPL's Delite project, which
currently has several EPFL Scala team members working on/around it. It
would seem that they see value in numeric operations over Vectors &
Matrices:

https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/...

-Ben

PS Delite's Arith numeric typeclass also demonstrates the diversity
around how to handle the division operator, having chosen a different
approach to the standard library.

Hi,
> Numeric defines Addition and Multiplication in one interface. Thats
> unnecessary coupling: considering TraversableOnce.{sum, product}
> (presently the main application/motivation of Numeric in the library),
> sum requires you to pass a definition of multiplication, even though
> it never uses it. Similarly, product requires Addition even though
> it's never used.
>
Please god, no!

In some cases you need not only multiplication but also division to have
a reasonable fast algorithm.
In the particular case it is a difference between O(1) and a runtime of
less than one ms or O(n) and completely useless runtimes of minutes for
large collections for sum.

Have a look at the mail I wrote a few hours ago, where I excatly
described that problem.

Thanks and bye,

Simon

> The problems I ran into with scala.math.Numeric related to:
>
>  * lack of speed
>  * lack of division/modulus
>  * lack of useful conversions
>
> I have addressed these concerns as well as I can in an alternate
> Numeric library (and compiler plugin) which are located on Github here:
> https://github.com/azavea/numeric.
>
> If you're interested in trying out your idea feel free to fork that
> repo, make your changes, test them, and send me a pull request.

I like your approach, ie outlining the present shortcomings of Numeric
and developing specific proposals for improvement. I'll try to
collaborate with you on this.

I share some of your concerns with the present Numeric abstractions
and have some others that are complimentary to your own:

* One is the non-separability of Sum and Product ops, as mentioned here.

* The other is around stuff the present API doesn't include that I
find essential for doing alot of math: trig, exponential, random
numbers, indications of precision/error bounding. Theres a question
around how to make this available for those who need it, without
imposing on those who dont?

I don't have the time to detail the latter issue in full at present,
but I'll try to write it up in the next day or so.

-Ben
-Ben

On Fri, Sep 09, 2011 at 11:09:03AM +1000, Ben Hutchison wrote:
> * One is the non-separability of Sum and Product ops, as mentioned here.

Agreed. To be clear, I don't mind creating new traits for those (and
even implementing Numeric in terms of them) as long as Numeric can
continue to perform well.

In fact, given that complex numbers don't have a total ordering, the
current Numeric design (which has Numeric[A] implementing Ordered[A])
doesn't work so well for Complex numbers either. You can always fake
it, but that isn't fantastic, nor are runtime exceptions (the approach
that Python takes). So I think it does make sense to try to create type
classes that express exactly what we want/need.

> * The other is around stuff the present API doesn't include that I
> find essential for doing alot of math: trig, exponential, random
> numbers, indications of precision/error bounding. Theres a question
> around how to make this available for those who need it, without
> imposing on those who dont?

I've thought about this also. It would be good to be able to support
all useful math operations in the type class rather than requiring
conversions to Double (which may produce bad results when dealing with
very large and/or very precise types). I may try to do this soon, since
it's relatively easy (as long as the underlying types have
implementations).

Questions around floating point errors, precision bounding, etc are a
bit more thorny. I don't think it will be possible to solve those
without (potentially) expensive run-time checks and conversions, which
are a deal-breaker for me. I almost imagine using some kind of boxed
data type to do this, which could wrap the operations and detect
errors/precision changes.

It's worth strategizing about, at any rate.

Perhaps a trade-off could be to create a few new traits. Something more like,
trait Monoid[A] {  def zero: A  def add(x: A, y: A): A}
trait Ring[A] extends Monoid[A] {   def one: A  def sub(x: A, y: A): A  def mul(x: A, y: A): A}
trait Numeric[A] extends Ring[A] {  def div(x: A, y: A): A}
trait Fractional[A] extends Ring[A] {

On Thu, Sep 8, 2011 at 8:30 PM, Ben Hutchison <brhutchison@gmail.com> wrote:

On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer <thomas.switzer@gmail.com> wrote:
> Numeric (and Fractional and Integral) is simple enough
> to be understandable by most people (vs. monoids, rings, fields, etc), while
> still providing a good amount of flexibility.

Actually, the problem is precisely that Numeric is not simple enough.
I don't think its about adding "algebraic structure" or "monoids" into
the library. Rather, simply splitting the methods already there into
smaller, more focused units. I suspect that it can be done while
maintaining backwards compatibility.

Numeric defines Addition and Multiplication in one interface. Thats
unnecessary coupling: considering TraversableOnce.{sum, product}
(presently the main application/motivation of Numeric in the library),
sum requires you to pass a definition of multiplication, even though
it never uses it. Similarly, product requires Addition even though
it's never used.


 chances are you are going to want
> to do a lot more with your vectors than just sum them. You'd probably want
> an entire library dedicated to dealing with them.

Indeed. Anyone can create such a library if they wish, using their
preferred design. But how and where will it integrate with the
standard library? The touchpoints may likely include sum and product,
and it makes sense for the standard lib to require the minimal
required interface from the provider of Numeric-like operations.

> Moreover, matrices and vectors have the problem that their dimension is an
> integral part of what operations are defined. So even defining something as
> simple as Vector addition requires runtime checks with a Numeric-like Monoid
> trait. Since scala's Numeric instances seem to be wholly against runtime
> exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,
> rather than an exception), I'm not sure if Vectors would mix well.

A counter example, from Stanford PPL's  Delite project, which
currently has several EPFL Scala team members working on/around it. It
would seem that they see value in numeric operations over Vectors &
Matrices:

https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/dsl/optiml/capabilities/Arith.scala#L94

I didn't mean to imply that you shouldn't able to do arithmetic over vectors or matrices (it obviously makes sense), but more that I wasn't entirely sure if there was a reason why Numeric seems to eschew runtime exceptions.  

-Ben

PS Delite's Arith numeric typeclass also demonstrates the diversity
around how to handle the division operator, having chosen a different
approach to the standard library.

Yep. I prefer Numeric's approach, but clearly several opinions in the conversation take "Arith"'s side.

Whoops, accidently sent that while typing... Again:
trait Monoid[A] {  def zero: A  def add(x: A, y: A): A}
trait Ring[A] extends Monoid[A] {   def one: A  def sub(x: A, y: A): A  def mul(x: A, y: A): A}
trait Numeric[A] extends Ring[A] {  def div(x: A, y: A): A}
type Fractional = Numeric
trait Integral[A] extends Ring[A] {  def quot(x: A, y: A): A  def rem(x: A, y: A): A}
Now, implement implicit objects as before, but mixin Numeric AND Integral for Int as well. Now people can use Numeric for division, Integral if they want to specify integer-style division, and I can use Ring to indicate that division will not be used.

I cannot see how whether an addition goes through Numeric or not can change the complexity from O(1) to O(n). Certainly wrapping an object for each addition/multiplication has performance penalties, but this would only change the constant factor. I have seen some people here looking for nice ways to get around Scala type classes' need to wrap an object for each call for a while. I'm not sure if anything has come of this though.
It would be nice if we could somehow get the compiler to go from "num.mkNumericOps(a).+(b)" to "num.plus(a, b)".
On Thu, Sep 8, 2011 at 8:59 PM, Simon Ochsenreither <simon@ochsenreither.de> wrote:

Please god, no!

In some cases you need not only multiplication but also division to have a reasonable fast algorithm.
In the particular case it is a difference between O(1) and a runtime of less than one ms or O(n) and completely useless runtimes of minutes for large collections for sum.

Have a look at the mail I wrote a few hours ago, where I excatly described that problem.

Thanks and bye,


Simon

On Thu, Sep 08, 2011 at 10:12:56PM -0400, Tom Switzer wrote:
> I cannot see how whether an addition goes through Numeric or not can change
> the complexity from O(1) to O(n).

I think Simon is just referring to the fact that if you don't have
division you can't use something like (n * (n + 1)) / 2 to sum a
NumericRange, so instead you must manually add all the entries up by
hand.

> It would be nice if we could somehow get the compiler to go from
> "num.mkNumericOps(a).+(b)" to "num.plus(a, b)".

Agreed.

Coincidentally, my projects has an optional compiler plugin which does
exactly this. :)

On Thu, Sep 8, 2011 at 10:12 PM, Tom Switzer <thomas.switzer@gmail.com> wrote:

I cannot see how whether an addition goes through Numeric or not can change the complexity from O(1) to O(n). Certainly wrapping an object for each addition/multiplication has performance penalties, but this would only change the constant factor.

Indeed.  But when the constant factor is 40, you start to get worried.  (Or you start to think that you should be programming in Python or Groovy.)

On Thu, Sep 8, 2011 at 8:59 PM, Simon Ochsenreither <simon@ochsenreither.de> wrote:

In some cases you need not only multiplication but also division to have a reasonable fast algorithm.
In the particular case it is a difference between O(1) and a runtime of less than one ms or O(n) and completely useless runtimes of minutes for large collections for sum.

You're either running out of memory or the JVM is optimizing away your code entirely if you are going from ms to minutes.  If the JVM can turn your nominally O(n) operation into an O(1) one, so can you.  Otherwise it's not more than a factor of 100 or so in the very worst cases (double-boxed vs. primitive on every operation) unless you are really stressing the memory system.

  --Rex

Let us also not repeat the mistakes of haskell, by splitting Monoid into a Semigroup first. Please :)

On 09/09/2011 11:53 AM, "Tom Switzer" <thomas.switzer@gmail.com> wrote:
> Perhaps a trade-off could be to create a few new traits. Something more
> like,
>
> trait Monoid[A] {
> def zero: A
> def add(x: A, y: A): A
> }
>
> trait Ring[A] extends Monoid[A] {
> def one: A
> def sub(x: A, y: A): A
> def mul(x: A, y: A): A
> }
>
> trait Numeric[A] extends Ring[A] {
> def div(x: A, y: A): A
> }
>
> trait Fractional[A] extends Ring[A] {
>
>
> On Thu, Sep 8, 2011 at 8:30 PM, Ben Hutchison <brhutchison@gmail.com> wrote:
>
>> On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer <thomas.switzer@gmail.com>
>> wrote:
>> > Numeric (and Fractional and Integral) is simple enough
>> > to be understandable by most people (vs. monoids, rings, fields, etc),
>> while
>> > still providing a good amount of flexibility.
>>
>> Actually, the problem is precisely that Numeric is not simple enough.
>> I don't think its about adding "algebraic structure" or "monoids" into
>> the library. Rather, simply splitting the methods already there into
>> smaller, more focused units. I suspect that it can be done while
>> maintaining backwards compatibility.
>>
>> Numeric defines Addition and Multiplication in one interface. Thats
>> unnecessary coupling: considering TraversableOnce.{sum, product}
>> (presently the main application/motivation of Numeric in the library),
>> sum requires you to pass a definition of multiplication, even though
>> it never uses it. Similarly, product requires Addition even though
>> it's never used.
>>
>>
>> chances are you are going to want
>> > to do a lot more with your vectors than just sum them. You'd probably
>> want
>> > an entire library dedicated to dealing with them.
>>
>> Indeed. Anyone can create such a library if they wish, using their
>> preferred design. But how and where will it integrate with the
>> standard library? The touchpoints may likely include sum and product,
>> and it makes sense for the standard lib to require the minimal
>> required interface from the provider of Numeric-like operations.
>>
>> > Moreover, matrices and vectors have the problem that their dimension is
>> an
>> > integral part of what operations are defined. So even defining something
>> as
>> > simple as Vector addition requires runtime checks with a Numeric-like
>> Monoid
>> > trait. Since scala's Numeric instances seem to be wholly against runtime
>> > exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,
>> > rather than an exception), I'm not sure if Vectors would mix well.
>>
>> A counter example, from Stanford PPL's Delite project, which
>> currently has several EPFL Scala team members working on/around it. It
>> would seem that they see value in numeric operations over Vectors &
>> Matrices:
>>
>>
>> https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/dsl/optiml/capabilities/Arith.scala#L94
>>
>>
> I didn't mean to imply that you shouldn't able to do arithmetic over vectors
> or matrices (it obviously makes sense), but more that I wasn't entirely sure
> if there was a reason why Numeric seems to eschew runtime exceptions.
>
>
>> -Ben
>>
>> PS Delite's Arith numeric typeclass also demonstrates the diversity
>> around how to handle the division operator, having chosen a different
>> approach to the standard library.
>>
>
> Yep. I prefer Numeric's approach, but clearly several opinions in the
> conversation take "Arith"'s side.

Over the past 18 months I have done some analysis and prototyping
around handling the variable numerical precision of a Numeric
abstraction, that I hope to write up and add to the thread when time
permits (hopefully tonight). But first, I just want to get off my
chest why for me, Numeric & friends are really worth caring about and
getting right.

Good, usable abstraction over numbers is /rare/ in current
programming/software technology. The majority of present day languages
and frameworks couple against concrete numeric representations, for
example int, single/double floating point, or BigDecimal. I believe it
would be something of a landmark, a /substantial/ advance in software
practice, if Scala offered a numeric abstraction of sufficient quality
and practicality that it enjoyed widespread use. For me, that's a
potentially achievable goal worth working towards, with big ongoing
payoffs over many years to come.

We already have 3 JVM formats that approximate real numbers with
varying cost/accuracy tradeoffs: 32 bit float, 64 bit double, and
BigDecimal. Cameron Purdy's recent talk on future JVM evolution
anticipates several more, including 128bit floats and decimals
[http://i.cmpnet.com/ddj/images/mediacenter/jvmlanguagesummit/2011_Purdy_JVM_Language_Summit.pdf].
So even restricted to real numbers, of varying precision, there's no
shortage of formats to abstract over. We just need to get the
abstraction mechanism right.

As I see it, the stakes in this game are: get Numeric right, and Scala
will have achieved something rare, special and lasting (not to deny it
already has in many other ways). Get it wrong, and we're Yet Another
Language that didn't quite manage to the slay the numeric-abstraction
dragon, and we'll have to wait a decade for the next chance to come
along.

-Ben

On Fri, Sep 9, 2011 at 11:21 AM, Erik Osheim wrote:
> On Fri, Sep 09, 2011 at 11:09:03AM +1000, Ben Hutchison wrote:
>> * One is the non-separability of Sum and Product ops, as mentioned here.
>
> Agreed. To be clear, I don't mind creating new traits for those (and
> even implementing Numeric in terms of them) as long as Numeric can
> continue to perform well.
>
> In fact, given that complex numbers don't have a total ordering, the
> current Numeric design (which has Numeric[A] implementing Ordered[A])
> doesn't work so well for Complex numbers either. You can always fake
> it, but that isn't fantastic, nor are runtime exceptions (the approach
> that Python takes). So I think it does make sense to try to create type
> classes that express exactly what we want/need.
>
>> * The other is around stuff the present API doesn't include that I
>> find essential for doing alot of math: trig, exponential, random
>> numbers, indications of precision/error bounding. Theres a question
>> around how to make this available for those who need it, without
>> imposing on those who dont?
>
> I've thought about this also. It would be good to be able to support
> all useful math operations in the type class rather than requiring
> conversions to Double (which may produce bad results when dealing with
> very large and/or very precise types). I may try to do this soon, since
> it's relatively easy (as long as the underlying types have
> implementations).
>
> Questions around floating point errors, precision bounding, etc are a
> bit more thorny. I don't think it will be possible to solve those
> without (potentially) expensive run-time checks and conversions, which
> are a deal-breaker for me. I almost imagine using some kind of boxed
> data type to do this, which could wrap the operations and detect
> errors/precision changes.
>
> It's worth strategizing about, at any rate.
>

On Fri, Sep 9, 2011 at 11:21 AM, Erik Osheim wrote:
> Questions around floating point errors, precision bounding, etc are a
> bit more thorny.

Here's my thinking on how precision interacts with numeric-abstraction:

An implementation of Numeric, or likely some subtype like Fractional
or a hypothetical "Real" trait, knows about the accuracy of the
underlying numeric data it operates on. It needs to expose this
information to allow:

1. Estimating and bounding the error in a computation. While error
analysis is a complex area and is algorithm dependent, it clearly
depends significantly upon the amount of precision in the numeric data
used.

2. A reasonable implementation of equality (or perhaps more correctly
for real numbers, approximate equality). When testing numerical
computations, its important to be able to know if two real number
values are sufficiently close to be considered equal. True, exact
equality at bit level is rarely useful for floating point
computations. How close two values need be is a function of the
expected error in the computation.

An approach that I have had some success with in a prototype Real
numeric trait is to signal precision via a relative error threshold.
Values closer, in relative not absolute terms, than the threshold
should be considered equal; the imprecision of the number format means
that lesser differences might simply be errors. For Double, I use a
value of one millionth as my threshold.

trait Real[T] extends Fractional[T] {
...
/** Hint as to the accuracy of this numeric representation.
* This is the relative error threshold below which two Real values
should be considered (approximately) equal
* (ie approxEq is defined in terms of this).
*/
def RelativeError: T
}

-Ben

Hi,

In some cases you need not only multiplication but also division to have a reasonable fast algorithm.
In the particular case it is a difference between O(1) and a runtime of less than one ms or O(n) and completely useless runtimes of minutes for large collections for sum.

You're either running out of memory or the JVM is optimizing away your code entirely if you are going from ms to minutes.  If the JVM can turn your nominally O(n) operation into an O(1) one, so can you.  Otherwise it's not more than a factor of 100 or so in the very worst cases (double-boxed vs. primitive on every operation) unless you are really stressing the memory system.

Please have a look at the specific case I mentioned: https://github.com/scala/scala/pull/83

This is a real verified case. The VM doesn't optimize the code in any way.
For some collections where start/end/step is given (Range and friends) it is possible to compute the result of the sum method without traversing the whole collection.

I'm pretty sure that no VM on this planet can optimize "add every element of this collection together O(n)" to "invent a better algorithm to solve the problem in O(1)".

Thanks and bye

Hi Ben,

I am not an expert in numerical analysis, error propagation, etc. so
please take my response with the requisite dosage of salt.

On Fri, Sep 09, 2011 at 09:24:00PM +1000, Ben Hutchison wrote:
> An approach that I have had some success with in a prototype Real
> numeric trait is to signal precision via a relative error threshold.
> Values closer, in relative not absolute terms, than the threshold
> should be considered equal; the imprecision of the number format means
> that lesser differences might simply be errors. For Double, I use a
> value of one millionth as my threshold.
>
> trait Real[T] extends Fractional[T] {
> ...
> /** Hint as to the accuracy of this numeric representation.
> * This is the relative error threshold below which two Real values
> should be considered (approximately) equal
> * (ie approxEq is defined in terms of this).
> */
> def RelativeError: T
> }

So I guess you plan is to create an instance of Real[T] with the type
and error you care about?

implicit object RealDoubleWithMillionthThreshold extends Real[Double] {
def relativeError = 0.000001
}

I worry that this approach would either be cumbersome or cause
unforeseen problems when you need to deal with two (or more) different
epsilons in a single algorithm. It seems like it tries to hard the part
about numerical analysis that people often want to concentrate on.

I'm not sure that these are real concerns, but I'm not that they are
not either.

A different approach I can imagine would be something like this:

case class Epsilon[T:Fractional](error:T) {
def compareWithError(a:T, b:T) = {
val delta = a - b
if (delta.abs < error) 0 else delta.signum
}
}

class ApproximateReal[T:Fractional](val value:T, val epsilon:T) {
def +(rhs:ApproximateReal[T]) = {
val v = this.value + rhs.value
val e = max(this.epsilon, rhs.epsilon)
new ApproximateReal(v, e)
}
...
def cmp(rhs:ApproximateReal[T]) = {
val e = min(this.epsilon, rhs.epsilon)
e.compareWithError(this.value, rhs.value)
}
...
}

object ApproximateReal {
def apply[T:Fractional](v:T)(implicit e:Epsilon[T]) = new ApproximateReal(v, e)
def apply[T:Fractional](v:T, e:T) = new ApproximateReal(v, e)
...
}

This approach introduces boxing (which will certainly impact
performance) but makes it easy to manage many different epsilons, and
potentially recalculate them in useful ways.

Finally, I could imagine using your method but introducing some kind of
syntax-seeming construct to make it easier to provide the correct
implicit epsilon, e.g.:

val result = withError(0.000001) {
// do all the calculations in here
}

I am reluctant to try to demonstrate writing withError until I've
looked more closely at it though.

One final though: the problems of trying to compute and track errors
(round off and truncation) and precision extend just beyond the
problems of testing numeric equality with floating-point numbers. It is
worth considering other cases too, e.g. BigDecimal, rational numbers,
etc.

On Thu, Sep 8, 2011 at 6:16 PM, Erik Osheim <erik@plastic-idolatry.com> wrote:

But when trying to abstract an algorithm across Int/Double the lack of
any concept that something like division is defined on both is
crippling. This is *especially* true given that both Int and Double
define the / operator, so in practice your code for those cases will be
*identical*. I haven't met anyone who's tried to use Numeric for
anything serious and hasn't hit this problem.

For what its worth. A better improvement would be to remove /(x:Int):Int entirely. On the whole this "feature" has probably caused significantly more costs to the world than value.

I've never seen code using integer division where it didn't just seem like an interesting hack. Somewhat like n << 1 instead of n * 2. Sure it works, but in no way does it signal any useful intent.

The times I've seen it used accidentally is quite numerous though, round(sum(qty)/sum(samples)) for example. The worst thing with this kind of bug is that it isn't directly obvious in the output. More often than not (in my experience) this kind of bug is discovered by by coincidence during random code inspections rather than by the users relying on the wrong figures to base their decisions on.

Yeah sure TDD, discipline, education and all that will remove this problem too, but keep in mind that Scala is now starting to take steps into the wonderful world of ERP development. A world where most developers have no clue about floating points, number precisions or other "geeky"-details. It is no coincidence that Java tries very, very, hard not to be scary. (Which it fails miserably at by the way, COBOL is a much better language in key aspects such as IO and database-integartion)

While on the topic one might also consider removing float and double in their base-2 version from the Prelude and instead expose base-10 versions[1] by default. If you care enough about fp-performance to need base-2 floats you also know enough to able to use a specialised library for it. I don't know how to do this and still interoperate with Java though...

[1] http://en.wikipedia.org/wiki/Decimal_floating_point

BR,
John

On Fri, Sep 09, 2011 at 10:22:23PM +0200, John Nilsson wrote:
> The times I've seen it used accidentally is quite numerous though,
> round(sum(qty)/sum(samples)) for example. The worst thing with this kind of
> bug is that it isn't directly obvious in the output. More often than not (in
> my experience) this kind of bug is discovered by by coincidence during
> random code inspections rather than by the users relying on the wrong
> figures to base their decisions on.

If this is a big concern of yours then you'd probably want to go the
way Python has and have two division operators: floor division and true
division. Then you can define things so that / uses true division (even
with integral types) and always yields a fractional result. Then people
will also be able to use floor division (mapped to some other operator)
to recover the whole quotient (the way division on integers currently
works).

This type of feature would probably require support for a better
numeric tower in the compiler, and would make the current type class
strategy harder (since Integral[A] would need to define which
Fractional[B] you end up with after doing true division). But I would
be excited to work on something like this.

I don't consider removing integer division to be a useful way to
resolve this issue.

> While on the topic one might also consider removing float and double in
> their base-2 version from the Prelude and instead expose base-10 versions[1]
> by default. If you care enough about fp-performance to need base-2 floats
> you also know enough to able to use a specialised library for it. I don't
> know how to do this and still interoperate with Java though...

This isn't realistic. While it would be nice to have base-10 floating
point types available, it shouldn't force the removal of the base-2
versions. Changing the definition of Float and Double would break
backward compatibility, force a large change to the language spec, and
complicate/destroy Java interop on primitive types.

It seems like you are saying that we need to cripple integral types and
slow down the fractional types in order to satisfy "enterprise
programmers," even though these same souls are already working with
Java and C#, both of which have these exact same issues. Am I
misunderstanding?

On Fri, Sep 9, 2011 at 11:07 PM, Erik Osheim <erik@plastic-idolatry.com> wrote:

If this is a big concern of yours then you'd probably want to go the
way Python has and have two division operators: floor division and true
division.

Or possible just return a reminder with the floor.

I don't consider removing integer division to be a useful way to
resolve this issue.

Remove/rename I'm not suggesting making the operation unavailable, just to make it harder to accidentally use it.

It seems like you are saying that we need to cripple integral types and
slow down the fractional types in order to satisfy "enterprise
programmers," even though these same souls are already working with
Java and C#, both of which have these exact same issues. Am I
misunderstanding?

No you understand me correct. Yes they are struggling with these issues in Java and C#, and Scala are in many way positioning it self as an improvement over the current mainstream languages. I'm just proposing that it could be even more of an improvement.

Compare it to null vs Option[T], yes you are constructing and boxing your values which have a performance impact. But in the end the common case is "fast enough" to warrant its use.

I'm not convinced that you have to "cripple" anything or make scientific computing impossible to achieve this though. Btw. there are chips out there that have hardware implementation of the decimal floats, would the feature be readily available in mainstream languages I'm sure Intel and AMD would include it it into their chips.

BR,
John

Erik,

After examining your code sketches, Im fairly sure there's been a
miscommunication of my numerical precision proposal, such that our
thinking may be solving different problems.

Let's start at the beginning: why do we abstract over numbers? We want
to write code that does maths, and be able to vary the type of numbers
we use, from one application to the next, or from one run to the next.
For example, we might have a rendering library, that can run in 32 bit
applications on mobile devices, but 64 bits in a server-deployed app.
Or, a differential equation solver that we can run at 32bit in
prototyping mode, but switch to 256 bits when we need ultra-accuracy,
eg planning a spacecraft trajectory.

The point is, in any given app or context, there is typically only one
Numeric instance present. We choose our number format and stick with
it. The application designer (ie consumer of Numeric) has some
"accuracy/error management strategy" (which will often be to do
nothing, but might be some error measure or interval) but for that
strategy to be credible, they need one crucial piece of information
from the provider of the Numeric instance in use: "how accurate is the
underlying Numeric representation?"

That is the piece of information I was trying to expose (indirectly)
via the RelativeError member of the Numeric instance. But in further
consideration, it seems better to model the parameters of the
representation as literally as possible.

Most non-integer numbers in use to day are floating point. What we
call "floating point" use a base2 digits, while what are called
"decimal numbers" use base 10 digits, but in both cases the points
"float". Ive called the proposed trait below Real, but Im not 100%
comfortable with that name. Maybe FloatingPoint[T] is actually
better..

//Proposal Version 2
trait Real[T] extends Fractional[T] {

//the number base used _internally_ by the representation
def Base //ie an enum: Base2 || Base10

//the number of significant digits in the internal base. Ie binary
digits for base 2.
def SignificantDigits: Int

//enum of rounding mode strategies, similar to BigDecimal's
def RoundingMode
}

For example:
- Scala type Double has 53 significant binary digits, is Base2, and
uses Round Half to Even Rounding Mode.
- C# decimal has 28 significant decimal digits, is Base 10, and uses
Round Half to Even Rounding Mode
- java.util.BigDecimal same as C# decimal, but with possibly unlimited
significant digits. (how best to represent "unlimited' in an API?
Option[Int]?)

From these "building blocks" we can derive many useful attributes:
- Exactness: can the number format represent decimal numbers exactly?
Yes, if base10, no otherwise.
- How many significant decimal digits are there? (ie 15-16 for Double,
being log2(53))
- A RelativeError value can be derived from the SignificantDigits &
Exactness along with knowledge of our application's computational
behaviour & demands.

-Ben

PS In thinking about numeric abstraction design, I'll observe that
java.util.BigDecimal makes for an excellent case study: Because it
represents floating point decimals of variable precision, it has had
to contend with many of the relevant issues.

On Sat, Sep 10, 2011 at 1:31 AM, Erik Osheim wrote:
> On Fri, Sep 09, 2011 at 09:24:00PM +1000, Ben Hutchison wrote:
>> An approach that I have had some success with in a prototype Real
>> numeric trait is to signal precision via a relative error threshold.
>> Values closer, in relative not absolute terms, than the threshold
>> should be considered equal; the imprecision of the number format means
>> that lesser differences might simply be errors. For Double, I use a
>> value of one millionth as my threshold.
>>
>> trait Real[T] extends Fractional[T] {
>> ...
>>   /** Hint as to the accuracy of this numeric representation.
>>    * This is the relative error threshold below which two Real values
>> should be considered (approximately) equal
>>    * (ie approxEq is defined in terms of this).
>>    */
>>   def RelativeError: T
>> }
>
> So I guess you plan is to create an instance of Real[T] with the type
> and error you care about?
>
> implicit object RealDoubleWithMillionthThreshold extends Real[Double] {
>    def relativeError = 0.000001
> }
>
> I worry that this approach would either be cumbersome or cause
> unforeseen problems when you need to deal with two (or more) different
> epsilons in a single algorithm. It seems like it tries to hard the part
> about numerical analysis that people often want to concentrate on.
>
> I'm not sure that these are real concerns, but I'm not that they are
> not either.
>
> A different approach I can imagine would be something like this:
>
> case class Epsilon[T:Fractional](error:T) {
>    def compareWithError(a:T, b:T) = {
>        val delta = a - b
>        if (delta.abs < error) 0 else delta.signum
>    }
> }
>
> class ApproximateReal[T:Fractional](val value:T, val epsilon:T) {
>    def +(rhs:ApproximateReal[T]) = {
>        val v = this.value + rhs.value
>        val e = max(this.epsilon, rhs.epsilon)
>        new ApproximateReal(v, e)
>    }
>    ...
>    def cmp(rhs:ApproximateReal[T]) = {
>        val e = min(this.epsilon, rhs.epsilon)
>        e.compareWithError(this.value, rhs.value)
>    }
>    ...
> }
>
> object ApproximateReal {
>    def apply[T:Fractional](v:T)(implicit e:Epsilon[T]) = new ApproximateReal(v, e)
>    def apply[T:Fractional](v:T, e:T) = new ApproximateReal(v, e)
>    ...
> }
>
> This approach introduces boxing (which will certainly impact
> performance) but makes it easy to manage many different epsilons, and
> potentially recalculate them in useful ways.
>
> Finally, I could imagine using your method but introducing some kind of
> syntax-seeming construct to make it easier to provide the correct
> implicit epsilon, e.g.:
>
> val result = withError(0.000001) {
>    // do all the calculations in here
> }
>
> I am reluctant to try to demonstrate writing withError until I've
> looked more closely at it though.
>
> One final though: the problems of trying to compute and track errors
> (round off and truncation) and precision extend just beyond the
> problems of testing numeric equality with floating-point numbers. It is
> worth considering other cases too, e.g. BigDecimal, rational numbers,
> etc.
>

On Sep 11, 2011, at 08:44 , Ben Hutchison wrote:

> [snip]

> - java.util.BigDecimal same as C# decimal, but with possibly unlimited
> significant digits. (how best to represent "unlimited' in an API?
> Option[Int]?)
>
Considering that the underlying BigInteger will start failing at 2^31 bits, I’d say “unlimited” is quite easily expressible in this case ;-) The general point being that unlimited numeric precision cannot be available on a finite computer.

Regards,

Roland Kuhn
Typesafe – Enterprise-Grade Scala from the Experts
twitter: @rolandkuhn

On 09/11/2011 02:44 AM, Ben Hutchison wrote:
> ... but switch to 256 bits when we need ultra-accuracy,
> eg planning a spacecraft trajectory.

I wasn't planning on adding anything to this thread, but I have worked
on systems that created plans for satellites, and we used plain old
doubles -- in .NET no less. To be honest we wouldn't have wanted an
ultra-precise numeric library. The reality that your model will never be
perfectly accurate, so you build buffers around your limits so you don't
need to worry about such imprecisions.

But one thing that would be really useful in a numeric library is an
easy (e.g. hard to ignore) way to incorporate tolerances in comparisons.
We didn't care so much about the precision of our answers so much that
our calculations did not exceed limits, and we always compared our
answers against the limits using tolerances. Or at least we should have,
and not checking against a tolerance (because it was easy to ignore) was
a large source of hard-to-find and harder-to-replicate bugs.

ARKBAN

P.S.: I am now fortunate to be using Scala professionally instead of .NET.

On Mon, Sep 12, 2011 at 12:01 PM, ARKBAN wrote:
>
> On 09/11/2011 02:44 AM, Ben Hutchison wrote:
>>
>> ... but switch to 256 bits when we need ultra-accuracy,
>> eg planning a spacecraft trajectory.
>
> I wasn't planning on adding anything to this thread, but I have worked on
> systems that created plans for satellites, and we used plain old doubles --
> in .NET no less. To be honest we wouldn't have wanted an ultra-precise
> numeric library.

OK, its a data point. But we cannot conclude that because you didn't
use them in your project, precision above 64 bits is not needed. 128
bit floats are listed in the JVM's future wish list I linked to
earlier, which I'd claim indicates more than one party has been
wanting them.

Regardless of the case, or lack of, for 128+ bit floats, numeric
abstraction is useful for abstracting across the 32/64 bit divide.

> But one thing that would be really useful in a numeric library is an easy
> (e.g. hard to ignore) way to incorporate tolerances in comparisons.

I fully agree tolerances are important and use them myself. However,
its important to distinguish attributes that properly belong /on/ the
numeric abstraction from those that can be built /on top of/ the
abstraction.

I suspect error tracking (eg a +- error value, interval arithmetic)
techniques can be constructed on top of a numeric abstraction; you may
or may not take the numeric precision into account in that layer.

-Ben

We
> didn't care so much about the precision of our answers so much that our
> calculations did not exceed limits, and we always compared our answers
> against the limits using tolerances. Or at least we should have, and not
> checking against a tolerance (because it was easy to ignore) was a large
> source of hard-to-find and harder-to-replicate bugs.
>
> ARKBAN
>
> P.S.: I am now fortunate to be using Scala professionally instead of .NET.
>

On Sun, Sep 11, 2011 at 7:01 PM, ARKBAN wrote:
> But one thing that would be really useful in a numeric library is an easy
> (e.g. hard to ignore) way to incorporate tolerances in comparisons. We
> didn't care so much about the precision of our answers so much that our
> calculations did not exceed limits, and we always compared our answers
> against the limits using tolerances. Or at least we should have, and not
> checking against a tolerance (because it was easy to ignore) was a large
> source of hard-to-find and harder-to-replicate bugs.

Sort of a tangent, but it's underappreciated and you can embed it:

http://futureboy.us/frinkdocs/#IntervalArithmetic

In the below, PLT is "possibly less than" and CLT "certainly less than".

velocity = new interval[50, 55] mph
[2794/125 (exactly 22.352), 15367/625 (exactly 24.5872)] m s^-1 (velocity)
time = new interval[4.0, 4.4] seconds
[4.0, 4.4] s (time)
velocity / time
[5.0799999999999999998, 6.1468] m s^-2 (acceleration)
(velocity / time) PLT 5.08 m/s^2
true
(velocity / time) CLT 5.08 m/s^2
false
(velocity / time) PLT 5.07 m/s^2
false

On Mon, Sep 12, 2011 at 1:47 PM, Paul Phillips wrote:
> Sort of a tangent, but it's underappreciated and you can embed it:
>
> http://futureboy.us/frinkdocs/#IntervalArithmetic
>

From a quick review of interval operators
[http://en.wikipedia.org/wiki/Interval_arithmetic], it seems that a
sensible Numeric typeclass could be defined for intervals, built atop
any Numeric definition for the interval endpoints. That looks like the
"easy" way to include error bounds into computations that Arkan
wanted, without having to touch the computational code itself.

-Ben

> In the below, PLT is "possibly less than" and CLT "certainly less than".
>
> velocity = new interval[50, 55] mph
> [2794/125 (exactly 22.352), 15367/625 (exactly 24.5872)] m s^-1 (velocity)
> time = new interval[4.0, 4.4] seconds
> [4.0, 4.4] s (time)
> velocity / time
> [5.0799999999999999998, 6.1468] m s^-2 (acceleration)
> (velocity / time) PLT 5.08 m/s^2
> true
> (velocity / time) CLT 5.08 m/s^2
> false
> (velocity / time) PLT 5.07 m/s^2
> false
>

On Fri, Sep 9, 2011 at 11:53 AM, Tom Switzer wrote:
> Perhaps a trade-off could be to create a few new traits. Something more
> like,
> trait Monoid[A] {
>   def zero: A
>   def add(x: A, y: A): A
> }
>
> trait Ring[A] extends Monoid[A] {
>   def one: A
>   def sub(x: A, y: A): A
>   def mul(x: A, y: A): A
> }
> trait Numeric[A] extends Ring[A] {
>   def div(x: A, y: A): A
> }

A beautiful and liberating aspect of switching from an OO- centric to
a Typeclass- centric "default worldview" is that you no longer need to
inherit from something to be that something. You don't need to inherit
from Number to be a number, and you dont need to inherit from Monoid
to be a monoid. Sum and Product are monoids, and they don't need the
consent of the core library:

implicit def sum2Monoid[A](sum: Sum[A]) = new Monoid[A] {
def zero = sum.zero
def add(x: A, y: A) = sum.add(x, y)
}

Another limitation of inheritance is that it's essentially a global
declaration. The trait hierarchy sketched above states that Numeric is
always interpreted as a Monoid via addition/zero. But
multiplication/one is an equally valid way to interpret Numeric as a
Monoid. And to represent that via inheritance requires that Numeric
inherits from Monoid twice simultaneously with differing
implementations: a contortion not even Scala will allow!

-Ben

>
> On Thu, Sep 8, 2011 at 8:30 PM, Ben Hutchison wrote:
>>
>> On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer
>> wrote:
>> > Numeric (and Fractional and Integral) is simple enough
>> > to be understandable by most people (vs. monoids, rings, fields, etc),
>> > while
>> > still providing a good amount of flexibility.
>>
>> Actually, the problem is precisely that Numeric is not simple enough.
>> I don't think its about adding "algebraic structure" or "monoids" into
>> the library. Rather, simply splitting the methods already there into
>> smaller, more focused units. I suspect that it can be done while
>> maintaining backwards compatibility.
>>
>> Numeric defines Addition and Multiplication in one interface. Thats
>> unnecessary coupling: considering TraversableOnce.{sum, product}
>> (presently the main application/motivation of Numeric in the library),
>> sum requires you to pass a definition of multiplication, even though
>> it never uses it. Similarly, product requires Addition even though
>> it's never used.
>>
>>
>>  chances are you are going to want
>> > to do a lot more with your vectors than just sum them. You'd probably
>> > want
>> > an entire library dedicated to dealing with them.
>>
>> Indeed. Anyone can create such a library if they wish, using their
>> preferred design. But how and where will it integrate with the
>> standard library? The touchpoints may likely include sum and product,
>> and it makes sense for the standard lib to require the minimal
>> required interface from the provider of Numeric-like operations.
>>
>> > Moreover, matrices and vectors have the problem that their dimension is
>> > an
>> > integral part of what operations are defined. So even defining something
>> > as
>> > simple as Vector addition requires runtime checks with a Numeric-like
>> > Monoid
>> > trait. Since scala's Numeric instances seem to be wholly against runtime
>> > exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,
>> > rather than an exception), I'm not sure if Vectors would mix well.
>>
>> A counter example, from Stanford PPL's  Delite project, which
>> currently has several EPFL Scala team members working on/around it. It
>> would seem that they see value in numeric operations over Vectors &
>> Matrices:
>>
>>
>> https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/...
>>
>
> I didn't mean to imply that you shouldn't able to do arithmetic over vectors
> or matrices (it obviously makes sense), but more that I wasn't entirely sure
> if there was a reason why Numeric seems to eschew runtime exceptions.
>
>>
>> -Ben
>>
>> PS Delite's Arith numeric typeclass also demonstrates the diversity
>> around how to handle the division operator, having chosen a different
>> approach to the standard library.
>
> Yep. I prefer Numeric's approach, but clearly several opinions in the
> conversation take "Arith"'s side.

I completely agree its a single data point, I never meant to imply
otherwise. I know for fact that there are other spacecraft systems where
higher precision is needed.

ARKBAN

On 9/11/11 10:42 PM, Ben Hutchison wrote:
> On Mon, Sep 12, 2011 at 12:01 PM, ARKBAN wrote:
>> On 09/11/2011 02:44 AM, Ben Hutchison wrote:
>>> ... but switch to 256 bits when we need ultra-accuracy,
>>> eg planning a spacecraft trajectory.
>> I wasn't planning on adding anything to this thread, but I have worked on
>> systems that created plans for satellites, and we used plain old doubles --
>> in .NET no less. To be honest we wouldn't have wanted an ultra-precise
>> numeric library.
> OK, its a data point. But we cannot conclude that because you didn't
> use them in your project, precision above 64 bits is not needed. 128
> bit floats are listed in the JVM's future wish list I linked to
> earlier, which I'd claim indicates more than one party has been
> wanting them.
>
> Regardless of the case, or lack of, for 128+ bit floats, numeric
> abstraction is useful for abstracting across the 32/64 bit divide.
>
>> But one thing that would be really useful in a numeric library is an easy
>> (e.g. hard to ignore) way to incorporate tolerances in comparisons.
> I fully agree tolerances are important and use them myself. However,
> its important to distinguish attributes that properly belong /on/ the
> numeric abstraction from those that can be built /on top of/ the
> abstraction.
>
> I suspect error tracking (eg a +- error value, interval arithmetic)
> techniques can be constructed on top of a numeric abstraction; you may
> or may not take the numeric precision into account in that layer.
>
> -Ben
>
> We
>> didn't care so much about the precision of our answers so much that our
>> calculations did not exceed limits, and we always compared our answers
>> against the limits using tolerances. Or at least we should have, and not
>> checking against a tolerance (because it was easy to ignore) was a large
>> source of hard-to-find and harder-to-replicate bugs.
>>
>> ARKBAN
>>
>> P.S.: I am now fortunate to be using Scala professionally instead of .NET.
>>

On Fri, Sep 9, 2011 at 17:22, John Nilsson wrote:
>
> I've never seen code using integer division where it didn't just seem like
> an interesting hack. Somewhat like n << 1 instead of n * 2. Sure it works,
> but in no way does it signal any useful intent.

It depends on what you do. I've never written code using any kind of
floating point, except to produce statistics (and, these, mostly
benchmarks -- ie, not production code). Well, maybe "never" is going
too far, but I honestly can't recall any such instance.

Integer division? It is everywhere. How many full pages are needed to
display n items, m items per page? n / m. Total number of pages is (n
+ m - 1) / m.

The same problem under different disguises appear over and over:
memory allocation, scheduling, compression, etc.

Sure, scientific computing of all sorts use floating point.

> While on the topic one might also consider removing float and double in
> their base-2 version from the Prelude and instead expose base-10 versions[1]
> by default. If you care enough about fp-performance to need base-2 floats
> you also know enough to able to use a specialised library for it. I don't
> know how to do this and still interoperate with Java though...

What? I can't think of a single use for base-10 floating point
*except* to represent money. That would be like BCD all over again --
which was hardware supported, and then discarded because of its
uselessness.

If you want to represent money, there's a type for you: BigDecimal.
Accurate decimal fractions, no overflows, no underflows.

On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral <dcsobral@gmail.com> wrote:

Integer division? It is everywhere. How many full pages are needed to
display n items, m items per page? n / m. Total number of pages is (n
+ m - 1) / m.

Why not just floor(n/m)  ? or val (times, rest) = n / m, basically any way of expressing the intent that cant be mistaken for a bug.
 

What? I can't think of a single use for base-10 floating point
*except* to represent money. That would be like BCD all over again --
which was hardware supported, and then discarded because of its
uselessness.

Any use case where you expect a clueless business user to enter a fraction you'd want a representation with the same rounding errors as they are used to.

Money is one use case yes, but there are other. It's just my experience that it's the most common use case, I have no clue what the actual statistics are though.

If you want to represent money, there's a type for you: BigDecimal.
Accurate decimal fractions, no overflows, no underflows.

I think BigDecimal is perfect for the task. But I can see how some people might think it could be a performance problem.
So for the sake of arguments I'm suggesting that  val a = 4.2 would be interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)

BR,
John

On Tue, Sep 13, 2011 at 7:19 AM, John Nilsson wrote:
> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral wrote:
>> What? I can't think of a single use for base-10 floating point
>> *except* to represent money. That would be like BCD all over again --
>> which was hardware supported, and then discarded because of its
>> uselessness.
>
> Any use case where you expect a clueless business user to enter a fraction
> you'd want a representation with the same rounding errors as they are used
> to.
>
> Money is one use case yes, but there are other. It's just my experience that
> it's the most common use case, I have no clue what the actual statistics are
> though.

Im favoring John's argument here. Base 2 floats are a legacy of the
need to do math the most efficient way possible. They put the
computers convenience ahead of the humans. But many users do not see
10-100x performance difference as an issue: the recent tendency to
treating Java and Ruby as interchangeable tech options is an example
of this.

Other than money itself, a common decimal use case is fractional
"factors" and "thresholds" used in business rules, eg:
- The proportional amount a price is discounted in a sale
- The number of loyalty points accrued per month in a scheme
- The maximum distance a customer can live from a store to receive free delivery

Money related, yes, because business is about money, but not just money itself.

Lets turn it around: how is representing our base 10 number system in
base 2 a "sensible default"?

The most likely way this could make it into Scala, IMO, is for the
future JVM to add an intrinsic decimal type, and then Java/Scala etc
add a decimal literal syntax.

-Ben

On Mon, Sep 12, 2011 at 18:19, John Nilsson wrote:
> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral wrote:
>>
>> Integer division? It is everywhere. How many full pages are needed to
>> display n items, m items per page? n / m. Total number of pages is (n
>> + m - 1) / m.
>
> Why not just floor(n/m)  ? or val (times, rest) = n / m, basically any way
> of expressing the intent that cant be mistaken for a bug.

Look, you have an outlook. To you, division means fractions, and
that's that. To people like me, division is integer division. There's
no bug or mistaken intent, because there's nothing using floating
points at all. To *use* floating points, on the other hand, now *that*
may cause bugs! Floating points have no place in a discrete world,
arrays don't have an index 4.2. To introduce floating points there at
all means having to constantly guard against fraction. Miss a floor
here, and add two numbers, and you might end up with the wrong result.

Personally, I think type widening is a mistake. Get rid of it, and
you'll *never* have the problems you mention, because the instant you
try to feed that number to something expecting a double (or BigInt),
it will blow.

>> What? I can't think of a single use for base-10 floating point
>> *except* to represent money. That would be like BCD all over again --
>> which was hardware supported, and then discarded because of its
>> uselessness.
>
> Any use case where you expect a clueless business user to enter a fraction
> you'd want a representation with the same rounding errors as they are used
> to.
>
> Money is one use case yes, but there are other. It's just my experience that
> it's the most common use case, I have no clue what the actual statistics are
> though.

And how many applications do you think handle money? The compiler sure
doesn't, nor does the kernel. I've worked telecom for ten years, and
while there certainly were applications handling money there, none of
mine did. They all dealt in nice integers -- the only time a
non-integer was passed to it, it was handled simply as a string to be
fed to the output.

There's a huge world of integer-using applications. It might not be
_your_ world, but it is there.

> I think BigDecimal is perfect for the task. But I can see how some people
> might think it could be a performance problem.
> So for the sake of arguments I'm suggesting that  val a = 4.2 would be
> interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)

Personally, it's almost what I'd prefer. I think the ideal would be
BigInt, properly optimized to work as a Double as long as it doesn't
overflow/underflow. If hardware supported decimal point, then I'd go
with BigDecimal, but I'd never forge ahead in the hopes that hardware
will catch up. Not unless I'm Microsoft or Oracle, at least.

Just as an example, grepping for Double on the compiler yield 55
instances. All of them seem related to compiling doubles, too. Float
and Short have 41 instances, which I assume are _all_ related to
compiling them. In contrast, Byte, of all things, have 124 instances,
and Int has 1216. In the library, which has to provide floating point
support, these numbers are 360, 298, 229 and 2340.

On Mon, Sep 12, 2011 at 20:40, Daniel Sobral wrote:
> On Mon, Sep 12, 2011 at 18:19, John Nilsson wrote:
>> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral wrote:
>>>
>>> Integer division? It is everywhere. How many full pages are needed to
>>> display n items, m items per page? n / m. Total number of pages is (n
>>> + m - 1) / m.
>>
>> Why not just floor(n/m)  ? or val (times, rest) = n / m, basically any way
>> of expressing the intent that cant be mistaken for a bug.
>
> Look, you have an outlook. To you, division means fractions, and
> that's that. To people like me, division is integer division. There's
> no bug or mistaken intent, because there's nothing using floating
> points at all. To *use* floating points, on the other hand, now *that*
> may cause bugs! Floating points have no place in a discrete world,
> arrays don't have an index 4.2. To introduce floating points there at
> all means having to constantly guard against fraction. Miss a floor
> here, and add two numbers, and you might end up with the wrong result.
>
> Personally, I think type widening is a mistake. Get rid of it, and
> you'll *never* have the problems you mention, because the instant you
> try to feed that number to something expecting a double (or BigInt),
> it will blow.
>
>>> What? I can't think of a single use for base-10 floating point
>>> *except* to represent money. That would be like BCD all over again --
>>> which was hardware supported, and then discarded because of its
>>> uselessness.
>>
>> Any use case where you expect a clueless business user to enter a fraction
>> you'd want a representation with the same rounding errors as they are used
>> to.
>>
>> Money is one use case yes, but there are other. It's just my experience that
>> it's the most common use case, I have no clue what the actual statistics are
>> though.
>
> And how many applications do you think handle money? The compiler sure
> doesn't, nor does the kernel. I've worked telecom for ten years, and
> while there certainly were applications handling money there, none of
> mine did. They all dealt in nice integers -- the only time a
> non-integer was passed to it, it was handled simply as a string to be
> fed to the output.
>
> There's a huge world of integer-using applications. It might not be
> _your_ world, but it is there.
>
>> I think BigDecimal is perfect for the task. But I can see how some people
>> might think it could be a performance problem.
>> So for the sake of arguments I'm suggesting that  val a = 4.2 would be
>> interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)
>
> Personally, it's almost what I'd prefer. I think the ideal would be
> BigInt, properly optimized to work as a Double as long as it doesn't
> overflow/underflow. If hardware supported decimal point, then I'd go
> with BigDecimal, but I'd never forge ahead in the hopes that hardware
> will catch up. Not unless I'm Microsoft or Oracle, at least.
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
>

My outlook isnt based on what I think. Its based on what I think the person who wrote the code thought. Lile I said I see this little gem from time to time: Math.round(int1/int2) ...

In my second example I didn't mean to imply converting things to a float btw.

val (times, re) = i1/i2
or another symbol like
val times = i1/!i2
still integer division.

BR
John

Sent from my phone

Den 13 sep 2011 01:40 skrev "Daniel Sobral" <dcsobral@gmail.com>:
> On Mon, Sep 12, 2011 at 18:19, John Nilsson <john@milsson.nu> wrote:
>> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral <dcsobral@gmail.com> wrote:
>>>
>>> Integer division? It is everywhere. How many full pages are needed to
>>> display n items, m items per page? n / m. Total number of pages is (n
>>> + m - 1) / m.
>>
>> Why not just floor(n/m)  ? or val (times, rest) = n / m, basically any way
>> of expressing the intent that cant be mistaken for a bug.
>
> Look, you have an outlook. To you, division means fractions, and
> that's that. To people like me, division is integer division. There's
> no bug or mistaken intent, because there's nothing using floating
> points at all. To *use* floating points, on the other hand, now *that*
> may cause bugs! Floating points have no place in a discrete world,
> arrays don't have an index 4.2. To introduce floating points there at
> all means having to constantly guard against fraction. Miss a floor
> here, and add two numbers, and you might end up with the wrong result.
>
> Personally, I think type widening is a mistake. Get rid of it, and
> you'll *never* have the problems you mention, because the instant you
> try to feed that number to something expecting a double (or BigInt),
> it will blow.
>
>>> What? I can't think of a single use for base-10 floating point
>>> *except* to represent money. That would be like BCD all over again --
>>> which was hardware supported, and then discarded because of its
>>> uselessness.
>>
>> Any use case where you expect a clueless business user to enter a fraction
>> you'd want a representation with the same rounding errors as they are used
>> to.
>>
>> Money is one use case yes, but there are other. It's just my experience that
>> it's the most common use case, I have no clue what the actual statistics are
>> though.
>
> And how many applications do you think handle money? The compiler sure
> doesn't, nor does the kernel. I've worked telecom for ten years, and
> while there certainly were applications handling money there, none of
> mine did. They all dealt in nice integers -- the only time a
> non-integer was passed to it, it was handled simply as a string to be
> fed to the output.
>
> There's a huge world of integer-using applications. It might not be
> _your_ world, but it is there.
>
>> I think BigDecimal is perfect for the task. But I can see how some people
>> might think it could be a performance problem.
>> So for the sake of arguments I'm suggesting that  val a = 4.2 would be
>> interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)
>
> Personally, it's almost what I'd prefer. I think the ideal would be
> BigInt, properly optimized to work as a Double as long as it doesn't
> overflow/underflow. If hardware supported decimal point, then I'd go
> with BigDecimal, but I'd never forge ahead in the hopes that hardware
> will catch up. Not unless I'm Microsoft or Oracle, at least.
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.

On Thu, Sep 8, 2011 at 23:12, Tom Switzer wrote:
> I cannot see how whether an addition goes through Numeric or not can change
> the complexity from O(1) to O(n). Certainly wrapping an object for each
> addition/multiplication has performance penalties, but this would only
> change the constant factor. I have seen some people here looking for nice
> ways to get around Scala type classes' need to wrap an object for each call
> for a while. I'm not sure if anything has come of this though.
> It would be nice if we could somehow get the compiler to go from
> "num.mkNumericOps(a).+(b)" to "num.plus(a, b)".

You mean like this?

scala> import scala.math.Numeric.Implicits._
import scala.math.Numeric.Implicits._

scala> def f[T: Numeric](a: T, b: T) = a + b
f: [T](a: T, b: T)(implicit evidence$1: Numeric[T])T

On Mon, Sep 12, 2011 at 3:19 PM, John Nilsson <john@milsson.nu> wrote:

On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral <dcsobral@gmail.com> wrote:

Integer division? It is everywhere. How many full pages are needed to
display n items, m items per page? n / m. Total number of pages is (n
+ m - 1) / m.

Why not just floor(n/m)  ? or val (times, rest) = n / m, basically any way of expressing the intent that cant be mistaken for a bug.

I'd prefer if integer division returned a Rational, which would give a type safe and accurate way of handling the result. From there it can be either converted back to an integer or to a double depending on your requirements. It would also make '5 / 2 * 2' equivalent to '5 * 2 / 2'  --
Derek Williams

On Tue, Sep 13, 2011 at 01:08:58PM -0300, Daniel Sobral wrote:
> You mean like this?
>
> scala> import scala.math.Numeric.Implicits._
> import scala.math.Numeric.Implicits._
>
> scala> def f[T: Numeric](a: T, b: T) = a + b
> f: [T](a: T, b: T)(implicit evidence$1: Numeric[T])T

If you examine the parse tree of this you'll see that this is actually:

def f[T](a:T, b:T)(implicit ev:Numeric[T]):T = new ev.Ops(a).+(b)

What Tom was talking about was removing the object construction that
the new nv.Ops(a) does to get directly to the underlying Numeric.plus:

def f[T](a:T, b:T)(implicit ev:Numeric[T]):T = num.add(a, b)

This transformation isn't safe to do in general, because Ops'
constructor might do something important. In this case though it is a
perfectly safe optimization (as it is for most type classes).

This is one of the root motivations of Josh Suereth's proposals related
to optimizing abstract decorators and type classes, AFAIK.

On Tue, Sep 13, 2011 at 03:40, John Nilsson wrote:
> My outlook isnt based on what I think. Its based on what I think the person
> who wrote the code thought. Lile I said I see this little gem from time to
> time: Math.round(int1/int2) ...
>
> In my second example I didn't mean to imply converting things to a float
> btw.
>
> val (times, re) = i1/i2
> or another symbol like
> val times = i1/!i2
> still integer division.

IIRC, integer division in Pascal was "div". I have no problems with that.

>
> BR
> John
>
> Sent from my phone
>
> Den 13 sep 2011 01:40 skrev "Daniel Sobral" :
>> On Mon, Sep 12, 2011 at 18:19, John Nilsson wrote:
>>> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral
>>> wrote:
>>>>
>>>> Integer division? It is everywhere. How many full pages are needed to
>>>> display n items, m items per page? n / m. Total number of pages is (n
>>>> + m - 1) / m.
>>>
>>> Why not just floor(n/m)  ? or val (times, rest) = n / m, basically any
>>> way
>>> of expressing the intent that cant be mistaken for a bug.
>>
>> Look, you have an outlook. To you, division means fractions, and
>> that's that. To people like me, division is integer division. There's
>> no bug or mistaken intent, because there's nothing using floating
>> points at all. To *use* floating points, on the other hand, now *that*
>> may cause bugs! Floating points have no place in a discrete world,
>> arrays don't have an index 4.2. To introduce floating points there at
>> all means having to constantly guard against fraction. Miss a floor
>> here, and add two numbers, and you might end up with the wrong result.
>>
>> Personally, I think type widening is a mistake. Get rid of it, and
>> you'll *never* have the problems you mention, because the instant you
>> try to feed that number to something expecting a double (or BigInt),
>> it will blow.
>>
>>>> What? I can't think of a single use for base-10 floating point
>>>> *except* to represent money. That would be like BCD all over again --
>>>> which was hardware supported, and then discarded because of its
>>>> uselessness.
>>>
>>> Any use case where you expect a clueless business user to enter a
>>> fraction
>>> you'd want a representation with the same rounding errors as they are
>>> used
>>> to.
>>>
>>> Money is one use case yes, but there are other. It's just my experience
>>> that
>>> it's the most common use case, I have no clue what the actual statistics
>>> are
>>> though.
>>
>> And how many applications do you think handle money? The compiler sure
>> doesn't, nor does the kernel. I've worked telecom for ten years, and
>> while there certainly were applications handling money there, none of
>> mine did. They all dealt in nice integers -- the only time a
>> non-integer was passed to it, it was handled simply as a string to be
>> fed to the output.
>>
>> There's a huge world of integer-using applications. It might not be
>> _your_ world, but it is there.
>>
>>> I think BigDecimal is perfect for the task. But I can see how some people
>>> might think it could be a performance problem.
>>> So for the sake of arguments I'm suggesting that  val a = 4.2 would be
>>> interpreted as val a = BigDecimal("4.2") and not val a =
>>> Float.valueOf(4.2)
>>
>> Personally, it's almost what I'd prefer. I think the ideal would be
>> BigInt, properly optimized to work as a Double as long as it doesn't
>> overflow/underflow. If hardware supported decimal point, then I'd go
>> with BigDecimal, but I'd never forge ahead in the hopes that hardware
>> will catch up. Not unless I'm Microsoft or Oracle, at least.
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>

There are two errors in my previous email:

1. When I wrote "new nv.Ops(a)" I meant "new ev.Ops(a)"
2. When I wrote "num.add(a, b)" I meant "num.plus(a, b)"

Hopefully the underlying meaning was not lost.

On Tue, Sep 13, 2011 at 10:21:33AM -0600, Derek Williams wrote:
> I'd prefer if integer division returned a Rational, which would give a type
> safe and accurate way of handling the result. From there it can be either
> converted back to an integer or to a double depending on your
> requirements. It would also make '5 / 2 * 2' equivalent to '5 * 2 / 2'

Boy has this thread gone beyond the original scope!

Python 3's division operator does return rational results from integral
arguments. It's certainly a valid strategy. That said...

A good way to move forward would be for people who have particular
needs or desires to build their own libraries/code which they can then
promote. I'm definitely interested in discussing "standard"
implementations of other numeric types and I'm happy to try to make the
Numeric implementation I manage interop with these other libraries as
well as possible. But I don't think Numeric is the place to build them.

As for a type class hierarchy for Semigroup, Monoid, Ring, Fractional,
and Integral: I want to help out, and am willing to incorporate it my
Numeric implementation as long as it doesn't impact performance.

For those who want to take a more radical track, the right thing to do
is probably to create some kind of abstract Number class (with multiple
subclasses wrapping different numeric classes) that could track
precision, handle promotion, etc. While this would end up being slower,
I think you could create a really powerful and expressive numeric tower
this way.

I'm not sure how someone would go about lobbying for changes like
Int/Int -> Double, but I am pretty sure that discussions about Numeric
are the wrong place for it. :)

On Tue, Sep 13, 2011 at 12:11 PM, Erik Osheim <erik@plastic-idolatry.com> wrote:

I'm not sure how someone would go about lobbying for changes likeInt/Int -> Double, but I am pretty sure that discussions about Numeric
are the wrong place for it. :)

To bring my comment back on topic, if we had more granular type classes we could have something like:
trait Divide[T, R] {  def div(a: T, b: T): R }
object IntDivide extends Divide[Int, Int] {  def div(a: Int, b: Int): Int = ...}
object IntDivideToRational extends Divide[Int, Rational] {   def div(a: Int, b: Int): Rational = ...}
object IntDivideToDouble extends Divide[Int, Double] {  def div(a: Int, b: Int): Double = ... }
-- 
Derek Williams

Afaik, some languages use +, -, *, / for integer operations and +., -.,
*., /. for floating point.

Might not work with the current syntax rules in Scala, though...

> IIRC, integer division in Pascal was "div". I have no problems with that.
>

The logical split is `div` for integer division and `/` for floating-point division, plus the introduction of a `Rational` type.  The problem is that it would require some tweaking of the current precedence rules, and some dev time that's currently in very high demand...


On 13 September 2011 20:18, Simon Ochsenreither <simon@ochsenreither.de> wrote:

Afaik, some languages use +, -, *, / for integer operations and +., -., *., /. for floating point.

Might not work with the current syntax rules in Scala, though...

IIRC, integer division in Pascal was "div". I have no problems with that.

--
Kevin Wright
mail: kevin.wright@scalatechnology.com
gtalk / msn : kev.lee.wright@gmail.com quora: http://www.quora.com/Kevin-Wrightgoogle+: http://gplus.to/thecoda
kev.lee.wright@gmail.com twitter: @thecoda
vibe / skype: kev.lee.wrightsteam: kev_lee_wright
"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

On Tue, Sep 13, 2011 at 08:35:30PM +0100, Kevin Wright wrote:
> The logical split is `div` for integer division and `/` for floating-point
> division, plus the introduction of a `Rational` type. The problem is that
> it would require some tweaking of the current precedence rules, and some dev
> time that's currently in very high demand...

I that it would be nice to have a Rational type, although there are
still details to work out. E.g. Is it Rationa[T] or Rational? And if
the latter which underlying type is used? BigInt? Long?

I'd really prefer something involving / instead of `div`, especially
given that I doubt the precedence rules are up for modification/debate
any time soon. Python's // is probably out due to being a comment in
Scala, and Ocaml's /. wouldn't work either.

But maybe something similar? /~ and /$ both spring to mind (and would
have the correct precedence already). While normally inventing
operators is in bad taste, in this case I think there is historical
precedent to doing so, especially if it were going to become part of
the core library.

When I made my Rational type I chose BigInt simply because, if you are going out of the way to use Rational instead of Double, you probably care enough about precision (over speed) to want BigInt. Also, I felt that Rationals should be able to be constructed from any Double (or BigDecimal) without loss of precision.
I think a Rational[T] type may not be the best choice; if the choice to use Long was REALLY wanted, I'd think it make more sense to have 2 classes: Rational (Long) and BigRational (BigInt).
Tom

On Tue, Sep 13, 2011 at 3:58 PM, Erik Osheim <erik@plastic-idolatry.com> wrote:

On Tue, Sep 13, 2011 at 08:35:30PM +0100, Kevin Wright wrote:
> The logical split is `div` for integer division and `/` for floating-point
> division, plus the introduction of a `Rational` type.  The problem is that
> it would require some tweaking of the current precedence rules, and some dev
> time that's currently in very high demand...

I that it would be nice to have a Rational type, although there are
still details to work out. E.g. Is it Rationa[T] or Rational? And if
the latter which underlying type is used? BigInt? Long?

I'd really prefer something involving / instead of `div`, especially
given that I doubt the precedence rules are up for modification/debate
any time soon. Python's // is probably out due to being a comment in
Scala, and Ocaml's /. wouldn't work either.

But maybe something similar? /~ and /$ both spring to mind (and would
have the correct precedence already). While normally inventing
operators is in bad taste, in this case I think there is historical
precedent to doing so, especially if it were going to become part of
the core library.

On Tue, Sep 13, 2011 at 04:26:38PM -0400, Tom Switzer wrote:
> When I made my Rational type I chose BigInt simply because, if you are going
> out of the way to use Rational instead of Double, you probably care enough
> about precision (over speed) to want BigInt. Also, I felt that Rationals
> should be able to be constructed from any Double (or BigDecimal) without
> loss of precision.

Assuming Rational is "opt-in" I totally agree with you that it makes
sense to have the most precision possible. If we were to make 3 / 4 ->
Rational then I'm not sure that's such a great assumption anymore. I
think it's hard to appreciate the performance impact this would have
without doing a lot of profiling of existing Scala codebases first.

Then again maybe I'm just too concerned with performance.

> I think a Rational[T] type may not be the best choice; if the choice to use
> Long was REALLY wanted, I'd think it make more sense to have 2 classes:
> Rational (Long) and BigRational (BigInt).

You are probably right. There aren't many Ts which could satisfy
Rational[T] so maybe it's better not to act like there are.

On 13 September 2011 21:26, Tom Switzer <thomas.switzer@gmail.com> wrote:

When I made my Rational type I chose BigInt simply because, if you are going out of the way to use Rational instead of Double, you probably care enough about precision (over speed) to want BigInt. Also, I felt that Rationals should be able to be constructed from any Double (or BigDecimal) without loss of precision.
I think a Rational[T] type may not be the best choice; if the choice to use Long was REALLY wanted, I'd think it make more sense to have 2 classes: Rational (Long) and BigRational (BigInt).
Tom

+1 on Rational / BigRational, it fits in nicely with existing conventions.
I'd like to see Rational[T] as an abstract parent of IntRational, LongRational and BigRational, which gives the benefits of specialisation in the first two cases.  There's certainly an argument to be made for wanting accuracy without sacrificing too much performance, though care would have to be taken in cases where an operation on xRational would cause the numerator or denominator to overflow.  

On Tue, Sep 13, 2011 at 3:58 PM, Erik Osheim <erik@plastic-idolatry.com> wrote:

On Tue, Sep 13, 2011 at 08:35:30PM +0100, Kevin Wright wrote:
> The logical split is `div` for integer division and `/` for floating-point
> division, plus the introduction of a `Rational` type.  The problem is that
> it would require some tweaking of the current precedence rules, and some dev
> time that's currently in very high demand...

I that it would be nice to have a Rational type, although there are
still details to work out. E.g. Is it Rationa[T] or Rational? And if
the latter which underlying type is used? BigInt? Long?

I'd really prefer something involving / instead of `div`, especially
given that I doubt the precedence rules are up for modification/debate
any time soon. Python's // is probably out due to being a comment in
Scala, and Ocaml's /. wouldn't work either.

But maybe something similar? /~ and /$ both spring to mind (and would
have the correct precedence already). While normally inventing
operators is in bad taste, in this case I think there is historical
precedent to doing so, especially if it were going to become part of
the core library.