Some of us who have the knack of writing metaprograms in D know that many algorithms can be implemented with both recursive templates and CTFE. A simple example is map:

Recursive template instantiation:

template staticMap(alias pred, A...)
{
    static if (A.length)
        alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
}

CTFE:

template staticMap(alias pred, A)
{
    mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
}

private string _staticMap(size_t len)
{
    string result;
    if (len)
    {
        result ~= "pred!(A[0])";
        for(size_t i = 1, i < len; ++i)
        {
            result ~= ", pred!(A[" ~ to!string(i) ~ "])";
        }
    }
    return result;
}

It is not easy to decide which approach to implement in a library because both have drawbacks.

Can anybody give informed advice as to which one is preferable in practice? Or should a library provide both?

On 01/06/2011 07:49 PM, Max Samukha wrote:
> template staticMap(alias pred, A...)
> {
> static if (A.length)
> alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
> }
>

Should be:

template staticMap(alias pred, A...)
{
    static if (A.length)
        alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
    else
        alias TypeTuple!() staticMap;
}

On Thu, 06 Jan 2011 12:49:19 -0500, Max Samukha <spambox@d-coding.com> wrote:

> Some of us who have the knack of writing metaprograms in D know that many algorithms can be implemented with both recursive templates and CTFE. A simple example is map:
>
> Recursive template instantiation:
>
> template staticMap(alias pred, A...)
> {
>      static if (A.length)
>          alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
> }
>
> CTFE:
>
> template staticMap(alias pred, A)
> {
>      mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
> }
>
> private string _staticMap(size_t len)
> {
>      string result;
>      if (len)
>      {
>          result ~= "pred!(A[0])";
>          for(size_t i = 1, i < len; ++i)
>          {
>              result ~= ", pred!(A[" ~ to!string(i) ~ "])";
>          }
>      }
>      return result;
> }
>
> It is not easy to decide which approach to implement in a library because both have drawbacks.
>
> Can anybody give informed advice as to which one is preferable in practice? Or should a library provide both?

CTFE is generally easier to write/understand and more generic than doing the same thing in templates. However, there are some serious flaws in how DMD currently handles CT strings (and arrays in general) which can lead extremely complex CTFE code to be incorrect, very slow to compile or crash DMD outright. For example, I initially implemented a compile-time reflection to runtime-time reflection system for an improved std.variant using CTFE, but had to switch to templates/conditional compilation instead.  (see https://jshare.johnshopkins.edu/rjacque2/public_html/) See bug 1382 (http://d.puremagic.com/issues/show_bug.cgi?id=1382).

On Thursday, January 06, 2011 09:49:19 Max Samukha wrote:
> Some of us who have the knack of writing metaprograms in D know that many algorithms can be implemented with both recursive templates and CTFE. A simple example is map:
> 
> Recursive template instantiation:
> 
> template staticMap(alias pred, A...)
> {
>      static if (A.length)
>          alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
> }
> 
> CTFE:
> 
> template staticMap(alias pred, A)
> {
>      mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
> }
> 
> private string _staticMap(size_t len)
> {
>      string result;
>      if (len)
>      {
>          result ~= "pred!(A[0])";
>          for(size_t i = 1, i < len; ++i)
>          {
>              result ~= ", pred!(A[" ~ to!string(i) ~ "])";
>          }
>      }
>      return result;
> }
> 
> It is not easy to decide which approach to implement in a library because both have drawbacks.
> 
> Can anybody give informed advice as to which one is preferable in practice? Or should a library provide both?

I suppose that in theory, I would say to use templates for things that really are intended to always be used at compile time and CTFE for functions which would make sense both for compile time and runtime. But whether that's actually the best practice (particularly given the current state of dmd and CTFE), I don't know.

Personally, I think what generally happens in that when I'm trying to do something which needs to be done at compile time, I use CTFE if a function already exists which will do what I want, and I use a template if it doesn't. Or if it's something that I know that I need to be used both at compile time and runtime, then I make it a function for use with CTFE. I think that in at least one case, I've created a template for use at compile time and a function for use at runtime so that I could have additional checks or different behavior at runtime (I think that I had it throw an exception at runtime, which you can't do at compile time), but that's not the norm.

I don't know. I've rarely sat down and tried to decide whether something should be a template or a CTFE-able function. I think that it most cases I've either been creating a function for runtime and possible used it also at compile time, or I've needed something at compile time, so I've created a template.

- Jonathan M Davis

On 06/01/11 17:49, Max Samukha wrote:
> Some of us who have the knack of writing metaprograms in D know that
> many algorithms can be implemented with both recursive templates and
> CTFE. A simple example is map:
>
> Recursive template instantiation:
>
> template staticMap(alias pred, A...)
> {
> static if (A.length)
> alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
> }
>
> CTFE:
>
> template staticMap(alias pred, A)
> {
> mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
> }
>
> private string _staticMap(size_t len)
> {
> string result;
> if (len)
> {
> result ~= "pred!(A[0])";
> for(size_t i = 1, i < len; ++i)
> {
> result ~= ", pred!(A[" ~ to!string(i) ~ "])";
> }
> }
> return result;
> }
>
> It is not easy to decide which approach to implement in a library
> because both have drawbacks.
>
> Can anybody give informed advice as to which one is preferable in
> practice? Or should a library provide both?

Put each of those implementations in its own file, then call it several times. Look at the binary size for each implementation, also run `strings ctfeTest` if you're on a *nix. This should give you your answer :)

-- 
Robert
http://octarineparrot.com/

Actually they are not that related, you may solve a problem with each of them but this is different.
What makes CTFE awesome is that you use same function for runtime and compile-time, without a single change.
The answer to your question is just in this very definition i believe.

> It is not easy to decide which approach to implement in a library because both have drawbacks.
And one fills the holes of the other.

> Can anybody give informed advice as to which one is preferable in practice? Or should a library provide both?
I can't guarantee the "informed" part but,
Between your two implementations it is obvious which one, after you answer the question:
What you want it to be, runtime? compile-time? both?

On 01/06/2011 09:28 PM, Robert Clipsham wrote:
>
> Put each of those implementations in its own file, then call it several
> times. Look at the binary size for each implementation, also run
> `strings ctfeTest` if you're on a *nix. This should give you your answer :)
>

The problem is they are not easy to compare using artificial tests. For example, there is a hard-wired limit to template nesting depth in the compiler. And with the number of input elements less than this limit, the difference in results seems to be insignificant.

BTW, if we want to be taken seriously such limits should be configurable. Why the depth of 500 and not 600? I wonder where the value comes from.

Ok, I think I will simply implement both variants and let the user choose. Thanks for the responses.

Max Samukha wrote:
> On 01/06/2011 09:28 PM, Robert Clipsham wrote:
>>
>> Put each of those implementations in its own file, then call it several
>> times. Look at the binary size for each implementation, also run
>> `strings ctfeTest` if you're on a *nix. This should give you your answer :)
>>
> 
> The problem is they are not easy to compare using artificial tests. For example, there is a hard-wired limit to template nesting depth in the compiler. And with the number of input elements less than this limit, the difference in results seems to be insignificant.
> 
> BTW, if we want to be taken seriously such limits should be configurable. Why the depth of 500 and not 600? I wonder where the value comes from.

It's about the largest value it can be before a compiler stack overflow occurs.

On 01/07/2011 03:12 PM, Don wrote:
> Max Samukha wrote:
>> On 01/06/2011 09:28 PM, Robert Clipsham wrote:
>>>
>>> Put each of those implementations in its own file, then call it several
>>> times. Look at the binary size for each implementation, also run
>>> `strings ctfeTest` if you're on a *nix. This should give you your
>>> answer :)
>>>
>>
>> The problem is they are not easy to compare using artificial tests.
>> For example, there is a hard-wired limit to template nesting depth in
>> the compiler. And with the number of input elements less than this
>> limit, the difference in results seems to be insignificant.
>>
>> BTW, if we want to be taken seriously such limits should be
>> configurable. Why the depth of 500 and not 600? I wonder where the
>> value comes from.
>
> It's about the largest value it can be before a compiler stack overflow
> occurs.

I meant the value should not be a magical number hard-coded somewhere in template.c. One can configure stack size and it should be possible to configure a dmd build with adjusted nesting value.

On Thu, 06 Jan 2011 12:49:19 -0500, Max Samukha <spambox@d-coding.com> wrote:

> Some of us who have the knack of writing metaprograms in D know that many algorithms can be implemented with both recursive templates and CTFE. A simple example is map:
>
> Recursive template instantiation:
>
> template staticMap(alias pred, A...)
> {
>      static if (A.length)
>          alias TypeTuple!(pred!(A[0]), staticMap!(A[1..$])) staticMap;
> }
>
> CTFE:
>
> template staticMap(alias pred, A)
> {
>      mixin("alias TypeTuple!(" ~ _staticMap(A.length) ~ ") staticMap;");
> }
>
> private string _staticMap(size_t len)
> {
>      string result;
>      if (len)
>      {
>          result ~= "pred!(A[0])";
>          for(size_t i = 1, i < len; ++i)
>          {
>              result ~= ", pred!(A[" ~ to!string(i) ~ "])";
>          }
>      }
>      return result;
> }
>
> It is not easy to decide which approach to implement in a library because both have drawbacks.
>
> Can anybody give informed advice as to which one is preferable in practice? Or should a library provide both?

You should prefer CTFE IMO.  Templates can leave a trail of instantiated templates in the exe.  The compiler does not trim anything out that's only used at compile time, but I think with CTFE it does not instantiate as many templates.  I'd guess the exe size would be significantly larger for the template solution for a large number of elements.

-Steve