\documentclass[final]{beatcs}

\usepackage{verbatim}

\DeclareFontFamily{U}{eur}{\skewchar\font'177}
  \DeclareFontShape{U}{eur}{m}{n}{%
    <-6> eurm5 <6-8> eurm7 <8-> eurm10}{}
  \DeclareFontShape{U}{eur}{b}{n}{%
    <-6> eurb5 <6-8> eurb7 <8-> eurb10}{}
  \DeclareSymbolFont{ugrf@m}{U}{eur}{m}{n}
  \SetSymbolFont{ugrf@m}{bold}{U}{eur}{b}{n}
  \DeclareMathSymbol{\minop}{\mathord}{ugrf@m}{"16}

\newcommand{\cppid}[1]{\texttt{#1}}
\newenvironment{cppsrc}{\begingroup \small \selectfont \verbatim}
{\endverbatim \endgroup}

\title{The Computational Power of Compiling C++}

\author{Martin B\"ohme\thanks{Universit\"at zu L\"ubeck,
  \url{
 This e-mail address is being protected from spambots. You need JavaScript enabled to view it
 }.\;
   $^\dagger$Universit\"at zu L\"ubeck, Institut f\"ur Theoretische Informatik,
 \url{
 This e-mail address is being protected from spambots. You need JavaScript enabled to view it
 }.
}
\and Bodo Manthey$^\dagger$
%\thanks{\mbox{Universit\"at zu L\"ubeck, Institut f\"ur Theoretische Informatik,}
%\texttt{
 This e-mail address is being protected from spambots. You need JavaScript enabled to view it
 }}
}

\date{}

\begin{document}
\maketitle


\begin{abstract}
Using a C++ compiler, any partial recursive function can be computed \emph{at
compile time}. We show this by using the C++ template mechanism to define 
functions via primitive recursion, composition, and $\minop$-recursion.
\end{abstract}

\section{Introduction}
Any partial recursive function can be computed using the programming language
C++. But what about the computational power of C++ compilers? Are there any 
functions that can be computed just by compiling C++ source code instead
of executing a C++ program after compilation? 
The answer is surprising: Any partial recursive
function can be computed by running a C++ compiler.
We show this by presenting a way to specify 
primitive recursion, composition, and 
$\minop$-recursion~\cite{Smith:Recursive:1994} by (ab)using the C++ template
mechanism and type system~\cite{Stroustrup:CPP:1997}.
Our strategy for obtaining the output is to provide an error message that
contains the result in unary representation.
When we run the C++ compiler, after specifying a partial recursive 
function $f$ and a natural number $x$ as C++ source code, 
the error message typed out by the compiler will be $f(x)$.
We make the reasonable assumption that the compiler outputs helpful error
messages that give the names of the types involved in a type conflict, for
example.
However, even if the only error message that is produced by the compiler 
is ``error'', we show that the compiler still has to compute $f(x)$ internally.

The idea of using the C++ template mechanism for computations at compile time
goes back to
Unruh. He developed a program that printed out prime
numbers
at compile time~\cite{Unruh:Prime}, 
and stated that any partial recursive function could be 
computed in this way~\cite{Unruh:WWW:2002}.
As far as we are aware, though, he has never published a proof.
Veldhuizen~\cite{Veldhuizen:TemplateMeta:1995} picked up the idea and 
applied it
to improve the speed of C++ programs. 
He considers C++ to be a two-level language: 
static computations performed at compile time and dynamic computations
performed at run time~\cite{Veldhuizen:Partial:1999}. 
Splitting the computation up in such a way is called 
``partial evaluation'' or ``program
specialization'' (see e.g.\ Jones~\cite{Jones:Partial:1996}
or Stroustrup~\cite[Sec.~13.5]{Stroustrup:CPP:1997}), and today this technique
is widely used in template libraries.

\section{Defining Functions Using C++ Templates}

We now present the mechanism by which we compute partial recursive functions
using the template mechanism.
To represent numbers, we choose not to use the built-in integer type
\cppid{int}; instead, we use types constructed recursively using the C++
template mechanism, which in theory allows us to represent arbitrarily large
numbers. 
We will call a C++ type that represents a natural number a
\emph{number type}.

To make this concrete,

\begin{cppsrc}
struct zero { };
\end{cppsrc}

\noindent is the number type that represents the number zero, and, given a
number type \cppid{T},

\begin{cppsrc}
template<class T> struct suc
{
   typedef T pre;
};
\end{cppsrc}

\noindent represents the successor of that number. For example,
\cppid{suc<suc<zero>~>} represents the number 2. The \cppid{pre} typedef
can be used to obtain the predecessor. Thus, for any number type
\cppid{T} that is not \cppid{zero}, \cppid{T::pre} represents the predecessor
of that number.
(For brevity, we will use \cppid{struct} instead 
of \cppid{class} throughout this
work; both are equivalent except that the default access for 
\cppid{struct} is \cppid{public} whereas for \cppid{class} it is 
\cppid{private}.)

A function is represented as a C++ class that contains a typedef
called \cppid{val}. This typedef is equal to the number type of the
result. The arguments of the function are represented as template arguments.
We will refer to classes that represent functions in this way as
\emph{function types}. For example,

\begin{cppsrc}
template<class T> struct plus2
{
   typedef suc<suc<T> > val;
};
\end{cppsrc}

\noindent is a function type that computes the function $f(x)=x+2$. 
If we want to compute $f(1)$, we add 
\begin{cppsrc}
int main()
{
   plus2<suc<zero > >::val tmp;
   return (int) tmp;
}
\end{cppsrc}

\noindent as the main program.
Due to the illegal type cast \cppid{(int) tmp;} the compiler will type out 
the error message
\begin{cppsrc}
`struct suc<suc<suc<zero> > >' used where a `int' was expected
\end{cppsrc}

\noindent and thus we obtain the result $f(1)=3$.

To show that any partial recursive function can be 
computed in this way, we need to be able to express 
the base functions as well as primitive recursion, 
composition and $\minop$-recursion.
We quickly review their definitions (see e.g.\ 
Smith~\cite{Smith:Recursive:1994}).

{\small
\begin{description}
\item[Base Functions:] The zero function $Z$ with
$Z(x) = 0$, the successor function $S$ with
$S(x) = x+1$ and the projection functions $U_j^n$ ($1 \leq j \leq n$)
with $U_j^n(x_1, \ldots , x_n) = x_j$ are primitive recursive.
\item[Primitive Recursion:] Let $g$ and $h$ be primitive recursive functions 
of arity $n$ and $n+2$, respectively. Then the function $f$ with
%
\[\begin{array}{lcl}
f(x_1, \ldots, x_n, 0) & = & g(x_1, \ldots, x_n) \: \mbox{ and}\\
f(x_1, \ldots, x_n, y+1) & = & h(x_1, \ldots, x_n, y, f(x_1, \ldots, x_n, y))
\end{array}
\]
is also primitive recursive.
\item[Composition:] Let $g_1$, $\ldots$, $g_m$ be primitive recursive 
functions, 
each of arity $n$, and
$h$ be a primitive recursive function of arity $m$. Then the function $f$ with
%
\[\begin{array}{lcl}
f(x_1, \ldots, x_n)&=&
h(g_1(x_1, \ldots, x_n), \ldots, g_m(x_1, \ldots, x_n))\: .
\end{array}
\]
%
is also primitive recursive.
\item[\boldmath $\minop$-Recursion:]
Let $h$ be a (partial) function of arity $n+1$. 
A function $f$ of arity $n$ is defined by $\minop$-recursion
from $h$ if 
\[
f(x_1, \ldots, x_n) = \minop \,  y[h(x_1, \ldots, x_n, y) = 0] \: ,
\] 
where $\minop\,  y[h(x_1, \ldots, x_n, y) = 0] = z$ 
if
\begin{list}{--}{\setlength{\itemsep}{0mm} \setlength{\topsep}{0mm}
                 }
\item 
$h(x_1, \ldots, x_n, z)=0$ and
\item 
for all $y'<z$, $h(x_1, \ldots, x_n, y')$ is defined and
$h(x_1, \ldots, x_n, y') \neq 0$.
\end{list}
If no such $z$ exists, $\minop \,  y[h(x_1, \ldots, x_n, y) = 0]$ 
is undefined.
\end{description}
}

We first demonstrate that 
primitive recursion 
can be expressed. We
demonstrate this only for the case 
where 
$f$ is a binary function,
but the
extension to the general case is 
easy. 
Therefore, let 
$g$ and $h$ 
be unary
and ternary primitive recursive functions, respectively, and let \cppid{G} and
\cppid{H} be function types that compute $g$ and $h$. Then the following
function type \cppid{F} computes the function $f$ as defined by primitive
recursion from $g$ and $h$.

\begin{cppsrc}
template<class X, class Y> struct F;

template<class X> struct F<X, zero>
{
   typedef typename G<X>::val val;
};

template<class X, class Y> struct F
{
   typedef typename H
   <
      X, typename Y::pre, typename F<X, typename Y::pre>::val
   >::val val;
};
\end{cppsrc}

We omit a demonstration of how the base functions and 
composition can be expressed since the base functions are fairly easy
and composition merely involves assembling the various function types.

With the base functions, primitive recursion and composition,
any primitive recursive function can be expressed
as a function type.
We will now show that $\minop$-recursion
can be expressed, thus allowing us to compute any partial 
recursive function, since
any partial recursive function can be 
expressed with a single $\minop$-operator acting
on a primitive recursive function.

In our demonstration of how to express the $\minop$-operator, we again 
restrict ourselves to unary functions, but again, generalization is 
easy. Let $f$ be
a unary partial recursive function, let $h$ be a binary primitive recursive
function such that
$f(x) = \minop\, y [h(x,y)=0]$, and
let \cppid{H} be a function type that computes $h$. 
The idea for computing $\minop\, y [h(x,y)=0]$ using the template mechanism is 
to construct a function
\[
\mathrm{mu}(h,x,y,p) = \left\{
\begin{array}{ll}
y-1 & \mbox{ if $p=0$ and} \\
\mathrm{mu}(h,x,y+1,h(x,y)) & \mbox{ otherwise.} 
\end{array} \right.
\]
We have $f(x) = \minop\, y [h(x,y)=0] = \mathrm{mu}(h,x,0,1)$. The way this
works is that we always have $p=h(x,y-1)$ (except for $y=0$), and so when $p$
is zero for the first time we return $y-1$ as the result. If $h(x,y) \neq 0$
for all $y$ then the recursion never terminates, and so $\mathrm{mu}(h,x,0,1)$
is undefined.

We now define a class \cppid{Mu<H, X, Y, HprY>} that computes $\mathrm{mu}$.

\begin{cppsrc}
template<template<class A,class B> class H, 
         class X, class Y, class HprY> struct Mu;

template<template<class A,class B> class H, 
         class X, class Y> struct Mu<H,X,Y,zero>
{
   typedef typename Y::pre min;
};

template<template<class A,class B> class H, 
         class X, class Y, class HprY> struct Mu
{
   typedef typename Mu<
      H, X, suc<Y>, typename H<X,Y>::val>::min min;
};
\end{cppsrc}

This is a straightforward implementation of the definition of
$\mathrm{mu}$. Template specialization is used to select the first definition
of $\cppid{Mu}$ when $\cppid{HprY}\equiv\cppid{zero}$, and the second
definition otherwise.

This means that 
if $f(x)=\minop\, y[h(x, y) = 0]=\mathrm{mu}(h,x,0,1)$ is defined,
\cppid{Mu<H, X, zero, suc<zero>~>::min} is the
number type that represents $f(x)$. If 
$f(x)$ is
undefined, the type \cppid{Mu<H, X, zero, suc<zero>~>::min} is likewise
undefined; specifically, it is an infinite nesting of template instantiations,
which will cause the compiler to go into an infinite loop (or hit an internal
limit on the template instantiation depth).


\section{Concluding Remarks}

We have seen how to compute any partial recursive function $f$
using the C++ template mechanism and type system, outputting the result as an
error message from the compiler.
But what happens if the compiler does not print out any (helpful) error 
messages?

In this case, the compiler still has to compute the value
$f(x)$ internally. Suppose
that \cppid{suc<T>} is given the member variables 
\cppid{T dummy1} and \cppid{int dummy2}. This means that we have
\cppid{sizeof(suc<T>)} $>$ \cppid{sizeof(T)}, because \cppid{suc<T>} contains
an object of type \cppid{T} as well as an additional 
integer.\footnote{Strictly speaking, for machines with very restrictive 
alignment rules, it is conceivable that one additional integer variable would 
not necessarily increase the size of the type (because of structure packing).
In this case, we could use more than one dummy integer to make sure we always 
have \cppid{sizeof(suc<T>)} $>$ \cppid{sizeof(T)}.}
Thus, the function that maps a natural number $n$ to the size of the number
type representing $n$ is injective. If, in our program, we instantiate (create
a variable of) the
number type representing $f(x)$, the compiler has to work out its size and
thus compute $f(x)$. We note that it should be possible to devise a
(compiler-dependent) scheme for extracting $f(x)$ from the executable
generated by the compiler, but we will not go into the technicalities of how 
such a scheme might work.

The way in which we have specified functions 
is quite similar to the pattern matching used in functional 
programming languages. 
Consider for example our implementation of primitive recursion. First we try
to match the template arguments with \cppid{F<X,zero>} (with arbitrary 
\cppid X). 
If this fails, we try 
to match them with \cppid{F<X, Y>} (which should be successful).
In the latter case we know that $\cppid Y \not\equiv \cppid{zero}$, so we can
safely use \cppid{Y::pre}.

It is surely interesting to find other programming languages for which
com\-pile-time computations are possible.
Veldhuizen~\cite{Veldhuizen:Safe:2001} presented an experimental compiler for
Java that performs partial evaluation to improve the performance of numerical
code. The worst-case running time of this compiler is quadratic.

As we have seen, C++ allows arbitrary computations at compile time. This is
something of a dilemma. We want the power to perform complex program
manipulations at compile time, but we would also like to have a guaranteed
time bound for the compiler. On the other hand, it could be argued that, since
we are completely responsible for the \emph{run-time} complexity of our
programs, we should simply get used to being responsible for the
\emph{compile-time} complexity, too.

\begin{thebibliography}{1}

\bibitem{Jones:Partial:1996}
Neil~D. Jones.
\newblock An Introduction to Partial Evaluation.
\newblock {\em ACM Computing Surveys}, 28(3):480--503, 1996.

\bibitem{Smith:Recursive:1994}
Carl~H. Smith.
\newblock {\em A Recursive Introduction to the Theory of Computation}.
\newblock Springer, 1994.

\bibitem{Stroustrup:CPP:1997}
Bjarne Stroustrup.
\newblock {\em The {C++} Programming Language}.
\newblock Addison-Wesley, 1997.

\bibitem{Unruh:Prime}
Erwin Unruh.
\newblock Prime number computation.
\newblock ANSI X3J16-94-0075/ISO WG21-462, 1994.

\bibitem{Unruh:WWW:2002}
Erwin Unruh.
\newblock Template Metaprogrammierung, 2002.
\newblock URL: http://www.erwin-unruh.de/meta.html (in German).

\bibitem{Veldhuizen:TemplateMeta:1995}
Todd~L. Veldhuizen.
\newblock Using {C++} template metaprograms.
\newblock {\em C++ Report}, 7(4):36--43, 1995.

\bibitem{Veldhuizen:Partial:1999}
Todd~L. Veldhuizen.
\newblock C++ Templates as Partial Evaluation.
\newblock In 
{\em Proc. of the ACM SIGPLAN Workshop on Partial Evaluation and
  Semantics-Based Program Manipulation (PEPM)}, Technical report BRICS NS-99-1,
  University of Aarhus, pages 13--18, 1999.

\bibitem{Veldhuizen:Safe:2001}
Todd~L. Veldhuizen.
\newblock Just when you thought your little language was safe: ``Expression
  Templates'' in {J}ava.
\newblock In 
{\em Proc. of the 2nd Symp. Generative and Component-Based
  Software Engineering (GCSE)}, volume 2177 of {\em Lecture Notes in Comput.
  Sci.}, pages 188--200. Springer, 2001.

\end{thebibliography}
\end{document}

e-max.it: your social media marketing partner
 
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.