Some thoughts on templates and compile-time evaluation.

[Reiner Pope]

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;
}

produces

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.

Problems:
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.

Cheers,

Reiner