Version 1.2 of ai12s/ai12-0305-1.txt

Unformatted version of ai12s/ai12-0305-1.txt version 1.2
Other versions for file ai12s/ai12-0305-1.txt

!standard A.5.8(0)          19-02-01 AI12-0305-1/01
!class Amendment 19-02-01
!status work item 19-02-01
!status Hold 9-0-1 19-02-26
!status received 19-01-29
!priority Low
!difficulty Medium
!subject Bounded Big Integers
!summary
Define a Bounded Big Integer package to support arbitrary precision mathematics with bounded memory usage.
!problem
AI12-0208-1 defines big numbers packages. However, these packages have to be able to support numbers with arbitrary magintudes. As such, some sort of dynamic allocation is needed. For safety-critical applications, dynamic memory management is often not allowed, as there needs to be a guarantee that operations complete as expected. We need to provided bounded but larger than native precision mathematics for such applications.
!proposal
(See Summary.)
!wording
A.5.8 Bounded Big Integers [TBD: should Bounded Big Integers come before or after Big Rationals in the RM?]
An instance of the language-defined generic package Numerics.Big_Numbers.Bounded_Big_Integers provides an Optional_Big_Integer type and operations corresponding to those declared in Numerics.Big_Numbers.Big_Integers, but with the difference that the maximum storage (and, consequently, the set of representable values) is bounded.
The declaration of the generic library package Numerics.Big_Numbers.Bounded_Big_Integers has the same contents and semantics as Numerics.Big_Numbers.Big_Integers except:
- Bounded_Big_Integers is a generic package and takes a generic formal:
Capacity : Natural;
- two additional visible expression functions are declared:
function Last return Big_Integer is ((+256) ** Capacity); function First return Big_Integer is (-Last);
- the partial view of Bounded_Big_Integers.Optional_Big_Integer includes
a type invariant specification,
Type_Invariant => (if Is_Present (Optional_Big_Integer) then In_Range (Optional_Big_Integer, First, Last) or else (raise Constraint_Error))
[TBD: instead express this as a Dynamic_Predicate? If so, on Optional_Big_Integer or on Big_Integer?]
Each subprogram of an instance of Numerics.Big_Numbers.Bounded_Big_Integers behaves like the corresponding Numerics.Big_Numbers.Big_Integers subprogram except that type invariant checks are performed as described in 7.3.2. [TBD: change the preceding wording if we go with a predicate instead of a type invariant].
The type Optional_Big_Integer declared by an instance of Bounded_Big_Integers does not require finalization.
Implementation Requirements
For each instance of Bounded_Big_Integers, the output generated by Optional_Big_Integer'Output or Optional_Big_Integer'Write shall be readable by the corresponding Input or Read operations of the Optional_Big_Integer type declared in either another instance of Bounded_Big_Integers or in the package Numerics.Big_Numbers.Big_Integers. [This is subject to the preceding requirement that type invariant checks are performed, so that Constraint_Error may be raised in some cases.]
Implementation Advice
The implementation of (an instance of) Bounded_Big_Integers should not make use of controlled types or dynamic allocation.
[end of Implementation Advice]
The generic unit Numerics.Big_Numbers.Conversions provides operations for converting between the Big_Integer types declared in Numerics.Big_Numbers.Big_Integers and in an instance of Numerics.Big_Numbers.Bounded_Big_Integers.
The generic package Numerics.Big_Numbers.Conversions has the following declaration:
with Ada.Numerics.Big_Numbers.Big_Integers; with Ada.Numerics.Big_Numbers.Bounded_Big_Integers; generic with package Bounded is new Bounded_Big_Integers (<>); package Ada.Numerics.Big_Numbers.Conversions with Preelaborate, Nonblocking is function To_Bounded (Arg : Big_Integers.Big_Integer) return Bounded.Big_Integer; function From_Bounded (Arg : Bounded.Big_Integer) return Big_Integers.Big_Integer; end Ada.Numerics.Big_Numbers.Conversions;
AARM Note: No Bounded_Big_Rationals generic package is provided.
!discussion
Several items have been posed as open issues about this package:
* Should Capacity be expressed as a generic formal (as it
is in the current proposal) or instead as a discriminant? Each approach has advantages and disadvantages.
* What should the meaning of the capacity values be, and how do
those map to First/Last values? The current AI has a very implementation-oriented approach, but perhaps a more user-oriented approach would be better (say, a number of decimal digits).
!ASIS
[Not sure. It seems like some new capabilities might be needed, but I didn't check - Editor.]
!ACATS test
ACATS B- and C-Tests are needed to check that the new capabilities are supported.
!appendix

From: Steve Baird
Sent: Tuesday, January 29, 2019  7:23 PM

Bounded Big Integers were originally part of AI12-0208, but it was
decided to split them off into a separate AI. This decision was
made in part because there was no consensus about the answers to
several questions:

   1) Should Capacity be expressed as a generic formal (as it
      is in the current proposal) or instead as a discriminant?
      Each approach has advantages.

   2) What should the mapping from Capacity values to
      First/Last values be? The current proposal somewhat
      arbitrarily defines Last = 256**Capacity (and First=-Last).
      This has the advantage of portability, but perhaps it
      overconstrains implementations.

   3) Do we have a clear understanding of what problem this language
      feature is intended to solve?

The currently proposed wording for bounded big integers appears below.
[Actually, in version /01 of the AI - Editor.]
The consensus at the moment seems to be to omit bounded big integers from
Ada 2020, although there has been no formal vote yet.

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

From: Randy Brukardt
Sent: Friday, February 1, 2019  7:23 PM

>Bounded Big Integers were originally part of AI12-0208, but it was 
>decided to split them off into a separate AI. This decision was made in 
>part because there was no consensus about the answers to several 
>questions:
>
>   1) Should Capacity be expressed as a generic formal (as it
>      is in the current proposal) or instead as a discriminant?
>      Each approach has advantages.
>
>   2) What should the mapping from Capacity values to
>      First/Last values be? The current proposal somewhat
>      arbitrarily defines Last = 256**Capacity (and First=-Last).
>      This has the advantage of portability, but perhaps it
>      overconstrains implementations.

This is an incomplete description of my position on this issue.

I think the Capacity setting should be clearly described in terms that the 
end-user will understand. Ada has a long tradition of using user-oriented 
type declarations (digits and delta and ranges); the implementation 
implications are secondary.

In the existing presentation, nothing ever attempts to tell anyone what 
Capacity means. It simply is described as setting First/Last, and it's up 
to the user to try to figure out how that relates to what they need. That 
doesn't seem to be a very Ada approach.

I think Steve was trying to use the capacity to describe the number of storage 
elements used; at a minimum, the wording needs to say that. But given that we 
don't even know the size of a storage element, I think we're going about this 
the wrong way.

I would prefer have the capacity represent something directly meaningful to 
the end user. Since we have to avoid using BigInts to describe BigInts, we 
can't use a range. But we could use something like the number of decimal 
digits required.

I'd also suggest giving minimum bounds for First and Last, rather than hard 
coding some values. So, one could use a decimal digit capacity and a binary 
implementation. Ergo, Last would be described to be at least 10**Capacity, 
but the actual value would be implementation-defined. (That is, have it work
like an integer type declaration - what a concept! :-)

I note that such a description for Capacity also answers the generic vs. 
discriminant issue, as it doesn't seem likely that we could ever allow 
expressions involving "**" and Log2 as discriminant expressions. (I know Steve 
tried to find some rules that would allow simple expressions involving 
discriminants as part of a declaaration, but I'm pretty certain a Log2 lookup 
table isn't part of that. ;-).

So I'd be happy with just these changes (but I'm probably the only one :-).

> 3) Do we have a clear understanding of what problem this language
>    feature is intended to solve?

Well, I had to put something into the AI, so this is what I wrote:

  AI12-0208-1 defines big numbers packages. However, these packages have to be 
  able to support numbers with arbitrary magintudes. As such, some sort of 
  dynamic allocation is needed. For safety-critical applications, dynamic 
  memory management is often not allowed, as there needs to be a guarantee 
  that operations complete as expected. We need to provided bounded but 
  larger than native precision mathematics for such applications.

We do need to be sure we agree with this, and if we don't or aren't sure, then 
clearly the best course of action is "No Action". It could very well make 
sense to see if there really is any user demand for such a package, because 
if there isn't, any time spent on it is wasted. (Humm, my meter is running. 
Ding! $$ Ding! $$ Better move on. :-)

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

Questions? Ask the ACAA Technical Agent