The Ada 95 Booch Components

Documentation

--

Key Abstractions
The Patterns of the BCs
Tactical Issues
Macro Organization
Class Families
Micro Organization
Time and Space Semantics
Storage Management
Exceptions
Iteration
Support packages
Conclusion

--

Key Abstractions

The Ada 95 version of the components will contain the same key abstractions as the C++ form (Structs, Tools and Support). However, the organization will be slightly different, particularly in the Support domain. This is because Ada 95 provides several special forms of memory management that are quite different from C++.

The Structs category provides an array of structural abstractions (Bags, Collections, Deques, Graphs, Lists, Maps, Queues, Rings, Sets, Stacks, and Trees). The Tools category provides algorithmic abstractions (Searching, Sorting, etc.). The Support category contains all the "concrete" forms, plus structures to create the components.

Some of the structures permit structural sharing (graphs, lists, and trees). Some structures may also be ordered (collections, dequeues, and queues). There are also multiple forms for some structures: single and double linked lists, directed and undirected graphs, and binary, multiway, and AVL trees.

The Patterns of the BCs

The BCs cover several issues:

These patterns have evolved in a way that each language feature is used in an efficient and appropriate manner, with the overall goal of balancing usability and extensibility.

Tactical Issues

The particular semantics of a given programming language influence our architectural decisions. To ignore these influences leaves us with abstractions that do not take advantage of the language's unique features, or with mechanisms that cannot be efficiently implemented. -- G. Booch

Ada 95 inherently provides several features not present in C++: safe generics, safe object-oriented programming (no silent "object slicing"), general access types and access discriminants, and concurrency support. All this as well as user-definable storage management, automatic reclamation of resources (garbage collection "lite"), aggregation, inheritance, and parameterization available in C++ and other languages.

The BCs take advantage of several critical forms of structuring: inheritance, parameterization, modularity, concurrency, and aggregation. Of these forms, parameterization is the form most often used.

Macro Organization

The BCs emphasize separation of policy from implementation. For this reason, abstract classes are declared for every major component type. Also, the Support category provides the common low-level features used in constructing the different components, in order to help the "power user" create new components or extend existing ones.

An example:
A Mail_Queue is an instance of a Priority_Event_Queue, which itself is a generic instantiated with Network_Event as the item it contains. The Priority_Event_Queue is derived from Queue.

Class Families

Each abstract base class has several derived concrete forms, each designed to support specific needs for time and space semantics. The user selects the concrete form most appropriate to their needs. The net result is that copy, assignment, and equality operations work between each different form of the components.

There are two very common variations of structure management: bounded and unbounded. A third form was added to the latest BCs: dynamic. This form represents a heap structure which behaves (basically) as a dynamic array. Its performance lies between that of a bounded and unbounded structure. The array can grow or shrink in multiples of a chunk_size. [Note, this becomes less valuable given Ada's support for user-defined storage pools.]

The selection rules are:

Bounded
Use where size is statically known or allocation from the heap is prohibited.
Dynamic
Average storage size of each instance must be considered when setting chunk_size. Indexing is as efficient as bounded, but insertion other than at the front or back of a structure is less efficient than the unbounded form. Storage is allocated by a storage manager.
Unbounded
Space efficient, but requires memory allocation for each new item added, under the control of a storage manager. The most recently accessed item is cached.
Unmanaged
Space efficient, but requires memory allocation for each new item added, from the system's memory pool. The most recently accessed item is cached.

Micro Organization

Each Abstract Base Class generally follows the same form of derivation: Picture of organisation of classes

(Each level is a derivation via inheritance. Each class is a generic using Item as the container parameter)

Time and Space Semantics

The fundamental difference between the Unbounded and Bounded forms is that the unbounded form is essentially an time efficient linked-list, but is not very space efficient. The bounded form uses a packed array base class, which is space efficient, but can become time inefficient if adding items into the middle of the array.

Bounded forms have two parameters for their generics: Item and Maximum_Size. Dynamic and Unbounded forms have Item and the actual Storage Pool for parameters.

Storage Management

Storage management on certain architectures can be complex, and so requires that all of our classes use a policy tailored to the platform, rather than using a general one assumed by the library designer to work in all circumstances. By clearly isolating these patterns of storage management, we can provide a robust, adaptable library.

By treating the storage manager as an argument to all the dynamic and unbounded concrete structures, we effectively decouple storage management policy from its implementation, and make it possible for library users to insert their own storage management policy without changing the library. This is a classic example of extensibility through instantiation instead of inheritance.

The only requirement we place upon storage managers is that they provide the same well-defined protocol. This is defined by the standard package Ada.Storage_Pools.

Two predefined managers are available:

BC.Support.Standard_Storage.Pool
is effectively the default heap manager.
BC.Support.Managed_Storage.Pool (Chunk_Size)
provides management of store within a pool whose unit (chunk) size is specified when the pool is created.

Note that the supplied BC.Support.Managed_Storage will not support allocation of items larger than its chunk size.

For those who don't need this level of control, we provide Unmanaged forms.

Exceptions

All exceptions for the BCs are placed in the topmost package, BC. This precludes the user from having to include a separate "Exceptions" package. Exception behaviour of the BCs is standard and portable, unlike other languages.

As well as the exceptions from the C++ Components, an exception Should_Have_Been_Overridden is possible. It will only be raised if the implementor has forgotten to override a private subprogram of an abstract class (such subprograms can't be abstract, see RM95 3.9.3(10)).

Iteration

Separate types act as agents responsible for iterating across a structure. This was done for two reasons:

There are two forms: active and passive. Active iteration requires the client explicitly advance the iterator. For passive, the client supplies a single procedure Apply to work across the structure.

In both forms, mechanisms are provided (where appropriate) to allow access to the actual contained object rather than just to its value.

There are many different approaches to iteration in Ada 95. The current mechanism was selected for its direct simplicity and efficiency.

Support

The support packages (BC.Support and children) come in two flavours:

The general utilities are:

Managed_Storage
A storage pool by Pat Rogers, which can allocate objects up to a user-defined size (supplied as a constraint).
Unmanaged_Storage
A storage pool by Pat Rogers, implemented using the default storage pool (works for GNAT, ObjectAda, Apex, may work on others).
Memory_Streams
Support streaming to memory.
Smart_Pointers
Provide reference-counting pointers.
Standard_Storage
Interface to the standard storage pool (works for GNAT, ObjectAda, may work on others).
Synchronization
The Components don't provide forms that are directly suitable for use in concurrent programs. This is mainly because it's not possible to support all the ways that people might want to use them.
You'll probably want to use the Components to implement your own abstractions, so it's best to provide your own wrappers using protected types and tasks as needed.
This package provides Semaphores and Monitors which may be helpful.

Conclusion

Here's a table of the components and the forms that are supported (U=Unbounded, B=Bounded, D=Dynamic, N=Unmanaged).

Bags         : UBDN
Collections  : UBDN
  (ordered)  : UBDN
Dequeues     : UBDN
Graphs
  Directed   : U
  Undirected : U
Lists
  Single     : U
  Double     : U
Maps         : UBDN
Queues       : UBDN
  (ordered)  : UBDN
Rings        : UBDN
Sets         : UBDN
Stacks       : UBDN
Trees
  AVL        : U
  Binary     : U
  Multiway   : U

--

[index]