55 views

Skip to first unread message

Oct 22, 2021, 2:24:52 AM10/22/21

to

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

}

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

}

Oct 22, 2021, 8:13:13 PM10/22/21

to

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.

Oct 22, 2021, 8:16:16 PM10/22/21

to

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.

Oct 22, 2021, 8:42:15 PM10/22/21

to

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
> 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.

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.

Oct 23, 2021, 7:54:54 PM10/23/21

to

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

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.

Oct 24, 2021, 6:04:49 AM10/24/21

to

On 22/10/2021 07:24, luser droog wrote:

> I was reading through some old code and found this function to

> reverse an array.

> 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 {
> a new array.

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

Oct 24, 2021, 8:59:33 PM10/24/21

to

one I posted doesn't work. It would produce [1 2 3 2 1] for this example.

Nov 8, 2021, 1:09:00 PM11/8/21

to

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

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.

Jan 21, 2022, 5:11:00 AM1/21/22

to

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.

> ...
> 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:
> a new array.

/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
pop

exch {cvx} if

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

Jan 22, 2022, 12:23:00 AM1/22/22

to

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
> 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.

>

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.

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

Aug 10, 2022, 4:11:08 PM8/10/22

to

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

/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) =

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu