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
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 reply 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
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.


 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.


Ouch, fixed. Thanks!

Andrei
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 reply 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
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 parent reply 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
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
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
next sibling 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 "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


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


 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 Brian Palmer <d brian.codekitchen.net> writes:
Andrei Alexandrescu Wrote:


 bearophile wrote:

 Andrei Alexandrescu:


 SPJ held a gun to my head and said: "take(10, fib)".
 
 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 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
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 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
parent reply 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
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 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 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
parent reply "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!!


  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


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
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!!


  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


 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 parent reply "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!!


  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


 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
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!!


  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


 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 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 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!!


  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


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