generalised slicing

[Knud Soerensen]

On Tue, 09 Jan 2007 01:40:25 +0000, Warren D Smith wrote:

> Here are some suggested improvements for D.
You should post them piecewise on http://all-technology.com/eigenpolls/dwishlist/

> 
> popcount and first1:
> Often one represents a set by means of an array of booleans, or
> equivalently by the bits of a machine word.
> Now, the cray used to have a wonderful "popcount" machine-instruction
>  a = popcount(b);
> which would cause the number of 1-bits in the uint b, to be placed in
> the integer a.
> E.g. popcount(21)=3.
> Also, some machines had a "first1" instruction which would cause, e.g,
>   c=0;
>   printf("here are the locations of the 1bits in b: ");
>   for(a = first1(b); b!=0; b >>= a){
>      c += a;
>      printf("%d,", c);
>   }
>   printf("\n");
> to work as a way to loop thru the elements of the set.
> 
> This was all very fine.  It led to TREMENDOUS speedup and
> simplification of the right kinds of programs.
> BUT, later hardware got rid of the instruction and languages
> did not have these as features.  Vicious circle:
>   Hardware designers:  no language has popcount and first1, so we see no
> reason to support it in hardware.
>   Language designers: hardware does not support these, so why should
> our language?
> Break the cycle - put these in D!   This'll speed up chess programs by
> a factor of 2.
> 

Well if we generalise the concept of array slicing to index generator
functions.  

Then if onebits(b) returned the index for 1-bits in b then you example
could be written:

foreach(c in onebits(b))
{
printf("%d,", c);
}

and popcount(b) as onebits(b).length

expanding the generator functions to more dimensions would be very 
helpful in numerical calculations.
Ex. the generator function symmetric(3) generated the 3 dimensional
symmetric permutations e.g.:
(0,1,2)
(2,0,1)
(1,2,0)
and antisymmetic(3):
(0,2,1)
(2,1,0)
(1,0,2)

then using the vectorzation syntax from
http://all-technology.com/eigenpolls/dwishlist/index.php?it=10

the determinant of the 3x3 matrix "a" can be written by.
det=sum([i in symmetric(3)](a[0,i[0]]*a[1,i[1]]*a[2,i[2]))
-sum([i in antisymmetric(3)](a[0,i[0]]*a[1,i[1]]*a[2,i[2]));

and the general nxn case can be written as 
det=sum([i in symmetric(n)](multiply([j in 0..n](a[j,i[j]]))) 
-sum([i in antisymmetric(n)](multiply([j in 0..n](a[j,i[j]])));

If the generator function is defined by a constant like symmetric(3) 
the loop should be unfolded at compiler time for optimal speed.

D could use a interface for defining index generator functions
such that this is possible.