Ada design documents

Ada design documents

[Ehud Lamm]

Hi,

I always find reading the Ada9x (and older) design documents fascinating.
Arecent discussion here pointed to an older discussion of
access-to-subprogram types, whcih referred to the MRT documents. Reading
those was very informative.
Reading Tuft's LSN about multiple inheritance is another example, and the
LSN about hierarchical libraries is also highly recommended to reaaders
that are not from the Ada9x team/DR etc.

I was looking for a discussion of the "storage pool" mechanism, but wasn't
able to find it. 
Can anyone point me in the reight direction?

Thanks

P.S
If anyone wants to read the documents I referred to, he may go to the AJPO
directory at http://wuarchive.wustl.edu/languages/ada/ajpo/ . Going into
the pol-history direcotry will bring you to many interesting documents.

Ehud Lamm mslamm@mscc.huji.ac.il
http://purl.oclc.org/NET/ehudlamm <== My home on the web 
Check it out and subscribe to the E-List- for interesting essays and more!

Re: Ada design documents

[Tucker Taft]

Ehud Lamm wrote:
> 
> Hi,
> 
> I always find reading the Ada9x (and older) design documents fascinating.
> Arecent discussion here pointed to an older discussion of
> access-to-subprogram types, whcih referred to the MRT documents. Reading
> those was very informative.
> Reading Tuft's LSN about multiple inheritance is another example, and the
> LSN about hierarchical libraries is also highly recommended to reaaders
> that are not from the Ada9x team/DR etc.

For a list of the Ada 9X Language Study Notes, see:

    http://www.adaic.org/standards/95lsn/lsn-titles

The actual LSNs may be found in the enclosing directory:

    http://www.adaic.org/standards/95lsn/

> I was looking for a discussion of the "storage pool" mechanism, but wasn't
> able to find it.
> Can anyone point me in the reight direction?

There is no LSN on that.  Some of the rationale for storage pools
is given in the old "Mapping Specification" documents, in Appendix
G, but I don't know of any on-line versions of that document other
than version 4.6, which omitted appendix G for some reason.

You still might find Mapping Spec version 4.6 interesting reading:

    http://www.adaic.org/standards/95lsn/ms-4.6

> 
> Thanks
> 
> P.S
> If anyone wants to read the documents I referred to, he may go to the AJPO
> directory at http://wuarchive.wustl.edu/languages/ada/ajpo/ . Going into
> the pol-history direcotry will bring you to many interesting documents.
> 
> Ehud Lamm mslamm@mscc.huji.ac.il
> http://purl.oclc.org/NET/ehudlamm <== My home on the web
> Check it out and subscribe to the E-List- for interesting essays and more!

-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: Ada design documents

[Tucker Taft]

Ehud Lamm wrote:
> 
> Hi,
> 
> I always find reading the Ada9x (and older) design documents fascinating.
> Arecent discussion here pointed to an older discussion of
> access-to-subprogram types, whcih referred to the MRT documents. Reading
> those was very informative.
> Reading Tuft's LSN about multiple inheritance is another example, and the
> LSN about hierarchical libraries is also highly recommended to reaaders
> that are not from the Ada9x team/DR etc.
> 
> I was looking for a discussion of the "storage pool" mechanism, but wasn't
> able to find it.
> Can anyone point me in the reight direction?

I found an old "Mapping Specification" document in the "history"
section of the Ada Information Clearinghouse (www.adaic.org).  I have
attached below the section of the Rationale relating
to storage pools.

> Thanks
> 
> P.S
> If anyone wants to read the documents I referred to, he may go to the AJPO
> directory at http://wuarchive.wustl.edu/languages/ada/ajpo/ . Going into
> the pol-history direcotry will bring you to many interesting documents.
> 
> Ehud Lamm mslamm@mscc.huji.ac.il
> http://purl.oclc.org/NET/ehudlamm <== My home on the web
> Check it out and subscribe to the E-List- for interesting essays and more!

-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

-----------------------------
Extract from:
  http://www.adaic.org/pol-hist/history/9x-history/mapping/map-spec-Mar92.txt
-----------------------------

S.G.3. User-Defined Allocators

User-defined  allocators  provide  the application programmer with control over
the management of dynamically allocated storage.  Examples of critical  details
that  a user might need to control include the placement of objects in pages of
different kinds of memory, control over fragmentation, and  trade-offs  between
speed of allocation and deallocation versus economy of storage space.

An alternative to a language-defined interface, such as the one specified here,
is  for  the  user  to   avoid   the   use   of   allocator   expressions   and
UNCHECKED_DEALLOCATION,  and  perform  all allocation and deallocation directly
through user-defined procedures.  There are limitations  to  this  alternative.
Some of these are:

   - A  compiler  might  represent  certain  types  of  data in a way that
     permits the storage to be non-contiguous.  That is,  there  might  be
     implicit    indirect    references   (i.e.   pointers)   within   the
     representation of the data, from one part to another.   There  is  no
     way for a user-defined allocation procedure to determine whether this
     is required, and to initialize  the  pointers  properly.    With  the
     present specification, the compiler-generated code can do this, after
     the  address  of  the  storage  is  obtained  from  the  user-defined
     allocator.

   - A  compiler  might  need to allocate extra storage for implementation
     data with certain types of objects (examples include the index bounds
     of  an array and storage for the discriminants of a record).  In some
     contexts explicit representation of such  implementation  data  might
     not  be necessary, since the constraints of the object are statically
     determinable.  Determining whether extra  storage  is  required,  how
     much  space it occupies, and how it needs to be initialized, presents
     a problem for a user-defined storage allocation  scheme,  similar  to
     the  problem  with  non-contiguous  representation.    In  fact, this
     problem is likely to  co-occur  with  the  previous  one,  since  the
     implementation  data might be stored discontiguously from the rest of
     the object.

   - A  compiler  might  assume  special  alignment  (e.g.   even-numbered
     addresses) for certain types of data.  Without some special interface
     such as is provided here, the  user  would  be  limited  to  defining
     storage  allocators  for types where the compiler does not assume any
     special alignment.
   - To be completely equivalent, the  user-defined  allocation  procedure
     would  also  need  to perform any default initialization required for
     the object.  This would require complete  visibility  of  the  object
     type declaration, and any operations that need to be performed in the
     course of the initialization, which is not possible for  limited  and
     private types.


S.G.3.1. STORAGE_POOL Representation Clause

The  proposed  association  of  an  access  type  with a storage pool using the
STORAGE_POOL attribute, allows the construction of user-defined allocators.  In
Ada, the new statement provides two complementary features:  dynamic allocation
of storage for data structures, and the initialization of these  objects  based
on  the  type  information.   With complex types (especially those that involve
unconstrained arrays and variant records), this  initialization  may  be  quite
complex.    In  these latter cases, it is often difficult for the user to mimic
the compiler work of initialization, if it chooses to  provide  the  allocation
routines  explicitly.    On  the  other  hand, there are many different storage
allocation algorithms.  A large number of trade-offs are involved (e.g. whether
an allocation request should be temporarily held when storage is not available,
or immediately raise STORAGE_ERROR), and the right choice often depends on  the
specific system architecture and application needs.

The  separation  of  duties  provided  by  user-defined  allocators  allows the
compiler to concentrate on using its knowledge of the type structure to perform
the  correct  and most efficient initialization, while providing a hook for the
user to choose and implement his favorite allocation technique without worrying
about initialization chores.  (This of course is optional; the default behavior
is as in Ada 83 where the compiler/RTS do both tasks.)

The model  provided  by  the  user-defined  allocator  matches  the  Ada  model
regarding  the  life-time  of access types and their corresponding collections.
Collections are not required to be deallocated on scope exit (but  in  Ada  9X,
they  do  if the STORAGE_SIZE attribute is specified).  Since a pool object may
serve multiple collections  (or  access  types),  the  objects  of  a  specific
designated  type are not deallocated from the pool object when the scope of the
corresponding access type is exited.  A user can achieve this effect  by  using
either  finalization  or UNCHECKED_DEALLOCATION.  The entire pool object is, of
course, deallocated when it goes out of scope, but the  rules  ensure  that  no
access  type  that uses that pool can still be active at that point; thus there
is no danger of dangling references.

A pool object is similar to the default heap in most  Ada  83  implementations:
multiple access types can share it, but objects of the designated types are not
automatically deallocated.

Allowing multiple access types to share a pool object provides  the  user  with
the  ability  to  share  allocation  algorithms  for  multiple  types.  It also
prevents unnecessary pre-allocation of storage (usually  up  to  the  maximum),
when  it  is known that ``groups'' of objects have disjoint life-times and thus
they can time-share a memory resource.  The ALIGNMENT parameter of the ALLOCATE
procedure   facilitates   pool   sharing   by   types  of  different  alignment
requirements.  Of course,  such  different  alignment  requests  might  not  be
supported by a user-defined allocation routine.

The  pool object concept encapsulates the allocation/deallocation routines with
the actual memory  resource.    The  type  ROOT_STORAGE_POOL  is  intentionally
similar  to  the  CONTROLLED  type.   It is our intention to consider, in later
versions, a change that will make it a derived type of  CONTROLLED  because  of
this inherent similarity.

It  is  envisioned  that  the  ALLOCATE/DEALLOCATE  operations  will use mutual
exclusion mechanisms such as protected records to ensure their correct behavior
in a multi-tasking program.

Usually, if only one access type is associated with the same pool object, these
two should be in the same scope.  It is illegal for the pool's scope to be  any
``deeper''  than the access type scope, since then dangling references would be
possible.  On the other hand, having the the access type scope be  deeper  will
leave  the  pool  object alive longer than is required, and its storage will be
held unnecessarily.

If all the access types that are using a given pool are declared in subprograms
that  are  more  deeply  nested than that of the pool, then it is impossible to
have dangling references for the  same  argument  as  above.    However,  since
objects  of  the  designated types may occupy the pool alternately (see example
below), there will be a trade-off between the frequency of entering and exiting
the  access  type  scope  and  the  overhead  associated  with  allocating  and
initializing the pool object itself.  (Sometimes, the initialization of a  pool
object  may require splitting sub-blocks, setting bit-vectors, pointers arrays,
etc.)

If the access types are in different scopes (deeper than  that  of  the  object
pool  itself),  their storage will be held longer than necessary.  If this is a
problem, then sub-pool objects may be created at the scope of each access type,
and point to the ``master'' pool.  When the object representing the sub-pool is
no longer in scope (i.e., its associated access type is also out of scope), the
user-defined  finalization routine can deallocate it, thus freeing space in the
master pool.

      -- This example shows how a single pool object may be used
      -- alternately by two access types living in sibling scopes.

    procedure EXAMPLE is

       -- Declare a pool object of some size to be shared by
       -- multiple types
       type BLOCK_LENGTH_TYPE is SYSTEM.STORAGE_COUNT (1..1000);
       type MY_POOL_TYPE is new SYSTEM.ROOT_STORAGE_POOL
        with record is
          BLOCK : BLOCK_LENGTH_TYPE;
       end record;
       POOL_OBJECT : MY_POOL_TYPE;

       -- Objects designated by T will be allocated in POOL_OBJECT
       type T is access SOME_TYPE;;
       for T'STORAGE_POOL use POOL_OBJECT;
       PTR : T;

       procedure PROC_1;
          -- Objects designated by T1 will be allocated in POOL_OBJECT
          type T1 is access SOME_TYPE_1;
          for T1'STORAGE_POOL use T'STORAGE_POOL;
          PTR_1 : T1;
       begin
          -- Perform various allocations using PTR_1 and T1
       end PROC_1;

       procedure PROC_2;
          -- Objects designated by T2 will all be allocated in
          -- POOL_OBJECT
          type T2 is access SOME_TYPE_2;
          for T2'STORAGE_POOL use T'STORAGE_POOL;
          PTR_2 : T2;
       begin
          -- Perform various allocations using PTR_2 and T2
       end PROC_2;

    begin
       for I in 1..N loop
          PTR := new SOME_TYPE;  -- (*1)
          PROC_1;
            -- (*2)
          PROC_2;
       end loop;
    end EXAMPLE;


Notes on the example:

   1. The memory occupied by these  allocations  (unless  being  unchecked
      deallocated)  will  live  until  PROC  is  exited and POOL_OBJECT is
      reclaimed.

   2. Here, objects of  SOME_TYPE_1  no  longer  exist.    However,  their
      storage  is  still  being  held  in  POOL_OBJECT,  unless explicitly
      deallocated.

      There are several trade-offs that need to be balanced  by  the  user
      here:    The  frequency  and  size of allocations vs the pool object
      size; the cost of allocation/deallocation of specific  objects;  the
      number of iterations and the relative length of the other code, etc.

      Based  on this trade-offs, the user can decide when and how often to
      deallocate objects, and how to sub-divide the pool object.

We have considered other alternatives for supporting this functionality.    One
alternative  would  simply  associate  two operations, ALLOCATE and DEALLOCATE,
with an access type.  These operations would be called in the same  way  as  in
the  current  proposal,  but  would  have no implicit association with the pool
object.  In fact, the concept of a pool object would not  exist;  it  would  be
represented  as  a hidden state of the operations (or the package in which they
are included).  The heap used by these types will be finalized when the  access
type  goes  out of scope.  But since there are no INITIALIZE/FINALIZE routines,
which are called automatically by the generated code, this would all have to be
dealt  with  explicitly by the user.  Furthermore, the code in these operations
would have no information about the types that use them,  so  the  checks  that
avoid  invoking,  for  example,  an  allocation  routine after the implied pool
object has gone, would be close to impossible to implement.

The issues of initialization and  finalization  of  the  user-defined  ``heap''
would  then  have to be dealt with explicitly, and be much more error-prone, or
an additional set of rules would have to be specified.  Therefore,  the  issues
of dangling references or heaps that live longer than necessary will have to be
addressed by the user in a way that is less safe and convenient.

Thus,  we  determined  that  this  approach  does  not  provide   the   desired
functionality and does not encapsulate well the service.

Another approach that was suggested was to specify the user-defined pool object
in the new construct itself.  This would require modifying the source  code  in
every  place  where such an allocation takes place (and the possible occasional
omission of some).  In the current proposal, everything  is  specified  in  one
place  and  applies to all allocations, deallocations, and finalizations of the
designated types.


S.G.3.2. Interactions with STORAGE_SIZE Attribute

The possibility of allowing STORAGE_SIZE  to  be  specified  for  a  type  with
user-defined  storage allocation was considered.  The reasonable interpretation
of this combination is for the compiler to pass the user-specified storage size
to  the  user-defined  storage  manager upon initialization of the pool object.
This possibility was rejected, on the grounds that first, this  information  is
already present as part of the pool object declaration, and providing it in two
different ways would be redundant.  Second, the  information  provided  by  the
STORAGE_SIZE  clause  could  not  be used effectively by a user-defined storage
manager.  The user-defined pool object must be declared and elaborated prior to
the  type to which it is bound.  If the user-defined pool is to be allocated on
the stack, the size must be fixed by that point.    The  problem  is  that  the
expression  for  STORAGE_SIZE  need  not be static, and so may not be evaluated
that early.  By the time  the  information  from  the  STORAGE_SIZE  clause  is
available,  it  is  too  late  to  use  it.  This problem of obtaining the size
information from the representation clause early enough to be  used  in  sizing
the  user-defined  storage pool is aggravated if the user wants to use a single
storage pool for several access types.


S.G.3.3. MAX_STORAGE_SIZE Attribute

There is a well-defined requirement for user control  over  storage  allocation
and  recovery.    A  very  important special case is where the user can achieve
constant-time allocation and  deallocation  operations,  by  using  a  pool  of
same-sized  storage blocks.  The MAX_STORAGE_SIZE attribute is intended to tell
the user the size of block that would be required in this case.

Note that the SIZE attribute of a type does not meet this requirement, since it
yields the minimum number of bits needed to hold an object of this type.