This post is a partial copy of a post of mine from digitalmars.D.learn. Lot of people seem to ignore that place.

This is the only way I have found to create a certain static array at compile time:

int sumSqrt(int n) {
    int result = 0;
    while (n) {
        int digit = n % 10;
        n /= 10;
        result += digit * digit;
    }
    return result;
}
template GenSquares(int n) {
    static if (n < 0)
        const int[] GenSquares = [];
    else
        const int[] GenSquares = GenSquares!(n-1) ~ [sumSqrt(n)];
}
void main() {
    const int CHUNK = 1000;
    static const auto squares = cast(int[CHUNK])GenSquares!(CHUNK-1);
}

That code works with D1, but gives a "recursive expansion" error with D2, this is bad. Can D2 be fixed to have capabilities similar to D1?

I have also tried to write a nicer version of the code that uses just one compile-time function and no templates, and starts as:
struct S(int N) { int[N] a; }
S!(N) genSquares(int N)() { ...

But so far I haven't found a way. If such limit is real, then I think D2 has to be improved to allow such things, because creating a fixed-size array at compile time is one of the main purposes of compile-time functions.

Bye,
bearophile

bearophile wrote:
> This post is a partial copy of a post of mine from digitalmars.D.learn. Lot of people seem to ignore that place.
> 
> This is the only way I have found to create a certain static array at compile time:
> 
> int sumSqrt(int n) {
>     int result = 0;
>     while (n) {
>         int digit = n % 10;
>         n /= 10;
>         result += digit * digit;
>     }
>     return result;
> }
> template GenSquares(int n) {
>     static if (n < 0)
>         const int[] GenSquares = [];
>     else
>         const int[] GenSquares = GenSquares!(n-1) ~ [sumSqrt(n)];
> }
> void main() {
>     const int CHUNK = 1000;
>     static const auto squares = cast(int[CHUNK])GenSquares!(CHUNK-1);
> }
> 
> That code works with D1, but gives a "recursive expansion" error with D2, this is bad. Can D2 be fixed to have capabilities similar to D1?

It's a bug in D1, actually.  The bug was fixed in D2 but not yet in D1. As you increase the value, D1 will just silently segfault eventually. I believe D1 will be fixed in the next release.

> 
> I have also tried to write a nicer version of the code that uses just one compile-time function and no templates, and starts as:
> struct S(int N) { int[N] a; } S!(N) genSquares(int N)() { ...
> 
> But so far I haven't found a way. If such limit is real, then I think D2 has to be improved to allow such things, because creating a fixed-size array at compile time is one of the main purposes of compile-time functions.

It's bug 2569. Nothing fundamental.



> 
> Bye,
> bearophile

On Mon, 25 May 2009 05:57:39 -0400, bearophile <bearophileHUGS@lycos.com> wrote:

>This post is a partial copy of a post of mine from digitalmars.D.learn. Lot of people seem to ignore that place.
>
>This is the only way I have found to create a certain static array at compile time:
>
>int sumSqrt(int n) {
>    int result = 0;
>    while (n) {
>        int digit = n % 10;
>        n /= 10;
>        result += digit * digit;
>    }
>    return result;
>}
>template GenSquares(int n) {
>    static if (n < 0)
>        const int[] GenSquares = [];
>    else
>        const int[] GenSquares = GenSquares!(n-1) ~ [sumSqrt(n)];
>}
>void main() {
>    const int CHUNK = 1000;
>    static const auto squares = cast(int[CHUNK])GenSquares!(CHUNK-1);
>}
>
>That code works with D1, but gives a "recursive expansion" error with D2, this is bad. Can D2 be fixed to have capabilities similar to D1?
>
>I have also tried to write a nicer version of the code that uses just one compile-time function and no templates, and starts as:
>struct S(int N) { int[N] a; }
>S!(N) genSquares(int N)() { ...
>
>But so far I haven't found a way. If such limit is real, then I think D2 has to be improved to allow such things, because creating a fixed-size array at compile time is one of the main purposes of compile-time functions.
>
>Bye,
>bearophile

Your example can be rewritten like this:

int[] genSquares(int n)
{
    int[] result;

    for(; n >= 0; --n)
    {
        int k = n;
        int m;
        while (k) {
            int digit = k % 10;
            k /= 10;
            m += digit * digit;
        }
        result = m ~ result;
    }

    return result;
}

void main() {
    const int CHUNK = 1000;
    static const auto squares = cast(int[CHUNK])genSquares(CHUNK - 1);
}

Works for both compiler versions.

Max Samukha:
> Your example can be rewritten like this: [...]<

Thank you, it works.
I have tried using result~=m; in a forward-directed for loop, but that didn't work. I think because result=m~result; creates a new array, while result~=m; tries to extend it, failing (even if with result~=m; D1 shows an error message that shows the full correct array anyway, strange).

It seems you have to use subtly functional-style code in compile-time functions too. I'll use similar solutions in various situations.

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

Don:

>It's a bug in D1, actually.  The bug was fixed in D2 but not yet in D1. As you increase the value, D1 will just silently segfault eventually. I believe D1 will be fixed in the next release.<

So I'll be unable to loop a template 1000 times in D1 too?


>It's bug 2569. Nothing fundamental.<

It's not fundamental, but fixed-sized arrays seems a very good fit for compile-time functions. So it deserves an improvement.

Thank you for the code and the explanations,
bye,
bearophile

bearophile wrote:
> Max Samukha:
>> Your example can be rewritten like this: [...]<
> 
> Thank you, it works.
> I have tried using result~=m; in a forward-directed for loop, but that didn't work. I think because result=m~result; creates a new array, while result~=m; tries to extend it, failing (even if with result~=m; D1 shows an error message that shows the full correct array anyway, strange).
> 
> It seems you have to use subtly functional-style code in compile-time functions too.
> I'll use similar solutions in various situations.
> 
> ------------------
> 
> Don:
> 
>> It's a bug in D1, actually.  The bug was fixed in D2 but not yet in D1. As you increase the value, D1 will just silently segfault eventually. I believe D1 will be fixed in the next release.<
> 
> So I'll be unable to loop a template 1000 times in D1 too?

Not sure.

> 
> 
>> It's bug 2569. Nothing fundamental.<
> 
> It's not fundamental, but fixed-sized arrays seems a very good fit for compile-time functions. So it deserves an improvement.
No, I meant that there's no fundamental reason why it's not working, it's just one of the many CTFE bugs. They'll all get fixed eventually.

> 
> Thank you for the code and the explanations,
> bye,
> bearophile

bearophile wrote:
>> It's a bug in D1, actually.  The bug was fixed in D2 but not yet in
>> D1. As you increase the value, D1 will just silently segfault
>> eventually. I believe D1 will be fixed in the next release.<
> 
> So I'll be unable to loop a template 1000 times in D1 too?


The problem is that enough recursion will blow up the stack in the compiler. I set a limit below that. But, naturally, for any limit I set someone will try to exceed it.

The solution is to use an iterative algorithm with CTFE, not recursive template expansion.

Walter Bright:
> The problem is that enough recursion will blow up the stack in the compiler. I set a limit below that. But, naturally, for any limit I set someone will try to exceed it.

I accept that some limits exist. For many situations a template nesting of 1000 is plenty. My problems were:
1) The limit of D1 seems different of the limit of D2, so a program I have written for D1 doesn't work with D2.
2) Of course I have first tried to write it with CTFE, but I have failed. First I have tried the simple solution:

int[] genSquares(int n) {
    int[] result;
    for (int i = 0; i < n; i++) {
        int k = i;
        int m;
        while (k) {
            int digit = k % 10;
            k /= 10;
            m += digit * digit;
        }
        result ~= m;
    }
    return result;
}

Then seeing it fail (I cast it into a fixed sized array at compile time), I have tried creating a fixed sized array, but functions can't return them yet. So I have tried to wrap the static array with a struct, but Don has shown this doesn't currently work yet:

struct S(int N) { int[N] a; }

S!(N) genSquares(int N)() {
    S!(N) s;
    for (int i = 0; i < N; i++) {
        int n = i;
        int m = 0;
        while (n) {
            int digit = n % 10;
            n /= 10;
            m += digit * digit;
        }
        s.a[i] = m;
    }

    return s;
}
void main() {
    const int CHUNK = 1000;
    static const auto squares = genSquares!(CHUNK)().a;
}

So I have created the mixed template/ctfe version I have shown in my original post. So far I have written tons of (sometimes quite complex) templates in D :-)

Max Samukha then has gently offered me a working solution, but it's not obvious, it uses a dynamic array, but builds it in a more functional way.

Bye,
bearophile

On Mon, 25 May 2009 14:14:17 -0400, bearophile <bearophileHUGS@lycos.com> wrote:

>Walter Bright:
>> The problem is that enough recursion will blow up the stack in the compiler. I set a limit below that. But, naturally, for any limit I set someone will try to exceed it.
>
>I accept that some limits exist. For many situations a template nesting of 1000 is plenty. My problems were:
>1) The limit of D1 seems different of the limit of D2, so a program I have written for D1 doesn't work with D2.
>2) Of course I have first tried to write it with CTFE, but I have failed. First I have tried the simple solution:
>
>int[] genSquares(int n) {
>    int[] result;
>    for (int i = 0; i < n; i++) {
>        int k = i;
>        int m;
>        while (k) {
>            int digit = k % 10;
>            k /= 10;
>            m += digit * digit;
>        }
>        result ~= m;
>    }
>    return result;
>}
>
>Then seeing it fail (I cast it into a fixed sized array at compile time), I have tried creating a fixed sized array, but functions can't return them yet. So I have tried to wrap the static array with a struct, but Don has shown this doesn't currently work yet:
>
>struct S(int N) { int[N] a; }
>
>S!(N) genSquares(int N)() {
>    S!(N) s;
>    for (int i = 0; i < N; i++) {
>        int n = i;
>        int m = 0;
>        while (n) {
>            int digit = n % 10;
>            n /= 10;
>            m += digit * digit;
>        }
>        s.a[i] = m;
>    }
>
>    return s;
>}
>void main() {
>    const int CHUNK = 1000;
>    static const auto squares = genSquares!(CHUNK)().a;
>}
>
>So I have created the mixed template/ctfe version I have shown in my original post. So far I have written tons of (sometimes quite complex) templates in D :-)
>
>Max Samukha then has gently offered me a working solution, but it's not obvious, it uses a dynamic array, but builds it in a more functional way.
>
>Bye,
>bearophile


It looks like you can workaround the bug by taking a slice of the result to "normalize" the array. This works with both compiler versions:

int[] genSquares(int n) {
    int[] result;
    for (int i = 0; i < n; i++) {
        int k = i;
        int m;
        while (k) {
            int digit = k % 10;
            k /= 10;
            m += digit * digit;
        }
        result ~= m;
    }
    return result[0..n];
}

void main() {
    const int CHUNK = 1000;
    static const auto squares = cast(int[CHUNK])genSquares(CHUNK);
}

But I'd rather use a dynamic array instead until Don fixes the bug :)