RFC 81 (v2) Lazily evaluated list generation functions

This and other RFCs are available on the web at
  http://dev.perl.org/rfc/

=head1 TITLE

Lazily evaluated list generation functions


=head1 VERSION

  Maintainer: Jeremy Howard <[email protected]>
  Created: 10 August 2000
  Last modified: 16 August 2000
  Version: 2
  Mailing List: [email protected]
  Number: 81

=head1 ABSTRACT

This RFC proposes that the existing C<..> operator produce a lazily
evaluated list. In addition, a new operation C<:> is proposed that allows
for the generation of lazily evaluated lists based on any Perl expression.

This proposal only discusses these operators in a list context. The
current meaning of '..' in a scalar context is not affected.

=head1 CHANGES

=head2 Since v1

=over 4

=item *

Changed notation to generate lists using previous element value from
I<(@start:&gen:$num_steps)> to I<(@start..&gen:$num_steps)>

=item *

Made I<(@start:&gen:$num_steps)> create a list that does not require
intermediate values to be calculated

=back

=head1 DESCRIPTION

This RFC proposes that Perl incorporate a broader tool box of list
generation techniques:

=over 8

=item *

Lazy evaluation of generated lists

=item *

Introduction of C<:> to generate arbitary lists

=back

These techniques would allow programs written in Perl to follow a
structure familiar to programmers used to numerical programming
environments. It would provide a more compact notation for many common
mathematical algorithms, and give Perl important information to make key
optimisations.

=head2 Lazy evaluation of generated lists

The C<..> of previous Perls is a I<list generation operator>, which
creates a list based on its parameters:

  ($start..$stop); # ($start, $start+inc, $start+2*inc, ... $stop)

where 'inc' is 1 if $start<$stop, or -1 otherwise. The list is generated
as soon as it is declared. These makes some code rather inefficient:

  @a = (1..1000000);   # One million element list generated here
  print $a[999999];

creates a one million element list despite only using one element of it.
Under I<lazy evaluation>, elements of the list are only created when they
are required, and saved for later use. In the previous example only
$a[999999] would be calculated by interpolation (not sequentially) and
stored when using lazy evaluation.

Lists, whether generated lazily or not, are assumed to be I<stable>. That
is, the value of $a[999999] will be the same everywhere in a program,
unless @a itself is modified. This means that lazily evaluated lists
provide a handy notation for memoization, as we will see later. It is
proposed that once an element has been calculated in a list, that it is
cached for use later rather than recalculated each time.

Lazy list elements get calculated when they are output, or used in an
expression that is output. If list elements are not output then they are
never calculated.

=head2 Introduction of C<:> to generate arbitary lists

It is proposed that a new operator be added to Perl's list generation
arsenal, C<:>. The ':' character is chosen because it reflects standard
notation for array slicing, which is an important use of this operator.

C<:> is only meaningful when called in a list context, generating a lazily
evaluated list in one of 3 ways.

=over 4

=item 1. I<($start..$end:$step)>

Although earlier Perls could create ascending and descending lists
incrementing by one, other increments required an unwieldy map:

  @threes = map {3*$_} (1..5);   # (3,6,9,12,15)

which was also less than intuitive to those used to the simple slicing
notation of numerical programming languages such as Matlab and IDL.

This proposed use of C<:> is identical to C<..> without C<:>, except that
it increments by $step rather than 1. Specifically, returns a list
($start, $start+$step, $start+2*$step, ... $end). If $step does not go
into ($end-$start) exactly, the last element of the list is the largest
number in the series less than or equal to $end.

$step is any non-zero number (not necessarily an integer). $step is
optional--if it's missing then $step is the same as if the C<:> wasn't
there at all. For example:

  (1..5:2);   # (1,3,5)
  (1..5:);    # Same as (1..5)
  (1..-5:-2);  # (1,-1,-3,-5)
  (1..5:-2);  # () Empty list

This slicing notation is particularly useful for dealing with arrays,
matrices, and tensors:

  @matrix = (1,3,4,
             2,6,7);
  @column1of3 = (1..10000:3);   # (1,4,7,...10000)
  print sum(@matrix[@column1of3]);          # Prints 3
  @matrix2 = readBig3ColumnMatrixFromSomewhere();
  $column1Sum = sum(@matrix2[@column1of3]); # No need to redefine our slice!

Note that more complex slicing, masking, and indirection across
n-dimensional tensors would make the win of not having to respecify the
indexes more substantial than in this simplified example.

=item 2. I<($start:$end:$step)>

An alias for ($start..$end:$step), to keep things familiar for folks
moving over from over languages supporting similar notation.

=item 3. I<(@start..&gen:$num_steps)>

The most general form of this is to provide a syntax to create bounded or
unbounded lists whose elements are generated by any arbitary function:

  ($start, &gen($start), &gen(&gen($start)), {$steps times}...);

This is created using the notation:

  ($start..&gen:$steps);

As before, $start is required (but need not be an integer). &gen takes one
parameter, which is the value of the previous element. For example:

  @first5PowersOf2 = (1..sub {$_[0]*2}:5);   # (1,2,4,8,16)

Because lists are memoized automatically, when we later say:

  print $powersOf2[4];

The value of $powersOf2[4] is pulled from the memoization cache rather
than recalculated. What's more:

  print $powersOf2[5];

is calculated from $powersOf2[4], rather than having to recalculate all
the in-betweens again, because of that caching.

This form of list generation can not generate the Fibonnaci sequence,
because it is not defined by a single $start, and it has more than
one parameter in its generator function. This requires a more
generalised form:

  ((@start)..&gen:$num_steps)

which allows us to say:

  @fib = ((1,1).. ^prev + ^next: 5);   # (1,1,2,3,5)

if we use the higher-order function notation proposed in RFC 23.

=item 4. I<(@start:&gen:$num_steps)>

The C<(@start:&gen:$num_steps)> notation makes it easy to generate lists
that depend on the value of the previous element. For lists where the
element is a direct function of the index, the comma operator could be
used to disregard the previous element:

  @even_numbers = (1.. ^prev, ^next*2: 5);   # (2,4,6,8,10)

Because this is a messy way of doing a common operation, and because we
want Perl to know how to generate one element of these lists without
having to generate all previous elements, the following notation is
proposed to achieve the same effect:

  @even_numbers = (1:^next*2: 5);   # (2,4,6,8,10)

This version of a lazily generated list is effectively a memoized function
that restricts its domain to the natural numbers. However it can be used
in some important additional roles--in particular, as a list index:

  @sub_list = @a[@even_numbers];

=back

=head1 IMPLEMENTATION

It will be common in numerical programming to see multiple layers of
indirection:

  @a = (1:5:100000);
  @b = getBigImage();
  @c = @a(@b);
  print $c[5];

In these cases Perl should consolidate as much as possible at compile time
to avoid too much overhead.

=back

=head1 REFERENCES

RFC 23: Higher-order functions

RFC 24: Semi-finite (lazy) lists

RFC 82: Apply operators component-wise in a list context

Memoization in Perl: 
http://www.plover.com/~mjd/perl/MiniMemoize/

List comprehension in Haskell:
http://www.numeric-quest.com/haskell/hcompanion/principles.html#List
comprehension

Fethi Rabhi and Guy Lapalme: 
I<Algorithms: A functional programming approach>,
Addison-Wesley, 235 pages, paperback, 1999. ISBN 0-201-59604-0

=head1 ACKNOWLEDGEMENTS

Damian Conway: Reviewed first draft

Karl Glazebrook: Suggested splitting from infinite lists proposal

Christian Soeller: Original 'slice' RFC; suggested argument reordering

Dan Sugalski: Implementation ideas