Unsigned Arithmetic -- Humble Recommendation for Improving Scala

Hi Seyed,

I like your idea.

We could add unsigned variants of Long, Int, Short, Byte, that are backed by their signed primitive
counterpars. The literals would be the same with "u" or "ul" at the end. The typenames would be
prefixed with "U".

Since there is no unsigned arithmetic in JVM, all operations would be performed via signed
operations + shifting + bitwise operations (like [2]).

No performance boost, though. Only simplifying the user code and avoiding subtle errors if doing all
those bit manipulations manually.

This would really simplify programming im many areas, for instance: imaging, cryptography.

--
Eugen

[1] JVM Spec, 2nd ed. # 3.11.3 Arithmetic Instructions
http://java.sun.com/docs/books/jvms/second_edition/html/Overview.doc.htm...

[2] http://darksleep.com/player/JavaAndUnsignedTypes.html

Hi Eugen,

I am pleased to see my idea embraced by the community -- although I
will wait to see what the rest would say too. Your proposal makes
sense to me and looks like it goes enough with the rest of language.

> No performance boost, though. Only simplifying the user code and avoiding subtle errors if doing all those bit manipulations manually.

I would put a more emphasise here on correctness; performing signed
arithmetic on conceptually unsigned entities is a gap between the
concept's semantics and that of the implementation. I'm afraid Scala
is currently wrong thus to silently perform signed arithmetic
operations on Char which is promised to be an unsigned type.

> This would really simplify programming im many areas, for instance: imaging, cryptography.

Rather than simplification, I would rather put the emphasis on
correctness. This makes the implementation semantically correct.
Something that currently is unfortunately not true in Scala.

Looking forward more feedback.

TTFN,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Sorry, new GMail hid reply-to-all...

See http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4504839.

On Fri, Nov 4, 2011 at 09:04, Seyed H. HAERI (Hossein)
wrote:
> Dear all,
>
> [I have done my best to polish my words as much as possible. I do
> apologise in case, despite all my endeavours, my words are still not
> polite enough. Furthermore, knowing that I'm a C++ man, please do not
> take me wrong; I am against any language war. All I write below is
> because I feel I have something to improve Scala with.]
>
> A few weeks ago, I started a thread that asked for help on long
> unsigned arithmetic and realised that, sadly enough, the only unsigned
> type that Scala provides is Char. Over another thread that I started
> yesterday, I realised that -- despite the fact that PinS clearly
> refers to Char as a numeric type -- any arithmetic operation on Char
> is uplifted to Int and performed there. The experts on the list who
> kindly responded to my query all implied that the reason for this
> uplifting is that Int is the smallest type that JVM supports
> arithmetic on. But, this is no excuse because, accordingly, this
> uplifting business is in fact a silent change of semantics. Here is
> the reason:
>
> The architecture level usually has no understanding of types. It only
> performs operations -- be it arithmetic or not -- on series of bits.
> It then is the compiler's job to interpret these series of bits as
> values of the proper types supported in the target programming
> language. And, there is a categoric difference in the semantics of
> signed integral arithmetic and the unsigned ones. (Feel free to
> consult you favourite textbook.) This includes the architecture level
> algorithms used, as well as the compiler level type presentation. Now,
> if JVM happens unfortunately not to support unsigned arithmetic, then
> Scala should find a way to simulate that. If you'd like to know what
> the benefits of unsigned arithmetic are, see the P.S. for a brief
> explanation.
>
> All in all, I would like to humbly recommend the addition of unsigned
> arithmetic in all possible integral lengths to Scala. Given that I am
> very new to this language, I expect the senior members are in a much
> better position to guides implementation of this idea. Comments are of
> course more than welcome.
>
> Best,
> --Hossein
>
> P.S. Usually, when unsigned arithmetic is preferred over signed ones,
> at least one of these reasons apply: (Consult your favourite textbook
> for more.)
>
> 1) The algorithms to implement are on unsigned numeric values and the
> conceptual semantics dictates it.
> 2) One needs a wider range of positive numbers to deal with.
> (Normally, the positive range in the unsigned world is as wide as
> twice the width of the positive range in the signed counterpart with
> the same number of bites.)
> 3) One does not need signed arithmetic and wants to suit the relevant
> speed of unsigned calculation over the signed one. (Typically, signed
> algorithms need to put some extra care on the sign bit and are
> relatively slower (by a very small factor in comparison) compared to
> the respective unsigned ones. This small factor can become quite
> important in speed-critical applications with a lot of arithmetics to
> perform.)
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------
>

Hi Daniel,

> See http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4504839.

Thank you for the link. My favourite one is:

Submitted On 24-OCT-2010
frgomes
X10 is a research programming language by IBM, which is pretty similar
to Scala and provides unsigned arithmetic, closures, reified generics,
type annotations (JSR-308) and better semantics for multithreaded
code.

Because it implements properly unsigned types and it generates both
Java and C++ code, it's possible to interoperate more or less easily.

which makes it clear that: a) This is doable after all in IBM; b) Sun
has already done it for us and we're perhaps not in a very big trouble
to let it in Scala too.

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

SHH> which makes it clear that: a) This is doable after all in IBM;

I meant: "This is doable in JVM."

SHH> b) Sun has already done it

I meant: "IBM has already done it."

That's the effect of posting emails over phone calls. Sorry...

--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On 04/11/2011 11:04, Seyed H. HAERI (Hossein) wrote:

> yesterday, I realised that -- despite the fact that PinS clearly
> refers to Char as a numeric type -- any arithmetic operation on Char
> is uplifted to Int and performed there.

Any non-trivial calculation in C or C++ will also end up type promoting
chars to ints.

https://www.securecoding.cert.org/confluence/display/seccode/INT02-C.+Un...

On Fri, Nov 4, 2011 at 7:16 AM, Daniel Sobral <dcsobral@gmail.com> wrote:

Sorry, new GMail hid reply-to-all...

See http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4504839.

Any day now.

Hi Alan,

> Any non-trivial calculation in C or C++ will also end up type promoting
> chars to ints.
>
> https://www.securecoding.cert.org/confluence/display/seccode/INT02-C.+Un...

This link is about C -- which I'm not authentic enough to talk about.
In C++, IINM, the story is totally different. I'll double-check that
in the C++ Standard and come back. Thank you for bringing the doubt
up. :)

TTFN,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Hi again,

>> Any non-trivial calculation in C or C++ will also end up type promoting chars to ints.

Double-check. That's totally wrong about C++ (clause 1, section 4.5,
ISO-IEC 14882:1998(E) for C++):

"1 An rvalue of type char, signed char, unsigned char, short int,
or unsigned short int can be converted to an rvalue of type int if int
can represent all the values of the source type; otherwise, the
source rvalue can be converted to an rvalue of type unsigned int."

The same holds for the recent C++11:

http://www.open-std.org/jtc1/sc22/open/n2356/conv.html

HTH,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On 04/11/2011 14:14, Seyed H. HAERI (Hossein) wrote:

> Double-check. That's totally wrong about C++ (clause 1, section 4.5,
> ISO-IEC 14882:1998(E) for C++):
>
> "1 An rvalue of type char, signed char, unsigned char, short int,
> or unsigned short int can be converted to an rvalue of type int if int
> can represent all the values of the source type; otherwise, the
> source rvalue can be converted to an rvalue of type unsigned int."
>
> The same holds for the recent C++11:
>
> http://www.open-std.org/jtc1/sc22/open/n2356/conv.html

Exactly what I said - in most cases, arithmetic with types shorter than
int will end up using either signed or unsigned ints.

Hi Alan,

>> "1 An  rvalue  of  type  char,  signed char, unsigned char, short int, or unsigned short int can be converted to an rvalue of type int if int can represent all the values of the source type;
>> otherwise, the source rvalue can be converted to an rvalue of type unsigned int."

No, this...

> Exactly what I said - in most cases, arithmetic with types shorter than int will end up using either signed or unsigned ints.

... is substantially different from your imprecise wording. There is a
great semantic difference between fixed-width arithmetic of signed
integral types and unsigned ones. The C++ snippet above is
pedantically prudent about what to mix with what. Whereas your wording
is a very coarse generalisation.

Hope you don't consider that too personal...

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On 04/11/2011 14:55, Seyed H. HAERI (Hossein) wrote:

> There is a
> great semantic difference between fixed-width arithmetic of signed
> integral types and unsigned ones. The C++ snippet above is
> pedantically prudent about what to mix with what. Whereas your wording
> is a very coarse generalisation.

Whereas you've been randomly mixing up signedness/unsigness issues with
integral type promotion issues - they aren't the same thing.

Plus you are banging on about something (wanting unsigned support)
without apparently doing even the most basic background research or even
just thinking about the problem yourself. For example, have you
researched or thought about the following questions?

* Do any other JVM languages offer unsigned support?
* If so, how do they do it?
* If so, what is the performance impact?
* How would you implement it in the JVM bytecodes emitted by Scala?
* How would it interact with Scala's type system?
* What impact would it have on the internals of the Scala compiler?
* What impact would it have on backwards compatibility of exiting Scala
code?

> Hope you don't consider that too personal...

Ditto.

Dear Alan,

> * Do any other JVM languages offer unsigned support?
> * If so, how do they do it?
> * If so, what is the performance impact?
> * How would you implement it in the JVM bytecodes emitted by Scala?
> * How would it interact with Scala's type system?
> * What impact would it have on the internals of the Scala compiler?
> * What impact would it have on backwards compatibility of exiting Scala
>  code?

I am too new to Scala to be able to answer these questions. But,
regardless of the difficulty, what evaporated out of my recent threads
on the matter is that there currently is a semantic flaw in Scala that
needs to be addressed. If one can find a solution which doesn't
sacrifice backward compatibility, then superb. But, even that's not of
slightest importance against correcting a mistake. (I have always been
more than thankful of C++ for not causing my programs crash by its
beautiful support for backward compatibility. So, as a C++ person, I
know the value of backward compatibility very well.)

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Signed and unsigned arithmetic is simply _not_ that different from unsigned arithmetic.  With a type of width b bits, both are modulo 2^b; the only difference is that 0..(2^b-1) is chosen as the representation for one while (-2^(b-1)..(2^(b-1)-1)) is chosen for the other.  But it's really the same ring, and if you have a wider ring of width b+d, you can trivially restrict the range to the narrower ring.

So, bottom line is that you can just do all addition, subtraction, and multiplication just like you would before (assuming you're not promoting to 2b bits when you do multiplication but are staying within the ring), and restrict at the end.

Division needs to be done in the larger ring with the correct sign to emulate unsigned division in the smaller ring.

Bitwise operations can be done in the larger ring, but after that you need to restrict to the smaller ring before you do more arithmetic.

Bit shifts use >> for signed and >>> for unsigned bit shift.  If you are doing an unsigned shift in the large ring, make sure you use the unsigned representation.

To get from a smaller unsigned ring to a larger signed one, do a bit mask of the appropriate bits after (signed) conversion to the larger ring.

So there are a few things to learn.  But once you've learned them, if you have to use them ALL the time you can create your own set of methods; if you don't, just follow the rules for the bit of math you have to do.

Just to give an example of char math:
  unsigned short a,b,c,d;
  unsigned short e = a + (b*c) - d;
  unsigned short f = (unsigned short)((int)a + ((int)b*(int)c) - (int)d);
  // e==f always
  Implication for Scala:
  val (a,b,c,d) = (chars)
  val e = (a + (b*c) - d).toChar  // This is correct
  val f = ((a*b-c)&d).toChar  // Correct
  val g = (a/b).toChar  // WRONG
  val g2 = ((a&0xFFFF) / (b&0xFFFF)).toChar // Correct
  val h = ((a<<b)&0xFFFF).toChar  // Correct
  val y,z: Short = //something
  val h2 = (y>>>z)toShort  // WRONG
  val h3 = ((y&0xFFFF)>>>z).toShort // Correct

If the distinction between signed and unsigned operations are essential for you, you should know all this already.  If you don't, you cannot reason properly about what is happening.  Yes, it's a bit of a chore to type it all out, but that's much, much less of a chore than changing the compiler and library to box unsigned values in different containers than signed ones (so they can be kept track of), for all statements of the form
  x match {
    case Int => //something
    case Long => //something
    ...
  }
to have to pick up a bunch more cases for UInt, ULong, etc. (slowing them down by a factor of two), for interoperability with Java to break if you use any of the unsigned features, for certain features to not work within the JVM even though it would seem that the unsigned types ought to be the ones to use (e.g. arrays cannot be indexed past 2^31-1), etc. etc. etc..

There are a tremendous number of tremendously difficult issues to work through to make everything function smoothly, especially if performance matters.  (If it does not, just implement your own unsigned classes!)  All that work to avoid a few (x&0xFFFF)s seems like a waste to me.

  --Rex

On Fri, Nov 4, 2011 at 7:04 AM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Dear all,

[I have done my best to polish my words as much as possible. I do
apologise in case, despite all my endeavours, my words are still not
polite enough. Furthermore, knowing that I'm a C++ man, please do not
take me wrong; I am against any language war. All I write below is
because I feel I have something to improve Scala with.]

A few weeks ago, I started a thread that asked for help on long
unsigned arithmetic and realised that, sadly enough, the only unsigned
type that Scala provides is Char. Over another thread that I started
yesterday, I realised that -- despite the fact that PinS clearly
refers to Char as a numeric type -- any arithmetic operation on Char
is uplifted to Int and performed there. The experts on the list who
kindly responded to my query all implied that the reason for this
uplifting is that Int is the smallest type that JVM supports
arithmetic on. But, this is no excuse because, accordingly, this
uplifting business is in fact a silent change of semantics. Here is
the reason:

The architecture level usually has no understanding of types. It only
performs operations -- be it arithmetic or not -- on series of bits.
It then is the compiler's job to interpret these series of bits as
values of the proper types supported in the target programming
language. And, there is a categoric difference in the semantics of
signed integral arithmetic and the unsigned ones. (Feel free to
consult you favourite textbook.) This includes the architecture level
algorithms used, as well as the compiler level type presentation. Now,
if JVM happens unfortunately not to support unsigned arithmetic, then
Scala should find a way to simulate that. If you'd like to know what
the benefits of unsigned arithmetic are, see the P.S. for a brief
explanation.

All in all, I would like to humbly recommend the addition of unsigned
arithmetic in all possible integral lengths to Scala. Given that I am
very new to this language, I expect the senior members are in a much
better position to guides implementation of this idea. Comments are of
course more than welcome.

Best,
--Hossein

P.S. Usually, when unsigned arithmetic is preferred over signed ones,
at least one of these reasons apply: (Consult your favourite textbook
for more.)

1) The algorithms to implement are on unsigned numeric values and the
conceptual semantics dictates it.
2) One needs a wider range of positive numbers to deal with.
(Normally, the positive range in the unsigned world is as wide as
twice the width of the positive range in the signed counterpart with
the same number of bites.)
3) One does not need signed arithmetic and wants to suit the relevant
speed of unsigned calculation over the signed one. (Typically, signed
algorithms need to put some extra care on the sign bit and are
relatively slower (by a very small factor in comparison) compared to
the respective unsigned ones. This small factor can become quite
important in speed-critical applications with a lot of arithmetics to
perform.)

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On Fri, Nov 4, 2011 at 11:40 AM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

I am too new to Scala to be able to answer these questions. But,
regardless of the difficulty, what evaporated out of my recent threads
on the matter is that there currently is a semantic flaw in Scala that
needs to be addressed. If one can find a solution which doesn't
sacrifice backward compatibility, then superb. But, even that's not of
slightest importance against correcting a mistake.

Your proposal is to sacrifice backwards compatibility to add a _feature_.  That's entirely different.  The implementation of numeric types as it stands is mathematically correct and adequate for typical use cases.

  --Rex

Rex,

> The implementation of numeric types as it stands is mathematically correct

No that's plain wrong. The semantics of Scala is at the moment flawed
for the following very simple reason:

val ch: Char = ...
val result = ch * ch

"result" is of type Int that is a signed type -- which has a lot of
difference in its semantics with unsigned type, including the ones you
said in your other posting in this thread.

TTFN,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

You're just thinking about it wrong.  * isn't defined on Char, only on Int (and larger types).  Scala is converting from Char to Int for you, rather than throwing an error.

I guess you could argue that there should be some way to avoid the automatic promotion from Char to Int.

  --Rex

On Fri, Nov 4, 2011 at 12:05 PM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Rex,

> The implementation of numeric types as it stands is mathematically correct

No that's plain wrong. The semantics of Scala is at the moment flawed
for the following very simple reason:

val ch: Char = ...
val result = ch * ch

"result" is of type Int that is a signed type -- which has a lot of
difference in its semantics with unsigned type, including the ones you
said in your other posting in this thread.

TTFN,
--Hossein

On Fri, Nov 4, 2011 at 11:05 AM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Rex,

> The implementation of numeric types as it stands is mathematically correct

No that's plain wrong. The semantics of Scala is at the moment flawed
for the following very simple reason:

val ch: Char = ...
val result = ch * ch

"result" is of type Int that is a signed type -- which has a lot of
difference in its semantics with unsigned type, including the ones you
said in your other posting in this thread.

You keep coming back to this one example as a demonstration of a problem. However you haven't given any examples where this behavior in fact becomes a problem and can lead to bugs.

People, there are plenty problems described in the link I posted to
the bug entry on Java, and on the related tickets indicated there.

Seyed, it is not going to happen unless someone implements it. Wanting
it won't make it happen. If you want unsigned bytes for the sake of
convenience, it is easy to implement them as a class, but it won't be
fast. In fact, it is even easy to add unsigned operators to Byte,
Char, Short and Int through implicit conversions. I think a plugin
might be able to do it with speed, but, if you want it, you and
like-minded people will have to do it yourselves.

Rex, there's no need to box it. Erase it to "int" and forget Java
integration. As you said, all that's needed is a few more opcodes for
a few operators.

On Fri, Nov 4, 2011 at 14:47, Aleksey Nikiforov wrote:
>
> On Fri, Nov 4, 2011 at 11:05 AM, Seyed H. HAERI (Hossein)
> wrote:
>>
>> Rex,
>>
>> > The implementation of numeric types as it stands is mathematically
>> > correct
>>
>> No that's plain wrong. The semantics of Scala is at the moment flawed
>> for the following very simple reason:
>>
>> val ch: Char = ...
>> val result = ch * ch
>>
>> "result" is of type Int that is a signed type -- which has a lot of
>> difference in its semantics with unsigned type, including the ones you
>> said in your other posting in this thread.
>
> You keep coming back to this one example as a demonstration of a problem.
> However you haven't given any examples where this behavior in fact becomes a
> problem and can lead to bugs.
>

Hi Aleksey,

>> val ch: Char = ...
>> val result = ch * ch
>>
>> "result" is of type Int that is a signed type -- which has a lot of
>> difference in its semantics with unsigned type, including the ones you
>> said in your other posting in this thread.
>
> You keep coming back to this one example as a demonstration of a problem.
> However you haven't given any examples where this behavior in fact becomes a
> problem and can lead to bugs.

Good point. I'll think about it and come back to you.

Thanks,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Hi Rex,

> You're just thinking about it wrong.  * isn't defined on Char, only on Int (and larger types).  Scala is converting from Char to Int for you, rather than throwing an error.

This contradicts the quote I provided earlier on from PinS in that
Char is a numeric type itself.

> I guess you could argue that there should be some way to avoid the automatic promotion from Char to Int.

Not sure whether this is really what will solve the multiplication
problem. But, Scala would then completely lack support for unsigned
arithmetic.

TTFN,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On 04/11/2011 17:11, Seyed H. HAERI (Hossein) wrote:

>> You keep coming back to this one example as a demonstration of a problem.
>> However you haven't given any examples where this behavior in fact becomes a
>> problem and can lead to bugs.
>
> Good point. I'll think about it and come back to you.

Finally.

Wading into this late, and risking saying something stupid...

Years ago I did a lot of coding in a language called Plus, which was
based on Sue, which was based on Pascal. One interesting feature of the
language was that there were no primitive types for integers like short,
int, long - rather there were only ranges (not to be confused with Scala
ranges). For example:

variables
foo is 0 to 10;
bar is -10 to 10;

Along with this the compiler ensured you could not do something like

foo := 43;

or you would get a range-check exception.

In order to make things convenient, in the standard import libraries we
had definitions such as

types
Integer is -2147483648 to 2147483647;
PositiveInteger is 0 to 4294967295;

because it was easier for most coders to do that than think about the
actual range they needed, or that you needed to know how many bits were
used when you had to pack your data. Plus was a systems programming
language.

If you wanted to, you could do things like

variable foo is packed array TinyPositiveInteger of Boolean;

but in most cases it was more clear to just write

variable foo is packed array 0 to 255 of Boolean;

Ignoring the realities of Java and the JVM for the moment, I am actually
kind of surprised Scala did not do something like this.

The point is - we got along fine without directly needing signed and
unsigned types and operations, as we trusted the compiler to do the
right thing and use signed or unsigned operations given the context of
the ranges we were using.

While there was a Character type in the language, you could not use it
in arithmetic unless you cast it to TinyPositiveInteger or TinyInteger
or something else compatible. This was before there was Unicode.

Cheers, Eric

On 2011-11-04 18:01, Daniel Sobral wrote:
> Seyed, it is not going to happen unless someone implements it. Wanting
> it won't make it happen. If you want unsigned bytes for the sake of
> convenience, it is easy to implement them as a class, but it won't be
> fast. In fact, it is even easy to add unsigned operators to Byte,
> Char, Short and Int through implicit conversions. I think a plugin
> might be able to do it with speed, but, if you want it, you and
> like-minded people will have to do it yourselves.

Perhaps someone is looking for the subject of his/her master thesis?

How about something like "Implementing unsigned integers in Scala via compiler plugin"?

The X10 language[1] mentioned in your link can be taken as an example[2,3] (search for "unsigned").

--
Eugen

[1] http://x10-lang.org

[2] X10 Language Specification v2.2
http://dist.codehaus.org/x10/documentation/languagespec/x10-latest.pdf

[3] X10 Programmer's Guide v2.1
http://dist.codehaus.org/x10/documentation/guide/2.1.0/pguide.pdf

This contradicts the quote I provided earlier on from PinS in that
Char is a numeric type itself.

Being a numeric type doesn't mean it implements certain methods like * or -. Java doesn't do that, too.

Hi Seyed,

I implemented unsigned integers of variable bit size recently for a
program that has to interface with a C++ data provider that has
unsigned types. You can easily implement something like UByte, UShort,
UInt and ULong by wrapping a signed long and overloading all the
relevant operations.

Most operations, like + and -, can be handed straight to the
underlying primitive. If I remember correctly, the only thing where
you need to be careful is division, comparison and toString. In my
case I had to represent all unsigned integers from 1 to 64 bits. For
everything except 64bit unsigned I just wrapped a long and masked the
unused bits after each operation. For 64bit I had to use BigInt
occasionally, which is of course quite slow.

Wrapping will be significantly slower than just using the primitive
type itself and doing the occasional masking operation yourself.
Escape analysis and scalar replacement should reduce some of the
temporary object creation, but not all of it. But it will be
completely transparent.

And realistically that is all you can hope for for a language running
on the JVM. Maybe you should try living with just signed integers for
a while and see if it really hinders you so much. I found that I don't
miss unsigned integers at all.

On Fri, Nov 4, 2011 at 12:04 PM, Seyed H. HAERI (Hossein)
wrote:
> Dear all,
>
> [I have done my best to polish my words as much as possible. I do
> apologise in case, despite all my endeavours, my words are still not
> polite enough. Furthermore, knowing that I'm a C++ man, please do not
> take me wrong; I am against any language war. All I write below is
> because I feel I have something to improve Scala with.]
>
> A few weeks ago, I started a thread that asked for help on long
> unsigned arithmetic and realised that, sadly enough, the only unsigned
> type that Scala provides is Char. Over another thread that I started
> yesterday, I realised that -- despite the fact that PinS clearly
> refers to Char as a numeric type -- any arithmetic operation on Char
> is uplifted to Int and performed there. The experts on the list who
> kindly responded to my query all implied that the reason for this
> uplifting is that Int is the smallest type that JVM supports
> arithmetic on. But, this is no excuse because, accordingly, this
> uplifting business is in fact a silent change of semantics. Here is
> the reason:
>
> The architecture level usually has no understanding of types. It only
> performs operations -- be it arithmetic or not -- on series of bits.
> It then is the compiler's job to interpret these series of bits as
> values of the proper types supported in the target programming
> language. And, there is a categoric difference in the semantics of
> signed integral arithmetic and the unsigned ones. (Feel free to
> consult you favourite textbook.) This includes the architecture level
> algorithms used, as well as the compiler level type presentation. Now,
> if JVM happens unfortunately not to support unsigned arithmetic, then
> Scala should find a way to simulate that. If you'd like to know what
> the benefits of unsigned arithmetic are, see the P.S. for a brief
> explanation.
>
> All in all, I would like to humbly recommend the addition of unsigned
> arithmetic in all possible integral lengths to Scala. Given that I am
> very new to this language, I expect the senior members are in a much
> better position to guides implementation of this idea. Comments are of
> course more than welcome.
>
> Best,
> --Hossein
>
> P.S. Usually, when unsigned arithmetic is preferred over signed ones,
> at least one of these reasons apply: (Consult your favourite textbook
> for more.)
>
> 1) The algorithms to implement are on unsigned numeric values and the
> conceptual semantics dictates it.
> 2) One needs a wider range of positive numbers to deal with.
> (Normally, the positive range in the unsigned world is as wide as
> twice the width of the positive range in the signed counterpart with
> the same number of bites.)
> 3) One does not need signed arithmetic and wants to suit the relevant
> speed of unsigned calculation over the signed one. (Typically, signed
> algorithms need to put some extra care on the sign bit and are
> relatively slower (by a very small factor in comparison) compared to
> the respective unsigned ones. This small factor can become quite
> important in speed-critical applications with a lot of arithmetics to
> perform.)
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------
>

You are really knocking on the wrong door here.

Tell the JVM team to implement it and Scala will probably think about supporting it.

Numbers need fast and predictable performance. Making the compiler emulate stuff is neither.

Hi Aleksey,

> You keep coming back to this one example as a demonstration of a problem. However you haven't given any examples where this behavior in fact becomes a problem and can lead to bugs.

Here you are:

> val ch: Char = 65535
ch: Char = ?
> val ii: Int = ch * ch
ii: Int = -131071

Multiplication of two positive (unsigned) values results in a negative
(signed) variable!!! You know why that happens? Because the first bit
in the 32 bits of Int is reserved for its sign. The series of bits
that I have repeatedly spoken about and the compiler's interpretation
job here comes to the play: The multiplication resulting series of
bits is mistakenly interpreted as signed values and because the result
is bigger than 2^31 - 1, it will be thought of as a negative value.
All that is the case because of the flawed mixture of signed/unsigned
arithmetic in Scala.

Hope that finally helps.
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Hi Simon,

>> This contradicts the quote I provided earlier on from PinS in that Char is a numeric type itself.
>
> Being a numeric type doesn't mean it implements certain methods like * or -. Java doesn't do that, too.

I don't want to speak about Java because nothing in its design suggest
any rational thinking to me. Regarding operator overloads in general,
however: Yes, operators need not to be overloaded for a type become
arithmetic; normal functions are equally acceptable when it comes only
to being arithmetic.

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Hi Rüdiger,

I am glad to see such a member in the Scala community. Can I by any
chance see your code?

TIA,
--Hossein

P.S. I am just as much of a theoretician as I am a pragmatic
(industrial) software developer. So, regardless of whether I myself
will be touching a lot of unsigned arithmetic in Scala, I will still
be concerned about correctness of the language I am working with.

On 4 November 2011 20:48, Rüdiger Klaehn wrote:
> Hi Seyed,
>
> I implemented unsigned integers of variable bit size recently for a
> program that has to interface with a C++ data provider that has
> unsigned types. You can easily implement something like UByte, UShort,
> UInt and ULong by wrapping a signed long and overloading all the
> relevant operations.
>
> Most operations, like + and -, can be handed straight to the
> underlying primitive. If I remember correctly, the only thing where
> you need to be careful is division, comparison and toString. In my
> case I had to represent all unsigned integers from 1 to 64 bits. For
> everything except 64bit unsigned I just wrapped a long and masked the
> unused bits after each operation. For 64bit I had to use BigInt
> occasionally, which is of course quite slow.
>
> Wrapping will be significantly slower than just using the primitive
> type itself and doing the occasional masking operation yourself.
> Escape analysis and scalar replacement should reduce some of the
> temporary object creation, but not all of it. But it will be
> completely transparent.
>
> And realistically that is all you can hope for for a language running
> on the JVM. Maybe you should try living with just signed integers for
> a while and see if it really hinders you so much. I found that I don't
> miss unsigned integers at all.
>
> On Fri, Nov 4, 2011 at 12:04 PM, Seyed H. HAERI (Hossein)
> wrote:
>> Dear all,
>>
>> [I have done my best to polish my words as much as possible. I do
>> apologise in case, despite all my endeavours, my words are still not
>> polite enough. Furthermore, knowing that I'm a C++ man, please do not
>> take me wrong; I am against any language war. All I write below is
>> because I feel I have something to improve Scala with.]
>>
>> A few weeks ago, I started a thread that asked for help on long
>> unsigned arithmetic and realised that, sadly enough, the only unsigned
>> type that Scala provides is Char. Over another thread that I started
>> yesterday, I realised that -- despite the fact that PinS clearly
>> refers to Char as a numeric type -- any arithmetic operation on Char
>> is uplifted to Int and performed there. The experts on the list who
>> kindly responded to my query all implied that the reason for this
>> uplifting is that Int is the smallest type that JVM supports
>> arithmetic on. But, this is no excuse because, accordingly, this
>> uplifting business is in fact a silent change of semantics. Here is
>> the reason:
>>
>> The architecture level usually has no understanding of types. It only
>> performs operations -- be it arithmetic or not -- on series of bits.
>> It then is the compiler's job to interpret these series of bits as
>> values of the proper types supported in the target programming
>> language. And, there is a categoric difference in the semantics of
>> signed integral arithmetic and the unsigned ones. (Feel free to
>> consult you favourite textbook.) This includes the architecture level
>> algorithms used, as well as the compiler level type presentation. Now,
>> if JVM happens unfortunately not to support unsigned arithmetic, then
>> Scala should find a way to simulate that. If you'd like to know what
>> the benefits of unsigned arithmetic are, see the P.S. for a brief
>> explanation.
>>
>> All in all, I would like to humbly recommend the addition of unsigned
>> arithmetic in all possible integral lengths to Scala. Given that I am
>> very new to this language, I expect the senior members are in a much
>> better position to guides implementation of this idea. Comments are of
>> course more than welcome.
>>
>> Best,
>> --Hossein
>>
>> P.S. Usually, when unsigned arithmetic is preferred over signed ones,
>> at least one of these reasons apply: (Consult your favourite textbook
>> for more.)
>>
>> 1) The algorithms to implement are on unsigned numeric values and the
>> conceptual semantics dictates it.
>> 2) One needs a wider range of positive numbers to deal with.
>> (Normally, the positive range in the unsigned world is as wide as
>> twice the width of the positive range in the signed counterpart with
>> the same number of bites.)
>> 3) One does not need signed arithmetic and wants to suit the relevant
>> speed of unsigned calculation over the signed one. (Typically, signed
>> algorithms need to put some extra care on the sign bit and are
>> relatively slower (by a very small factor in comparison) compared to
>> the respective unsigned ones. This small factor can become quite
>> important in speed-critical applications with a lot of arithmetics to
>> perform.)
>>
>> --------------------------------------------------------------------------------------------------------------
>>
>> Seyed H. HAERI (Hossein)
>>
>> Research Assistant
>> Institute for Software Systems (STS)
>> Technical University of Hamburg (TUHH)
>> Hamburg, Germany
>>
>> ACCU - Professionalism in programming - http://www.accu.org/
>> --------------------------------------------------------------------------------------------------------------
>>
>

Hi Simon,

> Tell the JVM team to implement it and Scala will probably think about supporting it.

I usually only speak to the people whom I guess I might be able to
make sense with. I'm afraid the entire idea of Java doesn't make much
sense to me ever.

> Numbers need fast and predictable performance. Making the compiler emulate stuff is neither.

At the moment, I don't know enough Scala to speak about this. But, as
a C++ person, by design, I have a lot to be concerned about when it
comes to performance. Maybe I'll sometime in the future consider the
problem when I know enough Scala...

TTFN,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On Fri, Nov 4, 2011 at 3:48 PM, Rüdiger Klaehn <rklaehn@googlemail.com> wrote:

Hi Seyed,

I implemented unsigned integers of variable bit size recently for a
program that has to interface with a C++ data provider that has
unsigned types. You can easily implement something like UByte, UShort,
UInt and ULong by wrapping a signed long and overloading all the
relevant operations.

Most operations, like + and -, can be handed straight to the
underlying primitive. If I remember correctly, the only thing where
you need to be careful is division, comparison and toString. In my
case I had to represent all unsigned integers from 1 to 64 bits. For
everything except 64bit unsigned I just wrapped a long and masked the
unused bits after each operation. For 64bit I had to use BigInt
occasionally, which is of course quite slow.

This is about 4x faster than BigInt in the worst case, more in the best:

def udiv(a: Long, b: Long): Long = {
  if (b < 0) {
    if (a<0 && a >= b) 1L else 0L
  }
  else if (a < 0) {
    val c = 0x7FFFFFFFFFFFFFFFL/b
    udiv(a - b*c, b) + c
  }
  else a/b
}

  --Rex

On Fri, Nov 4, 2011 at 3:13 PM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote

> val ch: Char = 65535
ch: Char = ?
> val ii: Int = ch * ch
ii: Int = -131071

Whar you are looking for is (ch * ch).toChar. Which pretty much fixes your issue. 

Multiplication of two positive (unsigned) values results in a negative
(signed) variable!!! You know why that happens? Because the first bit
in the 32 bits of Int is reserved for its sign. The series of bits
that I have repeatedly spoken about and the compiler's interpretation
job here comes to the play: The multiplication resulting series of
bits is mistakenly interpreted as signed values and because the result
is bigger than 2^31 - 1, it will be thought of as a negative value.

Compiler does not interpret anything, that is not compiler's job. Compiler converts everything to Int to do the multiplication. The only rule here is that all the smaller integral types are ALWAYS converted to Int to do any kind of math. It's not that hard to remember. You end up with all the bits, including the overflow. If you dont want the extra bits, you discard them with a cast back toChar.  

All that is the case because of the flawed mixture of signed/unsigned
arithmetic in Scala.

A mixture of signed and unsigned arithmetics has always been confusing. This is precisely the reason it was not included in Java... with the exception of Char. Notice how Char is not called UnsignedShort, or UShort, or UInt16. It's called Char. The implication is that it is a letter. If you treat it as a number, it means you know what you are doing.
So basically what you are complaining about is that when you multiply two letters you get an unexpected result! Can you really claim that you were misled by the strong numerical and behavioral implications placed into the type name CHAR?
Scala's type inference is where the real problem is hiding, because in Java, you would say:  char result = ch*ch;  if (result > 0) System.out.println("ok"); Which would fail to compile, and instantly make you alert to what is happening. On the other hand in Scala the upcast to Int is hidden behind the type inference:  val result = ch*ch;  if (result > 0) System.out.println("ok"); Now result is Int, which is not something you expected.
The only real solution for Scala is to strip all the numeric operations from Char and to force users to manually cast it to Int and back. That would accomplish two things: send the point across that Char is not an "UnsignedShort" and remove any possible confusion as to what is going on once and for all.

Just wanted to add that the situation you are describing with overflow is not unique to Chars. This could be equally confusing with signed integral types that get upcast to Int:
scala> val a: Byte = 127; val b: Byte = 1 a: Byte = 127b: Byte = 1
When you add two signed bytes a + b you expect them to overflow and produce a negative signed 8 bit number. That is not the case.
scala> if ((a + b) < 0) println("overflow") else println("what?")what?
scala> if ((a + b).toByte < 0) println("overflow") else println("what?") overflow
Clearly the problem is not so much unsigned/signed mixture, but the unexpected upcast to Int. Notice that in this case the result of the operation is never assigned so the upcast to Int would be hidden in Java as well. So Scala's type inference cannot be blamed for hiding the problem.
Well, looks like this is just one of those things that you simply have to keep an eye on. The main rule to remember is the upcast to Int when performing math on smaller numerical types. If you can remember that, you will be able to avoid any potential mistakes with Chars, Shorts, and Bytes. And they are really in the same boat here.

> Multiplication of two positive (unsigned) values results in a negative
> (signed) variable!!!

This is not related to signed/unsigned issues. It occurs because Scala does
not check for integer overflow. Consider:

scala> val i = 65535
i: Int = 65535

scala> val j = i * i
j: Int = -131071

In your example 65535 is first converted to (signed) Int thus yielding the
same results as above. It's not example a "semantic problem" unless you feel
that programming languages should always do integer computations with
arbitrary precision or, failing that, always report an error if integer
overflow occurs. That's not an unreasonable feeling, but it is different
than what many programming languages do. In particular, C++ behaves the same
was as Scala in this area.

Peter

Hi Peter,

> This is not related to signed/unsigned issues. It occurs because Scala does not check for integer overflow.

No, that's not the culprit. I refer you (and the rest) back to my
citation from the C++ Standard:

"1 An rvalue of type char, signed char, unsigned char, short int,
or unsigned short int can be converted to an rvalue of type int if
int can represent all the values of the source type; otherwise, the
source rvalue can be converted to an rvalue of type unsigned int."

> scala> val i = 65535
> i: Int = 65535
>
> scala> val j = i * i
> j: Int = -131071

When both multiplicands are unsigned, the result needs to be unsigned
too. If Scala had support for unsigned arithmetic of the right size
for Int, augmented with a similar rule to that of C++ above, it could
have simply realised that j needs to be an unsigned and it would have
stopped mistakenly representing it as a signed one.

TTFN,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Why do you persist in saying things like "would have stopped mistakenly representing it as a signed one" despite us repeatedly explaining that
  (1) The JVM only does signed arithmetic, and trying to hide this fact will cause multiple bugs and/or sizable degradation in performance in unexpected places, and
  (2) * is not defined on Char

Char is not the commutative ring with unity ({0..65535},+,0,*,1) that unsigned short is in C++.  If you saw "Char" in Scala or "char" in Java and thought, "Oh, that's just like unsigned short in C++, which I know!", you were wrong.  Char is _only_ the set {0..65535}.  Granted, the documentation may not make this quite as clear as it ought to, but if you read what the actual specifications are, you'll realize it.  To persist in calling the behavior exhibited by Scala a "mistake" without addressing this point in detail is foolish or lazy.

If you have an actual programming problem that you wish to solve, many of us are happy to help.  If you want Scala to work more like C++, without understanding the different constraints, so that you don't have to learn as much, I think you'll find considerably less sympathy.

  --Rex


On Fri, Nov 4, 2011 at 6:56 PM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

When both multiplicands are unsigned, the result needs to be unsigned
too. If Scala had support for unsigned arithmetic of the right size
for Int, augmented with a similar rule to that of C++ above, it could
have simply realised that j needs to be an unsigned and it would have
stopped mistakenly representing it as a signed one.

> When both multiplicands are unsigned, the result needs to be unsigned
> too.

Scala isn't C++. The Scala Reference Manual talks about these conversions in
section 12.2.1 on Numeric Value Types. There Char is defined to be a
"subrange type." It goes on to say

"Given two numeric value types S and T , the operation type of S and T is
defined as follows: If both S and T are subrange types then the operation
type of S and T is Int..."

It bothers you that Scala is converting an unsigned value to a signed value
in this situation (Char being converted to Int). There is nothing inherently
wrong with this... it's just as arbitrary a choice as the one C++ makes.
Since Scala doesn't have any unsigned integer types currently it's certainly
a natural choice to make. Adding support for an unsigned type to Scala is a
reasonable thing to think about, but I don't think you are justified in
saying that there is a "semantic flaw" in the current definition of the
language because of this situation.

Peter

On Fri, Nov 4, 2011 at 9:30 PM, Seyed H. HAERI (Hossein)
wrote:
> Hi Rüdiger,
>
> I am glad to see such a member in the Scala community. Can I by any
> chance see your code?
>
I am afraid not. This is proprietary code I wrote for my employer, and
in any case it is not exactly what you want, since it is more
concerned with efficient storage of unsigned data types in bulk while
retaining the type information than with doing calculations.

But to illustrate the basic principle I appended a rudimentary
implementation of an unsigned int. The same approach can be used to do
unsigned shorts (mask=0xFFFFL) or unsigned bytes (mask=0xFFL). An
unsigned long with the full 64bit needs some special treatment in
toString and multiplication/division. All the bit operations obviously
would just go straight to the underlying primitive, as do + and -.

> TIA,
> --Hossein
>
> P.S. I am just as much of a theoretician as I am a pragmatic
> (industrial) software developer. So, regardless of whether I myself
> will be touching a lot of unsigned arithmetic in Scala, I will still
> be concerned about correctness of the language I am working with.
>
This has nothing to do with correctness. The behavior of scala is
defined in the scala language specification. As long as the actual
behavior is consistent to what is described there, the language is
correct. Just because the behavior regarding conversions is different
to the C++ language specification does not mean that scala is not
correct, because scala is not C++.

Anyway, here is the code. To use, import unsigned.UInt._ to get the
pimps for int, short and byte.

---

package unsigned

final class UInt private(private val value: Long)
extends Ordered[UInt] {

def +(that: UInt) = UInt(value + that.value)

def -(that: UInt) = UInt(value - that.value)

def *(that: UInt) = UInt(value * that.value)

def /(that: UInt) = UInt(value / that.value)

def <<(count: Int) = UInt(value << count)

def >>(count: Int) = UInt(value >>> count)

def &(that: UInt) = UInt(value & that.value)

def |(that: UInt) = UInt(value | that.value)

def ^(that: UInt) = UInt(value ^ that.value)

def unary_- = UInt(-value)

def unary_~ = UInt(~value)

def compare(that: UInt) = value.compare(that.value)

override def equals(o: Any) = o match {
case that: UInt => value == that.value
case _ => false
}

override def hashCode = value.hashCode

override def toString = value.toString
}

object UInt {
private final val mask = 0xFFFFFFFFL

final val zero = UInt(0L)

final val one = UInt(1L)

final val MinValue = UInt(0L)

final val MaxValue = UInt(mask)

implicit def charFitsUInt(value: Char) = UInt(value.toLong)

implicit def ordering = new Ordering[UInt] {
def compare(x: UInt, y: UInt) = x.compare(y)
}

implicit def bytePimp(x:Byte) = new {
def toUInt = if(x >= 0) UInt(x) else throw new
ArithmeticException("Invalid conversion!")
}

implicit def shortPimp(x:Short) = new {
def toUInt = if(x >= 0) UInt(x) else throw new
ArithmeticException("Invalid conversion!")
}

implicit def intPimp(x: Int) = new {
def toUInt = if (x >= 0) UInt(x) else throw new
ArithmeticException("Invalid conversion!")
}

// implicit def uintFitsLong(value:UInt) = value.value

def apply(value: Long) = new UInt(value & mask)
}

On 04/11/2011 20:34, Seyed H. HAERI (Hossein) wrote:

> But, as a C++ person, by design,

I don't think you are. Because if you where, you'd know that C++ has
it's own quirks in this area as well.

On 04/11/2011 22:56, Seyed H. HAERI (Hossein) wrote:

> No, that's not the culprit. I refer you (and the rest) back to my
> citation from the C++ Standard:

The C++ standard distinguishes between integer conversions and integer
promotions. You seem to have conveniently ignored the promotions part,
and the consequences.

 It's not example a "semantic problem" unless you feel
that programming languages should always do integer computations with
arbitrary precision or, failing that, always report an error if integer
overflow occurs. 

Vote me +1 for always reporting overflows. There may be practical reasons for not reporting overflows; but in general, I do not see how failing to reporting an obvious error condition can possibly result in a more reliable program.
Ken 

On Friday, November 4, 2011 10:47:36 AM UTC-5, Rex Kerr wrote:

Signed and unsigned arithmetic is simply _not_ that different from unsigned arithmetic.  With a type of width b bits, both are modulo 2^b; the only difference is that 0..(2^b-1) is chosen as the representation for one while (-2^(b-1)..(2^(b-1)-1)) is chosen for the other.  But it's really the same ring, and if you have a wider ring of width b+d, you can trivially restrict the range to the narrower ring.

So, bottom line is that you can just do all addition, subtraction, and multiplication just like you would before (assuming you're not promoting to 2b bits when you do multiplication but are staying within the ring), and restrict at the end.

Division needs to be done in the larger ring with the correct sign to emulate unsigned division in the smaller ring.

Bitwise operations can be done in the larger ring, but after that you need to restrict to the smaller ring before you do more arithmetic.

Bit shifts use >> for signed and >>> for unsigned bit shift.  If you are doing an unsigned shift in the large ring, make sure you use the unsigned representation.

To get from a smaller unsigned ring to a larger signed one, do a bit mask of the appropriate bits after (signed) conversion to the larger ring.

So there are a few things to learn.  But once you've learned them, if you have to use them ALL the time you can create your own set of methods; if you don't, just follow the rules for the bit of math you have to do.

But Rex, you're missing one of the key points of programming, which is that of moving to higher and higher levels of abstraction. I remember, a _long_ time ago, seeing arguments that modern programming languages were encouraging programmers to lose sight of the register model they were programming for. Of course that was the case!
You've quoted a number of rules that, if remembered by the programmer, will eliminate the original problem. My response is, every (arbitrary) rule that the programmer must remember decreases the reliability of the finished product. The _only_ reason to require programmers to remember such rules is that to not do so would incur unacceptable performance penalties.
Ken 

Overflow checking may result in a slower program but I tend to agree with you… I’d rather have it than not.

 

Peter

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of Ken McDonald
Sent: Saturday, November 05, 2011 12:21
To: scala-user@googlegroups.com
Subject: Re: [scala-user] Unsigned Arithmetic -- Humble Recommendation for Improving Scala

 

 It's not example a "semantic problem" unless you feel
that programming languages should always do integer computations with
arbitrary precision or, failing that, always report an error if integer
overflow occurs. 

Vote me +1 for always reporting overflows. There may be practical reasons for not reporting overflows; but in general, I do not see how failing to reporting an obvious error condition can possibly result in a more reliable program.

 

Ken 

On Sat, Nov 5, 2011 at 12:26 PM, Ken McDonald <ykkenmcd@gmail.com> wrote:

On Friday, November 4, 2011 10:47:36 AM UTC-5, Rex Kerr wrote:

So, bottom line is that you can just do all addition, subtraction, and multiplication just like you would before (assuming you're not promoting to 2b bits when you do multiplication but are staying within the ring), and restrict at the end.

Division needs to be done in the larger ring with the correct sign to emulate unsigned division in the smaller ring.

Bitwise operations can be done in the larger ring, but after that you need to restrict to the smaller ring before you do more arithmetic.

Bit shifts use >> for signed and >>> for unsigned bit shift.  If you are doing an unsigned shift in the large ring, make sure you use the unsigned representation.

To get from a smaller unsigned ring to a larger signed one, do a bit mask of the appropriate bits after (signed) conversion to the larger ring.

So there are a few things to learn.  But once you've learned them, if you have to use them ALL the time you can create your own set of methods; if you don't, just follow the rules for the bit of math you have to do.

But Rex, you're missing one of the key points of programming, which is that of moving to higher and higher levels of abstraction.

If you have to care about whether your integers are signed or unsigned, or how many bits are in them, you've already lost that level of abstraction.
 

I remember, a _long_ time ago, seeing arguments that modern programming languages were encouraging programmers to lose sight of the register model they were programming for. Of course that was the case!
You've quoted a number of rules that, if remembered by the programmer, will eliminate the original problem. My response is, every (arbitrary) rule that the programmer must remember decreases the reliability of the finished product. The _only_ reason to require programmers to remember such rules is that to not do so would incur unacceptable performance penalties.

Well, there's not much reason to care whether integers are signed or unsigned or to limit the number of bits unless you care about the performance.  So I'd say this covers the bulk of the cases where it's an issue at all.

  --Rex

Hi Alan,

> The C++ standard distinguishes between integer conversions and integer promotions.  You seem to have conveniently ignored the promotions part, and the consequences.

By coincidence, I quoted clause 1, section 4.5 which is the opening
clause of Integral Promotion in the 1998 standard.

TTFN,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Dear Rex, Peter, and Rüdiger (amongst others),

I have apparently managed to spread the wrong impression that I want
Scala to become just another C++. I don't want to do so -- I would
like to say clearly. The reason why I keep referring to the clause I
quoted from the C++ standard is to show where one ought to put special
care for overflow whilst mixing signed and unsigned values. So, for
the case of

val ch: Char = 65535
val i = ch * ch

using a simple logarithmic calculation, one could have realised that
31 bits is not enough for storing the value of i. So, one quick escape
for Scala could have for example be to resort to larger signed types
in Scala in such cases. C++ does put this special care but resorts to
the respective unsigned types. (See the clause I quotes a few times
from the C++ Standard.) Scala has failed to realise this. And, that's
the flaw that I've been speaking about.

The fact that * is just not directly defined on Char is irrelevant so
long as there is my second line above is a valid Scala piece of code.

TTFN,
--Hossein

P.S. Sorry if my words above don't read very well. It's been a very
long day and I'm too tired at the moment to accommodate enough
concentration. I also do apologise for not being prompt in responding.
I was really busy today...

On 5 November 2011 00:48, Rex Kerr wrote:
> Why do you persist in saying things like "would have stopped mistakenly
> representing it as a signed one" despite us repeatedly explaining that
>   (1) The JVM only does signed arithmetic, and trying to hide this fact will
> cause multiple bugs and/or sizable degradation in performance in unexpected
> places, and
>   (2) * is not defined on Char
>
> Char is not the commutative ring with unity ({0..65535},+,0,*,1) that
> unsigned short is in C++.  If you saw "Char" in Scala or "char" in Java and
> thought, "Oh, that's just like unsigned short in C++, which I know!", you
> were wrong.  Char is _only_ the set {0..65535}.  Granted, the documentation
> may not make this quite as clear as it ought to, but if you read what the
> actual specifications are, you'll realize it.  To persist in calling the
> behavior exhibited by Scala a "mistake" without addressing this point in
> detail is foolish or lazy.
>
> If you have an actual programming problem that you wish to solve, many of us
> are happy to help.  If you want Scala to work more like C++, without
> understanding the different constraints, so that you don't have to learn as
> much, I think you'll find considerably less sympathy.
>
>   --Rex
>
>
> On Fri, Nov 4, 2011 at 6:56 PM, Seyed H. HAERI (Hossein)
> wrote:
>>
>> When both multiplicands are unsigned, the result needs to be unsigned
>> too. If Scala had support for unsigned arithmetic of the right size
>> for Int, augmented with a similar rule to that of C++ above, it could
>> have simply realised that j needs to be an unsigned and it would have
>> stopped mistakenly representing it as a signed one.
>
>

Dear Peter,

>> When both multiplicands are unsigned, the result needs to be unsigned too.
>
> Scala isn't C++.

I didn't say it is. And, a language doesn't need to be C++ to adopt
such a simple rule.

> The Scala Reference Manual talks about these conversions in section 12.2.1 on Numeric Value Types. There Char is defined to be a "subrange type." It goes on to say

OK, thank you for finally bringing this up. Maybe I should apologise
for not asking for where to look to find the matter in the language
spec in the first place. Now that you have pointed out the right
place, I would like to quote the following from right there:

"Any numeric value type T supports the following methods." ... (2nd
bullet) "Arithmetic methods addition (+), subtraction (),
multiplication (*), ..." So, despite what other folks earlier on said
about this, Char does indeed have * defined on it.

> "Given two numeric value types S and T , the operation type of S and T is defined as follows: If both S and T are subrange types then the operation type of S and T is Int..."

There exactly is the flaw because it's not careful enough about false
overflow in the cases similar to my exemplification. I would like to
cordially recommend replacing the above sentence with something like
this one:

"If both S and T are subrange types, then the operation type of S and
T is Int or the smallest higher ranked numeric type in the above
diagram which is large enough not to lose any information from the
resulting value"

> it's just as arbitrary a choice as the one C++ makes.

I'm afraid not because the choice that C++ makes is not arbitrary at
all. C++ is prudent enough on moving to the unsigned respective type
when the signed counterpart is not large enough to store the value
without producing false overflow. Scala doesn't have this care and
that's the flaw.

> Since Scala doesn't have any unsigned integer types currently it's certainly a natural choice to make. Adding support for an unsigned type to Scala is a reasonable thing to think about,

Thanks! :)

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

> "If both S and T are subrange types, then the operation type of S and
> T is Int or the smallest higher ranked numeric type in the above
> diagram which is large enough not to lose any information from the
> resulting value"

I can appreciate what you are trying to accomplish with this but I'm worried
about the fact that the resulting type would be operation dependent. For
example Char * Char would have to return Long by this rule but Char + Char
would still return Int. Furthermore I think it's only the Char * Char
operation that would behave differently under your rule as compared with
what is currently in the SLR. For example Char * Short would continue being
Int under your rule.

Is it really worth cluttering up the specification to handle the one case of
Char * Char? I suppose that's a matter of opinion based on just how badly
one needs that operation. :)

Peter

On Sat, Nov 5, 2011 at 9:14 PM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

> The Scala Reference Manual talks about these conversions in section 12.2.1 on Numeric Value Types. There Char is defined to be a "subrange type." It goes on to say

"Any numeric value type T supports the following methods." ... (2nd
bullet) "Arithmetic methods addition (+), subtraction (),
multiplication (*), ..." So, despite what other folks earlier on said
about this, Char does indeed have * defined on it.

> "Given two numeric value types S and T , the operation type of S and T is defined as follows: If both S and T are subrange types then the operation type of S and T is Int..."

"...The operation is evaluated by converting the receiver and its argument to their operation type and performing the given arithmetic operation of that type."

This is why it's unclear.  The spec says that, say, Byte has * defined, and then turns around and says that what this means is that Byte is converted to Int and the Int * is used.  Rather than consider this a bizarre operation on bytes, it's much simpler (and is in fact what happens with the bytecode--there are only integer registers in the JVM bytecode, and if you need to get a byte from an array, for example, you have a special operation--baload in this case--to load it into the integer register) to consider this as type promotion followed by integer multiplication.

(If I were in charge of the spec, I'd rewrite the spec to be more obvious.)

Again: Char is not a commutative ring with unity; it's just a set.  Saying that Char has * defined is just a distraction, since * takes you out of the set (so it's not defined on that ring).

  --Rex