A Case for Template Aliasing

Document number:   WG21/N1451 = J16/03-0034
Date:   April 25, 2003
Project:   Programming Language C++
Reference:   ISO/IEC IS 14882:2003(E)
Reply to:   Walter E. Brown <wb@fnal.gov>
  Mail Station 234
  Fermi National Accelerator Laboratory
  Batavia, IL 60510-0500, USA


Contents

1.  Foreword 7. The Case for Template Aliasing
2.  Outline of this Paper 8. Summary
3.  Recap of N1406 9.  Afterword
4.  Developments 10.  Acknowledgments
5.  The Problem Domain 11.  References
6.  A Notional Implementation

Figures

  1. Examples of Physical Quantities
  2. Two Categories of Commensurate Physical Quantities
  3. Determining Products of Physical Quantities
  4. Examples of Physical Quantities' Signatures
  5. Physical Quantities Implementation Sketch
  6. Examples of Desired Template-id Aliases
  7. Two Equivalent Function Implementations
  8. A Candidate Syntax for Template Aliasing
  9. Examples of Commensuration via a Shared Alias
  10. Applied Template Aliasing
  11. EWG Working Syntax for Template Aliasing

1. Foreword

This paper is based on a presentation given by the author to the members of WG21 and J16 at a joint meeting held the morning of April 8, 2003. It immediately followed a talk by Herb Sutter based on his paper, "Proposed Addition to C++: Typedef Templates" [Sutter].

Sutter's paper had been prepared pursuant to outcomes of discussions on this topic, notably during Evolution Working Group meetings held October 21-25, 2002, in Santa Cruz, California. In the paper and corresponding talk, Sutter presented two distinct approaches to the proposed new language feature, recommending one of the two approaches for further consideration. However, we had reasons to prefer the other approach. Accordingly, we prepared our 8 April presentation in order to set forth what we believed to be a compelling example motivating our preference.

In preparing the present paper, we introduced some changes from the 8 April presentation on which it is based: In addition to adaptations due to the different stylistic and formatting conventions, we have corrected typographical errors, have slightly extended some of the examples and expanded their exposition, and have added new sections: this Foreword; an Outline of this Paper; an Acknowledgment section; a section giving References to the literature; and a brief Afterword to incorporate a few, more recent, developments.

2. Outline of this paper

After a brief recap of [Sutter], we will describe a few relevant developments that have taken place since its October 2002 publication. This will be followed by a high-level exposition of the problem domain on which our examples are based. A notional implementation of this problem domain is then presented, setting the stage for our use of the typedef templates feature under discussion.

After showing our application for this feature, we present a code comparison illustrating the desirability of the alternative approach to typedef templates. An even more realistic application follows, underscoring the desirability of the typedef aliasing alternative we recommend. We conclude with a brief series of questions intended to point out the areas in which the aliasing alternative seems to provide more appropriate behavior.

3. Recap of N1406

In his paper, Sutter explicates and proposes a new feature, "typedef templates," for C++0x. The feature is motivated via the desire "to allow the programmer to create a synonym for a template where some, but not all, actual template arguments are fixed" [§1]. The feature itself would permit the introduction of "a parameterized synonym" [§2.1].

Sutter goes on to describe two distinct possible semantic models for the typedef template feature. Using the nomenclature "Specialization" for option 1 and "Everything Else" for option 2, the paper asserts that these models are mutually exclusive, and then recommends option 1, the specialization model, for further consideration. As Sutter puts it, "This paper proposes Option 1, thus favoring specialization at the expense of matching, deduction, and same-declarations . . . ."

4. Developments

Since publication of [Sutter], both Gabriel Dos Reis [Dos Reis] and David Vandevoorde [Vandevoorde1] communicated their opinions that the two semantic models outlined by Sutter are not necessarily mutually exclusive. This is potentially quite significant: as respected members of noted compiler implementation teams, these gentlemen have considerable expertise in the analysis of computer programming language features. It may thus be possible that sufficiently clever language design and implementation may permit the two semantic models to coexist. This would be a desirable outcome since both models appear to be useful to C++ programmers.

Vandevoorde also suggested ([Vandevoorde1 and Vandevoorde2]) alternate terminology to denote the semantics of Sutter's option 2. In contrast to the rather informal "Everything Else" parlance, Vandevoorde offered the term "template aliasing" to identify this semantic alternative to the "specialization" semantics of typedef templates. Because Vandevoorde's suggested nomenclature seems to provide a somewhat more precise indication of the desired intent of that semantic option, we will adopt it in the remainder of this paper, and recommend its future use as the terminology of choice to describe this variant of the feature under discussion.

Finally, the present author has come to the conclusion that, of the two semantic models identified by Sutter, the now-renamed "template aliasing" model is preferable to the initially recommended specialization model. In the remainder of this paper, we will present our reasons for this preference, expressed in the form of examples from a problem domain we will introduce in the next section.

5. The Problem Domain

Our examples are rooted in a problem domain known as "Physical Quantities" ("PQ" or "PQs" for short). According to International Standard 31, physical quantities "are used for the quantitative description of physical phenomena" [ISO31, part 0].

Pursuant to [ISO1000], the International System of Units (SI), Figure 1 presents several examples of PQs. The left column lists SI's seven prescribed base quantities, while the right column illustrates a number of derived quantities. Base quantities are treated as fundamental in that no base quantity depends on any other base quantity. In contrast, each derived quantity can be expressed as some product of base quantities.

Figure 1. Examples of Physical Quantities
SI's Base Quantities

   1. length
   2. mass
   3. time
   4. temperature
   5. current
   6. amount of substance
   7. luminous intensity
  Some Derived Quantities

   • area
   • volume
   • velocity
   • acceleration
   • force
   • energy
   • electric charge
   • etc.

PQs group into "categories ... which are mutually comparable" [ISO31, part 0]. This property of a category's PQs is commonly known as commensuration. Figure 2 presents two examples of PQ categories: each column constitutes a category of commensurate PQs.

Figure 2. Two Categories of Commensurate Physical Quantities
   • length
   • diameter
   • distance
   • perimeter
   • height
   • etc.
     ◊ energy
   ◊ heat
   ◊ work
   ◊ enthalpy
   ◊ electron affinity
   ◊ etc.

It is possible to form expressions based on PQs. The process of determining what kind (category) of PQ will result from such an expression is known as dimensional analysis. For example, the sum or difference of commensurate PQs yields a result of the same kind. However, the sum or difference of incommensurate PQs is not meaningful and so has no correct result.

In contrast, a product or quotient of PQs is always meaningful, and yields a result whose kind can be determined from the operands' kinds. The process is illustrated by the examples in Figure 3. Note that the key intermediate step is to express each PQ as the product of base quantities raised to powers.

Figure 3. Determining Products of Physical Quantities
length × area   ≡   length1 × length2   ≡   length3   ≡   volume
length / time   ≡   length1 / time1   ≡   length1 × time-1   ≡   velocity

Because each PQ can be expressed as a specific product of the seven base quantities, we identify each PQ by a list of the number of times each base quantity is used in such an alternate expression. Thus, an area is treated as the product of two lengths (and of no other base quantities), a volume as the product of three lengths, and so on. We will use the term PQ signature to denote such a list when it is in a canonical order (e.g., the length component always first, the mass component always second, the time component always third, etc.), Figure 4 presents several additional examples of such PQ signatures. Note that two PQs can have identical PQ signatures if and only if they are commensurate.

Figure 4. Examples of Physical Quantities' Signatures
Physical Quantity     PQ Signature
length, height, etc.     1, 0, 0, 0, 0, 0, 0
area     2, 0, 0, 0, 0, 0, 0
volume     3, 0, 0, 0, 0, 0, 0
time     0, 0, 1, 0, 0, 0, 0
velocity     1, 0,-1, 0, 0, 0, 0
acceleration     1, 0,-2, 0, 0, 0, 0

6. A Notional Implementation

The implementation sketch in Figure 5 is neither complete nor of suitable industrial strength; it is merely intended to complete the outline of our problem domain as it might be expressed in code. Although different in detail, it is similar in nature and intent to an exposition found in [Barton/Nackman, §16.5].

In brief, the implementation is based on a class template taking at least eight template parameters. Each instantiation of the template will correspond to a specific kind of physical quantity. The first template parameter, R, represents the user's desired representation type (such as double). Seven additional template parameters, one for each of SI's base quantities, collectively denote a PQ signature. (We have elided many of these additional parameters in order to simplify the presentation.)

Figure 5. Physical Quantities Implementation Sketch
template< class R                     // representation type
        , int L, int M, int T, ... >  // PQ signature
struct PQ
{
  R value;

  PQ( R v = R() )
  : value(v)
  { }

  // sum commensurate PQs:
  PQ
  operator += ( PQ rhs )
  {
    this->value += rhs.value;
    return *this ;
  }

  // multiply arbitrary PQs:
  template< int L2, int M2, int T2, ... >
  PQ< R, L+L2, M+M2, T+T2, ... >
  operator * ( PQ< R, L2, M2, T2, ... > rhs )
  {
    typedef PQ< R, L+L2, M+M2, T+T2, ... > result_type;
    return result_type( this->value * rhs.value );
  }

};

7. The Case for Template Aliasing

The above implementation identifies physical quantities by their PQ signatures. Because it is at best unwieldy to express a physical quantity in this way, we prefer our code to use the physical quantities' more conventional names. We would rather write length<R> than PQ<R,1,0,0,0,0,0,0>. At the same time, we wish the compiler to recognize, for purposes of dimensional analysis and type-checking, the equivalence of these two forms of template-ids.

Conventionally, such aliasing is accomplished in C++ via typedefs. Here, however, we seek a form of parameterized typedef because the desired form of the aliasing is based not on types but on templates and their partial specializations. Figure 6 provides examples of the sorts of code equivalence we believe necessary and useful.

Figure 6. Examples of Desired Template-id Aliases
PQ signature-based Template-id     Conventionally-named Alias
PQ< R, 1,0, 0,0,0,0,0 >     length< R >
PQ< R, 2,0, 0,0,0,0,0 >     area< R >
PQ< R, 3,0, 0,0,0,0,0 >     volume< R >
PQ< R, 0,0, 1,0,0,0,0 >     time< R >
PQ< R, 1,0,-1,0,0,0,0 >     velocity< R >
PQ< R, 1,0,-2,0,0,0,0 >     acceleration< R >

To demonstrate the utility and desirability of such aliasing, Figure 7 presents two implementations of a rather straightforward function. The first version uses only the PQ signature-based nomenclature, while the second version uses the more conventional nomenclature that would be made possible by the recommended template aliasing feature. It seems clear that the code's legibility and comprehensibility is greatly enhanced by use of conventional names for physical quantities.

Figure 7. Two Equivalent Function Implementations
template< class R >
PQ<R,1,0,0,0,0,0,0>
h( PQ<R,1,0,0,0,0,0,0> leg1, PQ<R,1,0,0,0,0,0,0> leg2 )
{
  return sqrt( leg1 * leg1  +  leg2 * leg2 );
}
template< class R >
length<R>
hypotenuse( length<R> leg1, length<R> leg2 )
{
  return sqrt( leg1 * leg1  +  leg2 * leg2 );
}

Sutter's proposed syntax (illustrated in Figure 8, extended to permit default template arguments) would be one acceptable means of expressing such equivalences, as would any clean alternate notation.

Figure 8. A Candidate Syntax for Template Aliasing
template< class R = double >
typedef  PQ< R, 1,0,0,0,0,0,0 >  // declared above
         length< R >;            // declared here

Further, Sutter's option 2, dubbed "template aliasing" by Vandevoorde as described above, would provide the "matching, deduction, and same-declarations" semantics we seek for such a feature. Together, these semantics would permit the compiler to apply the rules of commensuration as part of the type system. Commensurate PQs would share a common alias to identical PQ signature-based template-ids as illustrated in Figure 9; incommensurate PQs would have no common aliases. All listed template-ids are equivalent and hence fully interchangeable; template aliasing must be completely transitive.

Figure 9. Examples of Commensuration via a Shared Alias
Conventional Usage     PQ signature-based Alias
length<R>     PQ<R,1,0,0,0,0,0,0>
diameter<R>     same as above
distance<R>     same as above
perimeter<R>     same as above
height<R>     same as above
altitude<R>     same as above

Figure 10 shows one additional application of template aliasing. This is the declaration of a function that applies the physics of Bremsstrahlung in calculating the energy of a particle after it passed through a piece of material. This calculation is based on formulas in the Review of Particle Physics [PDG, §23.4.1]. Its parameters include the material's composition, density, and thickness, as well as the particle's energy before encountering the material.

Figure 10. Applied Template Aliasing
template< class R >
energy< R >
final_energy( element<R> const &  material
            , density<R> const    how_dense
            , length <R> const    how_thick
            , energy <R> const    starting_energy
            );

It seems clear, again from rather straightforward inspection, that the declaration in Figure 10 would be considerably uglier in the absence of the conventional names that template aliasing could introduce. More importantly, with all the elided int parameters exposed, the code would have taken significant effort to ensure its correctness and, once written, would still be significantly more difficult to comprehend.

8. Summary

In this paper, we have presented a case for the adoption of a new C++ language feature, template typedefs, and have advocated that this feature's semantics be those known as template aliasing, formerly referred to as "Everything Else." We have presented a compelling use case for template aliasing in order to explicate the desired semantics, and to demonstrate significant advantages of the template aliasing semantics over the "Specialization" semantics.

We believe this feature, with our preferred semantics including deduction, matching, and same-declarations, would be a useful contribution to the C++ programming language, for it seems to fill a significant gap that can not be met today. While C++ does today encompass the notion of type identity (typically expressed via typedef), there is today no comparable means of expressing template identity, with or without partial specialization.

9. Afterword

The Evolution Working Group has given this topic considerable attention, both before (e.g., in [Dos Reis] and in [Vandevoorde2]) as well as after this paper's presentation. A tentative resolution of the underlying issues has emerged from these deliberations, with syntax (applied to our problem domain) approximately as shown in Figure 11, and with tentative semantics akin to those advocated herein. Consistent with the recent [Dos Reis/Marcus], this feature is now known as "template aliasing" in preference to Sutter's "typedef templates" nomenclature, and encompasses a form of specialization as well.

Figure 11. EWG Working Syntax for Template Aliasing
template< class R = double >
length = PQ< R, 1,0,0,0,0,0,0 >;

Future evolution of this topic may result in a more general approach to aliasing, encompassing this and other features already part of C++. For example, namespace aliases and typedefs are in today's C++, and are certainly forms of aliasing. While it may become possible to unify all these features, current thinking on this issue now encompasses the notion of aliases for templates.

10. Acknowledgments

We would like to express our appreciation to Gabriel Dos Reis, Benjamin Kosnik, Mat Marcus, Bjarne Stroustrup, Herb Sutter, and David Vandevoorde for their very helpful respective discussions and correspondence related to this paper's topic. We are also grateful to our colleagues Mark Fischler, James Kowalkowski, and Marc Paterno for their careful reading of earlier drafts of this paper. Finally, we wish to recognize the support of the Fermi National Accelerator Laboratory's Computing Division, sponsors of Fermilab's participation in the C++ standards effort. Thank you, one and all.

11. References

[Barton/Nackman]
Barton, John J., and Lee R. Nackman: Scientific and Engineering C++. Addison-Wesley, 1994. ISBN 0-201-53393-6.
[Dos Reis]
Dos Reis, Gabriel: typedef template and template typedef. Reflector message c++std-ext-5658. November 29, 2002.
[Dos Reis/Marcus]
Dos Reis, Gabriel, and Mat Marcus: Proposal to add template aliases to C++. WG21/N1449 (same as J16/03-0032): April, 2003.
[ISO31]
International Standards Organization: "Quantities and units," International Standard ISO 31:1992(E). In Quantities and units, Third edition, 1993. ISBN 92-67-10185-4.
[ISO1000]
International Standards Organization: "SI units and recommendations for the use of their multiples and of certain other units," International Standard ISO 1000:1992(E). In Quantities and units, Third edition, 1993. ISBN 92-67-10185-4.
[PDG]
Particle Data Group (Groom, D. E., et al.): "Review of Particle Physics," Eur. Phys. J. C 15, 1-878 (2000).
[Sutter]
Sutter, Herb: Proposed Addition to C++: Typedef Templates. WG21/N1406 (same as J16/02-0064): October 21, 2002.
[Vandevoorde1]
Vandevoorde, David: Personal Conversation. April, 2003.
[Vandevoorde2]
Vandevoorde, David: Re: typedef template and template typedef. Evolution group reflector message c++std-ext-5680. December 2, 2002.