www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Anyone come up with some cool algorithms/templates for D lately?

reply janderson <askme me.com> writes:
In the past people have posted these cool algorithms/templates they 
figured out how to do in some neat way with D.  Things like wow, this 
would take INF+ lines in C++ but I can do it in 2 in D.   This seems to 
have died down a bit.   I always found these topics most interesting.

So I'm requesting people to post "cool stuff" they figured out how to do 
in D.

-Joel
Apr 17 2008
next sibling parent reply "Saaa" <empty needmail.com> writes:
I'd expect interesting topics with a new release.
Have you noticed; it's been the longest wait since at least a year.


 So I'm requesting people to post "cool stuff" they figured out how to do 
 in D.

 -Joel 

Apr 17 2008
next sibling parent reply "Lionello Lunesu" <lionello lunesu.remove.com> writes:
You're right, but still: the last release introduced struct destructors, 
which have been requested a couple of times (mostly C++ folk, probably) and 
I, too, am eagerly awaiting cool code making use of struct destructors.

L.


"Saaa" <empty needmail.com> wrote in message 
news:fu93d0$1cfh$1 digitalmars.com...
 I'd expect interesting topics with a new release.
 Have you noticed; it's been the longest wait since at least a year.


 So I'm requesting people to post "cool stuff" they figured out how to do 
 in D.

 -Joel


Apr 17 2008
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Psst -- don't tell anyone but ...
opDot... coming to a DMD near you soon.

--bb

Lionello Lunesu wrote:
 You're right, but still: the last release introduced struct destructors, 
 which have been requested a couple of times (mostly C++ folk, probably) 
 and I, too, am eagerly awaiting cool code making use of struct destructors.
 
 L.
 
 
 "Saaa" <empty needmail.com> wrote in message 
 news:fu93d0$1cfh$1 digitalmars.com...
 I'd expect interesting topics with a new release.
 Have you noticed; it's been the longest wait since at least a year.


 So I'm requesting people to post "cool stuff" they figured out how to 
 do in D.



Apr 17 2008
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2008-04-17 23:32:03 -0400, Bill Baxter <dnewsgroup billbaxter.com> said:

 Psst -- don't tell anyone but ...
 opDot... coming to a DMD near you soon.

opDot? I'd like to hear why it would be named this way instead of opMember, opFwd, or anything telling what usage the operator is about instead of what it looks like. There's a reason Walter has choosen opAdd, opDiv, opSlice, etc. instead of opPlus, opSlash, opBrakets, etc. and I feel it was a very good idea. Why move away from this? I know there's a precedent (opStar), but I'd like to hear the rationale behind this choice too (why isn't it called opDeref?). -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Apr 18 2008
next sibling parent reply Robert Fraser <fraserofthenight gmail.com> writes:
Michel Fortin wrote:
 On 2008-04-17 23:32:03 -0400, Bill Baxter <dnewsgroup billbaxter.com> said:
 
 Psst -- don't tell anyone but ...
 opDot... coming to a DMD near you soon.

opDot? I'd like to hear why it would be named this way instead of opMember, opFwd, or anything telling what usage the operator is about instead of what it looks like. There's a reason Walter has choosen opAdd, opDiv, opSlice, etc. instead of opPlus, opSlash, opBrakets, etc. and I feel it was a very good idea. Why move away from this? I know there's a precedent (opStar), but I'd like to hear the rationale behind this choice too (why isn't it called opDeref?).

Unlike opStar, opDot's name is instantly intuitive. It doesn't fit with the others, but at least it's easy to guess what it does, so it's a step up.
Apr 18 2008
parent Lionello Lunesu <lio lunesu.remove.com> writes:
Robert Fraser wrote:
 Michel Fortin wrote:
 On 2008-04-17 23:32:03 -0400, Bill Baxter <dnewsgroup billbaxter.com> 
 said:

 Psst -- don't tell anyone but ...
 opDot... coming to a DMD near you soon.

opDot? I'd like to hear why it would be named this way instead of opMember, opFwd, or anything telling what usage the operator is about instead of what it looks like. There's a reason Walter has choosen opAdd, opDiv, opSlice, etc. instead of opPlus, opSlash, opBrakets, etc. and I feel it was a very good idea. Why move away from this? I know there's a precedent (opStar), but I'd like to hear the rationale behind this choice too (why isn't it called opDeref?).

Unlike opStar, opDot's name is instantly intuitive. It doesn't fit with the others, but at least it's easy to guess what it does, so it's a step up.

It's not.. My first thought was 'dot-product?'. L.
Apr 18 2008
prev sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Michel Fortin wrote:
 On 2008-04-17 23:32:03 -0400, Bill Baxter <dnewsgroup billbaxter.com> said:
 
 Psst -- don't tell anyone but ...
 opDot... coming to a DMD near you soon.

opDot? I'd like to hear why it would be named this way instead of opMember, opFwd, or anything telling what usage the operator is about instead of what it looks like. There's a reason Walter has choosen opAdd, opDiv, opSlice, etc. instead of opPlus, opSlash, opBrakets, etc. and I feel it was a very good idea. Why move away from this? I know there's a precedent (opStar), but I'd like to hear the rationale behind this choice too (why isn't it called opDeref?).

There was a big thread about that one too where everyone complained that it didn't make sense and violated Walter's own proclamations about how operator functions should be named. But in the end he just ignored the debate. Hmmm, but it looks like no one ever filed anything about it. Time to fire up bugzilla. --bb
Apr 18 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 18/04/2008, Michel Fortin <michel.fortin michelf.com> wrote:
  I know there's a precedent (opStar), but I'd like to hear the rationale
 behind this choice too

I believe opStar() applied to a value will cause it to become the principle performer in a major Hollywood movie! :-)
Apr 18 2008
prev sibling parent Jesse Phillips <jessekphillips gmail.com> writes:
On Fri, 18 Apr 2008 09:15:31 -0400, Michel Fortin wrote:

 On 2008-04-17 23:32:03 -0400, Bill Baxter <dnewsgroup billbaxter.com>
 said:
 
 Psst -- don't tell anyone but ...
 opDot... coming to a DMD near you soon.

opDot? I'd like to hear why it would be named this way instead of opMember, opFwd, or anything telling what usage the operator is about instead of what it looks like. There's a reason Walter has choosen opAdd, opDiv, opSlice, etc. instead of opPlus, opSlash, opBrakets, etc. and I feel it was a very good idea. Why move away from this? I know there's a precedent (opStar), but I'd like to hear the rationale behind this choice too (why isn't it called opDeref?).

Wouldn't it still be legal to use the asterisk as multiply or deferef? I understand the reason for +, but you really can't say * isn't both multiply and dereference. Maybe the dot could be used as a member call, and just to say that there should be something here but don't know what. :)
Apr 18 2008
prev sibling next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
janderson wrote:
 In the past people have posted these cool algorithms/templates they 
 figured out how to do in some neat way with D.  Things like wow, this 
 would take INF+ lines in C++ but I can do it in 2 in D.   This seems to 
 have died down a bit.   I always found these topics most interesting.
 
 So I'm requesting people to post "cool stuff" they figured out how to do 
 in D.

I'm still flabbergasted by the cool things you can do inside fixed-length matrix/vector templates. For instance (this is all from my matrix/vector classes in OpenMesh/D which are basically a complete rewrite of the original C++ versions) struct MatrixT(T, int M, int N) { alias T Scalar; union { Scalar[M*N] values_ = void; static if(M<=10 && N<=10) { mixin(_gen_elements!(M,N)("Scalar")); } } } // Generate the elements m00,m01,m02... elements // For matrices with dimensions < 10 x 10 only. private string _gen_elements(int M, int N)(string type) { static assert(M<=10); static assert(N<=10); char[] Num = "0123456789"; string ret; for(int col=0; col<N; ++col) { ret ~= type ~ " "; for (int row=0; row<M; row++) { ret ~= "m" ~ Num[row] ~ Num[col]; if (row!=M-1) ret ~= ", "; } ret ~= ";\n"; } return ret; } This creates aliases to each element of the matrix of the form m00, m01, m02, but only if the matrix is small enough. I have no idea how you'd do that in C++. I don't think it's really possible. Here's another -- generating the unrolled code for multiplying two matrices together: /// Multiply MxN matrix time NxP matrix void mat_mult_ret(T,int M,int N,int P)( /*const*/ref MatrixT!(T,M,N) A, /*const*/ref MatrixT!(T,N,P) B, inout MatrixT!(T,M,P) ret) { with(ret) { mixin(_gen_mat_mult_body!(M,N,P)("A","B")); } } private string _gen_mat_mult_body(int M, int N, int P)(string A, string B) { string ret; for (int row=0; row<M; ++row) { for(int col=0; col<P; ++col) { ret ~= " "; ret ~= "values_["~ctfe_itoa(col*M+row)~"] = "; for(int jj; jj<N; ++jj) { string JJ = ctfe_itoa(jj); string iA = ctfe_itoa( row+jj *M ); string iB = ctfe_itoa( jj +col*N ); ret ~= A ~ ".values_["~iA~"]*"~B~".values_["~iB~"]"; if (jj != N-1) { ret ~= " + "; } else { ret ~= ";\n"; } } } ret ~= "\n"; } return ret; } Wow. The code generating function basically just looks like a standard triply-nested matrix multiply, but instead of doing multiplies it just splits out code that implements multiplies. I think that's pretty sweet. --bb
Apr 17 2008
next sibling parent janderson <askme me.com> writes:
Bill Baxter wrote:
 janderson wrote:
 In the past people have posted these cool algorithms/templates they 
 figured out how to do in some neat way with D.  Things like wow, this 
 would take INF+ lines in C++ but I can do it in 2 in D.   This seems 
 to have died down a bit.   I always found these topics most interesting.

 So I'm requesting people to post "cool stuff" they figured out how to 
 do in D.

I'm still flabbergasted by the cool things you can do inside fixed-length matrix/vector templates. For instance (this is all from my matrix/vector classes in OpenMesh/D which are basically a complete rewrite of the original C++ versions) struct MatrixT(T, int M, int N) { alias T Scalar; union { Scalar[M*N] values_ = void; static if(M<=10 && N<=10) { mixin(_gen_elements!(M,N)("Scalar")); } } } // Generate the elements m00,m01,m02... elements // For matrices with dimensions < 10 x 10 only. private string _gen_elements(int M, int N)(string type) { static assert(M<=10); static assert(N<=10); char[] Num = "0123456789"; string ret; for(int col=0; col<N; ++col) { ret ~= type ~ " "; for (int row=0; row<M; row++) { ret ~= "m" ~ Num[row] ~ Num[col]; if (row!=M-1) ret ~= ", "; } ret ~= ";\n"; } return ret; } This creates aliases to each element of the matrix of the form m00, m01, m02, but only if the matrix is small enough. I have no idea how you'd do that in C++. I don't think it's really possible. Here's another -- generating the unrolled code for multiplying two matrices together: /// Multiply MxN matrix time NxP matrix void mat_mult_ret(T,int M,int N,int P)( /*const*/ref MatrixT!(T,M,N) A, /*const*/ref MatrixT!(T,N,P) B, inout MatrixT!(T,M,P) ret) { with(ret) { mixin(_gen_mat_mult_body!(M,N,P)("A","B")); } } private string _gen_mat_mult_body(int M, int N, int P)(string A, string B) { string ret; for (int row=0; row<M; ++row) { for(int col=0; col<P; ++col) { ret ~= " "; ret ~= "values_["~ctfe_itoa(col*M+row)~"] = "; for(int jj; jj<N; ++jj) { string JJ = ctfe_itoa(jj); string iA = ctfe_itoa( row+jj *M ); string iB = ctfe_itoa( jj +col*N ); ret ~= A ~ ".values_["~iA~"]*"~B~".values_["~iB~"]"; if (jj != N-1) { ret ~= " + "; } else { ret ~= ";\n"; } } } ret ~= "\n"; } return ret; } Wow. The code generating function basically just looks like a standard triply-nested matrix multiply, but instead of doing multiplies it just splits out code that implements multiplies. I think that's pretty sweet. --bb

Neat Stuff!
Apr 17 2008
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Bill Baxter wrote:
 For instance (this is all from my matrix/vector classes in OpenMesh/D 
 which are basically a complete rewrite of the original C++ versions)

Got a link to your code? (What you're doing looks pretty cool!)
Apr 17 2008
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Walter Bright wrote:
 Bill Baxter wrote:
 For instance (this is all from my matrix/vector classes in OpenMesh/D 
 which are basically a complete rewrite of the original C++ versions)

Got a link to your code? (What you're doing looks pretty cool!)

It's on dsource. http://www.dsource.org/projects/openmeshd The snippet was from the Geometry dir: http://www.dsource.org/projects/openmeshd/browser/trunk/OpenMeshD/OpenMesh/Core/Geometry specifically, MatrixT: http://www.dsource.org/projects/openmeshd/browser/trunk/OpenMeshD/OpenMesh/Core/Geometry/MatrixT.d My other big dsource project is MultiArray. http://www.dsource.org/projects/multiarray I recently added DFLAT (D Flexible Linear Algebra Types) which is a port+improvements of the C++ library, FLENS. DFLAT has templates to supports all the matrix storage types used by BLAS and LAPACK, and also the sparse matrix libraries SuperLU, TAUCS, and UMFPACK. No CTFE there, but plenty of template logic, like here: http://www.dsource.org/projects/multiarray/browser/trunk/multiarray/dflat/Blas.d ...which tries to take any type of matrix arguments and figure out the right BLAS call to make to multiply them together. --bb
Apr 17 2008
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
Reply to janderson,

 In the past people have posted these cool algorithms/templates they
 figured out how to do in some neat way with D.  Things like wow, this
 would take INF+ lines in C++ but I can do it in 2 in D.   This seems
 to have died down a bit.   I always found these topics most
 interesting.
 
 So I'm requesting people to post "cool stuff" they figured out how to
 do in D.
 
 -Joel
 

// Sort data using keys as the order uint[] keys, data; assert(keys.length == data.length); ulong[] arr; arr.length = keys.length; foreach(int i, uint _; keys) arr[i] = (cast(uint)keys[i])<<32 | data[i]; arr.sort; foreach(int i, uint _; keys) data[i] = cast(uint)(arr & 0x0ffff_ffff);
Apr 17 2008
parent reply janderson <askme me.com> writes:
BCS wrote:
 Reply to janderson,
 
 In the past people have posted these cool algorithms/templates they
 figured out how to do in some neat way with D.  Things like wow, this
 would take INF+ lines in C++ but I can do it in 2 in D.   This seems
 to have died down a bit.   I always found these topics most
 interesting.

 So I'm requesting people to post "cool stuff" they figured out how to
 do in D.

 -Joel

// Sort data using keys as the order uint[] keys, data; assert(keys.length == data.length); ulong[] arr; arr.length = keys.length; foreach(int i, uint _; keys) arr[i] = (cast(uint)keys[i])<<32 | data[i]; arr.sort; foreach(int i, uint _; keys) data[i] = cast(uint)(arr & 0x0ffff_ffff);

It took me a while to figure out what was going on here. Anyway I never thought of sorting this way. Another way to do this would be with a struct, although it would be non-portable unless you defined a comparison operator (of course). Anyways great stuff! -Joel
Apr 17 2008
parent BCS <ao pathlink.com> writes:
Reply to janderson,

 Anyways great stuff!
 
 -Joel
 

BTW: I'm getting paid for that one :)
Apr 17 2008
prev sibling parent reply Brian Palmer <d brian.codekitchen.net> writes:
Content-Type: text/plain

janderson Wrote:

 In the past people have posted these cool algorithms/templates they 
 figured out how to do in some neat way with D.  Things like wow, this 
 would take INF+ lines in C++ but I can do it in 2 in D.   This seems to 
 have died down a bit.   I always found these topics most interesting.
 
 So I'm requesting people to post "cool stuff" they figured out how to do 
 in D.
 
 -Joel

I'm not sure if this is the kind of thing you're looking for, but this is a proof-of-concept template that I came up with a few days ago, inspired by a blog post describing similar functionality in Factor [1]. Completely at compile time, it parses a text file describing a mapping between an 8-bit encoding and Unicode, and builds data structures and functions to convert between that encoding and Unicode. The text files are all in a standard format, available at ftp://ftp.unicode.org/Public/MAPPINGS/ Of course, this wouldn't be a big deal to do at runtime with a module constructor, or to simply write a pre-processor to convert each text file to a D module, since they're unlikely to ever change. But I'm pretty new at D and for my own education I wanted to see if I could do all the parsing at compile time so that the full text of the file isn't stored in the executable or bundled with the software. alias Encoding!("CP1252.txt") windows1252; // ftp://ftp.unicode.org/Public/MAPPINGS/VENDORS/MICSFT/WINDOWS/CP1252.TXT auto w1 = "Trademark\x99"; // TM symbol in Windows-1252 auto u1 = "Trademark\u2122"w; // TM symbol in Unicode wchar[] conv1 = windows1252.toU(w1); assert(conv1 == u1); char[] convback = windows1252.fromU(conv1); assert(convback == w1); To be honest I was expecting this to be easier than it was. What I thought would be a trivial experiment ended up taking about an hour, most of that time spent trying different approaches to get CTFE to accept my code. CTFE is a wonderful feature but it's still much, much too limited in what code it will accept, in my opinion. I've attached the ugly, proof-of-concept code for the module. Please don't think less of me after reading it. :) [1] http://useless-factor.blogspot.com/2008/04/programming-in-series-of-trivial-one.html
Apr 18 2008
parent Robert Fraser <fraserofthenight gmail.com> writes:
Brian Palmer wrote:
 To be honest I was expecting this to be easier than it was. What I thought
would be a trivial experiment ended up taking about an hour, most of that time
spent trying different approaches to get CTFE to accept my code. CTFE is a
wonderful feature but it's still much, much too limited in what code it will
accept, in my opinion.

Agreed. CTFE is basically just an interpreter that operates on an existing syntax tree, so there's no reason nearly every feature of the language can't be supported (mutable global state + CTFE might not be a great idea, but dynamic allocation, classes, exceptions, etc. would be great to see).
Apr 18 2008