Compile-Time Function Evaluation and Its Limits

A compiler already contains a machine for manipulating the program. Adding a second machine that executes parts of it is tempting, and every language that has done so has run into the same wall: the operations a program performs at run time are not the operations a compiler can perform while translating it. The design of compile-time evaluation is largely the design of that wall, and of what happens at it.

Constant folding is not the same thing

The oldest form is not an interpreter at all. An optimizer recognises that both operands of an arithmetic instruction are literal integers, computes the result, and replaces the instruction with a constant. This is a local rewrite over the intermediate representation, and it terminates because the rewrite strictly reduces the number of instructions.

Constant folding cannot call a function. It has no frame, no calling convention, and no way to run a loop whose trip count is unknown at the point of the rewrite. What it can do is bounded by the pattern the optimizer knows how to match, which is why folding a min of two literals usually works and folding a min of two literals through three layers of user-defined wrapper does not.

Compile-time evaluation replaces the pattern matching with an actual interpreter. The compiler takes the function’s body, its arguments as constant values, and runs it in an environment where the available operations are the compiler’s own. The result is a value that replaces the call.

Why the interpreter must be a subset

The interpreter inside a compiler cannot perform an operation whose effect is only defined at run time. Reading a file, writing to standard output, allocating from the operating system, taking the address of a mutable global, calling a function through a function pointer whose target is unknown — each of these has an effect that the compiler cannot model and, more importantly, cannot undo.

The standard response is a purity requirement expressed as a whitelist. In Rust, a const fn may call only other const fns and may not perform I/O; the permitted set of operations is checked by the compiler, and violating it is an error rather than a silently deferred computation. The set has widened across releases — floating-point arithmetic in constant context, for instance, moved from rejected to accepted — so a const fn that uses a recently permitted operation is not portable to older toolchains. In C++, a constexpr function’s body is checked against a list of permitted constructs, and an invocation that reaches a forbidden construct makes the expression non-constant rather than making the program fail.

const fn fifth_power() -> u32 {
    let mut acc = 1u32;
    let mut i = 0u32;
    let base = 3u32;
    while i < 5 {
        acc *= base;       // overflow is a compile-time error here, not a wrapping result
        i += 1;
    }
    acc
}

const P: u32 = fifth_power();

The while loop is permitted because the interpreter can execute it, and its bound is a constant, so the interpreter’s own step budget is what limits the run rather than anything in the type system. The multiplication is permitted but its overflow behaviour differs from run time: an overflow in a constant expression is diagnosed at compile time, where the same code in a run-time function would wrap or trap depending on the build configuration. That divergence is deliberate — a compile-time value that silently wrapped would make the constant disagree with the function it was computed from — but it means a const fn is not simply “the same function, run earlier”.

The step limit and what it protects

An interpreter running inside a compiler is running on input the compiler did not write. A recursive const fn with no decreasing argument, or a loop whose bound is a constant but enormous, would hang the compiler. Every implementation therefore imposes a budget: a maximum number of interpreter steps, a maximum memory allocation, a maximum call depth, or a maximum size of the resulting value.

These limits are implementation-defined and version-sensitive, which makes them a portability hazard. A constant expression that is accepted by one compiler version can be rejected by the next when the budget is tightened, and the failure is a hard error at the definition site. The alternative — no limit — converts a bad program into a compiler that does not return, which is worse for every user of that compiler.

The same budget creates a subtle boundary in what the language promises. Because the limit is not part of the specification, a program cannot rely on a computation being cheap enough to evaluate; the only portable statement is that a computation within the documented limits will succeed.

Termination is not the same as decidability

It is worth separating two questions that are often conflated. The first is whether the interpreter terminates on a given input, which the step budget answers by fiat. The second is whether an expression of the language is guaranteed to be evaluable during translation, which is a question about the language’s definition rather than about any particular run.

C++ template metaprogramming is the cautionary case. Before constexpr, computation at compile time was expressed by instantiating templates: a recursive template specialization computes a value, and the recursion terminates when a partial specialization matches the base case. The language did not need an interpreter because template instantiation already ran during translation. The cost was that every computation was expressed in a language with no variables, no loops, and no local state, and that the compiler’s recursion depth for template instantiation became a hard limit on what programs could be written. Implementations expose that limit as a flag with a default in the hundreds of levels, and a program that exceeds it fails with a diagnostic about instantiation depth rather than about anything the programmer did wrong.

Modern constexpr and consteval moved the computation back into ordinary function syntax, which fixed the expressiveness problem but not the depth problem: the interpreter still has a call-depth limit, and recursive constant functions still hit it.

Where the evaluated value goes

The result of compile-time evaluation is a value embedded in the compiled artifact, and how it is embedded determines what can be done with it. Three placements are common.

An immediate operand: the value is small enough to be encoded in an instruction, so the call disappears and the constant is loaded directly. This is what constant folding produces and it is the cheapest outcome.

A read-only data section: the value is a table or a string, so the compiler emits bytes into the object file’s read-only segment and the program refers to them by address. A lookup table generated at compile time costs nothing at run time except the cache misses its accesses cause, and it costs object-file size in proportion to the table. A table of 256 entries of 4 bytes each is one kilobyte of object file; a table of 65536 entries of the same size is a quarter of a megabyte, which is enough to be worth thinking about in an embedded target.

A recomputed value: nothing is embedded, and the computation happens again at run time. This is what happens when a const fn is called in a non-constant context, and it is why the function must be written so that it is valid in both contexts. The compile-time evaluation is then purely an optimization that the compiler may or may not apply.

The placement is observable in ways that matter. Taking the address of a constant may or may not force it into memory; comparing two identical constants may or may not yield the same address; and a constant that is large enough to be placed in a data section may be deduplicated with an identical constant from another translation unit or may not, depending on the linker.

The boundary as a design decision

The interesting design question is not whether to evaluate at compile time but what the language guarantees about it. Three positions are defensible, and languages occupy all three.

Guaranteed evaluation: the specification says the expression is evaluated during translation, and a program that cannot be so evaluated is ill-formed. This is the C++ consteval position and the Rust const item position. It makes the computation part of the program’s meaning, so its result can be used where a constant is required — an array length, a template argument, a discriminant.

Permitted evaluation: the specification says the compiler may evaluate, and the program must behave identically either way. This is ordinary optimization. It cannot be used where a constant is required, because the language does not promise the value will be known.

Required refusal: some expressions must not be evaluated, because their evaluation would have an effect the compiler cannot represent. This is where the subset restriction lives, and it is the reason a compile-time evaluator is always smaller than the language it is embedded in.

The third position is the one that constrains the other two. Every operation excluded from the interpreter is a place where a programmer must restructure code — hoisting an allocation out of a function, replacing a call through a function pointer with a direct call, splitting a function into a constant part and an effectful part. The restructuring is not incidental; it is the visible shape of the boundary, and languages that hide the boundary behind “the compiler will figure it out” tend to produce code whose compile-time behaviour changes when the optimizer changes. The explicit annotation, whether const fn or constexpr, exists so that the boundary is written down and checked rather than inferred.

Compile-time evaluation also composes with the other facilities in this cluster in one specific way: it gives a macro a way to compute a value rather than only to rearrange syntax. A macro that needs a table can call a constant function to build it, and a derive macro that needs a size can ask the compiler for one. The mechanics of the second case are in derive macros and structural recursion, and the phase ordering that makes the first case work is in phase separation and the ordering of compilation stages.