In generic programming we can do wonderful things like container classes and template functions.

Using more advanced feature will result in metaprogramming, like the compile time regex.

I wonder if compile time regex is really a thing of practical use.

If I a lot of compile time regex pattern, it is very nice to have compiler error for invalid patterns.

But disadvantages are:
- compile time is increasing fast
- code size is increasing with every new pattern (is it?).

With a parser like Spirit in C++ it would be the same. In the Spirit FAQ, a 78 rule parser was reported with 2 hours compile time.

Well, D might be faster, but it shows that the compile time can increase very fast.

In both cases an external regex or parser generator would make more sense.

Now my questions:
1.) Is metaprogramming really useful or only kind of hype?
2.) Are there examples where a metaprogramming solution is the best way
to solve it?

Frank Benoit (keinfarbton) wrote:
>
> 1.) Is metaprogramming really useful or only kind of hype?

In-language code generation has an advantage over using a standalone preprocessor to perform the same task.  And generated code has the potential to contain fewer bugs than hand-written code, as well as reduce coding time for a project.  Finally, template code in general combined with common optimizer techniques can result in extremely fast code because it is essentially equivalent to hand-optimized code in many cases.  How fast?  Bjarne did a presentation at SDWest regarding some real-world applications where C++ was shown to outperform hand-tuned C and even FORTRAN by an order of magnitude for numeric calculations, and the reason was entirely attributed to the extensive use of template code.  Granted, metaprogramming is but a subset of template programming, but sometimes the line between the two is fairly blurry.

> 2.) Are there examples where a metaprogramming solution is the best way
> to solve it?

Blitz++ uses metaprogramming to gain a measurable speed increase in executable code.  But I think the real power of metaprogramming is contingent upon how well it integrates with the run-time language.  In C++, this integration is really fairly poor.  In D it's much better, but could still be improved.  The ideal situation would be if the syntax of a normal function call could be optimized using metaprogramming if some of the arguments were constants, rather than requiring a special syntax to do so.  Two fairly decent examples of metaprogramming in C++ are expression templates and lambda functions (Boost).


Sean

Good response.  This info should be on a publicly available FAQ.

With respect to compile time regex, the full power of this will not be available until D can better optimize the code that is generated.  I've never seen any benchmark comparisons with the run-time regexes and I assume its because it doesn't end up being much faster. (Correct me if I'm wrong here.)  If this is the case, it is not because metaprogramming is not useful, it is because DMD doesn't do certain optimizations yet.

That said, there will always be a trade off between run-time and compile-time performance when dealing with metaprogramming.  In a systems programming language, usually run-time performance is more important.  Thus metaprogramming definitely has merit in a language like D.  However, if you want faster compiles, use run-time code.

-Craig

"Sean Kelly" <sean@f4.ca> wrote in message news:ekerg7$32b$1@digitaldaemon.com...
> Frank Benoit (keinfarbton) wrote:
>>
>> 1.) Is metaprogramming really useful or only kind of hype?
>
> In-language code generation has an advantage over using a standalone preprocessor to perform the same task.  And generated code has the potential to contain fewer bugs than hand-written code, as well as reduce coding time for a project.  Finally, template code in general combined with common optimizer techniques can result in extremely fast code because it is essentially equivalent to hand-optimized code in many cases.  How fast?  Bjarne did a presentation at SDWest regarding some real-world applications where C++ was shown to outperform hand-tuned C and even FORTRAN by an order of magnitude for numeric calculations, and the reason was entirely attributed to the extensive use of template code.  Granted, metaprogramming is but a subset of template programming, but sometimes the line between the two is fairly blurry.
>
>> 2.) Are there examples where a metaprogramming solution is the best way to solve it?
>
> Blitz++ uses metaprogramming to gain a measurable speed increase in executable code.  But I think the real power of metaprogramming is contingent upon how well it integrates with the run-time language.  In C++, this integration is really fairly poor.  In D it's much better, but could still be improved.  The ideal situation would be if the syntax of a normal function call could be optimized using metaprogramming if some of the arguments were constants, rather than requiring a special syntax to do so.  Two fairly decent examples of metaprogramming in C++ are expression templates and lambda functions (Boost).
>
>
> Sean

Frank Benoit (keinfarbton) wrote:
> In generic programming we can do wonderful things like container classes
> and template functions.
> 
> Using more advanced feature will result in metaprogramming, like the
> compile time regex.
> 
> I wonder if compile time regex is really a thing of practical use.
> 
> If I a lot of compile time regex pattern, it is very nice to have
> compiler error for invalid patterns.
> 
> But disadvantages are:
> - compile time is increasing fast
> - code size is increasing with every new pattern (is it?).

Not necessarily. With the compile-time regex I'm working in, all it does is convert one human-readable string literal (eg, "ab+") into a byte-code string literal. There's no code generation. Executable code size should decrease very slightly, because the regex compilation code isn't included, and there's a bit less memory manipulation.
However, the size of the obj file does increase. If 'early discard' was implemented for templates*, compilation speed would be extremely fast, and there'd be no effect on obj file size.

* 'early discard' = if a template contains only const values, evaluate it, then immediately delete it from the symbol table. Apply this recursively.

> With a parser like Spirit in C++ it would be the same. In the Spirit
> FAQ, a 78 rule parser was reported with 2 hours compile time.
> 
> Well, D might be faster, but it shows that the compile time can increase
> very fast.

AFAIK, D is fast because import system is so much faster than the #include system, and the name lookup rules are simpler. It's like the difference between quicksort and bubblesort; as the complexity increases, the advantage of D becomes greater and greater.

> In both cases an external regex or parser generator would make more sense.
> 
> Now my questions:
> 1.) Is metaprogramming really useful or only kind of hype?
> 2.) Are there examples where a metaprogramming solution is the best way
> to solve it?

I hope to provide some <g>.

Frank Benoit (keinfarbton) wrote:
> In generic programming we can do wonderful things like container classes
> and template functions.
> 
> Using more advanced feature will result in metaprogramming, like the
> compile time regex.
> 
> I wonder if compile time regex is really a thing of practical use.
> 
> If I a lot of compile time regex pattern, it is very nice to have
> compiler error for invalid patterns.
> 
> But disadvantages are:
> - compile time is increasing fast
> - code size is increasing with every new pattern (is it?).
> 
> With a parser like Spirit in C++ it would be the same. In the Spirit
> FAQ, a 78 rule parser was reported with 2 hours compile time.
> 
> Well, D might be faster, but it shows that the compile time can increase
> very fast.
> 
> In both cases an external regex or parser generator would make more sense.
> 
> Now my questions:
> 1.) Is metaprogramming really useful or only kind of hype?

Naturally, I will speak to what I know, which is Pyd. A goal of Pyd is to wrap as much of the D language as possible, as easily as possible. This requires meta-programming techniques: Template functions, function meta-info, typeof, tuples.

Thanks to these techniques, I can completely wrap a D function without knowing its return type, argument types, or even its name, by just saying:

def!(foo);

"Wrapping" a function implies generating a function (with C linkage) that accepts (in the case of the Python API) some PyObject* arguments and returns a PyObject*; somehow calls the function with the PyObject* arguments; and somehow converts the function's return value to a PyObject*. All of this can occur automatically, given only an alias to the function. The generated code is probably only slightly slower than if the wrapper had been written by hand (though I have yet to test Pyd's performance). It might even be faster, if the hand-written code uses PyArg_ParseTuple to convert the arguments. (Which determines the types to convert to at runtime, using a format string. Pyd determines the types at compile-time.)

And, regarding compilation times: Pyd compiles nigh-instantly. Boost::Python is notorious for long (sometimes in the range of hours) compilation times. D seems to be just plain better at this than C++.

> 2.) Are there examples where a metaprogramming solution is the best way
> to solve it?

I would say that using Pyd (or even Boost::Python) is much more pleasant than the raw Python/C API.

As soon as you start working with metaprogramming, you start wanting compile-time equivalents of things you have at runtime. I've started working on a compile-time writef-style formatter, for instance. (Due to bug 586, it only works with types at the moment, and not other compile-time values like ints and function aliases. But you can specify field widths, and so forth.) This thing is based heavily on stuff in Don Clugston's meta library (have you had the same idea, Don?), and serves to unify many of the string-conversion templates that are floating around (Don's Nameof, that itoa template, and so on).

-- 
Kirk McDonald
Pyd: Wrapping Python with D
http://pyd.dsource.org

Thanks for all your answers.
I think be imagination of what template are good for is getting more clear.

On Mon, 27 Nov 2006 14:28:15 +0100, "Frank Benoit (keinfarbton)" <benoit@tionex.removethispart.de> wrote:

>Well, D might be faster, but it shows that the compile time can increase very fast.

When doing the metaprogramming, the compiler is basically acting as an interpreter as opposed to a compiler. It is nothing more advanced or freaky than that.

A lot of work is already done in interpreted languages already. In fact, since that term is often applied to languages that actually compile to virtual machine bytecode (e.g. Python) and since other languages that compile to virtual machine bytecode are considered compilers (e.g. Java) there is no clear line between compilers and interpreters these days. Interpreters often do a bit of pre-compiling (to intermediate code), and compilers often do a bit of interpreting (precalculating constant expressions, as well as metaprogramming).

The reason C++ metaprogramming is slow is (1) because it has never been a big priority for compiler developers, and (2) because C++ template metaprogramming forces programmers to work in indirect and inefficient ways, substituting specialisation for simple conditionals and recursion for simple loops.

Support metaprogramming properly and it need be no slower than, for instance, using a scripting language for code generation - an annoyingly common thing. In fact, the compiler could simply generate a compiled code generator, run it, and then pick up the output for the next compilation stage if performance was that big a deal. This could give better performance than writing code generation tools in C++, since the compiler knows its own internal representations and could create compiled code generators that generate this directly rather than generating source code.

Getting back to scripting languages, Perl was originally described as 'programmers glue' or 'programmers duct tape' since it was written as an extension to awk, which was widely used for simple code generation. The web page generation thing obviously became the real Perl killer app, but that was a bit later. So clearly code generation is quite a common necessity, or why would people write tools to make it easier?

People have even used XSLT to generate source code - strange, but true.

But using a scripting language for code generation is a bad thing, since it means you have to learn two languages to develop one application. Why not just have all the tools you need in one language?

>In both cases an external regex or parser generator would make more sense.
>
>Now my questions:
>1.) Is metaprogramming really useful or only kind of hype?
>2.) Are there examples where a metaprogramming solution is the best way
>to solve it?

These are really the same questions, since metaprogramming is useful if and only if it is the best way to solve certain problems. So...


Consider that the whole point of a library is that as much complexity as possible should be handled once (in the library itself) rather than over-and-over again by the users of the library. But at the same time, that shouldn't add unnecessary run-time overheads. And also, you shouldn't duplicate code - ideally, each algorithm should be written once with all the needed flexibility - not in several separately maintained versions.

Well, even generic data structures can reach a point where you need 'metaprogramming' to handle them properly - where you want lots of flexibility. Managing bloat can lead to even more complexity, since different applications require different trade-offs between code size and speed, so that can be a few more options there.

How many options can there be? Well, maybe you have a particular data structure that you need, but sometimes you need it in memory and sometimes you need it in a disk file. Sometimes, you even need it split between memory and a file (e.g. specialised caching, or handling transactions with commit and rollback). Sometimes you need maximum performance and want to do any moves using memcpy, other times you want to support arbitrary objects and cannot assume that memcpy is safe so you need to use copy constructors and assignment operators etc. And maybe there are optional features to your data structures - e.g. it's a tree data structure that can hold certain kinds of summary information in nodes to optimise certain search operations, but only if that summary information is useful for the current application. For example, you might want efficient subscripted access to an associative container - easy if each node knows how many items are in its subtree, impossible otherwise.

My experience is that doing this kind of thing in C++ is easy enough when dealing with the search and iteration algorithms, but insert and delete algorithms can get very complex to manage because there are so many variations. You end up with fragments of each algorithm, each with multiple variants, selected through specialisation. But thats a nightmare, so in practice you end up writing several separate libraries, increasing the bloat, and losing some of the flexibility that comes from having all the options in one library. Not to mention the maintenance headache from having several copies of each algorithm.

The D way - each algorithm remaining a single algorithm, but with a few static-if blocks - is a lot easier. For some things, you can even prototype with run-time ifs and convert to static-ifs later just by adding the word 'static' here and there.


Of course this sounds like just making libraries overcomplex, but the whole point of a library is that as much complexity as possible should be handled once (in the library itself) rather than over-and-over again by the users of the library. But at the same time, that shouldn't add unnecessary run-time overheads.

But then again, the truth is that most programmers simply won't write libraries to be that flexible because of the complexity. That isn't how programming should be, though, it's just a limitation of current programming languages - you can't reasonably do some of the things you should be able to do easily.


Right now, I don't think I'd use a metaprogramming-based regular expression or parser library, and certainly not in C++. A lot of current metaprogramming stuff is experimental, and not really to be used for serious work. Some of those experiments remind me of the old obfuscated C contest. But todays experiments are important - without them, tomorrow will be no better than today.

Or perhaps you'd rather be driving a horse and cart, since after all the earliest cars were clearly impractical and obviously horses were fine up until then, which PROOVES there could never be a real need for cars, eh! ;-)

-- 
Remove 'wants' and 'nospam' from e-mail.

"Steve Horne" <stephenwantshornenospam100@aol.com> wrote in message news:tqrmm25d9217h5r45hem4jnp2g1hi6oh7o@4ax.com...

> When doing the metaprogramming, the compiler is basically acting as an interpreter as opposed to a compiler. It is nothing more advanced or freaky than that.
>
> A lot of work is already done in interpreted languages already. In fact, since that term is often applied to languages that actually compile to virtual machine bytecode (e.g. Python) and since other languages that compile to virtual machine bytecode are considered compilers (e.g. Java) there is no clear line between compilers and interpreters these days. Interpreters often do a bit of pre-compiling (to intermediate code), and compilers often do a bit of interpreting (precalculating constant expressions, as well as metaprogramming).
>
> The reason C++ metaprogramming is slow is (1) because it has never been a big priority for compiler developers, and (2) because C++ template metaprogramming forces programmers to work in indirect and inefficient ways, substituting specialisation for simple conditionals and recursion for simple loops.
>
> Support metaprogramming properly and it need be no slower than, for instance, using a scripting language for code generation - an annoyingly common thing. In fact, the compiler could simply generate a compiled code generator, run it, and then pick up the output for the next compilation stage if performance was that big a deal. This could give better performance than writing code generation tools in C++, since the compiler knows its own internal representations and could create compiled code generators that generate this directly rather than generating source code.

A little off the topic, but not really, as it spins off of the idea of a compiler as an interpreter.  I always thought it would be an interesting exercise to make a language where metaprogramming is not only possible, but nearly as full-featured as the actual code.  That is, templates (or whatever they'd be called, because they'd be far more advanced) would be a script for the compiler, which could even be compiled to bytecode.  The input would be language constructs -- symbols, statements, expressions -- and the output would be code which could then be compiled.  It'd basically be a scriptable compiler.

The problem that I always run into in this thought experiment is the syntax. I mean, for a lot of cases, template syntax is great.  When you're writing a simple type-agnostic stack class, you just need to be able to substitute T for the type of the data everywhere; it's simple, straightforward, and easy to understand.  Using another syntax for that would be kind of clumsy.

Maybe, then, this metaprogramming language would have several different constructs, just as the real language does.  It might have a templating system for replacing types, symbols, and constants in code.  It might then have other constructs for dynamic code modification and generation.

// The namespace is where the function will be generated
metafunction WrapFunction(symbol func, namespace owner = func.namespace)
{
    assert(func.isFunction, "WrapFunction: '" ~ func.nameof ~ "' is not a
function");

    // Generation of identifiers from strings
    symbol wrappedName = symbol(func.nameof ~ "_wrapped");

    // Create a new function, and set its first param name to 's'
    int function(MDState) wrappedFunc = new function int(MDState);
    wrappedFunc.params[0].name = identifier("s");

    // An array of symbols for calling the real function
    symbol[] params;

    // The code for the generated function
    Statement[] code;

    foreach(i, param; func.params)
    {
        // Add the new param name to the symbol array
        params ~= symbol("param" ~ i);

        // VarDeclaration takes type, symbol of the name to declare,
        // and an initialization expression.
        // DotExp takes the two sides of the dot.
        // TemplateFunctionCallExp takes a name, a list of types, and a
        // list of params (not used here).
        code ~= new VarDeclaration(param.typeof, params[$ - 1],
                new DotExp(symbol("s"),
                new TemplateFunctionCallExp(symbol("pop"), param.typeof)));
    }

    // Get the function return (if any)
    if(is(func.returnType == void) == false)
    {
        // Get the return type in the local "ret" and push it, then
        // return 1
        code ~= new VarDeclaration(func.returnType, symbol("ret"),
                new CallExp(func, expand(params));

        code ~= new CallExp(new DotExp(symbol("s"), symbol("push")),
symbol("ret"));
        code ~= new ReturnExp(1);
    }
    else
    {
        // Just call the function and return 0
        code ~= new CallExp(func, expand(params));
        code ~= new ReturnExp(0);
    }

    // Set the wrapped function's code to the code array
    wrappedFunc.code = code;

    // Put the function in the owner namespace's symbol table
    owner[wrappedName] = wrappedFunc;
}

...

int fork(int x, float y)
{
    writefln("fork: x = ", x, " y = ", y);
    return 65;
}

WrapFunction!(fork);

That call would produce the code:

int fork_wrapped(MDState s)
{
    int param0 = s.pop!(int)();
    float param1 = s.pop!(float)();
    int ret = fork(param0, param1);
    s.push(ret);
    return 1;
}

;)

Steve Horne wrote:
> On Mon, 27 Nov 2006 14:28:15 +0100, "Frank Benoit (keinfarbton)"
> <benoit@tionex.removethispart.de> wrote:
> 
>> Well, D might be faster, but it shows that the compile time can increase
>> very fast.
> 
> When doing the metaprogramming, the compiler is basically acting as an
> interpreter as opposed to a compiler. It is nothing more advanced or
> freaky than that.
> 
Interesting...particularly as what I really want is basically the opposite.  I expect PyD to just exactly fill my needs in a few more months.  Currently I'm working in Python, and my only option has been Pyrex (not a bad choice in itself!), but PyD should be a much better choice, as D is a better underlying match to Python than C is, and what I'll be doing is largely translating chunks of Python into a compilable language for speed.

Of course, what would be really interesting would be a runtime version of D, with runtime type assignment, etc., but without the kind of bloat that would occur if this were done with templates.

(OTOH, I must admit that I'm guessing at the amount of bloat that a generic template would add.  They don't add that much in Eiffel or Ada code, but they were impossibly bloated the last time I tried it in C++ [admittedly that's over a decade ago].)

Kirk McDonald wrote:
> Frank Benoit (keinfarbton) wrote:
>> In generic programming we can do wonderful things like container classes
>> and template functions.
>>
>> Using more advanced feature will result in metaprogramming, like the
>> compile time regex.
>>
>> I wonder if compile time regex is really a thing of practical use.
>>
>> If I a lot of compile time regex pattern, it is very nice to have
>> compiler error for invalid patterns.
>>
>> But disadvantages are:
>> - compile time is increasing fast
>> - code size is increasing with every new pattern (is it?).
>>
>> With a parser like Spirit in C++ it would be the same. In the Spirit
>> FAQ, a 78 rule parser was reported with 2 hours compile time.
>>
>> Well, D might be faster, but it shows that the compile time can increase
>> very fast.
>>
>> In both cases an external regex or parser generator would make more sense.
>>
>> Now my questions:
>> 1.) Is metaprogramming really useful or only kind of hype?
> 
> Naturally, I will speak to what I know, which is Pyd. A goal of Pyd is to wrap as much of the D language as possible, as easily as possible. This requires meta-programming techniques: Template functions, function meta-info, typeof, tuples.
> 
> Thanks to these techniques, I can completely wrap a D function without knowing its return type, argument types, or even its name, by just saying:
> 
> def!(foo);
> 
> "Wrapping" a function implies generating a function (with C linkage) that accepts (in the case of the Python API) some PyObject* arguments and returns a PyObject*; somehow calls the function with the PyObject* arguments; and somehow converts the function's return value to a PyObject*. All of this can occur automatically, given only an alias to the function. The generated code is probably only slightly slower than if the wrapper had been written by hand (though I have yet to test Pyd's performance). It might even be faster, if the hand-written code uses PyArg_ParseTuple to convert the arguments. (Which determines the types to convert to at runtime, using a format string. Pyd determines the types at compile-time.)
> 
> And, regarding compilation times: Pyd compiles nigh-instantly. Boost::Python is notorious for long (sometimes in the range of hours) compilation times. D seems to be just plain better at this than C++.
> 
>> 2.) Are there examples where a metaprogramming solution is the best way
>> to solve it?
> 
> I would say that using Pyd (or even Boost::Python) is much more pleasant than the raw Python/C API.
> 
> As soon as you start working with metaprogramming, you start wanting compile-time equivalents of things you have at runtime. I've started working on a compile-time writef-style formatter, for instance. (Due to bug 586, it only works with types at the moment, and not other compile-time values like ints and function aliases. But you can specify field widths, and so forth.) This thing is based heavily on stuff in Don Clugston's meta library (have you had the same idea, Don?), 

Indeed I have. The tuple stuff makes this all really appealing. In particular, I've played around with a writef() equivalent which checks the parameters for 'easy' cases, and splits it off into:
-> single string only
-> strings, chars, and integers
-> floating point, arrays, and objects.

This way you can avoid linking in the floating-point conversion code if you're not using it, keeping the code size down. In fact, it ought to be possible to remove the usage of TypeInfo completely, moving it all into compile-time.

and serves
> to unify many of the string-conversion templates that are floating around (Don's Nameof, that itoa template,  and so on).
That was mine as well, BTW.