Extended modal types

Extended modal types

[Anatoly Chernyshev]

Once I have been introduced in Ada programming, I was very
exciting about modular types. Later on it became evident to me that
these types are rather limited, and one cannot use arbitrary modular
range,
for example, like -100..345. I didn't find any packages in the WWW that
can
deal with such "extended" modular variables, so I wrote my own.
Anyone interested could pick it up at
http://www.polarhome.com/~ada/ch_rings.zip

Anatoly Chernyshev

Re: Extended modal types

[Marc A. Criley]

Anatoly Chernyshev wrote:
> 
> Once I have been introduced in Ada programming, I was very
> exciting about modular types. Later on it became evident to me that
> these types are rather limited, and one cannot use arbitrary modular
> range,
> for example, like -100..345. I didn't find any packages in the WWW that
> can
> deal with such "extended" modular variables, so I wrote my own.
> Anyone interested could pick it up at
> http://www.polarhome.com/~ada/ch_rings.zip

Hmmm, modular types are unsigned by design.  So a "modular range" having
a negative lower bound doesn't really make any sense; it's no longer a
modular type.  Though one can produce a package that provides operations
on an integer type that mimics some of the modular type behavior.

Marc A. Criley
Consultant
Quadrus Corporation
www.quadruscorp.com

Re: Extended modal types

[Robert Dewar]

Anatoly Chernyshev <rhezusfactor@yahoo.com> wrote in message news:<3CEDFF90.B94D7E32@yahoo.com>...
> and one cannot use arbitrary modular
> range,
> for example, like -100..345.

I can't even guess what an arbitrary modular range might be. Modular
refers to the fact that integer values are
represented by their (positive) remainder value when
divided by the modulus in use. Thus modular types can
never have negative numbers. 

If you are talking about wrap around types, then sure
you can get the effect you want. For example, in the
above case, you can define a type that is

   type r is mod 446;

Now you represent numbers in the range -100 .. 345 using
this type, and for example if you say

   rr : r := -100;

then the actual value would be 346.

The only thing you might want is an output routine that
understands this convention (which in fact is very similar
to how twos complement works).

But this is all a guess, since the term extended modular
type is meaningless.


Also I must say it is plain bizarre to get excited about
the prospect of such a peculiar special purpose feature (to
me even allowing non-binary modulus values is a mistake.

Actually a bit of history as to how this mistake came to
pass is of interest:

The URG agreed to provide unsigned types using a modular
type approach with binary modulus values that corresponded
to natural word sizes of the machine (much as C does).

We agreed to extend it to arbitrary powers of 2, since
an AND instruction is cheap on all machines.

Someone proposed (Bryce Bardin perhaps, apologies if that
is a wrong memory) extending this to non-binary values. The
vote in the URG was N-1 *against* this extension on the
grounds that it was frivolous (you can always program this
if you need it).

The Ada 9X design team put in general modular types, and
I and a couple of other people complained that it was a
feature that could not be justified.

Tuck and Bob responded that they had a commitment to 
implement the URG recommendations, and claimed that the
URG had recommended this. As chair of the URG, I knew
just how wrong this was :-) 

Turned out they had used as gospel the rejected proposal
for general modular types, assuming that the URG had
accepted it.

By that time, the feature was out, and featuritis had
set in and enough people were in favor that it stayed in.
Since it was not that much of a pain to implement, it
was not worth fighting.

But I find it a bit of nonsense in the
language (especially the weird semantics of NOT. For
example:

with Text_IO; use Text_IO;
procedure q is
  type r is mod 446;
  x : r := 13;

begin
   Put_Line (r'Image (not x));
end;

prints 432, and I do not find anything reasonable or
intuitive about that result :-)

To me this is orthogonality in language design run amok!

Re: Extended modal types

[Frank J. Lhota]

I think the real issue here is that for moduli other than powers of 2, e.g.

    type r is mod 446;

the bitwise operations "and", "or", and "not" simply do not have any
intuitive meaning. It may very well have been preferable for these
operations to be undefined for mod 446.

Re: Extended modal types

[Florian Weimer]

"Frank J. Lhota" <NOSPAM.FrankLho@rcn.com> writes:

> I think the real issue here is that for moduli other than powers of 2, e.g.
>
>     type r is mod 446;
>
> the bitwise operations "and", "or", and "not" simply do not have any
> intuitive meaning. It may very well have been preferable for these
> operations to be undefined for mod 446.

You can't do that without violating the generic contract model.

(IMHO, modular types whose modular type whose modulus is not a power
of two should have been avoided altogether.)

Re: Extended modal types

[David C. Hoos, Sr.]

----- Original Message ----- 
From: "Florian Weimer" <fw@deneb.enyo.de>
Newsgroups: comp.lang.ada
To: <comp.lang.ada@ada.eu.org>
Sent: May 25, 2002 1:40 PM
Subject: Re: Extended modal types
<snip>
> (IMHO, modular types whose modular type whose modulus is not a power
> of two should have been avoided altogether.)
Every allowed modulus _is_ a power of two -- just not an _integer_
power of two ;)

Re: Extended modal types

[Robert I. Eachus]

Florian Weimer wrote:


> (IMHO, modular types whose modular type whose modulus is not a power
> of two should have been avoided altogether.)


Shows your hardware bias. ;-)  There are two very useful applications of 
modular types in Ada.  One where the modulus is an integral power of two 
maps nicely to a lot of hardware device interfaces, etc.  The other is 
in the area of cryptography and hashing, where the modulus tends to be a 
prime, or the product of two primes.  On a lot of hardware (X * Y) mod 
some large prime is a very useful operation, and maps neatly to a 32-bit 
by 32-bit multiply with a 64 (actually 63) bit result, and a divide by a 
32 bit integer keeping the remainder.  Most programming languages have 
no easy way of getting to those hardware instructions.

Are there operations on modular types which are pretty useless for 
non-power of two modulii, and there are operations that are only of 
interest for such modulii.  Ada supports both, and there is a large 
enough set of operations that make sense for both that the two sets of 
types were unified.  (Except in the limits in package System.)

Re: Extended modal types

[Florian Weimer]

"Robert I. Eachus" <rieachus@attbi.com> writes:

> The other is in the area of cryptography and hashing, where the
> modulus tends to be a prime, or the product of two primes.

The modulus has to be static, that's why modular types aren't
extremely useful even in this context.

Re: Extended modal types

[Robert I. Eachus]

Florian Weimer wrote:


> The modulus has to be static, that's why modular types aren't
> extremely useful even in this context.


You are probably thinking of public-key encryption where the keys and 
modulii are too big for ordinary modular types anyway.   I was thinking 
of many algorithms that use modular arithmetic to introduce 
non-linearity, for example multiplying two four-bit nibbles mod 17.  In 
cases like this, the modulus is a static part of the algorithm 
definition, and needs to be prime for invertability.

Similarly, hashing tables often use the sum of the character values mod 
the size of the hash table to generate a hash location.

Re: Extended modal types

[Robert Dewar]

"Robert I. Eachus" <rieachus@attbi.com> wrote in message news:<3CF2C6AF.60607@attbi.com>...
> Florian Weimer wrote:

> You are probably thinking of public-key encryption where the keys and 
> modulii are too big for ordinary modular types anyway.   I was thinking 
> of many algorithms that use modular arithmetic to introduce 
> non-linearity, for example multiplying two four-bit nibbles mod 17.  In 
> cases like this, the modulus is a static part of the algorithm 
> definition, and needs to be prime for invertability.

The fact that there are many algorithms which need a particular datatype
with some particular properties is NOT a reason for putting the type into
the language as a primitive type.

All these arguments about cryptography and hashing were made in the URG
meeting which rejected the generalization of unsigned wrap around types
to general non-binary modulus values overwhelmingly. I think the URG had
it right and Ada 95 has it wrong.

There are lots and lots of types that belong in the language long before
non-binary modular types (one that jumps to mind as clearly more important
is multiple precision integer arithmetic -- but I would not put that in
either :-)

Re: Extended modal types

[Robert A Duff]

dewar@gnat.com (Robert Dewar) writes:

> Actually a bit of history as to how this mistake came to
> pass is of interest:
...
> Tuck and Bob responded that they had a commitment to 
> implement the URG recommendations, and claimed that the
> URG had recommended this. As chair of the URG, I knew
> just how wrong this was :-) 

Robert,

Your history is slightly wrong.  I never wanted to have non-binary
modular types, and I agree with you that they are a mistake.

Modular types are one of my least favorite features of Ada 95.
If anybody cares, I could rant for several paragraphs about
what's wrong with them.

- Bob

Re: Extended modal types

[Dmitry A. Kazakov]

On Wed, 29 May 2002 02:31:35 GMT, Robert A Duff
<bobduff@shell01.TheWorld.com> wrote:

>Modular types are one of my least favorite features of Ada 95.
>If anybody cares, I could rant for several paragraphs about
>what's wrong with them.

Do it, please. I find it very interesting.

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Extended modal types

[Robert Dewar]

Robert A Duff <bobduff@shell01.TheWorld.com> wrote in message news:<wccd6vfelbs.fsf@shell01.TheWorld.com>...

> Robert,
> 
> Your history is slightly wrong.  I never wanted to have non-binary
> modular types, and I agree with you that they are a mistake.

OK, sorry about that! So too bad you did not manage to eliminate them :-)

Re: Extended modal types

[Anatoly Chernyshev]

Well, this post got a surprising response, so I have to make some
explanation on that.
First, I beg your pardon for probable confusing of the terms. I did not
think of modular types as a computer scientist, instead I just thought of
some �cyclical� integer type, which will never overflow even being added
with an �out of range� number. I found this type should mostly be the
modular alike.

I see the usefulness of this type is in arrays dimensions � when one goes
beyond the array boundary it automatically gets to the opposite side.
Arrays with such a property known as �periodic boundary condition� are
widely used in molecular mechanics and cellular automata (Conway�s Game of
Life, for instance). I had not found those types in packages available to
public, so I decided to write my own.

Actually, the package for deal with such �extended modular� types merely is
a service one aimed for further development of package(s) for periodical
boundary condition arrays.

Anatoly Chernyshev


Anatoly Chernyshev wrote:

> Once I have been introduced in Ada programming, I was very
> exciting about modular types. Later on it became evident to me that
> these types are rather limited, and one cannot use arbitrary modular
> range,
> for example, like -100..345. I didn't find any packages in the WWW that
> can
> deal with such "extended" modular variables, so I wrote my own.
> Anyone interested could pick it up at
> http://www.polarhome.com/~ada/ch_rings.zip
>

Re: Extended modal types

[Robert Dewar]

Anatoly Chernyshev <rhezusfactor@yahoo.com> wrote in message news:<3CF4F1A8.6A491F3@yahoo.com>...
> Well, this post got a surprising response, so I have to make some
> explanation on that.
> First, I beg your pardon for probable confusing of the terms. I did not
> think of modular types as a computer scientist, instead I just thought of
> some �cyclical� integer type, which will never overflow even being added
> with an �out of range� number. I found this type should mostly be the
> modular alike.

So please read my post carefully and explain why ordinary
modular types do not meet this need perfectly well?