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

RFC 204 (v1) Arrays: Notation for declaring and creating arrays

From:
Perl6 RFC Librarian
Date:
September 8, 2000 15:38
Subject:
RFC 204 (v1) Arrays: Notation for declaring and creating arrays
Message ID:
20000908223809.17792.qmail@tmtowtdi.perl.org
This and other RFCs are available on the web at
  http://dev.perl.org/rfc/

=head1 TITLE

Arrays: Notation for declaring and creating arrays

=head1 VERSION

  Maintainer: Jeremy Howard <j@howard.fm>
  Date: 8 September 2000
  Mailing List: perl6-language-data@perl.org
  Number: 204
  Version: 1
  Status: Developing

=head1 ABSTRACT

RFC 202 described the need to be able to declare a data structure that
contains elements of the same type stored contiguously in memory, which is
called an I<array>. This RFC outlines the syntax to declare and create
arrays. The syntax to create arrays is identical to that to create lists
of lists (described in L<perllol> in the Perl 5 documentation). The syntax
to declare the type of elements is the standard type syntax.

RFC 203 describes a syntax for multidimensional indexing of arrays. A
syntax to declare the bounds of the dimensions is described in this RFC
using a new ':bounds' attribute.

=head1 DESCRIPTION

It is proposed that if a list is declared that specifies a simple type for
its elements:

  my int @a;
  
then that list be stored as an array--that is, contiguously in memory.
These arrays support I<all> the same syntax as lists. Therefore any
description of syntax for a 'list' also applies to an 'array', and visa
versa. However, their implementation is very differenct.

Furthermore, it is proposed that lists accept a new C<:bounds> attribute:

  my @a :bounds(3);

that defines the maximum index for a list. This is equivalent to:

  my @a;
  $#a = 3;
  
except that an attempt at accessing beyond $a[3] would result in an error
if :bounds(3) is set.
  
The :bounds attribute can also accept a list:

  my @b :bounds(3,3);

The second element of the list is the maximum index of the list, as
before. The first element is the maximum index of lists that are
referenced as elements of the list. Therefore

  my @b :bounds(3,3);
  $b[3][4] = 0;   # Error: access beyond bounds of @b

would result in an error. :bounds can take as many arguments as
required--an n-element list declares a list with at most n levels of
nesting, with the maximum index at level x being (n-x). Because lists of
lists support multidimensional indexing (see RFC 204) the :bounds attribute
effectively specifies the bounds of a multidimensional structure.

Efficient multidimensional arrays can be declared by combining a fixed
simple type with the :bounds attribute:

  my int @b :bounds(3,3);

Perl in this case would set aside enough room for sixteen ints, and store
an attribute with @b that it had two dimensions, each indexed by (0..3).
Because @b here is stored as an array, and supports multidimensional
indexing (see RFC 204), it is a true multidimensional array.

Although @b looks just like a normal list of lists that happens to
have a type and an attribute, it is implemented as a multidimensional
array. Therefore

  my int @b :bounds(3,3);
  @b = ([1,2,3,4],
        [5,6,7,8],
        [9,10,11,12],
        [13,14,15,16]);

creates a multidimensional array @b that contains all sixteen ints in a
contiguous block of memory, but can be accessed using standard list of
lists syntax, along with the extensions proposed in RFC 204.

The bounds of an array or list can be specified at run time, of course:

  my int @t1 :bounds(@dimList) = getFromSomeplace();

Where the type and bounds of an array can be derived at run time, it is
not necessary to specify them explicitly:

  my int @t1 :bounds(@dimList) = getFromSomeplace();
  my int @t2 :bounds(@dimList) = getFromSomeplaceElse();
  my @prod = @t1 * @t2;   # @prod magically has type (int) and :bounds (@dimlist)

Note that this is using an element-wise multiplication operation,
described in RFC 82.

A list (of lists...) that contains elements of the same type can be
converted to an array by specifying its type:

  my @some_LOL = ([1,2],
                  [3,4]);
  my int @array = @some_LOL;
  
and its bounds can be locked in as well if required:

  my @some_LOL = ([1,2],
                  [3,4]);
  my int @array :bounds(@#some_LOL) = @some_LOL;

=head1 IMPLEMENTATION

Too early to get into much detail beyond the obvious... Clearly arrays are
not a list of SVs, but are the raw data stored contiguously in memory,
along with the attributes of the array stored someplace.

:bounds applies to lists as well, of course (because lists and arrays
share identical syntax), but this should be fine because its just an
attribute.

Arrays do not require :bounds to be specified. If not specified, they
should grow by doubling in size (like lists), but programmers will be
encouraged to avoid this because a new contiguous memory block will have
to be found each time. Programmers may also specify bounds after the fact
with '@#' (see RFC 206), which will also require a new block of memory.

=head1 REFERENCES

RFC 202: Overview of multidimensional array RFCs 

perllol in the Perl 5 documentation

Implementation in PDL: http://pdl.sourceforge.net/PDLdocs/Internals.html




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