classic loop to controlled iterator

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
I think this is a nice trick.
Lets say we have a loop that will not stop until it finish e.g.

my \$i=5;
for (1..\$i) {
print "\$_\n"
}
for (2*\$i..4*\$i) {
print "\$_\n"
}
}

it is possible to convert it to a contolable iterator like this

use strict;
use warnings;

my \$prog = wrapper(5);

print "first  result : ", \$prog->() ,"\n";
print "second result : ", \$prog->() ,"\n";
while ( \$_ = \$prog->() ) {
print "*\$_*\n";
}

sub wrapper {
my (\$i, \$last) = (\$_[0], 0);

sub {
++\$last;
my \$result;
for (\$last .. \$i)  { \$result ||= \$_ }
for (\$last .. 4*\$i) { \$result ||= \$_ }
\$result
}
}

Re: classic loop to controlled iterator

"George Mpouras"

Note that this set of loops performs 3*\$i iterations of the loop bodies.

This will perform ((3*\$i)^2)/2 iterations of the loop body.

In this specific case the difference might be negligible as the constant
number of print operations overshadows the other costs. But when
generalizing this method you need to take very care that the loop bodies
in the wrapper always has the form '\$result ||= expr' which turns into
almost a no-op in all iterations except the initial.

You method will also have hard to handle the case where the loop body
might result in a false value.

//Makholm

Re: classic loop to controlled iterator

There are general comments I can make: consistent indentation really
helps in understanding code, I prefer ";" at the end of each block,
the output for two alternatives should be identical so you can compare
the output of the two versions, I really prefer "return" for an
explicit return.

The biggest problem is that the proposal as written doesn't work.  The
original code outputs 1..5, 10..20, but the replacement outputs 1..20.
Even if it's a contrived example to illustrate a point, working code
should be posted.

I also agree with the comment about inefficiency.  It's repeating the
entire sequence to reach one value, "||" to get a value but continuing
past the first value.  I'm thinking you might not have been aware of
"return", and it would not work with a zero or null value.

Here's a working version:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#! /usr/bin/perl
use strict;
use warnings;

if (0) {
my \$i=5;
for (1..\$i) {
print "\$_\n"
}
for (2*\$i..4*\$i) {
print "\$_\n"
}
} else {
my \$prog = wrapper(5);

while ( \$_ = \$prog->() ) {
print "\$_\n";
}
}
exit 0;

sub wrapper {
my (\$i, \$last) = (\$_[0], 0);

return sub {
++\$last;
for (\$last .. \$i)  { return \$_; }
\$last = 2*\$i if \$last < 2*\$i;
for (\$last .. 4*\$i) { return \$_; }
return undef;
}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(After Perl 5.9.4, you could use a "state" declaration, but I've hit
old versions of perl often enough, on systems that I don't control,
that a solution that works on older perls is a good notion.)

In
for (\$last .. \$i)  { return \$_; }
I believe that "for \$i (a..b)" is optimized to "for (\$i = a; \$i < b; ++\$i)".
Because the loop body returns immediately, the "for" really functions
as an "if": this works the same:
return \$last if \$last <= \$i;
But using "for" makes it perhaps a little more readable, makes it look
more like the original version.

This is no longer O(n^2), but roughly as efficient as the original
version -- sub has no actual loops.  But it still goes thru a series
of implicit if statements on each call.  It's a trivial enough thing
in this case, but in general, it might be highly problematic.

One solution would be to generate the output stream on the first call
and parcel them out one at a time:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

sub wrapper {
my (\$i) = (\$_[0]);
my @results = (1..\$i, 2*\$i..4*\$i);

return sub {
return shift @results;
}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

It's certainly clear to understand.  But that sort of misses the point
of having a generator.  It has to generate all the results at the
start, but one purpose of a generator is that you can get a few of the
first results, not bother getting the rest, and only pay the cost of
getting the ones you got.  Also, if the process to get a result
consumes something or is less trivial than this (e.g., reading from a
terminal), it could be problematic or impossible to do this.  It also
consumes all the sorage to hold all the results at once, so there are
two failures if your generator is supposed to, say, return all the
positive integers.

In general, what you really want are "generators".  The notion is that
a computation can proceed for a time, but suspend and yield a result
to the caller.  When the caller calls back, the thread of execution
starts continuing after the point of the last yield.

From a quick search, looking at only the first few pages of 1292 hits
in CPAN for
generator
http://search.cpan.org/~mlehmann/Coro-6.23/ is the basis of what you
want.  It implements coroutines / continuations, which have the
stop-and-resume model but don't necessarily yield a result.
http://search.cpan.org/~rintaro/Attribute-Generator-0.02/lib/Attribute/Generator.pm
appears to use Coro to implement stop-and-resume plus yielding
results.  I've not used either, so I can't express an opinion about
how reliable, efficient, and usable they are.

--
Tim McDaniel, tmcd@panix.com

Re: classic loop to controlled iterator

tmcd@panix.com (Tim McDaniel) writes:

[...]

http://search.cpan.org/~rintaro/Attribute-Generator-0.02/lib/Attribute/Generator.pm

One of the really 'nice' parts of the Wikipedia page on generators is
that it states that (paraphrase) "A generator is a kind of coroutine
except that it isn't coroutine but a subroutine" (which only ever
returns to the caller). Any 'thing' which can be 'invoked' somehow and
then returns 'the next value from some set of values' utilizing
internal state information to keep track of what precisely 'the next
value' is supposed to be, is 'a generator'. The obvious idea how to
implement that would be 'some kind of class with a next_value
method'. Often, it will be more convenient to use a closure instead.