Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

linked lists in Perl

75 views
Skip to first unread message

Rainer Weikusat

unread,
Feb 14, 2024, 5:37:12 PMFeb 14
to
Recently, I had to implement support for cancellable timers in
Perl. As maximum number of these was going to be small, I wanted to use
a sorted list as priority queue implementation. Originally, this used an
array to store the list. Unfortunately, a situation this needed to be
dealt with was that a timer supposed to fire before all others would
repeatedly be created and cancelled again with a high frequency (a HTTP
request timeout). When implemented naively, this caused the array to
grow by one element for each such timer and considering that the
complexity of the algorithm was already quadratic, this seemed like a
very undesirable property. I then implemented a bunch of algorithms for
compacting this array but these were all hideously complicated, negating
the original idea that doing something simple should be sufficient.

Then, I came up with the following idea: Anonymous arrays of size 2 make
perfect cons cells in Perl and can thus be used to implement LISP-style
linked lists. This led to a much simpler implementation of a priority
queue represented as sorted list which doesn't keep growing when
handling the situation created above.

Here's a bit of Perl code to illustrate the principle:

----
sub cons { [@_] }

sub car : lvalue
{
$_[0][0]
}

sub cdr : lvalue
{
$_[0][1]
}

sub printl
{
my ($what, $l) = @_;

print($what, "\n--\n");
while ($l) {
print(car($l), "\n");
$l = cdr($l);
}
print("\n");
}

sub do_revl
{
my $l = $_[0];
my ($first, $last);

for (cdr($l)) {
return ($l, $l) unless defined;
($first, $last) = do_revl($_);
}

$l = cdr($last) = cons(car($l));
return ($first, $l);
}

sub revl
{
(do_revl($_[0]))[0]
}

my $l = cons(1, cons(2, cons(3, cons(4))));

printl('forward', $l);
printl('reverse', revl($l));

Kenny McCormack

unread,
Feb 15, 2024, 5:52:05 AMFeb 15
to
In article <87wmr67...@doppelsaurus.mobileactivedefense.com>,
Rainer Weikusat <rwei...@talktalk.net> wrote:
>Recently, I had to implement support for cancellable timers in
>Perl. As maximum number of these was going to be small, I wanted to use
>a sorted list as priority queue implementation. Originally, this used an

Doesn't this belong in some "Perl" newsgroup (Of which there are many) ?

--
The randomly chosen signature file that would have appeared here is more than 4
lines long. As such, it violates one or more Usenet RFCs. In order to remain
in compliance with said RFCs, the actual sig can be found at the following URL:
http://user.xmission.com/~gazelle/Sigs/Mandela

Rainer Weikusat

unread,
Feb 15, 2024, 6:33:07 AMFeb 15
to
gaz...@shell.xmission.com (Kenny McCormack) writes:
> Rainer Weikusat <rwei...@talktalk.net> wrote:
>>Recently, I had to implement support for cancellable timers in
>>Perl. As maximum number of these was going to be small, I wanted to use
>>a sorted list as priority queue implementation. Originally, this used an
>
> Doesn't this belong in some "Perl" newsgroup (Of which there are many) ?

It's about programming on UNIX and the Perl groups I'm aware no longer
have any traffic except sex spam.

Nicolas George

unread,
Feb 15, 2024, 8:45:30 AMFeb 15
to
Rainer Weikusat , dans le message
<87frxu0...@doppelsaurus.mobileactivedefense.com>, a écrit :
> It's about programming on UNIX

Absolutely not, your message was about algorithm and data structure and had
nothing to do with system programming. Saying it is “on UNIX” is as relevant
as if you asked a question about GIMP because you happen to run it on your
Linux box.

Kaz Kylheku

unread,
Feb 15, 2024, 11:30:09 AMFeb 15
to
On 2024-02-14, Rainer Weikusat <rwei...@talktalk.net> wrote:
> sub do_revl
> {
> my $l = $_[0];
> my ($first, $last);
>
> for (cdr($l)) {
> return ($l, $l) unless defined;
> ($first, $last) = do_revl($_);
> }
>
> $l = cdr($last) = cons(car($l));
> return ($first, $l);
> }

A concise way to write reverse is to iterate, and push the items onto a
new list:

(let (out)
(dolist (item list out)
(push item out)))

where (push item out) is equivalent to (setf out (cons item out)),
except that out is evaluated only once.

An oft-seen idiom in Common Lisp programs is the use of the destructive
function nreverse rather than reverse. It's used when a function builds
up some output in reverse (like by pushing onto a stack) but it's needed
in the right order. The list isn't shared with any other part of the
program, since it is brand new, and so it is safe to destructively
reverse it. nreverse typically rearranges the conses into opposite
order. ANSI CL allows it work in any manner, including by keeping the
conses in the same order, but reshuffling the cars, etc.

If your cancellable timers need the reverse operation, it's possible
that a destructive one could be used in place.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazi...@mstdn.ca

Rainer Weikusat

unread,
Feb 15, 2024, 1:21:41 PMFeb 15
to
Kaz Kylheku <433-92...@kylheku.com> writes:
> On 2024-02-14, Rainer Weikusat <rwei...@talktalk.net> wrote:
>> sub do_revl
>> {
>> my $l = $_[0];
>> my ($first, $last);
>>
>> for (cdr($l)) {
>> return ($l, $l) unless defined;
>> ($first, $last) = do_revl($_);
>> }
>>
>> $l = cdr($last) = cons(car($l));
>> return ($first, $l);
>> }
>
> A concise way to write reverse is to iterate, and push the items onto a
> new list:
>
> (let (out)
> (dolist (item list out)
> (push item out)))
>
> where (push item out) is equivalent to (setf out (cons item out)),
> except that out is evaluated only once.

But that's absolutely no fun, ie, I wanted to do a recursive version,
because I originally had absolutely no idea how to do that, I
was just convinced that it must be possible.

[...]

> If your cancellable timers need the reverse operation, it's possible
> that a destructive one could be used in place.

That was a demonstration subroutine.

Tim Rentsch

unread,
Feb 16, 2024, 2:39:21 AMFeb 16
to
Rainer Weikusat <rwei...@talktalk.net> writes:

> Then, I came up with the following idea: Anonymous arrays of size 2
> make perfect cons cells in Perl and can thus be used to implement
> LISP-style linked lists. This led to a much simpler implementation
> of a priority queue represented as sorted list which doesn't keep
> growing when handling the situation created above.
>
> Here's a bit of Perl code to illustrate the principle:
>
> ----
> sub cons { [@_] }
>
> sub car : lvalue
> {
> $_[0][0]
> }
>
> sub cdr : lvalue
> {
> $_[0][1]
> }
>
> sub do_revl
> {
> my $l = $_[0];
> my ($first, $last);
>
> for (cdr($l)) {
> return ($l, $l) unless defined;
> ($first, $last) = do_revl($_);
> }
>
> $l = cdr($last) = cons(car($l));
> return ($first, $l);
> }
>
> sub revl
> {
> (do_revl($_[0]))[0]
> }
>
> [...]

Code to reverse a list can be a lot simpler:

sub rev
{
my ($r, $s) = @_;
($r) ? rev( cdr( $r ), cons( car( $r ), $s ) ) : $s;
}

Please excuse any poor choices in the perl code, today is the
first time I've ever looked at perl or written any code in it.

Rainer Weikusat

unread,
Feb 16, 2024, 8:17:47 AMFeb 16
to
Tim Rentsch <tr.1...@z991.linuxsc.com> writes:
> Rainer Weikusat <rwei...@talktalk.net> writes:
>> Then, I came up with the following idea: Anonymous arrays of size 2
>> make perfect cons cells in Perl and can thus be used to implement
>> LISP-style linked lists. This led to a much simpler implementation
>> of a priority queue represented as sorted list which doesn't keep
>> growing when handling the situation created above.
>>
>> Here's a bit of Perl code to illustrate the principle:

[...]

>> sub do_revl
>> {
>> my $l = $_[0];
>> my ($first, $last);
>>
>> for (cdr($l)) {
>> return ($l, $l) unless defined;
>> ($first, $last) = do_revl($_);
>> }
>>
>> $l = cdr($last) = cons(car($l));
>> return ($first, $l);
>> }
>>
>> sub revl
>> {
>> (do_revl($_[0]))[0]
>> }
>>
>> [...]
>
> Code to reverse a list can be a lot simpler:
>
> sub rev
> {
> my ($r, $s) = @_;
> ($r) ? rev( cdr( $r ), cons( car( $r ), $s ) ) : $s;
> }
>
> Please excuse any poor choices in the perl code, today is the
> first time I've ever looked at perl or written any code in it.

To keep this in line with the style of the example, it should be

sub do_revl
{
my ($l, $rl) = @_;

return $rl unless $l;
return do_revl(cdr($l), cons(car($l), $rl));
}

sub revl
{
do_revl($_[0])
}

but the idea to build the reversed list as second argument while moving
downward instead of from its first element while moving upward is
definitely neat. This also fixes a bug with my version which modifies
the last cons of the original list directly, something it wasn't
supposed to do.

Rainer Weikusat

unread,
Feb 16, 2024, 5:33:15 PMFeb 16
to
Rainer Weikusat <rwei...@talktalk.net> writes:
> Tim Rentsch <tr.1...@z991.linuxsc.com> writes:
>> Rainer Weikusat <rwei...@talktalk.net> writes:

[...]

>>> sub do_revl
>>> {
>>> my $l = $_[0];
>>> my ($first, $last);
>>>
>>> for (cdr($l)) {
>>> return ($l, $l) unless defined;
>>> ($first, $last) = do_revl($_);
>>> }
>>>
>>> $l = cdr($last) = cons(car($l));
>>> return ($first, $l);
>>> }
>>>
>>> sub revl
>>> {
>>> (do_revl($_[0]))[0]
>>> }
>>>
>>> [...]
>>
>> Code to reverse a list can be a lot simpler:

[...]

> To keep this in line with the style of the example, it should be
>
> sub do_revl
> {
> my ($l, $rl) = @_;
>
> return $rl unless $l;
> return do_revl(cdr($l), cons(car($l), $rl));
> }

This is obviously the - presumably well-known - standard solution. A
fixed version of the other could look like this:

sub do_revl
{
my $l = $_[0];
my ($first, $last);

for (cdr($l)) {
do { return ($_, $_) for cons(@$l) } unless defined;
($first, $last) = do_revl($_);
}

return ($first, cdr($last) = cons(car($l)));

}

The out for (...) isn't strictly necessary, that's basically syntactic
sugar (a so-called topicalizer) for avoiding to have to write cdr($l)
twice.

Spiros Bousbouras

unread,
Feb 17, 2024, 1:29:28 PMFeb 17
to
I see plenty of legitimate posts on comp.lang.perl.misc .In fact , I even see

From: Rainer Weikusat <rwei...@talktalk.net>
Newsgroups: comp.lang.perl.misc
Subject: Re: printf with trailing dots ?
Date: Thu, 23 Nov 2023 19:35:23 +0000
Message-ID: <87v89sl...@doppelsaurus.mobileactivedefense.com>
References: <slrnuls0ir...@nasalinux.net>

It would have been strange if the group had gone totally downhill in 3 months.

Rainer Weikusat

unread,
Feb 18, 2024, 7:46:38 AMFeb 18
to
It has. It's mostly flooded with sex and (illegal) drug ads.

Scott Lurndal

unread,
Feb 18, 2024, 11:24:34 AMFeb 18
to
That will diminish in 6 days.

Kenny McCormack

unread,
Feb 18, 2024, 11:46:41 AMFeb 18
to
In article <1bqAN.85208$Sf59....@fx48.iad>,
Scott Lurndal <sl...@pacbell.net> wrote:
...
>>> It would have been strange if the group had gone totally downhill in 3 months.
>>
>>It has. It's mostly flooded with sex and (illegal) drug ads.

Actually, that has been true of many/most Usenet groups for the past 6
months or so. In order to survive on Usenet, it has been necessary for each
and every one of us to develop some method of killing most of the posts in
most of the groups.

>That will diminish in 6 days.

I've heard that D Day is going to be 2/22 - that is only 4 days away, right?

--
https://www.rollingstone.com/politics/politics-news/the-10-dumbest-things-ever-said-about-global-warming-200530/

RS contributor Bill McKibben lambasted this analysis in his 2007 book, Deep Economy.
It's nice to have microelectronics; it's necessary to have lunch, wrote McKibben.

James Kuyper

unread,
Feb 18, 2024, 1:08:19 PMFeb 18
to
On 2/18/24 11:24, Scott Lurndal wrote:
> Rainer Weikusat <rwei...@talktalk.net> writes:
>> Spiros Bousbouras <spi...@gmail.com> writes:
...
>>> From: Rainer Weikusat <rwei...@talktalk.net>
>>> Newsgroups: comp.lang.perl.misc
>>> Subject: Re: printf with trailing dots ?
>>> Date: Thu, 23 Nov 2023 19:35:23 +0000
>>> Message-ID: <87v89sl...@doppelsaurus.mobileactivedefense.com>
>>> References: <slrnuls0ir...@nasalinux.net>
>>>
>>> It would have been strange if the group had gone totally downhill in
>>> 3 months.
>>
>> It has. It's mostly flooded with sex and (illegal) drug ads.
>
> That will diminish in 6 days.

Why? They already stopped all posting of new messages through GG. All
that's going to happen on 2024-02-22 is that they're going to stop
displaying any new messages, regardless of where they are posted. If you
use GG, all new posts will stop completely, regardless of sender or
newsgroup. If you don't use GG, if your newsserver has good filtering,
you won't see those messages, and if your newsserver has poor filteing,
you should continue seeing those messages.


Spiros Bousbouras

unread,
Feb 18, 2024, 1:29:33 PMFeb 18
to
On Sun, 18 Feb 2024 13:08:14 -0500
James Kuyper <james...@alumni.caltech.edu> wrote:
> On 2/18/24 11:24, Scott Lurndal wrote:
> > Rainer Weikusat <rwei...@talktalk.net> writes:
> >> Spiros Bousbouras <spi...@gmail.com> writes:
> ...
> >>> From: Rainer Weikusat <rwei...@talktalk.net>
> >>> Newsgroups: comp.lang.perl.misc
> >>> Subject: Re: printf with trailing dots ?
> >>> Date: Thu, 23 Nov 2023 19:35:23 +0000
> >>> Message-ID: <87v89sl...@doppelsaurus.mobileactivedefense.com>
> >>> References: <slrnuls0ir...@nasalinux.net>
> >>>
> >>> It would have been strange if the group had gone totally downhill in
> >>> 3 months.
> >>
> >> It has. It's mostly flooded with sex and (illegal) drug ads.
> >
> > That will diminish in 6 days.
>
> Why? They already stopped all posting of new messages through GG.

No they haven't. If you had bothered to actually visit comp.lang.perl.misc ,
you would have seen that googlegroups posted spam continues unabated ; same
for comp.lang.forth , comp.lang.lisp and I'm sure many others. This doesn't
excuse Rainer posting here instead of comp.lang.perl.misc where the most
recent legitimate post I see is

Newsgroups: comp.lang.perl.misc
Subject: Re: Permissions, USB drive
Date: Sat, 17 Feb 2024 09:16:11 -0500
Message-ID: <uqqf3b$ejlp$1...@dont-email.me>

As long as legitimate posters remain , it makes no sense (and it's actually
harmful) not to post on a group where the subject is on topic.

Richard Harnden

unread,
Feb 18, 2024, 1:36:45 PMFeb 18
to
They stopped new posts from some, but not all, groups.
They have promised to depeer themselves completely on the 22nd.

Which means all the spam will move to those servers that handle binaries
- simply because those admins either don't care, or won't notice because
then increase in bandwidth is basically zero for them.


James Kuyper

unread,
Feb 18, 2024, 1:46:50 PMFeb 18
to
On 2/18/24 13:29, Spiros Bousbouras wrote:
> On Sun, 18 Feb 2024 13:08:14 -0500
> James Kuyper <james...@alumni.caltech.edu> wrote:
>> On 2/18/24 11:24, Scott Lurndal wrote:
>>> Rainer Weikusat <rwei...@talktalk.net> writes:
>>>> Spiros Bousbouras <spi...@gmail.com> writes:
>> ...
>>>>> From: Rainer Weikusat <rwei...@talktalk.net>
>>>>> Newsgroups: comp.lang.perl.misc
>>>>> Subject: Re: printf with trailing dots ?
>>>>> Date: Thu, 23 Nov 2023 19:35:23 +0000
>>>>> Message-ID: <87v89sl...@doppelsaurus.mobileactivedefense.com>
>>>>> References: <slrnuls0ir...@nasalinux.net>
>>>>>
>>>>> It would have been strange if the group had gone totally downhill in
>>>>> 3 months.
>>>>
>>>> It has. It's mostly flooded with sex and (illegal) drug ads.
>>>
>>> That will diminish in 6 days.
>>
>> Why? They already stopped all posting of new messages through GG.
>
> No they haven't. If you had bothered to actually visit
> comp.lang.perl.misc ,
> you would have seen that googlegroups posted spam continues unabated ;
> same


I can see that the spam continues unabated, but GG won't let me see the
headers, so I can't tell where it's being posted from. I had thought
they'd found a new server to post from.

My apologies - I had thought that GG cut off posting of all new messages
a couple of months ago - they did turn off all of the newsgroups I
regularly frequent. However, I just checked, and it does let me start
the process of posting a message to comp.lang.perl.misc, something it no
longer permits me to do on most of the groups I subscribe to.

Spiros Bousbouras

unread,
Feb 18, 2024, 4:21:47 PMFeb 18
to
On Sun, 18 Feb 2024 13:46:45 -0500
James Kuyper <james...@alumni.caltech.edu> wrote:
> On 2/18/24 13:29, Spiros Bousbouras wrote:
> > On Sun, 18 Feb 2024 13:08:14 -0500
> > James Kuyper <james...@alumni.caltech.edu> wrote:
> >> Why? They already stopped all posting of new messages through GG.
> >
> > No they haven't. If you had bothered to actually visit
> > comp.lang.perl.misc ,
> > you would have seen that googlegroups posted spam continues unabated ;
> > same
>
> I can see that the spam continues unabated, but GG won't let me see the
> headers, so I can't tell where it's being posted from. I had thought
> they'd found a new server to post from.

If you want to check the spam situation , you can use a server like
news.cyber23.de which doesn't filter spam. With this and your own
filters off , you will be able to see the spam including the headers.

It is very unlikely that any other newsserver will be as negligent as
googlegroups so no , I don't expect that the spammers will find any
server anywhere near as convenient as googlegroups any time soon.

> My apologies - I had thought that GG cut off posting of all new messages
> a couple of months ago - they did turn off all of the newsgroups I
> regularly frequent. However, I just checked, and it does let me start
> the process of posting a message to comp.lang.perl.misc, something it no
> longer permits me to do on most of the groups I subscribe to.

From what I remember , googlegroups turned off posting on comp.lang.c ,
comp.lang.c++ , comp.lang.fortran , comp.arch .With all the other groups ,
it was still spammers paradise.
0 new messages