Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #2675 > unrolled thread

decoupled for-loop/iterator-variable construct

Back to article view | Back to comp.lang.postscript

Contents

  decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-06-23 21:04 -0700
    Re: decoupled for-loop/iterator-variable construct jdaw1 <jdawiseman@gmail.com> - 2016-09-11 16:49 -0700
      Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-11 20:58 -0700
        Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-13 18:52 -0700
    Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-14 22:58 -0700
      Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-14 23:01 -0700
        Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-14 23:02 -0700
      Re: decoupled for-loop/iterator-variable construct Carlos <angus@quovadis.com.ar> - 2016-09-17 15:04 +0200
        Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-18 14:10 -0700
          Re: decoupled for-loop/iterator-variable construct Carlos <angus@quovadis.com.ar> - 2016-09-19 15:03 +0200
            Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-19 10:56 -0700
              Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-19 11:35 -0700
              Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-09-19 11:42 -0700
                Re: decoupled for-loop/iterator-variable construct luser droog <luser.droog@gmail.com> - 2016-10-01 13:59 -0700

#2675 — decoupled for-loop/iterator-variable construct

/iter takes the same parameters as a for loop
and yields a self-modifying procedure which will yield
the successive index values and call `exit` after 
condition fails.


% start inc fin  iter  proc
/iter {
    [ 4 1 roll
    { % s i f
        2 index lt { pop pop exit } if % s i
        1 index 3 1 roll % s s i
        add              % s s'
        /SELF exch 0 exch put % s 
    }aload pop 
    ]   
    0 1 2 index length 1 sub { % [] i
        2 copy get /SELF eq { % [] i
            1 index 3 copy put % []' i
            pop
        } if
        pop %stack()=
    } for % []
    cvx % {}
}def

/i 0 1 9 iter def 
%i = i = i =
{ i == } loop

[toc] | [next] | [standalone]

#2802

So it’s like a Python iterator, except in PostScript. Cool. 

Hmm: for what could I use it?

[toc] | [prev] | [next] | [standalone]

#2803

On Sunday, September 11, 2016 at 6:49:03 PM UTC-5, jdaw1 wrote:
> So it’s like a Python iterator, except in PostScript. Cool. 
> 
> Hmm: for what could I use it?

I was thinking it might be useful in situations where you've
already written some other kind of loop, ie. loop, repeat, 
forall, but then discover that you do in fact need an 
index value. Using /iter can provide that index value.

Particularly with forall, I seem to find I need to 
`dup load 1 add store` or `exch 1 add exch` a lot.

I haven't actually used it for anything yet. But I'll share
if ever I do!

[toc] | [prev] | [next] | [standalone]

#2808

On Sunday, September 11, 2016 at 10:58:26 PM UTC-5, luser droog wrote:
> On Sunday, September 11, 2016 at 6:49:03 PM UTC-5, jdaw1 wrote:
> > So it’s like a Python iterator, except in PostScript. Cool. 
> > 
> > Hmm: for what could I use it?
> 
> I was thinking it might be useful in situations where you've
> already written some other kind of loop, ie. loop, repeat, 
> forall, but then discover that you do in fact need an 
> index value. Using /iter can provide that index value.
> 
> Particularly with forall, I seem to find I need to 
> `dup load 1 add store` or `exch 1 add exch` a lot.
> 
> I haven't actually used it for anything yet. But I'll share
> if ever I do!

Another possibility is if you want something like a for
loop but you want the index value somewhere in the 
middle. Using iter could save you a few rolls.


0 1 9 { 
    n 1 roll
    ...
    n -1 roll
    ...use index ...
} for

=>
/i 0 1 9 iter def
{
   ...
   //i exec
   ...use index ...
} loop

[toc] | [prev] | [next] | [standalone]

#2812

On Friday, June 24, 2016 at 7:25:21 PM UTC-5, luser droog wrote:
> /iter takes the same parameters as a for loop
> and yields a self-modifying procedure which will yield
> the successive index values and call `exit` after 
> condition fails.

Improved version works with negative increments:

% start inc fin  iter  proc
/iter {
    [ 4 1 roll
    { % s i f
        2 index 2 index 0 lt {gt}{lt}ifelse { pop pop exit } if % s i
        1 index 3 1 roll % s s i
        add              % s s'
        /SELF exch 0 exch put % s 
    }aload pop 
    ]   
    0 1 2 index length 1 sub { % [] i
        2 copy get /SELF eq { % [] i
            1 index 3 copy put % []' i []'
            pop % []' i
        } if % [] i
        pop % []
    } for % []
    cvx % {}
}def

/doit { { i == } loop } def 
/i 0 1 9 iter def doit
()=
/i 9 -1 0 iter def doit

[toc] | [prev] | [next] | [standalone]

#2813

On Thursday, September 15, 2016 at 12:58:46 AM UTC-5, luser droog wrote:
> On Friday, June 24, 2016 at 7:25:21 PM UTC-5, luser droog wrote:
> > /iter takes the same parameters as a for loop
> > and yields a self-modifying procedure which will yield
> > the successive index values and call `exit` after 
> > condition fails.
> 
> Improved version works with negative increments:
> 
> % start inc fin  iter  proc
> /iter {
>     [ 4 1 roll
>     { % s i f
>         2 index 2 index 0 lt {gt}{lt}ifelse { pop pop exit } if % s i

Dammit! Remove that extra `lt`. The first one.


>         1 index 3 1 roll % s s i
>         add              % s s'
>         /SELF exch 0 exch put % s 
>     }aload pop 
>     ]   
>     0 1 2 index length 1 sub { % [] i
>         2 copy get /SELF eq { % [] i
>             1 index 3 copy put % []' i []'
>             pop % []' i
>         } if % [] i
>         pop % []
>     } for % []
>     cvx % {}
> }def
> 
> /doit { { i == } loop } def 
> /i 0 1 9 iter def doit
> ()=
> /i 9 -1 0 iter def doit

[toc] | [prev] | [next] | [standalone]

#2814

On Thursday, September 15, 2016 at 1:01:02 AM UTC-5, luser droog wrote:
> On Thursday, September 15, 2016 at 12:58:46 AM UTC-5, luser droog wrote:
> > On Friday, June 24, 2016 at 7:25:21 PM UTC-5, luser droog wrote:
> > > /iter takes the same parameters as a for loop
> > > and yields a self-modifying procedure which will yield
> > > the successive index values and call `exit` after 
> > > condition fails.
> > 
> > Improved version works with negative increments:
> > 
> > % start inc fin  iter  proc
> > /iter {
> >     [ 4 1 roll
> >     { % s i f
> >         2 index 2 index 0 lt {gt}{lt}ifelse { pop pop exit } if % s i
> 
> Dammit! Remove that extra `lt`. The first one.
> 

Wait, never mind. I skipped it while retyping, and then compared this to that
without thinking. The first `lt` should remain stet.

> >         1 index 3 1 roll % s s i
> >         add              % s s'
> >         /SELF exch 0 exch put % s 
> >     }aload pop 
> >     ]   
> >     0 1 2 index length 1 sub { % [] i
> >         2 copy get /SELF eq { % [] i
> >             1 index 3 copy put % []' i []'
> >             pop % []' i
> >         } if % [] i
> >         pop % []
> >     } for % []
> >     cvx % {}
> > }def
> > 
> > /doit { { i == } loop } def 
> > /i 0 1 9 iter def doit
> > ()=
> > /i 9 -1 0 iter def doit

[toc] | [prev] | [next] | [standalone]

#2817

[luser droog <luser.droog@gmail.com>, 2016-09-14 22:58]
> external iterator

That's a great idea. I started to play with it, and I found it makes
a lot of things easier. I generalized it to a makeiterator function:

% obj1...objn n procnext procnext? -> userprocnext userprocnext?

You pass to it:
 - some objects you need to keep track of the iteration
 - n, the number of objects
 - a proc, which gets those objects and returns the next iteration
   item(s) and a new set of objects with the updated iteration status
 - another proc, which receives the objects and returns whether there
   are more items

and it returns two procs that don't take any arguments:
 - one that returns the next iteration item(s)
 - and one that returns true or false, whether there is a next iteration
   item

For example, a function to create "for" iterators like yours would be
constructed this way:

% start inc end -> next next?
/foriter {
    3
    % i inc end -> i  i+1 inc end
    { 2 index 2 index add 3 1 roll }
    % i inc end -> t|f
    { exch 0 lt { gt } { lt } ifelse }
    makeiterator
} def

  GS> 1 3 6 foriter
  GS<2> /next? exch def   /next exch def
  GS>next =
  1
  GS>next? = 
  true
  GS>next =
  4
  GS>next?
  false

I struggle writing functions that take procs and execute them inside
loops without stack or dictionary interference. With external iterators
that problem doesn't exist anymore! You just have to yield the next
value, and let "{ } loop" take care of the looping.

With a little syntactic sugar (the function "done") to hide the
details they almost look like control structures:

  GS>(External iterators are great) 9 eachslice { == } done
  (External )
  (iterators)
  ( are grea)

I think this idea can be extended to filters and mappers. I'll get into
it when I get tired of writing all kind of iterators :)

Here is the code of makeiterator and done, and a couple of iterators:

% obj1...objn n nextproc next?proc -> unextproc unext?proc
/makeiterator {
    4 dict begin
    /next?proc exch def  /nextproc exch def
    array astore /arr exch def
    /unext? [
        /arr load /aload cvx /pop cvx
        /next?proc load /exec cvx
    ] cvx def
    [ /unext? load /exec cvx /not cvx { exit } /if cvx
      /arr load /aload cvx /pop cvx /nextproc load /exec cvx
      /arr load /astore cvx /pop cvx ] cvx
    /unext? load
    end
} def

% next next? proc -> -
/done {
    exch pop
    % { next proc } loop
    [ 3 1 roll  /exec cvx exch 1 index ] cvx
    loop
} def

% start inc end -> next next?
/foriter {
    3
    % i inc end -> i  i+1 inc end
    { 2 index 2 index add 3 1 roll }
    % i inc end -> t|f
    { exch 0 lt { gt } { lt } ifelse }
    makeiterator
} def

% arr -> n n?
/eachwithindex {
    0 2
    % arr i -> arr[i] i  arr i+1
    { 2 copy get  1 index  4 2 roll 1 add }
    % arr i -> t|f
    { exch length lt }
    makeiterator
} def

% arrayn ... array1 n -> nextproc next?proc
/eachinparallel {
    % get minimum length
    1 dict begin
    /n exch def
    dup length  1 1 n { index length 2 copy gt { exch } if pop } for
    0 n  % an...a1 len idx n
    n 3 add
    end
    % an...a1 len i n -> an[i]...a1[i]  an...a1 len i+1 n
    { 2 dict begin
      /n exch def  /i exch def
      n -1 1 { index i get n 2 add 1 roll } for
      i 1 add  n
      end
    }
    % an...a1 len i n -> t|f
    { 3 1 roll gt
      exch { exch pop } repeat
    }
    makeiterator
} def

% arr slicesize -> next next?
/eachslice {
    0 3
    % arr n i -> arr[i..i+n]  arr n i+1
    { 3 copy  exch getinterval  4 1 roll
      1 index add }
    % arr n i -> t|f
    { add  exch length le }
    makeiterator
} def


-- 

[toc] | [prev] | [next] | [standalone]

#2818

On Saturday, September 17, 2016 at 8:04:36 AM UTC-5, Carlos wrote:
> [luser droog <luser.droog@gmail.com>, 2016-09-14 22:58]
> > external iterator
> 
> That's a great idea. I started to play with it, and I found it makes
> a lot of things easier. I generalized it to a makeiterator function:
> 

That's awesome! After two reads, I still only understand half of what
you're doing. It's so far beyond what I was thinking.

Have you seen my loop that lets the user-proc `exit`?
http://stackoverflow.com/documentation/postscript/6199/error-handling/21486/re-throwing-errors

[toc] | [prev] | [next] | [standalone]

#2819

On 18/09/2016 23:10, luser droog wrote:
> On Saturday, September 17, 2016 at 8:04:36 AM UTC-5, Carlos wrote:
>> [luser droog <luser.droog@gmail.com>, 2016-09-14 22:58]
>>> external iterator
>>
>> That's a great idea. I started to play with it, and I found it makes
>> a lot of things easier. I generalized it to a makeiterator function:
>>
>
> That's awesome! After two reads, I still only understand half of what
> you're doing. It's so far beyond what I was thinking.

It's not explained very well. I'll try to explain it below.

> Have you seen my loop that lets the user-proc `exit`?
> http://stackoverflow.com/documentation/postscript/6199/error-handling/21486/re-throwing-errors

That's what I was talking about. You need to do contortions to get
stack and dictionaries out of the way, and to ensure cleanup code is
ran, so the user's proc can run "transparently", ie, as if it ran in
the context of the calling place. But with an external iterator you
don't need to do any of this, because the user's proc actually does
run in the context of the calling place.

A function that runs a proc on each element of a sequence tries to
look like this:

   { PUT-NEXT-ITEM-IN-STACK  USER'S-PROC } loop

but it needs a lot of auxiliary code because we are running
USER'S-PROC inside our own function and it needs to be invisible to
it.

But with an external iterator, what the user gets is just the function
PUT-NEXT-ITEM-IN-STACK, and it's the user themself who later puts it
inside a loop (if they want to):

    { PUT-NEXT-ITEM-IN-STACK  ...my-code... } loop

So we don't have to care about the user's proc or the loop at all. (We
can help them with a little syntactic sugar. That's what the function
`done` does: it takes three procs, discards the second one and
arranges the other two in this way:

     { PROC-1  PROC-3 } loop

)

Here is an example of a simple ascending `for` iterator. This is the
signature:

% start inc end -> next hasnext?

It gets the usual iteration arguments and returns two procs: one to
put next item in stack, and another to check whether there is a next
item (otherwise the iteration has finished).

Here is the code:

% start inc end  ->  next hasnext?
/makeforiterator {
     3 array astore     % store (start inc end) in an array.
                        % we will use the first position to hold
                        % the current value (i).
     /ARRAY exch def    % store the array here, so we can use it
                        % later.
     % now let's create the "hasnext?" proc. It will return true
     % if i < end.
     /hasnext? {
         ARRAY aload pop  % put the contents of the array in the stack.
                          % stack: i inc end
         exch pop         % discard inc. stack: i end
         lt               % return i < end
     } def
     % now the "next" proc. it will put i in the stack, and update
     % ARRAY with i's new value
     /next {
         % first, let's check if the iteration didn't finish yet
         hasnext? not { exit } if   % if it did, exit.
         ARRAY aload pop  % put the contents of the array in the stack.
                          % stack: i inc end
         2 index 2 index  % stack: i inc end i inc
         add              % stack: i inc end i+inc
         3 1 roll         % stack: i i+inc inc end
         % now we have in the stack: i (the value we want to leave
         % for the user) and  i+inc inc end (the updated iteration
         % status).
         ARRAY astore     % store the new iteration status back in ARRAY
         pop              % now just i is left in the stack
     } def
     % now return both procs:
     /next load
     /hasnext? load
} def

Now the user can write:

   1 2 3 makeforiterator

bind the procs:

   /next? exch def   /PUT-NEXT-ITEM-IN-STACK exch def

and use them in their own loop:

   { PUT-NEXT-ITEM-IN-STACK  ...my-code... } loop

or use the helpful function `done`:

   1 2 3 makeforiterator { ...my-code... } done

As you can see, there is a lot of boilerplate in
`makeforiterator`. The "array astore /ARRAY exch def" in the setup,
the "ARRAY aload pop" at the beginning of each proc, the check at the
beginning of /next, etc... We put all this in another function, which
will get just the variable parts:

   - 3
        the number of elements to store in ARRAY
   - { exch pop lt }
        a proc which gets three parameters (the result of `ARRAY aload
        pop`) and returns true|false. This's the non-boilerplate part
        of `hasnext?`
   - { 2 index 2 index add 3 1 roll }
        a proc that gets three parameters (the result of `ARRAY aload
        pop`) and returns (a) the current element (b) the updated
        iteration status, to be stored in ARRAY. This's the
        non-boilerplate part of `next`.

and will fill the boilerplate. That's is what `makeiterator` does.

Now, of course we can't just store the array and procs in the current
dictionary. We have discussed before methods to insert objects
directly in code, like in this thread:

   https://groups.google.com/d/msg/comp.lang.postscript/SjXE6-Azoz0/ZOWFzblMsrkJ

Then you came up with this

   https://groups.google.com/d/msg/comp.lang.postscript/oQ3CNa0opWk/Dx_HYmAEAQAJ

which is much more simpler (just do it "by hand") and doesn't require
any support code. That's what I used in `makeiterator`. I just changed
things like

   { ARRAY aload pop ... }

to

   [ /ARRAY load /aload cvx /pop cvx ... ] cvx

so ARRAY would be inserted directly in the code.

And I think that's all.

HTH.

-- 

[toc] | [prev] | [next] | [standalone]

#2820

On Monday, September 19, 2016 at 8:03:15 AM UTC-5, Carlos wrote:

> Then you came up with this
> 
>    https://groups.google.com/d/msg/comp.lang.postscript/oQ3CNa0opWk/Dx_HYmAEAQAJ
> 
> which is much more simpler (just do it "by hand") and doesn't require
> any support code. That's what I used in `makeiterator`. I just changed
> things like
> 
>    { ARRAY aload pop ... }
> 
> to
> 
>    [ /ARRAY load /aload cvx /pop cvx ... ] cvx
> 
> so ARRAY would be inserted directly in the code.
> 
> And I think that's all.
> 
> HTH.
> 

Yes. I see. It took a long time to make the idea that simple.
Further documented here: http://stackoverflow.com/a/22240595/733077
The crucial insight is that by constructing a small procedure
body, we're putting data on the Exec Stack. That's how to stay
clean from the other stacks.

In the pursuit of making loops, that led me down the rabbit hole
of having to catch errors and /where/ to catch the error.
Specifically if stopped is inside of a loop, then `exit` won't 
get to the loop in its crawl down Exec Stack.

Of course, we've hit so many complications in these threads that
it's hard to be at all certain that this final technique covers
everything that could go wrong. In this light, the iterators and
"inversion of control" is very very appealing. As you say,
it makes all these problems go away. 

[toc] | [prev] | [next] | [standalone]

#2821

On Monday, September 19, 2016 at 12:56:28 PM UTC-5, luser droog wrote:

> In the pursuit of making loops, that led me down the rabbit hole
> of having to catch errors and /where/ to catch the error.
> Specifically if stopped is inside of a loop, then `exit` won't 
> get to the loop in its crawl down Exec Stack.

The reverse of this rule is also very useful. `stop` will pass over
enclosing loops in its search for the stopped context. So you can
bail out of several nested loops with stop.

[toc] | [prev] | [next] | [standalone]

#2822

On Monday, September 19, 2016 at 12:56:28 PM UTC-5, luser droog wrote:
> On Monday, September 19, 2016 at 8:03:15 AM UTC-5, Carlos wrote:
> 
> > Then you came up with this
> > 
> >    https://groups.google.com/d/msg/comp.lang.postscript/oQ3CNa0opWk/Dx_HYmAEAQAJ
> > 
> > which is much more simpler (just do it "by hand") and doesn't require
> > any support code. That's what I used in `makeiterator`. I just changed
> > things like
> > 
> >    { ARRAY aload pop ... }
> > 
> > to
> > 
> >    [ /ARRAY load /aload cvx /pop cvx ... ] cvx
> > 
> > so ARRAY would be inserted directly in the code.
> > 
> > And I think that's all.
> > 
> > HTH.
> > 
> 
> Yes. I see. It took a long time to make the idea that simple.
> Further documented here: http://stackoverflow.com/a/22240595/733077
> The crucial insight is that by constructing a small procedure
> body, we're putting data on the Exec Stack. That's how to stay
> clean from the other stacks.
> 
> In the pursuit of making loops, that led me down the rabbit hole
> of having to catch errors and /where/ to catch the error.
> Specifically if stopped is inside of a loop, then `exit` won't 
> get to the loop in its crawl down Exec Stack.
> 
> Of course, we've hit so many complications in these threads that
> it's hard to be at all certain that this final technique covers
> everything that could go wrong. In this light, the iterators and
> "inversion of control" is very very appealing. As you say,
> it makes all these problems go away.

I think this technique of building a small array also supports
"continuations" in the functional sense. Without the `exec` as in
the above snippets, the resulting array contains the complete
context it needs to perform one step. In our case the object itself
/becomes/ its continuation, but it could easily be designed to 
return a new proc to support a different style.

[toc] | [prev] | [next] | [standalone]

#2831

On Monday, September 19, 2016 at 1:42:16 PM UTC-5, luser droog wrote:

> I think this technique of building a small array also supports
> "continuations" in the functional sense. Without the `exec` as in
> the above snippets, the resulting array contains the complete
> context it needs to perform one step. In our case the object itself
> /becomes/ its continuation, but it could easily be designed to 
> return a new proc to support a different style.

I've been thinking about functional intefaces
in other programming contexts and it now strikes
me that we're kind treading the same ground that 
happened when Level 2 brought out the `upath` 
structure, de-coupling the `pathforall` looping
operator into a suite of state-transition functions.

Using either of 
 * a proc which modifies its own stored values
 * a proc which constructs a new proc for the next call
we have created a "data structure" with a single 
implicit method.

On an unrelated tangent I've decided that /?? is a much
better variable name than /i.

-- 
...damn I thought I was going somewhere with this when I
started typing...

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.postscript

csiph-web