Re: What's the latest on Iterators?
On Sat, 12 Nov 2005, Larry Wall wrote: For example, this is guaranteed to have the side effect of running out of memory before it starts to print anything: print **1...; Speaking of which I wonder if it can be detected and cause an error to be emitted. Which is to say, if it is possible for the compiler to determine that a list is potentially infinite (i.e. no stopping mechanism, e.g. a last is present anywhere[*]) and being flattened at the same time. Since there may be some convoluted and intricated way to stop it, of course there should also be a pragma to locally disable the feature, of course... [*] Of course there may still be some code (boiling down to something) like last if 0; and the list would still be infinite and exhaust memory like the above, but one cannot expect the compiler to be smart enough to detect (all) cases like that, as fundamentally I think it reduces to the halting problem. Michele -- Shit Happens! - the predator, Predator 2 (1990)
Re: What's the latest on Iterators?
Larry Wall a écrit :
| On Fri, Nov 11, 2005 at 08:42:44AM -0500, Joe Gottman wrote:
| : Do functions like map and grep, which in Perl5 return lists, return
| : Iterators in Perl6?
|
| A list may contain iterators. Lists don't eagerly flatten in Perl 6.
|
| : Can an Iterator be passed to a function (like map and grep again)
| : that requires a list as an input?
|
| Certainly. You can pass as many iterators as you like. The range object
| is your prototypical iterator, and you can say:
|
| @results = grep {...} 0..9, 20..29, 40..49;
|
| The list that grep is returning can also function as an iterator, so
| @results isn't necessarily all there after the statement executes.
|
How can Perl6 can consistently cope with side effects if it is not
specified when evaluation is lazy or strict? Is there a trait to say
that a function (here the grepping predicat) does not have
side-effect or is also really functional (so as to permit various
optimizations)?
Ate they pragma to say, from here every function that will be defined will
by default functional or every parameter evaluation will be lazy:
use fun;
use lazy;
sub foo {$a } { ... } # functional and lazy
sub notfunctional($a) isnot fun {...) # can we unset a default attribute?
no fun; # use strict has another meaning btw.
...
use fun, lazy; # also can we do use bundling?
More generally I am worried of the mix of lazy and strict behavior in
the presence of all sorts of side effects that would happen in a random
order depending of the parameter evaluation order.
btw, for strict functions, is the left to right evaluation of
parameters guaranteed?
|
| Larry
|
--
cognominal stef
Re: What's the latest on Iterators?
On Sat, Nov 12, 2005 at 03:05:53PM +0100, Stéphane Payrard wrote:
: Larry Wall a écrit :
: | On Fri, Nov 11, 2005 at 08:42:44AM -0500, Joe Gottman wrote:
: | : Do functions like map and grep, which in Perl5 return lists, return
: | : Iterators in Perl6?
: |
: | A list may contain iterators. Lists don't eagerly flatten in Perl 6.
: |
: | : Can an Iterator be passed to a function (like map and grep again)
: | : that requires a list as an input?
: |
: | Certainly. You can pass as many iterators as you like. The range object
: | is your prototypical iterator, and you can say:
: |
: | @results = grep {...} 0..9, 20..29, 40..49;
: |
: | The list that grep is returning can also function as an iterator, so
: | @results isn't necessarily all there after the statement executes.
: |
:
: How can Perl6 can consistently cope with side effects if it is not
: specified when evaluation is lazy or strict?
It is my conjecture that it is not necessary to be totally consistent
about that most of the time, as long as people learn that list
context is consistently lazy by default (though the granularity of
that laziness is unguessable), and as long as we try to minimize
unnecessary side effects in the design of the rest of the langauge.
But people are already used to dealing with lazy evaluation of
things like file handles in Perl 5, and can know when they are
unsure of the order of evaluation, and install sync points to
compensate. That's really all a close is, after all. Or a
slurp, for that matter.
So Perl 6 has a standard for either the caller or callee to turn
off laziness, and in both cases it's the steamroller operator **.
It basically installs Perl 5 semantics for the rest of the list.
For example, this is guaranteed to have the side effect of running
out of memory before it starts to print anything:
print **1...;
: Is there a trait to say
: that a function (here the grepping predicat) does not have
: side-effect or is also really functional (so as to permit various
: optimizations)?
The lazy trait is the presence of an ordinary (non steamroller)
slurpy array in the signature. If I recall, Pugs already makes use
of an is pure trait that specifies no side effects, but it's also
the case that is cached implies pure functional behavior. On the
other hand, it's probably something the compiler should be figuring
out anyway, since it will probably be more honest than a person about
when it's guessing.
: Ate they pragma to say, from here every function that will be defined will
: by default functional or every parameter evaluation will be lazy:
:
: use fun;
: use lazy;
:
:sub foo {$a } { ... } # functional and lazy
:
:sub notfunctional($a) isnot fun {...) # can we unset a default attribute?
:
: no fun; # use strict has another meaning btw.
: ...
: use fun, lazy; # also can we do use bundling?
Such pragmas are certainly possible, but the default of scalar context
being nonlazy and list context being lazy feels about right to me, as
long as we provide easy ways to override. The ** in list context will
force evaluation of lazy arguments, while in scalar context, junctions
and hyperoperators implicitly declare that ordering doesn't matter
for that particular operation.
: More generally I am worried of the mix of lazy and strict behavior in
: the presence of all sorts of side effects that would happen in a random
: order depending of the parameter evaluation order.
Welcome to the world of parallel programming, and remote objects,
and software transactional memory, and virtual timelines. The entire
universe runs on side effects happening in random order. We'll have to
learn how to balance out determinism with efficiency, and unfortunately
we don't know of any efficient way to be deterministic except in
certain specific cases.
: btw, for strict functions, is the left to right evaluation of
: parameters guaranteed?
Yes, for some definition of evaluation that may or may not imply
final resolution of all side effects. You still probably shouldn't
depend on
print $i++, $i++;
working any particular way, despite the fact that it works consistently
in the one and only implementation of Perl 5.
And if I'm wrong about all this, it'll still be easy to add a pragma
that implies ** on every list.
Larry
What's the latest on Iterators?
The various synopses contain many mentions of Iterators. These are used, for instance, to implement lazy lists so the expression 1..1_000_000 does not have to allocate a million element array. But as far as I can tell the term is never defined anywhere in the synopses. Is Iterator a role, and if so what methods is it required to have? Do functions like map and grep, which in Perl5 return lists, return Iterators in Perl6? Can an Iterator be passed to a function (like map and grep again) that requires a list as an input? Does an array or hash have only one Iterator or can it have several independent ones? Joe Gottman
Re: What's the latest on Iterators?
On 11/11/05, Joe Gottman [EMAIL PROTECTED] wrote:
The various synopses contain many mentions of Iterators. These are used,
for instance, to implement lazy lists so the expression 1..1_000_000 does
not have to allocate a million element array. But as far as I can tell the
term is never defined anywhere in the synopses. Is Iterator a role, and if
so what methods is it required to have? Do functions like map and grep,
which in Perl5 return lists, return Iterators in Perl6? Can an Iterator be
passed to a function (like map and grep again) that requires a list as an
input? Does an array or hash have only one Iterator or can it have several
independent ones?
I'm going to speculate on a few of these items.
Iterator most certainly will be a role, though that doesn't mean that
internal iterators will do this role. I expect they would, though. It
will probably have methods that do the following:
* next_item
* prev_item
* nth_item
* rewind
* has_next_item?
* has_prev_item?
I expect that lists will be convertable to iterators and vice-versa.
You can do this in P5 already:
sub create_iterator_from_list {
my @list = @_;
return sub {
return shift @list;
};
}
create_list_from_iterator {
my ($iterator) = @_;
my @list;
while ( my $item =$iterator-() ) {
push @list, $item;
}
return @list;
}
Of course, that's extremely inefficient. I expect that Perl6 will be a
little smarter, though it's not clear how much smarter it can be. For
one thing, Iterators will have to support two modes - one where the
list is frozen (the P5 version I posted above) so that changes to list
don't change the iterator and another where the iterator iterates into
the list as it stands, so that changes to the list are reflected in
the iterator immediately. The second mode has the possibility of being
unstable, but if you choose this mode (which wouldn't be the default),
then it's on your head.
As for multiple iterators, that's the point of having a separate
iterator object. Each iterator maintains its own state, allowing for
multiple traversals across the same set.
As for lazylists (1..Inf), they have to be implemented via iterators
(which is why I'm almost positive the two will be interchangeable).
And, if you pass (1..Inf) to map/grep/sort, it would HAVE to return an
iterator back, otherwise you'll hang at that instruction.
Of course, if you said while (my $n = 1..Inf) { }, it's on your head
to provide a last in there somewhere.
Rob
Re: What's the latest on Iterators?
On Fri, Nov 11, 2005 at 08:42:44AM -0500, Joe Gottman wrote:
: Do functions like map and grep, which in Perl5 return lists, return
: Iterators in Perl6?
A list may contain iterators. Lists don't eagerly flatten in Perl 6.
: Can an Iterator be passed to a function (like map and grep again)
: that requires a list as an input?
Certainly. You can pass as many iterators as you like. The range object
is your prototypical iterator, and you can say:
@results = grep {...} 0..9, 20..29, 40..49;
The list that grep is returning can also function as an iterator, so
@results isn't necessarily all there after the statement executes.
Though it's possible that = should put more COW requirements on the
right side than := would, so we at least maintain the appearance of
eager evaluation.
: Does an array or hash have only one Iterator or can it have several
: independent ones?
An array can have as many iterators as it likes, according to A6. There's
an underlying .specs objects that contains the specifications for how
to genererate missing values, and if the specs are smart enough, they
can be generated from either end.
Larry
