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
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 "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 next 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 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 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:
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