Programming languages are typically either compiled or interpreted. This distinction isn't absolute. Some languages like Java and Python are first compiled to platform independent byte code, and then the byte code is interpreted by the platform specific interpreter. Nor is the distinction necessarily about the language itself, but rather about the typical implementation: A compiled program can be interpreted by an emulator, and an interpreted program can always be “compiled” by bundling the machine code of the interpreter with the source code of the program in a single object file.

Compiled vs. interpreted is usually what follows naturally from the design of the language. Interpreted languages emphasis high level constructs like reflection and dynamic typing that are most naturally represented by complex data structures inside the interpreter. Compiled languages emphasis performance by using constructs that closely map to machine code. And of course there is a spectrum within these categories: C++ needs more complex runtime support library than C, for instance.

In this post I write about C++ as interpreted language. There are actual interpreters implementing significant portions of the standard C++ (cling, CINT). In this post, however, I want to study something else: using the compile time computations to have the C++ compiler itself “interpret” a program and extracting the output without ever running any compiled code.

Compile time computations

One of the coolest things in modern C++ is how much more can be done at compile time in each new standard revision. I mean, if you want to check the primarlity of an integer at compile time in C++14, you just:

constexpr bool is_prime(int n)
{
    if (n <= 1) {
        return false;
    }
    for (int m = 2; m*m <= n; ++m) {
        if (n % m == 0) {
            return false;
        }
    }
    return true;
}

static_assert(is_prime(2));
static_assert(is_prime(7));
static_assert(is_prime(12)); // oops!

In C++98 you would have to write some pretty smart templates to achieve the same.

In the above example C++ compiler outputs (an empty) object file on successfully tested primes (2, 7), and fails to produce any output for composite numbers (12). Thus interpreting the static assertions as input and the compilation outcome (success/failure) as output of our program, we can use the C++ compiler to solve decision problems at compile time.

What about inputing and outputing something more complex, say a list of primes less than 100? You could encode the values as types, a common idiom in C++ metaprogramming. Here's the program:

template<int N>
using int_constant = std::integral_constant<int, N>;

template<int... Ns>
using int_sequence = std::integer_sequence<int, Ns...>;

template<int... Ns, int NEXT, int LAST>
constexpr auto get_first_primes_impl(
    int_sequence<Ns...> primes,
    int_constant<NEXT> next,
    int_constant<LAST> last)
{
    if constexpr (NEXT >= LAST) {
        return primes;
    } else if constexpr (is_prime(NEXT)) {
        return get_first_primes_impl(
            int_sequence<Ns..., NEXT> {},
            int_constant<NEXT+1> {},
            last
        );
    } else {
        return get_first_primes_impl(
            primes,
            int_constant<NEXT+1> {},
            last
        );
    }
}

template<int N>
constexpr auto get_first_primes(int_constant<N> last)
{
    return get_first_primes_impl(
        int_sequence<> {},
        int_constant<2> {},
        last
    );
}

void OUTPUT(decltype(get_first_primes(int_constant<100> {}))) {}

When you compile it and examine the signature of OUTPUT, you'll see the first 100 prime numbers encoded as the template parameters of the std::integer_sequence template.

$ g++ -c -std=c++17 primes.cc
$ nm primes.o | c++filt
0000000000000000 T OUTPUT(std::integer_sequence<int, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97>)

Let's take that apart. The important things to note here are:

• Types are used as values in the function templates. The return type of a particular template instantiation can depend on the types of its parameters, but not on their values. That's why instead of passing integers and arrays of integers, we pass std::integral_constant and std::integer_sequence objects.
• GCC mangles the name of the function OUTPUT in a way that encodes the type of its parameter. The c++filt utility demangles it and makes the output readable for humans. The function OUTPUT serves no runtime purpose: it takes an empty object as its parameter and does nothing. The only purpose of the definition is to produce the mangled symbol when compiled.
• The if constexpr statement introduced in C++17 greatly simplifies the implementation of get_first_primes_impl. The function can “choose” a different return type in each branch recursively.
• It's painfully obvious that the algorithm is far from optimal. The purpose is to demonstrate the possibilities of compile time computation, not the optimal ways of finding primes.

Using C++ compiler as interpreter

The above programs never produced an executable program (there is no main function to link with), yet there were results that could directly be extracted from the compiler output. Hence, interpreted C++ with the compiler acting as interpreter.

There are differences between “normal” and “interpreted” C++, some of which reflect the differences of compiled and interpreted languages in general.

1. I/O is awkward and implementation specific. Input is nonexistent beyond what is hardcoded in the source file itself, and possibly what could be injected from the command line arguments when invocing the compiler (macro definitions etc.). So no interactive programs I'm afraid.
2. Interpreted C++ is functional by nature. The instantiated types are immutable, and dynamic data structures are simulated by constructing new types recursively.
3. Interpreted C++ is free from undefined behavior.

In C and the languages inspired by it undefined behavior is a necessary design choice. It's essential to allow the compiler to produce the most performant machine code possible. On the other hand in a typical interpreted language the result of incorrect constructs (referencing non-existent objects, accessing arrays beyond bounds etc.) are controlled: they may explicitly blow into your face, but at least in a consistent way. The latter is also true for core constant expressions in C++. Things that can potentially lead to undefined behavior are prohibited during compile time. And the number of prohibited things is being reduced revision by revision of the C++ standard!

The second point is likely being addressed by the C++ standards committee eventually. If a future C++ revision supported non-transient allocations during compile time, the results of a non-fixed size computation (like the prime listing above) could more naturally be encoded by having the compiler emit a particular value for a compile time constant appearing in the object file.

In the unlikely case that the C++ standards committee would include the I/O library in core constant expressions, you could start executing full fledged programs at compile time.