Beyond C++ Templates

STL and other code-instantiation strategies

Fred is principal of Advantage Software Technologies and can be contacted at [email protected].

STL provides more than a set of templates

To a software developer, instantiation means "to create an instance of something." Considering C++'s object-oriented facilities, you should be familiar with the idea that there are classes, and an object is an instance of a class. When adding a declaration such as Str inputLine; to a program, you are asking the C++ compiler to create an instance of the class Str that you can refer to as inputLine. The compiler creates machine code and run-time calls that perform the act of instantiation. In this case, the act of instantiation is defined by the C++ language, and prescribes a process of allocating space for the class, invoking its constructor, and so on.

Instantiation is an important concept for achieving reuse. It is also a general idea that has meaning and application well outside the realm of creating C++ class instances (which is among the simpler notions of instantiation). For example, C++ now includes templates, which add a degree of instantiation power and flexibility. The value of this flexibility has surfaced in the Standard Template Library (STL).

C++ templates are a start, but there are other exciting activities surrounding instantiation, some of which you may not be acquainted with.

Levels of Code Instantiation

There are a number of levels of code instantiation and associated instantiation devices. Each level gets more involved and handles a larger granularity of what is created as a result of the code instantiation process. For completeness, I'll first examine a few familiar mechanisms in C/C++ and ask you to think of them in ways just slightly different than you may have in the past.

Leaving aside the instantiation of classes and predefined types in declaring variables, let's look instead at the levels of code instantiation. In code instantiation, you create code through automatic means, then feed the resulting code into a compiler as if you had typed it in yourself. The preprocessor step in translating a C/C++ program does this, so I'll start there.

Macros

Macros have always been a topic of dispute among developers. Used too much (or for the wrong reasons), they seem to mar code readability. Nevertheless, their role as an instantiation device has been one of their most accepted uses. The familiar max macro creates an instance of an expression that compares the two values passed in, and yields the greater of the two. Here, the preprocessor is the instantiation engine. The max macro in Example 1(a) is expanded without regard for the types of its arguments; see Example 1(b). After the preprocessor does its work, the compiler is left with an expression to translate, as in Example 1(c). The resulting code will fail to compile if the types of the two items being compared are not defined over the greater-than operator. The macro simply defines a lexical code-creation rule and leaves the rest of the details of handling what is produced to the compiler.

Macros have a practical but limited value as an instantiation device. It's a useful practice to instantiate executable statements with macros. It's also okay to instantiate typedefs. In fact, it's generally safe to use macros to instantiate any sections of code that don't create link-time definitions or symbols. If you try to use macros to manufacture complete classes, however, you can easily get into trouble. Consider a case in which you try to use macros to manufacture a class; see Example 2. You can put the macro in a header file, and use it in your system, but you need to worry about how many times you expand the macro and where you expand it.

If you aren't careful with the macro mechanism, you can create tangles of multiple declarations and who knows what else. What you are trying to do in this example is define a code pattern that we can instantiate for various named types. C++ provides direct support for this goal with templates.

Templates

The previous example is easier to accomplish with templates. C++ helps in a number of ways, particularly in that it manages the instantiation process. As before, you need to declare the code pattern for the list class. This time, however, when you want to apply the code pattern to a specific type, you simply cite the name of the class template with the type supplied as a parameter. You can refer to instantiations of your template without the concerns of managing the process of instantiation; see Example 3(a). Unlike the situation with macros, you don't need to know where the compiler creates the instantiated versions of your code. You don't even need to come up with unique identifiers to refer to the instantiations-the name and parameter list provided to the compiler are identification enough; see Example 3(b).

Once instantiated, class templates create bona fide class declarations that can be used anywhere you would normally use a class declaration. This includes using a class declaration from one template instantiation in another. You may run across List< List<String> > listOfStringLists;, which is perfectly legal.

If you don't like how type indicators look when they refer to instances of templates, you can use a macro to give them a more pleasing name. Alternatively, you might use a typedef to accomplish the same thing; unlike a macro, it will cause the template to be expanded, even if it is not used anywhere in your code, and that can have a big performance impact at compile time. From a compilation-overhead point of view, macros are the better choice. In Example 4, macros are used to refer to templates with more pleasing names.

STL

The Standard Template Library provides more than a set of templates. The power of STL is that its templates are meant to interoperate, and are connected by a set of standard interfaces and behaviors. This allows great flexibility when creating new containers or algorithms.

STL contains several categories of templates: containers, iterators (that navigate through containers in standard ways), and algorithms (that rely on iterators to provide a standard set of capabilities).

The principle of consistency of interfaces provides a great amount of flexibility in STL. For example, you don't need to go to the declaration of a specific random-access collection to see what iterator it provides. That is predetermined and is consistent across all container types that can be accessed randomly. You can freely create algorithmic-code patterns that can be instantiated to operate on any random-access collection.

There are natural safeguards at work in instantiating templates. These safeguards are similar to those in Example 1, in which an appropriate greater-than operator was needed during compilation. If you instantiate an STL algorithm that requires a random-access iterator with a collection that does not supply a random-access iterator, it won't compile. Moreover, since all suitable collections do provide a random-access iterator as part of their interface, they can be used in the instantiation of an algorithm that is meant to work with a random-access collection, and the generated references within the algorithm will find what they are looking for without exception.

The standard iterators and algorithms of STL are an excellent step forward in code-pattern-based software creation, but the "parameterized class" approach supported by templates has its limitations. What lies beyond templates? Higher-leverage instantiation, of course.

Instantiating Larger Code Patterns

Templates provide features that make parameterized classes possible. This lets you create many interesting strategies in which a fixed number of parameters are used to create a fixed number of lines of code, substituting the parameters into prescribed places. When this is all you need, the recommendation is simple-use templates.

Looking at instantiation in a more general way, note that the instantiation process requires two fundamental inputs. First, there are the rules that are used to create the resulting code (for example, a C++ template). Second, there is information that is applied to the code creation rules to create a particular instance of what the rules were meant to produce (a type parameter applied to a C++ template, for instance). This higher-level view of instantiation allows us to imagine other possibilities.

There are code patterns that are not expressible simply by substituting fixed lists of parameters into prescribed places. Some code patterns require more complex parameters and prescribe code-creation decision making based on the characteristics of those parameters. Example 5 presents an example code pattern that requires this level of flexibility. Example 5(a) shows several object descriptions, each having a few attributes. I'll use these objects as a group of parameters to an executable template. PetOwner is an object having a Name and a list of pets named Pets. Pet has a PetKind attribute and a pointer back to PetOwner.

You need an executable template for creating the constructors from this input. You need to be able to iterate over the objects and test their attributes for specific characteristics that match the code you would create for initializing member variables of each different type.

When inspecting the sample executable template in Example 5(b), note that each line beginning with a dot (.) is a template-control directive. Each line beginning with a colon (:) emits a line of code. The pound sign (#) leads off a comment. This set of instructions creates a constructor for each object, and adds lines to each constructor body to clear its list_of attributes and set the ptr_to attributes to NULL. Other attribute types in the input (the unadorned String attributes) are ignored as sufficiently self-initializing.

Example 5 illustrates the need for iteration and selection when expressing certain code patterns. As before, if the template creates something wrong, the compiler will tell you about it. However, if the template is also responsible for instantiating the class declarations and their member-variable declarations, simply following a few naming and typing conventions can enable flawless code generation for groups of collaborating classes.

Instantiating Entire Applications or Architectures

The scale of instantiation can grow larger still. You can expand your view from instantiating groups of fine-grained objects to include larger architectural patterns. Imagine layering specifications that would allow reusable patterns of interaction across entire subsystems.

For example, compiler construction is one area in which this strategy has been employed for some time. There are a number of general architectures, structures, and strategies that can be applied to most compilers for procedural languages. Languages consist of a number of lexemes that are used to make up a grammar. Constructs in the grammar are associated with structural and behavioral semantics, according to the language's definition. A set of abstract machine instructions can be created from the parsed language input, run through various optimization strategies, and finally mapped onto the facilities of a physical machine architecture.

Retargetable compilation systems follow a replaceable subsystem strategy. While the situation is really a bit more complex than this, the general idea is to combine compiler front ends for various languages with back ends that produce machine code. The output of the front ends and the inputs to the back ends are the main connection points of this subsystem-integration strategy. To support a new language, a new front end is created. To add a new machine to the list of those supported, a new back end is added.

Compilers form a domain of software products that are well understood. When any application area is well understood, there is an opportunity for creating higher-leverage construction strategies. The key is to specify how all members of the family of applications are the same and how they are different. The ways in which they are the same can be used to form a set of rules by which the applications are created. The ways in which they differ can be used as parameters to the creation rules, to allow for those differences to be weaved into the general framework in prescribed ways.

Large organizations such as ARPA, the Software Engineering Institute (SEI), and Software Productivity Consortium (SPC) have been pursuing development strategies for well-understood application domains. While you may not have access to their tools (membership is required in some cases), the organizations are usually happy to discuss what they are doing.

ARPA.

ARPA provides a system for domain-specific software architectures (DSSA), named DADSE 2.3. An Architecture tool provides a graphical interface for browsing and creating application descriptions, both of the application's architecture and its design. The tool offers domain-specific description languages based on a reference architecture for the domain. The Core is the central integration and invocation point for the Architecture tool and any other tightly integrated DADSE tools. It guides the user of the Architecture tool and informs them about semantic implications of their actions. A Repository stores descriptions of reusable components and prior architectures. As a project progresses, it accumulates all new components and configurations within the Repository.

SEI.

Product-line engineering that the SEI delivers focuses on engineering and reengineering of software-intensive systems from a product-line perspective, utilizing domain models and architectures to gain leverage from identified commonality and variability in systems. It addresses the proliferation and high cost of separately developed and maintained systems.

SPC.

Megaprogramming is a set of concepts that provides a product-line approach to software development, based on the Consortium's Synthesis approach to software development. The term "megaprogramming" was coined to describe a radically different method for developing software. Programming is done with individual lines of code. Megaprogramming is done with large pieces, or components, of code that have been designed and implemented for reuse in a variety of systems. Reuse can eliminate work; increase quality (in that you reuse proven software); and significantly reduce development time.

References

Horton, M. Portable C Software. Englewood Cliffs, NJ: Prentice Hall, 1990.

Musser, D. and A. Saini. STL Tutorial and Reference Guide: C++ Programming With the Standard Template Library. Reading, MA: Addison-Wesley, 1996.

Terribile, M. Practical C++. New York, NY: McGraw-Hill, 1993.

Example 1: (a) The max macro; (b) max expanded without regard for the types of its arguments; (c) the expression left to translate.

(a)
#define max(a,b)     (((a) > (b)) ? (a) : (b))
<a name="0003_0004"><a name="0003_0003">(b)
int larger ;
larger = max(item1, item2) ;  /* before preprocessing */
(c)
int larger ;
larger = (((item1) > (item2)) ? (item1) : (item2)); 
/* after preprocessing */

Example 2: Using macros to manufacture a class.

(a) 
#define MAKELISTCLASS(listname,itemtype)     \
class listname {     \
public:      \
     \
    void AddItem (itemtype theItem);     \
    void RemoveItem (itemtype theItem);     \
} ;      \
          \
inline listname##::AddItem (itemtype theItem) ...     \
     \
inline listname##::RemoveItem (itemtype theItem) ...     \

(b)

MAKELISTCLASS (NameList, String)
NameList    students ; 
students.AddItem("Jane");

Example 3: (a) Referring to instantiations managing the process of instantiation; (b) referring to instantiations by name and parameter list.

(a)     template<class T>
class List {
public:
    ...
    void AddItem (T theItem);
    void RemoveItem (T theItem);

} ;

template<class T>
List<T>::AddItem (T theItem) ...

template<class T>
List<T>::RemoveItem (T theItem) ...
<a name="0003_0007">(b)     List<String>    students ;
 ...
students.AddItem ("Jane");

Example 4: The #define created in (a) can be used to refer to a list of strings with a more pleasing name, as shown in (b).

(a)     #define  StrList   List<String>
(b)     StrList     students ;
 ...
students.AddItem("Jane") ;  

Example 5: (a) Several object descriptions, each having a few attributes; (b) sample executable template.

(a)
object PetOwner
    Name        :            String ;
    Pets        :   list_of  Pet ;
end ;
object Pet
    PetKind   :          String ;
    MyOwner   :   ptr_to   PetOwner ;
end ;
<a name="0003_000d">(b)
# create a constructor for each object
.each_obj
# output the constructor function signature
# and opening brace
:<obj.name>::<obj.name>() 
:{
# if the object has any 'list_of' attributes,
# output code to clear the list
.each_attr <attr.list_of>
:   <attr.name>.Clear();
.end
# if the object has any 'ptr_to' attributes,
# set them to NULL
.each_attr <attr.ptr_to>
:   <attr.name> = NULL ;
.end
# add a closing brace, and a trailing blank line
:}
:
.end  # .each_obj