www.digitalmars.com         C & C++   DMDScript  

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

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 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

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
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
prev sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
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
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
prev sibling next sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
next sibling parent Don <nospam nospam.com> writes:
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
prev sibling parent Neal Becker <ndbecker2 gmail.com> writes:
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
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
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
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
next sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
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
parent grauzone <none example.net> writes:
Ary Borenszweig wrote:
 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.

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
prev sibling parent Brian Palmer <d brian.codekitchen.net> writes:
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
prev sibling next sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Sat, 31 Jan 2009 14:35:50 +0100, Ary Borenszweig <ary esperanto.org.ar>
wrote:

 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


Who is SPJ?

http://en.wikipedia.org/wiki/Simon_Peyton_Jones
 I 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
prev sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
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
parent Michel Fortin <michel.fortin michelf.com> writes:
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
prev sibling next sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
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
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
next sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
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
next sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
Ary Borenszweig escribió:
 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.

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
parent reply Christopher Wright <dhasenan gmail.com> writes:
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
parent Ary Borenszweig <ary esperanto.org.ar> writes:
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
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
next sibling parent Don <nospam nospam.com> writes:
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
prev sibling next sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
parent Ary Borenszweig <ary esperanto.org.ar> writes:
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
prev sibling parent reply Derek Parnell <derek psych.ward> writes:
On Sat, 31 Jan 2009 07:22:17 -0800, 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.

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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Derek Parnell wrote:
 On Sat, 31 Jan 2009 07:22:17 -0800, 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.

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
next sibling parent Derek Parnell <derek psych.ward> writes:
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
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
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
parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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
prev sibling parent Jason House <jason.james.house gmail.com> writes:
Andrei Alexandrescu Wrote:

 Derek Parnell wrote:
 On Sat, 31 Jan 2009 07:22:17 -0800, 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.

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
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
prev sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
Andrei Alexandrescu wrote:
 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);

Awesome :-) I think that proves the efficacy of the approach all by itself. Sean
Feb 03 2009
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Denis Koroskin" wrote
 On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> 
 wrote:

 Andrei Alexandrescu wrote:
 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!!

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
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Denis Koroskin" wrote
 On Tue, 03 Feb 2009 22:43:06 +0300, Steven Schveighoffer 
 <schveiguy yahoo.com> wrote:

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

 Andrei Alexandrescu wrote:
 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!!

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
parent reply "Joel C. Salomon" <joelcsalomon gmail.com> writes:
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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
next sibling parent Derek Parnell <derek psych.ward> writes:
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
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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!

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
prev sibling next sibling parent Lars Kyllingstad <public kyllingen.NOSPAMnet> writes:
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
prev sibling parent "Joel C. Salomon" <joelcsalomon gmail.com> writes:
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
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Denis Koroskin wrote:
 On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> 
 wrote:
 
 Andrei Alexandrescu wrote:
 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!!

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
prev sibling next sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
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
prev sibling next sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
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
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean invisibleduck.org> wrote:

 Andrei Alexandrescu wrote:
 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!!

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
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 03 Feb 2009 22:43:06 +0300, Steven Schveighoffer <schveiguy yahoo.com>
wrote:

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

 Andrei Alexandrescu wrote:
 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!!

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
prev sibling parent Bill Baxter <wbaxter gmail.com> writes:
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
prev sibling next sibling parent Don <nospam nospam.com> writes:
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
prev sibling parent Bill Baxter <wbaxter gmail.com> writes:
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