Version 1.4 of ai05s/ai05-0175-1.txt

Unformatted version of ai05s/ai05-0175-1.txt version 1.4
Other versions for file ai05s/ai05-0175-1.txt

!standard 3.5.9          10-02-16 AI05-0175-1/02
!class Amendment 09-10-28
!status No Action (10-0-0) 10-02-26
!status work item 09-10-28
!status received 09-10-28
!priority Low
!difficulty Medium
!subject Cyclic fixed point types
!summary
Fixed point types that wrap around in a similar way to modular integer types are (not?) introduced.
!problem
Ada does not provide a simple way to model naturally occurring cyclic quantities such as angles. Angles have the property of requiring absolute accuracy rather than relative accuracy; an error of 0.01 degrees is just as important at a bearing of 5 degrees as at 50 degrees. This implies that floating types are not appropriate for angles. Moreover, wrap around at a whole cycle must be modelled exactly.
At the moment, we can model angles as a modular integer type which solves the accurate wrap around but then we have to look after the scaling ourselves which means that programs are word length dependent and also introduces the risk of errors in mapping from the problem domain (that is getting the scaling wrong).
Or we can model angles as ordinary fixed point types but then we have to look after the wrap around ourselves which is also prone to error and can lose accuracy.
!proposal
Modular fixed point types could be introduced using declarations of the form
type T is delta D mod range L .. R;
This provides a type whose values range from L up to (but not including) R with an accuracy of at least D. The modulus M is defined as R-L.
The range L .. R must either have lower bound zero or be symmetric about zero. For example
type Bearing is delta 0.001 mod range 0.0 .. 360.0; -- M is 360.0 type Angle is delta 0.001 mod range -Pi .. Pi; -- M is 2.0*Pi
The values wrap around so that 360 degrees is "the same" as 0 degrees and similarly -Pi is "the same" as +Pi.
Small is chosen to be an implementation defined power of 2 less than or equal to delta (D) so that the range L to R is mapped onto a suitable unsigned word.
The base range is from L to R-small.
If a result of the execution of a predefined operation returning a value of type T lies outside the base range then the result is normalized by the addition or subtraction of integer multiples of M so that it lies within the base range.
In hardware terms, it should happen automatically using unsigned integer arithmetic. The intention is that the implementation cost should be low. Zero of type T is always represented as a word of zeroes.
Attributes Delta, Small, and Modulus are available. Small cannot be set. Similarly, First, Last and Range are available.
F'First gives L, F'Last gives R-Small.
The predefined operations could either be as for ordinary fixed point types or they could be restricted as described in the !discussion.
An additional form of generic parameter is required thus
generic type F is delta <> mod range <>;
!wording
<tbd>
!discussion
At first sight it might seem appropriate to use a syntax such as
type T is delta D mod M;
which merges the syntax of ordinary fixed point types and modular types. Thus
type Bearing is delta 0.001 mod 360.0;
However, although a range of 0 degrees to 360 degrees is OK for many applications such as navigation bearings, it is more helpful to use a range such as -180 to +180 for angles used in geometrical constructions and architecture.
It thus seems more appropriate to use syntax which includes the range. There is then no need to give the modulus explicitly but we insert mod to distinguish from ordinary fixed point types giving
type T is delta D mod range L .. R;
Wrap around semantics is required so that L and R are the same and the whole can be simply implemented as an unsigned word. Small is thus chosen by the implementation as an appropriate power of 2 to give the required delta. An important difference from ordinary fixed point types is that small cannot be set by a use clause.
For predefined operations, we have a choice, we can either make them the same as possible as ordinary fixed point (choice A) or be quite restrictive (choice B).
Consider
type Bearing is delta 0.001 mod range 0.0 .. 360.0; -- M is 360.0 type Angle is delta 0.001 mod range -180.0 .. +180.0; -- M is 360.0
A. Lots of operations
Operations are basically the same as ordinary fixed point followed by the application of wraparound when necessary. For example
Addition and subtraction are as expected but with wraparound semantics. Thus a Bearing of 200.0 degrees + 300.0 degrees gives 140.0 degrees and 200.0 - 300.0 is 260.0.
Unary + does nothing. Unary minus changes the sign followed by wraparound. Thus applying unary minus to a Bearing of 10 degrees gives 350.0 and applying to an Angle of 10 degrees give -10.0.
Abs changes the sign if negative.
Multiplication and division by an integer return a result of type T. Multiplication and division by the same or another fixed point type (cyclic or not) results in a value of universal fixed.
Conversion to and from other numeric types are as expected.
Equality is defined as expected. The comparison operations apply with the normal arithmetic definition. Thus for type Bearing, 20.0 is greater than 10.0 and 0.0 is less than 350.0
B. Minimal operations
In order to avoid surprises the operations are restricted. The following are not allowed.
Unary minus. Abs. This is because a natural interpretation of changing the sign of a Bearing is to go backwards.
Multiplication and division by the same or other fixed point types. It makes no sense to multiply a Bearing by an Angle and so on.
The ordering operations. This is because it is clear that if a Bearing of 40 degrees is greater than one of 20 (ie clockwise is greater for Bearings) then 10 should be greater than 350 but it wouldn't be.
Attributes
The attributes Modulus, Delta and Small are available. However, Small cannot be set by a use clause since this could upset the automatic wrap around. Modulus is useful when using the trigonometric functions from Ada.Numerics.Elementary_Functions thus
A: Signed_Angle; ... X := Sin(Float(A), Angle'Modulus);
Note that this works no matter whether Signed_Angle is defined in terms of degrees, radians or cycles. The latter might be
type Cycle is delta 0.00001 mod range 0.0 .. 1.0;
The attributes First and Last are defined. First returns L. Last does not return R but R-Small.
For completeness, it is necessary to provide an additional form of generic parameter thus
generic type F is delta <> mod range <>;
The main implementation difficulty is with multiplication by an integer where we are multiplying an unsigned value by a signed one. Hopefully the problems are reduced by providing the minimal operations only.
... thinks ...
One problem with the above proposal is that on a binary machine a range such as -180 to +180 does not permit the exact representation of 60 degrees which mathematically is a very important angle.
Similarly, we could not represent a stepping motor which turns a shaft in increments of exactly one degree because one degree cannot be accurately represented.
So we have a fundamental problem with a binary machine if we want wraparound to be hardware automatic and be able to choose our own small.
The alternative of using a normal modular type solves most problems. Thus we might write
type Bearing is mod 360*60; Degree: constant Bearing := 60; Minute: constant Bearing := 1;
and then
East: Bearing := 30*degrees;
For the more elaborate signed angles we can declare a handy generic as suggested by Ed in a private message (see at the end of this discussion)
About the only thing missing with such alternatives is literals. To get literals and to be able to represent fractions of angles to the required accuracy means cyclic fixed point and setting one's own small and hence not using hardware wraparound which somewhat defeats the object of the exercise.
Here is Ed's suggestion. Note the cunning use of conditional expressions in the initial values for the constants Scale and Bias.
generic type Support is mod <>; High_Bound : Long_Float; Zero_Based : Boolean; -- values start from zero. -- Otherwise symmetric around zero. package Angles is type Angle is private; function "+" (X, Y: Angle) return Angle; function "-" (X, Y: Angle) return Angle; function "*" (X : Angle; Y : integer) return Angle; function "/" (X : Angle; Y : integer) return Angle;
function Sin (X : Angle) return Long_Float; ... other trigonometric functions
function To_Angle (X : Long_Float) return Angle; function To_Angle (X : Long_Integer) return Angle; function To_Integer (X : Angle) return Long_Integer; function To_Float (X : Angle) return Long_Float; function Image (X : Angle) return String; private type Angle is new Support; end Angles;
with Ada.Numerics.Long_Elementary_Functions; use Ada.Numerics.Long_Elementary_Functions; package body Angles is Scale : constant := (if Zero_Based then High_Bound / Support'Modulus; else 2 * High_Bound / Support'Modulus); Bias : constant := (if Zero_Based then 0 else Support'modulus / 2);
-- now we can use regular arithmetic on these types. -- Scale and Bias only -- show up in the implementation of To_Angle and Image.
function "+"(X, Y: Angle) return Angle is begin return Angle (Support (X) + Support (Y)); end "+";
function "-"(X, Y: Angle) return Angle is begin return Angle (Support (X) - Support (Y)); end "-";
function Sin (X : Angle) return Long_Float is Val : Long_Float := Long_Float (X - Bias) * Scale; begin return Sin (Val); end Sing;
function To_Angle (X : Long_Float) return Angle is begin return Bias + Support (X / Scale); end;
function Image (X : Angle) return String is Val : Long_Float := Long_Float (X - Bias) * Scale; begin return Long_Float'Image (Val); end Angles;
!example
--!corrigendum
!ACATS test
!appendix

From: John Barnes
Date: Friday, October 16, 2009

We had a meeting at the BSI recently and discussed a number of mostly
seemingly minor matters which had arisen and caused frustration in
practice (that is to real programmers working mostly in the aerospace
industries - your life could depend on them not making a mistake).

...
1 Cyclic fixed point. This is hardly minor but fixed point is used for
angles for navigation (aircraft bearing). The value of fixed point is
that it is accurate and meets the abstraction whereas the only cyclic
types we have are modular and to use them requires scaling once more.
So either we have to scale or we have to cope with wrap around at 360
degrees. Both provide opportunities for error.

There are, however, additional problems since the above works fine for
bearings and longitude but not for latitude. Thus adding 3 degrees to
88 degrees N does not give 91 degrees N but 89 degrees N with the
longitude changed by 180 degrees as well. So a package of operations
on latitude and longitude in fixed point might be a worthy addition.
Much as we added stuff on complex numbers last time.

...

****************************************************************

From: Tucker Taft
Date: Friday, 16 October 2009

Adding "mod 360.0" to the end of a fixed-point type for degrees would
seem to be reasonable syntax.

...

A latitude/longitude package sounds interesting, but we should try to
start from something that some project already finds useful.  I could
easily see spending a lot of energy creating something that no one ever
uses.

****************************************************************

From: Jean-Pierre Rosen
Date: Friday, 16 October 2009

Getting farther than a trivial package that anyone can write in half an
hour would be incredibly difficult, since there are lots of geographical
referentials, and n**2 conversions. Latitude and longitude are well
defined, but altitude can be relative to the surface or the center of
the earth. You must then decide if you use a spheric or ellipsoidic
model of the earth, WGS84 or other. And this is just the surface of it...

****************************************************************

From: Bob Duff
Date: Sunday, 18 October 2009

Sounds like a very special-purpose feature.  And a rather large change
(for example, as somebody else pointed out, it requires adding a couple
of new kinds of generic formal types).

I already hate modular types.  I think if you want to do a "mod"
operation, you should write "mod" in your expressions.  So adding a
new kind of modular type does not excite me.  (I do understand that
you can get overflows, which is a pain.)

****************************************************************

From: Terry Frogatt
Date: Sunday, 18 October 2009

I've spent a lot of my working life in this area!

Angles are the one area where fixed-point is more logical than float.
Why on earth should we navigate more accurately at Heathrow near 0 deg
than at Apia in Samoa near 180 deg? (That's what happens with float).
 I've landed at both, and Apia's runway is far narrower than Heathrow's.
But that's only a detail, the real problem is the wrap-round problem.

From as far back as the 1960/70s when I worked on the Jaguar flight
program on the Elliott 920M, to as recently as 2004 on the UK's Harrier
(a.k.a. USA's AV-8B) flight program on the AN/AYK14, angles were
represented in fixed-point, scaled so that wrap-round could be
implemented simply by ignoring the overflow. Thus, a heading of 355 deg
plus a wind drift of 10 deg gave a track of 5 deg.

And yes I can confirm that Ado's lack of cyclic fixed-point types is a
pain, although it might be a bit late in the day to be fixing it. When
BEE rewrote the Harrier program in Ada a lot of explicit wrap-round
code had to be added. (They also switched angles from fixed to float,
which they might not have done given a suitable cyclic fixed type).

If I declare an integer modular type such as "type degree is mod 360",
I guess their compiler has no choice but to generate wrap-round code (but
not for "type byte is mod 256"). But for fixed-point types, provided
"arbitrary" (non-power-of-2) scales are supported properly, the circle
of angles can be mapped onto the whole circle of underlying integers
with no wrap-round code. (Some folk call this mapping "BAMS").

Ideally I would like to be able to declare 4 cyclic fixed-point types

   type signed_degrees from -180.0 to almost +180.0
   type signed_radians from -pi to almost +pi
   type unsigned_degrees from 0.0 to almost +360.0
   type unsigned_radians from 0.0 to almost +2pi

followed by an "abs digits" clause to select accuracy-v-costs from the
available integer types, and I would like to be sure that all 4 mapped
onto the full integer circle without having to specify or know exactly
what the word-length was, or the value of the bottom bit (no more than
I do with float).

Thus the underlying bit pattern 1.1000000.... = -0.5 BAMS would
simultaneously represent -90, -pi/2, +270, or +3pi/2, in the 4 above
types. Providing all 4 types (per integer length) ensures that signed
& unsigned, and degrees & radians, don't get confused, whilst
conversions between them (which abound in the Harrier program) can be
encapsulated into suitably-named functions (which could be in-lined calls
to unchecked_conversion that generate no code). All 4 types have distinct
uses. The pilot's interface works in Degrees, whereas the navigation
internals work best in Radians, (remember that small-angle approximations
like sin(x)=x=tan(x) only work in radians, not BAMS, another source of
gotchas on the Harrier). Bearings are usually given Unsigned, 0 to 360,
whereas Longitudes are Signed, -180=west, +180=east. (And providing yet
more distinct types for Magnetic & True bearings would have avoided
several errors which weren't detected until after flight trials started).

As John has pointed out, Latitudes are different, -90=south, +90=north,
 but I feel this is up to the programmer to sort out. In all the code I've
seen, Latitudes are scaled to range from -180 to +180 like Longitudes. If
an equation produces a Latitude outside -90 to +90 it is sometimes
appropriate to "reflect" it in the pole (+91 becomes +89) and take the
back-bearing of the Longitude (add or subtract 180), but sometimes it
can only have occurred due to rounding errors, so that the correct
action is to "saturate" it at the pole (just as you do if you find
yourself taking the arcsine of a number slightly outside -1 to +1 due
to rounding). I don't think that wrapping at -90 or +90 is ever the
right behaviour.

Hope this helps. Regards, Terry.

****************************************************************

From: Terry Froggat
Date: Monday, 19 October 2009

[This is part of an email conversation between Terry Froggatt and Bob Duff.]

Bob, this is in answer to your questions, but is NOT a request
for yet more changes, I do support the idea of Cyclic Fixed Types,
but sadly it is far too late to be of any help to me now. I'm a
"lapsed" member of the UK BSI panel. I was not at the meeting, so the
comments below are my own, and may not represent the panel's views.
Regards, Terry. www.tjfroggatt.plus.com
 
---
 
Terry Froggatt wrote:
Angles are the one area where fixed-point is more logical than float.

Bob Duff wrote
Well, not the _only_ area.  Fixed point makes sense for money, and for time.

Terry's reply:
Yes fixed-point makes sense for money, but the reason is completely different.
For money, you want fractions which are exact (and not a power of 2).
Usually you want delta=small=1/100. You want "scaled integers".
When you are using fixed-point for mathematically "real" quantities
(either because you have no floating hardware, or because for angles
you want to exploit cyclic wrapround) there is no conceptual delta.
Ideally here you want "scaled fractions" defined by the value of their
most significant bit. (See Ada Letters Jan/Feb 1987 pp71-81?).

---

Terry Froggatt wrote:
Why on earth should we navigate more accurately at Heathrow near 0 deg

Bob Duff wrote:
Why "on earth" (roughly a sphere) indeed.  ;-)

Terry's reply:
The pun was intended. Your point about "roughly" is valid, though.
For example, the formula for working out which way to turn, to pray
facing Mecca, is straightforward on a spherical earth. On an ellipsoid,
the real-time programmer has to choose between an iterative accurate
algorithm or a faster less accurate algorithm. And you may have to
convert between mapping datums too. There's a lot of interesting math
in navigation, but a lot of trade-offs too, so I don't really support
trying to provide a lat/long package as part of the Ada language.

---
 
Terry Froggatt wrote:
From as far back as the 1960/70s when I worked on the Jaguar flight program
on the Elliott 920M, to as recently as 2004 on the UK's Harrier (a.k.a. USA's
AV-8B) flight program on the AN/AYK14, angles were represented in fixed-point,
scaled so that wrap-round could be implemented simply by ignoring the overflow.
Thus, a heading of 355 deg plus a wind drift of 10 deg gave a track of 5 deg.

Bob Duff wrote:
Can you give some example Ada code?  I'm not sure I understand what you mean.

Terry's reply:
   -- The following types and functions provide a neat mechanism for
   -- adding circular quantities scaled in BAMS, without raising an
   -- exception at any point in the circle. For example
   -- TRACK := Cyclic (HEADING + DRIFT);
   type ANGLE_ADD is record LEFT, RIGHT: ANGLE; end record;
   function "+" (LEFT, RIGHT: ANGLE) return ANGLE_ADD is begin
      return (LEFT, RIGHT);
   end "+";
   function Cyclic (ITEM: ANGLE_ADD) return ANGLE is begin
      if ITEM.LEFT >= 0.0 and then ITEM.RIGHT >= 0.0
      and then ITEM.LEFT + ANGLE'FIRST + ITEM.RIGHT >= 0.0 then
         return ITEM.LEFT + ANGLE'FIRST + ITEM.RIGHT + ANGLE'FIRST;  
      elsif ITEM.LEFT < 0.0 and then ITEM.RIGHT < 0.0
      and then ITEM.LEFT - ANGLE'FIRST + ITEM.RIGHT < 0.0 then
         return ITEM.LEFT - ANGLE'FIRST + ITEM.RIGHT - ANGLE'FIRST;
      end if;
      return ITEM.LEFT + ITEM.RIGHT;
   end Cyclic;

The above code is for a SIGNED type ANGLE, say -180.0..(almost)+180.0.
(When I wrote this in 1999 to simulate fixed-point wrap-round in Ada,
I was deliberately making the Cyclics explicit and not compulsory,
otherwise I could have defined a cyclic "+" directly).

It would be nice if Ada let me write just TRACK := HEADING + DRIFT;
by providing a modular "+" with no risk of overflow or exceptions,
And then as a distinct issue, it would be nice if this mapped this
onto assembly code "read heading, add drift, write track" with no
need for any wrap-round code, which it does provided angles are
scaled so that the "sign" bit is worth +180deg for unsigned angles
or -180 for signed angles (and the next bit is worth +90 either way).

---

Terry Froggatt wrote:
And yes I can confirm that Ada's lack of cyclic fixed-point types is a pain,
although it might be a bit late in the day to be fixing it. When BAE rewrote
the Harrier program in Ada95 a lot of explicit wrap-round code had to be
added. (They also switched angles from fixed to float, which they might
not have done given a suitable cyclic fixed type).

Bob Duff wrote:
I don't understand that (the switch from fixed to float), because neither one
does any modular/wrap-around arithmetic.

Terry's reply:
Yes, neither currently provides wrap-round. If there had been cyclic
fixed types BAE might have mimicked the AN/AYK-14's fixed-point working
as being least risky. But forced to choose twixt the inefficient fixed-point
code I've given above, or using an (inefficient?) floating point subtype
(where you can use the base type to do the add and much simpler wrap) you
can understand why they opted for float. (It wasn't my decision anyway). 
---

Terry Froggatt wrote:
...(Some folk call this mapping "BAMS").

Bob Duff wrote:
Sorry for my ignorance, but what's BAMS?

Terry's reply:
I was tempted to write "In some CIRCLES this mapping is called BAMS". ;-)
"Binary Angular Measurement System". I'd been using fixed-point angles
scaled in what I'd always assumed was the obvious way for many years
before I found out that it was called BAMS. It's certainly defined in
the documentation of the AV-8B, and in various on-line dictionaries.
I think there once was a mention in the Wikipedia article about
fixed-point number representations but it's not there now.
 
---
 
Terry Froggatt wrote:
Ideally I would like to be able to declare 4 cyclic fixed-point types
   type signed_degrees from -180.0 to almost +180.0
   type signed_radians from -pi to almost +pi
   type unsigned_degrees from 0.0 to almost +360.0
   type unsigned_radians from 0.0 to almost +2pi
followed by an "abs digits" clause to select accuracy-v-costs from the
available integer types, and I would like to be sure that all 4 mapped
onto the full integer circle without having to specify or know exactly what the
word-length was, or the value of the bottom bit (no more than I do with float).

Bob Duff wrote: 
Makes sense to me, except I don't understand the reference to float.

Terry's reply:
I no more need to know the bottom-bit value for fixed than for float.
When I define a float type I say "digits N" meaning I want at least
this accuracy, maybe more (but not the best you have if it costs me more).
When I define a fixed type for a "real" quantity (NOT money!) the same
is true: I want a given range and minimal accuracy, but I don't really
want or need to know the delta or small. (Except that, when you've found
the smallest integer type that fits my range and accuracy, if there are
some spare bits, please use them for added accuracy, not inaccessible range).
I think someone once proposed the "abs digits" syntax to declare fixed types
where "delta" was OMITTED and to distinguish them from float types, because
float types have relative accuracy and fixed types have ABSolute accuracy.
But equally you could do this by putting the all-important range first
"type FIXED is range L..U digits N; -- Upper endpoint probably excluded".
Ada83 had "delta" to meet the money requirement, Ada95's decimal fixed
types do money better, but by then it was too late to change delta to
digits on the "real" fixed types, so it is far too late to sort it now.
 
****************************************************************

From John Barnes
Date: Monday, 26 October 2009  9:03 AM

!topic Cyclic fixed point
!reference Ada 2005 RM3.59(1)
!from John Barnes 09-10-26
!keywords angels bearings
!discussion

Some of us have been discussing the problems of using fixed point for angles.
The note below roughly summarizes my view as of this moment. I am indebted to
feedback from Terry Froggatt, Tucker Taft, Michael Pickett, Bob Duff,
Jean-Pierre Rosen and anyone else whom I have regrettably overlooked.

...
We had a meeting at the BSI recently and discussed a number of mostly
seemingly minor matters which had arisen and caused frustration in practice
(that is to real programmers working mostly in the aerospace industries - your
life could depend on them not making a mistake).

...

1 Cyclic fixed point. This is hardly minor but fixed point is used for angles
for navigation (aircraft bearing). The value of fixed point is that it is accurate
and meets the abstraction whereas the only cyclic types we have are modular and
to use them requires scaling once more. So either we have to scale or we have to
cope with wrap around at 360 degrees. Both provide opportunities for error.

There are, however, additional problems since the above works fine for bearings
and longitude but not for latitude. Thus adding 3 degrees to 88 degrees N does
not give 91 degrees N but 89 degrees N with the longitude changed by 180 degrees
as well. So a package of operations on latitude and longitude in fixed point
might be a worthy addition. Much as we added stuff on complex numbers last time.

...

At first sight it might seem appropriate to use a syntax such as

type T is delta D mod M;

which merges the syntax of ordinary fixed point types and modular types.
Thus

type Bearing is delta 0.001 mod 360.0;

However, although a range of 0 degrees to 360 degrees is OK for many applications
such as navigation bearings, it is more helpful to use a range such as -180 to +180
for angles used in geometrical constructions and architecture.

Moreover, it seems reasonable to want the two ends of the range to be represented in
exactly the same way since they represent the same physical entity. Indeed we want
the range to map exactly onto a full unsigned word with the two ends of the range
(such as -180 and +180) being represented in exactly the same way. Thus using a
16-bit word the range from -180 to +180 would have

-180.0 -> 16#0000#
 -90.0 -> 16#4000#
   0.0 -> 16#8000#
  45.0 -> 16#A000#
  90.0 -> 16#C000#
+180.0 -> 16#0000#

It thus seems more appropriate to use syntax which includes the range.
Moreover, if we just give the range then it looks like an ordinary fixed point
type still so we had better give the mod thus

type Signed_Degrees is delta 0.0001 range -180.0 .. 180.0 mod 360.0;

where the value of mod has to statically match the range.

Perhaps the value after mod can be omitted. On the other hand perhaps the
range can be omitted if the lower bound is zero. But redundancy is a good
thing if they have to statically match.

The exact value of delta is pretty useless and is just given in order to
enable the compiler to choose an appropriate word length.

We would also be able to write

type Signed_Angle is delta D range -Ada.Numerics.Pi..Ada.Numerics.Pi mod
2*Pi;

The operations available would be much as expected. Addition and subtraction
are only permitted between values of the same type. Multiplication and
division by an integer are permitted as for ordinary fixed point types.
Should multiplication and division between values of modular fixed types be
permitted? Probably not. If you multiply an Angle by an Angle then you have
probably made a nasty mistake.

The operation abs could bring surprise. Thus if we have

type Curious is range -270.0 .. +90.0 mod 360.0;

C: Curious := -120.0;
D := abs C;

We might expect +120.0 but this wraps around to give -240.0 which is
nonsense. So abs is not permitted.

Conversions to other numeric types would be permitted as usual.

The attributes Mod, Delta and Small are available. However, Small cannot be
set by a use clause since this could upset the automatic wrap around. Mod is
useful when using the trigonometric functions from
Ada.Numerics.Elementary_Functions thus

A: Signed_Angle;

...

X := Sin(Float(A), Angle'Mod);

Note that this works no matter whether Signed_Angle is defined in terms of
degrees, radians or cycles. The latter might be

type Cycle is range 0.0 .. 1.0 mod 1.0;

Equality is permitted. Not sure about comparisons. It is clear that 45
degrees is greater than 40 degrees but not sure about -90 degrees and +90
degrees.

For completeness, it is necessary to provide an additional form of generic
parameter thus

generic
   type F is delta <> mod <>;

It does not seem fruitful to contemplate modular decimal types.

One problem with the above proposal is that on a binary machine a range such
as -180 to +180 does not permit the exact representation of 60 degrees which
mathematically is a very important angle. Oh, maybe it doesn't matter we
cannot represent one-third accurately in any scheme.

And the thought of writing a standard package for dealing with latitude and
longitude is just likely to lead to sleepless nights and no package.

Any thoughts anyone?

****************************************************************

From Bob Duff
Date: Monday, 26 October 2009 2009  9:41 AM

> !topic Cyclic fixed point

As I said before, I am not convinced that this feature is worth the trouble.
I'm mainly concerned about implementation cost.

> -180.0 -> 16#0000#
>  -90.0 -> 16#4000#
>    0.0 -> 16#8000#
>   45.0 -> 16#A000#
>   90.0 -> 16#C000#
> +180.0 -> 16#0000#

Hmm...  As a compiler writer, the above numbers look scary.

****************************************************************

From Randy Brukardt
Date: Monday, 26 October 2009  5:14 PM

Bob Duff writes:
 
> John Barnes wrote:
>
> > !topic Cyclic fixed point
>
> As I said before, I am not convinced that this feature is
> worth the trouble.
> I'm mainly concerned about implementation cost.

I agree with Bob.

> > -180.0 -> 16#0000#
> >  -90.0 -> 16#4000#
> >    0.0 -> 16#8000#
> >   45.0 -> 16#A000#
> >   90.0 -> 16#C000#
> > +180.0 -> 16#0000#
>
> Hmm...  As a compiler writer, the above numbers look scary.

They do to me, too. John might have missed the obvious problem: he has the
same representation for -180.0 and +180.0. That's going to make it really
hard to represent Bearing'First and Bearing'Last. I suppose one could define
the range such that the upper bound of the specified range isn't included in
the actual range (the real upper bound being Bearing'Last-Bearing'Small),
but that surely is going to complicate things. Especially as someone might
prefer that the lower bound is excluded rather than the upper (you would not
be allowed to write +180.0 in the scheme I suggested above - it's not in
range).

****************************************************************

From: John Barnes
Date: Monday, 26 October 2009  5:29 PM

Interesting point about First and Last. Maybe we don't need them. Maybe they
can be the same. Would it matter? Why would you want to use them? The
difficulty seems to me to lie with trying to pretend that they are
different. There is no difference physically between -180 degrees and +180
degrees (except in obscure bits of quantum mechanics but that's a
different application).

Terry Froggatt wanted the upper limit to be the given value minus Small.

Implementation looked rather easy to me at the code generation level.

****************************************************************

From: Randy Brukardt
Date: Monday, 26 October 2009  6:37 PM

John Barnes writes:
> Interesting point about First and Last. Maybe we don't need
> them. Maybe they can be the same. Would it matter? Why would
> you want to use them?

Well, the problem is that pretty much all of the semantics of scalar
subtypes in Ada is defined based on the range (or First .. Last) of the
subtype. And every scalar subtype has a range. I tried to eliminate that
requirement when I was working on discontiguous subtypes, and I completely
failed -- I ended up defining the range anyway.

You'd pretty much have to ban the use of any constraints with such a cyclic
type if you don't define the range. Along with the attributes 'First, 'Last,
'range. That could get pretty messy, and it would be totally inconsistent
with every other scalar type.

> The difficulty seems to me to lie with
> trying to pretend that they are different. There is no
> difference physically between -180 degrees and +180 degrees
> (except in obscure bits of quantum mechanics but that's a
> different application).
>
> Terry Froggatt wanted the upper limit to be the given value
> minus Small.

Right, that's the obvious answer. Fixed point already works that way and it
causes all kinds of problems writing the value of 'Last.
 
> Implementation looked rather easy to me at the code generation level.

Maybe if you know how to handle biased representations. If you don't
(Janus/Ada doesn't), it would appear that you'd have to add (at least) the
full generality of that. That's a *big* change to the code generation model.

****************************************************************

From: John Barnes
Date: Tuesday, 27 October 2009  2:54 AM

Randy Brukardt writes

>> Terry Froggatt wanted the upper limit to be the given value
>> minus Small.
>
> Right, that's the obvious answer. Fixed point already works that way
and it causes all kinds of problems writing the value of 'Last.

I don't think its the obvious answer. But maybe that is what one would have
to do.

It is a conundrum. Maybe one doesn't want constraints but it would seem nice
to be able to say to the pilot "steer East (90) with a tolerance of 2
degrees". Actually I don't suppose we really want Constraint_Error if he
veers slightly off course!

**************************************************************

From: Martin Dowie
Date: Tuesday, 27 October 2009  11:58 AM

FWIW...

Although the pilot (or any user of an avionic system) is presented with
degrees, it's very likely that value is converted before being 'used' by
the underlying software system. I've seen them converted into a
fixed-point range -1.0 .. 1.0-small; float range -180 .. 180; float
range -pi .. pi; float range -1.0 .. 1.0 and probably others.

I think getting a "System of Units" addition to the language would help
here more than trying to create a super-set solution to the curiosities
of deg/rad, az/el, u/v/w or lat/long. If there were a SoU feature to the
language I'm pretty sure that building lat/long et al packages on top
would be much simpler.

**************************************************************

From: John Barnes
Date: Tuesday, 16 February 2010  4:03 PM

Please find attached a further iteration (cycle perhaps?) of this intriguing
idea. [This is version /02 of the AI - Editor.]

If you get as far as reading towards the end of the discussion you will see that
I am disillusioned. Maybe that's just because I am broken down by age (and sex?)
but I conclude that binary machines are boring. The Babylonians were right - we
need base 60 hardware.

I hope we don't get a ton of snow in Boston.

**************************************************************

From: Robert Dewar
Date: Tuesday, 16 February 2010  4:19 PM

> If you get as far as reading towards the end of the discussion you
> will see that I am disillusioned. Maybe that's just because I am
> broken down by age (and sex?) but I conclude that binary machines are
> boring. The Babylonians were right - we need base 60 hardware.

Note that the next generation of chips will likely support decimal
floating-point natively.

**************************************************************

From: Tucker Taft
Date: Tuesday, 16 February 2010  10:24 PM

> About the only thing missing with such alternatives is literals. To
> get literals and to be able to represent fractions of angles to the
> required accuracy means cyclic fixed point and setting one's own small
> and hence not using hardware wraparound which somewhat defeats the
> object of the exercise.

If you overload unary "+" and unary "-" to take a (long) Float and return an
Angle then you come pretty close to having literals.

>
> Here is Ed's suggestion. Note the cunning use of conditional
> expressions in the initial values for the constants Scale and Bias.

This generic seems pretty straightforward to use, and has the potential to have
the desired performance characteristics while giving the user control over the
underlying representation.

I don't quite buy the claim that we can use "normal" multiplication if
Zero_Based is False.  Zero times anything has to be zero, and if Zero is
'Modulus/2, then you will have to do some correction on multiplication.

Probably better is for Angle zero
always be represented by Support'(0), and subtract Support'Modulus if the value
is >= Support'Modulus/2 when converting to Float.  Hence:

    function To_Float(X : Angle) return Long_Float is
    begin
        if Zero_Based or else
          X < Angle'Modulus/2 then
            return Long_Float(X)*Scale;
        else
            return Long_Float(X)*Scale -
              Long_Float(Angle'Modulus)*Scale;
        end if;
    end To_Float;

Similarly:

    function To_Angle(X : Long_Float) return Angle is
    begin
        if Zero_Based or else X >= 0 then
           return Angle(X/Scale);
        else
           return Angle(X/Scale +
             Long_Float(Angle'Modulus));
        end if;
    end To_Angle.

Actually, now that I think about it, it is important that Angle Zero be
represented by Support'(0) even for addition and subtraction.  So I think you
definitely want to use a scheme like the one suggested above.

...
>    Scale : constant :=
>      (if Zero_Based then High_Bound / Support'Modulus;
>        else 2 * High_Bound / Support'Modulus);
>    Bias : constant :=
>      (if Zero_Based then 0
>        else Support'modulus / 2);

These can't be named numbers because they aren't static.
Scale should presumably be type Long_Float, and Bias should be presumably of
type Support.

**************************************************************

From: Edmond Schonberg
Date: Wednesday, 17 February 2010  6:35 AM

For completeness, here is an updated version of the generic that John mentioned
in his message on cyclic fixed point.  Lightly tested with 0  to 360,  -180 to
180,  and 0 to 2.Pi.   I think this does most of what  was proposed, in Ada95 (I
removed the use of conditional expressions).

--  A package to provide cyclic fixed point numbers, to be used for angle
--  computations. Instantiations of generic package Angle_Representation
--  export a type Angle, together with  constructors, conversions, arithmetic
--  operations and elementary functions that apply to the type.

package Angles is
  type Units is (Radians, Degrees);

   generic
      type Support is mod <>;
      --  The modular type to be used for the underlying representation.
      --  Typically Interfaces.Unsigned_32 or Interfaces.Unsigned_64;

      Unit       : Units;
      --  The upper bound is given either in radians or degrees.

      High_Bound : Long_Float;
      --  Typically 360, 180, 2*Pi, or Pi.

      Zero_Based : Boolean;
      --  Values range from 0 to High_Bound or -High_Bound to High_Bound
      --  depending on the setting of this parameter. If Zero_Based, the
      --  representation is biased, to get maximum precision.

   package Angle_Representation is
      type Angle is private;

      function "+" (X, Y: Angle) return Angle;
      function "-" (X, Y: Angle) return Angle;
      function "*" (X : Angle; Y : integer) return Angle;
      function "*" (X : Integer; Y : Angle) return Angle;
      function "/" (X : Angle; Y : integer) return Angle;

      function "-" (X : Angle) return Angle;

      function Sin (X : Angle) return Long_Float;
      --  other elementary functions.

      --  Constructors.
      function To_Angle   (X : Long_Float)   return Angle;
      function To_Angle   (X : Long_Integer) return Angle;

      --  Conversions.
      function To_Integer (X : Angle)   return Long_Integer;
      function To_Float   (X : Angle)   return Long_Float;

      --  Display
      function Image      (X : Angle)   return String;

   private
      type Angle is new Support;
   end Angle_Representation;
end Angles;


with Text_IO;
with Ada.Numerics.Long_Elementary_Functions;
use  Ada.Numerics.Long_Elementary_Functions;
with Text_Io;
package body Angles is
   --  All intermediate computations are done as long_float, or whatever
   --  is the largest available floating point type.

   package LF_IO is new Text_IO.Float_IO (Long_Float);

   package body Angle_Representation is
      --  Ada 2012 notation
      --  Scale : constant Long_Float :=
      --   (if Zero_Based then High_Bound / Long_Float (Support'modulus)
      --     else 2.0 * High_Bound / Long_Float (Support'Modulus));

      --  Bias : constant Angle :=
      --  (if Zero_Based then 0 else Angle (2 ** Support'size / 2));

      --  Radian_Value : constant Long_Float :=
      --     (if Unit = Radians then 1.0 else Ada.Numerics.Pi / 180.0);

      Scale        : Long_Float;
      Bias         : Angle;
      Radian_Value : Long_Float;

      --  Utility to convert from the biased integer representation to
      --  a usable argument for display and for elementary functions.

      function Float_Val (X : Angle) return Long_Float;

      --  Given that the representation of angle Alpha is
      --   rep (alpha) = s(alpha) + bias
      --  the representation of Alpha + Beta is
      --         rep (alpha) + rep (beta) - bias

      function "+"(X, Y: Angle) return Angle is
      begin
         return Angle (Support (X) + Support (Y) - Support (Bias));
      end "+";

      function "-"(X, Y: Angle) return Angle is
      begin
         return Angle (Support (X) - Support (Y));
      end "-";

      function "*" (X : Angle; Y : integer) return Angle is
      begin
         return Angle (Support (X) * Support (Y))
             - Angle (Support (Y - 1)) * Bias;
      end "*";

      function "*" (X : Integer; Y : Angle) return Angle is
      begin
         return Angle (Support (X) * Support (Y))
             - Angle (Support (X - 1)) * Bias;
      end "*";

      function "/" (X : Angle; Y : integer) return Angle is
      begin
         return Angle (Support (X) / Support (Y));
      end "/";

      function "-" (X : Angle) return Angle is
      begin
         if Zero_Based then
            raise Constraint_Error;
         else
            if Support (X) < Support (Bias) then
               --  angle is negative
               return Angle (Support (Bias) + Support (Bias - X));
            else
               return Angle (Support (Bias) - Support (X - Bias));
            end if;
         end if;
      end "-";

      function Sin (X : Angle) return Long_Float is
      begin
         return Sin (Radian_Value * Float_Val (X));
      end Sin;

      --  If the literal is not  within the bounds of the type,
      --  a scaling step is needed.

      function To_Angle (X : Long_Float) return Angle is
         Full_Circles : constant Integer :=
           Integer (Long_Float'Floor (X / High_Bound));
      begin
         if Full_Circles = 0 then
            return Angle (Support (Bias) + Support (X / Scale));

         else
            return Angle (Support (Bias) +
               Support ((X - Long_Float (Full_Circles) * High_Bound) / Scale));
         end if;
      end To_Angle;

      function To_Angle (X : Long_Integer) return Angle is
      begin
         return To_Angle (Long_Float (X));
      end To_Angle;

      function Float_Val (X : Angle) return Long_Float is
      begin
         return Scale * (Long_Float (X) - Long_Float (Bias));
      end Float_Val;

      function To_Integer (X : Angle)   return Long_Integer is
      begin
         return Long_Integer (Float_Val (X));
      end To_Integer;

      function To_Float   (X : Angle)   return Long_Float is
      begin
         return Float_Val (X);
      end To_Float;

      function Image (X : Angle) return String is
         Target : String (1 .. 10) := (others => ' ');

      begin
         LF_IO.Put (To => Target, Item => Float_Val (X), Aft => 4, Exp => 0);
         return Target;
      end;

   begin
      --  Initialize global parameters. In Ada 2010 this can be done
      --  with conditional expressions. With some effort this could be
      --  done using Boolean'Pos in convoluted ways.

      Scale:= (2.0 - Long_Float (Boolean'Pos (Zero_Based))) *
        High_Bound / Long_Float (Support'Modulus);

      if Zero_Based then
         Bias := 0;
      else
         Bias := Angle (2 ** (Support'Size - 1));
      end if;

      if Unit = Radians then
        Radian_Value := 1.0;
      else
         Radian_Value := Ada.Numerics.Pi / 180.0;
      end if;
   end Angle_Representation;
end Angles;

**************************************************************

From: Tucker Taft
Date: Wednesday, 17 February 2010  7:22 AM

As I mentioned in my response to John, I believe it is simplified if, when
Zero_Based is False, you map:

   0 ==> 0
   Modulus/2-1 ==> High_Bound - small
   Modulus/2 ==> -High_Bound
   Modulus -1 ==> -small

That is, zero always maps to zero.  Then "+", "-", and "*" can use modular
arithmetic directly, as you originally suggested.

**************************************************************


Questions? Ask the ACAA Technical Agent