|Perl: the Markov chain saw|
Streams and "deep recursion" warningby tlm (Prior)
|on Aug 30, 2005 at 19:54 UTC||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.
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:
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
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
4 In particular, the return statement in prime_filter was originally this:
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