www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Template limits

reply 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
May 25 2009
next sibling parent 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

May 25 2009
prev sibling parent reply 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.
May 25 2009
parent reply 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
May 25 2009
next sibling parent 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.

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

May 25 2009
prev sibling parent reply 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.
May 25 2009
parent reply 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
May 25 2009
parent 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 :)
May 26 2009