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
}

On Friday, October 22, 2021 at 1:24:52 AM UTC-5, luser droog wrote:
> 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
> }

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.

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.

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.

On Friday, October 22, 2021 at 7:13:13 PM UTC-5, luser droog wrote:
> On Friday, October 22, 2021 at 1:24:52 AM UTC-5, luser droog wrote:
> > 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
> > }
> 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.

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.

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

On Sunday, October 24, 2021 at 5:04:49 AM UTC-5, James wrote:
> 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

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.

On Sunday, October 24, 2021 at 5:04:49 AM UTC-5, James wrote:
> 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

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.

%!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)