CD Actual 14

home *** CD-ROM | disk | FTP | other *** search

/ CD Actual 14 / CDACTUAL.iso / cdactual / demobin / share / program / c / ZCPP_JAE.ZIP / PAPER.TXT < prev next >

Wrap

Text File | 1991-04-29 | 33.9 KB | 826 lines

**** EARLY DRAFT **** A Portable Implementation of Parameterized Templates Using A Sophisticated C++ Macro Facility **** EARLY DRAFT **** Mary Fontana LaMott Oren Texas Instruments Incorporated Computer Science Center Dallas, TX Martin Neath Texas Instruments Incorporated Information Technology Group Austin, TX ABSTRACT The Texas Instruments C++ Object-Oriented Library (COOL) is a collection of classes, templates and macros for use by C++ programmers writing complex applica- tions. Parameterized types, symbolic computing and exception handling are significant features of COOL which improve the development capabilities available to the programmer. These features are implemented in COOL with a sophisticated C++ macro facility. This paper describes the COOL macro facility, discusses how sup- port for parameterized templates is built upon it, and provides details of two programmer interfaces (both implemented) for easy use of parameterized templates in application programs. 1. Introduction The Texas Instruments C++ Object-Oriented Library (COOL) is a collection of classes, templates and macros for use by C++ pro- grammers writing complex applications. It is designed to raise the level of abstraction for the programmer in order to facili- tate concentration on the problem domain, not on implementing base data structures, macros, and classes. In addition, COOL -1- provides a system-independent software platform on top of which applications are built. Parameterized templates, symbolic comput- ing, and exception handling are significant features of COOL which substantially improve the development capabilities avail- able to the C++ programmer. We wished to provide these facili- ties in a compiler- and machine-independent manner across several hardware platforms. We examined the macro definition and expan- sion mechanism found in standard C-preprocessors and determined that it is not sufficient for implementing these features. As a result, we developed the COOL macro facility to allow the pro- grammer to define powerful extensions to the C++ language in a seamless and unobtrusive manner. This macro facility is imple- mented as an extension to a standard C preprocessor [1]. The modifications made to the preprocessor are both portable and com- piler independent. This paper describes this enhanced macro facility, discusses how parameterized templates is built upon it, and provides details of two programmer interfaces (both imple- mented) for easy use of parameterized templates. For an overview of COOL see the paper, COOL - A C++ Object-Oriented Library [2]. For complete details, see the reference document, COOL User's Manual [3]. 2. The COOL Preprocessor and the defmacro Keyword Many C++ language implementations separate the preprocessor and compiler functions into two separate programs. Others, (such as the Glockenspiel C++ language system), combine the preprocessor and compiler into one step. Since we needed a portable utility to massage C++ source code that works under both scenarios and exe- cutes after include files and standard preprocessor directives have been expanded, but before the C++ compiler itself begins parsing, we decided to modify a C-preprocessor to support the COOL C++ language extensions. Thus, the COOL preprocessor is derived from and based upon a public domain C-preprocessor (the DECUS C preprocessor) made available by the DEC User's group and supplied on the X11R3 source tape from MIT. It has been modified to comply with the draft ANSI C specification with the exception that trigraph sequences are not supported. The draft-proposed ANSI C standard indicates that extensions and changes to the language or features implemented in a preprocessor or compiler should be made by using the #pragma keyword. The COOL preprocessor recognizes a #pragma defmacro declaration and is the single hook through which features such as the class macro, parameterized templates, and polymorphic enhancements have been implemented. The defmacro keyword provides a way to define and execute arbitrary filter programs or macro expanders on C++ code fragments. The syntax of the defmacro declaration is: #pragma defmacro name "program" options #pragma defmacro name <program> options where name is the name of the macro, program is either the name of an executable file or the name of an internal preprocessor function which implements the macro expansion, and options are any combination of the following optional parameters: -2- recursive - the macro may be recursively expanded. expanding - the input to the macro is expanded. delimiter= x - the default delimiter (semi-colon) is replaced with x. Unknown options are passed as arguments to the macro expander named program. This provides the necessary handle through which COOL functions and language extensions can be identified. For example, the MACRO and template keywords are defined in a top- level header file with: #pragma defmacro MACRO "macro" delimiter=} recursive #pragma defmacro template "template" delimiter=} The implementation of the macro expander program may be either external or internal to the preprocessor. Fundamental COOL macro-expanders are implemented internal to the COOL preprocessor for the sole reason of providing a more efficient execution pro- file to reduce compile time for the application programmer. When the preprocessor encounters a defmacro declaration in the source code, it searches first for an executable file named program on the same search path as that used for include files. If a match is not found, it then searches for program in an internal prepro- cessor function table. If a match is still not found, an error is reported indicating that the macro expander could not be found. This search order allows an internal preprocessor defini- tion to be overridden by an external one. When a defmacro name is successfully recognized, the name and all following characters upto and including the delimiter character (including all matching and nested levels of {} [] () <> "" '' and comments found along the way) are piped into the standard input of the macro expander program. The expander program per- forms whatever function(s) is appropriate and the resulting mas- saged character stream is piped back onto the standard output of the macro expander. This output stream is scanned as new input by the preprocessor for any further processing that might be necessary. The original text in the source file is replaced with the preprocessor output before being sent onto the C++ compiler. The expansion replacing a defmacro name in the source code is C++ 2.0 syntax acceptable to any conforming C++ translator or com- piler [4]. 3. The MACRO Keyword The COOL MACRO keyword provides a powerful and flexible macro capability used to implement and simplify many of the features and functions contained in the library. A defmacro named MACRO (all uppercase) provides an enhanced #define macro that supports multi-line, arbitrary length, nested macros and cpp-directives with positional, optional, optional keyword, required keyword, rest, and body arguments. MACRO has the following syntax: MACRO name ( parmlist ) { body } parmlist := [KEY: | REST: | BODY:] identifier [= identifier] [, parmlist] -3- where name is the name of the macro, parmlist is a list of param- eters separated by commas, and body is the code which replaces the MACRO reference. The parmlist specification allows posi- tional, keyword, rest, and body parameters to be identified by the programmer. The positional and keyword parameters may be required or optional. Optional parameters are supported by use of an equal sign followed by an identifier that specifies the default value. All the optional positional parameters must fol- low all of the required positional ones. When KEY: is specified in the parmlist, all parameters which fol- low are keyword parameters. Keyword parameters are position- independent parameters. A keyword parameter is provided a value in an argument list by supplying the keyword name followed by an equal sign and the argument value. REST: in the parmlist indi- cates that the remaining parameters are referenced by one named identifier. An optional equal sign followed by an identifier sets the identifier after the equal sign to the number of argu- ments remaining. Finally, BODY: in the parmlist indicates that the parameter which follows is expanded to include all the source code within the braces after the MACRO call. This is useful for passing a source code fragment onto other nested MACROs. Examples of these three types of arguments are given below. 3.1. MACRO Examples The following examples show some of the power and flexibility of MACRO. This first example uses both positional parameters and keyword parameters. MACRO set_val (size, value=NULL, KEY: low=0, high) { init (size, value, low, (high-low)) } set_val has three parameters: size is a required positional parameter, value is an optional positional parameter that if not specified in a particular call has a default value of NULL, low is an optional keyword parameter with a default value of 0, and high is a required keyword parameter. In this example, the expansion calls the function init with four arguments. The fol- lowing shows several expansions of set_val. set_val (0, high=20) ----> init (0, NULL, 0, (20-0)); set_val (0, low=5, high=15) ----> init (0, NULL, 5, (15-5)); set_val (1, 2, high=25) ----> init (1, 2, 0, (25-0)); The next example uses the REST: parameter. Note that there are two MACROs defined: build_table calls build_table_internal to do most of the work. -4- MACRO build_table (name, REST: rest) { char* name[] = { build_table_internal(rest) NULL} } MACRO build_table_internal (first, REST: rest=count) { #first, #if count build_table_internal (rest) #endif } build_table has two parameters: name is the name of the table of char*'s and rest refers to all the remaining arguments. build_table calls build_table_internal passing its rest argument. Note that this call is embedded within the initialization braces of the table and is followed by a NULL. In build_table_internal, first is set to the first argument of the rest argument list in the invoking macro call, and the remaining count arguments are left in rest. build_table_internal uses the ANSI # character on first to double quote the value. A conditional clause tests count to see if there are remaining arguments. If count is non-zero, the macro is called recursively with the remaining arguments. When there are no more arguments, build_table regains control and appends the NULL character and closing brace to the result of build_table_internal. A sample use of build_table is shown below to illustrate the con- struction of a NULL-terminated table containing character strings. The first line shows the macro call and the second shows the resulting expansion. build_table (table, 1,2,3,4,5,6,7); expands to: char* table[] = {"1", "2", "3", "4", "5", "6", "7", NULL}; This last example uses the BODY: parameter and also takes advan- tage of the current position feature found in the COOL container classes [2]. This is used to implement a general purpose loop macro similar to that found in Common LISP [5]. MACRO LOOP (type, identifier, object, BODY: body) { { type identifier; for ( object.reset(); object.next(); ) { identifier = object.value(); body } } } LOOP has four parameters: type is the type of each element in a container class (such as, int), identifier is the name of a variable to be declared of the given type, object is the name of a container class instance, and body is the body of code to apply on each element in the container object. A specific example for -5- the parameterized List<int> class is shown below. extern List<int> list1; LOOP (int, var1, list1) { cout << var1; } expands to: extern List<int> list1; { int var1; for ( list1.reset(); list1.next(); ) { var1 = list1.value(); cout << var1; } } In this example, list1 is an instance of List<int> which is a container class representing a list of integers. LOOP takes this list object and iterates through the elements, assigning each to a temporary integer variable var1 and printing its value. The net result will print all elements in the list. 4. COOL Parameterized Templates One of the main uses of the COOL macro facility is the implemen- tation of template, DECLARE and IMPLEMENT for supporting parameterized templates. The syntax of the template grammar is that as specified by Stroustrup in his paper, Parameterized Types for C++ [6]. COOL fully implements this functionality such that there will be minimal source code conversion necessary when this feature is finally implemented in the C++ language. COOL pro- vides templates for a number of parameterized classes (such as, Range and Iterator) and container classes (such as, Vector, List, Binary_Tree and Hash_Table) which are described in COOL User's Guide [3]. 4.1. The template Keyword The template keyword provides a mechanism for defining parameter- ized classes. A parameterized class is a type-independent class. A typical use is a container class where the type of the con- tained object is specified at compile-time. For example, vectors can be declared to hold a specific type of element, such as, a vector of integers or a vector of doubles, from a single parameterized class, Vector<type>. A template is divided into the declarative part and the implemen- tation part of a class. The declarative part may occur many times in an application and is analogous to including a header file for a class which contains the class definition and its inline member functions. The implementation part is analogous to the file that contains the source code implementing the member and friend functions of the class. COOL provides four variations of template for these two parts. template <class type [, parms]> class name<type> { class_description }; Defines the class template for the declarative part of the name class. -6- template <class type [, parms]> inline result name<type>::function { ... }; Defines an inline member function for the declara- tive part of the name class. template <class type [, parms]> result name<type>::function { ... }; Defines a member function for the implementation part of the name class. template <class type [, parms]> name { anything }; Defines anything else associated with a template for the name class. This form is used to define such things as typedefs or friend functions of a parameterized class. When this form is found before the class template, the contents are expanded before the class definition. When this form is found after the class tem- plate, the contents are expanded as part of the class implementa- tion. Note that this form is not part of the parameterized type syntax described by Stroustrup [6]. Rather, it is something we found lacking in the original proposal and found very useful in several COOL container classes for defining predicate types for the class. Another use of this form is to provide automatic declarations of nested parameterized classes, that is, to declare a parameterized class for a class template which is itself derived from another parameterized class template. Each variation of template allows additional optional parameters with the following syntax: parms ::= type name [= value] [, parms] where type is the type of the parameter, (such as, class or int); name is the name of the parameter that is substituted when tem- plate is expanded; and value is the default value of parameter name. The following is an example of template for the class, Vector<type>. -7- template <class Type> Vector { // predicate functions typedef int (*Vector_Type##_Predicate) (const Type&, const Type&); typedef Boolean (*Vector_Type##_Compare) (const Type&, const Type&); }; template <class Type> class Vector<Type> { // Parameterized Vector class private: Type* v; // Vector of pointer to Type int num_elements; // Element count int size; // Size of vector object public: Vector<Type> (); // Empty constructor Vector<Type> (int); // Constructor with size Vector<Type> (const Vector<Type>&); // Constructor with reference ~Vector<Type> (); // Destructor inline Type& operator[](int n); // Operator[] overload for Type ... // ... other member functions }; template <class Type> // Overload operator [] inline Type& Vector<Type>::operator[] (int n) { return this->v[n]; } template <class Type> // Constructor with size Vector<Type>::Vector<Type> (int n) { this->v = new Type[n]; this->size = n; this->num_elements = 0; } ... // ... other member functions 4.2. An Initial Programmer Interface: DECLARE and IMPLEMENT As stated earlier, a template for a parameterized class is divided into a declarative part and an implementation part. In our first attempt at implementing parameterized template support, the programmer creates instances of a parameterized class using DECLARE to expand the declarative part and IMPLEMENT to expand the implementation part. DECLARE defines the parameterized class for a specific type and IMPLEMENT generates the member functions supporting this type-specific class. DECLARE must be used in every file that includes or makes use of the parameterized class. IMPLEMENT must be used only once in the application for each type over which the class is parameterized; otherwise the linker will generate errors about multiple versions of the same member func- tions. For example, to create a vector of doubles, the following would be used: -8- #include <Vector.h> DECLARE Vector<double>; IMPLEMENT Vector<double>; Vector<double> vs(30); DECLARE expands to code which defines a vector class of doubles and its associated inline member functions. IMPLEMENT causes a class definition with its associated member functions to be gen- erated and expanded in the file. When compiled, this causes the class Vector_double to be declared and defined. One drawback of the use of IMPLEMENT, however, is the fact that the entire class with all its member functions is generated and linked into the program image, even if the programmer only requires the use of two or three member functions. This problem can be avoided by the use of the COOL C++ Control Program (CCC) discussed below. Con- tinuing with the example above, the template for the Vector<type> class for doubles would expand to the following code: // predicate functions typedef int (*Vector_double_Predicate) (const double&, const double&); typedef Boolean (*Vector_double_Compare) (const double&, const double&); class Vector_double { // Parameterized Vector class private: double* v; // Vector of pointer to double int num_elements; // Element count int size; // Size of vector object public: Vector_double (); // Empty constructor Vector_double (int); // Constructor with size Vector_double (const Vector_double&); // Constructor with reference ~Vector_double (); // Destructor inline double& operator[](int n); // Operator[] overload for double ... // ... other member functions ... }; // Overload operator [] inline double& Vector_double::operator[] (int n) { return this->v[n]; } // Constructor with size Vector_double::Vector_double (int n) { this->v = new double[n]; this->size = n; this->num_elements = 0; } ... // ... other member functions ... Vector_double vs(30); Declarations of nested parameterized types and the use of non- -9- type arguments in a template definition are also supported. For example, it is possible to declare a vector of vectors of ints with Vector<Vector<int>>. In addition, a class template derived from another class template is supported, that is, a type parame- ter in one template class can be used to declare another class template of that type. For example, the COOL Association<T1,T2> class is a parameterized container class that takes two type arguments, T1 and T2. The header file for this class has the following templates. template <class T1, T2> Association { DECLARE Pair<T1, T2>; // Declare Pair object type DECLARE Vector<Pair<T1, T2>>; // Declare Vector of Pairs } ... // ... // Association<T1,T2> class definition here template <class T1, T2> Association { IMPLEMENT Pair<T1, T2>; IMPLEMENT Vector<Pair<T1, T2>>; } By using template in this manner, DECLARE for the Association<T1,T2> class invokes DECLARE on the correct types for the Pair<T1,T2> and Vector<Type> classes. Likewise, IMPLEMENT for the Association<T1,T2> class invokes IMPLEMENT for the Pair<T1,T2> and Vector<Type> classes. Non-type arguments as template parameters are used to provide guidelines to be used when a template is expanded. For example, the N_Tree<Node,Type,nchild> class in COOL takes as arguments a node type (either static or dynamic), a type specifying the value-type each node will hold, and an argument that specifies the number of initial subtrees (or children) each node is to have. The node argument is itself the name of a parameterized class and a nested parameterized template definition is automati- cally generated based upon the supplied type and number argu- ments. As such, a single template can be used to generate several different classes with different behaviors and features. 4.3. A Revised Programmer Interface: COOL C++ Control Program (CCC) The DECLARE and IMPLEMENT macros discussed above were the first programmer interface implemented for parameterized template sup- port. We soon discovered, however, that this macro expansion mechanism had two serious problems. First, the type over which a class was parameterized would have to support all operators used in the template, even if not applicable or needed. For example, the COOL List<Type> class has several member functions that use operator<. However, if what the programmer needs is a list of window objects and does not ever use List<Type> member functions that require operator<, compile-time errors from the offending functions that got macro-expanded are nevertheless generated. Second, With the simplistic linkers available on many operating -10- systems today, an application gets all of these member functions linked into the executable image. Typically, an application uses only a small percentage of the member functions of a parameter- ized class. The remaining unused member functions are useless overhead, increasing program size and memory requirements. A revised programmer interface for parameterized templates was implemented to resolve these problems and centers around a new program to be used as the main interface between the user and the preprocessor/compiler in a make file. This program, the COOL C++ Control program (CCC), augments the standard CC script. For most operations, user options and command line arguments are passed straight through to the underlying CC program. However, when the -X option is specified, the CCC program goes to work in the fol- lowing manner. As Stroustrup[6] suggested, -X"Foo<Bar>" is used on the command line to indicate that the programmer wants to parameterize class Foo<Type> over some type Bar. Additional options for include file search path and a user-defined library archive are required as described below. CCC finds the header file(s) implementing class Foo and type Bar, then proceeds to define that type for the compiler. It then fractures the imple- mentation of this new type along template boundaries, placing each non-inline member function in a separate source file, com- piling it, and putting the resulting object file in a user- specified library archive. If a particular operator is not defined for the type over which the class is parameterized (as with the example of operator< above), a compile time error for that one file is generated. However, the remaining member func- tions, one in each fractured template, are still compiled and added to the user library. For each parameterized class in an application, CCC fractures the parameterized class definition along template boundaries, causing each template specifying a member function of the parameterized class to be compiled into a separate object file. These separate object files are then added to an application-specific object library. Since each member function is in its own object module in the library, only those member functions actually used in the application are linked into the final executable image. To use CCC, the programmer specifies a library name, one or more header files containing templates, and specific parameterized classes as command line arguments to CCC. Other arguments are passed on unchanged to the C++ compiler and system linker. A single invo- cation of CCC can either process a parameterized class type or compile a C++ source file, but not both. For example, CCC -lapp -c List.h String.h -X "List<String>" expands the template for a list of strings. The resulting object files from the fractured parameterized List<Type> class are stored in the library, libapp.a. The -c option is passed to the compiler to indicate that it should not continue with the link phase. The library archive libapp.a is added to the list of libraries specified in the make file to be searched during the link step. The net result is a library archive containing object files, each -11- implementing one member function for the parameterized class and type. This process solves the two problems identified above with the use of the macros DECLARE and IMPLEMENT. First, operators not defined for a type cause compile-time errors on that one file. Once a parameterized class has been implemented and provided in a library, compile errors will only occur when a type is selected that does not have all operators implemented. The user of the class will see these, and if the member function in question is required, s/he can add that necessary operator to the type class. Second, only member functions actually used in an application are linked into the final executable image. 4.4. Future Improvements to CCC CCC essentially provides a more sophisticated version of the IMPLEMENT macro discussed above. However, the programmer is still required to place the DECLARE macro in the appropriate files. One option under consideration to resolve this problem is the use of a command line switch similar to the +e0/+e1 switchs on the AT&T cfront translator. Under this scenario, the equivalent of the +e0 option would be used to declare the type for a parameter- ized class and generate the inline member functions (as the DECLARE macro does) but not to generate the remaining member functions. The programmer would use the equivalent of the +e1 option on one source file to cause the remaining non-inline member functions to be generated and placed in a library archive. A second problem with CCC concerns the specification of nested parameterized classes. A programmer should be able to use -X"Vector<List<int>>" on the command line to specify creation of nested parameterized classes. Currently, CCC does not handle this case appropriately. A more sophisticated command line parser should be able to recognize and implement nested types before trying to expand the outer most parameterized class. 5. Conclusion The COOL macro facility provides a mechanism to implement signi- ficant language features and extensions for C++ that are unavail- able with current language implementations. The macro facility is implemented in an enhanced preprocessor that is both efficient and portable, thus allowing for delivery of enhanced language features on many platforms. This macro extension is at the heart of the parameterized templates functionality. CCC is used in place of the normal procedure for controlling the compilation process. It provides all of the functionality of the original CC program with additional support for the COOL preprocessor and parameterized type expansion. Finally, the preprocessor provides an ideal mechanism for quickly prototyping and testing additional language functions and syntax without requiring access to or modification of a compiler. 6. Status of COOL Texas Instruments has been using the enhanced macro facility and the implementation of parameterized templates internally on several projects for the last year. Many classes and programs have been successfully designed and implemented, taking full advantage of the power of parameterized templates and the enhanced macro facility. In particular, we have found that the -12- use of a class library supplying many basic parameterized con- tainer classes significantly increases the productivity of the programmer, enabling applications to be prototyped in a shorter time period than might otherwise be possible. COOL is currently up and running on a Sun SPARCstation 1 (TM) running SunOS (TM) 4.x, a PS/2 (TM) model 70 running SCO XENIX(r) 2.3, a PS/2 model 70 running OS/2 1.1, and a MIPS running RISC/os 4.0. The SPARC and MIPS ports utilize the AT&T C++ translator (cfront) version 2.0 and the XENIX and OS/2 ports utilize the Glockenspiel translator with the Microsoft C compiler. 7. References [1] Brian Kernighan and Dennis Richie, The C Programming Language, Second Edition, Printice-Hill, Englewood Cliffs, NJ, 1988. [2] Mary Fontana, Martin Neath and Lamott Oren, COOL - A C++ Object-Oriented Library, Information Technology Group, Aus- tin, TX, Internal Original Issue January 1990. [3] Texas Instruments Incorporated, C++ Object-Oriented Library User's Manual, Information Technology Group, Austin, TX, Internal Original Issue January 1990. [4] AT&T Incorporated, C++ Language System Release 2.0, AT&T Product Reference Manual Select Code 307-146, 1989. [5] Guy L. Steele Jr, Common LISP: The Language, Second Edition, 1990. [6] Bjarne Stroustrup, Parameterized Types for C++, Proceedings of the USENIX C++ Conference, Denver, CO, October 17-21, 1988, pp. 1-18. _________________________ SunOS and SPARCstation 1 are trademarks of Sun Mi- crosystems, Inc. PS/2 is a trademark of International Business Machines Corporation. XENIX is a registered trademark of Microsoft Corpora- tion. -13- -14-