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

In article <87wmr67jvw.fsf@doppelsaurus.mobileactivedefense.com>,
Rainer Weikusat <rweikusat@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

gazelle@shell.xmission.com (Kenny McCormack) writes:
> Rainer Weikusat <rweikusat@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.

Rainer Weikusat , dans le message
<87frxu0xoy.fsf@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.

On 2024-02-14, Rainer Weikusat <rweikusat@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: @Kazinator@mstdn.ca

Kaz Kylheku <433-929-6894@kylheku.com> writes:
> On 2024-02-14, Rainer Weikusat <rweikusat@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.

Rainer Weikusat <rweikusat@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.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Rainer Weikusat <rweikusat@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 <rweikusat@talktalk.net> writes:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>> Rainer Weikusat <rweikusat@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.

On Thu, 15 Feb 2024 11:33:01 +0000
Rainer Weikusat <rweikusat@talktalk.net> wrote:
> gazelle@shell.xmission.com (Kenny McCormack) writes:
> > Rainer Weikusat <rweikusat@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.

I see plenty of legitimate posts on comp.lang.perl.misc .In fact , I even see

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

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

Spiros Bousbouras <spibou@gmail.com> writes:
> On Thu, 15 Feb 2024 11:33:01 +0000
> Rainer Weikusat <rweikusat@talktalk.net> wrote:
>> gazelle@shell.xmission.com (Kenny McCormack) writes:
>> > Rainer Weikusat <rweikusat@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.
>
> I see plenty of legitimate posts on comp.lang.perl.misc .In fact , I even see
>
> From: Rainer Weikusat <rweikusat@talktalk.net>
> Newsgroups: comp.lang.perl.misc
> Subject: Re: printf with trailing dots ?
> Date: Thu, 23 Nov 2023 19:35:23 +0000
> Message-ID: <87v89sl0uc.fsf@doppelsaurus.mobileactivedefense.com>
> References: <slrnuls0ir.nep.hymie@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.

Rainer Weikusat <rweikusat@talktalk.net> writes:
>Spiros Bousbouras <spibou@gmail.com> writes:
>> On Thu, 15 Feb 2024 11:33:01 +0000
>> Rainer Weikusat <rweikusat@talktalk.net> wrote:
>>> gazelle@shell.xmission.com (Kenny McCormack) writes:
>>> > Rainer Weikusat <rweikusat@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.
>>
>> I see plenty of legitimate posts on comp.lang.perl.misc .In fact , I even see
>>
>> From: Rainer Weikusat <rweikusat@talktalk.net>
>> Newsgroups: comp.lang.perl.misc
>> Subject: Re: printf with trailing dots ?
>> Date: Thu, 23 Nov 2023 19:35:23 +0000
>> Message-ID: <87v89sl0uc.fsf@doppelsaurus.mobileactivedefense.com>
>> References: <slrnuls0ir.nep.hymie@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.

In article <1bqAN.85208$Sf59.82726@fx48.iad>,
Scott Lurndal <slp53@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.

On 2/18/24 11:24, Scott Lurndal wrote:
> Rainer Weikusat <rweikusat@talktalk.net> writes:
>> Spiros Bousbouras <spibou@gmail.com> writes:
....
>>> From: Rainer Weikusat <rweikusat@talktalk.net>
>>> Newsgroups: comp.lang.perl.misc
>>> Subject: Re: printf with trailing dots ?
>>> Date: Thu, 23 Nov 2023 19:35:23 +0000
>>> Message-ID: <87v89sl0uc.fsf@doppelsaurus.mobileactivedefense.com>
>>> References: <slrnuls0ir.nep.hymie@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.

On Sun, 18 Feb 2024 13:08:14 -0500
James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
> On 2/18/24 11:24, Scott Lurndal wrote:
> > Rainer Weikusat <rweikusat@talktalk.net> writes:
> >> Spiros Bousbouras <spibou@gmail.com> writes:
> ...
> >>> From: Rainer Weikusat <rweikusat@talktalk.net>
> >>> Newsgroups: comp.lang.perl.misc
> >>> Subject: Re: printf with trailing dots ?
> >>> Date: Thu, 23 Nov 2023 19:35:23 +0000
> >>> Message-ID: <87v89sl0uc.fsf@doppelsaurus.mobileactivedefense.com>
> >>> References: <slrnuls0ir.nep.hymie@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.

On 18/02/2024 18:08, James Kuyper wrote:
> On 2/18/24 11:24, Scott Lurndal wrote:
>> Rainer Weikusat <rweikusat@talktalk.net> writes:
>>> Spiros Bousbouras <spibou@gmail.com> writes:
> ...
>>>> From: Rainer Weikusat <rweikusat@talktalk.net>
>>>> Newsgroups: comp.lang.perl.misc
>>>> Subject: Re: printf with trailing dots ?
>>>> Date: Thu, 23 Nov 2023 19:35:23 +0000
>>>> Message-ID: <87v89sl0uc.fsf@doppelsaurus.mobileactivedefense.com>
>>>> References: <slrnuls0ir.nep.hymie@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.

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.

On 2/18/24 13:29, Spiros Bousbouras wrote:
> On Sun, 18 Feb 2024 13:08:14 -0500
> James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>> On 2/18/24 11:24, Scott Lurndal wrote:
>>> Rainer Weikusat <rweikusat@talktalk.net> writes:
>>>> Spiros Bousbouras <spibou@gmail.com> writes:
>> ...
>>>>> From: Rainer Weikusat <rweikusat@talktalk.net>
>>>>> Newsgroups: comp.lang.perl.misc
>>>>> Subject: Re: printf with trailing dots ?
>>>>> Date: Thu, 23 Nov 2023 19:35:23 +0000
>>>>> Message-ID: <87v89sl0uc.fsf@doppelsaurus.mobileactivedefense.com>
>>>>> References: <slrnuls0ir.nep.hymie@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.

On Sun, 18 Feb 2024 13:46:45 -0500
James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
> On 2/18/24 13:29, Spiros Bousbouras wrote:
> > On Sun, 18 Feb 2024 13:08:14 -0500
> > James Kuyper <jameskuyper@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.

On 2/18/24 15:21, Spiros Bousbouras wrote:
> On Sun, 18 Feb 2024 13:46:45 -0500
> James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
[snip]
>> 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.

Yeah, I think they forgot about GG until we complained to them.

>> 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.
I thought there were more GG blocked groups tho.
--
user <candycane> is generated from /dev/urandom