Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > perldocs (etc) on recursion in Perl? Don't understand _WCPS_ example

Reply
Thread Tools

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

 
 
usenet@DavidFilmer.com
Guest
Posts: n/a
 
      05-07-2006
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!

--
http://DavidFilmer.com

 
Reply With Quote
 
 
 
 
Paul Lalli
Guest
Posts: n/a
 
      05-07-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> 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

 
Reply With Quote
 
 
 
 
Anno Siegel
Guest
Posts: n/a
 
      05-07-2006
<(E-Mail Removed)> wrote in comp.lang.perl.misc:
> 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
--
If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.
 
Reply With Quote
 
Ilya Zakharevich
Guest
Posts: n/a
 
      05-07-2006
[A complimentary Cc of this posting was sent to
Anno Siegel
<(E-Mail Removed)-berlin.de>], who wrote in article <(E-Mail Removed)>:
> > 48 sub process_url($); #Needed because this is recursive
> > 49 sub process_url($)
> > 50 { #etc - code which examines and qualifies the URL


> 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
 
Reply With Quote
 
Uri Guttman
Guest
Posts: n/a
 
      05-07-2006
>>>>> "PL" == Paul Lalli <(E-Mail Removed)> writes:

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

--
Uri Guttman ------ (E-Mail Removed) -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
 
Reply With Quote
 
Paul Lalli
Guest
Posts: n/a
 
      05-07-2006
Uri Guttman wrote:
> >>>>> "PL" == Paul Lalli <(E-Mail Removed)> writes:

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

 
Reply With Quote
 
brian d foy
Guest
Posts: n/a
 
      05-08-2006
In article <(E-Mail Removed) .com>,
<(E-Mail Removed)> wrote:

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

*** Posted via a free Usenet account from http://www.teranews.com ***
 
Reply With Quote
 
Anno Siegel
Guest
Posts: n/a
 
      05-09-2006
brian d foy <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> In article <(E-Mail Removed) .com>,
> <(E-Mail Removed)> wrote:
>
> > 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.


That's wicked cool call stack for you.

Anno
--
If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.
 
Reply With Quote
 
David Combs
Guest
Posts: n/a
 
      06-02-2006
In article <(E-Mail Removed) .com>,
<(E-Mail Removed)> wrote:
>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


 
Reply With Quote
 
Ingo Menger
Guest
Posts: n/a
 
      06-02-2006

Anno Siegel wrote:
> <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> > 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.


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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Data::Dumper not indenting per perldocs usenet@DavidFilmer.com Perl Misc 1 01-30-2007 03:20 AM
I need to be amused on the perldocs that ship with Perl. grocery_stocker Perl Misc 5 11-06-2006 07:29 PM
Perldocs for Schwartzian transforms? jl_post@hotmail.com Perl Misc 33 02-26-2006 12:13 AM
search perldocs against each word in a string ioneabu@yahoo.com Perl Misc 0 02-16-2005 04:29 AM
best way to search perldocs wana Perl Misc 7 09-27-2004 11:55 PM



Advertisments