perldocs (etc) on recursion in Perl? Don't understand _WCPS_ example

U

usenet

Greetings. I was reading Steve Oualline's book, "Wicked Cool Perl
Scripts." In one of the scripts he illustrates a script to check
broken links on a website (page 22-25). Of course, this is a task which
is well suited to a recursive approach, and this approach interests me,
but I know little about how recursion is implemented in Perl (and the
perldocs have not proven helpful - but maybe I haven't looked in
the right place).

In lines 48-50, Mr. Oualline codes as follows:

48 sub process_url($); #Needed because this is recursive
49 sub process_url($)
50 { #etc - code which examines and qualifies the URL

Let's ignore the fact that he's using a subroutine prototype (Mr.
Conway would be appaled). What interests me is the comment on line 48,
which seems to be an empty subroutine declaration. Actually, I'm not
sure exactly WHAT this is, which is why I'm posting this question.

Unfortunately, this part of the script is not explained in the
commentary. What exactly is going on with this seemingly "empty"
declaration on line 48, and how/why is it necessary for the recursive
nature of the task?

I would appreciate a reference to some information which can help me
understand how Perl implements recursion, and what is happening in this
_WCPS_ example.

Thanks!
 
P

Paul Lalli

Greetings. I was reading Steve Oualline's book, "Wicked Cool Perl
Scripts." In one of the scripts he illustrates a script to check
broken links on a website (page 22-25). Of course, this is a task which
is well suited to a recursive approach, and this approach interests me,
but I know little about how recursion is implemented in Perl

Recursion is not implemented by a language, it's implemented by a
program. To my knowledge there is no difference using recursion in a
Perl program from using recursion in a program written in any other
language.
(and the
perldocs have not proven helpful - but maybe I haven't looked in
the right place).

In lines 48-50, Mr. Oualline codes as follows:

48 sub process_url($); #Needed because this is recursive
49 sub process_url($)
50 { #etc - code which examines and qualifies the URL

Let's ignore the fact that he's using a subroutine prototype (Mr.
Conway would be appaled). What interests me is the comment on line 48,
which seems to be an empty subroutine declaration. Actually, I'm not
sure exactly WHAT this is, which is why I'm posting this question.

This is a subroutine declaration. It's main use is to notify Perl that
a subroutine with this name and this prototype will be declared
eventually. This enables the programmer to call the subroutine before
being defined. There are only two circumstances in which this is
needed: 1) The subroutine involves a prototype; 2) You want to call
the subroutine without using parentheses around the arguments.

perldoc perlsub
for more information
Unfortunately, this part of the script is not explained in the
commentary. What exactly is going on with this seemingly "empty"
declaration on line 48, and how/why is it necessary for the recursive
nature of the task?

It's not. The author is mistaken. There is no need to use a
subroutine declaration just because that subroutine will be called
recursively. Indeed, with no code of any kind between that declaration
and definition, I'm 99% sure you could remove the declaration entirely
without affecting anything else in the program.

An example of a recursive subroutine, without a pointless function
declaration:

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

foo(4);

sub foo {
my $arg = shift;
if ($arg == 1) {
print "Last recursion, arg = $arg\n";
} else {
print "Recursing again, arg = $arg\n";
foo($arg - 1);
}
}
__END__
Recursing again, arg = 4
Recursing again, arg = 3
Recursing again, arg = 2
Last recursion, arg = 1

Note that if we were to use a prototype on the above subroutine, then
we would need to either 1) move the call to the subroutine below the
subroutine itself, or 2) use a subroutine declaration above the call.
This, however, is true of *any* prototyped subroutine, and has nothing
to do with recursion.

Paul Lalli
 
A

Anno Siegel

Greetings. I was reading Steve Oualline's book, "Wicked Cool Perl
Scripts." In one of the scripts he illustrates a script to check
broken links on a website (page 22-25). Of course, this is a task which
is well suited to a recursive approach, and this approach interests me,
but I know little about how recursion is implemented in Perl (and the
perldocs have not proven helpful - but maybe I haven't looked in
the right place).

There is nothing special about recursion in Perl. You can write recursive
Perl routines without ever bothering how it is implemented.
In lines 48-50, Mr. Oualline codes as follows:

48 sub process_url($); #Needed because this is recursive
49 sub process_url($)
50 { #etc - code which examines and qualifies the URL

Let's ignore the fact that he's using a subroutine prototype (Mr.
Conway would be appaled). What interests me is the comment on line 48,
which seems to be an empty subroutine declaration. Actually, I'm not
sure exactly WHAT this is, which is why I'm posting this question.

It is exactly that. See "declaration" in perlsub.

The forward declaration is *needed* here just because of the prototype,
which must be visible when the function is first called. It would also
be needed if the recursive call(s) were written without parentheses.
Apart from that, recursion as such doesn't necessitate a forward declaration.

Anno
 
I

Ilya Zakharevich

[A complimentary Cc of this posting was sent to
Anno Siegel
The forward declaration is *needed* here just because of the prototype,
which must be visible when the function is first called. It would also
be needed if the recursive call(s) were written without parentheses.

It makes sense to remember that the major reason for this brain damage
of Perl is that CORE:: namespace was introduced very late in Perl
history. Thus it was thought at time that it is beneficial if
subroutine declaration is "visible" only after the full text of
subroutine is parsed, as in

sub syswrite {
syswrite(...) or die "..."; # CORE function called here
}

So NOW we need to live with such a nuisance; this is somewhat similar
to `my' variables being visible only on the next statement after their
declaration; likewise, this precludes "natural" ways to define
"recursive structures":

my $foo = [1, 2, 3, \$foo]; # Probably not what the writer thought

Hope this helps,
Ilya
 
U

Uri Guttman

PL> Recursion is not implemented by a language, it's implemented by a
PL> program. To my knowledge there is no difference using recursion in a
PL> Perl program from using recursion in a program written in any other
PL> language.

that is slightly wrong. recursion is a language feature in that a
language must handle a stack for the recursive calls. some older langs
did not do this and you could only call a sub once and had to return
before calling it again. other langs had to declare a sub would be
recursive so they could compile in the stack stuff (regular calls were
different internally than recursive calls/subs). and with any language
you can always fake recursion with a loop and your own stack. in some
cases this is not a bad solution and it can be much faster than real
recursion.

PL> This is a subroutine declaration. It's main use is to notify Perl
PL> that a subroutine with this name and this prototype will be
PL> declared eventually. This enables the programmer to call the
PL> subroutine before being defined. There are only two circumstances
PL> in which this is needed: 1) The subroutine involves a prototype;
PL> 2) You want to call the subroutine without using parentheses
PL> around the arguments.

and in the cool hacks code since he was recursively calling his
prototyped sub, the compiler had to compile a declared prototype so it
could be refered to inside the sub. the sub's prototype couldn't be used
inside the sub for a declaration as it happens too late. but as the OP
noted, damian and others eschew prototypes so that makes this 'cool'
hack much less cool to me.

PL> It's not. The author is mistaken. There is no need to use a
PL> subroutine declaration just because that subroutine will be called
PL> recursively. Indeed, with no code of any kind between that declaration
PL> and definition, I'm 99% sure you could remove the declaration entirely
PL> without affecting anything else in the program.

it is just the prototype that forces the need for the predeclaration.

PL> Note that if we were to use a prototype on the above subroutine, then
PL> we would need to either 1) move the call to the subroutine below the
PL> subroutine itself, or 2) use a subroutine declaration above the call.
PL> This, however, is true of *any* prototyped subroutine, and has nothing
PL> to do with recursion.

well, you can define a prototyped sub and not need a separate prototype
declaration as long as all callers are later in the source and so the
compiler will have seen the prototype. it is the 'cool' code's use of
prototypes AND recursion that requires the predeclared prototype for the
sub's own use.

uri
 
P

Paul Lalli

Uri said:
PL> There are only two circumstancesin which [a subroutine
PL> pre-declaration] is needed: 1) The subroutine involves a prototype;
PL> 2) You want to call the subroutine without using parentheses
PL> around the arguments.

and in the cool hacks code since he was recursively calling his
prototyped sub, the compiler had to compile a declared prototype so it
could be refered to inside the sub. the sub's prototype couldn't be used
inside the sub for a declaration as it happens too late.

For some reason that demonstrates poor judgement on my part, I did not
try a version of the code without the declaration statement before
posting my response. I have just done so now, and see the standard
"main::foo() called too early to check prototype" warning. My
apologies for not doing this the first time around.
PL> It's not. The author is mistaken. There is no need to use a
PL> subroutine declaration just because that subroutine will be called
PL> recursively. Indeed, with no code of any kind between that declaration
PL> and definition, I'm 99% sure you could remove the declaration entirely
PL> without affecting anything else in the program.

it is just the prototype that forces the need for the predeclaration.

Yes. I meant that the author is mistaken in his comment, that the
declaration was required simply because of recursion. In his specific
example, the declaration was required because of recursion, the
prototype, and the desire to avoid the warning.

I was incorrect about my "without affecting anything else" statement.
Good thing I left that 1% of being unsure available... ;-)
well, you can define a prototyped sub and not need a separate prototype
declaration as long as all callers are later in the source and so the
compiler will have seen the prototype. it is the 'cool' code's use of
prototypes AND recursion that requires the predeclared prototype for the
sub's own use.

I understand that now. Thanks for the corrections and clarifications,
Uri.

Paul Lalli
 
B

brian d foy

Greetings. I was reading Steve Oualline's book, "Wicked Cool Perl
Scripts." In one of the scripts he illustrates a script to check
broken links on a website (page 22-25). Of course, this is a task which
is well suited to a recursive approach

An iterative solution isn't any more difficult, either, and has the
advantages of not generating a potentially huge call stack. :)

*** ***
 
A

Anno Siegel

brian d foy said:
An iterative solution isn't any more difficult, either, and has the
advantages of not generating a potentially huge call stack. :)

That's wicked cool call stack for you.

Anno
 
D

David Combs

Greetings. I was reading Steve Oualline's book, "Wicked Cool Perl
Scripts." ...

I'm thinking of buying that book -- what's your opinion
of it?

Thanks!,

David
 
I

Ingo Menger

Anno said:
There is nothing special about recursion in Perl.

Except that after 100 recursions or so you get the message
"Deep recursion in foo() at ..."
At least this was so in earlier versions of perl and one could not get
rid of it.
 
U

Uri Guttman

IM> Except that after 100 recursions or so you get the message
IM> "Deep recursion in foo() at ..."
IM> At least this was so in earlier versions of perl and one could not get
IM> rid of it.

it was easy to get rid of the deep recursion warning. one way is to do:

no warnings 'recursion' ; # check the actual warning name

in the scope of the top level recursive call.

or you could disable all warnings by dropping the 'recursion' arg or
clearing the warning variable $^W:

local( $^W ) ;

again, do that before the top level recursive call and in its scope.

the deep recursion warning is a minor annoyance that can save you in
some nasty cases. and working around it is easy so it will likely stay
around.

uri
 
I

Ingo Menger

Uri said:
IM> Except that after 100 recursions or so you get the message
IM> "Deep recursion in foo() at ..."
IM> At least this was so in earlier versions of perl and one could not get
IM> rid of it.

it was easy to get rid of the deep recursion warning. one way is to do:

no warnings 'recursion' ; # check the actual warning name

in the scope of the top level recursive call.

Maybe now, but I'm talking about a time, where there was no warnings.pm
yet.
or you could disable all warnings by dropping the 'recursion' arg or
clearing the warning variable $^W:

local( $^W ) ;

Hehe.
You call this "nothing special about recursion"?
the deep recursion warning is a minor annoyance that can save you in
some nasty cases

like, for example, you have to pay per CPU second or memory page
swapped :)
. and working around it is easy so it will likely stay
around.

IMHO, it is anti DWIM. When I say foo(), I mean foo(), even when I am
already in foo.
 
T

Ted Zlatanov

IMHO, it is anti DWIM. When I say foo(), I mean foo(), even when I
am already in foo.

The vast majority of deep recursions are done in error. I would
rather see this warning. Disabling it is simple enough.

DWIM doesn't mean "do what I say," you know...

Ted
 
I

Ingo Menger

Ted said:
The vast majority of deep recursions are done in error.

No, thats simply not true.
You could also state that the vast majority of while statements that
loop more than 100 times are done in error.
The following holds for while loops AND recursions:
- if the n+1st (n>=0) loop/recursion is in error then so is the nth
- if the nth loop/recursion is not an error, then so the next.
- either all loops/all recursions are in error OR they are all correct
It's that simple.
So why not warn at the first recursion?
 
P

Peter J. Holzer

Ingo said:
No, thats simply not true.
You could also state that the vast majority of while statements that
loop more than 100 times are done in error.

You could state that, but it wouldn't be true.

Loops are frequently executed many times. Even infinite loops are
not uncommon.

OTOH, deep recursion is rarely used in procedural languages. Recursion
is often used for hierarchical data structures or for heuristically
searching for a solution to a problem. The total number of calls
typically grows exponentially with recursion depth for these problems,
which limits recursion depth to small levels. Also each recursion level
takes space on the stack, and the stack is typically rather small for
languages compiled to machine code (a few MB seems to be typical for
Unixes). Languages where deep recursion is normal (e.g., functional
languages which don't have explicit loops) normally have a compiler
which detects tail recursion and converts the recursion into a loop.

The following holds for while loops AND recursions:
- if the n+1st (n>=0) loop/recursion is in error then so is the nth
- if the nth loop/recursion is not an error, then so the next.
- either all loops/all recursions are in error OR they are all correct
It's that simple.
So why not warn at the first recursion?

Because shallow recursion is frequently used. Warning about that whould
be extremely annoying. OTOH, I don't think I encountered the "deep
recursion" warning more than a handful of times in 10+ years of perl
programming, and it is easy to turn off. (On the gripping hand, I'm not
sure if this warning ever saved me from a programming error, so I guess
I wouldn't miss it).

hp
 
T

Ted Zlatanov

No, thats simply not true.

You are right. I assumed you would understand the context here is
Perl and didn't specify the language. In Perl, this is true. If you
doubt it, feel free to survey all CPAN modules and see how many
recursive methods exist, and how many of those can potentially go over
100 levels in normal usage. I've been writing and reading Perl for a
while, and I can assure you that deep recursion is rare in Perl (or
any other procedural language, once people move past the CS101
level).

As a matter of performance in Perl, I would avoid recursion. A
recursive solution is almost always slower than a procedural solution
to the same problem. Depending on the algorithm this may be hard to
do; sometimes a recursive solution ends up faster (especially with the
Memoize module). I recommend "Higher-Order Perl" for a good
discussion of recursion in Perl in some practical situations (chapters
5 and 6 may be of interest, though the whole book is excellent).
You could also state that the vast majority of while statements that
loop more than 100 times are done in error.

I wouldn't, though. Let's not extrapolate my opinion on loops from my
opinion on deep recursion.
The following holds for while loops AND recursions:
- if the n+1st (n>=0) loop/recursion is in error then so is the nth
- if the nth loop/recursion is not an error, then so the next.
- either all loops/all recursions are in error OR they are all correct
It's that simple.

I think you're trying to do proof by induction here, but you're just
not making sense. Proving all three of your postulates wrong is
trivial, so I won't waste anyone's time with it.
So why not warn at the first recursion?

The proper question is, why 100 levels and not 101 for the deep
recursion warning? The answer is, because a number has to be picked,
and 100 is larger than "annoying" but smaller than "unreasonable."

Ted
 
T

Ted Zlatanov

No, thats simply not true.

You are right. I assumed you would understand the context here is
Perl and didn't specify the language. In Perl, this is true. If you
doubt it, feel free to survey all CPAN modules and see how many
recursive methods exist, and how many of those can potentially go over
100 levels in normal usage. I've been writing and reading Perl for a
while, and I can assure you that deep recursion is rare in Perl (or
any other procedural language, once people move past the CS101
level).

As a matter of performance in Perl, I would avoid recursion. A
recursive solution is almost always slower than a procedural solution
to the same problem. Depending on the algorithm this may be hard to
do; sometimes a recursive solution ends up faster (especially with the
Memoize module). I recommend "Higher-Order Perl" for a good
discussion of recursion in Perl in some practical situations (chapters
5 and 6 may be of interest, though the whole book is excellent).
You could also state that the vast majority of while statements that
loop more than 100 times are done in error.

I wouldn't, though. Let's not extrapolate my opinion on loops from my
opinion on deep recursion.
The following holds for while loops AND recursions:
- if the n+1st (n>=0) loop/recursion is in error then so is the nth
- if the nth loop/recursion is not an error, then so the next.
- either all loops/all recursions are in error OR they are all correct
It's that simple.

I think you're trying to do proof by induction here, but you're just
not making sense. Proving all three of your postulates wrong is
trivial, so I won't waste anyone's time with it.
So why not warn at the first recursion?

The proper question is, why 100 levels and not 101 for the deep
recursion warning? The answer is, because a number has to be picked,
and 100 is larger than "annoying" but smaller than "unreasonable."

Ted
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top