Author: ruoso Date: 2008-11-27 14:20:22 +0100 (Thu, 27 Nov 2008) New Revision: 24088
Added: docs/Perl6/Spec/S07-iterators.pod Log: [spec] Adding the first sketches on S07, thanks to wayland76++ Added: docs/Perl6/Spec/S07-iterators.pod =================================================================== --- docs/Perl6/Spec/S07-iterators.pod (rev 0) +++ docs/Perl6/Spec/S07-iterators.pod 2008-11-27 13:20:22 UTC (rev 24088) @@ -0,0 +1,256 @@ +=encoding utf8 + +=head1 Title + +Synopsis 7: Iterators and Laziness + +=head1 Version + + Maintainer: ??? + Contributions: Tim Nelson <[EMAIL PROTECTED]> + Daniel Ruoso <[EMAIL PROTECTED]> + Date: 27 Nov 2008 + Last Modified: 27 Nov 2008 + Version: 1 + +=head1 Laziness and Eagerness + +As we all know, one of the primary virtues of the Perl programmer is +laziness. This is also one of the virtues of Perl itself. However, +Perl knows better than to succumb to false laziness, and so is eager +sometimes, and lazy others. Perl defines 4 levels of laziness for +Iterators: + +=over + +=item Strictly Lazy + +Does not evaluate anything unless explictly required by the user, +including not traversing non-lazy objects. + +=item Mostly Lazy + +Try to obtain available items without causing eager evaluation of +other lazy objects. + +=item Mostly Eager + +Obtain all items, but does not try to eagerly evaluate when known to +be infinite. + +=item Strictly Eager + +Obtain all items, fail in data structures known to be infinite. + +=back + +It's important to realize that the responsability of determining the +level of lazyness/eagerness in each operation is external to each lazy +object, the runtime, depending on which operation is being performed +is going to assume the level of lazyness and perform the needed +operations to apply that level. + +=head2 The lazyness level of some common operations + +=over + +=item List Assignment: my @a = @something; + +In order to provide p5-like behavior in list assignment, this +operation is performed in the Mostly Eager level, meaning that if you do + + my @a = grep { ... }, @b; + +the grep will be evaluated as long as @b is not infinite. + + my @a = grep { ... }, 1, 2, 3, 4..* + +will give grep an infinite list (even if the first elements are +known), therefore it will also be lazy. On the other hand + + my @a = grep { ... }, 1, 2, 3, 4; + +will be eagerly evaluated. + +=item Feed operators: my @a <== @something; + +The feed operator is strictly lazy, meaning that no operation should +be performed before the user requests any element from @a. That's how + + my @a <== grep { ... } <== map { ... } <== grep { ... }, 1, 2, 3 + +is completely lazy, even if 1,2,3 is a fairly small known compact +list. + +=back + +But it's important to notice that eagerness takes precedence over +lazyness, meaning that + + my @a = grep { ... } <== map { ... } <== grep { ... }, 1, 2, 3 + +Will be eagerly evaluated, but that is still different from + + my @d = 1,2,3; + my @c = grep { ... }, @d; + my @b = map { ... }, @c; + my @a = grep { ... }, @b; + +Because in the first, the processing would be made as a flow, avoiding +the creation of the intermediary eager lists that the second example +creates. On the other hand + + my @d <== 1,2,3; + my @c <== grep { ... }, @d; + my @b <== map { ... }, @c; + my @a = grep { ... }, @b; + +provides the same lazyness level of the first example. + +=head1 The Iterator Role + +The iterator role represents the lazy access to a list, walking +through a data structure (list, tree whatever), feeds (map, grep etc) +or and, each time it is called, will return one (or more) of the nodes +from the data structure. + +When an iterator runs out of items, it will throw an exception. + +The iterator role has the following methods: + +=head2 method prefix:<=> {...} + +Returns something appropriate depending on the context: + +=head2 method new(Laziness => $laziness, Context => $context) {...} + +Creates the iterator, with appropriate laziness defaults. + +=head2 method SetLaziness($laziness) {...} + +Set the Laziness + +=head2 method SetContext($context) {...} + +Set the Context (intended only for coercions, not user use) + +=head2 Iterator Summary + +=begin code + +role Iterator { + has $!laziness; + has $!context; + + # enforces item context + method FETCH() {...} + # returns a list + method List() {...} + # returns a slice + method Slice() {...} + # returns the capture of the next iteration + method prefix:<=> { + given $self.context { + when 'Item' { return self.FETCH() } # called in item context + when 'Slice' { return self.Slice() } # called in slice context + when * { return self.List() } # called in list context (or any other context) + } + } + # Creates a new iterator; can be called with no parameters, and chooses sensible defaults + method new(Laziness => $laziness, Context => $context) { + if(! $context) { + given want { + when :($) { $context = 'Item'; } # called in item context + when :(@@) { $context = 'Slice'; } # called in slice context + when * { $context = 'List'; } # called in list context (or any other context) + } + } + $self.context = $context; + self.SetLaziness($laziness); + } + method SetContext($context) { + $context ~~ /^(Item|List|Slice)$/) or die "Invalid context $context\n"; + $self.context = $context; + self.SetLaziness(); + } + method SetLaziness($laziness) { + if($laziness) { + $self.laziness = $laziness; + } else { + given $self.context { + when 'Item' { self.laziness = 'Mostly Lazy'; } + when * { self.laziness = 'Mostly Eager'; } + } + } + } +} + +=end code + +=head1 Default Implementations + +Perl's built-ins require that a number of default iterators exist. + +=head2 GenericIterator implementation + +This is what is returned by default when an iterator is asked for, but no iterator type is known. + +=head2 MapIterator implementation + +Example call: + +# this is a good example of loose context information anyway... + other_something(| map { ... }, something()) + +When the map is initiated(???) this does the following steps in order: + +=over + +=item Coerce the return of something to Iterator (returning an Iterator object, which we can call $input_iterator) + +=item Coerce the iterator to item context (calls $input_iterator.SetContext() ) + +=item Create and return a new iterator that holds a reference to both the input iterator and to the map codeblock + (lets call this $map_iterator) + +=back + +When data is requested from the $map_iterator, the following steps are taken: + +=over + +=item map calls $map_iterator.prefix:<=> and gets the next item (even if that means many iterations or no new iterations in the input data) + +=item $map_iterator.prefix:<=> calls $map_iterator.code($item) (the number of arguments is defined by the .arity of the signature, and a call to $input_iterator.prefix:<=> is made to get each argument.) + +=item map returns the capture with no context applied (which means that it might contain several or no items) + +=back + +=begin code + +class MapIterator does Iterator { + has $.input_iterator; + has $.code; + method FETCH() { + return GenericItemIterator.new(input_iterator => self); + } + method List() { + return GenericLazyList.new(input_iterator => self); + } + method Slice() { + return GenericLazySlice.new(input_iterator => self); + } + method prefix:<=> { + return $.code.(=$.input_iterator); + } +} + +=end code + +=head2 GrepIterator implementation + +=head1 Additions + +Please post errors and feedback to perl6-language. If you are making +a general laundry list, please separate messages by topic.