D at compile time: CTFE, templates, mixins

enum fib50 = fib(50); makes the compiler run an ordinary D function while it builds the program, so the program starts with 12,586,269,025 already in it, and static assert(fib(10) == 55) stops the build the day that fact about your code turns false. This is D’s signature feature: the language of the program is also the language that runs while compiling.

Here you evaluate functions at compile time and see what that evaluation refuses, write templates whose constraints report a wrong call where it is made, give quantities their units in their types, generate code with string mixins, inspect a struct’s members with __traits and std.traits, and build one program with and without D’s runtime.

enum and static assert run a function while compiling

fib below is an ordinary function with a loop, and the program uses it twice: once to fill a manifest constant, whose value must exist while compiling, and once with a number known only at run time. A second function builds the table of the CRC-32 that zlib uses, also while compiling. Step through the build and the run:

import std.stdio;

/// The n-th Fibonacci number, with a loop: an ordinary function.
ulong fib(uint n)
{
    ulong a = 0, b = 1;
    foreach (i; 0 .. n)
    {
        immutable next = a + b;
        a = b;
        b = next;
    }
    return a;
}

enum fib50 = fib(50);            // a manifest constant: fib runs while compiling
static assert(fib(10) == 55);    // checked while compiling

/// The table of the CRC-32 that zlib and PNG use, one entry per byte value.
uint[256] makeCrcTable()
{
    uint[256] table;
    foreach (uint i; 0 .. 256)
    {
        uint c = i;
        foreach (_; 0 .. 8)
            c = (c & 1) ? 0xEDB88320 ^ (c >> 1) : c >> 1;
        table[i] = c;
    }
    return table;
}

immutable uint[256] crcTable = makeCrcTable();   // computed while compiling, stored in the program

uint crc32(const(ubyte)[] data)
{
    uint c = 0xFFFFFFFF;
    foreach (b; data)
        c = crcTable[(c ^ b) & 0xFF] ^ (c >> 8);
    return c ^ 0xFFFFFFFF;
}

void main()
{
    pragma(msg, "while compiling, fib(50) = ", fib50);
    writeln("fib(50) = ", fib50);
    writefln("crc32(\"hello\") = %08x", crc32(cast(const(ubyte)[]) "hello"));
    uint n = 50;
    writeln("fib(n) at run time = ", fib(n));
}

from session import run

# A function run while compiling: pragma(msg) prints during the build, the program prints at run time, and Python's
# zlib computes the same CRC-32 as the table that was built while compiling. Then a static assert that fails, and two
# functions that compile-time evaluation refuses. -c compiles a module without linking a program.
run("""
cd ctfe
ldc2 ctfe.d
./ctfe
python3 -c "import zlib; print(format(zlib.crc32(b'hello'), '08x'))"
!ldc2 -c wrong.d
!ldc2 -c limits.d
""")

$ cd ctfe
$ ldc2 ctfe.d
while compiling, fib(50) = 12586269025LU
$ ./ctfe
fib(50) = 12586269025
crc32("hello") = 3610a686
fib(n) at run time = 12586269025
$ python3 -c "import zlib; print(format(zlib.crc32(b'hello'), '08x'))"
3610a686
$ ldc2 -c wrong.d
wrong.d(13): Error: static assert:  "fib(10) should be 56"
static assert(fib(10) == 56, "fib(10) should be 56");
^
[exit status 1]
$ ldc2 -c limits.d
limits.d(8): Error: static variable `counter` cannot be read at compile time
    return ++counter;
             ^
limits.d(16):        called from here: `next()`
enum first = next();
                 ^
limits.d(13): Error: `getenv` cannot be interpreted at compile time, because it has no available source code
    return getenv("HOME").fromStringz.idup;
                 ^
[exit status 1]

The first output line came from the build, not from the program: pragma(msg) prints while compiling, and it showed 12586269025LU, the constant with the suffix of a ulong literal. This is compile-time function evaluationcompile-time function evaluation (CTFE): The D compiler running an ordinary function while it builds the program, wherever a value must exist then: an enum constant, a static initialiser, static assert, static if, a template value argument or a mixin.. The specification lists the places where it happens, among them the initialiser of a manifest constant or of a global or static variable, an argument of a template value parameter, static if, static foreach, static assert, mixins and the size of a static array. The CRC table shows why it matters: 256 entries, worked out bit by bit while compiling, went into the program as data, and its CRC-32 of “hello”, 3610a686, is the value Python’s zlib.crc32 gave in the same session.

The last two commands show what the interpreter refuses. wrong.d claims that fib(10) is 56, and the build stopped with the static assert’s own message. limits.d asks for two constants that cannot exist before the program runs: one reads a mutable counter at module level, a static variable in the compiler’s message, which the specification forbids, and one calls getenv, a C function whose D source the compiler does not have.

A constraint reports a wrong call where it is made

A template is code with parameters that the compiler fills in, and it makes one copy of the code per set of arguments. total adds the elements of any array; called with an array of strings, it is a mistake, and the question is where the compiler says so. open.d has no constraint and checked.d has if (isNumeric!T):

import std.traits : isNumeric;

T total(T)(T[] values)
if (isNumeric!T)
{
    T sum = 0;
    foreach (v; values)
        sum += v;
    return sum;
}

void main()
{
    auto a = total([1.5, 2.25]);
    auto b = total(["7", "8"]);
}

from session import run

# One template without a constraint and one with it, called with an array of strings; static if in a template; and a
# units type whose dimension is part of its type, so that adding metres to seconds does not compile.
run("""
cd templates
!ldc2 open.d
!ldc2 checked.d
ldc2 -run describe.d
ldc2 units.d quantity.d
./units
!ldc2 -c units_wrong.d
""")

$ cd templates
$ ldc2 open.d
open.d(3): Error: cannot implicitly convert expression `0` of type `int` to `string`
    T sum = 0;
            ^
open.d(5): Error: slice `sum` is not mutable
        sum += v;
            ^
open.d(5):        did you mean to concatenate (`sum ~= v`) instead ?
        sum += v;
            ^
open.d(12): Error: template instance `open.total!string` error instantiating
    auto b = total(["7", "8"]);
                  ^
[exit status 1]
$ ldc2 checked.d
checked.d(15): Error: template `total` is not callable using argument types `!()(string[])`
    auto b = total(["7", "8"]);
                  ^
checked.d(3):        Candidate is: `total(T)(T[] values)`
  with `T = string`
  must satisfy the following constraint:
`       isNumeric!T`
T total(T)(T[] values)
  ^
[exit status 1]
$ ldc2 -run describe.d
42: a whole number of 4 bytes
42: a whole number of 8 bytes
2.5: a floating-point number
Pune: text of 4 code units
$ ldc2 units.d quantity.d
$ ./units
speed: 10.491 m/s
Quantity!(1, 0): 100.5
Quantity!(1, -2): 1.095
Quantity!(0, 0): 2.01
$ ldc2 -c units_wrong.d
units_wrong.d(5): Error: none of the overloads of template `quantity.Quantity!(1, 0).Quantity.opBinary` are callable using argument types `!("+")(Quantity!(0, 1))`
    auto mixedUp = Metres(100) + Seconds(9.58);
                         ^
quantity.d(9):        Candidates are: `opBinary(string op)(Quantity other) const`
    Quantity opBinary(string op)(Quantity other) const
             ^
quantity.d(16):                        `opBinary(string op, int m2, int s2)(Quantity!(m2, s2) other) const`
  with `op = "+",
       m2 = 0,
       s2 = 1`
  must satisfy one of the following constraints:
`       op == "*"
       op == "/"`
    auto opBinary(string op, int m2, int s2)(Quantity!(m2, s2) other) const
         ^
quantity.d(9):        `opBinary` defined here
    Quantity opBinary(string op)(Quantity other) const
             ^
[exit status 1]

Without the constraint, the compiler made total!string and compiled its body, so the errors came from inside it: T sum = 0 could not turn 0 into a string, and sum += v failed too, with a hint to concatenate with ~= instead. Only the last line pointed back to the call, at line 12. With the constrainttemplate constraint: A condition after a template's parameters, such as if (isNumeric!T), checked while compiling. A call whose arguments fail it is refused at the call, with the condition named, before the template's body is compiled., the call itself was refused, at line 15: total is not callable using !()(string[]), with T = string and the constraint that failed. Step through both calls:

describe.d uses static if, which chooses code while compiling: in each copy of describe, only the branch for that type remains, so describe(42) says 4 bytes for an int and describe(42L) 8 bytes for a long. The last branch is static assert(false, …), which turns a type that no branch handles into a compile error with a message of your own.

Types can carry units, checked while compiling

Quantity(int m, int s) in quantity.d keeps a quantity’s dimension in its type: metres to the power m times seconds to the power s. Metres is Quantity!(1, 0), Seconds is Quantity!(0, 1), and their opBinary templates say what each operator gives:

module quantity;

/// A quantity with its dimension as two exponents: metres^m * seconds^s.
struct Quantity(int m, int s)
{
    double value;

    /// Adding or subtracting needs the same dimension: the parameter's type says so.
    Quantity opBinary(string op)(Quantity other) const
    if (op == "+" || op == "-")
    {
        return Quantity(mixin("value " ~ op ~ " other.value"));
    }

    /// Multiplying adds the exponents, dividing subtracts them.
    auto opBinary(string op, int m2, int s2)(Quantity!(m2, s2) other) const
    if (op == "*" || op == "/")
    {
        static if (op == "*")
            return Quantity!(m + m2, s + s2)(value * other.value);
        else
            return Quantity!(m - m2, s - s2)(value / other.value);
    }
}

alias Metres = Quantity!(1, 0);
alias Seconds = Quantity!(0, 1);
alias MetresPerSecond = Quantity!(1, -1);

static assert(is(typeof(Metres(100) / Seconds(9.58)) == MetresPerSecond));
static assert(!__traits(compiles, Metres(1) + Seconds(1)));

+ and - take a Quantity of the same type, so only equal dimensions add. * and / take any Quantity!(m2, s2) and return a new type with the exponents added or subtracted, which the static if inside chooses. The two static asserts at the end are tests that run while compiling: Metres / Seconds must be MetresPerSecond, and Metres + Seconds must not compile, checked with __traits(compiles, …).

In the session, units.d printed a speed of 10.491 m/s from 100.5 m in 9.58 s, and the types of three expressions as the compiler names them: Quantity!(1, 0) for speed times time, Quantity!(1, -2) for speed per second and Quantity!(0, 0) for a ratio of two lengths. An alias such as Metres is only another name, so typeof shows the template. units_wrong.d, which adds metres to seconds, did not compile: no overload of opBinary accepts Quantity!(0, 1) for +. The program never has to check a unit at run time, because the wrong sum never becomes a program.

A string mixin compiles code that a function wrote

A string mixin, mixin(…), compiles a string as D code where it stands. The string is computed while compiling, so a function can write the code. getters below makes one getter per name, and pragma(msg) shows the code it wrote:

import std.stdio;
import std.format : format;

/// D source for one getter per name, built as a string while compiling.
string getters(string[] names)
{
    string code;
    foreach (n; names)
        code ~= format("int %s() const { return _%s; }\n", n, n);
    return code;
}

struct Score
{
    private int _runs, _wickets;
    this(int runs, int wickets) { _runs = runs; _wickets = wickets; }
    mixin(getters(["runs", "wickets"]));
}

void main()
{
    pragma(msg, getters(["runs", "wickets"]));
    auto s = Score(287, 6);
    writeln(s.runs, "/", s.wickets);
}

import std.stdio;
import std.conv : to;
import std.traits : FieldNameTuple;

struct Reading
{
    string station;
    int hour;
    double celsius;
    double fahrenheit() const { return celsius * 9 / 5 + 32; }
}

struct Order
{
    int id;
    string item;
    int quantity;
    bool paid;
}

/// The names of T's fields, in order: the CSV header.
string csvHeader(T)()
{
    string line;
    static foreach (i, name; FieldNameTuple!T)
        line ~= (i ? "," : "") ~ name;
    return line;
}

/// One CSV line with the values of value's fields, in the order of the header.
string toCsv(T)(T value)
{
    string line;
    static foreach (i, name; FieldNameTuple!T)
        line ~= (i ? "," : "") ~ __traits(getMember, value, name).to!string;
    return line;
}

void main()
{
    pragma(msg, "allMembers of Reading: ", __traits(allMembers, Reading));
    pragma(msg, "FieldNameTuple!Reading: ", FieldNameTuple!Reading);
    writeln(csvHeader!Reading);
    writeln(Reading("Pune", 6, 21.5).toCsv);
    writeln(csvHeader!Order);
    writeln(Order(17, "pencils", 12, true).toCsv);
}

from session import run

# A string mixin whose code is built while compiling, printed by pragma(msg); then a CSV writer for any struct, from
# the names of its fields.
run("""
cd mixins
ldc2 getters.d
./getters
ldc2 tocsv.d
./tocsv
""")

$ cd mixins
$ ldc2 getters.d
int runs() const { return _runs; }
int wickets() const { return _wickets; }
$ ./getters
287/6
$ ldc2 tocsv.d
allMembers of Reading: AliasSeq!("station", "hour", "celsius", "fahrenheit")
FieldNameTuple!Reading: AliasSeq!("station", "hour", "celsius")
$ ./tocsv
station,hour,celsius
Pune,6,21.5
id,item,quantity,paid
17,pencils,12,true

The build of getters.d printed the two lines of code that the string mixinstring mixin: mixin(...) with a string that is known while compiling: the compiler compiles the string as D code in that place, so a function run at compile time can write declarations or statements. compiled into Score, and the program then called them: 287/6. tocsv.d goes the other way: instead of writing code from names, it reads the names from a type. FieldNameTuple!T from std.traits gives the names of T’s fields, and static foreach unrolls one line of code per field, so toCsv works for Reading and for Order without knowing either.

A betterC build keeps the language and drops the runtime

-betterC builds a program that depends on the C library only, without druntime and its garbage collector. The specification gives the reasons: constrained targets, and D code inside a larger C program, which then need not start D’s runtime first. One source can build both ways, because -betterC defines the version D_BetterC:

import core.stdc.stdio : printf;

/// Adds the marks without allocating, so it builds with and without -betterC.
int total(const int[] marks) @nogc nothrow
{
    int sum = 0;
    foreach (m; marks)
        sum += m;
    return sum;
}

extern (C) int main()
{
    static immutable int[4] marks = [72, 45, 90, 61];
    version (D_BetterC)
        printf("built with -betterC: ");
    else
        printf("built with the D runtime: ");
    printf("total %d\n", total(marks[]));
    return 0;
}

from session import run

# One source built with the D runtime and with -betterC, and the sizes of both programs; then what -betterC refuses:
# an append, a throw, a class made with new (a link error) and std.stdio's writeln, and what it keeps: a bounds
# check, through C's assert.
run("""
cd betterc
ldc2 total.d -of=total_runtime
./total_runtime
wc -c < total_runtime
ldc2 -betterC total.d -of=total_betterc
./total_betterc
wc -c < total_betterc
!ldc2 -betterC append.d
!ldc2 -betterC throws.d
!ldc2 -betterC newclass.d
# writeln from std.stdio under -betterC: the errors of a build that fails, picked out with grep
ldc2 -betterC phobos.d 2>&1 | grep -e 'Error'
ldc2 -betterC index.d
!./index
""")

$ cd betterc
$ ldc2 total.d -of=total_runtime
$ ./total_runtime
built with the D runtime: total 268
$ wc -c < total_runtime
   50208
$ ldc2 -betterC total.d -of=total_betterc
$ ./total_betterc
built with -betterC: total 268
$ wc -c < total_betterc
   33568
$ ldc2 -betterC append.d
append.d(4): Error: appending to array in `marks ~= 90` requires the GC which is not available with -betterC
    marks ~= 90;
          ^
[exit status 1]
$ ldc2 -betterC throws.d
throws.d(3): Error: cannot use `throw` statements with `-fno-exceptions`
    throw new Exception("no runtime to catch this");
    ^
[exit status 1]
$ ldc2 -betterC newclass.d
Undefined symbols for architecture arm64:
  "__D6object6Object5opCmpMFCQqZi", referenced from:
      __D8newclass7Counter6__vtblZ in newclass.o
  "__D6object6Object6toHashMFNbNeZm", referenced from:
      __D8newclass7Counter6__vtblZ in newclass.o
  "__D6object6Object8opEqualsMFCQtZb", referenced from:
      __D8newclass7Counter6__vtblZ in newclass.o
  "__D6object6Object8toStringMFZAya", referenced from:
      __D8newclass7Counter6__vtblZ in newclass.o
  "__D8newclass7Counter7__ClassZ", referenced from:
      _main in newclass.o
  "__d_allocclass", referenced from:
      _main in newclass.o
ld: symbol(s) not found for architecture arm64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
Error: /usr/bin/cc failed with status: 1
[exit status 1]
# writeln from std.stdio under -betterC: the errors of a build that fails, picked out with grep
$ ldc2 -betterC phobos.d 2>&1 | grep -e 'Error'
…/bin/../import/std/stdio.d(4281): Error: none of the overloads of template `std.stdio.File.LockingTextWriter.put` are callable using argument types `!()(string)`
…/bin/../import/std/stdio.d(3279): Error: none of the overloads of template `std.utf.decodeFront` are callable using argument types `!()(char[])`
…/bin/../import/std/utf.d(2311): Error: cannot use `throw` statements with `-fno-exceptions`
…/bin/../import/std/utf.d(2514): Error: template instance `std.utf._utfException!(Flag.no)` error instantiating
$ ldc2 -betterC index.d
$ ./index
Assertion failed: (array index out of bounds), function index.main, file index.d, line 7.
[exit status 134]

The two builds printed their own line and the same total, 268, and the -betterC program was 33,568 bytes against 50,208. Both use extern (C) int main and printf, so neither pulls in much of the runtime; the hello.d of the first lesson, which used writeln, was 1,188,488. What -betterC refuses shows what the runtime does. An append needs the garbage collector. A throw cannot be compiled, because -betterC switches exceptions off. A class made with new compiled but did not link: Object’s methods and _d_allocclass, the runtime’s allocator, were missing. writeln failed deep inside std.stdio, which needs the runtime too. What stays is most of the language, compile-time evaluation included, and a bounds check: index.d stopped with C’s assertion message and exit status 134.

In short: build with the runtime for programs of your own, and with -betterC for D inside a C program or on a target without the runtime, as long as the code can live with structs, static arrays and printf.

Practise: the units, in Python

The exercise writes the rules of Quantity as Python functions on pairs of exponents: what the compiler works out while compiling, done at run time. Its sample tests replay the four lines of units.d and the sum that units_wrong.d could not compile.

NAMES = {(1, 0): "Metres", (0, 1): "Seconds", (1, -1): "MetresPerSecond"}


def times(a, b):
    """The dimension of a * b."""
    return (a[0] * b[0], a[1] * b[1])


def divided(a, b):
    """The dimension of a / b."""
    return (a[0] - b[0], a[1] - b[1])


def plus(a, b):
    """The dimension of a + b, or a TypeError when the dimensions differ."""
    return a


def type_name(d):
    """What D prints for the type of a quantity with dimension d."""
    return NAMES.get(d, f"Quantity!{d}")

from units import divided, plus, times, type_name

METRES, SECONDS = (1, 0), (0, 1)


def test_speed_from_distance_and_time():
    """distance / time is MetresPerSecond, Quantity!(1, -1)"""
    speed = divided(METRES, SECONDS)
    assert speed == (1, -1)
    assert type_name(speed) == "Quantity!(1, -1)"


def test_back_to_metres():
    """units.d printed Quantity!(1, 0) for speed * time"""
    assert type_name(times(divided(METRES, SECONDS), SECONDS)) == "Quantity!(1, 0)"


def test_speed_per_second():
    """units.d printed Quantity!(1, -2) for speed / time"""
    assert type_name(divided(divided(METRES, SECONDS), SECONDS)) == "Quantity!(1, -2)"


def test_a_ratio_has_no_dimension():
    """units.d printed Quantity!(0, 0) for distance / Metres(50)"""
    assert type_name(divided(METRES, METRES)) == "Quantity!(0, 0)"


def test_metres_plus_metres():
    """the sum in units.d: Metres(100) + Metres(0.5)"""
    assert plus(METRES, METRES) == METRES


def test_metres_plus_seconds_does_not_exist():
    """units_wrong.d did not compile; the model raises instead"""
    try:
        plus(METRES, SECONDS)
    except TypeError as e:
        assert str(e) == "cannot add Quantity!(1, 0) and Quantity!(0, 1)"
    else:
        assert False, "plus((1, 0), (0, 1)) must raise TypeError"


def test_areas_and_more():
    """products add exponents: an area, and an area per second squared"""
    area = times(METRES, METRES)
    assert area == (2, 0)
    assert type_name(divided(area, times(SECONDS, SECONDS))) == "Quantity!(2, -2)"

Then the self-check, on the five ideas of this lesson. It keeps to the idea you are least sure of until your answers show that you have it, and explains each answer as you give it:

Interview questions

Warm-up (mid-level to senior): What is compile-time function evaluation in D, and where does it run?

It is the compiler running ordinary D functions while it builds the program, through an interpreter in its front end. It runs wherever a value must exist while compiling: the initialiser of an enum manifest constant or of a global or static variable, static assert, static if, static foreach, a template value argument, a string mixin and the size of a static array. The function needs no special form, but it must have D source available and must not touch mutable global or static state, inline assembly or undefined behaviour. In the lesson, enum fib50 = fib(50) put 12,586,269,025 into the program, a CRC-32 table was built while compiling and matched zlib’s result, and calls of getenv and of a function that changes a static counter were refused.

Two longer questions, on the errors a library’s templates give its users and on D inside a C program:

Key takeaways

• enum, static assert, static initialisers and the other places of the specification run ordinary D functions while compiling; pragma(msg) showed the value during the build, and a CRC table built that way matched zlib.
• The interpreter refuses functions without D source, mutable global or static state and inline assembly, and it interprets, so heavy work belongs at run time.
• A template constraint refuses a wrong call at the call, naming the condition; without it the errors come from inside the template’s body. static if keeps only the branch for each type.
• A type such as Quantity!(m, s) carries its units, so Metres + Seconds does not compile, and static assert with __traits(compiles, …) tests that it does not.
• A string mixin compiles code that a function wrote, and FieldNameTuple lists a struct’s fields, while __traits(allMembers, …) also lists its methods.
• -betterC keeps the language and needs only the C library, at the cost of the GC, exceptions, classes made with new and most of Phobos; version (D_BetterC) builds one source both ways.