Adding bit-operations to RichInt/RichLong

[Simon Ochsenreither]

Hi,

I added methods like bitCount, numberOfLeadingZeros, rotateLeft, ... which existed as static members on java.lang.Integer/java.lang.Long to RichInt/RichLong in this branch: https://github.com/soc/scala/tree/topic/int-long-bitops

The reasoning behind it is to have

• "all" operations in a single place, with a consistent API
• less explicit dependencies on the JDK
• less need for users to import Java classes for basic functionality

One question is the naming: Every operation seems to have a few alternative names, we could evaluate each operation on a case-to-case base or we can decide to pick the same as Java. I checked C#, and they don't seem to provide these operations at all.

Another question is whether smaller types like Byte or Short will automatically gain these methods if we add them to RichInt/RichLong (not sure how the implicit widening conversions interact with the implicit def from <Num> to Rich<Num>), because some methods might exhibit unintuitive semantics here (e. g. reverse will always be zero).

Ideas/objections/opinions?

Thanks and bye,

Simon

/CC'ing Erik

[Paul Phillips]

On Wed, May 22, 2013 at 5:44 PM, Simon Ochsenreither <simon.och...@gmail.com> wrote:

Another question is whether smaller types like Byte or Short will automatically gain these methods if we add them to RichInt/RichLong (not sure how the implicit widening conversions interact with the implicit def from <Num> to Rich<Num>), because some methods might exhibit unintuitive semantics here (e. g. reverse will always be zero).

This is a problem. Yes, Bytes and Shorts will automatically be widened to Ints if there is an Int => Foo implicit available. That means, for instance:

scala> implicit def intBitCount(x: Int) = new { def bitCount = java.lang.Integer.bitCount(x) }

intBitCount: (x: Int)AnyRef{def bitCount: Int}

scala> (-1: Byte).bitCount

res0: Int = 32

You might be tempted to try something like this:

scala> implicit def byteBitCount(x: Byte) = new { def bitCount = java.lang.Integer.bitCount(x & 0xFF) }

byteBitCount: (x: Byte)AnyRef{def bitCount: Int}

scala> (-1: Byte).bitCount

res1: Int = 8

Don't be tempted. Relying on either overloading or implicit precedence for numerical correctness is a guaranteed disaster.

And because there is no way to suppress coercion between numeric types, I question whether methods such as bitCount can safely be provided in any form.

[Eugene Burmako]

I think this can be done in a macro, though I have to admit that in their current form macros would be much more heavyweight than one would like them to be.

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Simon Ochsenreither]

I don't think it's more broken than the stuff I'm seeing right now (working on https://groups.google.com/d/topic/scala-internals/t2DndCtkhlw/discussion, https://issues.scala-lang.org/browse/SI-7511).
E. g. what's wrong with def signum: Int?

Math is hard, but it needs to be implemented and tested.
Not sure if it is just the Scala implementation which makes me want to kill myself or if it's math stuff in general. But at least I have found a new use for annotation.bridge now.

[Simon Ochsenreither]

Anyway, getting rid of these implicit conversions would solve a lot of issues (even if we'd only remove the ones which cause a loss of precision). Kotlin certainly doesn't need them, why do we?

[Paul Phillips]

On Thu, May 23, 2013 at 10:43 AM, Simon Ochsenreither <simon.och...@gmail.com> wrote:

Anyway, getting rid of these implicit conversions would solve a lot of issues (even if we'd only remove the ones which cause a loss of precision).

Do "these implicit conversions" mean Byte => Int, etc? It may be before your time, but I tried to do this (i.e. I implemented it and converted the whole codebase) years ago. It was MUCH less of a problem at the user level than I had anticipated going in. In fact, I was invariably glad to get a type error. But this was lumped into the "we have to be like java" blob. 

[Simon Ochsenreither]

Do "these implicit conversions" mean Byte => Int, etc?

Exactly. Actually, I had two additional branches which were a bit more “conservative”: one which kept the “safe” ones and one which disabled just the conversions from integral types to floating-point types.
 

It may be before your time, but I tried to do this (i.e. I implemented it and converted the whole codebase) years ago. It was MUCH less of a problem at the user level than I had anticipated going in. In fact, I was invariably glad to get a type error. But this was lumped into the "we have to be like java" blob. 

Especially in times were we start to have 128bit (and larger) numbers, I think it's time to try it again¹. Just like those fail-whales on Twitter: You fix them by keeping F5 pressed. :-)

¹ Pending on me reading that chapter of the Java spec again. I want to be sure that this change only interacts on the value-level and doesn't involve any overriding/overloading/signature nightmares.

[Rex Kerr]

This isn't the way to do it, for the reasons discussed.

Instead you need

// NOTE: no implicit conversion

class RichBitOps32(val value: Int) extends AnyVal {

  def count = ...

  def leadingZeros = ...

  def rotl = ...

}

// inside RichInt
  ...

  def bits32 = new RichBitOps32(self)
  ...

This way you explicitly state in your code that you're doing an operation on 32 bits.  However, you should use short method names inside RichBitOps32 so that the whole thing isn't too clunky.

    x.bits32.count

is not too bad.

    x.bits32.numberOfLeadingZeros

starts getting pretty painful.

(Whether you call it BitOps32 or something else isn't too important as long as it is very clear that it's not a Byte or Short.)

  --Rex

--

[Paul Phillips]

Oh, I forgot I left the warning in place.

% pscala -Ywarn-numeric-widen

Welcome to Scala version 2.11.0-20130523-110846-11bc448fe9 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_21).

Type in expressions to have them evaluated.

Type :help for more information.

scala> implicit def intBitCount(x: Int) = new { def bitCount = java.lang.Integer.bitCount(x) }

warning: there were 1 feature warning(s); re-run with -feature for details

intBitCount: (x: Int)AnyRef{def bitCount: Int}

scala> (-1: Byte).bitCount

<console>:9: warning: implicit numeric widening

              (-1: Byte).bitCount

                 ^

warning: there were 1 feature warning(s); re-run with -feature for details

res0: Int = 32

scala> 

[Simon Ochsenreither]

// NOTE: no implicit conversion

class RichBitOps32

This way you explicitly state in your code that you're doing an operation on 32 bits.  However, you should use short method names inside RichBitOps32 so that the whole thing isn't too clunky.

This looks pretty cumbersome and inconsistent with the twenty-something existing bit operations on Int/Long/... Or does this mean that we'll be deprecating and moving them, too?

[Rex Kerr]

The problem is that it's not clear whether these things are "math" or not.  Math is always widened to Int from any smaller numeric type.  You can recognize math because it uses symbolic operators.  It's annoying, yes, but there's a pretty simple heuristic that you can apply.  And really, (x+y).toByte is already hard enough; making you (x.toInt + y.toInt).toByte just obscures the important operation even more in a flurry of type conversions.  I can't envision an intermediate scheme which isn't overly burdened with special cases--maybe someone can propose one.

If you use Java, you're either using operators-which-are-math, or you know you are doing something with Int because you're calling java.lang.Integer.foo(x).  Whether by accident or design, the current set of methods in Scala are either enriched onto both the smaller types and Int (Paul's warning notwithstanding), or give correct behavior if widened.

So simply allowing the widening with bitCount and friends is a problem because it forces people to add rules, increasing cognitive burden (beyond the burden of remembering that these methods exist at all).  It is clunky to have to occasionally reach for java.lang.Integer.bitCount, but at least that keeps things clear.

Thus, I think the sensible options (all with their own drawbacks) are to do one of

  (1) Do nothing--use java.lang.Integer as your marker for widening.

  (2) Ignore Paul's don't-rely-on-it advice and write methods for all the small types also

  (3) Introduce a much shorter marker than java.lang.Integer like .bits32 or .intOp

Personally, I think (2) and making -Ywarn-numeric-widen into -Xwarn-numeric-widen is the most pragmatic solution.  There is a virtue in the ease of accomplishing (1), however, and an appealing purity in (3).

--Rex

--

[Simon Ochsenreither]

Hi!

The problem is that it's not clear whether these things are "math" or not.  Math is always widened to Int from any smaller numeric type.  You can recognize math because it uses symbolic operators.  It's annoying, yes, but there's a pretty simple heuristic that you can apply.  And really, (x+y).toByte is already hard enough; making you (x.toInt + y.toInt).toByte just obscures the important operation even more in a flurry of type conversions.  I can't envision an intermediate scheme which isn't overly burdened with special cases--maybe someone can propose one.

If you use Java, you're either using operators-which-are-math, or you know you are doing something with Int because you're calling java.lang.Integer.foo(x).  Whether by accident or design, the current set of methods in Scala are either enriched onto both the smaller types and Int (Paul's warning notwithstanding), or give correct behavior if widened.

So simply allowing the widening with bitCount and friends is a problem because it forces people to add rules, increasing cognitive burden (beyond the burden of remembering that these methods exist at all).  It is clunky to have to occasionally reach for java.lang.Integer.bitCount, but at least that keeps things clear.

I'm not sure for or against what you are arguing here ... implicit conversions? math-ops which return at least Int? bit-ops which also return at least Int?

Thus, I think the sensible options (all with their own drawbacks) are to do one of

  (1) Do nothing--use java.lang.Integer as your marker for widening.

  (2) Ignore Paul's don't-rely-on-it advice and write methods for all the small types also

  (3) Introduce a much shorter marker than java.lang.Integer like .bits32 or .intOp

I would also tend to look into to (2) and see how far I get. Maybe Paul is completely right and it will be horrible, but at least I've learned a bit about the dark corners of overloading and implicit conversions.

Bye, Simon