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
Synchronization
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.
Unbounded
Space efficient, but requires memory allocation for each new item added (unless the storage management policy is "Managed", see later discussions). The most recently accessed item is cached.

There is also variations for the presence of multiple threads of control. A component can take on a form of Sequential, Guarded, or Synchronous. These forms will be discussed later.

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)

The Guarded forms are created by instantiating BC.Guarded with the concrete form, whereas the Synchronized forms have to be provided individually.

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.

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.

Synchronization

Those components that provide structural sharing ("polylithic") exist only in unprotected forms. Concurrent access by multiple tasks requires the user to provide her own access control.

Other components provide access control, when required, in one of two forms:

Guarded forms

Clients of guarded objects must follow the simple protocol of first Seizing the object, operating on it, and then Releasing it (even if exceptions occur).

Seizing a guarded object and failing to release it blocks the object's use indefinitely; releasing an object never seized is improper; and ignoring the protocol altogether is likely to result in interleaved tasks corrupting the state of the object.

Guarded forms are created by instantiating the package BC.Containers.Guarded with

A standard Semaphore is supplied, using which will cause each object to have its own guard; an alternative possibility would be to create a new Semaphore type such that each object of that type accesses a common actual Semaphore. Using such a strategy, a global lock could be obtained on a whole group of objects in one operation.

Note particularly that the standard Guard will not work as you expect for "polylithic" structures (Graphs, Lists, Binary and Multiway Trees).

Synchronized forms

For synchronized objects, each operation on the object becomes an atomic transaction; clients don't have to worry about maintaining the proper protocol.

This is very much easier for the developer; however, if it's necessary to invoke several operations on one object as a single atomic transaction, the Guarded protocol should be used.

Conclusion

Here's a table of the components and the forms to be supported (U=Unbounded, B=Bounded, D=Dynamic, G=Guarded, S=Synchronized). The available components are shown in red. Those for which it's appropriate to use the standard Guard are marked G.

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

--

[index]