Modular type. What is it and why?

Modular type. What is it and why?

[Staffan Dittmer]

This might be a simple one but i can't figure it out.
What is a modular type, as opposed to the integer?
When is it useful?
Since ada relies so heavily on types I guess it's not by accident that the standard library includes modular_io.
But why?
Could someone please enlighten me on this subject.
An example of usage would be nice.
I've checked the RM but to be perfectly honest I didn't understand it.

Thanks in advance
Staffan Dittmer

Re: Modular type. What is it and why?

[Marin David Condic]

Staffan Dittmer wrote:
> 
> This might be a simple one but i can't figure it out.
> What is a modular type, as opposed to the integer?
> When is it useful?
> Since ada relies so heavily on types I guess it's not by accident that the standard library includes modular_io.
> But why?
> Could someone please enlighten me on this subject.
> An example of usage would be nice.
> I've checked the RM but to be perfectly honest I didn't understand it.
> 

Integer types are pretty much what you would expect: a means of
representing integer values both positive and negative. A typical
integer may, for example, be used to represent numbers between
-32768..32767. Ada gives you predefined integer types known as Integer,
Long_Integer, Short_Integer and (at the discretion of the
implementation) there may be others as well.

Modular types are also a means of representing integer values, but only
non-negative values. For example, a declaration such as:

type My_Modular_Type is mod 2**16 ;

would be able to take on values between 0..65535. Ada does not define
any standard Modular types - unless you want to count what you may find
in the packages Interfaces and Interfaces.C (See appendix B.2 and B.3 of
the ARM) to be "standard". The real interesting usage of Modular types
has to do with the operations on them. Arithmetic has "wrap around"
semantics - that is:

X : My_Modular_Type := 65535 ;

...

X := X + 1 ; -- X now = 0.

Also you get logical "and" "or" and "not" between two modular objects.
If you count what is in the package Interfaces (see appendix B.2 of the
ARM) you also get shift and rotate operations on modular types. (Its
just that the types and sizes are going to be implementation defined,
rather than guaranteed sizes by virtue of the language standard.)

Modular types were invented to fill a void in Ada83 - the need that many
embedded systems have for dealing with unsigned integers on which you
could perform bitwise operations. They also prove useful for other
things where the wraparound math is handy.

Hope this helps.

-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
***To reply, remove "bogon" from the domain name.***

Re: Modular type. What is it and why?

[David C. Hoos, Sr.]

Staffan Dittmer wrote in message <7ean3c$79m$1@eol.dd.chalmers.se>...
>This might be a simple one but i can't figure it out.
>What is a modular type, as opposed to the integer?
A mudular type is one in which incrementing from (modulus -1) gives zero, and when decrementing from zero gives (modulus -1) -- i.e.
overflow and underflow cannot occur.

E.g. the type mod 2 ** 8, has values 0 .. 255.

The type mod 7 has values 0 .. 6.

>When is it useful?


There are many uses for such a type -- e.g., the index of a circular array, or a representation of the days of the week, such that
the successor to the last day of the week is the first day of the week, and the predecesor of the first day of the week is the last
day of the week.

>Since ada relies so heavily on types I guess it's not by accident that the standard library includes modular_io.
>But why?
Well.. because someone might want to do IO on mudular types.

>Could someone please enlighten me on this subject.
>An example of usage would be nice.

In general, the unsigned C types in the package Interfaces.C are specified to be modular types, giving them the same behavior as
their C counterparts.

>I've checked the RM but to be perfectly honest I didn't understand it.


RM 95-3.5.4(8) says:

The set of values for a signed integer type is the (infinite) set of mathematical integers, though only values of the base range of
the type are fully supported for run-time operations. The set of values for a modular integer type are the values from 0 to one less
than the modulus, inclusive.

Re: Modular type. What is it and why?

[Mike Silva]

David C. Hoos, Sr. wrote in message <7eb2iq$jc3@hobbes.crc.com>...
<....>
>There are many uses for such a type -- e.g., the index of a circular array,
or a representation of the days of the week...

One of the little "goodies" I discovered in coming from C to Ada are modular
types.  I often had to write code like:

switch ( key )
{
   case ARROW_DOWN:
      if ( index < ( NUM_ELEMENTS - 1 ) )
         index++;
      else
         index = 0;
      break;
   case ARROW_UP:
      if ( index > 0 )
         index = NUM_ELEMENTS - 1;
      else
         index--;
      break;
}

Now with Ada I'll be able to write (assuming 'index' is the appropriate
modular type):

case ( key ) is
   when ARROW_DOWN =>
      index := index + 1;
   when ARROW_UP =>
      index := index - 1;
end case;

Now -that's- what I call progress!

Mike

Re: Modular type. What is it and why?

[Mike Silva]

Mike Silva wrote in message <7ede2p$pd1$1@its.hooked.net>...
>   case ARROW_UP:
>      if ( index > 0 )
>         index = NUM_ELEMENTS - 1;
>      else
>         index--;
>      break;

See that, another bug that wouldn't happen in the Ada code!  (I got the
if/else actions backwards in the above)


>   when ARROW_UP =>
>      index := index - 1;

Re: Modular type. What is it and why?

[Marin David Condic]

Mike Silva wrote:
> Now with Ada I'll be able to write (assuming 'index' is the appropriate
> modular type):
> 
> case ( key ) is
>    when ARROW_DOWN =>
>       index := index + 1;
>    when ARROW_UP =>
>       index := index - 1;
> end case;
> 
> Now -that's- what I call progress!
> 

My C is pretty rusty - not having done anything serious in it in at
least 10 years - but wasn't there some kind of type/operation that
allowed for wraparound semantics? I know one of the major early bitches
about Ada(83) was that it didn't allow for unsigned integers, logical
ops on integers & wraparound math - all things considered critical for
embedded programming. (At least at that point in time) If C doesn't
support some or all of these things, then how could it be so "popular"
with the embedded crowd?

I remember enough C to recall that you did have logical operations on
integers and shift/rotate operations on integers as well. Maybe (if my
Parts-heimers would clear up a little so I could remember) the
wraparound semantics were always implemented using logical ops? Not
nearly as pretty as The Ada Way, but it would get you there...

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
***To reply, remove "bogon" from the domain name.***

Re: Modular type. What is it and why?

[Ole-Hjalmar Kristensen]

"Mike Silva" <mjsilva@jps.net> writes:

> David C. Hoos, Sr. wrote in message <7eb2iq$jc3@hobbes.crc.com>...
> <....>
> >There are many uses for such a type -- e.g., the index of a circular array,
> or a representation of the days of the week...
> 
> One of the little "goodies" I discovered in coming from C to Ada are modular
> types.  I often had to write code like:
> 
> switch ( key )
> {
>    case ARROW_DOWN:
>       if ( index < ( NUM_ELEMENTS - 1 ) )
>          index++;
>       else
>          index = 0;
>       break;
>    case ARROW_UP:
>       if ( index > 0 )
>          index = NUM_ELEMENTS - 1;
>       else
>          index--;
>       break;
> }
> 
> Now with Ada I'll be able to write (assuming 'index' is the appropriate
> modular type):
> 
> case ( key ) is
>    when ARROW_DOWN =>
>       index := index + 1;
>    when ARROW_UP =>
>       index := index - 1;
> end case;
> 
> Now -that's- what I call progress!
> 
> Mike
> 
> 
> 
> 

Yes, this is a good illustration of modular types. However, what do
you do if NUM_ELEMENTS change? 
Maybe modular types isn't the right choice in this case.

-- 
E pluribus Unix

Re: Modular type. What is it and why?

[Mike Silva]

Marin David Condic wrote in message <370A4B3A.5EDB3B37@pwfl.com>...
>Mike Silva wrote:
>> Now with Ada I'll be able to write (assuming 'index' is the appropriate
>> modular type):
>>
>> case ( key ) is
>>    when ARROW_DOWN =>
>>       index := index + 1;
>>    when ARROW_UP =>
>>       index := index - 1;
>> end case;
>>
>> Now -that's- what I call progress!
>>
>
>My C is pretty rusty - not having done anything serious in it in at
>least 10 years - but wasn't there some kind of type/operation that
>allowed for wraparound semantics?...

Well, if you're going up you can do:

 index = ( index + 1 ) % NUM_ELEMENTS;    /* where % is the MOD operator */

but you can't do:

 index = ( index - 1 ) % NUM_ELEMENTS;    /* won't handle 0 ->
NUM_ELEMENTS - 1 correctly */

As Ole-Hjalmar Kristensen commented, the nice Ada solution doesn't work if
NUM_ELEMENTS varies at runtime (at least, it appears that a modular type
can't be defined dynamically -- correct?), but that's not the usual case I
run across.

Mike

Re: Modular type. What is it and why?

[bglbv]

"Mike Silva" <mjsilva@jps.net> writes:

> As Ole-Hjalmar Kristensen commented, the nice Ada solution doesn't work if
> NUM_ELEMENTS varies at runtime (at least, it appears that a modular type
> can't be defined dynamically -- correct?), but that's not the usual case I
> run across.

Correct: the standard requires the modulus to be a *static* expression.
There is a similar restriction for signed integer types (and fixed and
floating point types): presumably it would be too much trouble to have
to choose between, say, a 16-bit and a 64-bit representation at run time.
Subtypes, on the other hand, can have their constraints elaborated at
run time, but that doesn't let one change the modulus...

Re: Modular type. What is it and why?

[Ole-Hjalmar Kristensen]

"Mike Silva" <mjsilva@jps.net> writes:

> Marin David Condic wrote in message <370A4B3A.5EDB3B37@pwfl.com>...
> >Mike Silva wrote:
> >> Now with Ada I'll be able to write (assuming 'index' is the appropriate
> >> modular type):
> >>
> >> case ( key ) is
> >>    when ARROW_DOWN =>
> >>       index := index + 1;
> >>    when ARROW_UP =>
> >>       index := index - 1;
> >> end case;
> >>
> >> Now -that's- what I call progress!
> >>
> >
> >My C is pretty rusty - not having done anything serious in it in at
> >least 10 years - but wasn't there some kind of type/operation that
> >allowed for wraparound semantics?...
> 
> Well, if you're going up you can do:
> 
>  index = ( index + 1 ) % NUM_ELEMENTS;    /* where % is the MOD operator */
> 
> but you can't do:
> 
>  index = ( index - 1 ) % NUM_ELEMENTS;    /* won't handle 0 ->
> NUM_ELEMENTS - 1 correctly */
> 

Actually, if index is unsigned, then it *will* handle 0 ->
NUM_ELEMENTS - 1 correctly.

> As Ole-Hjalmar Kristensen commented, the nice Ada solution doesn't work if
> NUM_ELEMENTS varies at runtime (at least, it appears that a modular type
> can't be defined dynamically -- correct?), but that's not the usual case I
> run across.

Agreed, I just thought I would mention it.
> 
> Mike
> 
> 
> 

-- 
E pluribus Unix

Re: Modular type. What is it and why?

[Mike Silva]

Ole-Hjalmar Kristensen wrote in message ...
>> but you can't do:
>>
>>  index = ( index - 1 ) % NUM_ELEMENTS;    /* won't handle 0 ->
>> NUM_ELEMENTS - 1 correctly */
>
>Actually, if index is unsigned, then it *will* handle 0 ->
>NUM_ELEMENTS - 1 correctly.

No, if you roll e.g. a 16 bit unsigned int from 0 to 65535, the value 65535
mod N will not in general be N - 1, as we want.  (e.g., by inspection, 65535
mod 10 is 5)
>
>> As Ole-Hjalmar Kristensen commented, the nice Ada solution doesn't work
if
>> NUM_ELEMENTS varies at runtime (at least, it appears that a modular type
>> can't be defined dynamically -- correct?), but that's not the usual case
>> I run across.
>
>Agreed, I just thought I would mention it.

Actually, the more I thought about it the more the static limitation on
modular types makes my idea worthless.  Even if NUM_ELEMENTS is static for
each menu, I'd want the same routine to handle multiple menus, each with a
different NUM_ELEMENTS.  Oh well...

Mike

Re: Modular type. What is it and why?

[Stephen Leake]

"Mike Silva" <mjsilva@jps.net> writes:

> Actually, the more I thought about it the more the static limitation on
> modular types makes my idea worthless.  Even if NUM_ELEMENTS is static for
> each menu, I'd want the same routine to handle multiple menus, each with a
> different NUM_ELEMENTS.  Oh well...

That's what generics are for. Unless the number of elements in a given
menu is dynamic.

-- Stephe

Re: Modular type. What is it and why?

[Robert Dewar]

In answer to the question what is a modular
type, perhaps the most important way to answer
this is that the most typical use is to provide
an unsigned binary integer with wrap around
semantics, just like C unsigned, e.g.

  type x is mod 2 ** 32;

provides a type essentially identical to the C
type unsigned, presuming that the latter is 32
bits (as usual, there is no way of controlling
the size of types in C).

Yes, "peculiar" non-binary values can be used for
the modulus, and they have some limited uses for
addressing circular arrays etc, but in fact this
usage is quite marginal. By far the most important
use is for binary unsigned.

A bit of history here. The URG spent a lot of effort
on designing modular (unsigned) types. We had one
member who pushed for generalizing this to arbitrary
moduli, but this proposal was soundly rejected as a
frill.

The Ada 95 design team had the mission of incorporating
URG suggestions, and they read the report of this one
person, thinking it represented URG consensus, and hence
Ada 95 has the more general formulation.

I still think it is a bit of a frill. Yes, the circular
array is the canonical example of its use, but I doubt
this is worth the extra complexity of use and definition
(look for example at the strange definition of not on
non-binary modulus values).

And a difficulty is that the resulting types are called
modular types, instead of unsigned types, resulting in
exactly the confusion represented by the original
question here.

People can read a general definition of modular types,
and easily miss that this is in fact the facility in
Ada for providing conventional unsigned types.

Anyway, it does make for nice neat examples with circular
buffers, though the restriction to static values makes it
less useful for this purpose than one might at first
imagine.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Modular type. What is it and why?

[Bret]

In article <7egmbf$tgi$1@nnrp1.dejanews.com>, Robert says...
 
>
>People can read a general definition of modular types,
>and easily miss that this is in fact the facility in
>Ada for providing conventional unsigned types.
>

Then why did they not simply call it 'unsigned'? 
I agree it is more natural to call it 'unsigned' than
modular. Is it too late to change the RM?

Bert.
 

Re: Modular type. What is it and why?

[Ole-Hjalmar Kristensen]

"Mike Silva" <mjsilva@jps.net> writes:

> Ole-Hjalmar Kristensen wrote in message ...
> >> but you can't do:
> >>
> >>  index = ( index - 1 ) % NUM_ELEMENTS;    /* won't handle 0 ->
> >> NUM_ELEMENTS - 1 correctly */
> >
> >Actually, if index is unsigned, then it *will* handle 0 ->
> >NUM_ELEMENTS - 1 correctly.
> 

You're right, of course. I was just thinking about the wrap from 0 to 65535.

> No, if you roll e.g. a 16 bit unsigned int from 0 to 65535, the value 65535
> mod N will not in general be N - 1, as we want.  (e.g., by inspection, 65535
> mod 10 is 5)
> >
> >> As Ole-Hjalmar Kristensen commented, the nice Ada solution doesn't work
> if
> >> NUM_ELEMENTS varies at runtime (at least, it appears that a modular type
> >> can't be defined dynamically -- correct?), but that's not the usual case
> >> I run across.
> >
> >Agreed, I just thought I would mention it.
> 
> Actually, the more I thought about it the more the static limitation on
> modular types makes my idea worthless.  Even if NUM_ELEMENTS is static for
> each menu, I'd want the same routine to handle multiple menus, each with a
> different NUM_ELEMENTS.  Oh well...
> 
> Mike
> 
> 
> 
> 

I suppose you could make the routine generic? Then it will work if
NUM_ELMENTS is known at compile time.

-- 
E pluribus Unix

Re: Modular type. What is it and why?

[Florian Weimer]

Robert Dewar <robert_dewar@my-dejanews.com> writes:

> And a difficulty is that the resulting types are called
> modular types, instead of unsigned types, resulting in
> exactly the confusion represented by the original
> question here.

In addition, division doesn't work as expected if the modulus is prime
(at least from a mathematical point of view). :-/