Compile time function execution

Compile-time function execution (or compile time function evaluation, or general constant expressions) is the ability of a compiler, that would normally compile a function to machine code and execute it at run time, to execute the function at compile time. This is possible if the arguments to the function are known at compile time, and the function does not make any reference to or attempt to modify any global state (is a pure function).

If the value of only some of the arguments are known, the compiler may still be able to perform some level of compile-time function execution (partial evaluation), possibly producing more optimized code than if no arguments were known.

Examples

The Lisp macro system is an early example of the use of compile-time evaluation of user-defined functions in the same language.

The Metacode extension to C++ (Vandevoorde 2003)[1] was an early experimental system to allow compile-time function evaluation (CTFE) and code injection as an improved syntax for C++ template metaprogramming.

In earlier versions of C++, template metaprogramming is often used to compute values at compile time, such as:

template <int N>
struct Factorial {
  enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> {
  enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void Foo() {
  int x = Factorial<0>::value;  // == 1
  int y = Factorial<4>::value;  // == 24
}

Using compile-time function evaluation, code used to compute the factorial would be similar to what one would write for run-time evaluation e.g. using C++11 constexpr.

#include <cstdio>

constexpr int Factorial(int n) { return n ? (n * Factorial(n - 1)) : 1; }

constexpr int f10 = Factorial(10);

int main() {
  printf("%d\n", f10);
  return 0;
}

In C++11, this technique is known as generalized constant expressions (constexpr).[2] C++14 relaxes the constraints on constexpr – allowing local declarations and use of conditionals and loops (the general restriction that all data required for the execution be available at compile-time remains).

Here's an example of compile time function evaluation in C++14:

// Iterative factorial at compile time.
constexpr int Factorial(int n) {
  int result = 1;
  while (n > 1) {
    result *= n--;
  }
  return result;
}

int main() {
  constexpr int f4 = Factorial(4);  // f4 == 24
}

Here's an example of compile time function evaluation in the D programming language:[3]

int factorial(int n) {
    if (n == 0)
       return 1;
    return n * factorial(n - 1);
}

// computed at compile time
enum y = factorial(0); // == 1
enum x = factorial(4); // == 24

This example specifies a valid D function called "factorial" which would typically be evaluated at run time. The use of enum tells the compiler that the initializer for the variables must be computed at compile time. Note that the arguments to the function must be able to be resolved at compile time as well.[4]

CTFE can be used to populate data structures at compile-time in a simple way (D version 2):

int[] genFactorials(int n) {
    auto result = new int[n];
    result[0] = 1;
    foreach (i; 1 .. n)
        result[i] = result[i - 1] * i;
    return result;
}

enum factorials = genFactorials(13);

void main() {}

// 'factorials' contains at compile-time:
// [1, 1, 2, 6, 24, 120, 720, 5_040, 40_320, 362_880, 3_628_800,
//  39_916_800, 479_001_600]

CTFE can be used to generate strings which are then parsed and compiled as D code in D.

References

1. Daveed Vandevoorde, Edison Design Group (April 18, 2003). "Reflective Metaprogramming in C++" (PDF). Retrieved July 19, 2015.
2. Gabriel Dos Reis and Bjarne Stroustrup (March 2010). "General Constant Expressions for System Programming Languages. SAC-2010. The 25th ACM Symposium On Applied Computing" (PDF).
3. D 2.0 language specification: Functions
4. D 2.0 language specification: Attributes

External links

• Rosettacode examples of compile-time function evaluation in various languages