## digitalmars.D - ch-ch-update: series, closed-form series, and strides

- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 30 2009
- dsimcha <dsimcha yahoo.com> Jan 30 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 30 2009
- Jarrett Billingsley <jarrett.billingsley gmail.com> Jan 30 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 30 2009
- Bill Baxter <wbaxter gmail.com> Jan 30 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 30 2009
- Don <nospam nospam.com> Jan 31 2009
- Neal Becker <ndbecker2 gmail.com> Feb 07 2009
- Bill Baxter <wbaxter gmail.com> Jan 30 2009
- bearophile <bearophileHUGS lycos.com> Jan 30 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 31 2009
- Ary Borenszweig <ary esperanto.org.ar> Jan 31 2009
- grauzone <none example.net> Jan 31 2009
- Brian Palmer <d brian.codekitchen.net> Jan 31 2009
- "Simen Kjaeraas" <simen.kjaras gmail.com> Jan 31 2009
- Sean Kelly <sean invisibleduck.org> Jan 31 2009
- Michel Fortin <michel.fortin michelf.com> Jan 31 2009
- Ary Borenszweig <ary esperanto.org.ar> Jan 31 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 31 2009
- Ary Borenszweig <ary esperanto.org.ar> Jan 31 2009
- Ary Borenszweig <ary esperanto.org.ar> Jan 31 2009
- Christopher Wright <dhasenan gmail.com> Jan 31 2009
- Ary Borenszweig <ary esperanto.org.ar> Jan 31 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 31 2009
- Don <nospam nospam.com> Jan 31 2009
- Christopher Wright <dhasenan gmail.com> Jan 31 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 31 2009
- Ary Borenszweig <ary esperanto.org.ar> Jan 31 2009
- Derek Parnell <derek psych.ward> Jan 31 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 31 2009
- Derek Parnell <derek psych.ward> Jan 31 2009
- Michel Fortin <michel.fortin michelf.com> Jan 31 2009
- Frits van Bommel <fvbommel REMwOVExCAPSs.nl> Jan 31 2009
- Jason House <jason.james.house gmail.com> Jan 31 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Jan 31 2009
- Sean Kelly <sean invisibleduck.org> Feb 03 2009
- "Steven Schveighoffer" <schveiguy yahoo.com> Feb 03 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Feb 03 2009
- "Steven Schveighoffer" <schveiguy yahoo.com> Feb 03 2009
- "Joel C. Salomon" <joelcsalomon gmail.com> Feb 03 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Feb 03 2009
- Derek Parnell <derek psych.ward> Feb 03 2009
- "Steven Schveighoffer" <schveiguy yahoo.com> Feb 03 2009
- Lars Kyllingstad <public kyllingen.NOSPAMnet> Feb 04 2009
- "Joel C. Salomon" <joelcsalomon gmail.com> Feb 04 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Feb 03 2009
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Feb 03 2009
- Jarrett Billingsley <jarrett.billingsley gmail.com> Jan 31 2009
- Jarrett Billingsley <jarrett.billingsley gmail.com> Jan 31 2009
- "Denis Koroskin" <2korden gmail.com> Feb 03 2009
- "Denis Koroskin" <2korden gmail.com> Feb 03 2009
- Bill Baxter <wbaxter gmail.com> Feb 03 2009
- Don <nospam nospam.com> Jan 31 2009
- Bill Baxter <wbaxter gmail.com> Jan 31 2009

I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e); This means: * The state of the series consists of two values, which start as a[0] = 1 and a[1] = 1. This state will be stored inside the returned object in-situ (no dynamic allocation). * The means to compute the n+1'th element given the n'th and the n-1'th is a[n-1] + a[n]. The series object takes care of everything - keeping score, rotating buffers, advancing state, you name it. Walter sent me examples of famous series (e.g. Taylor, approximations of pi, etc.) that I want to put in as examples. I can't wait the next release so I can share this all with you guys! Feedback and suggestions welcome! (I know, I need to add the iota range presto!) Andrei

Jan 30 2009

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s articleI've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e); This means: * The state of the series consists of two values, which start as a[0] = 1 and a[1] = 1. This state will be stored inside the returned object in-situ (no dynamic allocation). * The means to compute the n+1'th element given the n'th and the n-1'th is a[n-1] + a[n]. The series object takes care of everything - keeping score, rotating buffers, advancing state, you name it. Walter sent me examples of famous series (e.g. Taylor, approximations of pi, etc.) that I want to put in as examples. I can't wait the next release so I can share this all with you guys! Feedback and suggestions welcome! (I know, I need to add the iota range presto!) Andrei

Is the code to this stuff posted anywhere yet? I'd be interested to read some of it. I actually learned a decent amount of template idioms by reading the old-school std.algorithm, so I'm curious how some of this stuff is implemented.

Jan 30 2009

dsimcha wrote:Is the code to this stuff posted anywhere yet? I'd be interested to read some of it. I actually learned a decent amount of template idioms by reading the old-school std.algorithm, so I'm curious how some of this stuff is implemented.

Thanks for the interest! Much obliged: http://ssli.ee.washington.edu/~aalexand/d/algorithm.d http://ssli.ee.washington.edu/~aalexand/d/range.d http://ssli.ee.washington.edu/~aalexand/d/functional.d Andrei

Jan 30 2009

Jarrett Billingsley wrote:On Fri, Jan 30, 2009 at 10:48 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:dsimcha wrote:Is the code to this stuff posted anywhere yet? I'd be interested to read some of it. I actually learned a decent amount of template idioms by reading the old-school std.algorithm, so I'm curious how some of this stuff is implemented.

http://ssli.ee.washington.edu/~aalexand/d/algorithm.d http://ssli.ee.washington.edu/~aalexand/d/range.d http://ssli.ee.washington.edu/~aalexand/d/functional.d

Shouldn't ClosedFormSeries.next, uh, increment _n? <_< But very, very cool.

Ouch, fixed. Thanks! Andrei

Jan 30 2009

On Fri, Jan 30, 2009 at 10:48 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:dsimcha wrote:Is the code to this stuff posted anywhere yet? I'd be interested to read some of it. I actually learned a decent amount of template idioms by reading the old-school std.algorithm, so I'm curious how some of this stuff is implemented.

Thanks for the interest! Much obliged: http://ssli.ee.washington.edu/~aalexand/d/algorithm.d http://ssli.ee.washington.edu/~aalexand/d/range.d http://ssli.ee.washington.edu/~aalexand/d/functional.d

Shouldn't ClosedFormSeries.next, uh, increment _n? <_< But very, very cool.

Jan 30 2009

Andrei Alexandrescu wrote: [snip] Oh, and I forgot: an embryonic Heap container is to be found in std.algorithm. Haven't figured how best to define heap growth yet. This is because it would be based on e.g. the controversial operator ~= for arrays. Andrei

Jan 30 2009

On Sat, Jan 31, 2009 at 12:12 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows.

This sounds interesting! So you'll have diagonal, banded, upper/lower triangular, symmetric, strided and dense matrices? How about 2D slices? --bb

Jan 30 2009

Bill Baxter wrote:On Sat, Jan 31, 2009 at 12:12 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows.

This sounds interesting! So you'll have diagonal, banded, upper/lower triangular, symmetric, strided and dense matrices? How about 2D slices?

Sparse matrices too. For dense block matrices I'm thinking of a type like this: alias BlockMatrix!(float, 3, [0, 2, 1]) M3; This defines a block rectangular matrix with three dimensions laid out in the order specified: In this case, M3 is laid out as a collection of column-order submatrices of 2 dimensions. (I deliberately chose a slightly odd example.) The last parameter of BlockMatrix can be any permutation of 0, 1, and 2, thus dictating how the dimensions are laid out. For an obvious example, here's a Fortran-compatible block matrix with column-major layout: alias BlockMatrix!(double, 2, [1, 0]) FortranMatrix; So it's pretty easy to choose any layout for any matrix with any number of dimensions. This matrix defines ranges that crawl it, called hyperplanes. There is a "natural" hyperplane that doesn't need any stride, and that's the cut along the dimension that varies slowest. That cut is the most efficient because it really has the layout of a (littler) BlockMatrix itself. Continuing on the M3 example, a "row" in that matrix has type: alias BlockMatrix!(float, 2, [1, 0]) M3Row; which is obtained by chopping the first element in the array [0, 2, 1] into [2, 1], and then decrementing what's left into [1, 2]. So if you have: M3 m; auto subM = m[3]; you get that smaller BlockMatrix with all amenities its larger cousin offered. But if you want a cut along a different dimension, a strided range will be returned. Jagged, banded, diagonal, fixed-size, and sparse layouts come naturally and will be hopefully supported in a mixable-and-matchable form (e.g. I want a block matrix of 3x3 matrices). I want to focus on storage for now, put it in the standard library, to then allow great scientific programmers like you guys to use those storages as a common data format on top of which cool algorithms can be implemented. Andrei

Jan 30 2009

Andrei Alexandrescu wrote:Jagged, banded, diagonal, fixed-size, and sparse layouts come naturally and will be hopefully supported in a mixable-and-matchable form (e.g. I want a block matrix of 3x3 matrices). I want to focus on storage for now, put it in the standard library, to then allow great scientific programmers like you guys to use those storages as a common data format on top of which cool algorithms can be implemented.

This sounds like the perfect approach. Everything's built around the storage format.

Jan 31 2009

One thing that I've found from various c++ vector/matrix libs, is that the most useful have flexible storage backends. In other words, all of them can allocate their own storage that they 'own', but the most useful can also wrap a matrix 'view' around existing storage. This allows interworking with other libraries.

Feb 07 2009

On Sat, Jan 31, 2009 at 1:40 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Bill Baxter wrote:On Sat, Jan 31, 2009 at 12:12 PM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows.

This sounds interesting! So you'll have diagonal, banded, upper/lower triangular, symmetric, strided and dense matrices? How about 2D slices?

Sparse matrices too. For dense block matrices I'm thinking of a type like this:

Whoa... excellent. I didn't even dare ask about sparse, or block sparse, or n-dimensional arrays.alias BlockMatrix!(float, 3, [0, 2, 1]) M3; This defines a block rectangular matrix with three dimensions laid out in the order specified: In this case, M3 is laid out as a collection of column-order submatrices of 2 dimensions. (I deliberately chose a slightly odd example.) The last parameter of BlockMatrix can be any permutation of 0, 1, and 2, thus dictating how the dimensions are laid out. For an obvious example, here's a Fortran-compatible block matrix with column-major layout: alias BlockMatrix!(double, 2, [1, 0]) FortranMatrix;

Nice. Maybe you can have some predefined symbols for Fortran and C layouts too, so users don't have to think about it.So it's pretty easy to choose any layout for any matrix with any number of dimensions. This matrix defines ranges that crawl it, called hyperplanes. There is a "natural" hyperplane that doesn't need any stride, and that's the cut along the dimension that varies slowest. That cut is the most efficient because it really has the layout of a (littler) BlockMatrix itself. Continuing on the M3 example, a "row" in that matrix has type: alias BlockMatrix!(float, 2, [1, 0]) M3Row; which is obtained by chopping the first element in the array [0, 2, 1] into [2, 1], and then decrementing what's left into [1, 2]. So if you have: M3 m; auto subM = m[3]; you get that smaller BlockMatrix with all amenities its larger cousin offered. But if you want a cut along a different dimension, a strided range will be returned. Jagged, banded, diagonal, fixed-size, and sparse layouts come naturally and will be hopefully supported in a mixable-and-matchable form (e.g. I want a block matrix of 3x3 matrices). I want to focus on storage for now, put it in the standard library, to then allow great scientific programmers like you guys to use those storages as a common data format on top of which cool algorithms can be implemented.

Excellent plan. This sounds like a great rallying point for numerics in D2. But get those ranges done first! --bb

Jan 30 2009

Andrei Alexandrescu:foreach (e; take(10, fib)) writeln(e);

I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

Jan 30 2009

bearophile wrote:Andrei Alexandrescu:foreach (e; take(10, fib)) writeln(e);

I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

SPJ held a gun to my head and said: "take(10, fib)". Andrei

Jan 31 2009

Andrei Alexandrescu escribió:bearophile wrote:Andrei Alexandrescu:foreach (e; take(10, fib)) writeln(e);

I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

SPJ held a gun to my head and said: "take(10, fib)".

Who is SPJ? I find "take(10, fib)" more readable: take 10 from fib. Same order.

Jan 31 2009

Ary Borenszweig wrote:Andrei Alexandrescu escribió:bearophile wrote:foreach (e; take(10, fib)) writeln(e);

I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

SPJ held a gun to my head and said: "take(10, fib)".

Who is SPJ? I find "take(10, fib)" more readable: take 10 from fib. Same order.

I prefer the other way around. There's another argument for take(fib, 10) that isn't just about taste: if fib was an array, you could write fib.take(10). Weren't there discussions to allow a.F(b...) for F(a,b...) in general?

Jan 31 2009

Andrei Alexandrescu Wrote:bearophile wrote:Andrei Alexandrescu:

Andrei

Yeah, but in Haskell they say "take 10 fib" because of partial function application, it's important to decide which parameter is most likely to be useful in the last positions even if it doesn't read as well. That doesn't apply in D, unless you and Walter have been working even more magic behind the scenes that you haven't talked about yet. ;)

Jan 31 2009

On Sat, 31 Jan 2009 14:35:50 +0100, Ary Borenszweig <ary esperanto.org.ar> wrote:Andrei Alexandrescu escribiÃ³:bearophile wrote:foreach (e; take(10, fib)) writeln(e);

I think take(fib, 10) is quite better. I presume the API of those things will need about a year of usage to become refined. Bye, bearophile

Who is SPJ?

http://en.wikipedia.org/wiki/Simon_Peyton_JonesI find "take(10, fib)" more readable: take 10 from fib. Same order.

Yeah, me too. "Take fib from 10" sounds backwards. -- Simen

Jan 31 2009

bearophile wrote:Andrei Alexandrescu:foreach (e; take(10, fib)) writeln(e);

I think take(fib, 10) is quite better.

I like function calls that read like a sentence. Here I'd read take(10, fib) as "take 10 from fib". The only advantage of reversing the arguments is that it might decompose well into the property syntax: fib.take(10). Sean

Jan 31 2009

On 2009-01-31 15:17:40 -0500, Sean Kelly <sean invisibleduck.org> said:I like function calls that read like a sentence. Here I'd read take(10, fib) as "take 10 from fib". The only advantage of reversing the arguments is that it might decompose well into the property syntax: fib.take(10).

How about fib[0..10]? -- Michel Fortin michel.fortin michelf.com http://michelf.com/

Jan 31 2009

Andrei Alexandrescu escribió:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e);

That is *SO* awesome!!

Jan 31 2009

Ary Borenszweig wrote:Andrei Alexandrescu escribió:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e);

That is *SO* awesome!!

Thanks! Constant-space factorial is just a line away: auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e); writes: 1 1 2 6 24 120 720 5040 40320 362880 And this lousy series approximating pi: auto piapprox = series!("a[n] + (n & 1 ? 4. : -4.) / (2 * n + 3)")(4.); foreach (e; take(200, piapprox)) writeln(e); Very slowly convergent. :o) Andrei

Jan 31 2009

Andrei Alexandrescu escribió:Ary Borenszweig wrote:Andrei Alexandrescu escribió:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges. Also Stride is provided. The Matrix container (speaking of scientific computing with D!) will support various representational choices, most importantly the ones endorsed by high-performance libraries. For Matrix, Stride is an important component as I'm sure anyone who's ever written a matrix knows. http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html Back to series. Finally my dream has come true: I can define a decent Fibonacci series clearly and efficiently in one line of code. No more idiotic recursive function that takes exponential time to finish! auto fib = series!("a[n-1] + a[n]")(1, 1); // write 10 Fibonacci numbers foreach (e; take(10, fib)) writeln(e);

That is *SO* awesome!!

Thanks! Constant-space factorial is just a line away: auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e); writes: 1 1 2 6 24 120 720 5040 40320 362880 And this lousy series approximating pi: auto piapprox = series!("a[n] + (n & 1 ? 4. : -4.) / (2 * n + 3)")(4.); foreach (e; take(200, piapprox)) writeln(e); Very slowly convergent. :o)

Nice! :-) I showed the Fibonacci example to a friend of mine and he said "that string stuff scares me a little". The same happens to me. What kind of error do you get if you mistype something in that string expression? Can you pass a delegate instead of a string? Something like: auto fib = series!((Range a, int n) { return a[n-1] + a[n]; })(1, 1); That seems much safe and will probably give a reasonable error if you mistype something. I know, it's longer than the previous one. But it would be nice if D had the following rule (or something similar to it): "if a delegate doesn't return, the last statement is converted to a return" (and you can ommit the semicolon). So now you can write: auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1); Still a little longer than the original, but you get all the benefits of not using a string.

Jan 31 2009

Ary Borenszweig escribió:Andrei Alexandrescu escribió:Ary Borenszweig wrote:

That is *SO* awesome!!

Thanks! Constant-space factorial is just a line away: auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e); writes: 1 1 2 6 24 120 720 5040 40320 362880 And this lousy series approximating pi: auto piapprox = series!("a[n] + (n & 1 ? 4. : -4.) / (2 * n + 3)")(4.); foreach (e; take(200, piapprox)) writeln(e); Very slowly convergent. :o)

Nice! :-) I showed the Fibonacci example to a friend of mine and he said "that string stuff scares me a little". The same happens to me. What kind of error do you get if you mistype something in that string expression? Can you pass a delegate instead of a string? Something like: auto fib = series!((Range a, int n) { return a[n-1] + a[n]; })(1, 1); That seems much safe and will probably give a reasonable error if you mistype something. I know, it's longer than the previous one. But it would be nice if D had the following rule (or something similar to it): "if a delegate doesn't return, the last statement is converted to a return" (and you can ommit the semicolon). So now you can write: auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1); Still a little longer than the original, but you get all the benefits of not using a string.

Ah... But I can see the problem with delegates. I guess with strings you just mix them in a bigger expression and it's like inlining the call. With delegates you can't do that. So there's also a performance tradeoff...

Jan 31 2009

Ary Borenszweig wrote:Ah... But I can see the problem with delegates. I guess with strings you just mix them in a bigger expression and it's like inlining the call. With delegates you can't do that. So there's also a performance tradeoff...

If it's an alias, it should be inlinable. The frontend doesn't do that, though, apparently (according to your compile time viewer).

Jan 31 2009

Christopher Wright escribió:Ary Borenszweig wrote:Ah... But I can see the problem with delegates. I guess with strings you just mix them in a bigger expression and it's like inlining the call. With delegates you can't do that. So there's also a performance tradeoff...

If it's an alias, it should be inlinable. The frontend doesn't do that, though, apparently (according to your compile time viewer).

The compile-time view doesn't show inlining. That happens later, I think.

Jan 31 2009

Ary Borenszweig wrote:Andrei Alexandrescu escribió: Nice! :-) I showed the Fibonacci example to a friend of mine and he said "that string stuff scares me a little". The same happens to me. What kind of error do you get if you mistype something in that string expression?

Let me see. Say I made the mistake of using "b": auto fib = series!("a[n-1] + b[n]")(1, 1); std/functional.d(185): static assert "Bad binary function: a[n] + b[n-1] for types Cycle!(int[]) and uint. You need to use an expression using symbols a and n." Heck, that's even better than compiler's own error messages. Unfortunately, the line where the actual instantiation was invoked is not shown. I think that's entirely doable though. Say I forget to close a bracket: auto fib = series!("a[n] + a[n-1")(1, 1); The compiler penalizes that by never finishing compiling. That's a bug.Can you pass a delegate instead of a string? Something like: auto fib = series!((Range a, int n) { return a[n-1] + a[n]; })(1, 1);

Not right now because delegate literals can't be templates. But I talked about that with Walter and he'll make it work.That seems much safe and will probably give a reasonable error if you mistype something. I know, it's longer than the previous one. But it would be nice if D had the following rule (or something similar to it): "if a delegate doesn't return, the last statement is converted to a return" (and you can ommit the semicolon). So now you can write: auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1); Still a little longer than the original, but you get all the benefits of not using a string.

Incidentally, I was talking to Walter about the shorter delegate form and he convinced me that it's too risky to have semantics depend on only one semicolon. But omitting the type names from a literal delegate is something we're mulling over. The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad. Andrei

Jan 31 2009

Andrei Alexandrescu wrote:Ary Borenszweig wrote:Andrei Alexandrescu escribió: Nice! :-) I showed the Fibonacci example to a friend of mine and he said "that string stuff scares me a little". The same happens to me. What kind of error do you get if you mistype something in that string expression?

Let me see. Say I made the mistake of using "b": auto fib = series!("a[n-1] + b[n]")(1, 1); std/functional.d(185): static assert "Bad binary function: a[n] + b[n-1] for types Cycle!(int[]) and uint. You need to use an expression using symbols a and n." Heck, that's even better than compiler's own error messages. Unfortunately, the line where the actual instantiation was invoked is not shown. I think that's entirely doable though.

In BLADE, what I did was provide an error message as an alternate return value from the inner templates. This is then passed down through the higher-level functions. At the user level, instead of mixing in code to invoke the function, it mixes in a static assert(0, errormsg) instead. Then there is an error ONLY on the line of user code. You can only achieve these perfect error messages if you have a mixin statement in the user code, unfortunately. Of course, using return values to indicate errors is so 1970's. Compile-time assert exception catching would be so much better... But a simple change to the static assert handling would get us most of the way there.Say I forget to close a bracket: auto fib = series!("a[n] + a[n-1")(1, 1); The compiler penalizes that by never finishing compiling. That's a bug.

There's a few cases in bugzilla about mismatched brackets. Some of them cause segfaults.Can you pass a delegate instead of a string? Something like: auto fib = series!((Range a, int n) { return a[n-1] + a[n]; })(1, 1);

Not right now because delegate literals can't be templates. But I talked about that with Walter and he'll make it work.That seems much safe and will probably give a reasonable error if you mistype something. I know, it's longer than the previous one. But it would be nice if D had the following rule (or something similar to it): "if a delegate doesn't return, the last statement is converted to a return" (and you can ommit the semicolon). So now you can write: auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1); Still a little longer than the original, but you get all the benefits of not using a string.

Incidentally, I was talking to Walter about the shorter delegate form and he convinced me that it's too risky to have semantics depend on only one semicolon. But omitting the type names from a literal delegate is something we're mulling over. The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad. Andrei

Jan 31 2009

Andrei Alexandrescu wrote:The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad.

Yes, but they don't interact with an IDE.

Jan 31 2009

Christopher Wright wrote:Andrei Alexandrescu wrote:The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad.

Yes, but they don't interact with an IDE.

It's the IDE that doesn't yet interact with them. Andrei

Jan 31 2009

Andrei Alexandrescu escribió:Christopher Wright wrote:Andrei Alexandrescu wrote:The truth is, the reasons against using strings for short functions are shrinking. I mean, you don't want to not use strings just to not use strings, right? I hope I convinced you that strings are unbeatable for short functions that don't need access to local state, their efficiency is exemplary, and their error messages are not half bad.

Yes, but they don't interact with an IDE.

It's the IDE that doesn't yet interact with them.

Hmm... How can the IDE tell that some T in a template, if it's a string, must have "a" and "n" as their parameters in expressions, their type, etc.? Anyway, I like the usage of strings if it's short and doesn't local state, you've convinced me. :-) As for the errors, the compiler should hold a stack of template instances invocations (same for string mixins), and add those in any error message report. I'll try to do that in Descent to see if it's enough.

Jan 31 2009

On Sat, 31 Jan 2009 07:22:17 -0800, Andrei Alexandrescu wrote:

And syntax-highlighting editors just love them ;-) Knowing which strings contain code and which don't is a piece of cake, no? -- Derek Parnell Melbourne, Australia skype: derek.j.parnell

Jan 31 2009

Derek Parnell wrote:On Sat, 31 Jan 2009 07:22:17 -0800, Andrei Alexandrescu wrote:

And syntax-highlighting editors just love them ;-) Knowing which strings contain code and which don't is a piece of cake, no?

The language can help here. q{stuff} is a "token string" which presumably contains code, whereas the other strings presumably don't. In my editor, q{code} comes off as highlighted. So I think in the future it's a good bet for both programmers and editors to consider q{} quotes as containing code. Andrei

Jan 31 2009

On Sat, 31 Jan 2009 16:26:08 -0800, Andrei Alexandrescu wrote:The language can help here. q{stuff} is a "token string"

I was not aware of the q{} syntax. That should work for smart editors. -- Derek Parnell Melbourne, Australia skype: derek.j.parnell

Jan 31 2009

On 2009-01-31 19:26:08 -0500, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:The language can help here. q{stuff} is a "token string" which presumably contains code, whereas the other strings presumably don't. In my editor, q{code} comes off as highlighted. So I think in the future it's a good bet for both programmers and editors to consider q{} quotes as containing code.

Hum, but since it's a string, shouldn't text editors highlight it as if it was a string? I was going to do that in D for Xcode at some point... perhaps I shouldn't. -- Michel Fortin michel.fortin michelf.com http://michelf.com/

Jan 31 2009

Michel Fortin wrote:On 2009-01-31 19:26:08 -0500, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:So I think in the future it's a good bet for both programmers and editors to consider q{} quotes as containing code.

Hum, but since it's a string, shouldn't text editors highlight it as if it was a string? I was going to do that in D for Xcode at some point... perhaps I shouldn't.

I think it might be a nice idea to syntax-highlight those like regular code, but with a different background color. For instance white background for regular code, light yellow for q{}, and successively darker shades for nested q{q{q{}}} (up to some limit). You'd have to make sure it stays readable though, so the background color should be a color that has sufficient contrast with foreground colors used for the code (e.g. don't pick the color used for regular strings(!) or keywords). Just a thought...

Jan 31 2009

Andrei Alexandrescu Wrote:Derek Parnell wrote:On Sat, 31 Jan 2009 07:22:17 -0800, Andrei Alexandrescu wrote:

And syntax-highlighting editors just love them ;-) Knowing which strings contain code and which don't is a piece of cake, no?

The language can help here. q{stuff} is a "token string" which presumably contains code, whereas the other strings presumably don't. In my editor, q{code} comes off as highlighted. So I think in the future it's a good bet for both programmers and editors to consider q{} quotes as containing code. Andrei

I have never seen an std.algorithm example using q{}. I'd also expect such an example to lose some of its apeal.

Jan 31 2009

Jarrett Billingsley wrote:On Sat, Jan 31, 2009 at 9:34 AM, Ary Borenszweig <ary esperanto.org.ar> wrote:auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1);

Or just steal things from other languages. auto fib = series!(\a, n -> a[n - 1] + a[n])(1, 1); Haskell function literals, wee! Of course, it means actually using \ for something useful, unlike how it's used now.

Today's naked string literals must go!! Andrei

Jan 31 2009

Andrei Alexandrescu wrote:Ary Borenszweig wrote:

That is *SO* awesome!!

Thanks! Constant-space factorial is just a line away: auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e);

Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

Feb 03 2009

"Denis Koroskin" wroteOn Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Andrei Alexandrescu wrote:Ary Borenszweig wrote:

That is *SO* awesome!!

auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e);

Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.

Factorial series is defined in terms of the last term, so you only need to remember the last term. i.e. 5! = 4! * 5. So constant space, constant time per iteration. One thing I was confused about, you are defining in the function how to calculate a[n+1]? I find it more intuitive to define what a[n] is. For example, auto fib = series!("a[n - 2] + a[n - 1]")(1, 1); // reads a[n] = a[n-2] + a[n-1] It's even less confusing in the factorial example (IMO): auto fact = series!("a[n - 1] * n")(1); Of course, I don't know how the template-fu works, so I'm not sure if it's possible ;) -Steve

Feb 03 2009

Steven Schveighoffer wrote:One thing I was confused about, you are defining in the function how to calculate a[n+1]? I find it more intuitive to define what a[n] is. For example, auto fib = series!("a[n - 2] + a[n - 1]")(1, 1); // reads a[n] = a[n-2] + a[n-1] It's even less confusing in the factorial example (IMO): auto fact = series!("a[n - 1] * n")(1); Of course, I don't know how the template-fu works, so I'm not sure if it's possible ;)

It's entirely possible, and I think it's a good idea. I'll look into changing the code. Thanks! Andrei

Feb 03 2009

"Denis Koroskin" wroteOn Tue, 03 Feb 2009 22:43:06 +0300, Steven Schveighoffer <schveiguy yahoo.com> wrote:"Denis Koroskin" wroteOn Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Andrei Alexandrescu wrote:Ary Borenszweig wrote:

That is *SO* awesome!!

auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e);

Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.

Factorial series is defined in terms of the last term, so you only need to remember the last term. i.e. 5! = 4! * 5. So constant space, constant time per iteration.

Of course, but does it *really* discard old values? That's what I doubt. Ok, Factorial/Fibonacci is easy. How would you implement, say, the following sequence: a[n] = a[0] + a[n / 8]; // ?

I don't think such a series is definable with Andrei's template. I think his series template is only usable in situations where computing a[n] depends only on n and the elements a[n-X]..a[n-1], where X is a constant. I'm not really a mathemetician, so I don't know the technical term for the differences, I'm sure there is one. -Steve

Feb 03 2009

Steven Schveighoffer wrote:I don't think such a series is definable with Andrei's template. I think his series template is only usable in situations where computing a[n] depends only on n and the elements a[n-X]..a[n-1], where X is a constant. I'm not really a mathemetician, so I don't know the technical term for the differences, I'm sure there is one.

Time-invariant, or shift-invariant.

Feb 03 2009

Joel C. Salomon wrote:Steven Schveighoffer wrote:I don't think such a series is definable with Andrei's template. I think his series template is only usable in situations where computing a[n] depends only on n and the elements a[n-X]..a[n-1], where X is a constant. I'm not really a mathemetician, so I don't know the technical term for the differences, I'm sure there is one.

Time-invariant, or shift-invariant.

Great! I didn't know (haven't learned college-level Math in English; sometimes I wonder how I fumbled through grad school without major misunderstandings). By the way, I might have been wrong with the name "series" itself. I thought "series" is something like a_n = f(a_{n-1},...,f_a{n-k}). However, according to Wikipedia: http://en.wikipedia.org/wiki/Infinite_series series is really what I thought is called "partial sums", i.e. s_n is the sum of elements of a sequence a_n up to the nth element. So should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite! Andrei

Feb 03 2009

On Tue, 03 Feb 2009 15:26:45 -0800, Andrei Alexandrescu wrote:So, what names should I use? English-speaking mathematicians across the newsgroup, unite!

I'm not a mathemetician, but to me elements in a series cannot necessarily be predicted by knowing the values of existing elements, whereas in a sequence an element can be predicted using only the existing element values. -- Derek Parnell Melbourne, Australia skype: derek.j.parnell

Feb 03 2009

"Andrei Alexandrescu" wroteSo should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite!

http://en.wikipedia.org/wiki/Recurrence_relation I'd say recurrence!(...) possibly? But definitely a range is analagous to a sequence defined in math (as defined by wikipedia). -Steve

Feb 03 2009

Andrei Alexandrescu wrote:Great! I didn't know (haven't learned college-level Math in English; sometimes I wonder how I fumbled through grad school without major misunderstandings). By the way, I might have been wrong with the name "series" itself. I thought "series" is something like a_n = f(a_{n-1},...,f_a{n-k}). However, according to Wikipedia: http://en.wikipedia.org/wiki/Infinite_series series is really what I thought is called "partial sums", i.e. s_n is the sum of elements of a sequence a_n up to the nth element. So should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite!

I believe the mathematically correct terms would be RecursiveSequence and ClosedFormSequence. If I were to use just Sequence, it would in fact be for the latter. A series is, as you said, the sum of all the terms in a sequence, whereas summing only a finite set of terms gives a partial sum. (The latter could be implemented as a range.) A recurrence relation is an expression that recursively defines a sequence (i.e. the string argument of the template). I prefer MathWorld to Wikipedia when it comes to these things. Here are some (possibly) useful links: Recursive sequences: http://mathworld.wolfram.com/RecursiveSequence.html Some sequences that could possibly be rangeified: http://mathworld.wolfram.com/Sequence.html Series: http://mathworld.wolfram.com/Series.html Partial sums (and other sums) of sequences: http://mathworld.wolfram.com/PartialSum.html -Lars

Feb 04 2009

Andrei Alexandrescu wrote:So should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite!

These are sequences. (Or, in an EE context, â€œsignalsâ€, but letâ€™s not go thereâ€¦ â˜º) Except: a sequence might be the coefficients {Î±â‚€, Î±â‚, Î±â‚‚, â€¦} of the power _series_ Î±â‚€xâ° + Î±â‚xÂ¹ + Î±â‚‚xÂ² + â‹¯, in which case the sequence is just a representation of the power series. There are some cool tricke to be played with power series represented this way; e.g., see Doug McIlroyâ€™s â€œSquinting at Power Seriesâ€ at <http://plan9.bell-labs.com/who/rsc/thread/squint.pdf>. â€”Joel Salomon

Feb 04 2009

Denis Koroskin wrote:Of course, but does it *really* discard old values? That's what I doubt.

It really discards old values.Ok, Factorial/Fibonacci is easy. How would you implement, say, the following sequence: a[n] = a[0] + a[n / 8]; // ?

Very simple (assuming a[0] = 1): auto s = series("cast(uint) (log(n) / 3) + 2")(1); At least that's what I got through expansion :o). What I'm saying is that series() does not do the work for you to either have unbounded state, backtrack as needed, or do algebraic manipulation. The series must come in analytic form. It's a good point. The current implementation defines a series as k initial elements and a method of computing a_{n} given a_{n-1} through a_{n-k}. Most series come in this form. Few interesting series don't, but they are rare and tricky anyway; they are not supported as of yet. I will note that your formula above shouldn't compile (it currently does and runs with erratic results).Now it is log(n) to compute from scratch but you should store O(n) elements to make it constant time. I mean, the algorithm ought to have very good heuristics. And sometimes it is better to re-compute elements instead of caching them.

There's no heuristics and no computation vs. storage tradeoff. It's as cut and dried as it gets. Given k initial elements and a formula to compute an element from the past k elements, series() implements an infinite range. But it would be great to extend this to more non-analytic series. Andrei

Feb 03 2009

Denis Koroskin wrote:On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Andrei Alexandrescu wrote:Ary Borenszweig wrote:

That is *SO* awesome!!

auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e);

Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.

I wouldn't use it either, in fact I have a dim view of all books, articles, and courses that promote exponential-time Fibonacci and linear-space factorial. It just promotes sloppy algorithmic thinking under the pretense that recursion is cool. (I also have a dim view of the FP proponents who promote the quicksort that actually doesn't sort in place and returns new arrays by value every iteration, consuming O(n log n) extra memory. But I digress.) The size of the state held by a series is equal to the number of initial arguments passed when it is constructed. The arguments are stored in a fixed-size array sitting in the series object. So: auto fib = series!("a[n-1] + a[n]")(1, 1); holds an int[2], initialized with [1, 1]. The current index in the series (a size_t initialized to 0) completes the state size. When fib.next is called, the ((n+1) % 2)th element in the array is overwritten with the result of a[(n-1)%2] + a[n%2]. Then n is incremented. fib.head returns a[n%2]. In the factorial case it's simpler because the state size is 1. Since the state size is used as a compile-time constant, the compiler has the opportunity to optimize away calculations like n%1. Andrei

Feb 03 2009

On Sat, Jan 31, 2009 at 9:34 AM, Ary Borenszweig <ary esperanto.org.ar> wrote:auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1);

Or just steal things from other languages. auto fib = series!(\a, n -> a[n - 1] + a[n])(1, 1); Haskell function literals, wee! Of course, it means actually using \ for something useful, unlike how it's used now.

Jan 31 2009

On Sat, Jan 31, 2009 at 10:23 AM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Jarrett Billingsley wrote:On Sat, Jan 31, 2009 at 9:34 AM, Ary Borenszweig <ary esperanto.org.ar> wrote:auto fib = series!((Range a, int n) { a[n-1] + a[n] })(1, 1); And if you could just ommit the types in the delegate... auto fib = series!((a, n) { a[n-1] + a[n] })(1, 1);

Or just steal things from other languages. auto fib = series!(\a, n -> a[n - 1] + a[n])(1, 1); Haskell function literals, wee! Of course, it means actually using \ for something useful, unlike how it's used now.

Today's naked string literals must go!!

:O

Jan 31 2009

On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Andrei Alexandrescu wrote:Ary Borenszweig wrote:Andrei Alexandrescu escribiÃ³:

That is *SO* awesome!!

auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e);

Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.

Feb 03 2009

On Tue, 03 Feb 2009 22:43:06 +0300, Steven Schveighoffer <schveiguy yahoo.com> wrote:"Denis Koroskin" wroteOn Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:Andrei Alexandrescu wrote:Ary Borenszweig wrote:Andrei Alexandrescu escribiÃ³:

That is *SO* awesome!!

auto fact = series!("a[n] * (n + 1)")(1); foreach (e; take(10, fact)) writeln(e);

Awesome :-) I think that proves the efficacy of the approach all by itself. Sean

I wonder how efficent it is? Does it store last few sequence elements or re-compute then again and again? I wouldn't use it in the latter case.

Factorial series is defined in terms of the last term, so you only need to remember the last term. i.e. 5! = 4! * 5. So constant space, constant time per iteration.

Of course, but does it *really* discard old values? That's what I doubt. Ok, Factorial/Fibonacci is easy. How would you implement, say, the following sequence: a[n] = a[0] + a[n / 8]; // ? Now it is log(n) to compute from scratch but you should store O(n) elements to make it constant time. I mean, the algorithm ought to have very good heuristics. And sometimes it is better to re-compute elements instead of caching them.One thing I was confused about, you are defining in the function how to calculate a[n+1]? I find it more intuitive to define what a[n] is. For example, auto fib = series!("a[n - 2] + a[n - 1]")(1, 1); // reads a[n] = a[n-2] + a[n-1] It's even less confusing in the factorial example (IMO): auto fact = series!("a[n - 1] * n")(1); Of course, I don't know how the template-fu works, so I'm not sure if it's possible ;) -Steve

I agree.

Feb 03 2009

On Wed, Feb 4, 2009 at 8:26 AM, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Joel C. Salomon wrote:Steven Schveighoffer wrote:I don't think such a series is definable with Andrei's template. I think his series template is only usable in situations where computing a[n] depends only on n and the elements a[n-X]..a[n-1], where X is a constant. I'm not really a mathemetician, so I don't know the technical term for the differences, I'm sure there is one.

Time-invariant, or shift-invariant.

Great! I didn't know (haven't learned college-level Math in English; sometimes I wonder how I fumbled through grad school without major misunderstandings). By the way, I might have been wrong with the name "series" itself. I thought "series" is something like a_n = f(a_{n-1},...,f_a{n-k}). However, according to Wikipedia: http://en.wikipedia.org/wiki/Infinite_series series is really what I thought is called "partial sums", i.e. s_n is the sum of elements of a sequence a_n up to the nth element. So should I change "series" with "sequence"? How about what I called "ClosedFormSeries"? By that I meant a series, (pardon, sequence), in which there is no recurrence formula - the nth element a_n can be expressed in terms of n and a[0], ..., a[k] (a sort of "random access" for a sequence). So, what names should I use? English-speaking mathematicians across the newsgroup, unite!

My digital signal processing textbook refers to "discrete-time sequences", not series. But I'm pretty sure I've heard "discrete-time series" used too. So I'd say either sequence or series is just fine. But that's just the EE perspective. Pure math guys might have a different take. --bb

Feb 03 2009

Andrei Alexandrescu wrote:I've updated my code and documentation to include series (as in math) in the form of infinite ranges. Also series in closed form (given n can compute the nth value without iterating) are supported as random-access ranges.

I've been thinking a little about the concepts involved in range endpoints. Most important ranges are homomorphic to ints; that is, given [x..y], there is some finite number n of elements in the range. And there is an ordering: successor(successor(x)) repeated n times will return y. As well as ints and many data structures, fixed-point and built-in floating-point arithmetic obey these properties. Interestingly this even applies to an "infinite" range: [1..real.infinity] has a limited number of elements. However, some other ranges do NOT behave this way. Mathematical real numbers defined symbollically, for example. More realistically, arbitrary-precision fractions. For these types of ranges, there is no successor function. Thus, they are not even input ranges; but they have some properties of random-access ranges. There are many algorithms which work on these non-quantised ranges. Now consider the range 5.0L..real.max, on a system where real is 128 bits. Is it a random-access range? Sort of. You can't provide an opIndex(), even with ulong as an index, because there are just too many entries. But there are many operations you can still do. predecessor and successor are nextDown(), nextUp(). My root-finding algorithm in std.numeric uses these functions as well as an approximate-midpoint-in-representation-space function. In any case, I think it would be good to come up with some standard names for the predecessor and successor functions.

Jan 31 2009

On Sun, Feb 1, 2009 at 3:30 AM, Don <nospam nospam.com> wrote:Andrei Alexandrescu wrote:Jagged, banded, diagonal, fixed-size, and sparse layouts come naturally and will be hopefully supported in a mixable-and-matchable form (e.g. I want a block matrix of 3x3 matrices). I want to focus on storage for now, put it in the standard library, to then allow great scientific programmers like you guys to use those storages as a common data format on top of which cool algorithms can be implemented.

This sounds like the perfect approach. Everything's built around the storage format.

Yes indeed. It's a tried and true approach. I think you'll find a similar approach in the likes of the Matrix Template Library, or FLENS. But I think those projects, particularly MTL, hit a wall because C++ meta-programming is just such a mess. I'm very excited to see what can be done with the full arsenal of D2 metaprogramming at one's disposal. --bb

Jan 31 2009