develooper Front page | perl.perl6.language.data | Postings from September 2000

RFC 207 (v2) Arrays: Efficient Array Loops

From:
Perl6 RFC Librarian
Date:
September 21, 2000 15:47
Subject:
RFC 207 (v2) Arrays: Efficient Array Loops
Message ID:
20000921224753.9009.qmail@tmtowtdi.perl.org
This and other RFCs are available on the web at
  http://dev.perl.org/rfc/

=head1 TITLE

Arrays: Efficient Array Loops

=head1 VERSION

  Maintainer: Buddha Buck <bmbuck@14850.com>
  Date: 8 Sep 2000
  Last Modified: 21 Sep 2000
  Mailing List: perl6-language-data@perl.org
  Number: 207
  Version: 2
  Status: Developing

=head1 ABSTRACT

This RFC proposes a notation for creating efficient implicit loops over
multidimensional arrays. It introduces the notation |i for an index
iterator for arrays, allowing temporary multidimensional arrays to be
created on the fly.

=head1 CHANGES

Version 2 is an almost complete rewrite, based on concerns and
enhancements that arose in discussion.  I was also unhappy with the
language in the original.  The primary semantic changes are:

* The syntax formerly known as "iterators" is now known as "looping
indices"

* |i is interpreted as "scalar-like", rather than "list-like". The
examples are now (to the best of my knowledge) consistant with that
interpretation.

* The scoping mechanism is enhanced.  It is now clearer what the
iterators mean in the various contexts within perl.

I believe the current version is much more understandable.

=head1 DESCRIPTION

Consider the problem of multiplying together two 2-dimensional tensors. In
standard notation, this would be symbolized by

    Cijkl = Aij * Bkl

where the letters i, j, k and l are written as subscripts and represent
the indices of their respective tensors. To accomplish that same
multiplication in Perl, one needs to write (using RFC 204 notation):

for my $i = (0..2) {    #assuming 3x3 tensors
   for my $j = (0..2) {
     for my $k = (0..2) {
       for my $l = (0..2) {
           $c[[$i,$j,$k,$l]] = $a[[$i,$j]] * $b[[$k,$l]] ;
       }
     }
   }
}

While this is not particularly difficult, it is clumsy, and slow. It could
be hidden in a subroutine, but then one lacks the flexibility to write
similar equations on the fly. For instance, transposition is easily
written as Tij = Aji. Such notation is assumed to be true for all legal
values of i and j -- in effect, it loops over all legal values of i and j
to compute the results. Furthermore, such notation along with appropriate
restrictions on use could allow Perl to create optimised loops.

This RFC proposes a similar notation, using |name as a notation for
looping indices like i and j above.

=head2 Details

This RFC proposes that the entire
The prefix | signifies that |i is an "looping index" within the
statement |i appears in.  More than one looping index can appear
within one statement.

The "scope" of a set of looping indices is the smallest subexpression
in the statement that contains all the looping indices in the
statement.  If the scope is not in list or void context, the scope is
expanded until it is in list or void context.  The scope of a set of
looping indices will never exceed one statement.

A set of looping indices generates an implicit loop (or nested loops)
surrounding the scope of the indices.

If used in list context, the implied loop creates a temporary array
whose dimensions and bounds are determined by the number and range of
the looping indices.

=over 4

     # In list context
     $dotproduct = reduce ^_+^_, 0, $a[|i] * $b[|i];
     @tensorproduct = $a[[|i,|j]] * $b[[|k,|l]];

=back

When there are multiple looping indices in an expression in list
context, the order of the indices in the temporary array is determined by
scanning the expression left-to-right.

If used in a void context, the implied loop does not create a
temporary array, but rather expects the side effects (if any) to do
the real work.

=over 4

     # In void context
     $c[[|i,|j,|k,|l]] = $a[[|i,|j]]*$b[[|k,|l]]; # compare with loop above

     $t[[|i,|j]] = $a[[|j,|i]];
     $product[[|i, |j]] = $a[[|i,|k]] * $b [[|k,|j]];
     $dotproduct += $a[|i] * $b[|i];  # tmtowdi
     $stack = $a[|i]; # $stack->STORE is TIEd to $stack->push($)

=back

As the two example shows, assignment to a scalar is assumed to be in
scalar context, not list, and so the scope of the looping indices is
expanded to include  the LHS of the assignment.

Looping indices can also have a user-defined range, using the syntax
"|i=@list".  This would create a bounding loop of the form "for |i
(@list) {...}" around the expression.  When no list explicitly given,
|i acts as if (0..) was the specified list.  The range for a looping
index can be specified anywhere in the statement, but only one range
can be given per looping index.

=over 4

     # take the upper-triangle of a square array
     $uppertri[[|i,|j]] = 0;  # clear array to begin with
     $uppertri[[|i,|j]] = $a[[|i,|j=(0..|i)]];

=back

Strictly speaking, |i does take on all the values in @list (or (0..)),
but rather solely those values which lead to valid (in bounds) array
indices.

=over 4

    # "unriffle" two arrays.  There are probably better ways to do this
    ($a[|i], $b[|i]) = ($c[ 2*|i ], $c[ 2*|i + 1 ]);
    $average[|i] = ($a[|i-1] + $a[|i] + $a[|i+1])/3;

=back

In the first example, |i will never take on values that would cause
2*|i+1 to be out of bounds for $c.

As mentioned above, using multiple looping indices  will cause a
nested loop.  The order of nesting the loops is not specified here,
but any interdependencies among the indices must be satisfied.

In most of the examples above, the loops caused by the multiple
iterators are independent.  However, in the "upper triangle" example,
since the range of |j depends on the current value of |i, |i must be
the "outer loop".

In expressions containing looping indices and RFC205-style Cartesian-product
array slices (e.g., $matrix[|x;@y]), each explicit (or implicit) non-singleton
argument to ; acts as if it were an anonymous iterator using the explicit (or
implicit (0..)) range list.  Each anonymous iterator is independent of
each other.  This can be very powerfull, especially when combined with
the * operand to ;:

=over 4

     # Generalized tensor multiplication:
     @product = $a[|i;*] * $b[|j;*];

=back

The use of ; also makes it easier to express long lists of looping
indices.  $array[[|1,|j,|k]] is equivilant to $array[|i;|j;|k], but
doesn't use as much punctuation.

Looping indices aren't restricted to being used solely as array
indices, as the "unriffle" example showed.  But each looping index has
to be used in an array index for at least one array.

=over 4

     # find $nth triangular number
     my $triangle = 0;
     $triangle += |i=(0..$n);   # compile-time error: |i not used as index

     # Fill a multiplication table
     my @multtable : shape(12,12);
     $multtable[|i;|j] = |i*|j; # OK

=back

=head Lazy Evaluation

Assuming that lazy evaluation is used in other parts of Perl6, it
would be nice if these loops could also be evaluated lazily.

In list context, this could be done by creating an anonymous function
to evaluate the looped expression at the desired indices:

=over 4

     $a[|i]*$b[|j]  # in list context
     # becomes

     sub { my ($i,$j) = @_; $a[$i]*$b[$j]; }

=back

This anonymous function can be TIEd to the resulting anonymous array,
so all array lookups would invoke this function.  Since TIEing is
supposed to be improved in Perl6, this would be a reasonable way to do
it.

If other lazy evaluation mechanisms work in Perl6, they could be used
instead.

I am uncertain if lazy evaluation makes sense in void context.

=head2 Examples:

=over 2

   $t[[|i,|j]] = $a[[|j,|i]];  # transpose 2-d @a

=back

would be equivilant to:

=over 2

   {
     my $i; my $j
     for $i (0..) { # last if out-of-bounds
       for $j (0..) { # last if out-of-bounds
         $t[[$i,$j]] = $a[[$j,$i]];
       }
     }
   }

=back

This notation also allows (as a specific use) an alternative notation
to the RFC 82 element-wise syntax.

=over 2
   #compute pairwise sum, pairwise product, pairwise difference...
   @sum = @a[[|i,|j,|k,|l]] + @b[[|i;|j;|k;|l]];  # RFC82: @sum  = @a + @b
   @prod= @a[[|i,|j,|k,|l]] * @b[[|i;|j;|k;|l]];  #        @prod = @a * @b
   @diff= @a[[|i,|j,|k,|l]] - @b[[|i;|j;|k;|l]];  #        @diff = @a - @b

=back

RFC 82 syntax is simpler, but this is perl, so There Is More Than One
Way To Do It.

Note that if the "Lazy Evaluation" schema mentioned above is adopted,
then these sums, products, and differences could be automagically lazy
as well.

=head1 IMPLEMENTATION

The simplest implementation would be to convert at compile-time (or
parse time) void-context looped iterator scopes to loops analogous to
the above examples, and convert list-context looped iterator scopes to
valued do-blocks or invoked anonymous subroutines:

=over 4

     $dotproduct = reduce {^_+^_},0,$a[|i]*$b[|i];

     # would be transformed into

     $dotproduct = reduce {^_+^_},0,
        sub { my $i; my @r;
              for $i (0..min($#a,$#b)) {
	       $r[$i] = $a[$i] * $b[$i];
              }
              return @r;
            }->();

=back

A more sophisticated, preferred, implementation would take advantage
of the static, known nature of the data to create a highly optimized
version of the loop.

Possible optimizations include: Common sub-expression elimintation,
encoding internally to some non-interpreted looping construct, etc. If
special 'numeric functions' are provided in Perl, then expressions
with just unoverloaded operators and numeric functions could be
optimised into tight compiled loops, as occurs for example with
fromfunction() and ufuncs in Numeric Python:

   http://starship.python.net/~da/numtut/array.html#SEC8
   http://starship.python.net/~da/numtut/array.html#SEC13

For lazy evaluation, the value of the expression at any given set of
indices is easy to calculate. However the lazy evaluation mechanism works,
it can use this property to calculate the appropriate values.

=head1 REFERENCES

RFC 203: Notation for declaring and creating arrays

RFC 204: Notation for indexing arrays with an LOL as an index

RFC 205: New operator ';' for creating array slices





nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About