View mode: basic / threaded / horizontal-split · Log in · Help
February 16, 2010
Re: disabling unary "-" for unsigned types
Andrei Alexandrescu wrote:
> Walter Bright wrote:
>> Lutger wrote:
>>> It's a valid viewpoint, but it is a 'should'. I believe many 
>>> programmers have only passing familiarity if at all with the 
>>> semantics of unsigned types and floating point operations. At least 
>>> when coding, they don't have these semantics in mind. Why do you 
>>> think Java doesn't have unsigned types? 
>>
>> Naive programmers have trouble with Java floating point as well:
>>
>>     http://www.eecs.berkeley.edu/~wkahan/JAVAhurt.pdf
>>
>> There's just no getting around it. Should Java just remove floating 
>> point types as well?
>>
>> Heck, I knew a degree'd mechanical engineer who could not understand 
>> why his calculator kept giving him answers off by a factor of 2 (he 
>> refused to understand roundoff error, no matter how many times I tried 
>> to explain it to him - he believed that calculators had mathematically 
>> perfect arithmetic).
> 
> How could he refuse?

Beats me. Naturally, I lost all respect for his engineering prowess.

> One of my favorite games with calculators was to 
> successively extract square root of 2 until I got 1. The better the 
> calculator, the more steps it takes. That's kind of difficult to refuse 
> to acknowledge :o).
> 
> Andrei
February 16, 2010
Re: disabling unary "-" for unsigned types
On Tue, 16 Feb 2010 00:35:21 -0500, Ellery Newcomer  
<ellery-newcomer@utulsa.edu> wrote:

> On 02/15/2010 09:17 PM, Steven Schveighoffer wrote:
>> On Mon, 15 Feb 2010 21:32:21 -0500, Rainer Deyke <rainerd@eldwood.com>
>> wrote:
>>
>>> Ellery Newcomer wrote:
>>>> On 02/15/2010 05:33 PM, Steven Schveighoffer wrote:
>>>>> uint a = -1; // error
>>>>
>>>> I can't say I would appreciate having to write
>>>>
>>>> uint a = 0xFFFFFFFF;
>>>>
>>>> or the equivalent for ulong.
>>>
>>> uint a = ~0u;
>>
>> even ~0 works, no need for the u (although it makes things clearer).
>>
>> Ellery, you didn't read my original post thoroughly, I said this was the
>> most common case of wanting to use unary negative on an unsigned value,
>> and it's easily rewritten, with the same number of characters no less.
>>
>> -Steve
>
> Ohhh! that post! You're right; I missed that part.
>
> Alright, here's something I found myself writing just today or yesterday:
>
> //x,r are long, n is ulong
>
> if(x < 0){
>    ulong ux = -x;
>    ...
> }

I think at the same time you can assign an int to a uint without issue,  
assigning an int that is the result of a negation operator on a uint to  
another uint is a problem.  This means that the type of the expression:

-n

where n is unsigned can't simply be the signed version of n's type.  If it  
was, it would be impossible to tell the difference between assigning a  
negation of an unsigned value from a simple int result (which has a 50%  
chance of being positive).  I don't know how the internal workings of the  
compiler behave, but there has to be a way to single the bad case out.  We  
already have range propagation, this could simply be part of it.

>
> I also have
>
> if(r < 0){
>    return n - (-r) % n;
> }

This is fine, you are not assigning the negation of unsigned to an  
unsigned value.  Binary subtraction on unsigned and signed numbers is not  
as error prone.

>
> emphasis on ensuring dividend is positive before it gets promoted to  
> ulong, etc etc, and I do guard that r is not remotely close to  
> ulong.max/min.
>
> assuming that the return type is long (it isn't, but it might as well  
> be, since n is always within [2,long.max]) or gets assigned to long or  
> whatever.
>
> -The bottom one obeys your rules.
> -The top one doesn't.

The top is a good example.  It is not something I thought of, but I think  
in the end, it should be allowed.  Coming up with all the nuances of the  
behavior is key to finding a sound rule to try and implement, and how to  
explain its behavior through example.

-Steve
February 16, 2010
Re: disabling unary "-" for unsigned types
On Tue, 16 Feb 2010 01:10:33 -0500, Walter Bright  
<newshound1@digitalmars.com> wrote:

> Steven Schveighoffer wrote:
>> For example, there is no possible way a person unfamiliar with computers
>
> That's a valid argument if you're writing a spreadsheet program. But  
> programmers should be familiar with computers, and most definitely  
> should be familiar with 2's complement arithmetic.

What I meant by that statement is that the behavior goes against common  
sense -- when it doesn't have to.  It only makes sense to advanced  
programmers who understand the inner workings of the CPU and even in those  
cases, advance programmers easily make mistakes.

When the result of an operation is 99.999% of the time an error (in fact  
the exact percentage is (T.max-1)/T.max  * 100), disallowing it is worth  
making the rare valid uses of it illegal.

This is no different in my mind to requiring comparison of an object to  
null to use !is instead of !=.  If you remember, the compiler was  
dutifully doing exactly what the user wrote, but in almost all cases, the  
user really meant !is.

To re-iterate, I do *not* think unary - for unsigned types should be  
disabled.  But I think the expression:

x = -(exp)

where x is an unsigned type and exp is an unsigned type (or a literal that  
can be interpreted as unsigned), should be an error.  The only case where  
it works properly is when exp is 0.

Note that you can allow this behavior, which makes it more obvious:

x = 0 - (exp)

Because this is not unary negation.  It follows the rules of subtraction,  
which do not disallow wrapping past zero.

> Similarly, if you do much with floating point, you should be familiar  
> with "What Every Computer Scientist Should Know About Floating-Point  
> Arithmetic"
>
> http://docs.sun.com/source/806-3568/ncg_goldberg.html

Yes, but I'm not talking about normal math with unsigned types.  I'm  
talking about a corner case where it is almost always an error.  The case  
I'm talking about is the equivalent to doing:

x = x / 0;

for floating point.  One could argue that this should be statically  
disallowed, because it's guaranteed to be an error.  This doesn't mean  
that:

x = x / y;

should be disallowed because y *might* be zero.

-Steve
February 16, 2010
Re: disabling unary "-" for unsigned types
On 02/15/2010 09:15 PM, Steven Schveighoffer wrote:
>
> For example, there is no possible way a person unfamiliar with computers
> (and most programmers who have not run into this) would believe that
>
> b = 5;
> a = -b;
>

Tell any math major that fixnum arithmetic is really just arithmetic 
modulo 2^32 and they would believe you, even if they had never heard of 
computers

> would result in a being some large positive number. It's just totally
> unexpected, and totally avoidable.
>
> -Steve
February 16, 2010
Re: disabling unary "-" for unsigned types
On Tue, 16 Feb 2010 09:17:32 -0500, Ellery Newcomer  
<ellery-newcomer@utulsa.edu> wrote:

> On 02/15/2010 09:15 PM, Steven Schveighoffer wrote:
>>
>> For example, there is no possible way a person unfamiliar with computers
>> (and most programmers who have not run into this) would believe that
>>
>> b = 5;
>> a = -b;
>>
>
> Tell any math major that fixnum arithmetic is really just arithmetic  
> modulo 2^32 and they would believe you, even if they had never heard of  
> computers

But you don't designate it as such.  If it was required to designate  
modulo 32 in the expression, then it would be fine with me.  I went  
through Calc V and never really had to worry about this.  Advanced  
mathematicians are not a model for the everyday programmer :)

Even if you explain it to people, they still forget!  It's the same as !=  
null was.

-Steve
February 16, 2010
Re: disabling unary "-" for unsigned types
Ellery Newcomer wrote:
> On 02/15/2010 09:15 PM, Steven Schveighoffer wrote:
>>
>> For example, there is no possible way a person unfamiliar with computers
>> (and most programmers who have not run into this) would believe that
>>
>> b = 5;
>> a = -b;
>>
> 
> Tell any math major that fixnum arithmetic is really just arithmetic
> modulo 2^32 and they would believe you, even if they had never heard of
> computers
> 
>> would result in a being some large positive number. It's just totally
>> unexpected, and totally avoidable.
>>
>> -Steve

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

> Fast forward to 2006. I was shocked to learn that the binary search
> program that Bentley proved correct and subsequently tested in Chapter
> 5 of Programming Pearls contains a bug. Once I tell you what it is,
> you will understand why it escaped detection for two decades. Lest you
> think I'm picking on Bentley, let me tell you how I discovered the
> bug: The version of binary search that I wrote for the JDK contained
> the same bug. It was reported to Sun recently when it broke someone's
> program, after lying in wait for nine years or so.
>
> ...
>
> The bug is in this line:
>
> 6:             int mid = (low + high) / 2;
>
> ...
>
> In Programming Pearls, Bentley says "While the first binary search was
> published in 1946, the first binary search that works correctly for
> all values of n did not appear until 1962." The truth is, very few
> correct versions have ever been published, at least in mainstream
> programming languages.

It's fun to note that one of the fixes the author proposes in the
article was actually shown to itself be wrong... nearly two years later.

Clearly, knowing that computers use two's complement fixed-width integer
arithmetic is insufficient to write correct code.  To believe otherwise
is to believe that humans are infallible.

In which case, I have literature on the Invisible Pink Unicorn [1] that
might interest you...


[1] http://en.wikipedia.org/wiki/Invisible_Pink_Unicorn
February 16, 2010
Re: disabling unary "-" for unsigned types
On Tue, 16 Feb 2010 10:36:04 -0500, Daniel Keep  
<daniel.keep.lists@gmail.com> wrote:

>
> It's fun to note that one of the fixes the author proposes in the
> article was actually shown to itself be wrong... nearly two years later.
>
> Clearly, knowing that computers use two's complement fixed-width integer
> arithmetic is insufficient to write correct code.  To believe otherwise
> is to believe that humans are infallible.

Yes, but in this case, the solution was incorrect for a small number of  
inputs (arrays with length > 2^30).

For negation of unsigned values, the code is incorrect for all inputs  
except for zero.

Appropriately, one will notice something is wrong sooner than a decade.  I  
would postulate they should know instantaneously because the compiler  
should reject it :)

-Steve
February 16, 2010
Re: disabling unary "-" for unsigned types
== Quote from Daniel Keep (daniel.keep.lists@gmail.com)'s article
> Ellery Newcomer wrote:
> > On 02/15/2010 09:15 PM, Steven Schveighoffer wrote:
> >>
> >> For example, there is no possible way a person unfamiliar with computers
> >> (and most programmers who have not run into this) would believe that
> >>
> >> b = 5;
> >> a = -b;
> >>
> >
> > Tell any math major that fixnum arithmetic is really just arithmetic
> > modulo 2^32 and they would believe you, even if they had never heard of
> > computers
> >
> >> would result in a being some large positive number. It's just totally
> >> unexpected, and totally avoidable.
> >>
> >> -Steve
> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
> > Fast forward to 2006. I was shocked to learn that the binary search
> > program that Bentley proved correct and subsequently tested in Chapter
> > 5 of Programming Pearls contains a bug. Once I tell you what it is,
> > you will understand why it escaped detection for two decades. Lest you
> > think I'm picking on Bentley, let me tell you how I discovered the
> > bug: The version of binary search that I wrote for the JDK contained
> > the same bug. It was reported to Sun recently when it broke someone's
> > program, after lying in wait for nine years or so.
> >
> > ...
> >
> > The bug is in this line:
> >
> > 6:             int mid = (low + high) / 2;
> >
> > ...
> >
> > In Programming Pearls, Bentley says "While the first binary search was
> > published in 1946, the first binary search that works correctly for
> > all values of n did not appear until 1962." The truth is, very few
> > correct versions have ever been published, at least in mainstream
> > programming languages.
> It's fun to note that one of the fixes the author proposes in the
> article was actually shown to itself be wrong... nearly two years later.
> Clearly, knowing that computers use two's complement fixed-width integer
> arithmetic is insufficient to write correct code.  To believe otherwise
> is to believe that humans are infallible.
> In which case, I have literature on the Invisible Pink Unicorn [1] that
> might interest you...
> [1] http://en.wikipedia.org/wiki/Invisible_Pink_Unicorn

I **HATE** this example because it's a classic example of extreme nitpicking.  On
most modern computers, (void*).sizeof == size_t.sizeof.  Furthermore, usually half
your address space is reserved for kernel use.  Therefore, this bug would only
show up when you're searching an array of bytes **and** very close to exhausting
available address space (i.e. when you probably have bigger problems anyhow).  I
have intentionally written binary searches like this even though I'm aware of this
bug because it's more readable and efficient than doing it "right" and would only
fail in corner cases too extreme to be worth considering.
February 16, 2010
Re: disabling unary "-" for unsigned types
On Tue, 16 Feb 2010 10:53:40 -0500, dsimcha <dsimcha@yahoo.com> wrote:

> == Quote from Daniel Keep (daniel.keep.lists@gmail.com)'s article
>> Ellery Newcomer wrote:
>> > On 02/15/2010 09:15 PM, Steven Schveighoffer wrote:
>> >>
>> >> For example, there is no possible way a person unfamiliar with  
>> computers
>> >> (and most programmers who have not run into this) would believe that
>> >>
>> >> b = 5;
>> >> a = -b;
>> >>
>> >
>> > Tell any math major that fixnum arithmetic is really just arithmetic
>> > modulo 2^32 and they would believe you, even if they had never heard  
>> of
>> > computers
>> >
>> >> would result in a being some large positive number. It's just totally
>> >> unexpected, and totally avoidable.
>> >>
>> >> -Steve
>> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
>> > Fast forward to 2006. I was shocked to learn that the binary search
>> > program that Bentley proved correct and subsequently tested in Chapter
>> > 5 of Programming Pearls contains a bug. Once I tell you what it is,
>> > you will understand why it escaped detection for two decades. Lest you
>> > think I'm picking on Bentley, let me tell you how I discovered the
>> > bug: The version of binary search that I wrote for the JDK contained
>> > the same bug. It was reported to Sun recently when it broke someone's
>> > program, after lying in wait for nine years or so.
>> >
>> > ...
>> >
>> > The bug is in this line:
>> >
>> > 6:             int mid = (low + high) / 2;
>> >
>> > ...
>> >
>> > In Programming Pearls, Bentley says "While the first binary search was
>> > published in 1946, the first binary search that works correctly for
>> > all values of n did not appear until 1962." The truth is, very few
>> > correct versions have ever been published, at least in mainstream
>> > programming languages.
>> It's fun to note that one of the fixes the author proposes in the
>> article was actually shown to itself be wrong... nearly two years later.
>> Clearly, knowing that computers use two's complement fixed-width integer
>> arithmetic is insufficient to write correct code.  To believe otherwise
>> is to believe that humans are infallible.
>> In which case, I have literature on the Invisible Pink Unicorn [1] that
>> might interest you...
>> [1] http://en.wikipedia.org/wiki/Invisible_Pink_Unicorn
>
> I **HATE** this example because it's a classic example of extreme  
> nitpicking.  On
> most modern computers, (void*).sizeof == size_t.sizeof.  Furthermore,  
> usually half
> your address space is reserved for kernel use.  Therefore, this bug  
> would only
> show up when you're searching an array of bytes **and** very close to  
> exhausting
> available address space (i.e. when you probably have bigger problems  
> anyhow).  I
> have intentionally written binary searches like this even though I'm  
> aware of this
> bug because it's more readable and efficient than doing it "right" and  
> would only
> fail in corner cases too extreme to be worth considering.

Actually, this bug is more common than that; overflow can happen on arrays  
of length uint.max/2 and that's to say nothing of using 64-bit code. Also,  
the std.algorithm binary search routines use a different algorithm that  
appears to be safe to use. (Though they won't compile in 64-bit mode due  
to a minor bug)
February 16, 2010
Re: disabling unary "-" for unsigned types
On 02/16/2010 09:36 AM, Daniel Keep wrote:
>
>
> Ellery Newcomer wrote:
>> On 02/15/2010 09:15 PM, Steven Schveighoffer wrote:
>>>
>>> For example, there is no possible way a person unfamiliar with computers
>>> (and most programmers who have not run into this) would believe that
>>>
>>> b = 5;
>>> a = -b;
>>>
>>
>> Tell any math major that fixnum arithmetic is really just arithmetic
>> modulo 2^32 and they would believe you, even if they had never heard of
>> computers
>>
>
> It's fun to note that one of the fixes the author proposes in the
> article was actually shown to itself be wrong... nearly two years later.
>
> Clearly, knowing that computers use two's complement fixed-width integer
> arithmetic is insufficient to write correct code.  To believe otherwise
> is to believe that humans are infallible.

In the same vein, having opposable thumbs is insufficient to peel 
bananas. To believe otherwise is a failure in logic.

But I don't recall saying anywhere that writing correct code is possible.

I will say that if I wanted my code to be reasonably correct, I probably 
wouldn't use fixnum arithmetic.

OT: I kinda wish BigInt could be dropped in as a replacement for int 
with less hassle.

OT: has anyone written a wrapper for int/long/etc that throws exceptions 
on overflow/underflow? Maybe such a thing should exist in the standard 
library?
1 2 3 4 5 6 7 8
Top | Discussion index | About this forum | D home