Compile-time function execution: Difference between revisions

Revision as of 20:43, 21 December 2011

Latest revision as of 23:44, 17 January 2025

(42 intermediate revisions by 29 users not shown)

Line 1:

{{Short description|A compiler's ability to execute a function at compile time rather than runtime}}

'''Compile time function execution''' (or '''compile-time function evaluation''', '''CTFE''') is the ability of a [[compiler]], that would normally compile a function to machine code and execute it at [[Run time (program lifecycle phase)|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]]).

In [[computing]], '''compile-time function execution''' (or '''compile-time function evaluation''', or '''general constant expressions''') is the ability of a [[compiler]], that would normally compile a [[Subroutine|function]] to [[machine code]] and [[Execution (computing)|execute]] it at [[run time (program lifecycle phase)|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 (i.e. it is a [[pure function]]).

Even 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.

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.

==Example==

==Examples==

In [[C++]], [[template metaprogramming]] is often used to compute values at compile time, such as:

===Lisp===

The [[Macro_(computer_science)#Syntactic_macros|Lisp macro system]] is an early example of the use of compile-time evaluation of user-defined functions in the same language.

===C++===

<source lang="CPP">

The Metacode extension to C++ (Vandevoorde 2003)<ref>{{cite web|url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1471.pdf|title=Reflective Metaprogramming in C++|author=Daveed Vandevoorde, Edison Design Group|date=April 18, 2003|accessdate=July 19, 2015}}</ref> was an early experimental system to allow compile-time function evaluation (CTFE) and code injection as an improved syntax for C++ [[template metaprogramming]].

template <int N> struct Factorial {

enum {

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

value = N * Factorial<N - 1>::value

};

<syntaxhighlight lang="cpp">

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 fooFoo() {

int x = Factorial<0>::value; // == 1

int y = Factorial<4>::value; // == 24

}

</syntaxhighlight>

</source>

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

Here's an example of CTFE in the [[D programming language]]<ref>[http://d-programming-language.org/function.html#interpretation D 2.0 language specification: Functions]</ref>:

<sourcesyntaxhighlight lang="Dcpp">

#include <cstdio>

int factorial(int n) {

if (n == 0)

return 1;

return n * factorial(n - 1);

}

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

// computed at compile time

const int y = factorial(0); // == 1

const int x = factorial(4); // == 24

</source>

constexpr int f10 = Factorial(10);

This example specifies a valid D function called "factorial" which would typically be evaluated at run time. The use of <code>const</code> 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.<ref>[http://d-programming-language.org/attribute.html#const D 2.0 language specification: Attributes]</ref>

int main() {

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

printf("%d\n", f10);

return 0;

<source lang="D">int[] genFactorials(int n) {

auto result = new int[n];

result[0] = 1;

foreach (i; 1 .. n)

result[i] = result[i - 1] * i;

return result;

}

</syntaxhighlight>

In [[C++11]], this technique is known as [[C++11#constexpr – Generalized constant expressions|generalized constant expressions]] (<code>constexpr</code>).<ref>{{cite web|url=http://www.stroustrup.com/sac10-constexpr.pdf|author=Gabriel Dos Reis and Bjarne Stroustrup | title=General Constant Expressions for System Programming Languages. SAC-2010. The 25th ACM Symposium On Applied Computing. | date=March 2010}}</ref> [[C++14]] [[C++14#Relaxed constexpr restrictions|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).

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]

</source>

==Example 2

#include<iostream>

#include<string>

#include<conio.h>

#include<sstream>

#include<cmath>

#include<fstream>

#include "Movie.h"

using namespace std;

cin.get(); eller getch();

alternativt

system("PAUSE");

//main

#include<iostream>

#include<string>

#include<conio.h>

#include<sstream>

#include<cmath>

#include<fstream>

using namespace std;

#include "Movie.h"

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

<syntaxhighlight lang="cpp">

void counter()

// Iterative factorial at compile time.

{

constexpr int Factorial(int n) {

string line;

int result = 1;

ifstream infile;

while (n > 1) {

int count=0;

result *= n--;

infile.open("Filmer.txt");

}

if (infile.is_open())

return result;

{

while ( !infile.eof() )

{

getline( infile, line);

count = count+1;

}

count = count-1;

cout << count << "st filmer finns i filen";

}

infile.close();

}

voidint utfilmain() {

constexpr int f4 = Factorial(4); // f4 == 24

{

string line;

ifstream infile;

infile.open("Filmer.txt");

if (infile.is_open())

{

while ( !infile.eof() )

{

getline( infile, line);

cout << line;

cout << endl;

}

}

else cout << "Unable to open file";

infile.close();

}

</syntaxhighlight>

===Immediate functions (C++)===

In [[C++20]], immediate functions were introduced, and compile-time function execution was made more accessible and flexible with relaxed <code>constexpr</code> restrictions.

<syntaxhighlight lang="cpp">

void infil()

// Iterative factorial at compile time.

{

consteval int Factorial(int n) {

Movie a;

int result = 1;

a.read();

while (n > 1) {

ofstream myfile;

result *= n--;

myfile.open ("Filmer.txt", ios::app);

}

myfile << a << "\n";

return result;

myfile.close();

}

int main() {

int f4 = Factorial(4); // f4 == 24

}

</syntaxhighlight>

Since function <code>Factorial</code> is marked <code>consteval</code>, 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).

void testmovie()

{

Movie m, a, b("Fetfilmen" , "Tjockien" , 45);

Here's an example of using immediate functions in compile-time function execution:

if(b.gettitle() == "Fetfilmen")

<syntaxhighlight lang="cpp">

{

void you_see_this_error_because_assertion_fails() {}

cout << "getfunktioner funkar!\n";

}

a.settitle("Grizzlyfilmen");

if(a.gettitle() == "Grizzlyfilmen")

{

cout << "setfunktioner funkar!\n";

}

b.settitle("Grizzlyfilmen");

if(a == b)

cout << "Compareoperatorn == funkar!\n";

consteval void cassert(bool b) {

if (!b)

you_see_this_error_because_assertion_fails();

}

consteval void main1test() {

int x = 10;

{

cassert(x == 10); // ok

x++;

Movie a, b("Glassfilm", "glassgubbe", 20);

cassert(x == 11); // ok

x--;

a.settitle("Gubbfilm");

cassert(x == 12); // fails here

a.setactor("Gubben");

a.setduration(9000);

a.write();

}

int main() { test(); }

</syntaxhighlight>

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.

void main2()

{

The typical compilation error message would display:

Movie a, b;

<syntaxhighlight lang="cpp">

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();

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

[ ... ]

</syntaxhighlight>

Here's another example of using immediate functions as constructors which enables compile-time argument checking:

a.read();

<syntaxhighlight lang="cpp">

b.read();

#include <string_view>

#include <iostream>

void you_see_this_error_because_the_message_ends_with_exclamation_point() {}

a.write();

b.write();

struct checked_message {

if(a == b)

std::string_view msg;

cout << "a och b är samma film!";

else

cout << "a och b är ej samma film";

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';

}

voidint main3main() {

send_calm_message("Hello, world");

{

send_calm_message("Hello, world!");

}

</syntaxhighlight>

The compilation fails here with the message:

Movie a("moviee", "apan", 2010);

<syntaxhighlight lang="cpp">

In function 'int main()':

cin>>a;

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()'

cout << a;

you_see_this_error_because_the_message_ends_with_exclamation_point();

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

[ ... ]

</syntaxhighlight>

===D===

Here's an example of compile-time function evaluation in the [[D programming language]]:<ref>[http://d-programming-language.org/function.html#interpretation D 2.0 language specification: Functions]</ref>

<syntaxhighlight lang="d">

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

</syntaxhighlight>

This example specifies a valid D function called "factorial" which would typically be evaluated at run time. The use of <code>enum</code> 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.<ref>[http://d-programming-language.org/attribute.html#const D 2.0 language specification: Attributes]</ref>

void main4()

{

Movie a("moviee", "apan", 2010);

Movie b("moviee", "gurkan", 1212);

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

<syntaxhighlight lang="d">

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);

int main()

{

bool menu = true;

int choice;

void main() {}

while(menu == true)

{

cout << "Vad vill du göra?\n" << "1.Add movie to archive 2.Read movies in archive 3.Test all functions 4.Count movies in archive 5.Exit 6.Delete all movies";

cin >> choice;

switch(choice)

{

case 1:

infil();

break;

// 'factorials' contains at compile-time:

case 2:

// [1, 1, 2, 6, 24, 120, 720, 5_040, 40_320, 362_880, 3_628_800,

utfil();

// 39_916_800, 479_001_600]

break;

</syntaxhighlight>

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

case 3:

testmovie();

break;

===Zig===

case 4:

Here's an example of compile-time function evaluation in the [[Zig programming language]]:<ref>[https://ziglang.org/documentation/0.11.0/#Compile-Time-Expressions Zig 0.11.0 Language Reference: Compile-Time Expressions]</ref>

counter();

break;

<syntaxhighlight lang="zig">

case 5:

pub fn factorial(n: usize) usize {

menu = false;

var result = 1;

break;

for (1..(n + 1)) |i| {

result *= i;

}

return result;

}

pub fn main() void {

case 6:

const x = comptime factorial(0); // == 0

remove("Filmer.txt");

const y = comptime factorial(4); // == 24

ofstream output("Filmer.txt");

}

break;

</syntaxhighlight>

This example specifies a valid Zig function called "factorial" which would typically be evaluated at run time. The use of <code>comptime</code> 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.

Zig also support Compile-Time Parameters.<ref>[https://ziglang.org/documentation/0.11.0/#Compile-Time-Parameters Zig 0.11.0 Language Reference: Compile-Time Parameters]</ref>

<syntaxhighlight lang="zig">

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

}

</syntaxhighlight>

CTFE can be used to create generic data structures at compile-time:

<syntaxhighlight lang="zig">

fn List(comptime T: type) type {

getch();

return struct {

items: []T,

return 0;

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,

};

</syntaxhighlight>

==References==

<references/>

==External links==

//hfil

* [http://rosettacode.org/wiki/Compile-time_calculation Rosettacode examples of compile-time function evaluation in various languages]

#include <iostream>

#include <string>

#include <istream>

{{Compiler optimizations}}

using namespace std;

class Movie

{

private:

string title;

string actor;

int duration;

public:

Movie() //constructor utan parametrar

{

title = "";

actor = "";

duration = 0;

}

Movie(string title, string actor, int duration) //constuctor med parametrar

{

this->title = title;

this->actor = actor;

this->duration = duration;

}

string gettitle() {return title;}

void settitle (string t) {title = t;}

string getactor(){return actor;}

void setactor(string a){actor = a;}

int getduration() {return duration;}

void setduration (int d){duration = d;}

friend ostream& operator<< (ostream& o, const Movie& Movie)

{

o << "(";

o << Movie.title;

o << ",";

o << Movie.actor;

o << ",";

o << Movie.duration;

o << ")";

return o;

}

friend istream& operator>> (istream &i, Movie& Movie)

{

char c;

i >> skipws >> c;

getline(cin, Movie.title, ',');

i >> skipws;

getline(cin, Movie.actor, ',');

i >> skipws;

i >> skipws >> Movie.duration;

i >> skipws >> c;

return i;

}

friend int operator== (const Movie m1, const Movie m2)

{

if ( m1.title == m2.title )

return 1;

else

return 0;

}

void read()

{ string c;

cout<< endl << "Enter movie name: ";

cin >> c;

getline(cin, this->title, '\n');

this->title = c + this->title;

cout << endl;

cout<< "Enter actor name: ";

getline(cin, this->actor, '\n');

cout << endl;

cout<< "Enter duration: ";

cin >> duration;

cout << endl;

}

void write()

{

cout << "Title: " << title << endl;

cout << "Actor: " << actor << endl;

cout << "Duration: " << duration << endl;

}

};

== References ==

<references/>

{{DEFAULTSORT:Compile Time Function Execution}}

[[Category:Compiler construction]]

[[Category:Articles with example C++ code]]

[[Category:Articles with example D code]]

[[Category:Compiler optimizations]]