This and other RFCs are available on the web at
http://dev.perl.org/rfc/
=head1 TITLE
Implementation of hash iterators
=head1 VERSION
Maintainer: Tom Hughes <[EMAIL PROTECTED]>
Date: 20 Aug 2000
Version: 1
Mailing List: [EMAIL PROTECTED]
Number: 136
=head1 ABSTRACT
Perl 5 makes very limited use of iterators internally. It has long
been suggested that certain common idioms could be implemented much
more efficiently using iterators and this RFC suggests some possible
mechanisms for achieving this goal.
=head1 DESCRIPTION
=head2 How iterators work in perl 5
In perl 5 every hash has exactly one iterator, which can be used
explicitly by the programmer using the each function and which is
also used by perl implicitly to implement the keys and values
functions.
This is confusing and dangerous as you can easily get an action
at a distance effect whereby using each/keys/values in a function
affects the iteration being performed by the caller.
=head2 How iterators might work in perl 6
In perl 6 the keys and values functions should no longer use the
same iterator as the each function - each use of keys and values
should use it's own private iterator instead.
In fact those iterators should probably be lazy so that a piece
of code like this:
foreach (keys %x)
{
...
}
does not immediately iterate over the whole hash, pushing copies
of all the keys onto the stack; but should instead create an
iterator object of some sort that can be passed to the loop op
which will then pull off one value for each pass of the loop.
This is significantly more efficient for large hashes, especially
if the loop exits early.
The only problem with this system is that the current implementation
of keys and values causes the result to be frozen so that changes to
the hash made in the loop body do not effect the values being iterated
over.
I believe this problem can be solved by using the vtable for the
hash to wrap any mutating functions with a completion routine that
will advance the iterator to completion, creating a temporary list
of copied keys/values that it can then continue to iterate over.
Obviously after this completion was done the wrapper routine would
call the original vtable routine to update the hash. It would also
remove itself from the vtable so you would only pay the cost of the
wrapper on the first change to the hash. Equally you would only pay
for building the temporary list when it was necessary - ie when you
change the hash inside the loop.
For keys the iterator would need to trap insertions and deletions
and for values it would need to trap these and also modifications of
existing values.
Because this mechanism can sit above the main hash implementation
it should work equally for both builtin hashes and for things like
tied hashes where implementation details are unknown to the core.
=head1 REFERENCES
RFC 123: Builtin: lazy
perlfunc manpage for discussion of each, keys and values
