Is there any actual interest in a SIP for fixing the numerical stuff in the standard library?

I'd love to see the work Erik did wind up as the prototype for a SIP.   I think it might be easier to split the SIP up a bit, i.e. Each of your bullet points might make a decent SIP, although you probably want a better name than "Numeric is broken and slow".   Perhaps "Speed and API improvements to Numeric".
- Josh

On Thu, Oct 20, 2011 at 8:26 AM, Simon Ochsenreither <simon.ochsenreither@googlemail.com> wrote:

Hi everyone!

From time to time people (including me) complain about the brokenness of the numerical stuff shipped with Scala.

The complaints usually include

• Numeric is broken and slow
• We need a better abstracted numerical hierarchy with things like Groups, SemiGroups, ...
• The standard library lacks classes for Complex numbers or Fractions
  

For the first part, Erik Osheim already sat down and did most of the work (and with the proposals about inlining implicits a complete solution looks achievable). (Thanks Erik!)

The second item was lengthly discussed on the mailing list, but I'm unsure if a conclusion was reached.

The third item was discussed to, but nobody stepped up with a proposed implementation.

Is there enough interest to put a SIP together, so we can finally move things forward?

I look forward hearing your opinion regarding that matter.

Thanks!


Simon

Thanks for the gentle prod Simon. :)

I will try to take some time soon to write up a SIP on improvements to
Numeric, get some feedback from folks and send it to the list.

Thanks, that would be really great!

IMHO a combined proposal makes sense here, because it is necessary that we have a look at the “big picture”, so that we don't end up with three different solutions not working together as well as they could.

Hi,

Simon Ochsenreither asked:
> Is there enough interest to put a SIP together, so we can finally move things forward?

yes please! I worked on specializing the Numeric hierarchy for a while and exchanged a few emails with Iulian Dragos but never really gotten any improvement into the library. I would absolutely love to move this forward and help in whatever way I can.

Kind regards
Andreas

Let's hope some of those who proposed the Monoid/SemiGroup/... stuff chime in, too.

On 10/20/11 14:13, Simon Ochsenreither wrote:
> Let's hope some of those who proposed the Monoid/SemiGroup/... stuff
> chime in, too.

"Int is not a Monoid." [1] Happy now? :)

-Martin

[1] http://groups.google.com/group/scala-user/msg/4cf7c38353c7ddfe

On Thu, Oct 20, 2011 at 8:13 PM, Simon Ochsenreither <simon.ochsenreither@googlemail.com> wrote:

Let's hope some of those who proposed the Monoid/SemiGroup/... stuff chime in, too.

Here's some inspiration:
https://github.com/ekmett/scala-numerics/tree/master/src/main/scala/numeric
https://github.com/ekmett/scala-ad/tree/master/src/main/scala/ad
-jason

I'd love to see a compare with epsilon in Float (Double or Real or whatsoever) as in geometrical computations the Java '==' comparing bits is practically useless. I dare even to say that it is wrong, as it is leading to well hidden errors.

I would love to use Scala-Double with an overriden compare, but I doubt that this is possible

Thomas


Am 20.10.2011 20:26, schrieb Jason Zaugg:

CAG3_yeXDTFHjzodkZDxdb2wt6ji0ZtUArbg4xD765yfJ4YCiKw [at] mail [dot] gmail [dot] com" type="cite">On Thu, Oct 20, 2011 at 8:13 PM, Simon Ochsenreither <simon [dot] ochsenreither [at] googlemail [dot] com" rel="nofollow">simon.ochsenreither@googlemail.com> wrote:

Let's hope some of those who proposed the Monoid/SemiGroup/... stuff chime in, too.

Here's some inspiration:
https://github.com/ekmett/scala-numerics/tree/master/src/main/scala/numeric
https://github.com/ekmett/scala-ad/tree/master/src/main/scala/ad
-jason

-- 
Flötenbau Thomas Fehr

Hulfteggstr. 13
CH-9534 Gähwil


Tel:   	+41 (0)44 926 65 26
Skype: 	thomas_fehr

www.floetenbau.ch

== is final on Any.  http://www.scala-lang.org/api/current/index.html#scala.Any

On Thu, Oct 20, 2011 at 3:42 PM, Thomas Fehr <thomas.fehr@floetenbau.ch> wrote:

I'd love to see a compare with epsilon in Float (Double or Real or whatsoever) as in geometrical computations the Java '==' comparing bits is practically useless. I dare even to say that it is wrong, as it is leading to well hidden errors.

I would love to use Scala-Double with an overriden compare, but I doubt that this is possible

Thomas


Am 20.10.2011 20:26, schrieb Jason Zaugg:

On Thu, Oct 20, 2011 at 8:13 PM, Simon Ochsenreither <simon.ochsenreither@googlemail.com> wrote:

Let's hope some of those who proposed the Monoid/SemiGroup/... stuff chime in, too.

Here's some inspiration:
https://github.com/ekmett/scala-numerics/tree/master/src/main/scala/numeric
https://github.com/ekmett/scala-ad/tree/master/src/main/scala/ad
-jason

-- 
Flötenbau Thomas Fehr

Hulfteggstr. 13
CH-9534 Gähwil


Tel:   	+41 (0)44 926 65 26
Skype: 	thomas_fehr

www.floetenbau.ch

It'd be nice if ==, != etc took an implicit Equivalence

(global equality is ungooddoubleplus)

On Thu, Oct 20, 2011 at 9:45 PM, Josh Suereth <joshua.suereth@gmail.com> wrote:

== is final on Any.  http://www.scala-lang.org/api/current/index.html#scala.Any

On Thu, Oct 20, 2011 at 3:42 PM, Thomas Fehr <thomas.fehr@floetenbau.ch> wrote:

I'd love to see a compare with epsilon in Float (Double or Real or whatsoever) as in geometrical computations the Java '==' comparing bits is practically useless. I dare even to say that it is wrong, as it is leading to well hidden errors.

I would love to use Scala-Double with an overriden compare, but I doubt that this is possible

Thomas


Am 20.10.2011 20:26, schrieb Jason Zaugg:

On Thu, Oct 20, 2011 at 8:13 PM, Simon Ochsenreither <simon.ochsenreither@googlemail.com> wrote:

Let's hope some of those who proposed the Monoid/SemiGroup/... stuff chime in, too.

Here's some inspiration:
https://github.com/ekmett/scala-numerics/tree/master/src/main/scala/numeric
https://github.com/ekmett/scala-ad/tree/master/src/main/scala/ad
-jason

-- 
Flötenbau Thomas Fehr

Hulfteggstr. 13
CH-9534 Gähwil


Tel:   	+41 (0)44 926 65 26
Skype: 	thomas_fehr

www.floetenbau.ch

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

Equality with epsilons doesn't really work though as it isn't transitive. For geometrical computations, you can get away with quite a lot without resorting to floating point math (use rationals or homogenous coordinates).
On Thu, Oct 20, 2011 at 3:42 PM, Thomas Fehr <thomas.fehr@floetenbau.ch> wrote:

I'd love to see a compare with epsilon in Float (Double or Real or whatsoever) as in geometrical computations the Java '==' comparing bits is practically useless. I dare even to say that it is wrong, as it is leading to well hidden errors.

I would love to use Scala-Double with an overriden compare, but I doubt that this is possible

Thomas


Am 20.10.2011 20:26, schrieb Jason Zaugg:

On Thu, Oct 20, 2011 at 8:13 PM, Simon Ochsenreither <simon.ochsenreither@googlemail.com> wrote:

Let's hope some of those who proposed the Monoid/SemiGroup/... stuff chime in, too.

Here's some inspiration:
https://github.com/ekmett/scala-numerics/tree/master/src/main/scala/numeric
https://github.com/ekmett/scala-ad/tree/master/src/main/scala/ad
-jason

-- 
Flötenbau Thomas Fehr

Hulfteggstr. 13
CH-9534 Gähwil


Tel:   	+41 (0)44 926 65 26
Skype: 	thomas_fehr

www.floetenbau.ch

thanks. What are the practical limitations of non-transitivity?

- Thomas

Am 20.10.2011 22:28, schrieb Tom Switzer:

CAMRK40bk6Nc8O6S+X_W7U9Qj4snGcT2TJ095ULbWjV58zSjXrQ [at] mail [dot] gmail [dot] com" type="cite">Equality with epsilons doesn't really work though as it isn't transitive. For geometrical computations, you can get away with quite a lot without resorting to floating point math (use rationals or homogenous coordinates).
On Thu, Oct 20, 2011 at 3:42 PM, Thomas Fehr <thomas [dot] fehr [at] floetenbau [dot] ch" rel="nofollow">thomas.fehr@floetenbau.ch> wrote:

I'd love to see a compare with epsilon in Float (Double or Real or whatsoever) as in geometrical computations the Java '==' comparing bits is practically useless. I dare even to say that it is wrong, as it is leading to well hidden errors.

I would love to use Scala-Double with an overriden compare, but I doubt that this is possible

Thomas


Am 20.10.2011 20:26, schrieb Jason Zaugg:

On Thu, Oct 20, 2011 at 8:13 PM, Simon Ochsenreither <simon [dot] ochsenreither [at] googlemail [dot] com" target="_blank" rel="nofollow">simon.ochsenreither@googlemail.com> wrote:

Let's hope some of those who proposed the Monoid/SemiGroup/... stuff chime in, too.

Here's some inspiration:
https://github.com/ekmett/scala-numerics/tree/master/src/main/scala/numeric
https://github.com/ekmett/scala-ad/tree/master/src/main/scala/ad
-jason

 

On Fri, Oct 21, 2011 at 5:09 AM, Thomas Fehr <thomas.fehr@floetenbau.ch> wrote:

thanks. What are the practical limitations of non-transitivity?

Broken code that appears correct.

Hi Thomas,
It can be hairy if you are using other libraries that expect equivalence to be transitive. For instance, just testing if 3 numbers are equal, a simple method would be,
import Ordering.Implicits._
def equal[A : Ordering](a: A, b: A, c: A) = (a equiv b) && (b equiv c)
If the equiv method here isn't transitive then how we order our parameters matters (which would be a surprise for many people).
case class EpsOrdering(e: Double) extends Ordering[Double] {  def compare(x: Double, y: Double) = {    val diff = x - y    if (scala.math.abs(diff) < e) 0     else if (diff < 0) -1    else 1  }}
val a = 0.9val b = 1.0val c = 1.1
assert(equal(a, b, c) == true) assert(equal(a, c, b) == false)

In the above, the order of the numbers matters, since the implementer of equal (ie. me) assumed that equivalence would be transitive (which it should be).
Cheers,Tom

On Fri, Oct 21, 2011 at 5:09 AM, Thomas Fehr <thomas.fehr@floetenbau.ch> wrote:

thanks. What are the practical limitations of non-transitivity?

- Thomas

Am 20.10.2011 22:28, schrieb Tom Switzer:

Equality with epsilons doesn't really work though as it isn't transitive. For geometrical computations, you can get away with quite a lot without resorting to floating point math (use rationals or homogenous coordinates).
On Thu, Oct 20, 2011 at 3:42 PM, Thomas Fehr <thomas.fehr@floetenbau.ch> wrote:

I'd love to see a compare with epsilon in Float (Double or Real or whatsoever) as in geometrical computations the Java '==' comparing bits is practically useless. I dare even to say that it is wrong, as it is leading to well hidden errors.

I would love to use Scala-Double with an overriden compare, but I doubt that this is possible

Thomas


Am 20.10.2011 20:26, schrieb Jason Zaugg:

On Thu, Oct 20, 2011 at 8:13 PM, Simon Ochsenreither <simon.ochsenreither@googlemail.com> wrote:

Let's hope some of those who proposed the Monoid/SemiGroup/... stuff chime in, too.

Here's some inspiration:
https://github.com/ekmett/scala-numerics/tree/master/src/main/scala/numeric
https://github.com/ekmett/scala-ad/tree/master/src/main/scala/ad
-jason

 

For floating point comparison, it's a better idea to just introduce a
separate op on float and double. I usually create isCloseTo(f:Float,
epsilon:Float):Boolean to use instead of equals.

For anyone who doesn't know why, here is a simple example:
val a = .3 + .3 + .3
val b = .9
val aEqualsB = (a == b) // this will actually be false

In this case, what is happening, is that floating point numbers
represent fractions as binary fractions, which are a sum of fractional
powers of 2 like 1/2, 1/4, 1/8, etc. Not all base 10 fractions are
representable exactly, that is why it is really an approximation.

It is safest to always think of floating point numbers as
"approximations", because most of the time they are.

James

On Thu, Oct 20, 2011 at 8:26 AM, Simon Ochsenreither <simon.ochsenreither@googlemail.com> wrote:

The third item was discussed to, but nobody stepped up with a proposed implementation.

I just put up my Rational implementation I use in my own projects on github: https://github.com/tixxit/q
It's a little better than the naive implementation, supports basic operations, but also implements ScalaNumber and ScalaNumericConversions and so it has conversions between all of Scala's number types (both ways) and supports the unified hashCode and equals (eg. 1 == Rational(1)).
It has some tests too (uses JUnit; it was one of the first things I wrote in Scala).

Looks interesting, although I would really prefer something like Rational[T], so people can choose which behaviour/accuracy they need.

One of the suggestions last time was to provide 2 classes, Rational and BigRational, which would match well with what we already have (eg. Int vs BigInt). Perhaps provide a type-parameterized trait for the boilerplate stuff, but do the more performance specific stuff in the specific implementations. I think we can safely treat Rational and BigRational as completely separate types, though, like Int and BigInt.

On Fri, Oct 21, 2011 at 2:28 PM, Simon Ochsenreither <simon.ochsenreither@googlemail.com> wrote:

Looks interesting, although I would really prefer something like Rational[T], so people can choose which behaviour/accuracy they need.

On Sat, Oct 22, 2011 at 2:57 AM, JamesJ wrote:
> For floating point comparison, it's a better idea to just introduce a
> separate op on float and double.  I usually create isCloseTo(f:Float,
> epsilon:Float):Boolean to use instead of equals.

Yes, this is of course the correct approach, as you well explained.

I do think Thomas was trying to say the same thing, ultimately. We
just got a bit side tracked on the question of overriding ==, which is
a non-starter.

So we all seem to agree on the need to standardize an Approximate
Equality operation for non-exact Fractional values (ie a hypothetical
sub-trait FloatingPoint extends Fractional, which doesnt exist but IMO
probably should) .

Now, there are two options for how it could work with abstracted
numbers ie Numeric & friends:

(a) The provider of the FloatingPoint instance implements an abstract
approxEq(t1:T, t2: T): Boolean operator. While this superficially
seems simple & easy, I fear its not "industrial grade". The users of
the numeric abstraction really needs some input into the tolerance
that the approxEq operator uses, since errors vary greatly between
algorithms & problem domains.

(b) There is a generic implementation of approxEq, parametrized on two
quantities: the accuracy of the underlying FloatingPoint
representation, and secondly, a user override-able tolerance value. I
advocate this option as superior. I discuss some details here:
[http://www.scala-lang.org/node/10871#comment-47348].

-Ben

+++

thanks
Thomas

Am 22.10.2011 04:14, schrieb Ben Hutchison:
> On Sat, Oct 22, 2011 at 2:57 AM, JamesJ wrote:
>> For floating point comparison, it's a better idea to just introduce a
>> separate op on float and double. I usually create isCloseTo(f:Float,
>> epsilon:Float):Boolean to use instead of equals.
> Yes, this is of course the correct approach, as you well explained.
>
> I do think Thomas was trying to say the same thing, ultimately. We
> just got a bit side tracked on the question of overriding ==, which is
> a non-starter.
>
> So we all seem to agree on the need to standardize an Approximate
> Equality operation for non-exact Fractional values (ie a hypothetical
> sub-trait FloatingPoint extends Fractional, which doesnt exist but IMO
> probably should) .
>
> Now, there are two options for how it could work with abstracted
> numbers ie Numeric& friends:
>
> (a) The provider of the FloatingPoint instance implements an abstract
> approxEq(t1:T, t2: T): Boolean operator. While this superficially
> seems simple& easy, I fear its not "industrial grade". The users of
> the numeric abstraction really needs some input into the tolerance
> that the approxEq operator uses, since errors vary greatly between
> algorithms& problem domains.
>
> (b) There is a generic implementation of approxEq, parametrized on two
> quantities: the accuracy of the underlying FloatingPoint
> representation, and secondly, a user override-able tolerance value. I
> advocate this option as superior. I discuss some details here:
> [http://www.scala-lang.org/node/10871#comment-47348].
>
> -Ben
>

On Thu, Oct 20, 2011 at 11:26 PM, Simon Ochsenreither
wrote:
> From time to time people (including me) complain about the brokenness of the
> numerical stuff shipped with Scala.
>
> The complaints usually include
>
> Numeric is broken and slow

Slow, yes. but broken.. No. Numeric is not broken. Not more than
java.util.List could be called broken for boxing its Ints.

Numeric is modelled on Haskell's Num typeclass, which while imperfect,
sees pretty widespread use & acceptance. Over discussions spanning
several years, I heard complaints about
1. Numeric's handling of division
2. The way that certain implicit conversions between number types are
not supported by Numeric
3. That the code using Numeric is verbose
4. Most often, that it causes allocation of too many temporary objects.

1 & 2 are explicit, defensible design choices. 3 is largely fixed. 4
is being worked on.

"X is broken" memes seem to replicate very easily on the net. That's
why Im trying to kill this one off explicitly.

But Numeric & friends can and should be improved further.

-Ben

On Thu, Oct 20, 2011 at 11:26 PM, Simon Ochsenreither
wrote:
> We need a better abstracted numerical hierarchy with things like Groups,
> SemiGroups, ...

First half of above sentence: fully agree. On /how/ to improve the
hierarchy: as I argued in an earlier thread
[http://www.scala-lang.org/node/10871#comment-47178], a crucial early
step to a "better abstracted" Numeric is to split its operations up
into finer grained sets. Then, clients of Numeric, like the sum and
product methods on TraversableOnce, can couple against only those
Numeric operations they need to get their job done.

In an effort to match word and deed, I've been working slowly away at
splitting Numeric, introducing Additive, Subtractive and
Multiplicative supertraits for Numeric. The timing of your post
catches this effort in-progress, but I've pushed this compilable
snapshot commit out, in the interest of putting up a straw man
proposal. I'd be interested to get feedback:

https://github.com/benhutchison/scala/commit/e7166f

An ascii art hierarchy shows where the proposed traits sit. Scala
collections now couple against Additive and Multiplicative.

Additive Multiplicative
| Ordered |
| | |
Subtractive |
| |
Numeric

This design was partly informed by the following Haskell works
[http://www.haskell.org/haskellwiki/Numeric_Prelude] and
[http://repetae.net/recent/out/classalias.html].

There is rarely one inheritance hierarchy to rule them all, that can
meet everyone's needs. For example, does SemiGroup[Int] do Sum or
Product [ http://www.scala-lang.org/node/10871#comment-47426]? That
makes me cautious, although not opposed, to retrofit "things like
Groups, SemiGroups" as super traits of Numeric abstractions in the
core...

Is it sufficient to have a numeric operator viewable as eg a Group via
implicit conversion? That's the road Scalaz takes, with apparent
success.

I know there's a performance penalty ATM for implicit conversions, but
that's likely to dwindle away over the expected life of such a Numeric
library, given optimisation work underway. The nice thing about
implicit conversions is that its "opt-in", supports
plurality/diversity of abstractions, and is more back-compatible.

> The standard library lacks classes for Complex numbers or Fractions

+1. They'd be useful.

-Ben

On Sat, Oct 22, 2011 at 11:33 PM, Ben Hutchison <brhutchison@gmail.com> wrote:

On Thu, Oct 20, 2011 at 11:26 PM, Simon Ochsenreither
<simon.ochsenreither@googlemail.com> wrote:
>
> The complaints usually include
>
> Numeric is broken and slow

Slow, yes. but broken.. No. Numeric is not broken. Not more than
java.util.List<Integer> could be called broken for boxing its Ints.

It is broken conceptually because there is no built in support for even _explicit_ conversions between number types.  It's not just that one might want Numeric[Short] to be automatically converted to Numeric[Int]; it's that if you have Numeric[T] and Numeric[U], there is no way to do anything with the two of them.

This is why frameworks that abstract over number type usually have a class that represents operators that is parameterized on two types.  In Scala we could use an implicit instead (either conversion or an implicit operator).  Without a regular way to do this, the Numeric abstraction cripples your ability to do mathematics, which is probably not intended or desired.  I have yet to be able to use Numeric for anything serious (despite writing reams of mathematical code) because of this limitation, though I admit with the boxing issues I have not been motivated to try very hard because much of the code would be too slow anyway.  In any case, in the sense that Numeric does not in practice achieve what in principle it should be good for, it is broken.  In the sense that it is not buggy, it is not broken.

Anyway, whether we call it broken or too limited, I'd very much support improvements.

  --Rex

After thinking a bit longer about it, my opinion is that adding a divison operator to Numeric would probably solve most of the problems people currently have in real world usage.

While the whole abstraction looks great on the surface, I don't think it works in practice.

Things like

def sum[A1 >: A](implicit addition: Additive[A1]): A1

are imho a great example how good intentions just don't work in practice and especially in the face of inheritance, because restrictions on the parent class prevent any meaningful refinement of algorithms in subclasses.

The Range#sum example is a poster child for this.

Maybe I'm a bit too negative about it, but I don't see a real solution apart from making Numeric more useful.

Thanks and bye,

Simon

Hi Rex,

I totally agree with what you've written.

I have written a different version of Numeric which uses
specialization, has better support for conversions, infix operators,
etc. Profiling has shown that with this code it's possible to write
Numeric code that is basically as fast as direct code (in some cases
there's a 10-15% slow down). This is in contrast to the current Numeric
code which I observe 200-1200% slow down.

You can see my code here: https://github.com/azavea/numeric

I tried to very explicit about what I've done in the README, as well as
keeping track of possible future work in the TODO.

I'm still looking for feedback from people on whether this approach
solves their problem, is something they'd use, etc. I'd love to get
opinion on what I've done--suggestions, criticism, praise and/or other
comments.

Thanks,

On Mon, Oct 24, 2011 at 3:16 AM, Rex Kerr wrote:
> [Numeric] is broken conceptually because there is no built in support for even
> _explicit_ conversions between number types.

The set of types for which Numeric can be defined is open by design.
To use your examples type T and U, its the developer of the app, your
"client code" if you will, that knows what T and U are via concrete
instances. But the Numeric instance for T doesn't know about U, nor
the reverse. Nor can they, unless the set of all Numeric instances is
some closed, finite set.

> It's not just that one might
> want Numeric[Short] to be automatically converted to Numeric[Int]; it's that
> if you have Numeric[T] and Numeric[U], there is no way to do anything with
> the two of them.

If your app has a way to turn Ts into Us, or the reverse, you are able
to do so. For example, if T=Int, and U=Short, you can convert T to U
via "myInt.toShort". Numeric doesn't need to be involved, nor can it
be. It know how mathematically operate over its target representation.

All thats possible is conversion via some well known intermediate type
(eg Int, Double). Is the essence of your complaint that you want more
fromX(value: X) coercion methods on Numeric or Fractional, eg
fromDouble(), fromLong(), fromFloat() ?

> This is why frameworks that abstract over number type usually have a class
> that represents operators that is parameterized on two types.

Do you have a link? I'd be interested to know what you're referring to.

> Without a regular way to do this, the Numeric abstraction cripples your
> ability to do mathematics, which is probably not intended or desired.

If Numeric is so crippled, how does the Haskell community get by using
something that is very similar, and from which Numeric was inspired?
Im trying to understand what precise difference leads people in the
Scala community to claim its broken, yet Num is fairly accepted in
Haskell..? [http://www.haskell.org/tutorial/numbers.html]

-Ben

On Mon, Oct 24, 2011 at 9:20 AM, Erik Osheim wrote:
> I have written a different version of Numeric which uses
> specialization, has better support for conversions, infix operators,
> etc. Profiling has shown that with this code it's possible to write
> Numeric code that is basically as fast as direct code (in some cases
> there's a 10-15% slow down). This is in contrast to the current Numeric
> code which I observe 200-1200% slow down.

> I'm still looking for feedback from people on whether this approach
> solves their problem, is something they'd use, etc. I'd love to get
> opinion on what I've done--suggestions, criticism, praise and/or other
> comments.

Erik,

In general, looks good. I think you've already received some fairly
positive feedback from a couple of core committers (Paul and Josh
IIRC) so I reckon your proposal has decent standing. Some queries:

* I like the model for conversion between types, but is it actually
related to being a number, specifically? Ie, any two types T and U
might or might not be convertible, whether numbers, dates, shapes or
insurance quotes. Couldn't it be a separable part of the library? For
example, type T is Numeric and ConvertibleTo[U], independently..?

* Where does Fractional sit in this?

* If the operations were to be split into smaler chunks, as per my
earlier proposal (Additive, Multiplicative etc), would there be any
incompatibility with your speedups, assuming appropriate
specialization? I can't see any at first glance.

-Ben

On Mon, Oct 24, 2011 at 01:18:49PM +1100, Ben Hutchison wrote:
> * I like the model for conversion between types, but is it actually
> related to being a number, specifically? Ie, any two types T and U
> might or might not be convertible, whether numbers, dates, shapes or
> insurance quotes. Couldn't it be a separable part of the library? For
> example, type T is Numeric and ConvertibleTo[U], independently..?

Yes, you could probably factor this out to be something more general,
but I'm not sure how well it would work.

Initially I had hoped to do something more flexible, e.g.
ConvertableFromAToB[A, B] or something, so that users could extend the
possible conversions (and so that things like toLong() wouldn't be
baked into the API). Unfortunately I wasn't able to get this working.
As such, ConvertableFrom[A] and ConvertableTo[A] "bake in" the types
you can convert to/from respectively (via the API) which limits how
flexible these type classes can be.

The big win of the design I chose was that you can convert between two
independent Numeric types (T and U) via toType or fromType.

As far as I can tell the "type class pattern" in Scala (as currently
implemented) wants you to either bake the type class instances (e.g.
IntIsNumeric) into the member type (e.g. Int) or the type class itself
(e.g. Numeric). This limits how extensible things like Numeric can be
in practice, or at least makes user-defined type class instances less
convenient to use.

> * Where does Fractional sit in this?

My proposal would be to have Fractional and Integral sit alongside
Numeric, rather than having each extend Numeric. I understand the
arguments for being able to limit your numeric types to one or the
other, but I do think there is a class of users who want something to
be a number, regardless of whether it's integral or fractional (in
particular, users who are coming from Scheme, Python, etc are used to
doing this).

> * If the operations were to be split into smaler chunks, as per my
> earlier proposal (Additive, Multiplicative etc), would there be any
> incompatibility with your speedups, assuming appropriate
> specialization? I can't see any at first glance.

The specialization strategy should work just as well with more small
type classes (Additive, Multiplicative, etc). I haven't tested this
design myself but I don't see any reason why it wouldn't work.

On Sun, Oct 23, 2011 at 9:58 PM, Ben Hutchison <brhutchison@gmail.com> wrote:

But the Numeric instance for T doesn't know about U, nor
the reverse. Nor can they, unless the set of all Numeric instances is
some closed, finite set.

Exactly.  That's the design flaw.  There's no mechanism for you to provide this information.
 

If your app has a way to turn Ts into Us, or the reverse, you are able
to do so. For example, if T=Int, and U=Short, you can convert T to U
via "myInt.toShort". Numeric doesn't need to be involved, nor can it
be. It know how mathematically operate over its target representation.

Yup.  Exactly.  x.toShort is not generic code.  Design flaw.
 

All thats possible is conversion via some well known intermediate type
(eg Int, Double). Is the essence of your complaint that you want more
fromX(value: X) coercion methods on Numeric or Fractional, eg
fromDouble(), fromLong(), fromFloat() ?

Not at all.  I want to look up a T to U conversion at the usage-site for the method.
 

> This is why frameworks that abstract over number type usually have a class
> that represents operators that is parameterized on two types.

Do you have a link? I'd be interested to know what you're referring to.

I had remembered Colt and EJML doing this, but they don't.  (They do provide operators separately from the classes, however.)  I now am no longer sure what I was remembering--sorry.  I have seen it at least twice before.
 

> Without a regular way to do this, the Numeric abstraction cripples your
> ability to do mathematics, which is probably not intended or desired.

If Numeric is so crippled, how does the Haskell community get by using
something that is very similar, and from which Numeric was inspired?

I don't know.  Maybe people don't use Haskell for high(ish) performance numeric work where sometimes it's essential to use different formats for whatever reason (size, performance, precision, etc.)?  It's weird enough to try using Java instead of C++.  Or maybe the Haskell type system allows some other way to solve the problem.  (Actually, I think so at least in part, from what I've seen, but I'm not familiar enough with Haskell to be certain.)

  --Rex

Erik,

This looks promising.  I tried something similar but ran into specialization bugs; it sounds like you've hit on a strategy that is successful!  I look forward to actually trying it; it's a bit hard to tell from a glance whether it will actually solve the problems I had.  But, anyway, IMO the Scala library numeric should be refactored to provide something like your version.

  --Rex

On Sun, Oct 23, 2011 at 6:20 PM, Erik Osheim <erik@plastic-idolatry.com> wrote:

Hi Rex,

I totally agree with what you've written.

I have written a different version of Numeric which uses
specialization, has better support for conversions, infix operators,
etc. Profiling has shown that with this code it's possible to write
Numeric code that is basically as fast as direct code (in some cases
there's a 10-15% slow down). This is in contrast to the current Numeric
code which I observe 200-1200% slow down.

You can see my code here: https://github.com/azavea/numeric

I tried to very explicit about what I've done in the README, as well as
keeping track of possible future work in the TODO.

I'm still looking for feedback from people on whether this approach
solves their problem, is something they'd use, etc. I'd love to get
opinion on what I've done--suggestions, criticism, praise and/or other
comments.

Thanks,

Hi everyone,

this is not directly related to the SIP, but I'd like to shamelessly
take the opportunity to point those Scala programmers interested in
precise numerical computations to the following work:

http://lara.epfl.ch/w/smartfloat

This is a library that allows Scala programmers to quickly identify
potential rounding errors arising from the use of floating-point
arithmetic as a mean for representing real numbers: you more or less
replace your "Double" declarations by "AffineFloat" or "SmartFloat"
definitions, and you get, in addition to the standard computation, a
sound approximation of the round-off error. (AffineFloats compute the
round-off error. SmartFloats can additionally track the precision loss
over a *range* of inputs, as opposed to a single input value.)

PS

On Oct 21, 5:57 pm, JamesJ wrote:
> For floating point comparison, it's a better idea to just introduce a
> separate op on float and double.  I usually create isCloseTo(f:Float,
> epsilon:Float):Boolean to use instead of equals.
>
> For anyone who doesn't know why, here is a simple example:
> val a = .3 + .3 + .3
> val b = .9
> val aEqualsB = (a == b) // this will actually be false
>
> In this case, what is happening, is that floating point numbers
> represent fractions as binary fractions, which are a sum of fractional
> powers of 2 like 1/2, 1/4, 1/8, etc.  Not all base 10 fractions are
> representable exactly, that is why it is really an approximation.
>
> It is safest to always think of floating point numbers as
> "approximations", because most of the time they are.
>
> James

While I think to[Type] is a great idea, I'm not sure how it fits into the library, consistency-wise.

Either we would need to add these kinds of conversions everywhere, or at least supply the "standard" ones (toLong, toInt, ...) in addition to the to[Type] ones...

On Thursday, October 20, 2011 2:26:16 PM UTC+2, Simon Ochsenreither wrote:

Hi everyone!

From time to time people (including me) complain about the brokenness of the numerical stuff shipped with Scala.

The complaints usually include

• Numeric is broken and slow
• We need a better abstracted numerical hierarchy with things like Groups, SemiGroups, ...
• The standard library lacks classes for Complex numbers or Fractions
  

Maybe also Decimal? 

For the first part, Erik Osheim already sat down and did most of the work (and with the proposals about inlining implicits a complete solution looks achievable). (Thanks Erik!)

The second item was lengthly discussed on the mailing list, but I'm unsure if a conclusion was reached.

The third item was discussed to, but nobody stepped up with a proposed implementation.

Is there enough interest to put a SIP together, so we can finally move things forward?

I look forward hearing your opinion regarding that matter.

Thanks!


Simon

On Mon, Oct 24, 2011 at 7:18 PM, Ittay Dror wrote:
> On Thursday, October 20, 2011 2:26:16 PM UTC+2, Simon Ochsenreither wrote:
>> The standard library lacks classes for Complex numbers or Fractions
>
> Maybe also Decimal?

If you are aware of BigDecimal, please detail what you wish to be
added/supported relative to it.

http://download.oracle.com/javase/7/docs/api/java/math/BigDecimal.html

-Ben

On Mon, Oct 24, 2011 at 1:29 PM, Erik Osheim wrote:
> Initially I had hoped to do something more flexible, e.g.
> ConvertableFromAToB[A, B] or something, so that users could extend the
> possible conversions (and so that things like toLong() wouldn't be
> baked into the API). Unfortunately I wasn't able to get this working.
> As such, ConvertableFrom[A] and ConvertableTo[A] "bake in" the types
> you can convert to/from respectively (via the API) which limits how
> flexible these type classes can be.
>
> The big win of the design I chose was that you can convert between two
> independent Numeric types (T and U) via toType or fromType.

On more careful consideration, I think the limited extensibility of
the proposed ConvertableFrom and ConvertableTo design is a significant
problem. The assumption that there are a fixed set of Numeric
instances (being the current common JVM types) will not age well nor
prove particularly portable.

>
> As far as I can tell the "type class pattern" in Scala (as currently
> implemented) wants you to either bake the type class instances (e.g.
> IntIsNumeric) into the member type (e.g. Int) or the type class itself
> (e.g. Numeric). This limits how extensible things like Numeric can be
> in practice, or at least makes user-defined type class instances less
> convenient to use.

Not so IMO. You can define a typeclass instance in your application at
the top level as a val. Instances in scope take precedence over
instances looked up from companion objects. Accordingly, the in-scope
instance will bind preferentially to the implicit param in method
calls, and continue to bind all the way down the call graph.

>
>> * Where does Fractional sit in this?
>
> My proposal would be to have Fractional and Integral sit alongside
> Numeric, rather than having each extend Numeric.

Hmmmm, how would "sit alongside" work:
- Does what is currently called Fractional essentially become
Numeric, or is there a difference? If so, what is it?
- Where are the Integrals quot and rem functions put? Can you do
modulus on any Numeric?
- Back-compatiblity?

-Ben

On Mon, Oct 24, 2011 at 4:56 PM, Philippe Suter
wrote:
> I'd like to shamelessly
> take the opportunity to point those Scala programmers interested in
> precise numerical computations to the following work:
>
> http://lara.epfl.ch/w/smartfloat
>

I reviewed your work just now. It looks useful - Interval arithmetic
is cool. Its also a good reminder of what Numeric & friends can offer,
if done well. To quote from your tech report:

"All that is needed to put our library into action are two import
statements ... and the replacement of Double types by SmartFloat. ...
In addition to this, our library supports a subset of the scala.math
library functions, which we consider the most useful:  log; expr;
pow; cos; sin; tan acos; asin; atan  abs; max; min"

On a large code base the complete replacement of Double with
SmartFloat will likely be prohibitively difficult. Further, each
numeric representation ends up having to code to same set of building
block functions over and over; at least some of this effort is
avoidable.

Have you considered/investigated providing a Numeric instance for smartfloat?

-Ben

Hi Ben,

That's a very good point, and I'll bring it to the attention of the
authors. (I'm not one of them, but they don't usually read this
mailing list.)

Thank you for the interest and the feedback!
PS

On Oct 25, 3:37 am, Ben Hutchison wrote:
> On Mon, Oct 24, 2011 at 4:56 PM, Philippe Suter
>
> wrote:
> > I'd like to shamelessly
> > take the opportunity to point those Scala programmers interested in
> > precise numerical computations to the following work:
>
> >http://lara.epfl.ch/w/smartfloat
>
> I reviewed your work just now. It looks useful - Interval arithmetic
> is cool. Its also a good reminder of what Numeric & friends can offer,
> if done well. To quote from your tech report:
>
> "All that is needed to put our library into action are two import
> statements ... and the replacement of Double types by SmartFloat. ...
> In addition to this, our library supports a subset of the scala.math
> library functions, which we consider the most useful:   log; expr;
> pow; cos; sin; tan acos; asin; atan   abs; max; min"
>
> On a large code base the complete replacement of Double with
> SmartFloat will likely be prohibitively difficult. Further, each
> numeric representation ends up having to code to same set of building
> block functions over and over; at least some of this effort is
> avoidable.
>
> Have you considered/investigated providing a Numeric instance for smartfloat?
>
> -Ben