comment on

While playing with HOP's Stream module (chapter 6), I ran into a warning (Deep recursion...) that I thought I understood, but now I realize I don't, because my method to get rid of it worked a little bit too well. I'm hoping to get a better understanding of what this warning means.

The script below takes a positive integer n and prints out the n-th prime number. It uses a modified form of a stream-based implementation of the Sieve of Eratosthenes^1,2, by Dominus (although it is not mentioned in HOP). (A lot could be said about this cool way to implement the sieve, but I'll relegate all this to a couple of supersized footnotes, since I want to cut to the chase.)

The script requires the non-CPAN module Stream³, also by Dominus. In the script I did not import any function names, to make it easier to spot those functions that are defined elsewhere. I also avoided some syntactic sugar⁴ (such as node and promise) to make the code more readily understandable to those not familiar with Stream.pm.

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 ) );
      }
    ];
}
[download]

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
[download]

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)) });
[download]

with

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

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.

¹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.▲

² 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. ▲

³ 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');
[download]

▲

⁴ 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 ) );
                   }
                 );
[download]

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. ▲

the lowliest monk

In reply to Streams and "deep recursion" warning by tlm

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Perl Monk, Perl Meditation
	PerlMonks