I think templates is the wrong way to go for compile-time meta-programming.

There's been some talk recently about executing functions at compile-time by some people, because these people (including me) feel that template recursion and tricks are not the appropriate way to manipulate/parse strings for specialized DSL (domain specific languages).

I will give you some ideas I have, and I would like to know your thoughts about them.

To me, compile time functions should employ the same concepts behind "constant folding": if an expression is composed of compile time constants, the compiler will compute the expression at compile time and replace it with the result.

# int x = 2 + 3;
will be optimized by the compiler to:
# int x = 5;
Here, the compiler computed the expression "2+3" at compile time, and replaced the expression with its result, "5".

The same concept should be applicable to compile time functions. A function is a complicated set of expressions.

Some functions are trivial; they take a set of parameters, do something with them, without calling or depending on other functions, and return the result.
A "trivial" example:
# int add( int x, int y ) { return x + y; }
If they take constant arguments, such functions can surely be computed at compile time without much hassle. Such that a call to
# int Q = add( 10, 12 );
can be replaced, at compile time, with this:
# int Q = 22;

The trick may lie in letting the compiler recognize these kind of functions. A simple solution might me to come up with a new attribute; let's call it "meta":
# meta int add( int x, int y ) { return x + y; }
This attribute will assist the compiler in recognizing that this function can be computed at compile time if it's given constant arguments.

Now, this may not be very useful because of the restriction that meta functions must not call other functions, which is very limiting; so we need to extend it.

If a function takes constant arguments and does call other functions, then it can only be executed at compile time if all of these other functions are meta functions.

example:
# void subtract( int x, int y ) { return add( x, -y ); }
This function calls "add", but add is a meta function that can be executed at compile time, and will be replaced at compile time with:
# void subtract( int x, int y ) { return x - y ); }
So this type of function can definitely be executed at compile time, and thus deserves to be a meta function.

# meta void subtract( int x, int y ) { return add( x, -y ); }

The same idea could be extended to string-manipulating functions.

Using these concepts as basis for compile-time meta-programming might give us another benefit: we don't have to write compile-time functions that repeat the same tasks already done by run-time functions (regex for example); we just have to be careful and design our functions so that they can be meta functions.

The idea is that if you call a meta function with non-constant arguments, the compiler shouldn't complain; it will just treat the function call in this case as a regular function call to a runtime function.

What do you think about this?! Please tell me your opinions.

On Thu, 08 Feb 2007 21:48:50 -0700, Hasan Aljudy wrote:

> I think templates is the wrong way to go for compile-time meta-programming.
 . . .
> What do you think about this?! Please tell me your opinions.

It seems like it is worth considering. I'm not fully convinced the templates should be used for everything compile-time either. The syntax and paradigm seems awkward and doesn't flow naturally for me.

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Justice for David Hicks!"
9/02/2007 3:56:56 PM

On Thu, 08 Feb 2007 21:48:50 -0700, Hasan Aljudy wrote:

> The trick may lie in letting the compiler recognize these kind of
> functions. A simple solution might me to come up with a new attribute;
> let's call it "meta":
> # meta int add( int x, int y ) { return x + y; }
> This attribute will assist the compiler in recognizing that this
> function can be computed at compile time if it's given constant arguments.
> 
> Now, this may not be very useful because of the restriction that meta functions must not call other functions, which is very limiting; so we need to extend it.
> 
> If a function takes constant arguments and does call other functions, then it can only be executed at compile time if all of these other functions are meta functions.
> 

I don't think a meta attribute is need,
if the compiler detects that a function is called with only
constant arguments it should try to inline the function and do constant
folding on it.
If the function calls another function then it should check if constant
folding reduce the arguments to constant and then try to inline and
folding it, if this fails it should just call the function.

If a signal to the compiler is really needed then maybe ! can be used

add!(2,3) would make the compiler look for the template "add!" first and then try to fold "add" if the template is not found.

Hasan Aljudy wrote:
[snip]
> The trick may lie in letting the compiler recognize these kind of functions. A simple solution might me to come up with a new attribute; let's call it "meta":
> # meta int add( int x, int y ) { return x + y; }
> This attribute will assist the compiler in recognizing that this function can be computed at compile time if it's given constant arguments.

This is much in keep with my idea on how metaprogramming should be done, with the little semantic nit that "meta" should be "dual" as add has dual functionality.

The attribute is not even needed if meta-code is flagged as such. My thoughts currently gravitate around the idea of using mixin as an escape into compile-time world. Anything that's printed to standard output in compile-time world becomes code, e.g. (using your function):

mixin
{
  writefln("int x = ", add(10, 20), ";");
}

is entirely equivalent to:

int x = 30;

No annotation is needed on add because mixin clarifies that it's called during compilation. The compiler will complain if add cannot be user dually.

Using mixin and write as separation devices makes it very clear what is to be done when; otherwise, it quickly becomes confusing what code is meant to actually get evaluated eagerly, and what code is to actually be "output" for compilation.

The not-so-nice thing is that we get to manipulate numbers, strings, and arrays, not trees like in LISP.


Andrei

Hasan Aljudy wrote:
> I think templates is the wrong way to go for compile-time meta-programming.
> 
> There's been some talk recently about executing functions at compile-time by some people, because these people (including me) feel that template recursion and tricks are not the appropriate way to manipulate/parse strings for specialized DSL (domain specific languages).
> 
> I will give you some ideas I have, and I would like to know your thoughts about them.
> 
> To me, compile time functions should employ the same concepts behind "constant folding": if an expression is composed of compile time constants, the compiler will compute the expression at compile time and replace it with the result.
> 
> # int x = 2 + 3;
> will be optimized by the compiler to:
> # int x = 5;
> Here, the compiler computed the expression "2+3" at compile time, and replaced the expression with its result, "5".
> 
> The same concept should be applicable to compile time functions. A function is a complicated set of expressions.
> 
> Some functions are trivial; they take a set of parameters, do something with them, without calling or depending on other functions, and return the result.
> A "trivial" example:
> # int add( int x, int y ) { return x + y; }
> If they take constant arguments, such functions can surely be computed at compile time without much hassle. Such that a call to
> # int Q = add( 10, 12 );
> can be replaced, at compile time, with this:
> # int Q = 22;
> 
> The trick may lie in letting the compiler recognize these kind of functions. A simple solution might me to come up with a new attribute; let's call it "meta":
> # meta int add( int x, int y ) { return x + y; }
> This attribute will assist the compiler in recognizing that this function can be computed at compile time if it's given constant arguments.
> 
> Now, this may not be very useful because of the restriction that meta functions must not call other functions, which is very limiting; so we need to extend it.
> 
> If a function takes constant arguments and does call other functions, then it can only be executed at compile time if all of these other functions are meta functions.
> 
> example:
> # void subtract( int x, int y ) { return add( x, -y ); }
> This function calls "add", but add is a meta function that can be executed at compile time, and will be replaced at compile time with:
> # void subtract( int x, int y ) { return x - y ); }
> So this type of function can definitely be executed at compile time, and thus deserves to be a meta function.
> 
> # meta void subtract( int x, int y ) { return add( x, -y ); }
> 
> The same idea could be extended to string-manipulating functions.
> 
> Using these concepts as basis for compile-time meta-programming might give us another benefit: we don't have to write compile-time functions that repeat the same tasks already done by run-time functions (regex for example); we just have to be careful and design our functions so that they can be meta functions.
> 
> The idea is that if you call a meta function with non-constant arguments, the compiler shouldn't complain; it will just treat the function call in this case as a regular function call to a runtime function.
> 
> What do you think about this?! Please tell me your opinions.

This method has been mentioned a few times now ("extention", "static", "plugin" ect...).  If so many people keep coming up with the same idea,  there must be something going for it.

I agree this is probably the best way to go.  I should add (and I've already said this) things marked with "what-ever-we call this" would be evaluated a compile time so to ensure their compiletime-ness.

-Joel

Andrei Alexandrescu (See Website For Email) wrote:
> Hasan Aljudy wrote:
> [snip]
>> The trick may lie in letting the compiler recognize these kind of functions. A simple solution might me to come up with a new attribute; let's call it "meta":
>> # meta int add( int x, int y ) { return x + y; }
>> This attribute will assist the compiler in recognizing that this function can be computed at compile time if it's given constant arguments.
> 
> This is much in keep with my idea on how metaprogramming should be done, with the little semantic nit that "meta" should be "dual" as add has dual functionality.
> 
> The attribute is not even needed if meta-code is flagged as such. My thoughts currently gravitate around the idea of using mixin as an escape into compile-time world. Anything that's printed to standard output in compile-time world becomes code, e.g. (using your function):
> 
> mixin
> {
>   writefln("int x = ", add(10, 20), ";");
> }
> 
> is entirely equivalent to:
> 
> int x = 30;
> 
> No annotation is needed on add because mixin clarifies that it's called during compilation. The compiler will complain if add cannot be user dually.
> 
> Using mixin and write as separation devices makes it very clear what is to be done when; otherwise, it quickly becomes confusing what code is meant to actually get evaluated eagerly, and what code is to actually be "output" for compilation.
> 
> The not-so-nice thing is that we get to manipulate numbers, strings, and arrays, not trees like in LISP.
> 
> 
> Andrei

Wow, I think that's just the perfect solution ..

Andrei Alexandrescu (See Website For Email) wrote:
> Hasan Aljudy wrote:
> [snip]
>> The trick may lie in letting the compiler recognize these kind of functions. A simple solution might me to come up with a new attribute; let's call it "meta":
>> # meta int add( int x, int y ) { return x + y; }
>> This attribute will assist the compiler in recognizing that this function can be computed at compile time if it's given constant arguments.
> 
> This is much in keep with my idea on how metaprogramming should be done, with the little semantic nit that "meta" should be "dual" as add has dual functionality.
> 
> The attribute is not even needed if meta-code is flagged as such. My thoughts currently gravitate around the idea of using mixin as an escape into compile-time world. Anything that's printed to standard output in compile-time world becomes code, e.g. (using your function):
> 
> mixin
> {
>   writefln("int x = ", add(10, 20), ";");
> }
> 
> is entirely equivalent to:
> 
> int x = 30;
> 
> No annotation is needed on add because mixin clarifies that it's called during compilation. The compiler will complain if add cannot be user dually.
> 
> Using mixin and write as separation devices makes it very clear what is to be done when; otherwise, it quickly becomes confusing what code is meant to actually get evaluated eagerly, and what code is to actually be "output" for compilation.
> 
> The not-so-nice thing is that we get to manipulate numbers, strings, and arrays, not trees like in LISP.
> 
> 
> Andrei

Although I like this idea, I fear it will not work for anything hidden in a library (if you are using something that is moved to a .lib, your code will stop working).  Maybe that's ok.  Actually now I think about it, that would be safer, because even if the D compiler could put an "ok" signatures in a library, someone could create fake signatures.

It could get confusing if you don't know which functions will work and which won't.  Perhaps the compiler could help there (spit out a list of functions u can use or something).

I think the compiler would compile these commands on demand and cache them so it doesn't need to do them every time.  That would help a lot. It could even cache results so it only needs to compute them once.

Anyways, there i think there is so much possibility with compile time coding.

-joel

Hasan Aljudy wrote:
> I think templates is the wrong way to go for compile-time meta-programming.
Yes, templates and compile-time programming should be distinct. But the template programming environment and the one you describe (as far as I can see, const-foldable and alias-free are equivalent) are in fact equivalent in my opinion (see my post in 'executing pure D at compile-time' where I that these two things are just syntactically different ways of expressing the same thing).

For this reason, I think that we could relatively easily get nicer environment such as the one you describe, because it is trivially convertable to the already-working template system. Perhaps Walter could do it, and we would be impressed for a while.

But I don't really want that, because later we will come and look at it and think, 'hey, this disallows aliasing, just because we were too lazy back then to support a full compile-time language' and then we will feel stuck with a limited language, just as we now feel stuck with a limited template language.

Or else the Ruby, LISP, and Nemerle people will look at D and say, 'well we can do meta-programming with whole language; why does D (seemingly arbitrarily) only allow meta-programming in a limited subset?'

-----------------

I also think we should consider that the ability of the compile-time language to do type manipulation might not extend to runtime.

A good old type-template just means parameterising the function by type as well as value. Further, a type-tuple is just an array of types (it has .length, it has indexing, and it has basic concatenation). I think we should make this similarity explicit, by actually calling a type-tuple an array of types, giving them D's advanced array features, as well as allowing generic array code to be used on type-arrays.

I think the best way to do this is to unify types with TypeInfo, so that a template Type parameter is just a template value parameter of type TypeInfo, and also having the additional rule that you can do the following:

   const TypeInfo T = foo!(stuff);
   T x; // declare x as type T

This also gives us a nice symmetry between the two varargs approaches: they both pass TypeInfo to the function, but the old one does it at runtime, and the new one does it at compile time.

Furthermore, treating type-tuples as arrays allows nesting of type-tuples, which may occasionally be useful, and which type-tuples currently do not support.

Cheers,

Reiner

janderson wrote:
> Andrei Alexandrescu (See Website For Email) wrote:
>> Hasan Aljudy wrote:
>> [snip]
>>> The trick may lie in letting the compiler recognize these kind of functions. A simple solution might me to come up with a new attribute; let's call it "meta":
>>> # meta int add( int x, int y ) { return x + y; }
>>> This attribute will assist the compiler in recognizing that this function can be computed at compile time if it's given constant arguments.
>>
>> This is much in keep with my idea on how metaprogramming should be done, with the little semantic nit that "meta" should be "dual" as add has dual functionality.
>>
>> The attribute is not even needed if meta-code is flagged as such. My thoughts currently gravitate around the idea of using mixin as an escape into compile-time world. Anything that's printed to standard output in compile-time world becomes code, e.g. (using your function):
>>
>> mixin
>> {
>>   writefln("int x = ", add(10, 20), ";");
>> }
>>
>> is entirely equivalent to:
>>
>> int x = 30;
>>
>> No annotation is needed on add because mixin clarifies that it's called during compilation. The compiler will complain if add cannot be user dually.
>>
>> Using mixin and write as separation devices makes it very clear what is to be done when; otherwise, it quickly becomes confusing what code is meant to actually get evaluated eagerly, and what code is to actually be "output" for compilation.
>>
>> The not-so-nice thing is that we get to manipulate numbers, strings, and arrays, not trees like in LISP.
>>
>>
>> Andrei
> 
> Although I like this idea, I fear it will not work for anything hidden in a library (if you are using something that is moved to a .lib, your code will stop working).  Maybe that's ok.  Actually now I think about it, that would be safer, because even if the D compiler could put an "ok" signatures in a library, someone could create fake signatures.

Good point. This is reasonable. To execute code during compilation it's reasonable to expect transparency. C++ commercial vendors did not really suffer financial loss due to this requirement, and at any rate, OSS is on the rise :o).

> It could get confusing if you don't know which functions will work and which won't.  Perhaps the compiler could help there (spit out a list of functions u can use or something).

Yes, that's a documentation issue. The nice thing is that a plethora of really useful functions (e.g. string manipulation) can be written in D's subset that can be interpreted. Pretty much the entire string library will be meta-executable. No more need for the metastrings lib!

> I think the compiler would compile these commands on demand and cache them so it doesn't need to do them every time.  That would help a lot. It could even cache results so it only needs to compute them once.
> 
> Anyways, there i think there is so much possibility with compile time coding.

Me too. Once compile-time interpretation (and mutation) makes it in, I think there's no fear of efficiency loss anymore. Speed will be comparable to that of any interpreted code, and there are entire communities that don't have a problem with that.

The question is, what is the subset of D that can be interpreted? I'm thinking:

* Basic data types (they will be stored as a dynamically-typed variant anyway), except pointers to functions and delegates.

* Arrays and hashes

* Basic expressions (except 'is', 'delete' et al.)

* if, for, foreach, while, do, switch, continue, break, return

I'm constructing this list thinking what it takes to write basic data manipulation functions. What did I forget?


Andrei

Andrei Alexandrescu (See Website For Email) wrote:
> The question is, what is the subset of D that can be interpreted? I'm thinking:
> 
> * Basic data types (they will be stored as a dynamically-typed variant anyway), except pointers to functions and delegates.
What's wrong with function pointers and delegates? For starters, you need to support them for user-written foreach's, and (as long as they are written in an alias-free form) they are const-foldable.

> I'm constructing this list thinking what it takes to write basic data manipulation functions. What did I forget?
What about structs? They are a plain old data type, and they don't have virtual functions. Is there something tricky with them that I'm missing?

Cheers,

Reiner