Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Streams and "deep recursion" warning

by tlm (Prior)
on Aug 30, 2005 at 19:54 UTC ( #487926=perlquestion: print w/ replies, xml ) Need Help??
tlm has asked for the wisdom of the Perl Monks concerning the following question:

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 Eratosthenes1,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 Stream3, 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 sugar4 (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 ) ); } ]; }

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.


1A 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

  1. added use strict and use warnings;
  2. changed the bareword Exporter to a string;
  3. edited the variables @EXPORT_OK and %EXPORT_TAGS to the fully qualified names;
  4. 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.

the lowliest monk

Comment on Streams and "deep recursion" warning
Select or Download Code
Re: Streams and "deep recursion" warning
by pg (Canon) on Aug 31, 2005 at 00:24 UTC

    Just a side note... this is quite slow.

    With the following code (you can see that it is raw and not tweaked for performance), it took 1 second to find the 2000th (17389):

    use Data::Dumper; use strict; use warnings; print time(), "\n"; my @primes; my $candidate = 2; while ($#primes < $ARGV[0] - 1) { my $found = 0; while (!$found) { for my $prime (@primes) { if (!($candidate % $prime)) { $found = 1; last; } } if (!$found) { push @primes, $candidate; } $candidate ++; } } print $primes[-1], "\n"; print time(), "\n";

    With the Stream one, it took 140 seconds.

Re: Streams and "deep recursion" warning
by ysth (Canon) on Aug 31, 2005 at 01:04 UTC
    Without having taken time to really look at your code, I'm guessing that the code that makes the magic 100th deep function call doesn't have warnings enabled.

      That's an intriguing possibility. Could that be the case if both files (the script and Stream.pm) ran under use warnings? (The only module Stream used is Exporter; in the unlikely event that this could have anything to do with missing warnings, I eliminated this dependency.)

      the lowliest monk

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://487926]
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2014-09-15 10:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (146 votes), past polls