Re: Ragged Array Proposal

["Nick Roberts" <nickroberts@callnetuk.com>]

Robert I. Eachus <eachus@mitre.org> wrote in message
news:37EA9A72.594ED8F5@mitre.org...
[...]
|    Not worthless, just excessive.  There are already two ways to do what
| you seem to want: arrays of Ada.Strings.Unbounded.Unbounded_String, or a
| generic
| package that does what you want using Controlled types.

Using Ada.Strings.Unbounded is one of the unappealing alternatives I was
talking about.

To use the fructuous example of another post in this thread, in Ada 95 one
would have to declare:

Fruits: constant array (Positive range <>) of Unbounded_String :=
    (To_Unbounded_String("Apple"),
     To_Unbounded_String("Orange"),
     To_Unbounded_String("Pear"),
     ...);

This technique suffers from the same heavy syntax of the allocator
technique, and while it saves having to explicitly declare an access type,
it's almost certain to have an implementation that involves dynamic
allocation (together with the further baggage of a controlled type). A very
clever optimiser might be able to perform pre-allocation (as mentioned in
other posts in this thread), but I suspect that most Ada compilers, in
reality, would not.

An overloading of "+" could be declared to slim down the declaration of each
component, but this does not resolve the inefficiency.

Similar comments apply to the use of Ada.Strings.Bounded. In this case,
there is the same syntactic clumsiness (with the addition of a generic
instantiation), and also inefficiency (albeit wasted memory rather than
dynamic allocation).

|    Note: I have implemented a slightly more general version of that
| package, where my major concern was to provide extensible records.
| Hmmm.  What you want seems to be a generic package with a specification
| like:
|
|    with Ada.Finalization;
|    generic
|      type Index is (<>);
|    package Ragged is
|
|      type Element is private with null;
|      type Element_Reference is access all Element'Class;
|      type Ragged_Array is array (Index range <>) of Element_Reference;
|
|      procedure Assign_To(R: in out Ragged_Array; I: in Index, E:
| Element);
|      function Dereference(R: Ragged_Array; I: Index) return
| Element'Class;
|
|    private
|      -- implemenation defined...
|    end Ragged;
|
|    Any comments?

This kind of package really only 'wraps up' the techniques using access
values or fixed-size buffers; it doesn't resolve the underlying problems.
Use of this kind of package will still suffer from the heavy syntax (in the
above case, a generic instantiation, a tagged type derivation, a declaration
of an object, and then several calls to a procedure!), and the inefficiency
of using dynamic allocation or fixed-size buffers.

| If you want to
| supply a package like that it would probably be considered, if not for
| the next standard, at least to be provided by all implementors.  (And if
| you do it before the ARG meeting Monday, it might even get considered
| there...)

I would be delighted for the ARG to consider my ragged array proposal, if it
comes within the group's remit. I will endeavour to get some or all of the
'Changes to the RM' section written before Monday.

I want to illustrate what I think is the key advantage of ragged arrays. In
the examples in my proposal, I declare an abstract type Figure, and a ragged
array type Figure_Array, and then various concrete types derived from
Figure. I then declare a record type Compound_Figure with a component of
this ragged array type, and finally I declare a subtype of this record type,
Double_Triangle.

I don't specify the components for the concrete figure types, but suppose
the type Circle has components for a radius and a centre (on flat plane),
and that there is a Label figure which has components for a Wide_Character
and a centre. Furthermore, suppose we declare another subtype:

subtype Telephone_Button is Compound_Figure(2)(Circle,Label);

A value could be assigned to an object, Star say, of the Telephone_Button
subtype as follows:

Star := (2, (15,(23,47), ('*',(23,47)));

Now, consider how such a record subtype could be implemented in Ada 95. One
possibility is:

type Figure_Access is access all Figure'Class;

type Figure_Array is array (Positive range <>) of Figure_Access;

type Compound_Figure (Length: Natural) is new Figure with
    record
        Constituents: Figure_Array(1..Length);
         ...
    end record;

Now consider declaring the subtype Telephone_Button. This can done with:

subtype Telephone_Button is Compound_Figure(2);

But note how the subtypes of the components of the array cannot be
constrained. Being able to impose such a constraint would be a valuable
technique in many situations.

Now consider assigning a value to an object of this subtype. We can either
use an allocator:

Star := (2, new Circle(15,(23,47)), new Label('*',(23,47)));

Or we can used aliased objects:

TBC: constant aliased Circle := (15,(23,47));
SBL: constant aliased Label := ('*',(23,47));

Star := (2, TBC'Access, SBL'Access);

I think both of these methods are less preferable to the ragged array. It's
obvious that the syntax is less concise. What may not be so obvious,
however, but which, I am convinced, is of great significance, is that the
above Ada 95 version (or, indeed, any Ada 95 alternative) will generally be
less efficient, in terms of memory used and often execution speed too, and
there's _no way around it_ except kludges.

It's unfortunate that it is difficult to come up with a realistic example
that isn't either too complicated for an example, or simply dismissed with a
wave of the hand as being unrealistic. But I am convinced that this is a
problem that could be critical for certain applications. Suppose an
application had extremely limited memory, for example (e.g. an embedded
controller), or needed to store a huge number of items of subtypes similar
to Telephone_Button; the memory saving from the use of ragged arrays could
be significant, or even critical.

-------------------------------------
Nick Roberts
http://www.callnetuk.com/home/nickroberts
http://www.adapower.com/lab/adaos
-------------------------------------