in-place reverse?

[luser droog]

I was reading through some old code and found this function to
reverse an array.

reverse {
dup xcheck exch
[ exch dup length 1 sub -1 0 { 2 copy get 3 1 roll pop } for pop ]
exch {cvx} if }

And I wondered if it were possible to do it in-place, without creating
a new array. I'm primarily using this for my args-begin function
which does an {exch def} forall to assign names to local variables
and parameters. The reverse is used to pre-process the array
of names so it can be written left-to-right but operated top-down
against the stack.

I wrote it two ways but both are ugly. Is there a nicer way to do it?
Does it require the invention of a fancy new control structure for
a super "for" loop with 2 indices? I've almost done that with the
second try here. It looks almost ready to factor out a new kind
of loop.

{
%dup length 2 idiv -1 0 { % [A B C ..] idx(C)
0 1 2 index 2 idiv { % [A B C ..] idx(A)
1 index length 1 index sub % [A B C ..] idx(A) dst(A)
3 copy 3 copy pop get % [] i(C) d(C) [] i d A
4 copy pop % [] i d [] i d A [] i d
3 copy exch pop get % [] i d [] i d A [] i d .
exch pop put % [] i d [] i d A ([. B C ..])
3 -1 roll pop put % [] i d ([. B C .. A])
pop pop % []
} for
} @pop
{ % [A B C ..]
dup length 0 exch dup 2 div exch 1 sub % [ABC..] lo mid hi
{ % [ABC..] lo mid hi
3 copy gt exch % [] lo mid hi mid>hi lo
3 index gt or % [] lo mid hi mid>hi||lo>mid
{exit} if
4 copy exch pop % [] l m h [] l h
3 copy 6 copy % [] l m h [] l h [] l h [] l h [] l h
exch pop get % [] l m h [] l h [] l h [] l h [h]
4 1 roll pop get % [] l m h [] l h [] l h [h] [l]
5 1 roll exch pop put % [h] l m h [h] l h [l]
3 -1 roll pop put % [hl] l m h
3 2 roll 1 add 3 1 roll 1 sub
} loop
}

[luser droog]

Alright. Had to sleep on it. Two loops, sequentially. No new arrays
created. It uses a fancy loop I already wrote called "fortuple"

array n proc fortuple --
for each invocation of proc, the stack contains successive n-tuples
of elements from array using getinterval.

So, by doing `1 {} fortuple` on the array, I fill the stack with little one-
element subarrays of the original array. Then a little stack juggling
to grab a copy of the original array. And then a regular old forall
loop to put each value in its target box, consuming one of the
subarrays on each iteration.

{
[ 1 index 1 {} fortuple counttomark 1 add index { % [...] [ [0] [1] .. [n-1] 0
0 exch put
} forall pop
}

Aside: I considered "dup [ exch" instead of "[ 1 index" but that executes
two operators instead of just one. Probably an insignificant useless
microoptimization but that's why I did that.

Aside, aside: I haven't actually run and tested this. I'm 90% sure that
"counttomark 1 add index" correctly grabs the thing just below the mark,
but I reckon there's a 10% chance I'm wrong about that.

[luser droog]

On Friday, October 22, 2021 at 1:24:52 AM UTC-5, luser droog wrote:

> 3 copy 6 copy % [] l m h [] l h [] l h [] l h [] l h

This line by itself ought to have been a red flag. It felt kinda overly
clever when I wrote it. But I thought it was "the good kind" of clever.
Ach.

[luser droog]

On Friday, October 22, 2021 at 7:13:13 PM UTC-5, luser droog wrote:

> Aside, aside: I haven't actually run and tested this. I'm 90% sure that
> "counttomark 1 add index" correctly grabs the thing just below the mark,
> but I reckon there's a 10% chance I'm wrong about that.

Okay, I've done some further post-hoc rationalizing. So my confidence
is up to 95% or so. Here's how I'm thinking it.

`counttomark` gives you the length of the array you want to make to
contain the stuff on the stack. So `counttomark index` is just going to
yield the `mark`. Since `0 index` == `dup`.
Eg.
[ /a /b /c counttomark % yields a 3
So.
[ /a /b /c counttomark index % yields that ol' mark

So, adding one is right. Yay, I'm so smart. Thanks, duckies.

[luser droog]

On Friday, October 22, 2021 at 7:13:13 PM UTC-5, luser droog wrote:

I rewrote it again to avoid using my fancy loop, since the fancy loop is itself
defined using /reverse.

{
dup % [] []
0 1 2 index length 1 sub { % [] ... [] 0
2 copy 1 getinterval % [] ... [] 0 [0]
3 1 roll pop % [] [0] ... []
} for % [] [0] [1] .. [n-1] []
{ 0 exch put } forall
}

So now I don't need the `mark ... counttomark` stuff because I can simply
carry along the original array in the loop and keep it close.
Finally, it becomes easier to see that the first loop isn't necessary.
All we truly need to do is calculate the target index and carry it along
on the stack.

{
dup length 1 sub 1 index { % [] n-1 0
3 copy put pop
1 sub
} forall pop
}

And this one, I think I'm happy with.

[James]

On 22/10/2021 07:24, luser droog wrote:
> I was reading through some old code and found this function to
> reverse an array.

> And I wondered if it were possible to do it in-place, without creating
> a new array.

/reverse {
aload dup length 1 sub
0 exch 1 exch
{ exch dup 4 2 roll exch put } for
} def

[ 1 2 3 4 5 ]
dup
reverse
pstack

[luser droog]

Yes. You have to dump the values or copy them somewhere. That last
one I posted doesn't work. It would produce [1 2 3 2 1] for this example.

[luser droog]

On Sunday, October 24, 2021 at 5:04:49 AM UTC-5, James wrote:

I adopted this version (since most of mine were ridiculous or broken
or both) but with a few tweaks. Substituting "dup ... exch ... exch" with "index",
and rearranging the innards of the loop to use "copy ... pop (pop)" which I'm
starting to like as an idiom. It's the same number of operators in the loop
but I find the changing stack picture easier to visualize with this rewrite.

/reverse { aload 0 1 2 index length 1 sub { 3 2 roll 3 copy put pop pop } for } def

Maybe "3 -1 roll" would be more readable (?). Is it more of a "grabbing the 3rd thing"
or "rearranging the 3 things with the top 2 at the bottom"? I'm not sure.

[David Newall]

On 22/10/21 5:24 pm, luser droog wrote:
> I was reading through some old code and found this function to
> reverse an array.

> ...

> And I wondered if it were possible to do it in-place, without creating
> a new array.

My first idea was this:

/reverse {
dup aload

0 1 2 index length 1 sub {

1 index exch 4 -1 roll put
} for
pop
} bind def

It works, is fast, but uses a lot of stack if the array is large.

So I came up with this, which uses minimal stack and gives similar
performance (when bound):

/reverse {
dup xcheck exch
dup length 1 sub
0 1 3 index length 2 idiv 1 sub {
2 index exch
1 index 3 index get
2 index 4 index 1 index 4 index get put
put
1 sub

} for
pop
exch {cvx} if

} bind def

By the way, I liked the xcheck. Obviously that's something I borrowed.

[luser droog]

On Friday, January 21, 2022 at 4:11:00 AM UTC-6, David Newall wrote:
> On 22/10/21 5:24 pm, luser droog wrote:
> > I was reading through some old code and found this function to
> > reverse an array.
> > ...
> > And I wondered if it were possible to do it in-place, without creating
> > a new array.
> My first idea was this:
>
> /reverse {
> dup aload
> 0 1 2 index length 1 sub {
> 1 index exch 4 -1 roll put
> } for
> pop
> } bind def
>
> It works, is fast, but uses a lot of stack if the array is large.
>

That's pretty good. It took me a second to think through it. But I think you
can go further and remove the 'dup' and the 'pop' (it's the same array you're
popping, or I suppose you could 'exch pop' to get rid of the other one).

> So I came up with this, which uses minimal stack and gives similar
> performance (when bound):
>
> /reverse {
> dup xcheck exch
> dup length 1 sub
> 0 1 3 index length 2 idiv 1 sub {
> 2 index exch
> 1 index 3 index get
> 2 index 4 index 1 index 4 index get put
> put
> 1 sub
> } for
> pop
> exch {cvx} if
> } bind def
>
> By the way, I liked the xcheck. Obviously that's something I borrowed.

That's a nice balance. for gives you one index. keeping the other on the
stack is simple. And actually doing a swap avoids the erroneous path
I followed trying to do everything like map().

I start to wish there were a nicer syntax to do 'index' operations. When there's
too many I start to write stack comments to follow it. But over time it's started
to seem like that's a warning sign and there's usually a different way to
conceive the problem where all the stack business falls neatly into place.
Until then I guess there's something like:

<< /2nd{1 index} /3rd{2 index} /4th{3 index} /5th{4 index} /6th{5 index} >> begin

(or up to whatever number you like.)

[jdaw1]

%!PS

/StackReverse {-1 2 {1 roll} for} bind def

/ArrayReverse
{
    1 dict begin dup dup xcheck exch cvlit /arr exch def
    0 1 arr length 2 sub 2 idiv
    {
        dup arr exch 2 copy get 4 -1 roll
        arr length 1 sub exch sub arr exch 2 copy get
        4 1 roll 3 -1 roll put put
    } for
    {cvx} if
} bind def % /ArrayReverse




mark (A) (B) (C) (D) (E) (F) (G)
7 StackReverse
(\n\n+pstack) = pstack (-pstack\n\n) =

cleartomark


{ (1) (2) } ArrayReverse ==
() =
[] ArrayReverse ==
() =
[ (1) (2) (3) (4) (5) (6) (7) ] ArrayReverse ==
() =
[ (1) (2) (3) (4) (5) (6) (7) (8) ] ArrayReverse ==

(\n\n+pstack) = pstack (-pstack\n\n) =