February 16, 2010
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
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
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
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
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

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
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
== 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
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
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?