August 25, 2006
There seems to be a problem with the template system in D, which is that it requires much code duplication to use it for compile-time evaluation.

It seems that template metaprogramming in D must be done by exploiting the constant folding capabilities of the compiler. However, this means that basically any non-trivial function in D must be rewritten to be accessed at compile-time (ie from a template). For instance, finding the index of a substring within a string is generally done by calling the std.string.find functions, but this doesn't work with templates. The following code:

import std.string;
import std.stdio : writefln;

template test(char[] c)
	static assert(find(c, "al") != -1);
	const int test = 5;

int main()
	writefln("%d", test!("alpha"));
	return 0;


template.d(6): static assert  ((find)("alpha","al") != -1) is not evaluatable at
 compile time
template.d(12): template instance template.test!("alpha") error instantiating

I can understand the reason behind this limitation, and I know that there are projects which aim to work around this, such as meta in DDL, but recreating the libraries as compile-time functions seems to be the wrong approach to me. I think a worthier goal would be making some functions accessible at compile-time.

The question: what is required for something to be determinable at compile time?

The answer: it can't rely on any user input or any other types of external info. This means it can't use IO or clocks. But basically everything else can feasibly be computed at compile-time.

So how can we apply this to D, to determine whether a function can safely be evaluated at compile-time (or, in other words, whether it is free of side effects)?

Such a function
1. Can't set or get any global or static variables, because this could lead to a different result each time it is evaluated.
2. Can't call any IO, etc. I presume this is done by assembly interrupts, and other side effects can also be found using them.
3. Can't call any functions which do any of these three things.

If one imagined annotating functions which had these properties, the compiler could check the annotations, and then do any compile-time evaluation it would see fit simply by *running the code*.

Pros of such a system:
1. It would simplify the writing of compile-time-evaluated things, avoiding code duplication.
2. It would blur the line between compile-time and runtime evaluation, perhaps allowing more optimizations/inlining on the compiler's part.
3. If evaluation was done by running the code instead of constant folding, it would be much faster (as I have demonstrated in my tests where the compile-time evaluation of a function took much longer than the runtime evaluation of the same logic).
4. If code were run at compile-time, perhaps compile-time evaluation of functions for which the source code was not accessible would even be possible, just by calling the already-compiled libraries which are accessible.

1. I have absolutely no idea about implementing this in a compiler. Because of problems which may occur due to dependencies between templates, and other tricky situations, this could require arbitrarily many cycles of
    compile a little
    run some code, and fold in the results, so we can
    compile a little more, and repeat.
I am yet to come up with such an example, but I am sure it could exist. This could make compiler implementation very difficult if it needed to be able to do this.
2. This annotation system is very much like a const annotation system and it therefore suffers from the same problems: virus-like spreading through code, and code bloat.
3. Although compile-time evaluation may be possible, serialization may cause difficulties, especially with references, which may stuff up an automatic serialization. Specifically, if a function generated a class at compile-time, how could this be stored in the executable and accessed at runtime? Perhaps the easiest approach is to disallow classes and perhaps even structs for this type of compile-time evaluation, but such a limitation would also be quite disappointing.

If you're still with me here, I admire your patience with me, someone who is only just discovering the power of D and templates. If you have any thoughts on what I say, please comment.


Top | Discussion index | About this forum | D home