Executing pure D at compile-time

[Reiner Pope]

Another approach is to harness what's already possible in templates, and 
just ask the compiler to do a little more. In many cases, the template 
coding style is nice, but there's just a lot of syntactical junk lying 
around. Consider atoi (from ddl's meta.conv):

# /* *****************************************************
#  *  char [] itoa!(long n);
#  */
# template itoa(long n)
# {
#     static if (n<0)
#         const char [] itoa = "-" ~ itoa!(-n);
#     else static if (n<10L)
#         const char [] itoa = decimaldigit!(n);
#     else
#         const char [] itoa = itoa!(n/10L) ~ decimaldigit!(n%10L);
# }

It's easy to understand, but compared to a practically identical 
implementation in 'pure D', it's very clumsy:

# char[] itoa(long n)
# {
#     if (n < 0)
#         return itoa(-n);
#     if (n < 10L)
#         return digits[n..n+1];
#     return itoa(n/10L) ~ digits(n%10L);
# }

It's clumsy for a few reasons:
   - you have to write 'const char[] itoa = ' whenever you mean return
   - you have to write 'static if' instead of 'if'
   - you don't explicitly get to document the return type, which even 
led to the comment shown, which would just be wasteful in 'pure D'

However, looking at it from the other point of view, a compiler could 
easily evaluate the 'pure D' version at compile time by converting all 
the 'if's to 'static if's, the 'return's to 'const char[] itoa =', the 
function calls to template insantiations and changing the prototype from 
'char[] itoa' to 'template itoa.'

Additionally, the compiler could then recognise this as a function call, 
and discard the intermediate templates, avoiding some of the memory 
issues involved with compile-time programming.

In fact, if you can avoid the aliasing issue[1] you can convert any D 
code in this fashion, as long as you keep away from asm. Avoiding the 
aliasing issue effectively means that the functions you call can't 
modify their parameters, which satisfies the requirements of template D 
that all variables are 'const'. This means that all statements will have 
to be converted into assign statements (eg Foo = x;)

The two not-so-obvious conversions are:
  - mutable variables
  - loops.

However, they turn out to not too difficult. Mutable variables:

# int x = 1;
# x = foo(x);
# x++;
# x = foo(x);

becomes

# const int x__0 = 1;
# const int x__1 = foo!(x__0);
# const int x__2 = x__1 + 1;
# const int x__3 = foo!(x__2);

and loops are converted into recursion:

# int x = 5;
# for (int i = 0; i < 5; i++)
# {
#    x++;
# }
# return x;

becomes:

# const int x = 5;
# template __loop(int x, int i=0)
# {
#   static if (! (i__0 < 5) )
#       alias x x__final;
#   else
#   {
#       const int x__0 = x + 1;
#
#       const int i__0 = i + 1;
#       alias __loop!(x__0, i__0).x__final x__final;
#   }
# }
# const int Value = __loop!(x);

I believe that all of these conversions could be done automatically, 
which would allow 'pure D' code[2] to be used in templates.

However, I prefer a more general approach such as kris suggested, 
because it does allow aliasing (which can certainly be useful), 
including any type of D code. The point of this post is both to show 
that, although templates are quite capable for metaprogramming, they are 
syntactically ugly, and using a no-pointer subset of 'pure D' in 
templates can be considered just a syntactic improvement.

Cheers,

Reiner

[1]Basically, this involves using const to show that your function is 
indeed 'pure functional'. Annotating functions thus would be useful for 
more than just compile-time programming, I'm sure.

Avoiding the aliasing issue allows everything to be converted to static 
single assignment (which means that it is treated as const), allowing 
const-folding. You could trivially meet this requirement by only 
allowing built-in types (and not even arrays), but you may be able to 
permit more with a 'const' system. In particular, I'm pretty sure that a 
'const' array could easily be const folded, and you could probably 
support structs and const pointer-to-structs. I'm dubious about classes, 
though.

[2]Of course, I mean the alias-free subset thereof.