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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <[email protected]>,
Rainer Weikusat <[email protected]> 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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

[email protected] (Kenny McCormack) writes:

Rainer Weikusat <[email protected]> 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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Rainer Weikusat , dans le message <[email protected]>, 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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 2024-02-14, Rainer Weikusat <[email protected]> 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: @[email protected]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Kaz Kylheku <[email protected]> writes:

On 2024-02-14, Rainer Weikusat <[email protected]> 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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Rainer Weikusat <[email protected]> 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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Tim Rentsch <[email protected]> writes:

Rainer Weikusat <[email protected]> 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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Rainer Weikusat <[email protected]> writes:

Tim Rentsch <[email protected]> writes:

Rainer Weikusat <[email protected]> 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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Spiros Bousbouras <[email protected]> writes:

On Thu, 15 Feb 2024 11:33:01 +0000
Rainer Weikusat <[email protected]> wrote:

[email protected] (Kenny McCormack) writes:

Rainer Weikusat <[email protected]> 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 <[email protected]>
Newsgroups: comp.lang.perl.misc
Subject: Re: printf with trailing dots ?
Date: Thu, 23 Nov 2023 19:35:23 +0000
Message-ID: <[email protected]>
References: <[email protected]>

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Rainer Weikusat <[email protected]> writes:

Spiros Bousbouras <[email protected]> writes:

On Thu, 15 Feb 2024 11:33:01 +0000
Rainer Weikusat <[email protected]> wrote:

[email protected] (Kenny McCormack) writes:

Rainer Weikusat <[email protected]> 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 <[email protected]>
Newsgroups: comp.lang.perl.misc
Subject: Re: printf with trailing dots ?
Date: Thu, 23 Nov 2023 19:35:23 +0000
Message-ID: <[email protected]>
References: <[email protected]>

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 2/18/24 11:24, Scott Lurndal wrote:

Rainer Weikusat <[email protected]> writes:

Spiros Bousbouras <[email protected]> writes:

...

From: Rainer Weikusat <[email protected]>
Newsgroups: comp.lang.perl.misc
Subject: Re: printf with trailing dots ?
Date: Thu, 23 Nov 2023 19:35:23 +0000
Message-ID: <[email protected]>
References: <[email protected]>

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 2/18/24 13:29, Spiros Bousbouras wrote:

On Sun, 18 Feb 2024 13:08:14 -0500
James Kuyper <[email protected]> wrote:

On 2/18/24 11:24, Scott Lurndal wrote:

Rainer Weikusat <[email protected]> writes:

Spiros Bousbouras <[email protected]> writes:

...

From: Rainer Weikusat <[email protected]>
Newsgroups: comp.lang.perl.misc
Subject: Re: printf with trailing dots ?
Date: Thu, 23 Nov 2023 19:35:23 +0000
Message-ID: <[email protected]>
References: <[email protected]>

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 2/18/24 15:21, Spiros Bousbouras wrote:

On Sun, 18 Feb 2024 13:46:45 -0500
James Kuyper <[email protected]> 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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)