Compile-time function execution

<h2 id="examples">Examples</h2>
<h3>Lisp</h3>
<p>The <a href="/facts/Macro_(computer_science)/7abAsm1o">Lisp macro system</a> is an early example of the use of compile-time evaluation of user-defined functions in the same language.
</p>
<h3>C++</h3>
<p>The Metacode extension to C++ (Vandevoorde 2003)<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> was an early experimental system to allow compile-time function evaluation (CTFE) and code injection as an improved syntax for C++ <a href="/facts/Template_metaprogramming/yybwJ7AN">template metaprogramming</a>.
</p><p>In earlier versions of <a href="/facts/C%2B%2B/Et0F2qn9">C++</a>, <a href="/facts/Template_metaprogramming/yybwJ7AN">template metaprogramming</a> is often used to compute values at compile time, such as:
</p>
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
}

<p>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.
</p>
#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;
}

<p>In <a href="/facts/C%2B%2B11/fI3YCoKQ">C++11</a>, this technique is known as <a href="/facts/C%2B%2B11/fI3YCoKQ">generalized constant expressions</a> (constexpr).<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> <a href="/facts/C%2B%2B14/CXukL6pA">C++14</a> <a href="/facts/C%2B%2B14/CXukL6pA">relaxes the constraints</a> 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).
</p><p>Here's an example of compile-time function evaluation in C++14:
</p>
// 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
}

<h3>Immediate functions (C++)</h3>
<p>In <a href="/facts/C%2B%2B20/hwpB1Vzp">C++20</a>, immediate functions were introduced, and compile-time function execution was made more accessible and flexible with relaxed constexpr restrictions.
</p>
// Iterative factorial at compile time.
consteval int Factorial(int n) {
  int result = 1;
  while (n > 1) {
    result *= n--;
  }
  return result;
}

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

<p>Since function Factorial is marked consteval, it is guaranteed to invoke at compile-time without being forced in another manifestly constant-evaluated context. Hence, the usage of immediate functions offers wide uses in metaprogramming, and compile-time checking (used in C++20 text formatting library).
</p><p>Here's an example of using immediate functions in compile-time function execution:
</p>
void you_see_this_error_because_assertion_fails() {}

consteval void cassert(bool b) {
  if (!b)
    you_see_this_error_because_assertion_fails();
}

consteval void test() {
  int x = 10;
  cassert(x == 10); // ok
  x++;
  cassert(x == 11); // ok
  x--;
  cassert(x == 12); // fails here
}

int main() { test(); }

<p>In this example, the compilation fails because the immediate function invoked function which is not usable in constant expressions. In other words, the compilation stops after failed assertion. 
</p><p>The typical compilation error message would display:
</p>
In function 'int main()':
  in 'constexpr' expansion of 'test()'
  in 'constexpr' expansion of 'cassert(x == 12)'
error: call to non-'constexpr' function 'you_see_this_error_because_assertion_fails()'
              you_see_this_error_because_assertion_fails();
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
  [ ... ]

<p>Here's another example of using immediate functions as constructors which enables compile-time argument checking:
</p>
#include <string_view>
#include <iostream>

void you_see_this_error_because_the_message_ends_with_exclamation_point() {}

struct checked_message {
    std::string_view msg;

consteval checked_message(const char* arg)
    : msg(arg) {
        if (msg.ends_with('!'))
            you_see_this_error_because_the_message_ends_with_exclamation_point();
    }
};

void send_calm_message(checked_message arg) {
    std::cout << arg.msg << '\n';
}

int main() {
    send_calm_message("Hello, world");
    send_calm_message("Hello, world!");
}

<p>The compilation fails here with the message:
</p>
In function 'int main()':
  in 'constexpr' expansion of 'checked_message(((const char*)"Hello, world!"))'
error: call to non-'constexpr' function 'void you_see_this_error_because_the_message_ends_with_exclamation_point()'
                    you_see_this_error_because_the_message_ends_with_exclamation_point();
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
 [ ... ]

<h3>D</h3>
<p>Here's an example of compile-time function evaluation in the <a href="/facts/D_programming_language/4qIzRjkF">D programming language</a>:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
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

<p>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.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p><p>CTFE can be used to populate data structures at compile-time in a simple way (D version 2):
</p>
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]

<p>CTFE can be used to generate strings which are then parsed and compiled as D code in D.
</p>
<h3>Zig</h3>
<p>Here's an example of compile-time function evaluation in the <a href="/facts/Zig_programming_language/nKAt49pj">Zig programming language</a>:<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
pub fn factorial(n: usize) usize {
    var result = 1;
    for (1..(n + 1)) |i| {
        result *= i;
    }
    return result;
}

pub fn main() void {
    const x = comptime factorial(0); // == 0
    const y = comptime factorial(4); // == 24
}

<p>This example specifies a valid Zig function called "factorial" which would typically be evaluated at run time. The use of comptime 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.
</p><p>Zig also support Compile-Time Parameters.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p>
pub fn factorial(comptime n: usize) usize {
    var result: usize = 1;
    for (1..(n + 1)) |i| {
        result *= i;
    }
    return result;
}

pub fn main() void {
    const x = factorial(0); // == 0
    const y = factorial(4); // == 24
}

<p>CTFE can be used to create generic data structures at compile-time:
</p>
fn List(comptime T: type) type {
    return struct {
        items: []T,
        len: usize,
    };
}

// The generic List data structure can be instantiated by passing in a type:
var buffer: [10]i32 = undefined;
var list = List(i32){
    .items = &buffer,
    .len = 0,
};

<h2 id="external-links">External links</h2>
<ul><li><a href="http://rosettacode.org/wiki/Compile-time_calculation">Rosettacode examples of compile-time function evaluation in various languages</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Daveed Vandevoorde, Edison Design Group (April 18, 2003). "Reflective Metaprogramming in C++" (PDF). Retrieved July 19, 2015. <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1471.pdf" target="_blank">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1471.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>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). <a href="http://www.stroustrup.com/sac10-constexpr.pdf" target="_blank">http://www.stroustrup.com/sac10-constexpr.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>D 2.0 language specification: Functions <a href="http://d-programming-language.org/function.html#interpretation" target="_blank">http://d-programming-language.org/function.html#interpretation</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>D 2.0 language specification: Attributes <a href="http://d-programming-language.org/attribute.html#const" target="_blank">http://d-programming-language.org/attribute.html#const</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Zig 0.11.0 Language Reference: Compile-Time Expressions <a href="https://ziglang.org/documentation/0.11.0/#Compile-Time-Expressions" target="_blank">https://ziglang.org/documentation/0.11.0/#Compile-Time-Expressions</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Zig 0.11.0 Language Reference: Compile-Time Parameters <a href="https://ziglang.org/documentation/0.11.0/#Compile-Time-Parameters" target="_blank">https://ziglang.org/documentation/0.11.0/#Compile-Time-Parameters</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Compile-time function execution open-in-new

Compile-time function execution