Experiments with template meta-programming in D

I want to create a typed implementation of the relational algebra using the D programming language’s template meta-programming and compile-time evaluation. Please keep in mind that I’m new to D, so I may be misusing (or abusing) its capabilities.

I’ll be using D version 2, which is not compatible with version 1 of the language. You won’t need to know any D to follow along, but you will need to understand C++ templates.

The relational algebra

In the terminology of the relational algebra, a database table is a relation; a row is a tuple; a column name is an attribute; and the set of possible values for an attribute is its domain.

My aim is to create a typed implementation of the relational algebra in D, where one can write code like the following:

// module Employees class Name : Attribute!string { /* ... */ } class Age : Attribute!uint { /* ... */ } class Employees : Relation!(Name, Age) { /* ... */ } alias Employees.Tuple Employee; Employees e = new Employees; foreach (Employee x; e) { writeln(x.name ~ ": " ~ x.age); } Employee e1 = new Employee("John Doe", 30); auto ages = e.π!(Age); // This should cause a compilation error // (PhoneNumber not an attribute of relation Employees): e.π!(PhoneNumber);

D uses the syntactically unambiguous !() for template parameters, so C++’s vector<T>(5, t) becomes vector!(T)(5, t). The first set of parentheses is optional if there is only one type parameter: vector!T(5, t).

Note the accessors x.name and x.age generated automatically from the type information passed to Relation.

π is the project operation (pronounced like the verb, not the noun). It selects certain attributes from the relation and discards the rest.

The type of ages will be Relation!(Age).

D’s auto keyword means that the type of ages will be deduced automatically from the expression on the right-hand side of the =.

Mixins

My first stab at implementing the Tuple structure follows:

relation.d

import std.stdio; import std.string; class Attribute(Domain) {} class NTuple(Attributes...) { mixin( __traits(identifier, Attributes[0]) ~ " " ~ toLower(__traits(identifier, Attributes[0])) ~ ";"); } class Name : Attribute!string {} class Age : Attribute!uint {} void main() { auto t = new NTuple!(Name, Age)(); writeln(typeid(typeof(t))); writeln(typeid(typeof(t.name))); }

Attribute and NTuple are class templates — Attribute is equivalent to the C++ template <typename Domain> class Attribute {};.

The mixin statement, called a string mixin, compiles the textual content of its argument as D code. In this case, it is exactly the same as declaring Name name;.

__traits allows the program to access, at compile time, information internal to the compiler (in this case an identifier as a string literal).

$ dmd relation.d && ./relation

relation.NTuple!(Name,Age).NTuple
relation.Name

Template mixins

That worked, but I am only defining the first attribute (name) of our tuple. For the rest, I’ll use a recursively-expanded template mixin:

relation.d

import std.stdio; import std.string; class Attribute(Domain) {} class NTuple(Attributes...) { mixin DefineAttribute!(Attributes); private mixin template DefineAttribute(T, Ts...) { mixin( __traits(identifier, T) ~ " " ~ toLower(__traits(identifier, T)) ~ ";"); static if (Ts.length > 0) { mixin DefineAttribute!(Ts); } } } class Name : Attribute!string {} class Age : Attribute!uint {} void main() { auto t = new NTuple!(Name, Age)(); writeln(typeid(typeof(t))); writeln(typeid(typeof(t.name))); writeln(typeid(typeof(t.age))); }

$ dmd relation.d && ./relation

relation.NTuple!(Name,Age).NTuple
relation.Name
relation.Age

A template mixin behaves somewhat like copying the body of the mixin template DefineAttribute declaration, and pasting it where mixin DefineAttribute!(Attributes); appears (with the appropriate substitution of compile-time parameters).

This template mixin is recursively defined in terms of itself. The body of the static if statement is only compiled when the boolean condition (evaluated at compile time) is true; so the recursion stops when Ts.length is 0.

Note the use of variadic templates, where Ts... (and Attributes...) is a type tuple packaging up the (0 or more) types specified in the template instantiation.

Template symbol lookup

Unfortunately the above code doesn’t compile when I use relation.d as a module called from external client code:

relation.d

import std.string; class Attribute(Domain) {} class NTuple(Attributes...) { mixin DefineAttribute!(Attributes); private mixin template DefineAttribute(T, Ts...) { mixin( __traits(identifier, T) ~ " " ~ toLower(__traits(identifier, T)) ~ ";"); static if (Ts.length > 0) { mixin DefineAttribute!(Ts); } } }

client.d

import relation; import std.stdio; class Name : Attribute!string {} class Age : Attribute!uint {} void main() { auto t = new NTuple!(Name, Age)(); writeln(typeid(typeof(t))); writeln(typeid(typeof(t.name))); writeln(typeid(typeof(t.age))); }

$ dmd client.d relation.d

relation.d(11): Error: undefined identifier Name, did you mean variable name?

Andrei Alexandrescu explains in his book The D Programming Language:

“Templates are entirely modular: Code inside a template looks up symbols at the template’s definition site. This is a desirable property because it means you can absorb and understand a template by just analyzing its definition.

“In contrast, a mixin template looks up symbols at the instantiation site.”

The error isn’t from my mixin, but from the NTuple template. This template may use a mixin, but it itself contains the equivalent of straight-out saying Name name; Age age;. And in this module (relation) Name and Age are not defined.

(Note that each .d source file constitutes a module named after the filename.)

Let’s take another look at the string mixin (not the template mixin). It is inside a parameterized scope (which happens to be a template mixin, but don’t let that confuse you) and within this scope, the type parameter “T” is a valid identifier too! Even more valid than “Name”, as we have seen.

relation.d

import std.string; class Attribute(Domain) {} class NTuple(Attributes...) { mixin DefineAttribute!(Attributes); private mixin template DefineAttribute(T, Ts...) { mixin( "T " ~ toLower(__traits(identifier, T)) ~ ";"); static if (Ts.length > 0) { mixin DefineAttribute!(Ts); } } }

client.d

$ dmd client.d relation.d && ./client

relation.NTuple!(Name,Age).NTuple
client.Name
client.Age

Much better. I’m starting to regain the faith that this is going to be possible.

The project operation

Leaving aside NTuple for now, I want to implement the project operation. (When I say “implement” I mean just the types and signatures, for now.)

relation.d

class Attribute(Domain) {} class Relation(Attributes...) { // The PROJECT operation Relation!(ProjectedAttributes) π(ProjectedAttributes...)() { return new Relation!(ProjectedAttributes); } }

client.d

import relation; import std.stdio; class Name : Attribute!string {} class Age : Attribute!uint {} class PhoneNumber : Attribute!string {} void main() { auto r1 = new Relation!(Name, Age); writeln(typeid(r1)); auto r2 = r1.π!(PhoneNumber); writeln(typeid(r2)); }

$ dmd client.d relation.d && ./client

relation.Relation!(Name,Age).Relation
relation.Relation!(PhoneNumber).Relation

Clearly I shouldn’t be able to get a Relation with a PhoneNumber from a Relation with only Name & Age; I’m going to have to restrict the types I allow in the project operation. After all, the whole point of this exercise is to get the compiler to catch errors such as this. Template constraints to the rescue! The following should only compile if all type parameters to π are present in the Relation object’s type parameters.

relation.d

$ dmd client.d relation.d

Assertion failed: (fd && fd->inferRetType), function mangle, file mangle.c, line 81.

Perhaps I was a bit naïve expecting that to work — mixing higher-order template “functions” (like allSatisfy) with regular functions. However I wasn’t expecting to crash the compiler!

Using a proper templatey predicate works better: The compiler now catches projections with the wrong attributes.

relation.d

import std.typetuple; class Attribute(Domain) {} class Relation(Attributes...) { // The PROJECT operation Relation!(ProjectedAttributes) π(ProjectedAttributes...)() if (ProjectedAttributes.length > 0 && allSatisfy!(attributeOfRelation, ProjectedAttributes)) { return new Relation!(ProjectedAttributes); } // Tests whether a type T is present in the Relation's Attributes. private template attributeOfRelation(T) { enum attributeOfRelation = (staticIndexOf!(T, Attributes) != -1); } }

$ dmd client.d relation.d

client.d(13): Error: template instance π!(PhoneNumber) does not match template declaration π(ProjectedAttributes...) if (ProjectedAttributes.length > 0 && allSatisfy!(attributeOfRelation,ProjectedAttributes))

attributeOfRelation makes use of D’s “eponymous template rule”: If a template defines a sole member with the same name as the template, then instantiations like attributeOfRelation(U) are automatically expanded by the compiler to attributeOfRelation(U).attributeOfRelation.

Finally, a working program:

relation.d

client.d

$ dmd -unittest client.d relation.d && ./client

relation.Relation!(Name,Age).Relation
relation.Relation!(Name).Relation

Note the use of D’s built-in unit testing facility (where I’m asserting that R.π!(B) is not a valid type).

Conclusions

Clearly I have a lot of work left to do, but I’m going to call it a day. The hardest parts are still ahead (how am I going to specify conditions for σ, the select operation?) but I’m feeling pretty confident in D’s abilities.

And look at those error messages! Imagine what the equivalent C++ template errors would look like (not to mention that variadic templates aren’t even possible in C++03).

I really like D, but its current implementation still has some bugs to iron out. The compiler assertion failure found in section 5, above, doesn’t seem too serious (it was invalid code anyway). But an earlier version of this article ran into a bug using string.toLower at compile-time, which remained un-fixed for 10 months. And in my previous experience with D, a year ago now, the very first program I tried to write suffered a run-time error caused by a bug in the standard library’s Array class. However that bug was promptly fixed, and things should only get better from here.

(Note that the above only applies to D version 2; D version 1 is considered stable, but has a slightly less compelling feature-set.)