!standard A.5.8(0)                                  19-02-01  AI12-0305-1/01
!class Amendment 19-02-01
!status Hold 9-0-1  19-02-26
!status work item 19-02-01
!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. :-)

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