C++ Templates as Partial Evaluation

arXiv:cs/9810010v2 [] 2 Nov 1998

Todd L. Veldhuizen∗

Abstract
This paper explores the relationship between C++ templates and partial evaluation.
Templates were designed to support generic programming, but unintentionally provided
the ability to perform compile-time computations and code generation. These features
are completely accidental, and as a result their syntax is awkward. By recasting these
features in terms of partial evaluation, a much simpler syntax can be achieved. C++
may be regarded as a two-level language in which types are first-class values. Template
instantiation resembles an offline partial evaluator. This paper describes preliminary
work toward a single mechanism based on Partial Evaluation which unifies generic
programming, compile-time computation and code generation. The language Catat is
introduced to illustrate these ideas.

1

Introduction

Templates were added to the C++ language to support generic programming. However,
their addition unintentionally introduced powerful mechanisms for compile-time computation and code generation. These mechanisms have proven themselves very useful in generating optimized code for scientific computing applications [13, 16, 22, 23]. Since they are
accidental features, their syntax is somewhat awkward. The goal of this paper is to achieve
a simpler syntax by recasting these features as partial evaluation. We start by briefly
summarizing the capabilities provided by C++ templates, both intended and accidental.

1.1

Generic programming

The original intent of templates was to support generic programming, which can be
summarized as “reuse through parameterization”. Generic functions and objects have
parameters which customize their behavior. These parameters must be known at compile
time (i.e. have static binding). For example, a generic vector class can be declared as:
template<typename T, int N>
class Vector {
// some member functions here...

1

private:
T data[N];
};

5

// Example use of Vector
Vector<int,4> x;

10

Indiana University Computer Science Department, Bloomington Indiana 47405, USA. Phone: (812)
855-8305. tveldhui@extreme.indiana.edu
∗

1

2
The Vector class takes two template parameters (line 1): T, a type parameter, specifies the
element type for the vector; N, a nontype parameter, is the length of the vector. To use the
vector class, template arguments must be provided (line 10). This causes the template to
be instantiated: an instance of the template is created by replacing all occurrences of T and
N in the definition of Vector with int and 4, respectively.
Functions may also be templates. Here is a function template which sums the elements
of an array:
template<typename T>
T sum(T* array, int numElements)
{
T result = 0;
for (int i=0; i < numElements; ++i)
result += array[i];
return result;
}

This function works for built-in types, such as int and float, and also for user-defined types
provided they have appropriate operators (=, +=) defined. Templates allow programmers
to develop classes and functions which are very customizable, yet retain the efficiency of
statically configured code.

1.2

Compile-time computations

Templates can be exploited to perform computations at compile time. This was discovered
by Erwin Unruh [19], who wrote a program which produced these errors at compile time:
erwin.cpp
erwin.cpp
erwin.cpp
erwin.cpp
erwin.cpp
...

10:
10:
10:
10:
10:

Cannot
Cannot
Cannot
Cannot
Cannot

convert
convert
convert
convert
convert

’enum’
’enum’
’enum’
’enum’
’enum’

to
to
to
to
to

’D<2>’
’D<3>’
’D<5>’
’D<7>’
’D<11>’

The program tricked the compiler into calculating a list of prime numbers! This capability
was quite accidental, but has turned out to be very useful. Here is a simpler example which
calculates pow(X,Y) at compile time:
template<int X, int Y>
struct ctime pow {
static const int result = X * ctime pow<X,Y-1>::result;
};
// Base case to terminate recursion
template<int X>
struct ctime pow<X,1> {
static const int result = X;
};
// Example use:
const int z = ctime pow<5,3>::result; // z = 125

The first template defines a structure ctime pow which has a single data member
result. The static const qualifiers of result make its value available at compile time.

3
ctime pow<X,Y> refers to ctime pow<X,Y-1>, so the compiler must recursively instantiate
the template for Y,Y-1, Y-2, ... until it hits the base case provided by the second template,
which is a partial specialization.
Here is an array class which uses ctime pow to calculate the number of array elements
needed:
template<typename T numtype, int N length, int N dim>
class SquareArray {
// ...
static const int numElements = ctime pow<N length,N dim>::result;
T_numtype data[numElements];
}
// Example use:
SquareArray<float,4,2> x;
SquareArray<float,4,3> x;

// A 4x4 array: will have 16 elements
// A 4x4x4 array: will have 64 elements

When the SquareArray template is instantiated, ctime pow is used to calculate the array
size required. Similar techniques can be used to find greatest common divisors, test for
primality, and so on. It is even possible to implement an interpreter for a subset of Lisp
which runs at compile time [4].

1.3

Code generation

It turns out that compile-time versions of flow control structures (loops, if/else, case
switches) can all be implemented in terms of templates. For example, the definition of
ctime pow (Section 1.2) emulates a for loop using tail recursion. These compile-time
programs can perform code generation by selectively inlining code as they are “interpreted”
by the compiler. This technique is called template metaprogramming [21]. Here is a template
metaprogram which generates a specialized dot product algorithm:
template<typename T, int I, int N>
struct meta dot {
static inline T f(T* a, T* b)
{ return meta dot<T,I-1,N>::f(a,b) + a[I]*b[I]; }
};
template<class T, int N>
struct meta dot<T,0,N> {
static inline T f(T* a, T* b)
{ return a[0]*b[0]; }
};
// Example use:
float x[3], y[3];
float z = meta dot<float,2,3>::f(x,y);

// **

In the above example, the call to meta dot in line marked ** results in code equivalent to:
float z = a[0]*b[0] + a[1]*b[1] + a[2]*b[2];

Head recursion is used to unroll the loop over the vector elements. The syntax for writing
such code generators is clumsy. However, the technique has proven very useful in producing
specialized algorithms for scientific computing [16, 23].

4
It is even possible to create and manipulate static data structures at compile time, by
encoding them as templates. This is the basis of the expression templates technique [20],
which creates parse trees of array expressions at compile time. These parse trees are used to
generate efficient evaluation routines for array expressions. This technique is the backbone
of several libraries for object-oriented numerics [13, 22].

1.4

Traits

The traits technique [14] allows programmers to define “functions” which operate on and
return types rather than data. As a motivating example, consider a generic function which
calculates the average value of an array. What should its return type be? If the array
contains integers, a floating-point result should be returned. But a floating-point return
type obviously will not suffice for a complex-valued array.
The solution is to define a traits class which maps from the type of the array elements
to a type suitable for containing their average. Here is a simple implementation:
template<typename T>
struct average traits {
typedef T T average;
};

// default behaviour: T -> T

template<>
struct average traits<int> {
typedef float T average; // specialization: int -> float
};

An appropriate type for averaging an array of type T is
average traits<T>::T average. Here is an implementation of average:

given

by

template<class T>
typename average traits<T>::T average average(T* array, int N)
{
typename average traits<T>::T average result = sum(array,N);
return result / N;
}

2

Templates as partial evaluation

Partial evaluators [12] regard a program’s data as containing two subsets: static data, which
is known at compile time, and dynamic data, which is not known until run time. A partial
evaluator evaluates as much of a program as possible (using the static data) and outputs a
specialized residual program.
To determine which portions of a program may be evaluated, a partial evaluator
performs binding time analysis to label language constructs and data as static or dynamic.
Such a labelled language is called a two-level language. For example, a binding-time analysis
of some scientific computing code might produce this two-level code fragment:
float volumeOfCube(float length)
{
return pow(length,3);
}

5
float pow(float x, int N)
{
float y = 1;
for (int i=0; i < N; ++i)
y *= x;
return y;
}

in which static constructs have been underlined. A partial evaluator such as CMix [1] would
evaluate the static constructs to produce the residual code:
float volumeOfCube(float length)
{
return pow3(length);
}
float pow3(float x)
{
float y = 1;
y *= x;
y *= x;
y *= x;
}

Such specializations can result in substantial performance improvements for scientific code
[2, 10].

2.1

C++ as a two-level language

C++ templates resemble a two-level language. Function templates take both template
parameters (which have static binding) and function arguments (which have dynamic
binding). For example, the pow function of the previous example might be declared in
C++ as:
template<int N>
float pow(float x);

// Calculate pow(x,N)

The static data (N) is a template parameter, and the dynamic data (x) is a function
argument. To incorporate template type parameters into this viewpoint, we need to regard
types as first-class values. For example, in a declaration such as
template<typename X, int Y>
void func(int i, int j);

we regard X as a piece of data whose value is a type. Since C++ is statically typed, type
variables may only have static binding.
It is useful to think of the type of X as being typename, which can be regarded as a type
whose possible values span all types. This point of view has a certain simplifying power:
for example, we can now view typedefs as assignments between typename variables. For
example,
typedef float float type;

can be regarded as equivalent to the (fictional syntax)
typename float type = float;

6

2.2

Template instantiation as offline PE

Partial evaluation of languages which contain binding-time information is called offline
partial evaluation. Template instantiation resembles offline partial evaluation: the compiler
takes template code (a two-level language) and evaluates those portions of the template
which involve template parameters (statically bound values). For example, consider this
template class:
template<int X>
struct foo {
static const int result = foo<(X % 2 == 0) ? (X/2) : (3*X+1)>::result;
};
// Base case: X = 1
template<>
struct foo<1> {
static const int result = 0;
};

When foo<X> is instantiated, the compiler must determine if X % 2 == 0 (i.e. whether X
is even). If true, it instantiates foo<X/2>; otherwise foo<3*X+1> is instantiated. In theory,
this continues until the compiler hits the base case X=1.1

3

A simpler syntax: Catat

We now present preliminary ideas for a single mechanism based on Partial Evaluation which
unifies generic programming, compile-time computation, and code generation. To illustrate
the ideas, we introduce a (currently hypothetical) language Catat. Catat is a multi-level
language based on C++ in which types are first-class values.

3.1

Binding time specifications

Each scope in a Catat program is associated with a default binding time. By default, the
global scope has dynamic binding. To indicate statically bound variables, an @ symbol is
appended to the type:
int i = 0;
int@ j = 0;

// Dynamic data
// Static data

The type int@ is equivalent to const int in C++.
To preserve consistency between the dynamic and static versions of the language, it is
necessary to allow multiple levels of binding (or stages). The @ symbol indicates that a
variable is bound in the previous stage.
The @ symbol may also be applied to control constructs:
// Calculate N! (factorial) at compile time
int@ N = 5, Nfact = 1;
for@ (int@ i=1; i < N; ++i)
Nfact *= i;
1

Whether this recursion terminates for all X is a well-known open problem. In C++, it is impossible to
determine if a chain of template instantiations will ever terminate. For this reason, compilers place limits
on the depth of template instantiation chains.

7
Operators such as = and * are applied at compile-time if their operands are statically
bound. Data may flow from static to dynamic constructs, but not vice-versa. This is called
cross-stage persistence by Taha and Sheard [18]. For example:
int@ i;
int j;
j = i;
i = j;

3.2

// Okay, i is known at runtime
// Not okay, j not known at ctime

Functions

Functions in Catat may take a mixture of static and dynamic arguments. We find
it convenient to give functions two separate parameters lists, as in C++. Here is an
implementation of the meta dot function described earlier:
function dot(int@ N, typename@ T)(T* a, T* b) {
T result = 0;
for@ (int@ i=0; i < N; ++i)
result += a[i]*b[i];
return result;
}

Note how much simpler this definition is than its template metaprogram counterpart
(Section 1.3).
The function dot may be thought of as a generating extension or higher-order function.
The concept is easier to express in a functional notation:
(define dot
(lambda (static-parms)
(PE static-parms
(lambda (dynamic-parms)
body))))

where (PE parms expr) performs partial evaluation of expr using static parameters parms.
The use of argument lists of the form (static-parms)(dynamic-parms) hints at this idea,
and also avoids the parsing difficulty associated with <> brackets in C++.
Catat discards the return type specification of C++ and replaces it with the keyword
function. The return type may result from compile-time calculations, and so must be
inferred from the body of the function. As in C++, we allow static parameters to be
inferred from dynamic argument types; for example, in the function average, T can be
inferred from the type of the array argument.
Functions may be evaluated at either compile-time or run-time. They are not fixed to
any stage. For example, given this definition of pow:
function pow(int X, int N) {
int result = 1;
for (int i = 0; i < N; ++i)
result *= X;
return result;
}

One can invoke pow at both run-time and compile-time:

8
int result1 = pow(2,3);
// Evaluated at run-time
int@ result2 = pow@(2,3); // Evaluated at compile-time

Functions can replace the use of traits classes in C++.
average traits (Section 1.4):

Here is a Catat version of

// Return a type appropriate for averaging an array of T
function average type(typename T) {
switch(T) {
case int:
return float;
case char:
return float;
case long int: return double;
// etc.
default:

return T;

}
}

This illustrates the usefulness of regarding types as first-class values. Here is the average
function, recoded in Catat:
function average(typename@ T)(T* array, int N) {
typename@ T_average = average type@(T);
// Sum the array, divide by N
T_average sum = 0;
for (int i=0; i < N; ++i)
sum += array[i];
return sum / N;
}

3.3

Specialization

When calls to function templates are encountered during C++ compilation, the template
is instantiated. In Catat a similar process would occur, which may be called specialization:
a partial evaluator produces a residual function by evaluating the static constructs. This
function call:
int data[10];
// ..
float result = average(int)(data,10);

triggers the partial evaluation of average; the resulting specialization (translated into
C++) might be
float average__int(int* array, int N) {
float sum = 0;
for (int i=0; i < N; ++i)
sum += array[i];
return sum;
}

3.4

Classes

Classes in Catat may take static parameters, and contain both static and dynamic data
members. For example:

9
1

5

10

15

20

class SquareArray(typename@ T numtype, int@ N length, int@ N dim) {
public:
SquareArray@()
{
// Calculate array size needed
if@ ((N dim < 1) || (N length < 1))
Catat error@("N dim and N length must be positive.");
else@
numElements = pow@(N length,N dim);
}
SquareArray()
{
// Initially set elements to zero
for (int i=0; i < numElements; ++i)
data[i] = 0;
}
private:
static int@ numElements;
T_numtype data[numElements];
}

In this class, there are two constructors: a compile-time constructor SquareArray@() and
a runtime constructor SquareArray(). The SquareArray@() constructor is invoked during
compilation when the class is specialized. At this time, it can check the static parameters
to ensure they are correct; if not, a compile-time error is issued. With the aid of some
reflection, this may be the right way to enforce constraints on template parameters (an
idea due to Vandevoorde [5]). The constructor SquareArray() is invoked at runtime when
instances of the class are created.
As with functions, classes have no specified binding time, but may be instantiated at
any stage. For example,
SquareArray@(int,3,2) x;
SquareArray(int,3,2) y;

3.5

// Array instantiated at compile-time
// Array instantiated at run-time

Thoughts on compiling Catat

To implement Catat as described, one apparently needs both a Catat-interpreter and a
Catat-compiler. For example, to compile a function f which has static parameters s and
dynamic parameters d, these steps would be needed:
1. Use the interpreter to partially evaluate f using the static parameters s:

[[interp]][f, s] = fs
2. Use the compiler to produce native code for the residual function fs :

[[compiler]]fs = fs⋆

10
where ⋆ indicates native code.2 This seems wasteful; there would be lots of duplicated effort
to create both an interpreter and compiler.
It may be possible to avoid this problem by using an approach similar to that pioneered
by the Cmix partial evaluation system [1]. The basic approach is to use a “closure compiler”
which uses run-time code generation (RTCG) to compile a single function. RTCG is a bit
of a misnomer, since the code generation is being done at compile-time by the compiler.
For example, to evaluate code such as
int@ result2 = pow@(2,3); // Evaluated at compile-time

One could use the closure compiler (CC) to compile pow to native code, and then execute
the function with the arguments (2, 3):
[[CC]]pow = pow⋆
[[pow⋆ ]][2, 3] = 8
To evaluate a two-level function such as f(s)(d), it must first be transformed into a singlelevel function. We suggest the term flattening for this transform. Flattening turns two-level
code into single-level code, by replacing dynamic code with static code that generates syntax
trees for the dynamic code. For example, the two-level function
float pow(int@ N)(float x)
{
float result = 1;
for@ (int@ i = 0; i < N; ++i)
result *= x;
return result;
}

would be transformed into something like:
ASTree powgen(int N)
{
ASTree func = make_lambda(...);
ASTree x = make_varref("x");
func.body().append(make_vardecl(float, "result", 1));
ASTree result = make_varref("result");
for (int i=0; i < N; ++i)
func.body().append(make_op("*=", result, x));
func.body().append(make_return(result));
return fn;
}

With the aid of this flattening transformation, two-level functions can be compiled without
an interpreter:
2

The [[·]] notation is from partial evaluation: if pow is a function, then [[pow]][input] is the result of
executing pow with input. For example, [[pow]][3, 2] = 9.

11

−−−−−→
f (s)(d) f latten fgen (s)
[[CC]]fgen

=

⋆
fgen

⋆
[[fgen
]]s

=

fs

[[CC]]fs

=

fs⋆

i.e. first the flattening transform is used to turn f (s)(d) into a single-level generator for f ,
⋆ . The native-code
called fgen . This generator is compiled using CC into native code fgen
version is then executed with the static parameters s, and produces the specialized version
fs . This function is then compiled using CC.
The availability of fast, portable run-time code generation systems such as vcode [6]
makes this approach to compilation possible.

3.6

Interesting possibilities

Languages with Catat-like abilities raise some interesting possibilities:
3.6.1 Scripting The partial evaluator for Catat needs to contain what is essentially
an interpreter to evaluate the static portions of the program. This implies that you get
scripting for no extra cost; a Catat program consisting solely of static constructs will be
completely interpreted, with no residual code generated. With a little bit of extra work, it
ought to be possible to dynamically link to already-compiled Catat programs; this would
make it possible to “steer” applications using a natural scripting interface.
3.6.2 Futamura projection Suppose we wrote an interpreter for a domain-specific
language (DSL) in Catat. We could design our interpreter to take the input text as a static
parameter, and input variables as dynamic parameters. Residualization of the interpreter
would result in the DSL code being compiled into the dynamic subset of Catat, via the
first Futamura projection [8]. This approach would allow users to incorporate fragments of
domain-specific languages into their applications, without sacrificing efficiency.
3.6.3 Reflection and Meta-level Processing A language like Catat may provide
a natural environment for implementing reflection and meta-level processing capabilities,
since the ability to perform compile-time calculations is there already. Such capabilities
would allow programmers to query objects about their methods and members, determine
the parameter types of functions, and perhaps even manipulate and generate abstract
syntax trees.

4

Related Work

Nielson and Nielson [15] first investigated two-level languages and showed that bindingtime analysis can be expressed as a form of type checking. The most closely related work
is MetaML, a statically typed multi-level language for hand-writing code generators [18].
MetaML does not appear to address the issue of generic programming. Glück and Jørgensen
described a program generator for multi-level specialization [9] which uses a multi-level
functional language to represent automatically produced program generators.
Metalevel processing systems address many of the same problems as Catat; they
give library writers the ability to directly manipulate abstract syntax trees at compile
time. Relevant examples are Xroma [5], MPC++ [11], Open C++ [3], and Magik [7].
These systems are not phrased in terms of partial evaluation or two-level languages; code

12
generation is generally done by constructing abstract syntax trees. A more closely related
system is Catacomb [17], which provides a two-level language for generating runtime library
code for parallelizing compilers. However, it does not address issues of generic programming.
The idea of types as first-class values originates in polymorphic or second order typed
lambda calculus, and languages based on it.

5

Conclusions

We have shown that C++ with templates may be regarded as a two-level language in
which types are first-class values with static binding, and that template instantiation bears
a striking resemblance to offline partial evaluation. Languages built on this insight may offer
a way to provide generic programming, code generation, and compile-time computation via
a single mechanism with simple syntax.

6

Acknowledgments

This work was supported in part by NSF grants CDA-9601632 and CCR-9527130. We are
grateful to Robert Glück for pointing out relevant work in Partial Evaluation.

References
[1] L. O. Andersen, Program Analysis and Specialization for the C Programming Language, PhD
thesis, DIKU, University of Copenhagen, May 1994. (DIKU report 94/19).
[2] A. Berlin and D. Weise, Compiling scientific code using partial evaluation, Computer, 23 (1990),
pp. 25–37.
[3] S. Chiba, A Metaobject Protocol for C++, in OOPSLA’95, 1995, pp. 285–299.
[4] K. Czarnecki and U. Eisenecker, Meta-control structures for template metaprogramming.
http://home.t-online.de/home/Ulrich.Eisenecker/meta.htm.
[5] K. Czarnecki, U. Eisenecker, R. Glück, D. Vandevoorde, and T. L. Veldhuizen, Generative
Programming and Active Libraries, in Proceedings of the 1998 Dagstuhl-Seminar on Generic
Programming, vol. TBA of Lecture Notes in Computer Science, 1998. (in review).
[6] D. R. Engler, VCODE : A retargetable, extensible, very fast dynamic code generation system,
in Proceedings of the ACM SIGPLAN Conference on Programming Language Design and
Implemantation, New York, May 21–24 1996, ACM Press, pp. 160–170.
, Incorporating application semantics and control into compilation, in USENIX Conference
[7]
on Domain-Specific Languages (DSL’97), October 15–17, 1997.
[8] Y. Futamura, Partial evaluation of computation process - an approach to a compiler-compiler,
Systems, Computers, Controls, 2 (1971), pp. 45–50.
[9] R. Glück and J. Jørgensen, An automatic program generator for multi-level specialization, Lisp
and Symbolic Computation, 10 (1997), pp. 113–158.
[10] R. Glück, R. Nakashige, and R. Zöchling, Binding-time analysis applied to mathematical
algorithms, in System Modelling and Optimization, J. Doležal and J. Fidler, eds., Chapman &
Hall, 1995, pp. 137–146.
[11] Y. Ishikawa, A. Hori, M. Sato, M. Matsuda, J. Nolte, H. Tezuka, H. Konaka, M. Maeda, and
K. Kubota, Design and implementation of metalevel architecture in C++ – MPC++ approach,
in Reflection’96, 1996.
[12] N. D. Jones, An introduction to partial evaluation, ACM Computing Surveys, 28 (1996),
pp. 480–503.
[13] S. Karmesin, J. Crotinger, J. Cummings, S. Haney, W. Humphrey, J. Reynders, S. Smith, and
T. Williams, Array design and expression evaluation in POOMA II, in ISCOPE’98, vol. 1505,
Springer-Verlag, 1998. Lecture Notes in Computer Science.
[14] N. Myers, A new and useful template technique: “Traits”, C++ Report, 7 (1995), pp. 32–35.

13
[15] F. Nielson and H. R. Neilson, Two-Level Functional Languages, Cambridge University Press,
Cambridge, Mass., 1992.
[16] J. G. Siek and A. Lumsdaine, The Matrix Template Library: A generic programming approach
to high performance numerical linear algebra, in International Symposium on Computing in
Object-Oriented Parallel Environments, 1998.
[17] J. Stichnoth and T. Gross, Code composition as an implementation language for compilers, in
USENIX Conference on Domain-Specific Languages, 1997.
[18] W. Taha and T. Sheard, Multi-stage programming with explicit annotations, ACM SIGPLAN
Notices, 32 (1997), pp. 203–217.
[19] E. Unruh, Prime number computation, 1994. ANSI X3J16-94-0075/ISO WG21-462.
[20] T. L. Veldhuizen, Expression templates, C++ Report, 7 (1995), pp. 26–31. Reprinted in C++
Gems, ed. Stanley Lippman.
[21]
, Using C++ template metaprograms, C++ Report, 7 (1995), pp. 36–43. Reprinted in
C++ Gems, ed. Stanley Lippman.
[22]
, Arrays in Blitz++, in ISCOPE’98, vol. 1505 of Lecture Notes in Computer Science,
1998.
[23] T. L. Veldhuizen and K. Ponnambalam, Linear algebra with C++ template metaprograms, Dr.
Dobb’s Journal of Software Tools, 21 (1996), pp. 38–44.

