Click here to get back home

FAQ 4.47 How do I handle circular lists?
 Home | NewsGroups | Search | About
Login Password
Register Now!
 comp.lang.perl.misc    Post an article   get this group's latest topics as an RSS feed add this group's latest topics to your My MSN content add this group's latest topics to your My Yahoo content
Subject Author Date
FAQ 4.47 How do I handle circular lists? PerlFAQ Server 05-12-2008
Posted by sheinrich on May 14, 2008, 5:09 am
Please log in for more thread options
> sheinr...@my-deja.com wrote:
> >> --------------------------------------------------------------------
>
> >> 4.47: How do I handle circular lists?
>
> >> Circular lists could be handled in the traditional fashion with lin=
ked
> >> lists, or you could just do something like this with an array:
>
> >> unshift(@array, pop(@array)); # the last shall be first
> >> push(@array, shift(@array)); # and vice versa
>
> > As the modulo operator provides a simple way to address an array in a
> > circular fashion, which is maybe not obvious to the less experienced,
> > I think it should be mentioned here.
>
> > my @Colours =3D qw( FFFFFF 000000 FFFF00 );
>
> > my $asize =3D @Colours;
> > my $index =3D 0;
>
> > for (1..10) {
> > print $Colours[$index], "\n";
>
> > $index =3D ++$index % $asize;
>
> perldoc perlop
>
> [ SNIP ]
>
> Note that just as in C, Perl doesn=92t define when the variable is
> incremented or decremented. You just know it will be done sometime
> before or after the value is returned. This also means that
> modifying a variable twice in the same statement will lead to
> undefined behaviour. Avoid statements like:
>
> $i =3D $i ++;
> print ++ $i + $i ++;
>
> Perl will not guarantee what the result of the above statements is.
>
> So don't do that. Do this instead:
>
> $index =3D ( $index + 1 ) % $asize;
>
> John

"You just know it will be done sometime before or after the value is
returned."

I've been reading that as 'sometime before' in case of a preincrement,
'after' for a postincrement.

In which case my
$index =3D ++$index % $asize;

looks fairly safe.


IMHO the expression above can result in an error only, if the
increment is first computed and returned and is assigned to $index
only after the modulo operation or even after the explicit assignment.

You may be right in that this can really happen. But then it's a very
strange behaviour indeed.
I've been using the autoincrement out of habit and for performance
considerations but agree that your suggestion certainly leaves no room
for error and is more readable anyway.

Cheers, Steffen

Posted by Peter J. Holzer on May 17, 2008, 8:50 am
Please log in for more thread options
>> sheinr...@my-deja.com wrote:
>> > $index = ++$index % $asize;
>>
>> perldoc perlop
>>
>> [ SNIP ]
>>
>> Note that just as in C, Perl doesn’t define when the variable is
>> incremented or decremented. You just know it will be done sometime
>> before or after the value is returned. This also means that
>> modifying a variable twice in the same statement will lead to
>> undefined behaviour. Avoid statements like:
>>
>> $i = $i ++;
>> print ++ $i + $i ++;
>>
>> Perl will not guarantee what the result of the above statements is.
>>
>> So don't do that. Do this instead:
>>
>> $index = ( $index + 1 ) % $asize;
>>
>
> "You just know it will be done sometime before or after the value is
> returned."
>
> I've been reading that as 'sometime before' in case of a preincrement,
> 'after' for a postincrement.
>
> In which case my
> $index = ++$index % $asize;
>
> looks fairly safe.

It may not be.

> IMHO the expression above can result in an error only, if the
> increment is first computed and returned and is assigned to $index
> only after the modulo operation or even after the explicit assignment.

Right. The compiler could produce something like:

$tmp1 = $index + 1
$tmp2 = $tmp1 % $asize
$index = $tmp2
$index = $tmp1

> You may be right in that this can really happen. But then it's a very
> strange behaviour indeed.

Not that strange for compilers which produce code for real CPUs (which
often have very strange timing requirements). I wouldn't really expect
it from a simple bytecode-generating compiler like perl's.


The warning that the execution order is undefined comes from C. But in C
this is a consequence of the concept of "sequence points". The language
defines certain points (e.g., the end of each statement, each function
call, etc.) where each previous operation must be finished and no
subsequent operation must have begun. between two sequence points the
compiler can reorder operations at will. There are two rules about
modifying values:

1) You can modify an object[1] only once between two sequence points
2) If you modify an object, you can only read it to compute the new
value.

But Perl doesn't have the concept of sequence points, and there is no
general prohibition agains modifying the same object twice in a
statement, just against using the increment and decrement operators.
That does stand out as an odd exception. IMHO Perl should either define
an execution order (which could be a partial order) or adopt a more
generic concept like that of C.

>
> I've been using the autoincrement out of habit and for performance
> considerations

Surprisingly,

$index = ++$index % $asize;

is really about 40 % faster than

$index = ( $index + 1 ) % $asize;

I had not expected this. Apparently creating a constant IV is a
relatively expensive operation (well, it takes about 36 nanoseconds on
my PC, so "relatively expensive" is, er, relative).

        hp


Posted by sheinrich on May 18, 2008, 5:12 am
Please log in for more thread options
>
> >> [ SNIP ]
>
> It may not be.
>
> > IMHO the expression above can result in an error only, if the
> > increment is first computed and returned and is assigned to $index
> > only after the modulo operation or even after the explicit assignment.
>
> Right. The compiler could produce something like:
>
> $tmp1 = $index + 1
> $tmp2 = $tmp1 % $asize
> $index = $tmp2
> $index = $tmp1
>
> > You may be right in that this can really happen. But then it's a very
> > strange behaviour indeed.
>
> Not that strange for compilers which produce code for real CPUs (which
> often have very strange timing requirements). I wouldn't really expect
> it from a simple bytecode-generating compiler like perl's.
>
> The warning that the execution order is undefined comes from C. But in C
> this is a consequence of the concept of "sequence points". The language
> defines certain points (e.g., the end of each statement, each function
> call, etc.) where each previous operation must be finished and no
> subsequent operation must have begun. between two sequence points the
> compiler can reorder operations at will. There are two rules about
> modifying values:
>
> 1) You can modify an object[1] only once between two sequence points
> 2) If you modify an object, you can only read it to compute the new
> value.
>
> But Perl doesn't have the concept of sequence points, and there is no
> general prohibition agains modifying the same object twice in a
> statement, just against using the increment and decrement operators.
> That does stand out as an odd exception. IMHO Perl should either define
> an execution order (which could be a partial order) or adopt a more
> generic concept like that of C.
>

And the restriction seems particularly odd for a language that
otherwise allows constructs like
@array[$k, $l] = @array[$l, $k];

Reading from the above, it probably wouldn't help to introduce some
strategical brackets, or would it?
$index = (++$index) % $asize;

Thank you,
Steffen

Posted by Dr.Ruud on May 18, 2008, 7:21 am
Please log in for more thread options
sheinrich@my-deja.com schreef:

> the restriction seems particularly odd for a language that
> otherwise allows constructs like
> @array[$k, $l] = @array[$l, $k];
>
> Reading from the above, it probably wouldn't help to introduce some
> strategical brackets, or would it?
> $index = (++$index) % $asize;

What don't you understand about "Note that just as in C, Perl doesn't
define when the variable is incremented or decremented. You just know it
will be done sometime before or after the value is returned. This also
means that modifying a variable twice in the same statement will lead to
undefined behaviour."?

--
Affijn, Ruud

"Gewoon is een tijger."


Posted by sheinrich on May 18, 2008, 8:36 am
Please log in for more thread options
> sheinr...@my-deja.com schreef:
>
> > the restriction seems particularly odd for a language that
> > otherwise allows constructs like
> > @array[$k, $l] = @array[$l, $k];
>
> > Reading from the above, it probably wouldn't help to introduce some
> > strategical brackets, or would it?
> > $index = (++$index) % $asize;
>
> What don't you understand about "Note that just as in C, Perl doesn't
> define when the variable is incremented or decremented. You just know it
> will be done sometime before or after the value is returned. This also
> means that modifying a variable twice in the same statement will lead to
> undefined behaviour."?
>
> --
> Affijn, Ruud
>
> "Gewoon is een tijger."

You didn't read the thread, did you?

Above I wrote in answer to John:

> "You just know it will be done sometime before or after the value is
> returned."
>
> I've been reading that as 'sometime before' in case of a preincrement,
> 'after' for a postincrement.

From what the doc says it is quite understandable why the given
examples

$i = $i ++;
print ++ $i + $i ++;

should be avoided.

However, it is not so clear and at least can be subject of debate, if
the outcome of

$index = ++$index % $asize;

is also indeterminate.

"This also means that modifying a variable twice in the same statement
will lead to undefined behaviour."
This of course sounds prohibitive, easy enough. But does it hold true?

As I read it from Peter's contribution, some doubt about perl adopting
the intrinsic problems from the C legacy is quite reasonable.

Steffen

Similar ThreadsPosted
FAQ 4.47 How do I handle circular lists? February 28, 2005, 12:03 pm
FAQ 4.47 How do I handle circular lists? May 17, 2005, 5:03 pm
FAQ 4.47 How do I handle circular lists? August 2, 2005, 4:03 pm
FAQ 4.47 How do I handle circular lists? October 5, 2005, 10:03 pm
FAQ 4.47 How do I handle circular lists? January 11, 2006, 5:03 pm
FAQ 4.47 How do I handle circular lists? April 20, 2006, 3:03 am
FAQ 4.47 How do I handle circular lists? August 2, 2006, 9:03 pm
FAQ 4.47 How do I handle circular lists? October 14, 2006, 9:03 pm
FAQ 4.47 How do I handle circular lists? December 26, 2006, 9:03 pm
FAQ 4.47 How do I handle circular lists? February 24, 2007, 9:03 pm

Our other projects:

Art Dolls, Fairies and Mermaids - Sunnyfaces.net

Roy's Linux, Programming and Search Engines messages

1-Script XML SitemapXML Sitemap