Logic Flow Question

[JR]

I'm having trouble understanding the logic flow of recipe 4.3 in the
Perl Cookbook (the below script is only slightly different from the
recipe in the Cookbook), and am hoping someone can clarify it for me.

Here's where I'm confused:

In the below permute subroutine, I don't understand how the $i
variable can ever reach 1 and 2. It is initially set to 0 before the
for loop is entered. Immediately after the unshift line, the permute
subroutine is recursively and unconditionally called. When the else
loop is hit on any further calls, the $i variable is again set to 0,
yet the below output clearly indicates that the variable is, at some
point, being incremented. I don't see how this is possible, yet,
clearly it is. I notice that the variable is always 1 or 2
immediately after a given group of perms is printed, but this just
isn't enough of a clue to help me understand how this works. I must
be missing the obvious here. Can someone please point it out to me?

Thanks much.


use strict;
use warnings;

my @array = ('A'..'C');

permute([@array]);
sub permute {
my @items = @{ $_[0] };
my @perms = @{ $_[1] } if defined @{ $_[1] };
if (!@items) {
print "\@perms=@perms\n";
}
else {
my (@newitems, @newperms);
my $i = 0;
for my $i (0..$#items) {
print "\$i=$i\n";
@newitems = @items;
@newperms = @perms;
## Splice @newitems element and prepend it to @newperms
unshift(@newperms, splice(@newitems, $i, 1));
permute([@newitems], [@newperms]);
}
}
}

__END__
$i=0
$i=0
$i=0
@perms=C B A
$i=1
$i=0
@perms=B C A
$i=1
$i=0
$i=0
@perms=C A B
$i=1
$i=0
@perms=A C B
$i=2
$i=0
$i=0
@perms=B A C
$i=1
$i=0
@perms=A B C

 

[Ben Morrow]

I'm having trouble understanding the logic flow of recipe 4.3 in the
Perl Cookbook (the below script is only slightly different from the
recipe in the Cookbook), and am hoping someone can clarify it for me.

Here's where I'm confused:

In the below permute subroutine, I don't understand how the $i
variable can ever reach 1 and 2.

use strict;
use warnings;

my @array = ('A'..'C');

permute([@array]);
sub permute {
my @items = @{ $_[0] };
my @perms = @{ $_[1] } if defined @{ $_[1] };
if (!@items) {
print "\@perms=@perms\n";
}
else {
my (@newitems, @newperms);
my $i = 0;

Did you add this line?

for my $i (0..$#items) {

The 'my' here makes this create a new variable called $i, masking the
old one, which now counts up from 0 to $#items. The old $i from the
line above is never incremented, but neither is it ever printed.

If you want access to the loop variable outside the loop, remove the
'my'.

print "\$i=$i\n";
@newitems = @items;
@newperms = @perms;
## Splice @newitems element and prepend it to @newperms
unshift(@newperms, splice(@newitems, $i, 1));
permute([@newitems], [@newperms]);
}
}
}

__END__

Ben

 

[Brian McCauley]

(e-mail address removed) (JR) wrote:

Did you add this line?


The 'my' here makes this create a new variable called $i, masking the
old one, which now counts up from 0 to $#items. The old $i from the
line above is never incremented, but neither is it ever printed.

If you want access to the loop variable outside the loop, remove the
'my'.

No, don't do that. It will not make any difference. Perl will put it
straight back in. IMNSHO Perl should issue a warning when it does this
to encourge people to put an explict my when using a lexical variable
as a loop iterator variable.

The situation is subtly different for package variables.

my $i = 'outer $i';

my $i_p = sub { print \$i,$i,"\n" };
$i_p->();

for $i ( 'inner $i' ) { # Implied my
print \$i,$i,"\n";
$i_p->();
}
$i_p->();

our $j = 'outer $j';

my $j_p = sub { print \$j,$j,"\n" };
$j_p->();

for $j ( 'inner $j' ) {
print \$j,$j,"\n";
$j_p->();
}
$j_p->();

__END__
SCALAR(0x81059f4)outer $i
SCALAR(0x8105ab4)inner $i
SCALAR(0x81059f4)outer $i
SCALAR(0x81059f4)outer $i
SCALAR(0x8105b14)outer $j
SCALAR(0x8105ba4)inner $j
SCALAR(0x8105ba4)inner $j
SCALAR(0x8105b14)outer $j


--
\\ ( )
. _\\__[oo
.__/ \\ /\@
. l___\\
# ll l\\
###LL LL\\

 

[Ben Morrow]

No, don't do that. It will not make any difference. Perl will put it
straight back in.

Sorry, yes, my error. (No pun intended.)

Ben

 

[JR]

I'm having trouble understanding the logic flow of recipe 4.3 in the
Perl Cookbook (the below script is only slightly different from the
recipe in the Cookbook), and am hoping someone can clarify it for me.

Here's where I'm confused:

In the below permute subroutine, I don't understand how the $i
variable can ever reach 1 and 2.

use strict;
use warnings;

my @array = ('A'..'C');

permute([@array]);
sub permute {
my @items = @{ $_[0] };
my @perms = @{ $_[1] } if defined @{ $_[1] };
if (!@items) {
print "\@perms=@perms\n";
}
else {
my (@newitems, @newperms);
my $i = 0;

Did you add this line?

for my $i (0..$#items) {

The 'my' here makes this create a new variable called $i, masking the
old one, which now counts up from 0 to $#items. The old $i from the
line above is never incremented, but neither is it ever printed.

If you want access to the loop variable outside the loop, remove the
'my'.

print "\$i=$i\n";
@newitems = @items;
@newperms = @perms;
## Splice @newitems element and prepend it to @newperms
unshift(@newperms, splice(@newitems, $i, 1));
permute([@newitems], [@newperms]);
}
}
}

__END__

Ben

Thanks, Ben. I removed the my from the for loop, the way it is
removed in recipe 4.3. I didn't mean to have that in there-it was a
typo. The results, even with my removed in the for loop, are still
the same. Am I correct in guessing that the $i variable is not reset
to 0 every time the for loop is entered? When permute is called at
the bottom of every iteration of the for loop, is the $i variable
somehow not being reset to 0 the next time the for loop is entered, or
does program control somehow stay in the for loop for a few iterations
before being passed back to the permute subroutine?

Thanks.

use strict;
use warnings;

my @array = ('A'..'C');

permute([@array]);
sub permute {
my @items = @{ $_[0] };
my @perms = @{ $_[1] } if defined @{ $_[1] };
if (!@items) {
print "\@perms=@perms\n";
}
else {
my (@newitems, @newperms, $i);
for $i (0..$#items) {
print "\$i=$i\n";
@newitems = @items;
@newperms = @perms;
unshift(@newperms, splice(@newitems, $i, 1));
permute([@newitems], [@newperms]);
}
}
}

__END__
$i=0
$i=0
$i=0
@perms=C B A
$i=1
$i=0
@perms=B C A
$i=1
$i=0
$i=0
@perms=C A B
$i=1
$i=0
@perms=A C B
$i=2
$i=0
$i=0
@perms=B A C
$i=1
$i=0
@perms=A B C

 

[Ben Morrow]

I removed the my from the for loop, the way it is removed in recipe
4.3.

As Brian pointed out, I was mistaken here: Perl assumes a my even if
you don't put one in, hence

The results, even with my removed in the for loop, are still
the same.

Apologies again.

Am I correct in guessing that the $i variable is not reset
to 0 every time the for loop is entered? When permute is called at
the bottom of every iteration of the for loop, is the $i variable
somehow not being reset to 0 the next time the for loop is entered, or
does program control somehow stay in the for loop for a few iterations
before being passed back to the permute subroutine?

Err... I think you don't quite understand how subroutine calls work?
Calling permute() doesn't simply jump back to the top. It creates a
new lexical context: i.e., the variable $i in the new instance of
permute() is not the same as the variable $i in the old. So your print
statements are actually printing *different* '$i's all the time.

This may make it a little clearer:

use strict;
use warnings;

my @array = ('A'..'C');

permute([@array]);

Change this to
permute(1, [@array]);

sub permute {

Add here
my $level = shift;
print "entering permute() level $level\n";

my @items = @{ $_[0] };
my @perms = @{ $_[1] } if defined @{ $_[1] };
if (!@items) {
print "\@perms=@perms\n";
}
else {
my (@newitems, @newperms, $i);
for $i (0..$#items) {
print "\$i=$i\n";
@newitems = @items;
@newperms = @perms;
unshift(@newperms, splice(@newitems, $i, 1));
permute([@newitems], [@newperms]);

Change this to
permute($level + 1, [@newitems], [@newperms]);

}
}

Add here
print "leaving permute() level $level\n";

}

__END__

Each time you enter a new level, a new copy of $i is created. When you
leave that level, that new copy is destroyed, and you go back to using
the last-oldest copy.

Ben

 

[ctcgag]

Thanks, Ben. I removed the my from the for loop, the way it is
removed in recipe 4.3. I didn't mean to have that in there-it was a
typo. The results, even with my removed in the for loop, are still
the same. Am I correct in guessing that the $i variable is not reset
to 0 every time the for loop is entered?

A new variable is created each time the loop is entered. That new variable
can be referred to as $i from within the loop for which it was created (and
now where else). This $i is set to 0, but there are still other variables,
which are also called $i but only from within their respective loops, that
are not affected here. This is the main point of recursion, that each
recursive layer has access to only it's own lexical variables.

Xho

 

[JR]

A new variable is created each time the loop is entered. That new variable
can be referred to as $i from within the loop for which it was created (and
now where else). This $i is set to 0, but there are still other variables,
which are also called $i but only from within their respective loops, that
are not affected here. This is the main point of recursion, that each
recursive layer has access to only it's own lexical variables.

Xho

Thanks again to Ben, and thanks to Xho. You answered precisely the
part that I didn't understand about subroutine calls, particularly
calls within a recursive subroutine. These finer points were not
explained in any of the Perl books I have read (or perhaps I missed
them, or misunderstood them). Thanks for clearing them up for me.

 

[JR]

A new variable is created each time the loop is entered. That new variable
can be referred to as $i from within the loop for which it was created (and
now where else). This $i is set to 0, but there are still other variables,
which are also called $i but only from within their respective loops, that
are not affected here. This is the main point of recursion, that each
recursive layer has access to only it's own lexical variables.

Xho

Damn, I did miss something from my readings. Page 222 of the 3rd
edition of Programming Perl states that "Subroutines may be called
recursively because each call get its own argument array, even when
the routine calls itself." Thanks again to everyone for your
responses.

JR