An Overview of the Booch Components for Ada95
Key Abstractions
The Patterns of the BCs
Tactical Issues
Macro Organization
Class Families
Micro Organization
Time and Space Semantics
Storage Management
Exceptions
Iteration
Conclusion
The Ada 95 verison of the components will contain the same key abstractions as the C++ form (Tools, Support, and Structs). 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 Booch Components (BCs) are organized in three major areas: Tools, Support, and Structs. The Tools category provides algorithmic abstractions (Searching, Sorting, etc.). The Structs category provides an array of structural abstractions (Bags, Collections, Deques, Graphs, Lists, Maps, Queues, Rings, Sets, Stacks, Sequences, and Trees). 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 llinked lists, directed and undirected graphs, and binary, multiway, and AVL trees.
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.
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++: user-defined storage pools, automatic reclamation of resources (garbage collection "lite"), general access types and access discriminants, and concurrency support. All this as well as the C++ features of aggregation, inheritance, and parameterization.
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.
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 same 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.
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.
The selection rules are:
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.
Each Abstract Base Class generally follows the same form of derivation:
Abstract Base Class
|
+----------------+------------------+
Bounded Form Dynamic Form Unboun. Form
/ \ / \ / \
Guarded Synchronized Guarded Synch Guarded Synch
(Each level is a derivation via inheritance. Each class is a generic using Item as the container parameter)
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 Size. Dynamic and Unbounded forms have Item and Storage_Manager for parameters.
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 our storage manager is that they provide the same well-defined protocol. This is accomplished through a specific derivation of Ada.Storage_Pools, from which a user may extend themselves.
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.
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 function "Apply" to work across the structure.
There are many different approaches to iteration in Ada 95. The current mechanism was selected for its direct simplicity and efficiency.
Here's a table of the components and the forms supported.
(U=Unbounded, B=Bounded, D=dynamic, G=Guarded, S=Synchronized)
Bags : UBDGS Collects : UBDGS Dequeues : UBDGS Graph Directed : U Undir : U List Single : U Double : U Maps : UBDGS Queues : UBDGS Rings : UBDGS Sets : UBDGS Stacks : UBDGS Sequences : UBDGS Trees AVL : U Binary : U Multiway : U