Can C++ Learn from Generics in Ada?

Introduction

Although C++ templates afford great flexibility and power in the language, it is widely recognised that the widespread adoption of modern template techniques is hampered by "features" of the implementation of templates [ Heinzmann2004a , Heinzmann2004b ]. At the recent ACCU, conference Stroustrup [ Stroustrup2005 ] described two proposals currently before the C++ standards committee for implementing Concepts in C++. Concepts seek to alleviate the difficulties of template programming by separating the definition of the template from its instantiation to a certain extent, in as much as the contract placed on the types used to instantiate the contract is explicitly stated, so it can be checked and more meaningful diagnostics given.

In a question at the end of this presentation, Coplien suggested that other languages may have models that C++ templates could learn from, and specifically mentioned Ada generics. This paper will give an overview of the features of the Ada generics model, from a personal perspective of a programmer with some experience of Ada, rather than a language designer. It will show why the author believes C++ has little to gain from Ada generics.

Rationale of Ada

The design of the Ada language puts a very strong emphasis on safety and integrity. It is a language that is particularly tractable to static analysis by abstract interpretation [ Chapman2001 ]. The design of the generic model carries this on, aiming to provide " the security that is present for ordinary, unparameterized program units; in particular the degree of compilation-time error checking " [ Ada83 ].

The main forces in the design of C++ are significantly different. While no language deliberately courts run time errors, C++ puts the emphasis more on flexibility and expressiveness [ Stroustrup2000 ]. As a consequence of these differences, the Ada generic model is very different from the template model of C++.

The Ada Generic Model

The model of generic units in Ada allows a high degree of static type checking to be applied to the generic body alone, independent of its instantiation. It imposes a contract on the types that can be used to instantiate the unit. This is a very attractive idea, and is the reasoning behind the proposals for Concepts in C++. However, the use of generics in Ada will not fit well with the kind of ad-hoc specialisation and template reuse that is common in modern C++.

Two features of the Ada generics mechanism would be particularly unsuitable for C++, and they are also key to the way Ada achieves the goal of separating definition and instantiation:

1. The need for explicit instantiation;

2. The limited set of formal types that can be used.

Furthermore, Ada's very strict type model leads to additional generic parameters being needed that at first sight seem redundant.

Explicit Instantiation

The first of these is a tiresome burden for the programmer but probably not inherent in the generic model. Given the overheads implied by the syntax, this can be as much typing (and therefore reading) as writing out the body in full. For example, whereas in C++ we might do this:

int x, y;
some_big_struct a, b;
. . .
swap (x, y);
swap (a, b);

The Ada equivalent would be:

X, Y : integer;
A, B : Some_Big_Struct;
procedure swap is new swap (integer);
procedure swap is new swap (Some_Big_Struct);
. . . 
swap (a, b);
swap (x, y);

This is generally a minor hassle in the idioms of Ada. However, it clearly makes the idioms of modern C++ impractical.

Limitations on Formal Types

The most significant drawback of the Ada generics mechanism is the restrictions on what the generic body can assume from the type provided to it. The declaration and instantiation of a generic in Ada takes the following form:

generic
   Type T is X;
Package Foo;

Package MyFoo is new Foo (Y)

Where X is one of the keywords listed in the following table and Y is an actual type argument as listed:

The only other permitted types are access (pointer) to one of those types, or an array of one of those types. As well as packages, functions and procedures can be declared using the same syntax. For example, the swap procedure might be declared in Ada as:

generic
   type T is private;
procedure swap (X, Y : in out T);

There is no way to access arbitrary components of a record (struct), nor to call overloaded subprograms ^{[ 1 ]} by name matching. The "new subtype_mark" form does allow access to arbitrary members and subprograms of the base subtype; this achieves approximately the same effect as passing an object by base-class reference in C++, which of course does not require a template at all.

As an example of the limitations this imposes, consider two record types:

Type rec1 is record
  X : Integer;
  Y : Integer;
  Some_Other_Stuff : Foo;
End record;

Type rec2 is record
  Y : Integer;
  X : Integer;
  More_Stuff : Bar;
End record;

This is roughly equivalent to the C++:

struct Rec1 {
  int X; 
  int Y;
  Foo some_other_stuff;
};

struct rec2 {
  int y;
  int x;
  bar more_stuff;
};

Now imagine that the X and Y members are semantically equivalent in both structs, and some duplication is discovered which can be refactored. In C++, the following is possible:

template <typename XandY>
void do_common_thing (XandY& obj) {
  obj.X = getX();
  obj.Y = getY();
}

This is not possible in Ada; "something with members called X and Y" is not in the list above, so when you try to write:

Generic
  Type XandY is ???
Procedure do_common_thing (obj : in out XandY);

There is nothing that can be put in the ???. The same problem extends to calling subprograms using arguments of the parameterised type (the Ada equivalent of calling member functions). The only way for the generic body to call a subprogram with the parameter type as an argument is to declare each subprogram required as an additional generic parameter. Clearly this can become very long-winded if there are several subprograms called from one generic.

The Ada standard [ Ada95 ] sec 12.1 gives the following example:

generic
type Item is private;
with function "*"(U, V : Item) return Item
is <>;
function Squaring(X : Item) return Item;

which has to be instantiated like this, assuming that the package contains an overloaded operator for its user-defined type:

function square is new squaring 
(My_Package.My_Type, My_Package."*");

Apparently Redundant Parameters

Another source of syntactic tedium is the lack of inference of parameterized types. This is not actually a result of the generic model, but arises from the strict type model in Ada. As an illustration, this code fragment is taken from the Ada 95 reference manual [ Ada95 ], section 12.5.4:

generic
     type Node is private;
     type Link is access Node;
package P is
     ...
end P;

Access is the Ada keyword for pointer; the programmer is forced to tell the compiler what synonym for "pointer to Node" is going to be used. Compare this with what might be used in C++:

template <typename Node>
class P {
public:
  typedef Node* Link;
  ...
};

To a C++ programmer's eyes, the Link parameter in Ada looks redundant. However, it is not; a new type created as a synonym for "access Node" is a distinct type and cannot be implicitly converted from any other similar type. The programmer thus has to tell the generic in case there is already a new type name in use. In C++ of course, typedef does not have this effect; it merely introduces a new spelling for the same type. While there are pros and cons for this approach, it does impose some lack of flexibility on the use of generics.

Conclusions

The Ada generics model has always been contract based, as befitting the origins and idioms of the language. This provides for a high degree of early checking, at the expense of flexibility. While there may be some general lessons to be drawn from this approach, the specifics of the mechanism make it far too restrictive to be of any direct use in C++.

Acknowledgements

The author wishes to thank the reviewers for their helpful comments.

References

[Ada83] "Rationale for the Design of the Ada Programming Language", http://archive.adaic.com/standards/83rat/html/ratl-12-01.html

[Ada95] http://www.adaic.com/standards/ada95.html

[Chapman2001] "SPARK and Abstract Interpretation - a white paper", http://praxis-his.com/pdfs/spark_abstract.pdf

[Heinzmann2004a] "The Tale of a Struggling Template Programmer", Stefan Heinzmann, Overload 61 June 2004.

[Heinzmann2004b] "A Template Programmer's Struggles Resolved", Stefan Heinzmann and Phil Bass, Overload 61 June 2004.

[Stroustrup2000] The C++ Programming Language, Special Edition , Bjarne Stroustrup, pub Addison Wesley.

[Stroustrup2005] "Better Support for Generic Programming", http://www.accu.org/conference/accu2005/kd9fc73n3uj94krmnfcj383jhpaduyivby/Stroustrup%20-%20Better%20Support%20for%20Generic%20Programming.pdf

^{[ 1 ]} Ada distinguishes between Functions, which return a value and may take only input parameters, and Procedures, which do not return a value and may take input, output and in-out parameters. Together they are termed subprograms.