C++ templates were designed to provide generic programming, but they are also capable of performing static computation. It is known that any partial recursive function can be computed at compile time, using the C++ templates to define primitive recursion, composition, and minimalization. It is also known that polynomial-time com putable functions can be computed statically, using the same mechanism together with a fine tuning of template specialization. In this paper, we define a subset of C++ based on templates and we prove that it characterizes the polytime functions; compared with the previous ones, our language captures more algorithms using a restricted version of the course-of-value recursion.
Extending C++ static computation of polynomial-time algorithms
PANI, Giovanni;COVINO, Emanuele;
2008-01-01
Abstract
C++ templates were designed to provide generic programming, but they are also capable of performing static computation. It is known that any partial recursive function can be computed at compile time, using the C++ templates to define primitive recursion, composition, and minimalization. It is also known that polynomial-time com putable functions can be computed statically, using the same mechanism together with a fine tuning of template specialization. In this paper, we define a subset of C++ based on templates and we prove that it characterizes the polytime functions; compared with the previous ones, our language captures more algorithms using a restricted version of the course-of-value recursion.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
