`use strict;
use warnings;
use Stream;
my $increment = sub { $_[ 0 ] + 1 };
my $upfrom2 = Stream::iterate_function( $increment, 2 );
my $primes = prime_filter( $upfrom2 );
my $n = shift || 1;
print nth_term( $primes, $n ), "\n";
exit 0;
sub nth_term {
my ( $s, $n ) = @_;
$s = Stream::tail $s while --$n > 0;
return Stream::head $s;
}
# a closure factory
sub not_multiple_of {
my $d = shift;
return sub { $_[ 0 ] % $d };
}
sub prime_filter {
my $s = shift; # a stream
my $p = Stream::head $s; # a "simple scalar"
my $t = Stream::tail $s; # another stream
my $not_multiple_of_p = not_multiple_of( $p );
return
[
$p,
sub {
prime_filter( &Stream::filter( $not_multiple_of_p, $t ) );
}
];
}
`

When I first tried the program, if the input was any integer between 1 and 97 (inclusive), it ran without any problem, but for inputs greater than 97 it began to generate warnings:

`% perl sieve.pl 97
509
% perl sieve.pl 98
Deep recursion on subroutine "Stream::tail" at Stream.pm line 90.
Deep recursion on subroutine "Stream::tail" at Stream.pm line 90.
521
`

This was not too surprising, since, after all, to find the 98-th prime, the input stream has to run through 97 recursively nested filters. But, still, out of curiosity, I tweaked

`Stream::filter` to inline a call to

`Stream::tail`. I.e. I replaced

` node(head($s),
promise { filter($f, tail($s)) });
`

with

` node( head( $s ),
promise {
$s->[ 1 ] = $s->[ 1 ]->() if is_promise $s->[ 1 ];
filter( $f, $s->[ 1 ] )
}
);
`

No more warnings for 98 after this change, which I sort of expected since now the call to

`Stream::filter` does not produce a nested call to

`Stream::tail`.

What puzzles me is that, with this change, I get no warnings even with arguments as high as 2000, whose subroutine call stack surpasses by far the one for 98 earlier. (I confirmed this by determining the highest integer argument to `caller` that would produce an `undef` result, which I took to be a reasonable proxy for the depth of the subroutine call stack. I'm sure there's a more civilized method to do this, and I'd love to learn about it.)

So what's going on? How come the subroutine call stack can now grow so much more than before without producing a warning? I suspect the problem lies in that the method I'm using to measure the "deep recursion" condition is not at all a good indicator of whatever perl uses, but I can't think of anything better.

I look forward to your comments.

**Update:** Per ysth's suggestion, I ran the code under `-W`, but still no warnings.

^{1}A stream is basically a "potentially infinite" linked list. The illusion of infiniteness is achieved through lazy evaluation, which in this case is implemented by wrapping the tail of each stream in an anonymous sub, often referred to as a *promise*. The promise takes no arguments, and returns a stream (which in turn has its own "lazy tail" ("lazy butt"?), if the stream in question is infinite). The function `Stream::tail` returns the stream obtained by evaluating ("forcing") the promise. `Stream::tail` also replaces the original promise in the linked list with the evaluated result, ensuring that each promise is forced at most once. It's important to keep in mind that the tail of a stream should always be *another stream* (though it could possibly be the "empty stream", aka `undef`).

The function `prime_filter` removes items from its input stream as necessary to generate an output stream with the property that no element of it is a multiple of a previous element. Therefore, when given the stream corresponding to the integers greater than 2, in their usual order, (which is what `$upfrom2` is) `prime_filter` produces the stream of prime numbers. Similarly, one could obtain the stream of primes by giving to `prime_filter` as input the stream whose head is the number 2 and whose tail is the stream of all odd numbers greater than 1.▲

^{2}
Note that Dominus's original implementation of the sieve uses an earlier version of the `Stream`, which is object-oriented, in contrast to the procedural version he presents in HOP. The code presented here uses the newer procedural version exclusively. Also note that __this is not a particularly efficient way to iterate over the prime numbers__; the range of usefulness for this script is the first few hundred primes or so, which could easily be tabulated. My interest in this snippet is purely as an exercise.
▲

^{3}
I made some small changes to the original `Serial.pm`. Specifically, I

- added
`use strict` and `use warnings`;
- changed the bareword
`Exporter` to a string;
- edited the variables
`@EXPORT_OK` and `%EXPORT_TAGS` to the fully qualified names;
- commented out the first definition of
`Stream::tail`.

Here's the patch:

`--- Stream.pm.orig Tue May 3 16:41:37 2005
+++ Stream.pm Mon Aug 29 20:00:14 2005
@@ -11,13 +11,16 @@
## Chapter 6 section 2
+use strict;
+use warnings;
+
package Stream;
-use base Exporter;
-@EXPORT_OK = qw(node head tail drop upto upfrom show promise
+use base 'Exporter';
+@Stream::EXPORT_OK = qw(node head tail drop upto upfrom show promise
filter transform merge list_to_stream cutsort
iterate_function cut_loops);
-%EXPORT_TAGS = ('all' => \@EXPORT_OK);
+%Stream::EXPORT_TAGS = ('all' => \@Stream::EXPORT_OK);
sub node {
my ($h, $t) = @_;
@@ -29,13 +32,13 @@
$s->[0];
}
-sub tail {
- my ($s) = @_;
- if (is_promise($s->[1])) {
- return $s->[1]->();
- }
- $s->[1];
-}
+# sub tail {
+# my ($s) = @_;
+# if (is_promise($s->[1])) {
+# return $s->[1]->();
+# }
+# $s->[1];
+# }
sub is_promise {
UNIVERSAL::isa($_[0], 'CODE');
`

▲

^{4}
In particular, the return statement in `prime_filter` was originally this:

` return
Stream::node (
$p,
Stream::promise {
prime_filter( &Stream::filter( $not_multiple_of_p
+, $t ) );
}
);
`

but

`Stream::node` merely stuffs its arguments into an anonymous array and returns it, and

`Stream::promise` is nothing more than an identity function for coderefs.

▲