Universal integer or universal expression 
Author Message
 Universal integer or universal expression


Quote:

>The RM is not crystal clear about how the 'Succ and 'Pred attributes work
>for integer types. It states that is returns the result of adding one
>or substracting one respectively to/from the arg.  I assume that this
>means it uses the predefined operator and effectively does arg + 1 or
>arg - 1.  In which case, a mod type would wrap.

That's right.  'Succ does the same thing as +1, and for modular types,
that means wrapping, not overflowing.

- Bob



Mon, 01 Dec 1997 03:00:00 GMT  
 Universal integer or universal expression


Quote:

> >    type Byte is range 0 .. 255;

> >creates a signed integer type.

> Yes.

> >(Of course, if you want an unsigned byte type, it's probably better to
> >declare it as

> >    type Byte is mod 256;

> >if you don't need Ada 83 compatibility.)

> Not necessarily.  It depends what you're doing.  In the first case, you
> get range checking.  In the second case you get wrap-around, plus
> bit-wise logical operators.  Thus, the modular type facility is (IMHO)
> somewhat lower level.  If you just want a number that happens to range
> from 0 to 255, the signed integer type seems best to me.  If you want
> wrap-around arithmetic, or bit-wise operators, then the modular type is
> best.

> Note that in both of the above examples, Byte'Size should be 8.

Also, signed integers are always symetric about zero so the base range
of Byte'Size >= 9.  This allows for a slight difference with the mod type
so that the following (perhaps poor) code is legal with a signed integer,
but not legal for the mode type:

        bias : constant := -128;
        x    : Byte;

        ...

        x := x + bias;

I am so glad I have this straight in my head again.  I lost it for awhile.

Now, I have one more question of my own to add (and then I promise not to
post anything more about mod types for a least an hour :-)

The RM is not crystal clear about how the 'Succ and 'Pred attributes work
for integer types. It states that is returns the result of adding one
or substracting one respectively to/from the arg.  I assume that this
means it uses the predefined operator and effectively does arg + 1 or
arg - 1.  In which case, a mod type would wrap.  The people I have talked
to agree but are not certain.  It could also raise a Constraint_Error
if it goes out of range.  What do the experts say?

--



Mon, 01 Dec 1997 03:00:00 GMT  
 Universal integer or universal expression

: Also, signed integers are always symetric about zero so the base range
: of Byte'Size >= 9.  

Byte'Size is still 8, but Byte'Base'Size is >= 9.

: ...
: The RM is not crystal clear about how the 'Succ and 'Pred attributes work
: for integer types. It states that is returns the result of adding one
: or substracting one respectively to/from the arg.  I assume that this
: means it uses the predefined operator and effectively does arg + 1 or
: arg - 1.  In which case, a mod type would wrap.  The people I have talked
: to agree but are not certain.  It could also raise a Constraint_Error
: if it goes out of range.  What do the experts say?

It wraps.



Intermetrics, Inc.



Tue, 02 Dec 1997 03:00:00 GMT  
 Universal integer or universal expression

  I was recently reminded that I promised to post an explanation of
the signed integer type vs. mod type issue.  I am apparantly not the
only person who was confused about mod type behaviour.  Thanks to the
good people of CLA (and special thanks to Robert A Duff), I have
"seen the light" and will now explain my misunderstandings.

  Originally, I asked if "+ 10" and "- 10" are universal constants or
expressions.  This has not changed, I gather, from Ada 83 and they are
still both expressions: a binary operator applied to 10.  I asked
because the predefined operators for mod type all guarantee the result
to be in range.  So, I wanted to do something like the following:

        type mod_10 is mod 10;
        x : mod_10 := +10;

Or, have a function that returns an integer and use the + operator to
put the value between 0..9.  This, it turns out is not possible.  It
comes from the explanation of type, and specifically integer types.

  A type actually declares a base type and it's first subtype.  For a
signed integer, the first subtype has the range given by the type
declaration.  The base type can have the same range or can have an
extended range.  Regardless of the first subtypes range, the base
types range will be symetric about zero.  Assuming a 2's compliment
architecture, here are some examples:

        type byte is range -128 .. 127;
        for byte'Size use 8;

This declares the anonymous type byte'base with at least the range
-128..127.  It also declares the first subtype, byte, which is both
limited to the range -128..127 and is made to be exactly 8 bits in
size.  The actual range of byte'base is implementation defined.  On
the VAX, it appears to have a base range larger than the first subtype
while on my i486 with GNAT, the base type has the same range.

        type Ubyte is range 0 .. 255;
        for Ubyte'Size use 8;

This type will definately have different ranges for the base type and
the first subtype.  The base type, since it's symetric about zero,
will have a range of at least -256..255 and is more likely to have a
range of -2**15..2**15-1.

  The predefined operators are all defined on the base type.  This
means that the following expression is legal:

        x : Ubyte := (10 - 100) + 200;

You may actually have an expression that relies on this fact.  It is
there to allow intermediate values within an expression to go outside
of range and still get the desired result.

  Mod types work exactly the same way with one exception.  The base
type and the first subtype of a mod type have the same range -
0..modulus-1.  Since all predefined operators are defined with the
base type, the operators for the mod type will only accept values in
the range 0..modulus-1.  So,

        x : mod_10 := +10;

is invalid because

        function "+" (value : in mod_10'base) return mod_10'base;

is chosen during overload resolution.  This means the literal "10" is
implicitly type converted to mod_10'base and a Constrain_Error is
raised because "10" is not in mode_10'base's range (0..9).  But, since
the results of the predefined operators for a mod type always
guarantee the result is in range, there is no problem with something
like

        x : mod_10 := (1 - 2) + 3;

because 1 - 2 is 9, 9 + 3 is 2.

  This whole thing came up because someone brought to my attention the
fact that an assignment to a mod type (which requires a type
conversion) does not force the value to be in range 0..modulus-1 as I
had originally thought, but rather raises Constraint_Error when the
value on the right hand side of the assignment is either implicitly or
explicitly type converted to the mod type and this value it is not in
range. I have found two published Ada 95 books that mistakenly assign
values out of range to an mod type object.  They have the excuse that
this area was changed fairly late in the game, so I don't blame them
for the error.  The way this worked also seemed a little odd to me,
until I realized that guaranteeing the results of an operator is in
range can be alot cheaper than doing an expensive divide with
remainder at assignment and worrying about possible overflow from
intermediate results.
--



Mon, 08 Dec 1997 03:00:00 GMT  
 Universal integer or universal expression
This is posted for Robert Dewar who had some trouble posting this.
--------------------------------------------------------------------
Sean's explanation is basically correct, but it is a little confusing in
the signed integer case. So here is another attempt.

RANGES OF ALLOWED NUMBERS FOR INTEGER TYPES

Signed integer types include the full set of mathematical integers,
whereas modular types include only the values in the base type. This
is a little surprising since we know something is suspicious about
infinite ranges of integers but that is exactly what the RM says,
see RM 3.5.4(8), so just accept this for the moment!

So for example

    type s is range 0 .. 10;
    type m is mod 10;
    sv : s;
    mv : m;

the values of type x are the (infinite) set of mathematical integers, and
the values of type y are 0,1,2,3,4,5,6,7,8,9.
MODULAR TYPES

The situation with modular types is easier to understand, so let's take
that first. Since the set of values is strictly limited, and corresponds
exactly the set of values that can be stored and manipulated inside the
machine, there are no surprises with modular types, andy value of a modular
type must be in this allowed range, and that is why:

        mv := 10;
        mv := +10;
        mv := 10 - 1;

are both legal. However, if we write:

        mv := 5 + 5;

That's OK, because the 5 is an OK value of type m, and the plus operator
wraps the result (that's what modular arithmetic is all about), giving a
value of 0. Note that the +10 was illegal because the 10 itself is illegal.

To add to the confusion, GNAT definitely had a missing check up through
version 2.06, but GNAT 2.07 to be released shortly is well behaved:

     1. procedure m is
     2.   type m is mod 10;
     3.   mv : m;
     4. begin
     5.   mv := 10;
                |
        >>> value not in range of type "m" declared at line 2
        >>> static expression raises "constraint_error"

     6.   mv := +10;
                 |
        >>> value not in range of type "m" declared at line 2
        >>> static expression raises "constraint_error"

     7.   mv := 10 - 1;
                |
        >>> value not in range of type "m" declared at line 2
        >>> static expression raises "constraint_error"

     8.   mv := 5 + 5;
     9. end m;

By the way, it is the 10 - 1 that can easily fool you, in fact if you look
at the version of the files a-numran.adb and a-numran.ads in GNAT 2.06 you
will see something like:

   Larger_Lag  : constant := 25;
   ...
   type Lag_Range is mod Larger_Lag;
   ...
   Result.R  := Larger_Lag - 1;    -- R of type Lag_Range

and that used to work fine, until we fixed GNAT to catch the error (this
happens to us every now and then, we add a new error check, and the first
victim is the GNAT runtime library :-)

The fix is easy, and you will find it in the 2.07 sources

      Result.R      := Lag_Range'Last;

which is probably nicer in any case.

So actually the situation with modular types is pretty simple, just like
enumeration types really, an absolutely fixed set of values, and if you
try to go outside this range you get immediately clobbered, and that is
the end of it.

SIGNED TYPES
------------

This is a more subtle situation. Given:

    type s is range 0 .. 10;
    sv : s;

there are three relevant ranges:

The range of values for the signed integer type we have declared, which is
the full set of mathematical values.

The base range, which is at least -10 .. +10, and may well be larger. For
any likely machine in use today, you will get at least -128 .. +127, and
some compilers may give you a bigger range. GNAT chooses the smallest
base type that covers the declared range so you get -128 .. +127, but
this is definitely NOT required, and is the source of possible errors.

Finally we have the declared range 0 .. 10.

These three ranges, we will call them the mathematical range, base range,
and declared range all have their relevance to the semantics.

For the evaluation of a static expression, the mathematical range is the
one used. This means that a statement like

   sv := 999999999999999999999999999 - 999999999999999999999999998;

is OK, even if the row of 9's far exceeds the base range, since the
whole expression on the right side is a static expression, which is
evaluated using the mathematical range, and gives a result of 1.

However, inside the machine at runtime, we don't feel like storing infinite
precision integers. This is purely an efficiency oriented decision. Some
languages like LISP and SETL don't have suh restrictions, but they pay a
price at runtime. In Ada, like most other languages of its level, we prefer
that integers be limited to what the machine can handle, which is the base
range. So now, let's consider the case:

   sv := 9999999999999999999999999999;

unlike the modular case, where this is wrong because the literal is out of
range of the type, the literal in this case is in range of the type, but
the assignment is illegal for another reason (we are assuming here that
the base range does not include this giant row of nines). The reason is
that when you have a value of some integer in a non-static context, it
must be in the base range. If not, the program is statically illegal.
The idea behind this rule is to make sure that you do not have to handle
embarrassing integer values at run time.

What about:

   sv := 11;

That's almost certainly legal, unless the compiler chooses a really bizarre
base range of -10 to +10. It is legal because the 11 fits into the base
range of the type. However, it will still raise constraint error at run
time, because on the assignment, the third kind of range, the declared
range comes into play, and the range check on the result will raise
constraint error.

What about:

   sv := 200;

this is a more interesting case. In practice this may or may not be legal
depending on the base type. Of course if it is legal it will raise constraint
error, so while this is an interesting point for language lawyers and
implementors to debate, it is not really that important a distinction.
Here is GNAT at work for these examples:

     1. procedure s is
     2.   type s is range 0 .. 10;
     3.   sv : s;
     4. begin
     5.   sv := 999999999999999999999999999 - 999999999999999999999999998;
     6.   sv := 9999999999999999999999999999;
                |
        >>> value not in range of type "s" declared at line 2
        >>> static expression raises "constraint_error"

     7.   sv := 11;
                |
        >>> warning: value not in range of type "s" declared at line 2
        >>> warning: "constraint_error" will be raised at runtime

     8.   sv := 200;
                |
        >>> value not in range of type "s" declared at line 2
        >>> static expression raises "constraint_error"

     9. end s;

Since GNAT chose -128 .. +127 as the base range, the assignment of 11
was OK, but will raise CE at runtime, but the other two assignments
are illegal. A compiler choosing a larger base range would have
accepted line 8 (but hopefully generated a warning message). It is
theoretically conceivable that a compiler might accept like 7, but
in practice no compiler will, since we use binary computers pretty
much exclusively these days, which means that all signed integer
base types have a binary range.

One more point. What happens with intermediate values in non-static
expressions? The important rule here is that all results of arithmetic
operators (and other operations such as the attributes pred and succ)
are always of the base type. Consider the example:

   type x is range 0 .. +127;
   vx : x;

   vx := 127;

   vx := ((-vx) + 60) + 70;

that's fine, it will for sure work on all compilers, and is completely
portable code, even though the intermediate value -vx is outside the
declared range, because unary minus delivers a result in the base
range, and we know that the base range of a signed integer type always
includes at least as many negative numbers as positive numbers, so the
minimum allowed base range for type x is -127 .. +127. The final result
stored in vx is +3, which is in the declared range, so all is well.

Let's modify this example a bit

   type x is range 0 .. +127;
   vx : x;

   vx := 120;

   vx := ((-vx) + 100 + 100 + 100 + 60) - 100 - 100;

Now here the final result in vx is +40, which is inside the declared
range, so all is well, but what about the intermediate values. The
result of the plus is +240, which we need to worry about. There are
three cases:

  1.  The compiler chose a big base range for x, big enough to include
      +240. In this case, all is well, and the assignments must work
      without raising constraint error, giving a result of +40.

  2.  The compiler chose a small base range (GNAT would choose
      -128 .. +127), so that this intermediate value is out of
      range of the base type, and the assignment raises constraint
      error.

  3.  Like 2, but the compiler takes advantage of the implementation
      permission of 3.5.4(24), and does not raise constraint error.
      This is fine, providing that it gives the right result.

The reason that we have the permission is that in any case it is
implementation dependent whether an assignment like this succeeds,
and it would often generate extra code to check for the result of
an intermediate operation being out of range. A notable case is
something like:

   vx := (vy * vz) / vw;

where many machines naturally handle the double length intermediate
result correctly, and checking for it being in the single length
base range would slow things down.

The m{*filter*}though is that if you want to write portable code, you
should keep intermediate results in the most restrictive base range.

For example:

   type s is range 0 .. 18;

If you are being super-correct, one might almost call it hyper-correct
in the real world, you should keep intermediate results in the range
-18 .. +18.

However, you can be sure that in practice you will get a base ...

read more »



Mon, 08 Dec 1997 03:00:00 GMT  
 Universal integer or universal expression
Robert Duff says:

"Only for us computer programmers whose minds are polluted by computer
hardware.  Now a mathemetician, on the other hand, ...

Ah ha! now it comes out, the RM was written by mathematicians, no wonder
we lowly computer programmers with polluted minds sometimes have trouble
understanding it :-) :-)

Actually, this is not a completely facetious remark. The new RM is witten
in much more definitional style. It is arguably more precise than the
Ada 83 RM, and less redundant, but this sometimes makes reading it harder.
It's easier to read the RM if you already know what it says :-)



Tue, 09 Dec 1997 03:00:00 GMT  
 Universal integer or universal expression


Quote:
> ...we know something is suspicious about
>infinite ranges of integers

Only for us computer programmers whose minds are polluted by computer
hardware.  Now a mathemetician, on the other hand, ...

;-) ;-)

- Bob



Tue, 09 Dec 1997 03:00:00 GMT  
 
 [ 22 post ]  Go to page: [1] [2]

 Relevant Pages 
 

 
Powered by phpBB® Forum Software