The sqrt() example I gave is cute, but not a very interesting reason for doing compile time function execution. So what's the real reason?

A while back, Eric Anderton and Don Clugston showed how one could use template metaprogramming techniques to do, for example compile time regular expressions. It was a marvelous technical demonstration, and showed that essentially any computation could be done, using templates, at compile time.

There were some serious problems, though:

1) They are hard and unintuitive to write (for those not comfortable with functional programming, which is most of us).

2) The result looks awful - templates are just syntactically unsuited to this, even though they're a lot easier on the eye than C++ template metaprograms.

3) This is off-putting enough that some question even having such facilities in the language, as it results in impenetrable code unmaintainable by joe coders.

4) While theoretically capable of any computation, such template metaprogramming had severe practical limitations. Every step of every computation required generating a unique template. This naturally is incredibly slow and memory consumptive (C++ metaprogramming is notorious for taking all night to do a build). Even worse, if you're going to use string templates to parse, say, a 1000 character DSL, the template name generated must include its arguments, so that template identifier will be 1000 characters long. Then, it slices off the first character, and generates another template for the rest (999), then 998, then 997, etc., until 1000 templates are generated averaging 500 characters long. It doesn't take much of that before the whole thing collapses.

5) In casting about for a solution, the compile time regex came up again. This was still strongly disliked.

6) I promised to try and make template metaprogramming less obtuse, and what better way to do that than to obsolete a whole class of templates, replacing them with ordinary functions?

Shhh.. You had me at "cute" ...

L.

Walter Bright wrote:
> The sqrt() example I gave is cute, but not a very interesting reason for doing compile time function execution. So what's the real reason?
> 
> A while back, Eric Anderton and Don Clugston showed how one could use template metaprogramming techniques to do, for example compile time regular expressions. It was a marvelous technical demonstration, and showed that essentially any computation could be done, using templates, at compile time.
> 
> There were some serious problems, though:
> 
> 1) They are hard and unintuitive to write (for those not comfortable with functional programming, which is most of us).
> 
> 2) The result looks awful - templates are just syntactically unsuited to this, even though they're a lot easier on the eye than C++ template metaprograms.
> 
> 3) This is off-putting enough that some question even having such facilities in the language, as it results in impenetrable code unmaintainable by joe coders.
> 
> 4) While theoretically capable of any computation, such template metaprogramming had severe practical limitations. Every step of every computation required generating a unique template. This naturally is incredibly slow and memory consumptive (C++ metaprogramming is notorious for taking all night to do a build). Even worse, if you're going to use string templates to parse, say, a 1000 character DSL, the template name generated must include its arguments, so that template identifier will be 1000 characters long. Then, it slices off the first character, and generates another template for the rest (999), then 998, then 997, etc., until 1000 templates are generated averaging 500 characters long. It doesn't take much of that before the whole thing collapses.
> 
> 5) In casting about for a solution, the compile time regex came up again. This was still strongly disliked.
> 
> 6) I promised to try and make template metaprogramming less obtuse, and what better way to do that than to obsolete a whole class of templates, replacing them with ordinary functions?

I think this is a fantastic feature.  It uses plain old D syntax and offers all the computational power of templates.  Will this work for template functions that follow the rules as well?  Also, is there any way to test whether a function is being executed at run time?  Perhaps by placing a pragma(msg) inside the function body?


Sean

Sean Kelly wrote:
> I think this is a fantastic feature.  It uses plain old D syntax and offers all the computational power of templates.  Will this work for template functions that follow the rules as well?

Yes.

> Also, is there any way to test whether a function is being executed at run time?

Yes, it will be always executed at runtime if it is not in a context where it is required to be folded to a constant.

Walter Bright wrote:
> Even worse, if you're going to use
> string templates to parse, say, a 1000 character DSL, the template name
> generated must include its arguments, so that template identifier will
> be 1000 characters long.

Wait... this sounds too wrong... instantiated templates with string arguments hold the whole string on the template symbol?

(checking myself...)

Ugh... yes, it is. Worse, the string is in hexadecimal...

Using the whole string on the template symbol limits the parameter size.
 On Linux, IIRC, the maximum symbol size is 4096 bytes, which limits
strings to a little less than 2000 bytes using the current scheme.

Is there some rationale for not using an MD5 hash of the string?

1. Although MD5 is not (anymore) a good cryptographic hash, it is fast
and good to avoid collisions;
2. collisions should not be a problem unless the programmer really wants
to collide symbols, for whatever strange reason;
3. it uses a fixed space on symbol name, allowing parameters of
arbitrary size;
4. it reduces the text object memory space for long strings;
5. it should reduce the overhead over the compiler and the linker.

Better yet would be to encode the MD5 hash using a variant of Base64 instead of hexadecimal digits, to make it shorter.

Miles wrote:
> Is there some rationale for not using an MD5 hash of the string?

It's not reversible - no pretty printing, no demangling, etc.

Walter Bright wrote:
> Miles wrote:
>> Is there some rationale for not using an MD5 hash of the string?
> 
> It's not reversible - no pretty printing, no demangling, etc.

For common usage, does it really need to be reversible?

Pretty printing and demangling are only used for debugging purposes, so, this information should go to debug sections of the object file, that are not loaded into memory unless you are running the debugger. And let the debugger use that information to extract what the symbol means.

Miles wrote:
> Walter Bright wrote:
>> Miles wrote:
>>> Is there some rationale for not using an MD5 hash of the string?
>> It's not reversible - no pretty printing, no demangling, etc.
> 
> For common usage, does it really need to be reversible?

Problem is, I can't tell when the uncommon use is required.

> Pretty printing and demangling are only used for debugging purposes, so,
> this information should go to debug sections of the object file, that
> are not loaded into memory unless you are running the debugger. And let
> the debugger use that information to extract what the symbol means.

Don has based some runtime reflection code on demangling names.

Walter Bright wrote:
> Miles wrote:
>> Walter Bright wrote:
>>> Miles wrote:
>>>> Is there some rationale for not using an MD5 hash of the string?
>>> It's not reversible - no pretty printing, no demangling, etc.
>>
>> For common usage, does it really need to be reversible?
> 
> Problem is, I can't tell when the uncommon use is required.
> 
>> Pretty printing and demangling are only used for debugging purposes, so,
>> this information should go to debug sections of the object file, that
>> are not loaded into memory unless you are running the debugger. And let
>> the debugger use that information to extract what the symbol means.
> 
> Don has based some runtime reflection code on demangling names.

Considering that, will it be fair to say that future reflection capabilities will be based off of demangling? Or is there any other ideas up the sleeve about how it's going to be implemented. (trying not to go way off subject, but feeding general curiosity)

Walter Bright wrote:
> Sean Kelly wrote:
>> I think this is a fantastic feature.  It uses plain old D syntax and offers all the computational power of templates.  Will this work for template functions that follow the rules as well?
> 
> Yes.
> 
>> Also, is there any way to test whether a function is being executed at run time?
> 
> Yes, it will be always executed at runtime if it is not in a context where it is required to be folded to a constant.

This looks awesome, by the way!

I don't have this version of dmd yet, but it looks like I can convert any expression to be run at compile time or runtime with not too much extra syntax.

int hack(int a, int b)
{
   return sqrt(a) + b*b;
}

int heck()
{
   // at runtime
   return hack(10, 20);
}

int hick()
{
    // compile time
    mixin("return "~ToString!(hack(11,22))~";");
}

Kevin