- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers

# scala numeric meta-sip

Sat, 2011-12-17, 00:41

Hi there folks,

Tom Switzer and I have been working on a huge series of SIPs designed

to improve Scala's numeric types, create new type classes, add more

unicorns, etc. This encompasses many things, from specializing Numeric

to adding types like Rational and Complex.

Even though this is surely going to be a completely uncontroversial

proposal (!) please feel free to share your thoughts, reactions, etc.

In particular I think we are interested in how we should proceed, which

parts are non-starters, which parts are OK, and what the process would

be to move forward. I don't have a good sense of what the 2.10 plan is,

and I assume that a bunch of pull requests adding these features is

*not* the right way to go forward. :)

Anyway, text is attached. Thanks for your time!

Sat, 2011-12-17, 03:21

#2
Re: scala numeric meta-sip

Anything that adds unicorns is an automatic +1

On Dec 16, 2011 6:41 PM, "Erik Osheim" <erik [at] plastic-idolatry [dot] com> wrote:

Tom Switzer and I have been working on a huge series of SIPs designed

to improve Scala's numeric types, create new type classes, add more

unicorns, etc. This encompasses many things, from specializing Numeric

to adding types like Rational and Complex.

Even though this is surely going to be a completely uncontroversial

proposal (!) please feel free to share your thoughts, reactions, etc.

In particular I think we are interested in how we should proceed, which

parts are non-starters, which parts are OK, and what the process would

be to move forward. I don't have a good sense of what the 2.10 plan is,

and I assume that a bunch of pull requests adding these features is

*not* the right way to go forward. :)

Anyway, text is attached. Thanks for your time!

Sat, 2011-12-17, 07:21

#3
Re: scala numeric meta-sip

On Fri, Dec 16, 2011 at 04:29:07PM -0800, Alex Cruise wrote:

> One thing I'd suggest is that the Bound type be spelled out explicitly in

> §6--it's clear enough from context, but I was confused and looking around

> for 15 seconds.

Yes, that's a good suggestion.

Incidentally, I will probably need to change the signatures involved. I

started implementing a first pass and the covariance was giving me

problems. You seem to have zeroed in on the least-developed part of the

essay!

Once I get something working I'll push it to the repo I linked.

Sat, 2011-12-17, 15:51

#4
Re: scala numeric meta-sip

On Friday, December 16, 2011 6:41:54 PM UTC-5, Erik Osheim wrote:

I'm not against the idea, because it has advantages, but I'm leery of this being a default boxing operation because of possibly detrimental memory and/or JVM overhead. Since this would have to do conditional operations to keep track of what underlying primitive type is currently wrapped, it may have quite significantly higher runtime overhead than the basic JVM boxed types. Performance testing here, ideally on more than one vendor's JVM, would be absolutely critical.7. Optionally, add a simple boxed Number type

This particular proposal is possibly too controversial, but will be included

because it provides an interesting way around many issues people seem to run

into.

Full removal would be bad. These types are still very much needed for interoperability with external binary data. They must exist in some form, even if they only have a subset of operations compared to other types.9. Remove support for Byte, Short and friends (H)

Sat, 2011-12-17, 16:01

#5
Re: Re: scala numeric meta-sip

On Sat, Dec 17, 2011 at 06:43:24AM -0800, Todd Vierling wrote:

> I'm not against the idea, because it has advantages, but I'm leery of this

> being a default boxing operation because of possibly detrimental memory

> and/or JVM overhead. Since this would have to do conditional operations to

> keep track of what underlying primitive type is currently wrapped, it may

> have quite significantly higher runtime overhead than the basic JVM boxed

> types. Performance testing here, ideally on more than one vendor's JVM,

> would be absolutely critical.

I agree. Like I wrote, it's sort of pie-in-the-sky. I imagine that

there'd need to be some kind of memoization or weakref cache to try to

limit the amount of GC churn, and it would definitely need to be

heavily profiled.

> Full removal would be bad. These types are still very much needed for

> interoperability with external binary data. They must exist in some form,

> even if they only have a subset of operations compared to other types.

I think I did a bad job of communicating. I'm not advocating removing

these types from Scala, but just generic numeric support for them. The

point is that if someone wrote:

def genericAlgorithm[T:Numeric](a:T, b:T, c:T) = ...

And you wanted to use instances of Byte or Short with it you'd need to

say something like:

val x:Byte = ...

val y:Byte = ...

val z:Byte = ...

genericAlgorithm[Int](x, y, z)

(It might be possible for Scala to decide to use Int automatically, but

I'm not completely sure this would work--it might end up choosing e.g.

Double instead which would be awkward.)

When doing IO and things like that Byte and ByteBuffer are essential

and I certainly don't want to remove Byte or Short from Scala. Sorry I

was unclear.

Sat, 2011-12-17, 16:11

#6
Re: Re: scala numeric meta-sip

Hi Todd,

When you are dealing with binary data and using Byte, Short, etc, then you probably won't be using generic numeric ops, but rather want to use the types directly, along with bit-wise operations. The other problem is that Java & Scala already treats operations involving Byte, Short, etc. as just integer operations. So, there is no concept of adding, or'ing, etc. Shorts on the JVM nor in Scala. Having people just use Numeric[Int] and cast makes sense, as it is what happens with primitives anyways.

By ignoring them in Numeric, you also save on having to @specialize on byte, short, etc, instead just focusing on Long, Int, Double. For a code base that is very performance oriented, that could be a lot of specialisation + extra generated code :\

Full removal would be bad. These types are still very much needed for interoperability with external binary data. They must exist in some form, even if they only have a subset of operations compared to other types.9. Remove support for Byte, Short and friends (H)

When you are dealing with binary data and using Byte, Short, etc, then you probably won't be using generic numeric ops, but rather want to use the types directly, along with bit-wise operations. The other problem is that Java & Scala already treats operations involving Byte, Short, etc. as just integer operations. So, there is no concept of adding, or'ing, etc. Shorts on the JVM nor in Scala. Having people just use Numeric[Int] and cast makes sense, as it is what happens with primitives anyways.

By ignoring them in Numeric, you also save on having to @specialize on byte, short, etc, instead just focusing on Long, Int, Double. For a code base that is very performance oriented, that could be a lot of specialisation + extra generated code :\

Sun, 2011-12-18, 04:21

#7
Re: Re: scala numeric meta-sip

On Saturday, December 17, 2011 10:00:16 AM UTC-5, Erik Osheim wrote:

OK, this makes a lot more sense. I think the example of> Full removal would be bad. These types are still very much needed for

> interoperability with external binary data. They must exist in some form,

> even if they only have a subset of operations compared to other types.I think I did a bad job of communicating. I'm not advocating removing

these types from Scala, but just generic numeric support for them.

just confused me a little and seemed, at first, that the proposal was about the base types.Byte.MaxValue + Byte.MaxValue -> Int = 254

Sun, 2011-12-18, 23:21

#8
Re: scala numeric meta-sip

Hi Erik,

first of all thanks for all the hard work to all involved in it.

I think the main point is really if we want to go down that rabbit hole.

I know that adding "special rules" is normally frowned upon, but numbers are such a fundamental thing, maybe it makes sense to "cheat" here a bit instead of relying on the ever-expanding amount of magic currently used. It is not like AnyVals aren't special-cased in the spec and in the compiler already.

For instance, it seems that Ceylon took this route. It would make sense to evaluate how painful/expensive it would be to start the whole SIP from a "prettified" "number extends the right interfaces" approach instead of the "implicit typeclass" magic.

In the end, the solution should be both nice to develop, to extend AND to use. Some of the things smell like they make the architecture prettier, but don't really improve the library user needs.

Even the Java creators agree that it was a mistake.

See https://issues.scala-lang.org/browse/SI-3235, especially the last comment.

Thanks again for all the hard work. I really use and appreciate it already.

Bye,

Simon

first of all thanks for all the hard work to all involved in it.

Like in Java, numeric types in Scala (which include most of the AnyVal types

as well as BigInt and BigDecimal) lack any super class which exposes

arithmetic operations. The types themselves also lack many methods for common

operations, which are instead provided by scala.math.

I think the main point is really if we want to go down that rabbit hole.

**Or if we bite the bullet and declare that e. g. scala.Double has a + method and implements some interface. It already "happens" in ScalaDoc anyway.**I know that adding "special rules" is normally frowned upon, but numbers are such a fundamental thing, maybe it makes sense to "cheat" here a bit instead of relying on the ever-expanding amount of magic currently used. It is not like AnyVals aren't special-cased in the spec and in the compiler already.

For instance, it seems that Ceylon took this route. It would make sense to evaluate how painful/expensive it would be to start the whole SIP from a "prettified" "number extends the right interfaces" approach instead of the "implicit typeclass" magic.

In the end, the solution should be both nice to develop, to extend AND to use. Some of the things smell like they make the architecture prettier, but don't really improve the library user needs.

This should be deprecated and removed. It was wrong, it is wrong and it will be wrong in the future.Much of scala.math simply operates on Double, and relies on

automatic conversions from Int/Float/Long to Double.

Even the Java creators agree that it was a mistake.

See https://issues.scala-lang.org/browse/SI-3235, especially the last comment.

I'm currently working on a pure Scala implementation of BigInt, but I have nothing to show yet.Part of the problem here is that Scala is trying to stay close to Java (its

BigInt and BigDecimal types are mostly just wrappers, which suffer from the

same deficiencies as their Java equivalents).

And due to the whole distinction of Numeric/Integral/Fractional being a complete anti-OO trainwreck in practice.Rather than simulating an inheritance hierarchy among numeric types, Scala

supports abstraction across numeric types via Numeric, Integral and

Fractional. Unfortunately due to performance problems, difficulties with the

type class interface, and other defects Numeric has not seen wide use,

either inside Scala's library or outside of it.

1. improve support for Long/BigInt/BigDecimal in scala.mathYes, please!

Please implement appropriate interfaces, too. (That was my point at the beginning, maybe we don't need all this implicit typeclass magic?)2. optionally, move things like abs() from scala.math to Int, Double, etc.

I think the name Decimal is problematic. I have some feeling that Oracle might use something like that for 128bit floating point numbers in the future.3. optionally, rename BigDecimal

Sounds nice. Although I still have no clear opinion on the issue of Rational vs. Rational[T:Numeric]... but I think Rational is the right choice.4. add a Rational type

Yes, please!5. add a Complex[T] type

Is there something which can't be solved by improving it instead?6. add an Interval[T] type (maybe interop with or replace NumericRange[T])

No opinion.7. optionally, implement a simple boxed Number type

This pretty much depends on whether we want to go the implicit typeclass route. I'm honest: I'm not convinced by it.8. @specialize Ordering, Numeric, etc.

9. remove support from numeric types classes for Byte and Short.

10. restructure Numeric and related type classes

11. create useful conversions for mixing literals and generic values

Thanks again for all the hard work. I really use and appreciate it already.

Bye,

Simon

Mon, 2011-12-19, 01:21

#9
Re: Re: scala numeric meta-sip

On Sun, Dec 18, 2011 at 02:17:11PM -0800, Simon Ochsenreither wrote:

> I know that adding "special rules" is normally frowned upon, but numbers

> are such a fundamental thing, maybe it makes sense to "cheat" here a bit

> instead of relying on the ever-expanding amount of magic currently used. It

> is not like AnyVals aren't special-cased in the spec and in the compiler

> already.

>

> For instance, it seems that Ceylon took this route. It would make sense to

> evaluate how painful/expensive it would be to start the whole SIP from a

> "prettified" "number extends the right interfaces" approach instead of the

> "implicit typeclass" magic.

Hi Simon,

I understand your concern. Unfortunately I do think that there are (at

least) two fundamentally incompatible cases, and a one-size-fits-all

solution will leave at least one of those cases out in the cold.

Given the situation with regard to boxing, primitives and the JVM,

there will always be a case for wanting to specialize code for a

particular primitive type. This is the case for numeric type classes

(or a macro system): you can write the method once, but it gets turned

into multiple specialized methods, each restricted to a particular

type. I can't think of any OO approach that will let you do this

without incurring terrible performance or significant boilerplate/code

duplication.

The other case is where you want to be able to ignore the particulars

of how wide various numeric representations are and just work with

numbers (increasing precision where necessary). The boxed Number +

numerical tower approach works very well for this case: you can

construct rules to ensure that Ints aren't getting accidentally turned

into Floats, make sure promotion happens to avoid overflow, and

generally decide how the different underlying types should interact.

For examples of this approach see e.g. Scheme.

I'm still working through this stuff (and hopefully will be speaking

about some of it at NEScala). But despite effort to make the type class

approach more flexible/easy or the boxed number approach faster, there

is still a gulf. My sense is that for the work Tom Switzer is doing a

boxed number type and numerical tower would pretty much solve his

needs. Whereas I basically need a Numeric type class, or a macro

system.

That said, I do agree that the community at large still hasn't fully

embraced the type trait/type class pattern yet, and so it's a bit risky

to do a big numeric redesign around it.

Mon, 2011-12-19, 03:51

#10
Re: Re: scala numeric meta-sip

Hello Simon,

Yep :-) The problem (among others) with Rational[T] is overflows. It is not easy to reason about whether you need Rational[Int], Rational[Long], or Rational[BigInt] given your problem. With Int, or Long, you just think about the min/max number you'll need. With Rational, you can't easily determine if an operation will overflow. The approach I tried was a BigInt-backed Rational, and another that can either be a Long-based Rational or a BigInt-based Rational, with automagic conversion on overflows. I felt this was a good trade-off. You'd get the size (memory) benefits and some speed benefits if your Rational's num & den fit in a Long, but don't need to worry about precision.

Also, if you are using Rational[Int], you are basically creating something that is imprecise. I think it would be hard to justify using it over Double, which is incredibly optimized on most processors. Basically, I am wary of the need to create yet another imprecise number implementation, that will never be able to compete with existing ones. I think Rational should be used when you need a data-type that can represent any rational number, given enough memory.

What may be good alternative is to provide a method on the Rational to the closest Rational with a denominator that can fit in a Long (or even any arbitrary denominator).

I still like the type class route. Truthfully, it was why I started using Scala first. I wanted to write algorithms that could use Int, BigInt, Double, or a Rational class interchangeably. Moreover, I didn't want to have to worry about having control over the implementations of those types. Scala's Numeric solved that. Type classes let you write JUST the glue between what you want and what you have. Interfaces + inheritance require you to have control over the implementation of what you have, which is not often the case.

There is also the class of people that are reusing the Int, Double, Rational, etc. data types, but not in a standard way. An obvious example is modulo arithmetic.

Cheers, Tom

Sounds nice. Although I still have no clear opinion on the issue of Rational vs. Rational[T:Numeric]... but I think Rational is the right choice.4. add a Rational type

Yep :-) The problem (among others) with Rational[T] is overflows. It is not easy to reason about whether you need Rational[Int], Rational[Long], or Rational[BigInt] given your problem. With Int, or Long, you just think about the min/max number you'll need. With Rational, you can't easily determine if an operation will overflow. The approach I tried was a BigInt-backed Rational, and another that can either be a Long-based Rational or a BigInt-based Rational, with automagic conversion on overflows. I felt this was a good trade-off. You'd get the size (memory) benefits and some speed benefits if your Rational's num & den fit in a Long, but don't need to worry about precision.

Also, if you are using Rational[Int], you are basically creating something that is imprecise. I think it would be hard to justify using it over Double, which is incredibly optimized on most processors. Basically, I am wary of the need to create yet another imprecise number implementation, that will never be able to compete with existing ones. I think Rational should be used when you need a data-type that can represent any rational number, given enough memory.

What may be good alternative is to provide a method on the Rational to the closest Rational with a denominator that can fit in a Long (or even any arbitrary denominator).

This pretty much depends on whether we want to go the implicit typeclass route. I'm honest: I'm not convinced by it.8. @specialize Ordering, Numeric, etc.

9. remove support from numeric types classes for Byte and Short.

10. restructure Numeric and related type classes

11. create useful conversions for mixing literals and generic values

I still like the type class route. Truthfully, it was why I started using Scala first. I wanted to write algorithms that could use Int, BigInt, Double, or a Rational class interchangeably. Moreover, I didn't want to have to worry about having control over the implementations of those types. Scala's Numeric solved that. Type classes let you write JUST the glue between what you want and what you have. Interfaces + inheritance require you to have control over the implementation of what you have, which is not often the case.

There is also the class of people that are reusing the Int, Double, Rational, etc. data types, but not in a standard way. An obvious example is modulo arithmetic.

Cheers, Tom

Mon, 2011-12-19, 04:41

#11
Re: Re: scala numeric meta-sip

Hi Erik, hi Tom,

I don't really want to argue, but from my POV it feels a bit like the use of typeclasses in the proposals is like "typeclasses are shiny, new and interesting, let's use them" and less about making something easy, accessible and simple to use.

Currently I don't see anything which wouldn't be solved more appropriately by having number classes implement an interface. We control _every_ number type we are currently discussing, so it feels wrong to use "last resort" tactics to do the same thing instead. While people can still use implicit typeclasses to retrofit external number types into the number hierarchy, choosing the simpler solution for the numbers under in the standard library has many benefits in my opinion:

I don't really want to argue, but from my POV it feels a bit like the use of typeclasses in the proposals is like "typeclasses are shiny, new and interesting, let's use them" and less about making something easy, accessible and simple to use.

Currently I don't see anything which wouldn't be solved more appropriately by having number classes implement an interface. We control _every_ number type we are currently discussing, so it feels wrong to use "last resort" tactics to do the same thing instead. While people can still use implicit typeclasses to retrofit external number types into the number hierarchy, choosing the simpler solution for the numbers under in the standard library has many benefits in my opinion:

- The implementation is understandable by non-experts
- ScalaDoc and code finally agree
- No need to worry about specialization, implicit classes or @inline semantics

Maybe I'm completely wrong in this regard, feel free to correct me!

Thanks and bye!

Simon

Mon, 2011-12-19, 06:31

#12
Re: Re: scala numeric meta-sip

On Sun, Dec 18, 2011 at 07:35:09PM -0800, Simon Ochsenreither wrote:

> Currently I don't see anything which wouldn't be solved more appropriately

> by having number classes implement an interface. We control _every_ number

> type we are currently discussing, so it feels wrong to use "last resort"

> tactics to do the same thing instead. While people can still use implicit

> typeclasses to retrofit external number types into the number hierarchy,

> choosing the simpler solution for the numbers under in the standard library

> has many benefits in my opinion:

OK, let me see if I can convince you...

Let's say that all numeric AnyVal types (e.g. Byte, Short, Int, Long,

Float, Double) implement a common interface (let's call it Number) that

gives you everything you want (e.g. +, -, /, *, etc).

Great, so now you can write things like:

def average(ns:Array[Number]) = ns.sum / ns.length

What kind of bytecode gets created here?

In order to avoid boxing, the JVM needs to decide if we're talking

about [I, [J, [D, or whatever (int[], long[] and double[]

respectively). Or maybe we're talking about [Lscala/math/Number;

(scala.math.Number[]) which would then box the primitives we're talking

about.

Since Number can support *all* the AnyVal types, you either need to

specialize it (to create the different implementations for int, long,

etc) or you have to box, which as I said kills performance. So at least

specialization (which you mentioned wanting to avoid) seems necessary.

Fine, you specialize. But you still have a problem, given that your

Array might contain an Int, a Float and two Doubles. Array[Number]

doesn't guarantee they're all the same number type, unless we use a

generic type parameter. So we still get a boxed array even after all

our trouble.

We can limit the array to a particular type using something like:

def average[T <: Number](ns:Array[T]) = ns.sum / ns.length

So now we have a generic type parameter bounded by our Number interface

type. We can be sure that our operators like + and / are available.

Things seem OK. At this point, the situation looks pretty similar to:

def average[T:Numeric](ns:Array[T]) = ns.sum / ns.length

This currently isn't quite so simple due to a few reasons:

1. Numeric's infix operators aren't in scope by default

2. Numeric lacks /

3. Numeric isn't able to handle T * Int

My previous work fixes #2 and #3, and #1 can be a top-level import

(e.g. import Numeric.Implicits._).

Anyway, I hope I have demonstrated that whether or not we use type

classes, good performance and a generalized number type are

fundamentally at odds with each other.

Mon, 2011-12-19, 06:41

#13
Re: Re: scala numeric meta-sip

Just to reiterate point #2: the proposal adds / to Numeric (which is why a ring type class was created; it's the old Numeric). This should make using Numeric simpler for most people as they no longer need to deal with Integral and Fractional, but rather can just use the simple Numeric. Those that need Integral (eg. NumericRange) still have it, but Numeric can be emphasized for people new to Scala.

I'm also not convinced that a Numeric type class would be that confusing. Most new Scala users see Ordering fairly soon. So, I think describing Numeric as "like Ordering, but for +,-,*, and / instead of <,>,>=,.." would put it within reach of most.

Cheers,Tom

On Mon, Dec 19, 2011 at 12:23 AM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

I'm also not convinced that a Numeric type class would be that confusing. Most new Scala users see Ordering fairly soon. So, I think describing Numeric as "like Ordering, but for +,-,*, and / instead of <,>,>=,.." would put it within reach of most.

Cheers,Tom

On Mon, Dec 19, 2011 at 12:23 AM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

On Sun, Dec 18, 2011 at 07:35:09PM -0800, Simon Ochsenreither wrote:

> Currently I don't see anything which wouldn't be solved more appropriately

> by having number classes implement an interface. We control _every_ number

> type we are currently discussing, so it feels wrong to use "last resort"

> tactics to do the same thing instead. While people can still use implicit

> typeclasses to retrofit external number types into the number hierarchy,

> choosing the simpler solution for the numbers under in the standard library

> has many benefits in my opinion:

OK, let me see if I can convince you...

Let's say that all numeric AnyVal types (e.g. Byte, Short, Int, Long,

Float, Double) implement a common interface (let's call it Number) that

gives you everything you want (e.g. +, -, /, *, etc).

Great, so now you can write things like:

def average(ns:Array[Number]) = ns.sum / ns.length

What kind of bytecode gets created here?

In order to avoid boxing, the JVM needs to decide if we're talking

about [I, [J, [D, or whatever (int[], long[] and double[]

respectively). Or maybe we're talking about [Lscala/math/Number;

(scala.math.Number[]) which would then box the primitives we're talking

about.

Since Number can support *all* the AnyVal types, you either need to

specialize it (to create the different implementations for int, long,

etc) or you have to box, which as I said kills performance. So at least

specialization (which you mentioned wanting to avoid) seems necessary.

Fine, you specialize. But you still have a problem, given that your

Array might contain an Int, a Float and two Doubles. Array[Number]

doesn't guarantee they're all the same number type, unless we use a

generic type parameter. So we still get a boxed array even after all

our trouble.

We can limit the array to a particular type using something like:

def average[T <: Number](ns:Array[T]) = ns.sum / ns.length

So now we have a generic type parameter bounded by our Number interface

type. We can be sure that our operators like + and / are available.

Things seem OK. At this point, the situation looks pretty similar to:

def average[T:Numeric](ns:Array[T]) = ns.sum / ns.length

This currently isn't quite so simple due to a few reasons:

1. Numeric's infix operators aren't in scope by default

2. Numeric lacks /

3. Numeric isn't able to handle T * Int

My previous work fixes #2 and #3, and #1 can be a top-level import

(e.g. import Numeric.Implicits._).

Anyway, I hope I have demonstrated that whether or not we use type

classes, good performance and a generalized number type are

fundamentally at odds with each other.

Mon, 2011-12-19, 11:41

#14
Re: Re: scala numeric meta-sip

Hello,

there is one point, which is implicit within the discussion,:

The overflow/underflow discussion and the different behavior of integral vs. floating points in case of errors.

Here are relevant statements in the proposal: in 4.

The implementation proposed uses a pair of Longs to represent the fraction

until the range of Long is exceeded, at which point it switches over to using

BigDecimal. This is all transparent to the user.

in 7.

However, most users don't particularly care aboutin 9.

these days, and don't want to consider things like integer overflow. It would

also allow us to override behaviors like Double.NaN, out-of-range Double's

becoming Infinity, and floating point error.

Since few people use these types, and since it will be difficult to achieve

their "normal" behavior in a type class providing T + T -> T it seems easiest

to remove them.

When it comes to the overflow/underflow issue, it was always told, that performance is more important than correctness. But I doubt, that a resultlike

scala> 1000000*1000000res0: Int = -727379968

will make any sense, even if it is very fast. Also the different behavior of integrals vs. floats is not very nice in the light of a uniform basic number system:

scala> 1/0java.lang.ArithmeticException: / by zero...

scala> 1.0/0res2: Double = Infinity

scala> 0.0/0res4: Double = NaN

So I would like a transparent conversion from Int -> Long -> BigInt.

In case performance is most demanding, someone can use the explicit (old) java type Int.

Also I would recommend a uniform Infinity, -Infinity and NaN behavior(as even BigInt has a upper/lower limit).

regardsEsser

Mon, 2011-12-19, 15:01

#15
Re: Re: scala numeric meta-sip

On Mon, Dec 19, 2011 at 02:37:22AM -0800, Esser wrote:

> When it comes to the overflow/underflow issue, it was always told, that

> performance is more important than correctness. But I doubt, that a result

> like

>

> scala> 1000000*1000000

> res0: Int = -727379968

It sounds like you're someone who would appreciate having a boxed

Number type to create some uniformity for numbers then. :)

> will make any sense, even if it is very fast. Also the different behavior

> of

> integrals vs. floats is not very nice in the light of a uniform basic

> number

> system:

>

> scala> 1/0

> java.lang.ArithmeticException: / by zero

> ...

>

> scala> 1.0/0

> res2: Double = Infinity

>

> scala> 0.0/0

> res4: Double = NaN

Unfortunately Scala does not control this behavior. The JVM treats

division-by-zero differently for int and double. The int behavior is

the one I prefer but unfortunately the only way to unify this behavior

is by wrapping all division, something I want to avoid (because once

you embrace that decision then users have no good way to opt-out).

> So I would like a transparent conversion from Int -> Long -> BigInt.

>

> In case performance is most demanding, someone can use the explicit

> (old) java type Int.

>

> Also I would recommend a uniform Infinity, -Infinity and NaN behavior

> (as even BigInt has a upper/lower limit).

I think you might be confused: Java doesn't have an Int type. Maybe you

mean Java's "int"? Unfortunately the "int" type is not available in

Scala programs, so I don't think this is feasible. Also, in a

statically-typed system these "transparent conversions" won't work

without a boxed type (because the resulting type of Int * Int -> ???

must be known). Is this what you mean?

Also, while Java's BigInteger does have a theoretical limit (it can use

at most 2^31 ints to hold it's value, so pow(2^31, 2^31) is the maximum

representable number) I think this is less of a BigInt.MaxValue and

more of a JVM limit (since it is bounded by the maximum size of an

Array). All numeric representations in finite memory will have some

upper limit. Thus, I don't think Infinity makes sense for BigInt (or

any of the integral numbers, really). Infinity is actually a huge

source of errors for people and in many cases it would be better for

operations returning infinity to produce an error (unfortunately the

JVM makes this decision for us and chooses not to).

Maybe I need to edit the proposal, but I thought I was clear that we

wanted to preserve the specific behaviors of the concrete number types

(e.g. Int, Double) while also creating a unified interface in other

cases (e.g. the boxed number/numerical tower case). Like I said,

different users fall at different places on the spectrum (I am probably

further toward the performance end, and it seems like you are further

toward the uniformity/correctness end).

I agree that the issues you point out are real. Many dynamically-typed

languages (which have no choice but to box everything) do solve them in

the ways you describe. But in Scala we do have a choice, and I think

the best solution is one which preserves people's ability to work with

the underlying JVM primitives (and their associated gotchas) when

needed, but also allows other people who want a more

consistent/friendly interface to have one.

If I were designing Scala from scratch I would probably make a boxed

Number type the default; users would have to specifically ask for Int

or Double. But as I said in the proposal adding a boxed Number type to

the language is a *big* change, and as such it seems unlikely.

Mon, 2011-12-19, 15:11

#16
Re: Re: scala numeric meta-sip

On Mon, Dec 19, 2011 at 08:57:11AM -0500, Erik Osheim wrote:

> Also, while Java's BigInteger does have a theoretical limit (it can use

> at most 2^31 ints to hold it's value, so pow(2^31, 2^31) is the maximum

> representable number) I think this is less of a BigInt.MaxValue and

> more of a JVM limit (since it is bounded by the maximum size of an

> Array).

Errr, sorry, this maximum value is too conservative, since we only need

to worry about sign bit for one of our ints, not all 2^31 of them. I

haven't read the BigInteger implementation recently, but I think the

real number is something like:

2^31 * pow(2^32, 2^30)

Anyway, it is quite large.

Mon, 2011-12-19, 15:21

#17
Re: Re: scala numeric meta-sip

On Mon, Dec 19, 2011 at 09:04:30AM -0500, Erik Osheim wrote:

> 2^31 * pow(2^32, 2^30)

Argh! I mean 2^31 * pow(2^32, 2^31 - 1).

I hope I haven't lost too much credibility due to these arithmetic

blunders. ;)

Tue, 2011-12-20, 19:51

#18
Re: scala numeric meta-sip

Just to post some updates:

1. It seems like interval arithmetic is probably a bit too nuanced to

do in a general way that won't bite people in the ass [1], so we're

going to remove it from the list. If you're interested to see what I

you can check out the interval branch at the Github project [2].

2. We are going to add OrderedRing (name not totally finalized) which

will generalize Integral and Fractional (Numeric does this currently

but is being repurposed in the proposal). Alternately if people felt

strongly that Numeric should keep it's current role, we'd need a name

that means "Some kind of Number, I don't care which, that has all the

number operations available."

3. There seems to be a lot of interest in a boxed Number type so I will

work on one and see how well I can get it performing.

I would love to hear back from more people with comments, questions or

critiques, even if it's just "looks good, keep on keepin' on." I would

also love to hear concrete feedback relating to the SIP process (which

hasn't really begun, and which I'm uncertain about).

Wed, 2011-12-21, 03:21

#19
Re: scala numeric meta-sip

On Sat, Dec 17, 2011 at 10:41 AM, Erik Osheim wrote:

> Tom Switzer and I have been working on a huge series of SIPs designed

> to improve Scala's numeric types, create new type classes, add more

> unicorns, etc. This encompasses many things, from specializing Numeric

> to adding types like Rational and Complex.

>

> Even though this is surely going to be a completely uncontroversial

> proposal (!) please feel free to share your thoughts, reactions, etc.

Some comments on your proposal and the Numeric APIs generally:

* I have my own issues with the currently API which I would like to

see addressed, that partly overlap your ideas. I have a patch against

the Scala library that breaks apart Numeric into more minimal, fine

grained traits, linked from ticket

[https://issues.scala-lang.org/browse/SI-5202]. Might be worth

comparing as it makes some different choices.

* Overall your proposals need modularity. I suggest to break out your

ideas into a series of smaller, more separate changes, with some

dependent upon others. Currently its a "snowball" of everything you

would like to add or change.

* On Partial vs Total Ordering, as touched on in "For instance,

complex numbers are unordered but Fractional extends Ordering".

There are many non-scalar "number-like" values that are not totally

ordered. Numeric presently models a /scalar/ value. Complex numbers,

and other non-scalars like intervals, polynomials, vectors, can

support some (or many) arithmetic ops, but they are only partially

ordered. I'd advocate a more general typeclass than Numeric that

inherits from PartialOrdering, that Complex can derive from.

* On math functions that are abstracted over Number types, as in

"Doesn't directly support many/most useful methods: for instance,

doing trig with Fractional requires conversion to Double."

How would we do trig for an arbitrary Fractional? Does

numerically-abstracted libraries exist for trig, power, log functions,

ie deriving via numerical methods? Thats considerable work! If not,

then I'd advocate putting such methods in a more specialized subtrait

than Fractional, since implementing them for any Fractional is

challenging.

* On Complex and Rational, and more generally, Type classes vs OO classes

The proposed Complex and Rational classes are written in

Object-oriented style. They won't fit easily with Numeric etc, which

are type classes, will they? We surely should have a consistent API

where all classes follow the same architecture, and I think the choice

(typeclasses) has already been made here.

* On user-configurable Numeric precision

I'd prefer Rational and Complex were parameterized on some T, being

Integral and Fractional respectively, rather than being hardwired to

BigInt and Double respectively. A typeclass approach encourages this.

* Rings and Fields of Abstraction

Hmmm, Im not completely comfortable that eg EuclidianRing is a

suitable name for something in the core lib, even if it is technically

correct. And for abstraction, why stop at Rings and Fields? What about

Addition, Multiplication etc as separable operations - see my proposal

[https://issues.scala-lang.org/browse/SI-5202].

As Ive mentioned [http://www.scala-lang.org/node/10871#comment-47426],

typeclass designs allow number data to behave as a Ring, Field etc,

without inheriting from it. So you can participate in algebraic

richness without needing to bake it into the core hierarchy.

-Ben

Wed, 2011-12-21, 06:11

#20
Re: scala numeric meta-sip

Hi Ben,

It does, but our goals are quite similar. We add / to Numeric too (though we also created (Ordered)Ring to replace what Numeric was (no division)). You break up things further by adding additive and multiplicative monoids. Our most basic structure is a ring. However, if your Additive, etc. traits were added too, it wouldn't cause any problems with the proposal (would just add some more super traits to ours).

I like to think of it more as throwing spaghetti at a wall and seeing what sticks ;-) I don't want to speak on Erik's behalf, but I think breaking the proposal up was always an option. The comments in this thread should help see how to prioritize/group things.

I agree, but I have a feeling it'll be hard enough to convince people of the utility of separating Fractional and Field, let alone adding something else in between the 2 :-\

You wouldn't do trig for an arbitrary Fractional, especially if you were just casting to a Double. It is much better to be explicit if you are narrowing from a Long or Rat(ional) to a Double, then to hide it. However, abs, min, max, etc. aren't so difficult.

Power (especially just to int) and nroots seem to be more common. However, nroot calculations aren't so hard, though would have to be done per number type. For something like Rat, it isn't so bad. We can get a good initial approx. using the integer nroots (ceil(nroot(num, n)) / floor(nroot(den, n))), then just use Newton's method which converges quite quickly (with a good initial approximation). I've actually just recently implemented this, so you will soon be able put a rational to a power of a rational.

At the risk of sounding type class happy, to deal with this you could, eg, create a trait with like methods (eg. nroot, sqrt) and use it as a context bound. In this case, for methods that need some sort of allowable error, you'd need to have the error be an implicit so that you can use a context bound and the error can be grabbed automagically. You can also just further extend the existing numeric traits, eg, CGAL has a FieldWithKthRoot.

However, I think the bigger problem is with silent conversions to Double.

Yes, they will. In our case, Rat is the data type, and you create type classes for it the same way you do for Int, Double, BigInt, etc.

I agree with Complex numbers being parameterized (they are currently too). However, do you have a compelling reason for parameterizing a rational type? The current implementation uses Longs if possible, but switches to BigInt on overflows. Yes, the overflow checks have some performance penalties, BUT if you allow overflows you run into problems.

Overflows in rationals are not easy to reason about. For instance, do you think (Rat(12345) / 54321 + Rat(1) / 3) pow 2 would overflow an int numerator and denominator? It does. I certainly couldn't tell you that if I didn't just type it into the REPL. I can tell, rationals grow fast. They really are the number type to use when accuracy is king.

One thing I'd like to do is let users convert a Rat to another Rat that is close to the source, but whose denominator is guaranteed to fit in, eg, a Long.

I hate choosing names, as I'm not very good at it. I welcome all alternative suggestions!

Thanks Ben!

Tom

* I have my own issues with the currently API which I would like to

see addressed, that partly overlap your ideas. I have a patch against

the Scala library that breaks apart Numeric into more minimal, fine

grained traits, linked from ticket

[https://issues.scala-lang.org/browse/SI-5202]. Might be worth

comparing as it makes some different choices.

It does, but our goals are quite similar. We add / to Numeric too (though we also created (Ordered)Ring to replace what Numeric was (no division)). You break up things further by adding additive and multiplicative monoids. Our most basic structure is a ring. However, if your Additive, etc. traits were added too, it wouldn't cause any problems with the proposal (would just add some more super traits to ours).

* Overall your proposals need modularity. I suggest to break out your

ideas into a series of smaller, more separate changes, with some

dependent upon others. Currently its a "snowball" of everything you

would like to add or change.

I like to think of it more as throwing spaghetti at a wall and seeing what sticks ;-) I don't want to speak on Erik's behalf, but I think breaking the proposal up was always an option. The comments in this thread should help see how to prioritize/group things.

* On Partial vs Total Ordering, as touched on in "For instance,

complex numbers are unordered but Fractional extends Ordering".

There are many non-scalar "number-like" values that are not totally

ordered. Numeric presently models a /scalar/ value. Complex numbers,

and other non-scalars like intervals, polynomials, vectors, can

support some (or many) arithmetic ops, but they are only partially

ordered. I'd advocate a more general typeclass than Numeric that

inherits from PartialOrdering, that Complex can derive from.

I agree, but I have a feeling it'll be hard enough to convince people of the utility of separating Fractional and Field, let alone adding something else in between the 2 :-\

* On math functions that are abstracted over Number types, as in

"Doesn't directly support many/most useful methods: for instance,

doing trig with Fractional requires conversion to Double."

How would we do trig for an arbitrary Fractional? Does

numerically-abstracted libraries exist for trig, power, log functions,

ie deriving via numerical methods? Thats considerable work! If not,

then I'd advocate putting such methods in a more specialized subtrait

than Fractional, since implementing them for any Fractional is

challenging.

You wouldn't do trig for an arbitrary Fractional, especially if you were just casting to a Double. It is much better to be explicit if you are narrowing from a Long or Rat(ional) to a Double, then to hide it. However, abs, min, max, etc. aren't so difficult.

Power (especially just to int) and nroots seem to be more common. However, nroot calculations aren't so hard, though would have to be done per number type. For something like Rat, it isn't so bad. We can get a good initial approx. using the integer nroots (ceil(nroot(num, n)) / floor(nroot(den, n))), then just use Newton's method which converges quite quickly (with a good initial approximation). I've actually just recently implemented this, so you will soon be able put a rational to a power of a rational.

At the risk of sounding type class happy, to deal with this you could, eg, create a trait with like methods (eg. nroot, sqrt) and use it as a context bound. In this case, for methods that need some sort of allowable error, you'd need to have the error be an implicit so that you can use a context bound and the error can be grabbed automagically. You can also just further extend the existing numeric traits, eg, CGAL has a FieldWithKthRoot.

However, I think the bigger problem is with silent conversions to Double.

* On Complex and Rational, and more generally, Type classes vs OO classes

The proposed Complex and Rational classes are written in

Object-oriented style. They won't fit easily with Numeric etc, which

are type classes, will they?

Yes, they will. In our case, Rat is the data type, and you create type classes for it the same way you do for Int, Double, BigInt, etc.

* On user-configurable Numeric precision

I'd prefer Rational and Complex were parameterized on some T, being

Integral and Fractional respectively, rather than being hardwired to

BigInt and Double respectively. A typeclass approach encourages this.

I agree with Complex numbers being parameterized (they are currently too). However, do you have a compelling reason for parameterizing a rational type? The current implementation uses Longs if possible, but switches to BigInt on overflows. Yes, the overflow checks have some performance penalties, BUT if you allow overflows you run into problems.

Overflows in rationals are not easy to reason about. For instance, do you think (Rat(12345) / 54321 + Rat(1) / 3) pow 2 would overflow an int numerator and denominator? It does. I certainly couldn't tell you that if I didn't just type it into the REPL. I can tell, rationals grow fast. They really are the number type to use when accuracy is king.

One thing I'd like to do is let users convert a Rat to another Rat that is close to the source, but whose denominator is guaranteed to fit in, eg, a Long.

* Rings and Fields of Abstraction

Hmmm, Im not completely comfortable that eg EuclidianRing is a

suitable name for something in the core lib, even if it is technically

correct.

I hate choosing names, as I'm not very good at it. I welcome all alternative suggestions!

As Ive mentioned [http://www.scala-lang.org/node/10871#comment-47426],

typeclass designs allow number data to behave as a Ring, Field etc,

without inheriting from it. So you can participate in algebraic

richness without needing to bake it into the core hierarchy.

-Ben

Thanks Ben!

Tom

Wed, 2011-12-21, 08:31

#21
Re: scala numeric meta-sip

Hi Ben,

Tom already replied, but I will add my few cents in also.

On Wed, Dec 21, 2011 at 01:17:16PM +1100, Ben Hutchison wrote:

> * I have my own issues with the currently API which I would like to

> see addressed, that partly overlap your ideas. I have a patch against

> the Scala library that breaks apart Numeric into more minimal, fine

> grained traits, linked from ticket

> [https://issues.scala-lang.org/browse/SI-5202]. Might be worth

> comparing as it makes some different choices.

Yes, I remember you mentioning this before. I am definitely not against

this, although I haven't spent any time working on it either. I can

imagine a concern that not having a type class with all the supported

operations listed will make it harder for users to reason about what

they can do with their instance of T, but I don't know if this will be

a problem in practice.

I can also imagine supporting your modular type classes, but then

combining them in (more-or-less) monolithic versions also, although

this might create a type class explosion.

> * Overall your proposals need modularity. I suggest to break out your

> ideas into a series of smaller, more separate changes, with some

> dependent upon others. Currently its a "snowball" of everything you

> would like to add or change.

Yeah, that's true. On the flip side, I think many of the motivations

for change come from other parts of the proposal (e.g. Rational,

Complex[T], etc) so it's nice to sketch things out. These are types

that many people try to reinvent themselves (more or less well) and

which many other languages provide out of the box.

Creating a richer universe of numeric types (as well as standardizing

and enriching the interfaces across them) will help motivate and guide

the often thorny discussion about things like numeric type classes.

Currently part of the problem is that one can imagine things working a

lot of different ways, but the "built-in" number types are so similar

(and anemic) that it's hard to get a lot of traction. If Scala is (or

is not) going to add a complex type I think that says a lot for how

seriously we need to worry about handling e.g. PartialOrdering.

That said, once things get hammered out a bit I expect that any SIPs

coming out of this will be a bit more focused.

> * On Partial vs Total Ordering, as touched on in "For instance,

> complex numbers are unordered but Fractional extends Ordering".

>

> There are many non-scalar "number-like" values that are not totally

> ordered. Numeric presently models a /scalar/ value. Complex numbers,

> and other non-scalars like intervals, polynomials, vectors, can

> support some (or many) arithmetic ops, but they are only partially

> ordered. I'd advocate a more general typeclass than Numeric that

> inherits from PartialOrdering, that Complex can derive from.

I think Tom feels as I do: in theory I support this. In practice I

don't know how many of these (specialized!) type classes we can have in

the standard library.

There's nothing to stop one from manually using PartialOrdering and

Field together, provided that both provide the right implicits, e.g.:

case class Interval[T:Field:PartialOrdering](...) = ...

Especially if we take your advice about modularity, I'm not sure we

absolutely need to support Field, PartiallyOrderedField and

OrderedField (in fact we may only need Field). In fact, you could argue

that we should drop support for Fractional and Integral on this same

basis (that you can simply say Integral:Ordering).

> * On math functions that are abstracted over Number types, as in

> "Doesn't directly support many/most useful methods: for instance,

> doing trig with Fractional requires conversion to Double."

>

> How would we do trig for an arbitrary Fractional? Does

> numerically-abstracted libraries exist for trig, power, log functions,

> ie deriving via numerical methods? Thats considerable work! If not,

> then I'd advocate putting such methods in a more specialized subtrait

> than Fractional, since implementing them for any Fractional is

> challenging.

Tom had spoken of creating type classes to support these kinds of

operations. I am assuming we would not want to define trig functions in

terms of first principles and Fractional. As long as things like

Rational or BigDecimal can do trig, and we can convert to/from a

Fractional T to those types, then maybe that is enough.

Especially if we use a type class, we can provide a default

implementation in terms of (t % 2pi).toDouble and fromDouble(d) that

should work OK, and users can always plug in their own if necessary.

Given that you support something like Complex[T:Fractional] I hope you

see the advantages of being able to do trigonometric functions on T

(for instance, when calculating a complex number's phase).

> The proposed Complex and Rational classes are written in

> Object-oriented style. They won't fit easily with Numeric etc, which

> are type classes, will they? We surely should have a consistent API

> where all classes follow the same architecture, and I think the choice

> (typeclasses) has already been made here.

I don't think this is true, although our repo may have given you the

wrong idea. GComplex[T:Fractional] is written in terms of the

Fractional type class, and is designed to be able to satisfy the Field

type class (it can't satisfy Fractional). Rat is written to be able to

satisfy Fractional. The older Complex and Rational types should be

removed once things are fully working.

In both of these cases the types behave similarly to the other concrete

number types (Double, BigDecimal, etc). While I initially wanted the

rational class to be parameterized, talking through the implementation

with Tom convinced me that this isn't a very good idea. It's easy to

define a Fraction[T] type if you want one and don't worry about

overflow, but like Tom says it's very hard to predict when overflow

will happen. I don't think a Fraction[T] is nearly as useful in

general (it's also much easier to write).

> I'd prefer Rational and Complex were parameterized on some T, being

> Integral and Fractional respectively, rather than being hardwired to

> BigInt and Double respectively. A typeclass approach encourages this.

As I said, the Complex implementation in the repo is superceded by the

(in-progress) GComplex[T:Fractional] which should suite you.

> Hmmm, Im not completely comfortable that eg EuclidianRing is a

> suitable name for something in the core lib, even if it is technically

> correct. And for abstraction, why stop at Rings and Fields? What about

> Addition, Multiplication etc as separable operations - see my proposal

> [https://issues.scala-lang.org/browse/SI-5202].

I am sympathetic to this view, although there is definitely a level of

granularity that goes too far. For instance, it's important that if

unary negation (or subtraction) is defined, that a compatible

definition of addition is used. If every simple operator consists of

its own type class I think that this may be lost.

One could certainly go farther than we have in this direction though.

For instance, one could implement AdditiveGroup, MultiplicativeGroup,

or go even farther back to things like Semigroup.

> As Ive mentioned [http://www.scala-lang.org/node/10871#comment-47426],

> typeclass designs allow number data to behave as a Ring, Field etc,

> without inheriting from it. So you can participate in algebraic

> richness without needing to bake it into the core hierarchy.

As far as I know none of the numeric types (number data) are inheriting

from Ring, Field or anything of the sort. Maybe I am confused? I think

that the current work is in line with this idea.

Anyway, thanks for your thoughtful and engaging reply. I know we

haven't seen eye-to-eye on everything as far as design of Numeric goes

but hopefully we can adjust things a bit to suit you. Alternately, if

you have a more concrete alternate vision I'd be interested to see how

it all hangs together.

Sincerely,

Thu, 2011-12-22, 01:31

#22
Re: scala numeric meta-sip

On Wed, Dec 21, 2011 at 6:25 PM, Erik Osheim wrote:

> On Wed, Dec 21, 2011 at 01:17:16PM +1100, Ben Hutchison wrote:

I have a patch against

>> the Scala library that breaks apart Numeric into more minimal, fine

>> grained traits, linked from ticket

>> [https://issues.scala-lang.org/browse/SI-5202]. Might be worth

>> comparing as it makes some different choices.

>

> I can also imagine supporting your modular type classes, but then

> combining them in (more-or-less) monolithic versions also, although

> this might create a type class explosion.

I think the additional typeclasses most likely to be useful are for

non-scalars: Partially Ordered and without conversions To/From scalar

values (eg toDouble etc). Two variants, one just Add & Multiply, one

adding Division.

Once the operations are broken out, clients can easily mix their own,

but I suspect the above variants will prove common enough to justify

standardizing.

>> How would we do trig for an arbitrary Fractional?

>

> I am assuming we would not want to define trig functions in

> terms of first principles and Fractional.

Agree, a sensible assumption but... long term.. I'm keen to

investigate the viability of this. Tom mentioned some techniques in

his earlier reply.

As long as things like

> Rational or BigDecimal can do trig, and we can convert to/from a

> Fractional T to those types, then maybe that is enough.

>

> Especially if we use a type class, we can provide a default

> implementation in terms of (t % 2pi).toDouble and fromDouble(d) that

> should work OK, and users can always plug in their own if necessary.

OK, all sounds pretty sensible.

>

> Given that you support something like Complex[T:Fractional] I hope you

> see the advantages of being able to do trigonometric functions on T

> (for instance, when calculating a complex number's phase).

Yeah, right. I see there's a problem.

>

>> The proposed Complex and Rational classes are written in

>> Object-oriented style. They won't fit easily with Numeric etc, which

>> are type classes, will they? We surely should have a consistent API

>> where all classes follow the same architecture, and I think the choice

>> (typeclasses) has already been made here.

>

> I don't think this is true, although our repo may have given you the

> wrong idea.

Ok, thats good to hear. In truth I scanned the code and saw some OO-

style methods, but didn't fully grasp the design. Glad to hear you

have the typeclass covered (which is more crucial case IMO)

>

>> I'd prefer Rational and Complex were parameterized on some T, being

>> Integral and Fractional respectively, rather than being hardwired to

>> BigInt and Double respectively. A typeclass approach encourages this.

Re: Tom's point about basing Rationals on BigInts. I still feel its

best to have a general Integral parameter in the rational typeclass,

but provide a default instance for BigInt.

BigInts are a lot slower computationally, and use more memory, than

native ints & longs, right? So if someone wants to use Rational in

anger, for heavy/speed critical computational code, they are kind of

stuck if you hardwire BigInt.

> For instance, it's important that if

> unary negation (or subtraction) is defined, that a compatible

> definition of addition is used. If every simple operator consists of

> its own type class I think that this may be lost.

Agreed. In my proposal, Subtractive extends Additive, and Divisive

extends Multiplicative, for this reason.

> or go even farther back to things like Semigroup.

I'll note that if you had an Additive or a Multiplicative operator,

you can safely define a non-ambiguous implicit conversion to (scalaz)

Monoid or Semigroup, hopefully enabling easy interop to Scalaz.

However, if you try to convert from (current) Numeric to Monoid, you

encounter ambiguity problems, because Numeric has so many features

there are many monoids it could form eg +, *, min(abs()), max(abs()).

Thats one of the other benefits of splitting Numeric up.

-Ben

Thu, 2011-12-22, 01:41

#23
Re: scala numeric meta-sip

On Wed, Dec 21, 2011 at 5:45 AM, Erik Osheim wrote:

> 1. It seems like interval arithmetic is probably a bit too nuanced to

> do in a general way that won't bite people in the ass...

> [1] For instance:

>

> * Complex intervals have multiple valid representations.

> * Suggestions that Taylor models may be better than traditional intervals [3]

> * Subtleties and slippage around identity, +, *, etc.

I don't quite understand the above, especially the last point, could

you explain a little more.

I feel an arithmetic typeclass instance, defined over an interval of

two scalar Fractional end point bounds, would be useful.

If you buy my argument that Complex isn't scalar and totally ordered,

and should be modelled by a weaker type than (current) Numeric, does

that resolve "Complex intervals have multiple valid representations".

Ie Type system would prevent putting a Complex into an Interval, but

you could put its real or imaginary parts in.

-Ben

Thu, 2011-12-22, 02:31

#24
Re: scala numeric meta-sip

>> I'd prefer Rational and Complex were parameterized on some T, being

>> Integral and Fractional respectively, rather than being hardwired to

>> BigInt and Double respectively. A typeclass approach encourages this.

Re: Tom's point about basing Rationals on BigInts. I still feel its

best to have a general Integral parameter in the rational typeclass,

but provide a default instance for BigInt.

BigInts are a lot slower computationally, and use more memory, than

native ints & longs, right? So if someone wants to use Rational in

anger, for heavy/speed critical computational code, they are kind of

stuck if you hardwire BigInt.

Well, they are slower. My implementation tries to help by using Longs when possible. The overflow checks do slow things down a bit, but its still faster than using BigInts and saves a lot of space too. Moreover, I feel that the small amount of time doing overflow checks will be dwarfed by finding the GCD. So, if you are staying within the range of Longs, then the code should perform decently well. If you go outside of the range of longs, then you don't have an error.

To me, this is the best compromise, especially for something in the standard lib.

Hrmm.... actually... If I came back with some benchmarks showing that the hybrid implementation performs nearly as well (about on part) as a purely Long-based implementation, for operations that don't overflow, do you think this would be enough evidence to convince people that we don't need to parameterize Rat(ional)? I think this is a good way to go: putting my money where my mouth is ;-) I may also find I need to optimize the code some more too.

Thu, 2011-12-22, 02:41

#25
Re: scala numeric meta-sip

Also, if you are looking at the code, look at Rat, not Rational. Rational is an old BigInt-backed version, Rat is the hybrid. We mean to remove Rational, and rename Rat to Rational at some point.

On Wed, Dec 21, 2011 at 8:25 PM, Tom Switzer <thomas [dot] switzer [at] gmail [dot] com> wrote:

On Wed, Dec 21, 2011 at 8:25 PM, Tom Switzer <thomas [dot] switzer [at] gmail [dot] com> wrote:

>> I'd prefer Rational and Complex were parameterized on some T, being

>> Integral and Fractional respectively, rather than being hardwired to

>> BigInt and Double respectively. A typeclass approach encourages this.

Re: Tom's point about basing Rationals on BigInts. I still feel its

best to have a general Integral parameter in the rational typeclass,

but provide a default instance for BigInt.

BigInts are a lot slower computationally, and use more memory, than

native ints & longs, right? So if someone wants to use Rational in

anger, for heavy/speed critical computational code, they are kind of

stuck if you hardwire BigInt.

Well, they are slower. My implementation tries to help by using Longs when possible. The overflow checks do slow things down a bit, but its still faster than using BigInts and saves a lot of space too. Moreover, I feel that the small amount of time doing overflow checks will be dwarfed by finding the GCD. So, if you are staying within the range of Longs, then the code should perform decently well. If you go outside of the range of longs, then you don't have an error.

To me, this is the best compromise, especially for something in the standard lib.

Hrmm.... actually... If I came back with some benchmarks showing that the hybrid implementation performs nearly as well (about on part) as a purely Long-based implementation, for operations that don't overflow, do you think this would be enough evidence to convince people that we don't need to parameterize Rat(ional)? I think this is a good way to go: putting my money where my mouth is ;-) I may also find I need to optimize the code some more too.

Thu, 2011-12-22, 04:31

#26
Re: scala numeric meta-sip

On Wed, Dec 21, 2011 at 6:25 PM, Erik Osheim wrote:

>> The proposed Complex and Rational classes are written in

>> Object-oriented style. They won't fit easily with Numeric etc, which

>> are type classes, will they? We surely should have a consistent API

>> where all classes follow the same architecture, and I think the choice

>> (typeclasses) has already been made here.

>

> I don't think this is true, although our repo may have given you the

> wrong idea. GComplex[T:Fractional] is written in terms of the

> Fractional type class, and is designed to be able to satisfy the Field

> type class (it can't satisfy Fractional). Rat is written to be able to

> satisfy Fractional.

Tom, Erik,

After reading Tom's recent comments on Rational, I reviewed your

existing Rat source. I now realise that before we go further on Longs

vs BigInts, we need to discuss out something more fundamental: to me,

Rat is not what I think of as a Type class.

So what do I claim is a type class? The essential idea is to separate

Data and Behaviour. In OO, the data contains a pointer to behavior,

but in type class style, they are defined separately, and joined by

the compiler with the aid of the type system (in Scala, via implicit

parameter search). There are three pieces:

1. The data, naked, un-encapsulated, without operations. Its type is

always tracked parametrically in the type system. Lets call it A.

2. The abstract behavior. The typeclass definition. A set of

operations, parameterised on the data type A, over As. But no data. In

scala, this is an abstract trait.

3. The implementations of the behavior, for a particular type of A.

The type class instances. In Scala, a concrete class or object that

implements the trait thats in implicit scope(s).

Lets look at rationals for example:

1. The data might be a pair of Longs in a bare case class Rational, or

just a tuple (Long, Long)

2. The typeclass definition is Fractional[Rational]

3. The typeclass implementation is a set of operations that implement

Fractional for Rational, by interpreting its 2 fields as the numerator

and denominator of a rational number.

Now, anywhere that code requires something Fractional, you can pass

your Rational case class or your tuple (Long, Long).

So the *key* benefit of typeclasses is that the client is free to pass

a new data representation B, so long as they also provide an

implementation of the Fractional operations Fractional[B]. Its that

extensibility, without inheritance, that makes typeclass designs so

open. And its exactly that extensibility that is enabling us to

"retrofit" a new Numeric hierarchy over the core JVM types, even

though their implementation and inheritance hierarchy is fixed and

unchangeable.

Now, in the context of above, how can a Rational "change type" between

Long and BigInt in-flight - I don't see how? And that's perhaps the

heart of why Ive not quite understood your proposals...

-Ben

Thu, 2011-12-22, 04:41

#27
Re: scala numeric meta-sip

On Thu, Dec 22, 2011 at 11:31:25AM +1100, Ben Hutchison wrote:

> On Wed, Dec 21, 2011 at 5:45 AM, Erik Osheim wrote:

> > 1. It seems like interval arithmetic is probably a bit too nuanced to

> > do in a general way that won't bite people in the ass...

> > [1] For instance:

> >

> > * Complex intervals have multiple valid representations.

> > * Suggestions that Taylor models may be better than traditional intervals [3]

> > * Subtleties and slippage around identity, +, *, etc.

>

> I don't quite understand the above, especially the last point, could

> you explain a little more.

>

> I feel an arithmetic typeclass instance, defined over an interval of

> two scalar Fractional end point bounds, would be useful.

>

> If you buy my argument that Complex isn't scalar and totally ordered,

> and should be modelled by a weaker type than (current) Numeric, does

> that resolve "Complex intervals have multiple valid representations".

> Ie Type system would prevent putting a Complex into an Interval, but

> you could put its real or imaginary parts in.

So, I should preface this by saying I haven't used interval arithmetic

a lot in a day-to-day way, so other practitioners should feel free to

jump in and clarify or contradict my points.

First, complex intervals:

When doing complex intervals there's a basic question: are you defining

rectangles in the complex plane using cartesian coordinates or defining

sectors (radial slices) using polar coordinates? This makes a

difference when figuring out how the various operations need to work.

All of the complex interval forms expose the user to significant loss

of interval precision (they are not minimal, they introduce pessimism).

The second point is sort of an aside, so I will leave it aside for now.

The last point just explicates the various ways that intervals can

be difficult to use correctly or reason about:

One common way to think about interval arithmetic is that each interval

represents a single particular value with built-in uncertainty. Thus, x

= [-1, 1] represents a single particular value (x') that is contained

somewhere in the closed interval from -1 to 1 (but we don't know

where).

Say I have:

x = [-1, 1]

y = [-1, 1]

First, does x == y? It depends: x' could equal y' but it also could not

(we don't actually know their values). We could choose to define this

as true or false (and false is probably more correct), but neither

answer is very satisfying.

If you say that they are not equal then equality and ordering become

difficult/useless with intervals. You also lose composition (because

you have to share "pointers" to be sure two intervals are the same) or

you end up doing other weird hacks. In any event, they don't behave how

we expect numbers to behave, and it means we can't use the obvious case

class implementation.

If you say they are equal, then consider:

x * x = z1 = pow(x, 2)

x * y = z2

If we know x' is in [-1, 1], then we can be pretty sure pow(x', 2) is

in [0, 1] right? So that means that z1 is [0, -1]. But if y' is -1 and

x' is 1, then z2' is -1, so that means that z2 must contain -1, so it

should be [-1, 1]. But if we say x == y then algebraically we'd expect

z1 == z2. Each time this happens you lose valuable precision until your

intervals are completely blown out.

When dealing with interval arithmetic these errors are often avoided by

trying not to repeat terms like x--if a particular range is only

mentioned once then you can dodge these kinds of "identity issues" and

not worry about them.

However, there are other kinds of slippage that happen also. For

instance, for positive numbers a, b, c and d:

x = [-a, b]

y = [-c, d]

z = x / y = (-∞, ∞)

This is true because y' can be arbitrarily close to 0 on either side,

since it's interval crosses zero. Thus, for a particular x' we can make

z' as large (or small) as we want, and so the resulting interval is

unbounded. People often avoid intervals crossing zero, or deal with

them piece-wise to avoid this kind of behavior.

There are a lot of good resources online and in books about the

problems and strategies for dealing with or minimizing them if you're

interested.

Hope this helps. I think even "normal" intervals would be difficult for

people to reason about, and the complex interval problems are just the

icing on an already treacherous cake.

Thu, 2011-12-22, 04:51

#28
Re: scala numeric meta-sip

Just to try to be clear about what Tom and I have proposed:

Complex[T] is a concrete type (case class) that is parameterized on the

type class fractional. Prototype:

case class Complex[T:Fractional](real:T, imag:T)

Rational is a concrete type (sealed trait with various subclasses) that

is not parameterized. Internally it uses Long-based subtype where

possible, and promotes that to a BigInt-based subtype as necessary. It

resembles BigDecimal in that the underlying implementation is opaque to

the user... it just "does the right thing" in terms of type promotion

to maintain precision.

Both types participate in (are members of) some type classes:

Complex is in Ring, EuclideanRing and Field (and Numeric)

Rational is in Ring, EuclideanRing and Field

as well as OrderedRing, Integral and Fractional (and Numeric)

Users could choose to create their own rational or complex types but

there is no "complex type class" or "rational type class" that they

could plug into, in the same way that there isn't a "decimal interface"

or "real value interface" in Scala.

Thus, code written with the Complex or Rational types in mind will

definitely *not* be compatible with some future user-defined complex

number representation, in the same way that code written with Int or

Double in mind is not compatible with UserInt or UserDouble types.

If you believe the Scala library should have all its uses of number

written in terms of a type class that permits future user-defined

versions of e.g. int, double, rational, complex, etc. then our proposal

definitely does *not* move in that direction. I didn't realize that was

what you might be proposing (and maybe I'm just putting words in your

mouth).

Does this clear anything up? Have I misunderstood your question or

position?

Thu, 2011-12-22, 05:21

#29
Re: scala numeric meta-sip

Hi Ben,

Erik just replied, but I'll post this anyways.

OK, there are some fundamental communication problems, I think! If I removed all operations from Rational and did everything from within a Fractional instance, we would have what you were thinking of.

The gain in this case is dubious. You would no longer be able to use Rational outside of the numeric typeclass. For a language like Haskell, this doesn't matter, because typeclasses are an essential part of the system. In Scala they are not. People don't expect to not be able to do Rat(1,2) * Rat(1,3) without having to import a a bunch of implicits. Scala is an OO language. I know the utility of type classes, but that doesn't require we also ditch the OO aspects of Scala.

Now, that said, think of the implementations in Rat as default implementations. If you really want, you are more than welcome to create a Fractional[Rat] type class that doesn't use any of the implementations of +, -, *, etc. that come within Rat by default. That is, you can just treat Rat as a data type. However, our default instance of Fractional[Rat] just delegates to Rat's implementation by default.

What we're doing is giving people both worlds; you can use Fractional[Rat] if you want (in this case, you shouldn't care that the implementation delegates to Rat's), or you can just use Rat directly, like you would if you were using Double without Fractional.

I think this would be bad, as (Long, Long) could also be a type class for Complex, or a 2D Point, or a 2d Vector, etc. This means you would need to explicitly pass implicits around if you were to mix these. In this case, a special class makes sense (eg. Rat). Now, if that is the case, why worry whether Rat has an implementation of +? All you care about is whether you can get an instance of Fractional[Rat] that implements these methods for the Rat "data type".

You can do this now:

def div[A: Fractional](x: A, y: A) = x / ydiv(Rat(1), Rat(2))div(1.0, 2.0)

The fact that (our implementation) Fractional[Rat] delegates its operations to Rat does not matter, as far as div is concerned. All it cares about is that there is a Fractional[A], which there is when A is a Rat.

Yes, exactly. Rat, the number type, is separate from Fractional[Rat], the typeclass. The fact that Rat can also be used by itself (as Scala is an OO language), shouldn't matter to people who are just using the Fractional typeclass.

Well,

sealed trait Rational { def numerator: BigInt def denominator: BigInt }case class BigRational(numerator: BigInt, denominator: BigInt) extends Rationalcase class LongRational(n: Long, d: Long) extends Rational { def numerator = n.toBigInt def denominator = d.toBigInt }

then in Fractional[Rational] you just pattern match.

Erik just replied, but I'll post this anyways.

Tom, Erik,

After reading Tom's recent comments on Rational, I reviewed your

existing Rat source. I now realise that before we go further on Longs

vs BigInts, we need to discuss out something more fundamental: to me,

Rat is not what I think of as a Type class.

OK, there are some fundamental communication problems, I think! If I removed all operations from Rational and did everything from within a Fractional instance, we would have what you were thinking of.

The gain in this case is dubious. You would no longer be able to use Rational outside of the numeric typeclass. For a language like Haskell, this doesn't matter, because typeclasses are an essential part of the system. In Scala they are not. People don't expect to not be able to do Rat(1,2) * Rat(1,3) without having to import a a bunch of implicits. Scala is an OO language. I know the utility of type classes, but that doesn't require we also ditch the OO aspects of Scala.

Now, that said, think of the implementations in Rat as default implementations. If you really want, you are more than welcome to create a Fractional[Rat] type class that doesn't use any of the implementations of +, -, *, etc. that come within Rat by default. That is, you can just treat Rat as a data type. However, our default instance of Fractional[Rat] just delegates to Rat's implementation by default.

What we're doing is giving people both worlds; you can use Fractional[Rat] if you want (in this case, you shouldn't care that the implementation delegates to Rat's), or you can just use Rat directly, like you would if you were using Double without Fractional.

1. The data might be a pair of Longs in a bare case class Rational, or

just a tuple (Long, Long)

I think this would be bad, as (Long, Long) could also be a type class for Complex, or a 2D Point, or a 2d Vector, etc. This means you would need to explicitly pass implicits around if you were to mix these. In this case, a special class makes sense (eg. Rat). Now, if that is the case, why worry whether Rat has an implementation of +? All you care about is whether you can get an instance of Fractional[Rat] that implements these methods for the Rat "data type".

2. The typeclass definition is Fractional[Rational]

3. The typeclass implementation is a set of operations that implement

Fractional for Rational, by interpreting its 2 fields as the numerator

and denominator of a rational number.

Now, anywhere that code requires something Fractional, you can pass

your Rational case class or your tuple (Long, Long).

You can do this now:

def div[A: Fractional](x: A, y: A) = x / ydiv(Rat(1), Rat(2))div(1.0, 2.0)

The fact that (our implementation) Fractional[Rat] delegates its operations to Rat does not matter, as far as div is concerned. All it cares about is that there is a Fractional[A], which there is when A is a Rat.

So the *key* benefit of typeclasses is that the client is free to pass

a new data representation B, so long as they also provide an

implementation of the Fractional operations Fractional[B]. Its that

extensibility, without inheritance, that makes typeclass designs so

open. And its exactly that extensibility that is enabling us to

"retrofit" a new Numeric hierarchy over the core JVM types, even

though their implementation and inheritance hierarchy is fixed and

unchangeable.

Yes, exactly. Rat, the number type, is separate from Fractional[Rat], the typeclass. The fact that Rat can also be used by itself (as Scala is an OO language), shouldn't matter to people who are just using the Fractional typeclass.

Now, in the context of above, how can a Rational "change type" between

Long and BigInt in-flight - I don't see how? And that's perhaps the

heart of why Ive not quite understood your proposals...

Well,

sealed trait Rational { def numerator: BigInt def denominator: BigInt }case class BigRational(numerator: BigInt, denominator: BigInt) extends Rationalcase class LongRational(n: Long, d: Long) extends Rational { def numerator = n.toBigInt def denominator = d.toBigInt }

then in Fractional[Rational] you just pattern match.

-Ben

Thu, 2011-12-22, 05:31

#30
Re: scala numeric meta-sip

On Thu, Dec 22, 2011 at 3:14 PM, Tom Switzer wrote:

>> After reading Tom's recent comments on Rational, I reviewed your

>> existing Rat source. I now realise that before we go further on Longs

>> vs BigInts, we need to discuss out something more fundamental: to me,

>> Rat is not what I think of as a Type class.

>

> OK, there are some fundamental communication problems, I think! If I removed

> all operations from Rational and did everything from within a Fractional

> instance, we would have what you were thinking of.

>

> The gain in this case is dubious. You would no longer be able to use

> Rational outside of the numeric typeclass. For a language like Haskell, this

> doesn't matter, because typeclasses are an essential part of the system. In

> Scala they are not. People don't expect to not be able to do Rat(1,2) *

> Rat(1,3) without having to import a a bunch of implicits. Scala is an OO

> language. I know the utility of type classes, but that doesn't require we

> also ditch the OO aspects of Scala.

>

> Now, that said, think of the implementations in Rat as default

> implementations. If you really want, you are more than welcome to create a

> Fractional[Rat] type class that doesn't use any of the implementations of +,

> -, *, etc. that come within Rat by default. That is, you can just treat Rat

> as a data type. However, our default instance of Fractional[Rat] just

> delegates to Rat's implementation by default.

Ok, makes sense. I understand the plan now: type class delegates to OO class.

-Ben

Looks great from a cursory reading!

One thing I'd suggest is that the Bound type be spelled out explicitly in §6--it's clear enough from context, but I was confused and looking around for 15 seconds.

-0xe1a