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

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.
1-60132-066-3
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11586/136666
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact