mention of "use sort" botched in perlfunc?

[Michael G Schwern]

From perlfunc

5.8 has a sort pragma for limited control of the sort. Its rather blunt
control of the underlying algorithm may not persist into future perls, but
the ability to characterize the input or output in implementation
independent ways quite probably will. See L</use>.

I presume that should be 'See "sort"' or to better clarify 'See the "sort"
man page'?

This came from patch 13313 from jpl. What was it supposed to be?

--

Michael G. Schwern <sch...@pobox.com> http://www.pobox.com/~schwern/
Perl Quality Assurance <per...@perl.org> Kwalitee Is Job One
Plus I remember being impressed with Ada because you could write an
infinite loop without a faked up condition. The idea being that in Ada
the typical infinite loop would be normally be terminated by detonation.
-- Larry Wall in <1999111922...@kiev.wall.org>

[John P. Linderman]

> >From perlfunc
>
> 5.8 has a sort pragma for limited control of the sort. Its rather blunt
> control of the underlying algorithm may not persist into future perls, but
> the ability to characterize the input or output in implementation
> independent ways quite probably will. See L</use>.
>
> I presume that should be 'See "sort"' or to better clarify 'See the "sort"
> man page'?
>
> This came from patch 13313 from jpl. What was it supposed to be?

On second viewing, this is probably ok as is. There *is* a discussion
of the sort pragma in the "use" section (thanks to Jarkko, who
both implemented and documented the pragma.) I suspect the See
was there before my patch. -- jpl

[John P. Linderman]

> >From perlfunc
>
> 5.8 has a sort pragma for limited control of the sort. Its rather blunt
> control of the underlying algorithm may not persist into future perls, but
> the ability to characterize the input or output in implementation
> independent ways quite probably will. See L</use>.
>
> I presume that should be 'See "sort"' or to better clarify 'See the "sort"
> man page'?
>
> This came from patch 13313 from jpl. What was it supposed to be?

I recall wanting to discourage _mergesort and _quicksort,
but I don't recall doing anything about the "See".
Since the pragma is discussed a few paragraphs later,
it seems to me there's no need to reference anything.
(The fact that the pragma doesn't have block scope,
like "use warnings" does, is likely to cause confusion,
but I don't know where to send people to explain that) -- jpl

=====================

--- perlfunc.pod.orig Fri Jul 19 06:10:34 2002
+++ perlfunc.pod Fri Jul 19 06:10:54 2002
@@ -4570,7 +4570,7 @@

limited control of the sort. Its rather blunt control of the
underlying algorithm may not persist into future perls, but the
ability to characterize the input or output in implementation

-independent ways quite probably will. See L</use>.
+independent ways quite probably will.

Examples:

[Michael G Schwern]

It all came in at the same time.
http://public.activestate.com/cgi-bin/perlbrowse?filename=&action=patch&patch=13313&.submit=&.cgifields=action

There's mention of sort in an example under perlfunc/use, but no discussion.
Seems a roundabout way to point people at the sort pragma.

--

Michael G. Schwern <sch...@pobox.com> http://www.pobox.com/~schwern/
Perl Quality Assurance <per...@perl.org> Kwalitee Is Job One

Not king yet

[John P. Linderman]

Schwern won't let me off the hook:

> On Fri, Jul 19, 2002 at 06:26:28AM -0400, John P. Linderman wrote:
> > > >From perlfunc
> > >
> > > 5.8 has a sort pragma for limited control of the sort. Its rather blunt
> > > control of the underlying algorithm may not persist into future perls, but
> > > the ability to characterize the input or output in implementation
> > > independent ways quite probably will. See L</use>.
> > >
> > > I presume that should be 'See "sort"' or to better clarify 'See the "sort"
> > > man page'?
> > >
> > > This came from patch 13313 from jpl. What was it supposed to be?
> >
> > On second viewing, this is probably ok as is. There *is* a discussion
> > of the sort pragma in the "use" section (thanks to Jarkko, who
> > both implemented and documented the pragma.) I suspect the See
> > was there before my patch. -- jpl
>
> It all came in at the same time.
> http://public.activestate.com/cgi-bin/perlbrowse?filename=&action=patch&patch=13313&.submit=&.cgifields=action
>
> There's mention of sort in an example under perlfunc/use, but no discussion.
> Seems a roundabout way to point people at the sort pragma.

Guilty, then. There are two issues here, one of which is the quality of
the documentation. To which I would quote a much-beloved, incredibly
hard-working former pumpking: "patches welcome".

The other issue is how the sort pragma controls the sort function,
and I'm afraid my answer is "not very well". This is *not* dissing
Jarkko, who implemented the pragma: it wouldn't have happened at all
if it had been left to me, because I wouldn't have known how to do it.
But the compile-time effect of the pragma(s) versus the runtime
operation of the sort means that

{ use sort "_quicksort"; # many repetitions of a few distinct values
@a = sort @b;
}
{ use sort "stable"; # input order matters
@c = sort @d;
}

quite probably won't Do What You Mean (the pragmas are a no-op,
since only the last one matters, and it doesn't change default
behavior). The saving grace is that I don't think the sort pragma
will get much use (apologies to the pun-prone), and still less
multiple-use, like the above, where confusion can arise.

In the best of all possible worlds (Perl 6?), I'd like to see the
attributes of the sort specified together with the sort, so there
isn't action at a distance (the distance also being partially
responsible for the documentation botch). Something along the lines of

@a = sort @b is suitable-for-many-repetitions;
$iterator = sort @d is stable reverse iterator;

(Maybe it's moving that way, I haven't read the Apocalypses, something
I'll try to correct soon). This puts the tweaking with the invocation,
and would confine the documentation to one place. -- jpl

[John P. Linderman]

I once again demonstrated my ignorance, thus:

> But the compile-time effect of the pragma(s) versus the runtime
> operation of the sort means that
>
> { use sort "_quicksort"; # many repetitions of a few distinct values
> @a = sort @b;
> }
> { use sort "stable"; # input order matters
> @c = sort @d;
> }
>
> quite probably won't Do What You Mean (the pragmas are a no-op,
> since only the last one matters, and it doesn't change default
> behavior).

This did neither what I meant, *nor* what I said. But, by accident,
it's an even better demonstration of the evils that can occur.
The second use doesn't reset the "_quicksort", it "merely" adds
"stable" to it. (sort::current() is "quicksort stable" for both).
This is probably the worst possible state of affairs.

A quicksort on an array with only 10 distinct values takes only
10 passes (and most of those on only a fraction of the data),
even if there are more than 2**10 elements, and it's immune to
quadratic behavior. It's one of the few good reasons to force
quicksort. But forcing "stable" effectively eliminates all
duplicated elements, adds an extra pass through the data
before and after the sort, increases the overhead of every comparison,
and re-exposes us to quadratic behavior.

A fine demonstration of my ignorance, and the dangers of the current
implementation. -- jpl

[Michael G Schwern]

Errr... I hadn't meant to dig into the sort pragma quite that far. All I
was really fishing for was something like this:

--- perlfunc.pod 2002/07/20 17:47:10 1.1
+++ perlfunc.pod 2002/07/20 17:47:50
@@ -4572,7 +4572,8 @@

limited control of the sort. Its rather blunt control of the
underlying algorithm may not persist into future perls, but the
ability to characterize the input or output in implementation

-independent ways quite probably will. See L</use>.
+independent ways quite probably will. See the L<sort> pragma man
+page.

Examples:

--

Michael G. Schwern <sch...@pobox.com> http://www.pobox.com/~schwern/
Perl Quality Assurance <per...@perl.org> Kwalitee Is Job One

There is a disurbing lack of PASTE ENEMA on the internet.

[John P. Linderman]

Schwern went fishing with this bait:

> Errr... I hadn't meant to dig into the sort pragma quite that far. All I
> was really fishing for was something like this:
>
> --- perlfunc.pod 2002/07/20 17:47:10 1.1
> +++ perlfunc.pod 2002/07/20 17:47:50
> @@ -4572,7 +4572,8 @@
> limited control of the sort. Its rather blunt control of the
> underlying algorithm may not persist into future perls, but the
> ability to characterize the input or output in implementation
> -independent ways quite probably will. See L</use>.
> +independent ways quite probably will. See the L<sort> pragma man
> +page.
>
> Examples:

Looks good to me, but I just work here, I don't have the keys to
documentation. I'm not sure the uninitiated will know where to
look for the "sort pragma man page", but almost anything they try
with perldoc is likely to get them there. -- jpl

[John P. Linderman]

Schwern kind of guilted me into trying to beef up the sort.pm
documentation to make the dangers and workarounds more explicit.
And then I realized that no workaround for turning "stable" on
was possible... once on, there was no mechanism for turning it off.
So I added an unimport method. But that seemed a bit clumsy when
I tried using it, so I also added a "defaults" subpragma,
to restore things to the initial state. That seems to be a bit
more natural for most cases.

The original sort.t still worked fine after the changes,
but I added three more tests to exercise the "defaults" subpragma,
and the "no sort" addition.

As Michael knows, I can get carried away on explanations,
so if the modified man page seems too long, please feel free
to prune it. -- jpl

[h...@crypt.org]

"John P. Linderman" <j...@research.att.com> wrote:
:Schwern kind of guilted me into trying to beef up the sort.pm

:documentation to make the dangers and workarounds more explicit.
:And then I realized that no workaround for turning "stable" on
:was possible... once on, there was no mechanism for turning it off.
:So I added an unimport method. But that seemed a bit clumsy when
:I tried using it, so I also added a "defaults" subpragma,
:to restore things to the initial state. That seems to be a bit
:more natural for most cases.
:
:The original sort.t still worked fine after the changes,
:but I added three more tests to exercise the "defaults" subpragma,
:and the "no sort" addition.

Thanks, applied as #17685.

I'd like to see the scoping fixed one day, to do what people expect.
But I don't think we have the mechanisms for that right now - we need
more than PL_hints for this sort of thing.

Hugo