Tom S wrote:
> Chad J wrote:
> 
>> Hmmm, why doesn't someone write a D interpreter using templates?
> 
> 
> 
> I'd say it's impractical with the current implementation of templates. Each template instantiation is remembered. You can't just run stuff and forget about it. Think, hundreds of megs of ram to 'interpret' a simple program. That's one of the reasons why ctrace runs so bloody slow :P
> 
> 
> -- 
> Tomasz Stachowiak

Yeah.  This seems to be a big problem with D templates though - they are getting pushed far enough nowadays that their unoptimized implementation is just not enough.  Perhaps we need the D compiler to be a bit more wise about how it instantiates templates.  It should probably consider discarding some templates early (particularly those that lack member functions/classes/structs/whatever), since some of these are unlikely to be instantiated again. Or maybe by default it should just not remember templates at all.  Then it could unroll some of the common tail recursion.  I also hear it generates object code while instantiating - baaad, it should probably do that lazily.  These improvements should help template metaprogramming in general, not just to create weird stuff like a D interpreter in metacode :)

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.

kris escribió:
> Andrei Alexandrescu (See Website For Email) wrote:
>> kris wrote:
>>
>>> Following on from the "Regex Redux thread, it seems to me there's an easy way to execute pure D at compile-time. A few elements are needed:
>>>
>>> 1) the ability to describe a compile-time function call
>>> 2) the facility to pass arguments to it, and recieve a return value
>>> 3) a means of identifiying the D code to execute
>>> 4) a manner in which the pure D is executed
>>> 5) a mechanism for ensuring the executed code is docile
>>
>>
>> 6) Ensuring that the code executing at compile-time has full access to program's symbols.
>>
>> 1-5 define a way to define dual functions in D, which is a good thing. But without (6), they are useless.
> 
> On the contrary, they have access to the arguments passed to them; and to thoose arguments only.
> 
> 

Sorry, I'm just catching up.
How would your regex example work if it can only access the arguments? It wouldn't be able to do "new RegExp".

-- 
Carlos Santander Bernal