Version 1.1 of ais/ai-20302.txt

Report of the ARG Select Committee on Containers
February 3, 2004


Executive Summary

The committee selected the second proposal as a starting point for a
standard containers library, with a number of simple changes. The
changes were simple enough that we produced a version of the library with
the changes made (AI-00302-3/01).

The resulting proposal is not much larger than the Vector and Matrix
libraries already adopted for the standard. It also should be a good seed
for a more encompassing secondary standard.

Therefore, we recommend that the ARG adopt this alternative for the standard.

     By the ARG Select Committee on Containers:

           Randy Brukardt
           Bob Duff
           Tucker Taft

Full Report

Goals

A core library of containers is an important addition to Ada. Other competitive
programming languages include standard sets of containers, and these are
widely used. Users often note that a standard set of containers is a missing
piece of Ada. In addition, adding such containers to the standard is not
a large burden on implementers.

However, the resources available for work on the standard preclude adding a
large container library to the standard. If the library is too large, it will
be insuffiently reviewed, and that has the danger of providing something
useless.

Therefore, the committee settled on a limited set of goals:
   (1) To provide a number of the most useful containers to Ada users in
       a standard fashion;
   (2) To provide a framework for future work in this area (hopefully leading
       to a secondary or de-facto standard).

We considered other goals as well. Performance issues were deemed of secondary
importance. Most uses of containers (indeed, most software) do not have
critical performance requirements. To provide a library with the variety of
components needed to meet critical requirements (bounded and unbounded forms,
array and list implementations, etc.) would be beyond the resources available
to work on the standard. Moreover, the existence of many components actually
makes construction of simple applications harder: the programmer has to choose
a component based on performance considerations that are simply irrelevant for
the application.

Evaluation of existing proposals

We determined that the most important containers are the following:
    * extensible "vectors" (like an array, indexed by any discrete type);
    * (hashed) "maps" (or "hash table", with arbitrary keys);
    * (sorted) "sets" (set of arbitrary items).
The names "map", "set", and "vector" are those used in the Java containers.

We evaluated the two proposals for their support of these components.

Alternative 1 (AI-302-1/07) contains a number of low level data structure
components such as Lists, Bags, Queues, etc. These can be used to create
"vector", "map", and "set" containers, but the containers themselves are
absent. Moreover, most of these components are relatively easy to create
when needed.

Alternative 2 (AI-302-2/02) contains mainly five containers: vector, list,
map, set, and multiset. These include the abstractions mentioned above. We
also determined that the basic design was consistent and sound.

Therefore, we discarded alternative 1, and concentrated on improving and
simplifying alternative 2.

We decided the sorts of changes that we would consider. The great value to
having containers in the standard is that they are standard: everybody has
them and can use them. Perfection is not required of the standard components.
Moreover, what is one person's "improvement" is another's "mistake". In
addition, we run the risk of introducing real errors by further fiddling.

Therefore, we decided to simplify the interfaces by deleting unnecessary
capabilities, by systematic substitutions, and by introducing missing
capabilities (along with general wordsmithing). In particular, we avoided
changing existing interfaces unless there was a clear error.

The specific improvements and simplifications are detailed in the Appendix.

Performance issues

For the purposes of components in the standard, the precise performance of them
is not important. Whatever the performance is will be good enough for the vast
majority of uses - in prototyping, quick and dirty programs, and the majority
of programs that aren't performance critical. Therefore, we provide only a
single version of each component. We don't, for instance, provide both Vectors
and Lists, which are really the same abstraction with the different performance
characteristics.

However, it is important that the performance characteristics of the components
be specified. That is, if searches are expected to be no worse than O(N), we
need to say that. That's because we want programs using the components to be
portable. That wouldn't be true for programs using components with large
numbers of items if the performance characteristics vary widely between
implementations. Consider a Vector component. It could in theory be implemented
with an array or with a linked list. The cost of an arbitrary insertion is O(N)
for the array implementation and O(1) for the list implementation. If a program
using a large vector is moved from a list implementation to an array
implementation, the performance change could be so large as to make the program
non-functional. That is unacceptable, so we specify minimum performance
characteristics. But those characteristics are not intended to specify a
particular implementation, only to insure that some characteristics can be
relied upon.

Therefore, the containers library needs to suggest some performance
characteristics. We believe Implementation Advice is best for this purpose,
as we don't have to be as precise in the language defining the characteristics,
and implementations are required to document deviations from the given
advice.

Appendix

Detailed changes made to the Alternative 2 proposal

The Unchecked_Modification packages were dropped. These are just a hack to
avoid copying keys - a solely performance-based concern. Other stuff does
not logically belong in keys, and modifying the key value itself it a disaster
waiting to happen.

The Vector, List, and Multiset abstractions are essentially the same
abstraction with differences in performance and details. When performance
is not critical, only one is needed.

The package structure has many levels of empty packages for organization.
These are unnecessary when there are only a few packages. Moreover, related
packages can be given similar names (i.e. "Bounded_Set", "Protected_Vector"),
which provides all of the organization needed. The extra empty packages
were eliminated. Similarly, "Unbounded" was dropped; these are the most
general forms, and should be the ones used for general-purpose programming.
Other forms (in a secondary standard) would be more specialized.

We discussed dropping the special string maps. We eventually decided to keep
them, because string maps are common, and a Map cannot be instantiated with
"String" (the key type must be definite).

We also discussed whether Sets should be sorted. We concluded that the extra
cost of sorted insertions is fairly small, and thus there is little advantage
to using unsorted sets other than when performance is critical (which again
is not the purpose of the standard). We did, however, name the package
"Sorted_Sets" so that a basic unsorted set could be provided in a secondary
standard without contorted naming.

We added a modular Hash_Type to Ada.Containers. The choice of Integer'Base is
a horrible one on compilers that use 16-bit Integer (as allowed by the
standard), and in any case, the hashing type should be modular.

The string hash and comparison functions were moved to be part of the
Ada.Strings heirarchy. It would be a bad idea to have the hash functions
of all types gathered in one place (in the containers library).

Unbounded string hash and comparison functions were added.

We changed the type names to the more descriptive "Vector_Type", "Map_Type",
and "Set_Type". These are much better for users who use Use clauses. The
argument that having a common name makes it easier to change between containers
is mostly irrelevant: changing between the provided containers is going to be
rare. Moreover, qualifying "Container_Type" (that is, "Vector.Container_Type")
would be necessary in any unit with more than one container -- eliminating any
advantage for using the same name.

The proposal confused the meaning of "iterator", using it both for the
code that visits each element of a container (the conventional meaning) and
the "handle" or "cursor" used to access an element of a container. We decided
to use "cursor" for the second meaning to make the interfaces clearer.

We added a sort routine to Vector. For some reason, this was only present
in the (removed) List abstraction. Having a simple sort available can
simplify many programming problems.

We added legality rules that these packages must be instantiated at the
library level. The requirement that these packages do not
leak memory (like Ada.Strings.Unbounded) imply that they are implemented with
controlled types (or something like controlled types). We do not want to
implicitly require implementers to support nested controlled types without
making that support available to users. (If AI-344 or AC-50 were adopted, we
could drop these rules.)

The proposal was completely missing definitions for the string hash and
compare functions.

Performance requirements were moved from the !proposal into Implementation
Advice. As much as possible, mention of specific implementation strategies
was moved into AARM notes following that Advice. (We're not going to specify
red-black trees!).

An Assert pragma was added to the Vector package to prevent instantiation with
a type for which Index_Type'Base'First = Index_Type'First. For such a type,
the initial value of Last and the value of Front must necessarily raise
Constraint_Error. It's better to fail an assertion immediately, rather than
during some later operation.

The Map container in the proposal is far too specific to a particular
implementation. It exposes that implementation in the interface, and as a
result makes iteration operations harder. That seems like a bad choice for
a simple abstraction; it's fine to suggest an implementation, but bad to
make it part of the interface. We therefore simplied the interface and the
description. (We consulted with the author of the proposal on this and other
changes.)
****************************************************************