scala numeric meta-sip

On Fri, Dec 16, 2011 at 3:41 PM, Erik Osheim <erik@plastic-idolatry.com> wrote:

... huge ... numeric

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 

Anything that adds unicorns is an automatic +1

On Dec 16, 2011 6:41 PM, "Erik Osheim" <erik@plastic-idolatry.com> wrote:

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!

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.

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

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.

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.

9. Remove support for Byte, Short and friends (H)

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.

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.

Hi Todd, 

9. Remove support for Byte, Short and friends (H)

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.

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 :\

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

> 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.

OK, this makes a lot more sense. I think the example of

Byte.MaxValue + Byte.MaxValue -> Int = 254

just confused me a little and seemed, at first, that the proposal was about the base types.

Hi Erik,

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.

 

Much of scala.math simply operates on Double, and relies on
automatic conversions from Int/Float/Long to Double.

This should be deprecated and removed. It was wrong, it is wrong and it will be wrong in the future.
Even the Java creators agree that it was a mistake.
See https://issues.scala-lang.org/browse/SI-3235, especially the last comment.

 

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).

I'm currently working on a pure Scala implementation of BigInt, but I have nothing to show yet.

 

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.

And due to the whole distinction of Numeric/Integral/Fractional being a complete anti-OO trainwreck in practice.

 

   1. improve support for Long/BigInt/BigDecimal in scala.math

Yes, please!

   2. optionally, move things like abs() from scala.math to Int, Double, etc.

Please implement appropriate interfaces, too. (That was my point at the beginning, maybe we don't need all this implicit typeclass magic?)

 

   3. optionally, rename BigDecimal

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.

   4. add a Rational type

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.

 

   5. add a Complex[T] type

Yes, please!
 

   6. add an Interval[T] type (maybe interop with or replace NumericRange[T])

Is there something which can't be solved by improving it instead?

 

   7. optionally, implement a simple boxed Number type

No opinion.
 

   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

This pretty much depends on whether we want to go the implicit typeclass route. I'm honest: I'm not convinced by it.

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

Bye,

Simon

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.

Hello Simon, 

   4. add a Rational type

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.

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). 

   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

This pretty much depends on whether we want to go the implicit typeclass route. I'm honest: I'm not convinced by it.

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

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:

• 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

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.

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@plastic-idolatry.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.

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 about
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. 

 in 9. 

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

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.

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.

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. ;)

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).

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

Hi Ben,

* 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

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,

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

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

>> 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.  

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.switzer@gmail.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.  

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

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.

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?

Hi Ben,
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

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