--- ai05s/ai05-0175-1.txt 2010/01/09 01:31:29 1.2 +++ ai05s/ai05-0175-1.txt 2010/02/19 07:39:36 1.3 @@ -1,4 +1,4 @@ -!standard 3.5.9(2) 09-10-28 AI05-0175-1/01 +!standard 3.5.9 10-02-16 AI05-0175-1/02 !class Amendment 09-10-28 !status work item 09-10-28 !status received 09-10-28 @@ -10,71 +10,76 @@ !summary Fixed point types that wrap around in a similar way to modular integer types -are introduced +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 +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 +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 +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 +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 are introduced using declarations of the form +Modular fixed point types could be introduced using declarations of the form -type Bearing is delta 0.01 range 0.0 .. 360.0 mod 360.0; +type T is delta D mod range L .. R; -This provides a type whose values range from 0.0 up to (but not -including) 360.0 with an accuracy of at least 0.01. +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. -Appropriate operations are provided much as for ordinary fixed point -types. Addition and subtraction are only permitted between values of -the same type. The result is normalized by the addition or subtraction -of 360.0 to bring it into range. +The range L .. R must either have lower bound zero or be symmetric about +zero. For example -(In hardware terms, it should happen automatically using unsigned -integer arithmetic.) +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 -Multiplication and division by an integer are defined. Conversions to -other numeric types are performed in the usual way. +The values wrap around so that 360 degrees is "the same" as 0 degrees +and similarly -Pi is "the same" as +Pi. -Abs and unary minus are not defined. +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. -Another example might be +The base range is from L to R-small. -type Angle is delta 0.001 range -Pi .. +Pi mod 2*Pi; +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. -An additional form of generic parameter is required thus +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. -generic - type F is delta <> range <> mod <>; +Attributes Delta, Small, and Modulus are available. Small cannot be set. +Similarly, First, Last and Range are available. -Consider the general case +F'First gives L, F'Last gives R-Small. -type F is delta D range L..R mod M; -Small is chosen so that the range L to R is mapped onto a suitable -unsigned word. The representations of L and R are identical. -Attributes Delta, Small, and Mod are available. Small cannot be set. -Similarly, First, Last and Range are available. +The predefined operations could either be as for ordinary fixed point +types or they could be restricted as described in the !discussion. -F'First gives L, F'Last gives R-Small. There is a static check that -Mod, L and R match appropriately. +An additional form of generic parameter is required thus +generic + type F is delta <> mod range <>; + + !wording <tbd> @@ -85,104 +90,208 @@ type T is delta D mod M; -which merges the syntax of ordinary fixed point types and modular types. +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 +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. +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 +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 --180.0 -> 16#0000# - -90.0 -> 16#4000# - 0.0 -> 16#8000# - 45.0 -> 16#A000# -..90.0 -> 16#C000# -+180.0 -> 16#0000# +type T is delta D mod range L .. R; -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 +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. -type T is delta D range L .. R mod M; +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). -where the value of mod has to statically match the range. For example +Consider -type Signed_Degrees is delta 0.0001 range -180.0 .. 180.0 mod 360.0; +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 -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. +A. Lots of operations -The exact value of delta is pretty useless and is just given in order to -enable the compiler to choose an appropriate word length. +Operations are basically the same as ordinary fixed point followed by +the application of wraparound when necessary. For example -We would also be able to write +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. -type Signed_Angle is delta D range -Pi..Pi mod 2*Pi; +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. -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. +Abs changes the sign if negative. -The operation abs could bring surprises. Thus if we have +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. -type Curious is range -270.0 .. +90.0 mod 360.0; +Conversion to and from other numeric types are as expected. -C: Curious := -120.0; -D := abs C; +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 -We might expect +120.0 but this wraps around to give -240.0 which is -nonsense. So abs is not permitted. Similarly unary minus. +B. Minimal operations -Conversions to other numeric types would be permitted as usual. +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 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 +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'Mod); +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 range 0.0 .. 1.0 mod 1.0; - -The attributes First and Last are defined. First returns L. Last does -not return R but R-Small. This prevents confusion which would occur since +type Cycle is delta 0.00001 mod range 0.0 .. 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. +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 +For completeness, it is necessary to provide an additional form of generic parameter thus generic - type F is delta <> mod <>; + type F is delta <> mod range <>; -It does not seem fruitful to contemplate modular decimal types. +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. -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. +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 @@ -196,24 +305,24 @@ 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). +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 +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. +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. ... @@ -223,14 +332,14 @@ 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. +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 +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. **************************************************************** @@ -238,11 +347,11 @@ 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 +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... **************************************************************** @@ -250,13 +359,13 @@ 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 +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 +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.) **************************************************************** @@ -266,31 +375,31 @@ 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 +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. + 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). +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", +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"). +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 @@ -299,37 +408,37 @@ 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 +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). +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 + 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. @@ -342,7 +451,7 @@ [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, +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. @@ -368,7 +477,7 @@ --- -Terry Froggatt wrote: +Terry Froggatt wrote: Why on earth should we navigate more accurately at Heathrow near 0 deg Bob Duff wrote: @@ -379,7 +488,7 @@ 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 +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. @@ -408,7 +517,7 @@ 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; + 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; @@ -423,7 +532,7 @@ 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 +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 @@ -436,7 +545,7 @@ 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). +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 @@ -488,12 +597,12 @@ 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 +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. +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 @@ -542,7 +651,7 @@ type T is delta D mod M; -which merges the syntax of ordinary fixed point types and modular types. +which merges the syntax of ordinary fixed point types and modular types. Thus type Bearing is delta 0.001 mod 360.0; @@ -564,7 +673,7 @@ 90.0 -> 16#C000# +180.0 -> 16#0000# -It thus seems more appropriate to use syntax which includes the range. +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 @@ -572,23 +681,23 @@ 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 +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 +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 +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 +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 @@ -598,14 +707,14 @@ C: Curious := -120.0; D := abs C; -We might expect +120.0 but this wraps around to give -240.0 which is +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 +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; @@ -614,16 +723,16 @@ X := Sin(Float(A), Angle'Mod); -Note that this works no matter whether Signed_Angle is defined in terms of +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 +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 +For completeness, it is necessary to provide an additional form of generic parameter thus generic @@ -631,12 +740,12 @@ 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 +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 +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? @@ -668,10 +777,10 @@ Bob Duff writes: > John Barnes wrote: -> +> > > !topic Cyclic fixed point -> -> As I said before, I am not convinced that this feature is +> +> As I said before, I am not convinced that this feature is > worth the trouble. > I'm mainly concerned about implementation cost. @@ -683,7 +792,7 @@ > > 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 @@ -701,11 +810,11 @@ 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 +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. @@ -718,8 +827,8 @@ 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 +> 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 @@ -733,13 +842,13 @@ '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 +> 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 +> +> 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 @@ -761,15 +870,15 @@ >> 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 +> 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 +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 +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! ************************************************************** @@ -790,6 +899,332 @@ 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