SIP-15: could this help e.g. NumericOps[T]?

[Erik Osheim]

So, I posed a comment on the SIP itself but then decided that maybe an
email would be a better way to kick off some discussion.

As I read the proposal, it seems like this proposal would not help type
classes like Ordering or Numeric. Specifically:

1. C must have exactly one parameter, which is marked with val
and which has public accessibility. The type of that parameter
(e.g. U above) is called the underlying type of C. That type
may not be a type parameter of C (but it can be a class or trait
that has type parameters of C as arguments.)

In most cases, the kind of class I would like to inline looks something
like this:

class NumericOps[T](lhs:T)(implicit n:Numeric[T]) {
def +(rhs:T) = n.plus(lhs, rhs)
}

Given that the "underlying type" of lhs is T (a type parameter of C)
this is not allowed to be a value class, right?

I haven't fully internalized the whole "value class" idea, and maybe
type-class-based-enrichment is not a good use-case for them, but this
is a huge problem in my own work and is something I was hoping an
implicit class SIP could solve.

Am I misunderstanding? Is there some other method that will work
instead? Is there another SIP in the works? Is there something else I
should be doing?

-- Erik

[Daniel Sobral]

This kind of pattern you mention is essentially used in one situation:

def f[t: Numeric](a: T, b: T): T = ...

Now, what value classes do is avoid boxing. Instead of using a
reference to a Double, a Double is used directly. The problem is that
only works as long as the class knows exactly what it is doing!
Consider a simple example:

trait Squares[T] { def squared: T; def +(b: T): T }
class MyInt(n: Int) extens AnyVal with Squares[Int] { def squared = n
* n; def +(b: MyInt) = n + b.n }
class MyDouble(n: Double) extends AnyVal with Squares[Double] { def
squared = n * n; def +(b: MyInt) = n + b.n }

def hypothenusaSquared[T <: Squares[T]](a: T, b: T) = a.squared + b.squared

I'm not sure this typechecks because of the plus operator, but,
anyway, the bytecode of adding Int is different than the bytecode of
adding Double, so hypothenusaSquared *cannot* inline the parameters.
It *must* receive a class and call a method on that class, because
only classes are polymorphic. Primitives are not polymorphic.

And that restriction applies to pretty much anything you'd use Numeric
for. There's no way to inline the operations, you'll always have to
call a method on an object.

--
Daniel C. Sobral

I travel to the future all the time.

[Erik Osheim]

Hi Daniel,

On Tue, Feb 07, 2012 at 07:26:39PM -0200, Daniel Sobral wrote:
> trait Squares[T] { def squared: T; def +(b: T): T }
> class MyInt(n: Int) extens AnyVal with Squares[Int] { def squared = n
> * n; def +(b: MyInt) = n + b.n }
> class MyDouble(n: Double) extends AnyVal with Squares[Double] { def
> squared = n * n; def +(b: MyInt) = n + b.n }
>
> def hypothenusaSquared[T <: Squares[T]](a: T, b: T) = a.squared + b.squared
>
> I'm not sure this typechecks because of the plus operator, but,
> anyway, the bytecode of adding Int is different than the bytecode of
> adding Double, so hypothenusaSquared *cannot* inline the parameters.
> It *must* receive a class and call a method on that class, because
> only classes are polymorphic. Primitives are not polymorphic.

I think you misunderstood what I was asking. It's currently impossible
to implement your Squares method, and in fact the only way to get
ad-hoc polymorphism like this is the strategy Numeric uses, which is
very different.

I'll try to sketch a more complete example of what I'm doing, and how I
think it could benefit from the value class strategy, if value classes
were allowed to use type parameters. I'll also try to show why I don't
see a satisfactory reason why it wouldn't work.

Here's some code:

// this is all just set up
trait HasPlus[A] {
def plus(x:A, y:A):A
}

trait IntHasPlus extends HasPlus[Int] {
def plus(x:Int, y:Int) = x + y
}

object HasPlus {
implicit object IntHasPlus extends IntHasPlus
}

class HasPlusOps[A](val lhs:A)(implicit ev:HasPlus[A]) {
def +(rhs:A) = ev.plus(lhs, rhs)
}

object Implicits {
implicit def infixPlusOps[A:HasPlus](lhs:A) = new HasPlusOps(lhs)
}

import Implicits._

// this is the code the user writes
def double1[A:HasPlus](a:A) = a + a

// this is double1 without the sugar
def double2[A](a:A)(ev:HasPlus[A]) = infixPlusOps(a)(ev).+(a)

In this case I am talking about "HasPlusOps" being the value class to e
inlined. I'm going to work through the steps (1-5) described in the
SIP, as I understand them.

1. It should be clear that it would be possible to define an extractor
method for HasPlusOps#plus; it would be:

class HasPlusOps[A](val lhs:A)(implicit ev:HasPlus[A]) {
def +(rhs:A) = HasPlusOps.extension$+(this, rhs)
}
object HasPlusOps {
...
def extension$+[A]($this:HasPlusOps[A], rhs:A)(ev:HasPlus[A]) = ev.plus($this.lhs, rhs)
}

2. Then we would reroute the calls to HasPlusOps#+ to the companion:

def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(infixPlusOps(a)(ev), a)

3. We then follow the erasure step which changes the infixPlusOps method:

object Implicits {
implicit def infixPlusOps[A:HasPlus](lhs:A):HasPlusOps$unboxed = new HasPlusOps(lhs)
}

After that, we do the good bit (peephole optimization), where we
rewrite away our use of the wrapper class:

object Implicits {
implicits def infixPlusOps[A:HasPlus](lhs:A):HasPlusOps$unboxed = lhs
}

4. Finally, we clean up the "unboxed" type:

object Implicits {
implicits def infixPlusOps[A:HasPlus](lhs:A):A = lhs
}

As you can see, we're left with:

object Implicits {
implicits def infixPlusOps[A:HasPlus](lhs:A):A = lhs
}

def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(infixPlusOps(a)(ev), a)

Since infixPlusOps now just returns "lhs", this translates to:

def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(a, a)

This is how type classes could avoid create a new HasPlusOps instance
every time enrichment is used to add + to instances of A. Hopefully I
have demonstrated why I am not persuaded by your example.

I'm sure there's a reason that type parameters (both specialized and
unspecialized) are not allowed to be the "underlying type" of a value
class, but it certainly isn't stated, and does block things like this,
which would otherwise seem to work as written in the SIP.

Sorry if I am being glib, but it would be nice to have an explanation
of why this use case is being excluded.

Thanks,

-- Erik

[Erik Osheim]

On Tue, Feb 07, 2012 at 09:30:11PM -0500, Erik Osheim wrote:
> // this is double1 without the sugar
> def double2[A](a:A)(ev:HasPlus[A]) = infixPlusOps(a)(ev).+(a)

Sorry, I meant:

def double2[A](a:A)(implicit ev:HasPlus[A]) = infixPlusOps(a)(ev).+(a)

Every time I write a definition of double2 please imagine that
"implicit" is before "ev".

-- Erik

[Erik Osheim]

Sorry, one other error. We'd have to reroute the implicit evidence
parameter also, so there'd be these changes:

> class HasPlusOps[A](val lhs:A)(implicit ev:HasPlus[A]) {
> def +(rhs:A) = HasPlusOps.extension$+(this, rhs)
> }

class HasPlusOps[A](val lhs:A)(implicit ev:HasPlus[A]) {

def +(rhs:A) = HasPlusOps.extension$+(this, rhs)(ev)

}

> def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(infixPlusOps(a)(ev), a)

def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(infixPlusOps(a)(ev), a)(ev)

> def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(infixPlusOps(a)(ev), a)

def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(infixPlusOps(a)(ev), a)(ev)

> def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(a, a)

def double2[A](a:A)(ev:HasPlus[A]) = HasPlusOps.extension$+(a, a)(ev)

Apologies again. It's hard to write these tree transformations freehand
without messing up, especially while cooking dinner!

-- Erik

[Tom Switzer]

The Numeric problem may be solved by nested value classes. Is the biggest problem with nested value classes that you can't see $outer if an instance escapes the scope it was created in? Or something else?

All instances of the value class are replaced by the underlying type. What if nested value classes require an implicit instances of the outer class. In this case, we can expand the methods of the value class as usual, but requiring an extra $outer parameter. The value of $outer can be the implicit instance of the outer class. This would let us write Numeric similar to how it is now,

trait Numeric[A] {

  def plus(a: A, b: A): A

  class Ops(a: A) extends AnyVal {

    def +(b: A): A = plus(a, b)

  }

}

Then perform the optimize this:

def add[A: Numeric](a: A, b: B): A = a + b

to:

def add[A](a: A, b: B)(implicit $outer: Numeric[A]): A = {

  Numeric$Ops$.extension$+($outer, a, b)

}

[Tom Switzer]

Or how about allowing implicit paramters, and map those to extra arguments:

class NumericOps[A](a: A)(implicit num: Numeric[A]) extends AnyVal {

   def +(b: A): A = num.plus(a, b)

}

maps to

object NumericOps {

  def extension$+(a: A, b: B)(implicit num: Numeric[A]) = num.plus(a, b)

}

Then, using the value class requires that the compiler can find the implicits.

[Erik Osheim]

On Tue, Feb 07, 2012 at 09:25:11PM -0800, Tom Switzer wrote:
> The Numeric problem may be solved by nested value classes. Is the biggest
> problem with nested value classes that you can't see $outer if an instance
> escapes the scope it was created in? Or something else?

The biggest problem with them is that they don't specialize properly.

I've run benchmarks which show that they are slower (2-3 times slower)
than non-nested classes in 2.9.1:

[info] length benchmark ns linear runtime
[info] 100 Nested 1993 =
[info] 100 External 513 =
[info] 1000 Nested 21941 =
[info] 1000 External 8482 =
[info] 10000 Nested 214572 ===
[info] 10000 External 76585 =
[info] 100000 Nested 2130726 ==============================
[info] 100000 External 835260 ===========

I've seen similar results from git master. The benchmarking code I used
is available at https://github.com/non/spec-benchmark.

If a (specialized) outer class could have inner classes which were also
correctly specialized then this wouldn't be such a problem. But the
signals I've picked up around specialization indicate that it's not
safe to assume that the feature will be expanded to included cases it
doesn't currently support.

There are already some open specialization bugs reported. I'll
summarize some known-bad cases:

class Foo[@spec A](...){ class Bar(...){...} }
class Foo[@spec A](...){ def bar[@spec B] = ... }
class Foo[@spec A](...){ class Bar[@spec B](...){...} }

I think the general rule seems to be that anytime you have nested
specialization occurring (whether with classes or methods) you can
assume that you aren't going to like the outcome.

This is why I have avoided inner classes in my numeric redesign, and
why I would like support for type-parameterized value classes if
possible.

-- Erik

[Pavel Pavlov]

Hi Erik,

Well, to clarify all this, let's eliminate all the Scala syntax sugar and convert your sample into simple Java-like Scala subset:

class NumericOps1[T](lhs: T)(implicit n: Numeric[T]) {

  def +(rhs: T) = n.plus(lhs, rhs)
}

becomes then:

class NumericOps1[T](_lhs: T, _n: Numeric[T]) {
  val lhs: T = _lhs
  val n: Numeric[T] = _n
  def +(rhs: T) = this.n.plus(this.lhs, rhs)
}

As you see there the class have two fields and this is necessary because both of them are used from `+` method.

Making such classes zero-cost is a way trcky than classes with only one field due to many reasons:
1) erasure logic becomes more complicated
2) non-trivial mapping to the bytecode causes numerous problems with methods overloading, java interop etc.

Nested classes do not help in any way as you need to hold the reference to outer class (well, we should find somewhere our Numeric[T] object, right?):

trait Numeric[T] {
  class Ops2(lhs: T) {
    def +(rhs: T): T = plus(lhs, rhs)
  }
}

is desugared to:

class Ops2[T](_lhs: T, _$outer: Numeric[T]) {
  val lhs: T = _lhs
  val $outer: Numeric[T] = _$outer
  def +(rhs: T) = this.$outer.plus(this.lhs, rhs);
}

Still two fields in `Ops` class.


Well, now let's try this one:

class NumericOps3[T](lhs: T) {
  def +(rhs: T)(implicit n: Numeric[T]) = n.plus(lhs, rhs)
}

Gotcha! Only one field remains:

class NumericOps3[T](_lhs: T) {
  val lhs: T = _lhs
  def +(rhs: T, n: Numeric[T]) = n.plus(this.lhs, rhs);
}

So, `NumericOps3` can be converted to value class, which resolves your issue.

Regards,
Pavel.

[Erik Osheim]

Hi Pavel,

On Wed, Feb 08, 2012 at 08:39:50AM -0800, Pavel Pavlov wrote:
> Making such classes zero-cost is a way trcky than classes with only one
> field due to many reasons:
> 1) erasure logic becomes more complicated
> 2) non-trivial mapping to the bytecode causes numerous problems with
> methods overloading, java interop etc.

I have been thinking about this as tree transformations, which didn't
seem so bad, but I will trust you that it's harder than I thought. :)

> class NumericOps3[T](_lhs: T) {
> val lhs: T = _lhs
> def +(rhs: T, n: Numeric[T]) = n.plus(this.lhs, rhs);
> }
>
> So, `NumericOps3` can be converted to value class, which resolves your
> issue.

Yes, although the spec says that the underlying type is not allowed to
be a type parameter. Is that your understanding also? I wonder if the
SIP-15 authors could chime in on this?

If the spec does permit solution #3 then I think that would be
reasonable.

Thanks,

-- Erik

[Pavel Pavlov]

среда, 8 февраля 2012 г. 23:50:54 UTC+7 пользователь Erik Osheim написал:

>   val lhs: T = _lhs
>   def +(rhs: T, n: Numeric[T]) = n.plus(this.lhs, rhs);
> }
>
> So, `NumericOps3` can be converted to value class, which resolves your
> issue.

> class NumericOps3[T](_lhs: T) {

Yes, although the spec says that the underlying type is not allowed to
be a type parameter.

My fault.

Really, this can be converted into bytecode only with boxing, which kills all the sense.

`class NumericOps[T <: AnyRef]` can be converted without boxing, but that's definitely not what you want.

In principle, specialization on T can help there, but I doubt it will be implemented in the first version of value classes.

 

Is that your understanding also? I wonder if the
SIP-15 authors could chime in on this?

As I'm not a member of EPFL/Typesafe team I cannot in any way influence on what, when and how will be implemented.
I just have long experience in JVM internals/implementation and understand (I hope) the goals of the proposal.
So I can imagine what's possible and what's not and thus in some extent predict what and how may or unlikely to be implemented.
All what I'm saying is solely my personal opinion based on my personal understanding of the things.

Regards,
Pavel.

[martin odersky]

On Wed, Feb 8, 2012 at 6:18 PM, Pavel Pavlov <pavel.e...@gmail.com> wrote:
>
>
> среда, 8 февраля 2012 г. 23:50:54 UTC+7 пользователь Erik Osheim написал:
>>
>>
>> >   val lhs: T = _lhs
>> >   def +(rhs: T, n: Numeric[T]) = n.plus(this.lhs, rhs);
>> > }
>> >
>> > So, `NumericOps3` can be converted to value class, which resolves your
>> > issue.
>>
>> > class NumericOps3[T](_lhs: T) {
>>
>> Yes, although the spec says that the underlying type is not allowed to
>> be a type parameter.
>
>
> My fault.
>
> Really, this can be converted into bytecode only with boxing, which kills
> all the sense.
>
> `class NumericOps[T <: AnyRef]` can be converted without boxing, but that's
> definitely not what you want.
>
> In principle, specialization on T can help there, but I doubt it will be
> implemented in the first version of value classes.
>

Pavel sums it up correctly. We could probably admit generic inline
classes (not 100% sure yet without having an implementation). But that
would not avoid boxing of primitive type arguments. Specialization
might help, but it's premature to speculate about this; we have to
implement value classes first, and also fix a bunch of other
restrictions for specialization. Once we have done that we can revisit
the issue.

Cheers

-- Martin

[Erik Osheim]

On Wed, Feb 08, 2012 at 06:31:56PM +0100, martin odersky wrote:
> Pavel sums it up correctly. We could probably admit generic inline
> classes (not 100% sure yet without having an implementation). But that
> would not avoid boxing of primitive type arguments. Specialization
> might help, but it's premature to speculate about this; we have to
> implement value classes first, and also fix a bunch of other
> restrictions for specialization. Once we have done that we can revisit
> the issue.

Thanks to Pavel and Martin for explaining this.

I would be happy to try to help fix some of the current restrictions
around specialization, since it's a feature I'm currently leaning on
pretty heavily.

-- Erik

[Pavel Pavlov]

Hi Martin,

9 февраля 2012 г. 0:31 пользователь martin odersky <martin....@epfl.ch> написал:

I think the code given by Erik is very common code pattern (without respect to primitive types) which can be found everywhere typeclass pattern is used (I will refer to it below as to "infix wrapper" pattern as its solely purpose is to add syntax sugar for infix methods to the typeclass interface). In some cases/environments/libraries its performance is even more sensitive than performance of "simple" rich wrapper pattern.

It's hard to reduce performance tax for such infix wrapper pattern with the "runtime-oriented" approaches as erasure-based inline/value class transformations. However, it can be easily done with AST rewritings which completely eliminate any traces of infix wrapper classes & their forwarder method at compile time. So I wonder if the macros can help there as well? My macro-fu is at very beginner level so I cannot definitely say that macros can help in that case, just trying to find the solution here.

Well, if we have:

trait Numeric[T] {

  def plus(x: T, y: T): T

}

implicit def n2ops[T](x: T)(implicit n:Numeric[T]) = new Ops(x)(n)

then we can define method `+` in class Ops as macro:

class Ops[T](x:T)(implicit n:Numeric[T]) {
  macro def +(y:T) = this match {
    case c"n2ops($x)($n)" => c"$n.plus($x, $y)"
    case _ => compileError("wrong use of infix wrapper pattern")
  }
}

Going further, we can generate such macro def forwarders by another macro, like this:

macro class InfixWrapper[T] = ...
trait Numeric[T] {

  def infix_+(x: T, y: T): T

}
type Ops = InfixWrapper[Numeric[T]]
implicit def n2ops[T](x: T)(implicit n:Numeric[T]) = new Ops(x)(n)

or like this:

macro class InfixWrapper[T] = ...
trait Numeric[T] {

  @infix("+") def plus(x: T, y: T): T

}
type Ops = InfixWrapper[Numeric[T]]
implicit def n2ops[T](x: T)(implicit n:Numeric[T]) = new Ops(x)(n)

If that is possible, we can define InfixWrapper once in the standard library.

May be even implicit def can be generated by the macro thus even more effectively removing infix wrapper definition boilerplate.

What do you think?

Cheers

 -- Martin

Regards,
Pavel

[martin odersky]

We'll hopefully have someone to pick up the specialization work soon.
Stay tuned...

Cheers

-- Martin

[martin odersky]

2012/2/8 Pavel Pavlov <pavel.e...@gmail.com>:

Macros can do almost anything, given enough effort. So, yes, this
might be an alternative. But first, we have to get a macro SIP and
then decide on whether it should go in.
I'm hopeful but let's take one step after another :-)

Cheers

-- Martin

[Paul Phillips]

On Wed, Feb 8, 2012 at 10:35 AM, Erik Osheim <er...@plastic-idolatry.com> wrote:
> I would be happy to try to help fix some of the current restrictions
> around specialization, since it's a feature I'm currently leaning on
> pretty heavily.

I don't know what martin has lined up, but don't let that slow you down, there are plenty of specialization bugs for all!

https://issues.scala-lang.org/secure/IssueNavigator.jspa?mode=hide&requestId=11008

[Erik Osheim]

On Wed, Feb 08, 2012 at 11:41:42AM -0800, Paul Phillips wrote:
> I don't know what martin has lined up, but don't let that slow you down,
> there are plenty of specialization bugs for all!
>
> https://issues.scala-lang.org/secure/IssueNavigator.jspa?mode=hide&requestId=11008

I hope to be sending some pull requests your way; I'm still coming up
to speed on the compiler generally and the specialization
implementation in particular.

Thanks for your words of encouragement.

[Paul Phillips]

On Wed, Feb 8, 2012 at 12:07 PM, Erik Osheim <er...@plastic-idolatry.com> wrote:

Thanks for your words of encouragement.

That you would interpret "there are plenty of bugs for all" as encouragement makes me glad to know you! (And It IS encouragement.)