On 11/24/14 4:54 AM, Don wrote:
> In D,  1u - 2u > 0u. This is defined behaviour, not an overflow.

I think I get what you mean, but overflow is also defined behavior (in D at least). -- Andrei

On Mon, 24 Nov 2014 12:54:58 +0000
Don via Digitalmars-d <digitalmars-d@puremagic.com> wrote:

> In D,  1u - 2u > 0u. This is defined behaviour, not an overflow.
this *is* overflow. D just has overflow result defined.

On Mon, 24 Nov 2014 12:54:58 +0000
Don via Digitalmars-d <digitalmars-d@puremagic.com> wrote:

> In D,  1u - 2u > 0u. This is defined behaviour, not an overflow.
p.s. sorry, of course this is not and overflow. this is underflow.

On Monday, 24 November 2014 at 16:00:53 UTC, ketmar via Digitalmars-d wrote:
> this *is* overflow. D just has overflow result defined.

So it basically is and isn't modular arithmetic at the same time? I think Ada got this right by providing the ability to specify the modulo value, so you can define:

type Weekday is mod 7;
type Byte is mod 256;

A solid solution solution is to provide «As if Infinitely Ranged Integer Model» where the compiler figures out how large integers are needed for computation and then does overflow detection when you truncate for storage:

http://resources.sei.cmu.edu/library/asset-view.cfm?assetid=9019

On Monday, 24 November 2014 at 16:45:35 UTC, Ola Fosheim Grøstad
wrote:
> On Monday, 24 November 2014 at 16:00:53 UTC, ketmar via Digitalmars-d wrote:
>> this *is* overflow. D just has overflow result defined.
>
> So it basically is and isn't modular arithmetic at the same time?

Overflow is part of modular arithmetic. However, there is no
signed and unsigned modular arithmetic, or, more precisely, they
are the same.

Computer words just aren't a good representation of integers.

You can either use modular arithmetic, which follows the common
arithmetic laws for addition and multiplication (commutativity,
associativity, etc., even most non-zero numbers have a
multiplicative inverse), but break the common ordering laws (a >=
0 && b >= 0 implies a+b >= 0).

Or you can use some other order preserving arithmetic (e.g.
saturating to min/max values), but that breaks the arithmetic
laws.

> I think Ada got this right by providing the ability to specify the modulo value, so you can define:
>
> type Weekday is mod 7;
> type Byte is mod 256;
>
> A solid solution solution is to provide «As if Infinitely Ranged Integer Model» where the compiler figures out how large integers are needed for computation and then does overflow detection when you truncate for storage:
>
> http://resources.sei.cmu.edu/library/asset-view.cfm?assetid=9019

You could just as well use a library like GMP.

On Monday, 24 November 2014 at 17:12:31 UTC, Matthias Bentrup wrote:
> Overflow is part of modular arithmetic. However, there is no
> signed and unsigned modular arithmetic, or, more precisely, they
> are the same.

Would you say that a phase that goes from 0…2pi overflows? Does polar coordinates overflow once every turn?

I'd say overflow/underflow means that the result is wrong. (Carry is not overflow per se).

> Or you can use some other order preserving arithmetic (e.g.
> saturating to min/max values), but that breaks the arithmetic
> laws.

I don't think it breaks them, but I think a system language would be better off by having explicit operators for alternative edge-case handling on a bit-fiddling type. E.g.:

a + b as regular addition
a (+) b as modulo arithmetic addition
a [+] b as clamped (saturating) addition

The bad behaviour of C-like languages is the implicit coercion to/from a bit-fiddling type. The bit-fiddling should be contained in expression where the programmer by choosing the type says "I am gonna do tricky bit hacks here". Just casting to uint does not convey that message in a clear manner.

>> A solid solution solution is to provide «As if Infinitely Ranged Integer Model» where the compiler figures out how large integers are needed for computation and then does overflow detection when you truncate for storage:
>>
>> http://resources.sei.cmu.edu/library/asset-view.cfm?assetid=9019
>
> You could just as well use a library like GMP.

I think the point with having compiler support is to retain most optimizations. The compiler select the most efficient representation based on the needed headroom and makes sure that overflow is recorded so that you can eventually respond to it.

If you couple AIR with constrained integer types, which Pascal and Ada has, then it can be very efficient in many cases.

On Monday, 24 November 2014 at 17:55:06 UTC, Ola Fosheim Grøstad wrote:
> I think the point with having compiler support is to retain most optimizations. The compiler select the most efficient representation based on the needed headroom and makes sure that overflow is recorded so that you can eventually respond to it.

It is also worth noting that Intel CPUs have 3 new instructions for working with large integers:

MULX and ADCX/ADOX.

http://www.intel.com/content/www/us/en/intelligent-systems/intel-technology/ia-large-integer-arithmetic-paper.html

So there is no reason to not go for it IMO.

On Monday, 24 November 2014 at 17:55:06 UTC, Ola Fosheim Grøstad
wrote:
> On Monday, 24 November 2014 at 17:12:31 UTC, Matthias Bentrup wrote:
>> Overflow is part of modular arithmetic. However, there is no
>> signed and unsigned modular arithmetic, or, more precisely, they
>> are the same.
>
> Would you say that a phase that goes from 0…2pi overflows? Does polar coordinates overflow once every turn?
>

No, sin and cos are periodic functions, but that doesn't mean
their arguments are modular. sin 4pi is well defined by e.g. the
taylor expansion of sin without any modular arithmetic at all.

> I'd say overflow/underflow means that the result is wrong. (Carry is not overflow per se).
>

There is no right or wrong in Mathematics, only true and false.
The result of modular addition with overflow is not wrong, it is
just different than the result of integer addition.

>> Or you can use some other order preserving arithmetic (e.g.
>> saturating to min/max values), but that breaks the arithmetic
>> laws.
>
> I don't think it breaks them, but I think a system language would be better off by having explicit operators for alternative edge-case handling on a bit-fiddling type. E.g.:
>
> a + b as regular addition
> a (+) b as modulo arithmetic addition
> a [+] b as clamped (saturating) addition
>
> The bad behaviour of C-like languages is the implicit coercion to/from a bit-fiddling type. The bit-fiddling should be contained in expression where the programmer by choosing the type says "I am gonna do tricky bit hacks here". Just casting to uint does not convey that message in a clear manner.
>

Agreed, though I don't like the explosion of new operators. I'd
prefer the C# syntax like check(<expression>), wrap(expression),
saturate(expression).

>>> A solid solution solution is to provide «As if Infinitely Ranged Integer Model» where the compiler figures out how large integers are needed for computation and then does overflow detection when you truncate for storage:
>>>
>>> http://resources.sei.cmu.edu/library/asset-view.cfm?assetid=9019
>>
>> You could just as well use a library like GMP.
>
> I think the point with having compiler support is to retain most optimizations. The compiler select the most efficient representation based on the needed headroom and makes sure that overflow is recorded so that you can eventually respond to it.
>
> If you couple AIR with constrained integer types, which Pascal and Ada has, then it can be very efficient in many cases.

And can fail spectacularly in others. The compiler always has to
prepare for the worst case, i.e. the largest integer size
possible, while in practice you may need that only for a few
extreme cases.

On Monday, 24 November 2014 at 19:06:35 UTC, Matthias Bentrup wrote:
> There is no right or wrong in Mathematics, only true and false.
> The result of modular addition with overflow is not wrong, it is
> just different than the result of integer addition.

I think we are talking past each other. In my view the term "overflow" has nothing to do with mathematics, overflow is a signal from the ALU that the computation is incorrect e.g. not in accordance with the intended type.

> Agreed, though I don't like the explosion of new operators. I'd
> prefer the C# syntax like check(<expression>), wrap(expression),
> saturate(expression).

Yep, that is another way to do it. What is preferable probably varies from case to case.

> And can fail spectacularly in others. The compiler always has to
> prepare for the worst case, i.e. the largest integer size
> possible, while in practice you may need that only for a few
> extreme cases.

In some loops it probably can get tricky to get it right without help from the programmer. I believe some languages allow you to annotate loops with an upper boundary to help the semantic analysis, but you could also add more frequent overflow checks on request?

On 11/24/2014 2:20 AM, Don wrote:
>> I believe I do understand the problem. As a practical matter, overflow checks
>> are not going to be added for performance reasons.
>
> The performance overhead would be practically zero. All we would need to do, is
> restrict array slices such that the length cannot exceed ssize_t.max.
>
> This can only happen in the case where the element type has a size of 1, and
> only in the case of slicing a pointer, concatenation, and memory allocation.

(length1 + length2) / 2


> In exchange, 99% of uses of unsigned would disappear from D code, and with it, a
> whole category of bugs.

You're not proposing changing size_t, so I believe this statement is incorrect.


>> Also, in principle, uint-uint can generate a runtime check for underflow (i.e.
>> the carry flag).
>
> No it cannot. The compiler does not have enough information to know if the value
> is intended to be positive integer, or an unsigned. That information is lost
> from the type system.
>
> Eg from C, wrapping of an unsigned type is not an error. It is perfectly defined
> behaviour. With signed types, it's undefined behaviour.

I know it's not an error. It can be defined to be an error, and the compiler can insert a runtime check. (I'm not proposing this, just saying it can be done.)


> To make this clear: I am not proposing that size_t should be changed.
> I am proposing that for .length returns a signed type, that for array slices is
> guaranteed to never be negative.

There'll be mass confusion if .length is not the same type as .sizeof