From:

Date:

August 29, 2000 06:35Subject:

Proposed RFC for matrix indexing and slicingMessage ID:

4.3.2.7.0.20000829093356.00c225b0@armstrong.cse.buffalo.eduThis is a copy of the RFC I sent to the Librarian. I don't know when the Librarian will publish it, but I don't want to wait any longer... We can discuss it while he is compiling/classifying/publishing it. ---------------------------------- =head1 TITLE Proposed syntax for matrix element access and slicing. =head1 VERSION Maintainer: Buddha Buck <bmbuck@14850.com> Date: 28 August 2000 Version: 1 Mailing List: perl6-language-data Number: =head1 ABSTRACT I propose the use of ';' as a separator for index terms when accessing multi-dimensional arrays (matrices). The syntax "$matrix[$w;$x;$y;$z];" is clearer and more flexible than other proposed alternatives. The flexibility is mainly in the possibility of a robust slicing syntax. Although I know of no RFC's that recommend the implementation of matrices, I expect such a proposal to be made, and this RFC does not make such a suggestion. =head1 DESCRIPTION Several suggestions have been made for matrix element accessors, including: $matrix[$x][$y][$z] # aka "(Lo)*L" notation ( (lists of)* lists) $matrix[$x,$y,$z] # aka "[,,]" notation $matrix{"$x,$y,$z"} # aka hash notation All three of these have problems. The (Lo)*L notation either requires matrices be (lists of)* lists, or uses the same syntax for both matrices and (lists of)* lists. The hash notation has the same confusion, but with hashes. The [,,] notation is too similar to the existing syntax for array slices. None of them allow for convenient matrix slicing. Using $matrix[$i;$j;$k;$l] has the advantage that it is dissimilar from exising syntax, thus minimizing confusion with pre-existing data structures, and it provides a clean separation of indices, allowing for a flexible slice notation. =head2 Matrix Element Access. Matrix elements should be accessed as normal arrays, but using ";" to separate the indices: my @matrix; $matrix[1;2;3;4] = 5; sub tensor2mul { my @tensor1 = @{shift @_}; my @tensor2 = @{shift @_}; my @tensor3; for $i (0..3) { for $j (0..3) { for $k (0..3) { for $l (0..3) { $tensor3[$i;$j;$k;$l] = $tensor1[$i;$j] * $tensor2[$k;$l]; } } } } return @tensor3; } Currently, ';' is only used for statement separators and as term separators in for(;;) loops. This new proposed use should not be a problem for the parser or programmers to understand in this context. =head2 Matrix Slices Because the indices are separate, array slice notation can easily be used for the individual indices. #exlude row $j and column $k, as if taking a determinant. @submatrix = @matrix[0..$j-1,$j+1..$n;0..$k-1,$k+1..$n]; While that should work obviously enough, a more flexible syntax would be nice: # leave index blank for "all" # or use unterminated ".." @row = @matrix[1;]; # @row = @matrix[1;..]; @col = @matrix[;1]; # @col = @matrix[..;1]; @swaprow = @matrix[1,0,2..$n;] # Use ^var to get more complicated slices @diagonal = @matrix[^i;^i]; @rdiagonal = @matrix[^i;$n-$i]; @uptriangle = @matrix[^i;0..$i]; @lowtriangle = @matrix[^i;$i..$#]; # These would be nice, but probably not feasable @trans[^i;^j] = @matrix[^j;^i]; @tensor3[^i;^j;^k;^l] = @tensor1[^i;^j] * @tensor2[^k;^l]; $dotproduct = reduce ^1+^2 , 0, a[^_] * b[^_]; Those above would work if the ^vars would scope across all indices in the statement, not just one. # use $# to get maximum val for index sub lowtriangle { @matrix = @{ shift @_ }; return @matrix[^i;^i..$#]; # works for all 2-d matrices. } Matrices of more than two dimensions should be handled similarly: # Slice through middle of cube perpendicular to main diagonal @slice = @matrix[^i;^j;^i-^j]; The use of the ^var syntax is analogous to the use of ^placeholder syntax in Damian Conway's HOF RFC. =head2 Computing the size of matrices I'd propose that, analogous to the $#array notation for revealing the upper index of @array, @#matrix return the analogous list: my @matrix $matrix[2;2;2] = 1; @sizes = @#matrix; # @sizes == (2,2,2) $numdim = @#matrix; # array in scaler context. =head2 Unresolved issue -- variable dimensionality Right now, the syntax above hardcodes the dimension of a matrix in the index list. This does not allow you to write programs which manipulate $n-dimensional matrices, where $n is computed at run-time. This is unfortunate, and I'd like to hear suggestions on how to deal with that issue. One possible mechanism would be to allow @k = @matrix[$n;]; to always assign to @k a matrix of one less dimension that @matrix, regardless of the original dimensionality, with the exception that @array[$n;] will return a singleton list rather than a 0-dimension matrix (which should by rights be a scalar). How that should generalize is not clear. =head2 Unresolved issue -- ^var slices and HOF Damian Conway suggested a HOF syntax which used ^var as a placeholder. The "reduce" example above shows how confusing using both HOF and ^var slices in the same expression can be. Originally, I thought this wouldn't be a problem because closures are not allowed as array indices, so @a[^i;^j] would be unambiguous. But this precludes being able to say: my &closure = $matrix[^_;^_]; # closure(1,2) == $matrix[1;2] my &c2 = closure(^_,5) ; c2(4) == $matrix[4;5] I think both functionalities are powerful and useful. I would appreciate how to get both of them unambiguously and cleanly. =head1 IMPLEMENTATION Using ; as a indices separator should cause no serious problems of implementation. The use of ^var indices could, in a reference implementation, be syntactic sugar for something like: @matrix[^i;^j;^k;^k] ==> do { my @result; my ($i,$j,$k); my @indices = @#matrix; for $i (0..$indices[0]) { for $j (0..$indices[1]) { for $k (0..$indices[2] { $result[$i;$j;$k] = $matrix[$i,$j,$k,$k]; } } } @result; } It should be noted that the matrix slice operations are likely to be inherently O(k), where k is the number of dimensions indexed over. =head1 REFERENCES RFC 24: "Higher Order Functions"Thread Next

**Proposed RFC for matrix indexing and slicing**by Buddha Buck- Re: Proposed RFC for matrix indexing and slicing by Jeremy Howard
- Re: Proposed RFC for matrix indexing and slicing by Buddha Buck
- Re: Proposed RFC for matrix indexing and slicing by David L. Nicol
- Re: Proposed RFC for matrix indexing and slicing by Nathan Wiger
- Re: Proposed RFC for matrix indexing and slicing by Jeremy Howard
- Re: Proposed RFC for matrix indexing and slicing by Dan Sugalski
- Re: Proposed RFC for matrix indexing and slicing by Dan Sugalski
- Re: Access to the perl6 parser by Damian Conway
- Re: Access to the perl6 parser by Damian Conway
- Re: Access to the perl6 parser by Damian Conway
- Re: Access to the perl6 parser by Dan Sugalski
- Re: Access to the perl6 parser by Christian Soeller
- Re: Proposed RFC for matrix indexing and slicing by Christian Soeller
- Re: Proposed RFC for matrix indexing and slicing by Karl Glazebrook
- Re: Proposed RFC for matrix indexing and slicing by Dan Sugalski
- Re: Proposed RFC for matrix indexing and slicing by Nathan Torkington
- Re: Proposed RFC for matrix indexing and slicing by Dan Sugalski
- Re: Proposed RFC for matrix indexing and slicing by Jeremy Howard
- Re: Proposed RFC for matrix indexing and slicing by Karl Glazebrook
- Re: Proposed RFC for matrix indexing and slicing by Bart Lateur
- Re: Proposed RFC for matrix indexing and slicing by c.soeller
- Re: Proposed RFC for matrix indexing and slicing by Karl Glazebrook
- Re: Access to the perl6 parser by Dan Sugalski
- Re: Access to the perl6 parser by Dan Sugalski
- Re: Access to the perl6 parser by Christian Soeller
- Re: Access to the perl6 parser by Jim Edwards
- Re: Access to the perl6 parser by Jim Edwards
- Access to the perl6 parser by Jim Edwards
- Re: Proposed RFC for matrix indexing and slicing by Karl Glazebrook
- Re: Proposed RFC for matrix indexing and slicing by Karl Glazebrook
- Re: Proposed RFC for matrix indexing and slicing by Buddha Buck

nntp.perl.org: Perl Programming lists via nntp and http.

Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About