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
