• bearophile (28/28) May 25 2009 This post is a partial copy of a post of mine from digitalmars.D.learn. ...
• Don (5/39) May 25 2009 It's a bug in D1, actually. The bug was fixed in D2 but not yet in D1.
• Max Samukha (24/52) May 25 2009 Your example can be rewritten like this:
• bearophile (12/15) May 25 2009 Thank you, it works.
• Don (4/29) May 25 2009 No, I meant that there's no fundamental reason why it's not working,
• Walter Bright (6/11) May 25 2009 The problem is that enough recursion will blow up the stack in the
• bearophile (43/46) May 25 2009 I accept that some limits exist. For many situations a template nesting ...
• Max Samukha (24/70) May 26 2009 It looks like you can workaround the bug by taking a slice of the

bearophile <bearophileHUGS lycos.com> writes:

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

Don <nospam nospam.com> writes:

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

Max Samukha <outer space.com> writes:

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.

bearophile <bearophileHUGS lycos.com> writes:

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

Don <nospam nospam.com> writes:

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

Walter Bright <newshound1 digitalmars.com> writes:

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.

bearophile <bearophileHUGS lycos.com> writes:

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

Max Samukha <outer space.com> writes:

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 :)