On 21 May 2021, EricP wrote
(in article <xMQpI.147659$Ms7.52969@fx34.iad>):

> Stephen Fuld wrote:
> > On 5/19/2021 8:47 AM, EricP wrote:
> > > MitchAlsup wrote:
> > > > On Wednesday, May 19, 2021 at 7:23:04 AM UTC-5, Anton Ertl wrote:
> > > > > Thomas Koenig <tko...@netcologne.de> writes:
> > > > > > Anton Ertl<an...@mips.complang.tuwien.ac.at> schrieb:
> > > > > > > Thomas Koenig <tko...@netcologne.de> writes:
> > > > > > > > Unsigned loops can cause a headache, because it is often not
> > > > > > > > possible to prove they actually terminate...
> > > > > > > And the difference to signed loops is? Note that you wrote
> > > > > > > "actually", so pretending that signed overflow does not happen
> > > > > > > does not count.
> > > > > > According to many language definitions, it does indeed not count.
> > > > > This sentence makes no sense.
> > > > <
> > > > How about this::
> > > > <
> > > > Languages, that want to be ported across multiple architectures, and
> > > > have high performing implementations, cannot specify that signed
> > > > integers overflow.
> > > > <
> > >
> > > The language spec should:
> > > - allow the programmer to choose between bounds-range checked,
> > > unchecked, modulo, or saturating data types
> >
> > Ada allows range checked, i.e. Range 20-100, unchecked, at least within
> > the limits of the size, and Modulo variables. I suspect adding
> > saturated wouldn't be a big stretch if it were popular enough.
> > Saturating would be pretty inexpensive to check, especially if you have
> > something like a CMOV instruction.
> >
> >
> > > - specify that range and array bounds checks can be enabled or disabled
> > > at compile time by command line options or inline pragmas,
> > > for blocks of code, individual data types, or individual objects.
> >
> > Since Ada supports Range attributes, and you can use a range restricted
> > variable as a subscript or loop limit, I think you can do all of that.
> >
> > But Nick Holsti is the Ada expert around here, so perhaps he will chime in.
>
> Ada defines support for checked signed integers,
> and later added unchecked modulo integers.
> Checked signed integers and floats can have arbitrary subtype ranges.
> So that part matches what I said.
>
> I like most of the Ada's subtyping. I eventually came to disliked that
> subtype conversions were automatic. The problem is that a subtype range
> check can raise an exception but that was invisible in the source code.

Just like an overflow in fact.
> I would prefer
> c = Char (i);
> as that gives you a heads-up that a conversion is taking place.
> Basically I prefer what C with warnings does.

If i is an Integer and c a Character, then

c := i;

is not legal Ada. You would have to write:

c := Character'Pos(i);

and a compiler can easily warn you that i may not be in range.
If you ignore that warning, it may fail at runtime, depending on i.
What it will NOT do is silently lose data by truncating i.

--
Bill Findlay

MitchAlsup <MitchAlsup@aol.com> schrieb:

> This brings to mind that the whole concept of arithmetic exceptions is
> fundamentally flawed.
><
> It is not the arithmetic that should be checked for out-of-range values
> it is the depositing of values into containers that should be checked.

What about intermediate values?

If you calculate (a + b) - c, where a + b overflows and
(a - c) + b does not, what should the result be?

On 2021-05-22 3:10, Bill Findlay wrote:
> On 21 May 2021, EricP wrote

...

>> I like most of the Ada's subtyping. I eventually came to disliked that
>> subtype conversions were automatic. The problem is that a subtype range
>> check can raise an exception but that was invisible in the source code.
>
> Just like an overflow in fact.

If you don't want implicit/invisible range checks, use types instead of
subtypes and add the (now required) explicit type conversions.

However, even in an assignment of a type T expression to a type T
variable (which of course does not require a type conversion) there is a
range check that can fail if the value of the expression violates the
constraints of the type. For example:

type T is new Integer range 1 .. 10;
-- The computational range is at least signed 16 bits, although
-- every object of this type is constrained to 1 .. 10.

ten : constant T := 10;

x : T := ten * ten;
-- Constraint_Error exception because 100 is not in 1 .. 10.

>> I would prefer
>> c = Char (i);
>> as that gives you a heads-up that a conversion is taking place.
>> Basically I prefer what C with warnings does.
>
> If i is an Integer and c a Character, then
>
> c := i;
>
> is not legal Ada. You would have to write:
>
> c := Character'Pos(i);

Yes, but of course you meant

c := Character'Val(i);

The 'Pos attribute maps in the other direction, as in

i := Character'Pos(c);

("Pos" is an abbreviation of "position number", and "Val" of "value.")

> and a compiler can easily warn you that i may not be in range.
> If you ignore that warning, it may fail at runtime, depending on i.
> What it will NOT do is silently lose data by truncating i.

Moreover, the current state of the art in Ada programming for
high-integrity applications is to use a static-analysis tool or prover
to show statically that "i" is always in range, and generally that no
run-time checks can fail. It is then safe to disable those checks,
unless one is worried about HW errors that make the static analysis invalid.

Thomas Koenig <tkoenig@netcologne.de> writes:
>MitchAlsup <MitchAlsup@aol.com> schrieb:
>> It is not the arithmetic that should be checked for out-of-range values
>> it is the depositing of values into containers that should be checked.
>
>What about intermediate values?
>
>If you calculate (a + b) - c, where a + b overflows and
>(a - c) + b does not, what should the result be?

For this example it is relatively cheap to compute with enough
precision and check afterwards. But for a*b*c*d*e, it is quite a bit
more expensive. Fortunately, such cases are rare.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>>MitchAlsup <MitchAlsup@aol.com> schrieb:
>>> It is not the arithmetic that should be checked for out-of-range values
>>> it is the depositing of values into containers that should be checked.
>>
>>What about intermediate values?
>>
>>If you calculate (a + b) - c, where a + b overflows and
>>(a - c) + b does not, what should the result be?
>
> For this example it is relatively cheap to compute with enough
> precision and check afterwards.

Checking does not absolve from defining what the result is
supposed to be.

For example, in Fortran, this is clearly defined: The compiler
can reorder a + b - a to b, but it must respect parentheses,
so my question would have a clear answer using Fortran rules
(it would overflow).

It would be not defined in the absence of parentheses, because
the compiler would be free to reorder a + b - c to a - c + b if
it so desired.

So, I don't think the concept of checking only on storage to
"containers" works well.

Bill Findlay wrote:
> On 21 May 2021, EricP wrote
>>
>> I like most of the Ada's subtyping. I eventually came to disliked that
>> subtype conversions were automatic. The problem is that a subtype range
>> check can raise an exception but that was invisible in the source code.
>
> Just like an overflow in fact.

It is an overflow that can occur on an assignment
which for me gives it a higher surprise factor.

Requiring an explicit conversion makes the programmer
acknowledge that they know they are changing container sizes.

>> I would prefer
>> c = Char (i);
>> as that gives you a heads-up that a conversion is taking place.
>> Basically I prefer what C with warnings does.
>
> If i is an Integer and c a Character, then
>
> c := i;
>
> is not legal Ada.

Right, but it is how I would do it,
and is how pretty much every other language except Ada handles chars.

> You would have to write:
>
> c := Character'Pos(i);
>
> and a compiler can easily warn you that i may not be in range.
> If you ignore that warning, it may fail at runtime, depending on i.
> What it will NOT do is silently lose data by truncating i.

Yes, a consequence of Ada defining characters as an enumerated type
with 8-bit size but which can only hold the Ascii values 0..127.
Unfortunately real world characters are bytes containing
values in the range 0..255.

On 2021-05-22 16:42, EricP wrote:
> Bill Findlay wrote:
>> On 21 May 2021, EricP wrote
>>>
>>> I like most of the Ada's subtyping. I eventually came to disliked that
>>> subtype conversions were automatic. The problem is that a subtype range
>>> check can raise an exception but that was invisible in the source code.
>>
>> Just like an overflow in fact.
>
> It is an overflow that can occur on an assignment
> which for me gives it a higher surprise factor.
>
> Requiring an explicit conversion makes the programmer
> acknowledge that they know they are changing container sizes.
>
>>> I would prefer
>>> c = Char (i);
>>> as that gives you a heads-up that a conversion is taking place.
>>> Basically I prefer what C with warnings does.
>>
>> If i is an Integer and c a Character, then
>>
>> c := i;
>>
>> is not legal Ada.
>
> Right, but it is how I would do it,

Huh? Above you said you would "prefer" c = Char(i), which is essentially
the Ada way except that Ada uses the 'Val attribute of the target type
for this conversion (not 'Pos as Bill wrote by mistake).

> and is how pretty much every other language except Ada handles chars.

No, at least Pascal also has characters that are not integers.

>> You would have to write:
>>
>> c := Character'Pos(i);
>>
>> and a compiler can easily warn you that i may not be in range.
>> If you ignore that warning, it may fail at runtime, depending on i.
>> What it will NOT do is silently lose data by truncating i.
>
> Yes, a consequence of Ada defining characters as an enumerated type
> with 8-bit size but which can only hold the Ascii values 0..127.

Wrong, Ada's Character type is 8-bit Latin-1, and Ada also has
Wide_Character for 16-bit and Wide_Wide_Character for 32-bit UNICODE
encodings (ISO/IEC 10646:2011).

Niklas Holsti wrote:
> On 2021-05-22 16:42, EricP wrote:
>> Bill Findlay wrote:
>>> On 21 May 2021, EricP wrote
>>>>
>>>> I like most of the Ada's subtyping. I eventually came to disliked that
>>>> subtype conversions were automatic. The problem is that a subtype range
>>>> check can raise an exception but that was invisible in the source code.
>>>
>>> Just like an overflow in fact.
>>
>> It is an overflow that can occur on an assignment
>> which for me gives it a higher surprise factor.
>>
>> Requiring an explicit conversion makes the programmer
>> acknowledge that they know they are changing container sizes.
>>
>>>> I would prefer
>>>> c = Char (i);
>>>> as that gives you a heads-up that a conversion is taking place.
>>>> Basically I prefer what C with warnings does.
>>>
>>> If i is an Integer and c a Character, then
>>>
>>> c := i;
>>>
>>> is not legal Ada.
>>
>> Right, but it is how I would do it,
>
>
> Huh? Above you said you would "prefer" c = Char(i), which is essentially
> the Ada way except that Ada uses the 'Val attribute of the target type
> for this conversion (not 'Pos as Bill wrote by mistake).

I meant the c = Char (i); that I said earlier.
And no, I do not want to type Character'val(i).

And in Ada83 it is definitely not the same.

>> and is how pretty much every other language except Ada handles chars.
>
>
> No, at least Pascal also has characters that are not integers.

I am fine with characters that are a derived type.
I am not fine with Ada83's characters as an enumerated type 0..127.
They changed it later, but the damage was done and people had moved on.

>>> You would have to write:
>>>
>>> c := Character'Pos(i);
>>>
>>> and a compiler can easily warn you that i may not be in range.
>>> If you ignore that warning, it may fail at runtime, depending on i.
>>> What it will NOT do is silently lose data by truncating i.
>>
>> Yes, a consequence of Ada defining characters as an enumerated type
>> with 8-bit size but which can only hold the Ascii values 0..127.
>
>
> Wrong, Ada's Character type is 8-bit Latin-1, and Ada also has
> Wide_Character for 16-bit and Wide_Wide_Character for 32-bit UNICODE
> encodings (ISO/IEC 10646:2011).

Ada83 defines the data type Character as an enumerated type
in the package Standard, with values from 0..127 and a
size clause setting it to 8-bits.
(Note that support for size clauses is implementation dependent
so you can't count on a Character actually being 8 bits).

That made it impossible to have a buffer that contained
characters and normal byte values outside the range 0..127,
and why you have to type Character'val(i) instead of
something simple like Char(i).

Ada83 Language Reference Manual
http://archive.adaic.com/standards/83lrm/html/ada_lrm.html

Ada83 C. Predefined Language Environment
http://archive.adaic.com/standards/83lrm/html/lrm-C.html

Ada95 still defined type Character as an enumerated type in the
package Standard, but values have been added between 128..255,
and it allowed 8-bit and 16-bit characters,
as well as implementation-specified character sets,
and the definition of an enumerated type has been "enhanced" to hack
around its type restrictions and allow and even wider value set.

However most people who tried Ada83 moved on before Ada95 was available.

If originally Ada83 had defined type Character as a derived integer type,
and subtype Char as Character range 0..255,
none of the problems would have occurred,
and c = Char(i) would work just fine,
and you can talk to your VT100 or PC using its extended characters,
and read or write records to files with normal byte buffers,
without massive dicking about in code.

Thomas Koenig <tkoenig@netcologne.de> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>>If you calculate (a + b) - c, where a + b overflows and
>>>(a - c) + b does not, what should the result be?
>>
>> For this example it is relatively cheap to compute with enough
>> precision and check afterwards.
>
>Checking does not absolve from defining what the result is
>supposed to be.

In a language that checks on storage, I expect that the language
supports the mathematical illusion. So the result would a a
wide-enough representation of the result of the operation on
mathematical integers.

So if (a+b)-c may need 66 bits, you need at least 66 bits before range
checking. In such a language it may be beneficial to define somewhat
smaller variable ranges such that you can still make do with 64-bit
intermediate results in most cases. But even with 64-bit a, b, and c,
this particular expression just costs two adds and two adcs; that's
what I meant with "relatively cheap".

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 2021-05-22 19:16, EricP wrote:
> Niklas Holsti wrote:
>> On 2021-05-22 16:42, EricP wrote:
>>> Bill Findlay wrote:
>>>> On 21 May 2021, EricP wrote
>>>>>
>>>>> I like most of the Ada's subtyping. I eventually came to disliked that
>>>>> subtype conversions were automatic. The problem is that a subtype
>>>>> range
>>>>> check can raise an exception but that was invisible in the source
>>>>> code.
>>>>
>>>> Just like an overflow in fact.
>>>
>>> It is an overflow that can occur on an assignment
>>> which for me gives it a higher surprise factor.
>>>
>>> Requiring an explicit conversion makes the programmer
>>> acknowledge that they know they are changing container sizes.
>>>
>>>>> I would prefer
>>>>> c = Char (i);
>>>>> as that gives you a heads-up that a conversion is taking place.
>>>>> Basically I prefer what C with warnings does.
>>>>
>>>> If i is an Integer and c a Character, then
>>>>
>>>> c := i;
>>>>
>>>> is not legal Ada.
>>>
>>> Right, but it is how I would do it,
>>
>>
>> Huh? Above you said you would "prefer" c = Char(i), which is
>> essentially the Ada way except that Ada uses the 'Val attribute of the
>> target type for this conversion (not 'Pos as Bill wrote by mistake).
>
> I meant the c = Char (i); that I said earlier.
> And no, I do not want to type Character'val(i).

Ok, if you like abbreviations, I can understand your dislike for Ada.

> And in Ada83 it is definitely not the same.

"Ada" today does not mean Ada83. It means Ada2012
(http://www.ada-auth.org/standards/ada12.html) and pretty soon it will
mean Ada202x, probably with x = 2.

On Saturday, May 22, 2021 at 3:09:01 AM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > This brings to mind that the whole concept of arithmetic exceptions is
> > fundamentally flawed.
> ><
> > It is not the arithmetic that should be checked for out-of-range values
> > it is the depositing of values into containers that should be checked.
> What about intermediate values?
>
> If you calculate (a + b) - c, where a + b overflows and
> (a - c) + b does not, what should the result be?
<
You snipped the part about x,y, and z being in the range [10..90].
There is no current machine where the given ranges will overflow.
This would require a 6-bit integer machine, BTW.

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Saturday, May 22, 2021 at 3:09:01 AM UTC-5, Thomas Koenig wrote:
>> MitchAlsup <Mitch...@aol.com> schrieb:
>> > This brings to mind that the whole concept of arithmetic exceptions is
>> > fundamentally flawed.
>> ><
>> > It is not the arithmetic that should be checked for out-of-range values
>> > it is the depositing of values into containers that should be checked.
>> What about intermediate values?
>>
>> If you calculate (a + b) - c, where a + b overflows and
>> (a - c) + b does not, what should the result be?
><
> You snipped the part about x,y, and z being in the range [10..90].
> There is no current machine where the given ranges will overflow.
> This would require a 6-bit integer machine, BTW.

So, what should happen when the ranges come close to machine
ranges?

Thomas Koenig wrote:
> MitchAlsup <MitchAlsup@aol.com> schrieb:
>> On Saturday, May 22, 2021 at 3:09:01 AM UTC-5, Thomas Koenig wrote:
>>> MitchAlsup <Mitch...@aol.com> schrieb:
>>>> This brings to mind that the whole concept of arithmetic exceptions is
>>>> fundamentally flawed.
>>>> <
>>>> It is not the arithmetic that should be checked for out-of-range values
>>>> it is the depositing of values into containers that should be checked.
>>> What about intermediate values?
>>>
>>> If you calculate (a + b) - c, where a + b overflows and
>>> (a - c) + b does not, what should the result be?
>> <
>> You snipped the part about x,y, and z being in the range [10..90].
>> There is no current machine where the given ranges will overflow.
>> This would require a 6-bit integer machine, BTW.
>
> So, what should happen when the ranges come close to machine
> ranges?

Lets say a,b,c,d are in range [10..90] which requires
8 bits as signed integers. d = (a + b) - c;

"(a + b) - c" needs N+2 = 10 bits to represent the intermediate results.

If the machine word size >= 10 bits then a compiler can trivially prove
that the register will not overflow in that expression calculation.

If the detection of overflow in this ISA is inconvenient, like on a RISC-V,
then a compiler can use that the above proof to eliminate the code that
detects intermediate overflows.

That leaves the result assignment which must be checked against
d's range of [10..90].

If this same code was compiled on a 8-bit processor then the
intermediate result might overflow. Compiler has 2 options:
- perform the calculation in 8 bits and detect intermediate overflow
whatever the cost in this ISA
- promote the intermediate values to double-wide and perform calculation
using double wide arithmetic without intermediate overflow.

In either case, the result must also be range checked because
d's range is smaller than either register result container.

In all cases the result is either the arithmetically correct result
within the range of the individual variables, or overflow is detected.

MitchAlsup wrote:
> On Friday, May 21, 2021 at 5:00:17 PM UTC-5, Stephen Fuld wrote:
>> On 5/21/2021 12:40 PM, EricP wrote:
>>> Stephen Fuld wrote:
>>>> On 5/20/2021 9:34 AM, MitchAlsup wrote:
>>>>> On Thursday, May 20, 2021 at 10:08:32 AM UTC-5, Stephen Fuld wrote:
>>>>>> On 5/19/2021 11:40 PM, Niklas Holsti wrote:
>>>>>>> On 2021-05-20 3:40, Stephen Fuld wrote:
>>>>>>>> On 5/19/2021 8:47 AM, EricP wrote:
>>>>>
>>>>>> Fair enough. This sort of gets back to the question of whether to add a
>>>>>> feature like this as an attribute of the variable (e.g. range) or of
>>>>>> the
>>>>>> operation (e.g. bignum). I think there are arguments for each.
>>>>>>
>>>>>> BTW, I am unsure of what the requirement is here. Suppose you have a
>>>>>> variable with a range of 10-90. Do you want saturation at 90? That is
>>>>> <
>>>>> If the value to be written is outside of the range [10..90] you raise an
>>>>> exception. The raised exception decides what to do.
>>>>
>>>> Certainly true for the non-saturating case, and is what Ada does. My
>>>> question is if you define saturating variables, what to do if you
>>>> somehow define the variable with a range *and* saturating.
>>>
>>> Any variables that are smaller than the machine register size are
>>> promoted to that size by either sign or zero extension.
>>>
>>> Expressions are executed using signed or unsigned checked or saturating
>>> operations at that machine size. This detects intermediate signed or
>>> unsigned overflows of the machine size results.
>>>
>>> I have instructions for trap on unsigned carry or signed overflow.
>>> I have an ADGO Add Generate Overflow and ADGC Add Generate Carry
>>> to set a 1 in the output register for overflow or carry.
>>> Then a LIC Load Immediate Conditional loads saturation limit values.
>>> One could have arithmetic instructions that saturate.
>>>
>>> The result is copied back to the variable. If there are constraints on
>>> the variable different from the limits on the physical register
>>> then those are range checked and either saturated or trapped.
>>> A CMPGT and CMPLT with a LIC loads upper or lower saturation value.
>>>
>>> Note that setting limits on variable to be in the range 10..90 does
>>> not mean that expression intermediate results are within that range.
>>> It means an expression EITHER produces the arithmetically correct result
>>> in that range, or it saturates or traps.
> <
>> That is certainly one way to do it. All the different ways have
>> drawbacks. Mitch pointed out some of the ones for you choice in his
>> followup.
>>
>> I don't know enough to have strong feelings as to the best choice. As
>> Thomas Koening said earlier in this thread, it takes a lot of thought.
> <
> This brings to mind that the whole concept of arithmetic exceptions is
> fundamentally flawed.
> <
> It is not the arithmetic that should be checked for out-of-range values
> it is the depositing of values into containers that should be checked.

I agree:

It is my strong and not so humble opinion that a cpu/program/language
should always be free to deliver the best result it can, i.e. even if an
intermediate results would overflow/trap on most other CPUs.

If the final result delivered is in range, and mathematically correct,
then use it, otherwise trap at that point.

It is typically more prevalent on FP where some architectures can
deliver results that are closer to the mathematical definition than
others (long double intermediates etc), but the recent uint16_t example
shows that this can be an issue for integer ops as well.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

EricP wrote:
> Bill Findlay wrote:
>> On 21 May 2021, EricP wrote
>>>
>>> I like most of the Ada's subtyping. I eventually came to disliked that
>>> subtype conversions were automatic. The problem is that a subtype range
>>> check can raise an exception but that was invisible in the source code.
>>
>> Just like an overflow in fact.
>
> It is an overflow that can occur on an assignment
> which for me gives it a higher surprise factor.
>
> Requiring an explicit conversion makes the programmer
> acknowledge that they know they are changing container sizes.
>
>>> I would prefer
>>> c = Char (i);
>>> as that gives you a heads-up that a conversion is taking place.
>>> Basically I prefer what C with warnings does.
>>
>> If i is an Integer and c a Character, then
>>
>> c := i;
>>
>> is not legal Ada.
>
> Right, but it is how I would do it,
> and is how pretty much every other language except Ada handles chars.
>
>> You would have to write:
>>
>> c := Character'Pos(i);
>>
>> and a compiler can easily warn you that i may not be in range.
>> If you ignore that warning, it may fail at runtime, depending on i.
>> What it will NOT do is silently lose data by truncating i.
>
> Yes, a consequence of Ada defining characters as an enumerated type
> with 8-bit size but which can only hold the Ascii values 0..127.
> Unfortunately real world characters are bytes containing
> values in the range 0..255.

Not true any more:

A huge majority of all real-world characters are unicode stored as utf8
these days, needing 20+ bits, but since they are in fact compressed into
that utf8 encoding, individual characters often make do with just 7 bits
(stored as single 8-bit bytes).

You still need a data type capable of handling all the legal unicode
values if you want to do operations on individual chars and not just on
parts of a utf8 storage format string.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Saturday, May 22, 2021 at 2:46:10 PM UTC-5, EricP wrote:
> Thomas Koenig wrote:
> > MitchAlsup <Mitch...@aol.com> schrieb:
> >> On Saturday, May 22, 2021 at 3:09:01 AM UTC-5, Thomas Koenig wrote:
> >>> MitchAlsup <Mitch...@aol.com> schrieb:
> >>>> This brings to mind that the whole concept of arithmetic exceptions is
> >>>> fundamentally flawed.
> >>>> <
> >>>> It is not the arithmetic that should be checked for out-of-range values
> >>>> it is the depositing of values into containers that should be checked.
> >>> What about intermediate values?
> >>>
> >>> If you calculate (a + b) - c, where a + b overflows and
> >>> (a - c) + b does not, what should the result be?
> >> <
> >> You snipped the part about x,y, and z being in the range [10..90].
> >> There is no current machine where the given ranges will overflow.
> >> This would require a 6-bit integer machine, BTW.
> >
> > So, what should happen when the ranges come close to machine
> > ranges?
> Lets say a,b,c,d are in range [10..90] which requires
> 8 bits as signed integers. d = (a + b) - c;
>
> "(a + b) - c" needs N+2 = 10 bits to represent the intermediate results.
>
> If the machine word size >= 10 bits then a compiler can trivially prove
> that the register will not overflow in that expression calculation.
>
> If the detection of overflow in this ISA is inconvenient, like on a RISC-V,
> then a compiler can use that the above proof to eliminate the code that
> detects intermediate overflows.
<
Or if there is easy access to [u]int128_t, as there is in My 66000, then
simply have the compiler construct overflow-free code sequences.
>
> That leaves the result assignment which must be checked against
> d's range of [10..90].
>
> If this same code was compiled on a 8-bit processor then the
> intermediate result might overflow. Compiler has 2 options:
> - perform the calculation in 8 bits and detect intermediate overflow
> whatever the cost in this ISA
> - promote the intermediate values to double-wide and perform calculation
> using double wide arithmetic without intermediate overflow.
>
> In either case, the result must also be range checked because
> d's range is smaller than either register result container.
>
> In all cases the result is either the arithmetically correct result
> within the range of the individual variables, or overflow is detected.

EricP <ThatWouldBeTelling@thevillage.com> schrieb:

> Lets say a,b,c,d are in range [10..90] which requires
> 8 bits as signed integers. d = (a + b) - c;
>
> "(a + b) - c" needs N+2 = 10 bits to represent the intermediate results.
>
> If the machine word size >= 10 bits then a compiler can trivially prove
> that the register will not overflow in that expression calculation.
>
> If the detection of overflow in this ISA is inconvenient, like on a RISC-V,
> then a compiler can use that the above proof to eliminate the code that
> detects intermediate overflows.

>
> That leaves the result assignment which must be checked against
> d's range of [10..90].
>
> If this same code was compiled on a 8-bit processor then the
> intermediate result might overflow. Compiler has 2 options:
> - perform the calculation in 8 bits and detect intermediate overflow
> whatever the cost in this ISA

[...]

Costly, but doable.

> - promote the intermediate values to double-wide and perform calculation
> using double wide arithmetic without intermediate overflow.

Much more costly.

Also, in the case of multiplication or exponentiation (OK, I am
moving goalposts here a bit), there is no guararantee that even
double wide arithmetic will work without intermediate overflow.
You would be asking for infinite precision intermediate arithmetic.

I am starting to like the "exception on overflow" idea better
and better...

I forgot about this in my drafts folder...

MitchAlsup wrote:
> On Friday, May 21, 2021 at 2:41:13 PM UTC-5, EricP wrote:
>> Stephen Fuld wrote:
>>> On 5/20/2021 9:34 AM, MitchAlsup wrote:
>>>> On Thursday, May 20, 2021 at 10:08:32 AM UTC-5, Stephen Fuld wrote:
>>>>> On 5/19/2021 11:40 PM, Niklas Holsti wrote:
>>>>>> On 2021-05-20 3:40, Stephen Fuld wrote:
>>>>>>> On 5/19/2021 8:47 AM, EricP wrote:
>>>>> Fair enough. This sort of gets back to the question of whether to add a
>>>>> feature like this as an attribute of the variable (e.g. range) or of the
>>>>> operation (e.g. bignum). I think there are arguments for each.
>>>>>
>>>>> BTW, I am unsure of what the requirement is here. Suppose you have a
>>>>> variable with a range of 10-90. Do you want saturation at 90? That is
>>>> <
>>>> If the value to be written is outside of the range [10..90] you raise an
>>>> exception. The raised exception decides what to do.
>>> Certainly true for the non-saturating case, and is what Ada does. My
>>> question is if you define saturating variables, what to do if you
>>> somehow define the variable with a range *and* saturating.
> <
>> Any variables that are smaller than the machine register size are
>> promoted to that size by either sign or zero extension.
>>
>> Expressions are executed using signed or unsigned checked or saturating
>> operations at that machine size. This detects intermediate signed or
>> unsigned overflows of the machine size results.
>>
>> I have instructions for trap on unsigned carry or signed overflow.
>> I have an ADGO Add Generate Overflow and ADGC Add Generate Carry
>> to set a 1 in the output register for overflow or carry.
> <
> And throw the actual add away ?
> <

Yes. It is similar idea to MULL and MULH.

One does an ADD for the result, and a ADGO to get the overflow bit.
On a risc-like ISA without a status register and not wanting
to increase the number of destination registers,
without an instruction like ADGO you'd have to do a
sequence to create an overflow flag:

result = a + b;
overflow = ((result ^ a) & (result ^ b)) < 0;

One ADGO instruction replaces 6.

>> Then a LIC Load Immediate Conditional loads saturation limit values.
>> One could have arithmetic instructions that saturate.
>>
>> The result is copied back to the variable. If there are constraints on
>> the variable different from the limits on the physical register
>> then those are range checked and either saturated or trapped.
>> A CMPGT and CMPLT with a LIC loads upper or lower saturation value.
>>
>> Note that setting limits on variable to be in the range 10..90 does
>> not mean that expression intermediate results are within that range.
>> It means an expression EITHER produces the arithmetically correct result
>> in that range, or it saturates or traps.
> <
> I am curious:
> <
> x, y, and z are range [10..90]: what is the result of:
> <
> x = y + ( z-x )
> < versus
> x = ( y+z ) - x
> < given that the non-overflowing arithmetic creates a result in the range [10..90] ?
>
> That is, does the arithmetic get checked, or does the delivery of a value into a variable
> get checked ?

Both.
You have to detect overflow of the individual + and - operators.
That ensures the result is arithmetically correct.

Then if the constraints on the destination variable are different
from those of the expression result, check those too.
Then update the destination.

> <
> What about::
> <
> x = y*z/x;
> ? where the multiply is either non-overflowing, or performed to double width
> and the divide is also of double width.

If y*z produces a double width result it requires no extra checks.
Double width numerator and single width denominator divide produces
a DW result (and DW remainder).
DW result is range checked that it can fit into SW x
(if unsigned upper==0, if signed upper==lower msb)
and lower SW result stored into x.

If y*z produces a single width result, then that is really the
double width result with a range check and demotion to single width.

On Saturday, May 22, 2021 at 6:17:27 PM UTC-5, EricP wrote:
> I forgot about this in my drafts folder...
> MitchAlsup wrote:
> > On Friday, May 21, 2021 at 2:41:13 PM UTC-5, EricP wrote:
> >> Stephen Fuld wrote:
> >>> On 5/20/2021 9:34 AM, MitchAlsup wrote:
> >>>> On Thursday, May 20, 2021 at 10:08:32 AM UTC-5, Stephen Fuld wrote:
> >>>>> On 5/19/2021 11:40 PM, Niklas Holsti wrote:
> >>>>>> On 2021-05-20 3:40, Stephen Fuld wrote:
> >>>>>>> On 5/19/2021 8:47 AM, EricP wrote:
> >>>>> Fair enough. This sort of gets back to the question of whether to add a
> >>>>> feature like this as an attribute of the variable (e.g. range) or of the
> >>>>> operation (e.g. bignum). I think there are arguments for each.
> >>>>>
> >>>>> BTW, I am unsure of what the requirement is here. Suppose you have a
> >>>>> variable with a range of 10-90. Do you want saturation at 90? That is
> >>>> <
> >>>> If the value to be written is outside of the range [10..90] you raise an
> >>>> exception. The raised exception decides what to do.
> >>> Certainly true for the non-saturating case, and is what Ada does. My
> >>> question is if you define saturating variables, what to do if you
> >>> somehow define the variable with a range *and* saturating.
> > <
> >> Any variables that are smaller than the machine register size are
> >> promoted to that size by either sign or zero extension.
> >>
> >> Expressions are executed using signed or unsigned checked or saturating
> >> operations at that machine size. This detects intermediate signed or
> >> unsigned overflows of the machine size results.
> >>
> >> I have instructions for trap on unsigned carry or signed overflow.
> >> I have an ADGO Add Generate Overflow and ADGC Add Generate Carry
> >> to set a 1 in the output register for overflow or carry.
> > <
> > And throw the actual add away ?
> > <
> Yes. It is similar idea to MULL and MULH.
>
> One does an ADD for the result, and a ADGO to get the overflow bit.
> On a risc-like ISA without a status register and not wanting
> to increase the number of destination registers,
> without an instruction like ADGO you'd have to do a
> sequence to create an overflow flag:
>
> result = a + b;
> overflow = ((result ^ a) & (result ^ b)) < 0;
<
My 66000:: C++ syntax:
<
{overflow,result} = a+b;
<
compiles into:
<
CARRY R9,{{O}}
ADD R8,R22,R17
<
// R9 has carry bit, R8 has sum.
>
> One ADGO instruction replaces 6.
<
But you need all sorts of instructions added, I only need 1 instruction-modifier !
<
> >> Then a LIC Load Immediate Conditional loads saturation limit values.
> >> One could have arithmetic instructions that saturate.
> >>
> >> The result is copied back to the variable. If there are constraints on
> >> the variable different from the limits on the physical register
> >> then those are range checked and either saturated or trapped.
> >> A CMPGT and CMPLT with a LIC loads upper or lower saturation value.
> >>
> >> Note that setting limits on variable to be in the range 10..90 does
> >> not mean that expression intermediate results are within that range.
> >> It means an expression EITHER produces the arithmetically correct result
> >> in that range, or it saturates or traps.
> > <
> > I am curious:
> > <
> > x, y, and z are range [10..90]: what is the result of:
> > <
> > x = y + ( z-x )
> > < versus
> > x = ( y+z ) - x
> > < given that the non-overflowing arithmetic creates a result in the range [10..90] ?
> >
> > That is, does the arithmetic get checked, or does the delivery of a value into a variable
> > get checked ?
> Both.
> You have to detect overflow of the individual + and - operators.
<
You could evaluate the expression in a form that guarantees no-overflow.
<
> That ensures the result is arithmetically correct.
>
> Then if the constraints on the destination variable are different
> from those of the expression result, check those too.
> Then update the destination.
> > <
> > What about::
> > <
> > x = y*z/x;
> > ? where the multiply is either non-overflowing, or performed to double width
> > and the divide is also of double width.
<
> If y*z produces a double width result it requires no extra checks.
> Double width numerator and single width denominator divide produces
> a DW result (and DW remainder).
<
Depends if you ASK for a remainder !
<
> DW result is range checked that it can fit into SW x
> (if unsigned upper==0, if signed upper==lower msb)
> and lower SW result stored into x.
>
> If y*z produces a single width result, then that is really the
> double width result with a range check and demotion to single width.

Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:

> "Ada" today does not mean Ada83. It means Ada2012

Tell that to the people who still think Fortran is
FORTRAN 66 + extensions...

MitchAlsup <MitchAlsup@aol.com> schrieb:

> My 66000:: C++ syntax:
><
> {overflow,result} = a+b;
><
> compiles into:
><
> CARRY R9,{{O}}
> ADD R8,R22,R17

I was wondering: Assuming you had enough bits to easily encode
all the four-operand instructions you like, as in

ADDC R8,R9,R22,R17

would you still see an advantage in your CARRY modifier (also
for multipliation)?

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:

> It is my strong and not so humble opinion that a cpu/program/language
> should always be free to deliver the best result it can, i.e. even if an
> intermediate results would overflow/trap on most other CPUs.
>
> If the final result delivered is in range, and mathematically correct,
> then use it, otherwise trap at that point.

Fortran is, by its language definition, allowed to do mathematical
simplification on expressions as long as parentheses are preserved.

So, Fortran could take

a = b + c - b

and simply evaluate it as

a = c

even when b is NaN. Some people have claimed that this violates
IEEE semantics, I haven't looked at the IEEE standard to check
(and I can't without spending €€€, which I don't want to do).

In

a = (b + c) - b

this would not be permitted.

On Sunday, May 23, 2021 at 7:31:54 AM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > My 66000:: C++ syntax:
> ><
> > {overflow,result} = a+b;
> ><
> > compiles into:
> ><
> > CARRY R9,{{O}}
> > ADD R8,R22,R17
> I was wondering: Assuming you had enough bits to easily encode
> all the four-operand instructions you like, as in
>
> ADDC R8,R9,R22,R17
>
> would you still see an advantage in your CARRY modifier (also
> for multipliation)?
<
CARRY prevents the explosion of Instructions to deal with {this and that};
as does PRED, as does "VEC and LOOP". So, instead of having 4× as many
instructions as I have, I have +4 more instructions. In addition, each of
these modifiers covers a number of instructions not just 1.

On Sunday, May 23, 2021 at 8:14:02 AM UTC-5, Thomas Koenig wrote:
> Terje Mathisen <terje.m...@tmsw.no> schrieb:
> > It is my strong and not so humble opinion that a cpu/program/language
> > should always be free to deliver the best result it can, i.e. even if an
> > intermediate results would overflow/trap on most other CPUs.
> >
> > If the final result delivered is in range, and mathematically correct,
> > then use it, otherwise trap at that point.
> Fortran is, by its language definition, allowed to do mathematical
> simplification on expressions as long as parentheses are preserved.
>
> So, Fortran could take
>
> a = b + c - b
>
> and simply evaluate it as
>
> a = c
>
> even when b is NaN. Some people have claimed that this violates
> IEEE semantics, I haven't looked at the IEEE standard to check
> (and I can't without spending €€€, which I don't want to do).
<
When b = NaN
b+c is NaN; Nan-Nan is NaN
c-b is NaN; NaN-NaN is NaN
So the result should be NaN
>
> In
>
> a = (b + c) - b
>
> this would not be permitted.
<
And would still be NaN

Thomas Koenig wrote:
> MitchAlsup <MitchAlsup@aol.com> schrieb:
>
>> My 66000:: C++ syntax:
>> <
>> {overflow,result} = a+b;
>> <
>> compiles into:
>> <
>> CARRY R9,{{O}}
>> ADD R8,R22,R17
>
> I was wondering: Assuming you had enough bits to easily encode
> all the four-operand instructions you like, as in
>
> ADDC R8,R9,R22,R17
>
> would you still see an advantage in your CARRY modifier (also
> for multipliation)?

I see a huge benefit in code density: A single new opcode provides a
bunch of new functionality, instead of having to add an extra bit of
encoding entropy for all of the corresponding normal ops.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"