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

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

map and higher order functions

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

Contents

  map and higher order functions Carlos <angus@quovadis.com.ar> - 2014-10-30 17:27 +0100
    Re: map and higher order functions ken <ken@spamcop.net> - 2014-10-30 16:57 +0000
      Re: map and higher order functions Carlos <angus@quovadis.com.ar> - 2014-10-30 19:55 +0100
        Re: map and higher order functions ken <ken@spamcop.net> - 2014-10-31 12:17 +0000
    Re: map and higher order functions Ross Presser <rpresser@gmail.com> - 2014-10-30 20:30 -0700
      Re: map and higher order functions Carlos <angus@quovadis.com.ar> - 2014-11-01 23:58 +0100
    Re: map and higher order functions luser- -droog <mijoryx@yahoo.com> - 2014-10-30 22:56 -0700
      Re: map and higher order functions Carlos <angus@quovadis.com.ar> - 2014-11-02 00:15 +0100
        Re: map and higher order functions luser- -droog <mijoryx@yahoo.com> - 2014-11-15 00:43 -0800
          Re: map and higher order functions Carlos <angus@quovadis.com.ar> - 2014-11-16 01:37 +0100
            Re: map and higher order functions luser- -droog <mijoryx@yahoo.com> - 2014-11-21 00:17 -0800
            Re: map and higher order functions luser- -droog <mijoryx@yahoo.com> - 2015-02-27 00:59 -0800

#2081 — map and higher order functions

How would you implement map and other higher order functions
(procedures taking one or more procedures)?

Especially the part when the procedure is to be run, and you must clear
the stacks from your working elements.

I've resorted to use a stack of dictionaries anchored on userdict
(implemented with a linked list) to keep local variables. It works but
I don't really like it.

What are other possibilities?

Carlos.

PS: what I'm using now:

#!
%----8<-----

userdict begin

/$--libstack-- null def

% - -frame- <current frame>
/-frame- { userdict /$--libstack-- get } bind def

% <dict> -newframe- -
/-newframe- {
    dup /$--next-- userdict /$--libstack-- get put
    userdict /$--libstack-- 3 -1 roll put
} bind def

% - -endframe- -
/-endframe- {
    userdict /$--libstack--
        userdict /$--libstack-- get  /$--next-- get
    put
} bind def

end % userdict
    

% applies proc to each element of array/str,
% collects results into new array/str
% <array/string> <proc> map <new array/string>
/map {
    5 dict begin
        /proc exch def
        /arr  exch def
        /res  arr length
              arr type /stringtype eq { string } { array } ifelse
        def
        /i    0   def
        currentdict
    end -newframe-
    0 1 -frame- /arr get length 1 sub { % for
        -frame- /i 3 -1 roll put
        -frame- /arr get  -frame- /i get get
        -frame- /proc get exec
        -frame- /res get  -frame- /i get  3 -1 roll put
    } for
    -frame- /res get
    -endframe-
} bind def

%----8<-----

-- 

[toc] | [next] | [standalone]

#2082

In article <20141030172728.0983c6bc@samara.DOMA>, angus@quovadis.com.ar 
says...
> 
> How would you implement map and other higher order functions
> (procedures taking one or more procedures)?

I'm not sure what your 'map' function is intended to do, but...
 

> % applies proc to each element of array/str,

forall applies 'proc' to each element in turn of arrays. packedarrays, 
dictionaries or strings, essentially any compound object in PostScript.

So I think I'd use forall myself.


> % collects results into new array/str
> % <array/string> <proc> map <new array/string>

If you want to retrieve results, then you'll have to have proc store the 
results *somewhere* as it executes. You could create a local variable, 
stash it in userdict, or simply create a variable on the stack before 
you execute forall, and have proc use 'index' to take a copy of it, 
which it can then manipulate:

Eg
(returned string) (string to process) 

{
1 index    %% Working variable is now top of stack
exch       %% (working string) string element 'n'
....
....       %% do some processing
....
} 

forall

This would leave (returned string) on the stack at the end, obviously 
your procedure has to be careful about stack manipulations.

NB if the local variable needs to grow, you might need to reallocate it 
and that would mean removing the copy from the stack, and replacing it 
with the increased allocation variable.

		Ken

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

#2083

[ken <ken@spamcop.net>, 2014-10-30 16:57]
> In article <20141030172728.0983c6bc@samara.DOMA>,
> angus@quovadis.com.ar says...
> > 
> > How would you implement map and other higher order functions
> > (procedures taking one or more procedures)?
> 
> I'm not sure what your 'map' function is intended to do, but...

This is what it's intended to do:

GS>[ 1 2 3 4 ] { 1 add } map ==
[2 3 4 5]

Inside map, I have to exec the proc ({ 1 add } in this case) without
having anything on the stack. Otherwise, this

GS> 3 [ 1 2 3 4 ] { 1 index add } map ==
[4 5 6 7]

wouldn't work, since "1 index" would retrieve some value used
internally by map, and not what the user expects.

I can't also simply use an entry in userdict, because it would get
clobbered if the function re-enters, and this would fail:

GS>[ [ 1 2 3 ] [ 4 5 6 ] ] { { 1 add } map } map ==
[[2 3 4] [5 6 7]]

Nor can I have anything on the dictionary stack (using "n dict
begin ... end" to hold "local variables"), because the user might
execute a "def" inside the procedure, and the entry would be stored in
the wrong dictionary.

I'd like to know what the options are to solve this problem.

I hope it is clearer now.

> [...]

-- 

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

#2086

In article <20141030195524.77fe473f@samara.DOMA>, angus@quovadis.com.ar 
says...

> I'd like to know what the options are to solve this problem.
> 
> I hope it is clearer now.

Yes, and to be honest, with such a stringent set of requirements, I 
can't think of a better solution than your original, or simlar 
variations.


			Ken

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

#2084

On Thursday, October 30, 2014 12:27:49 PM UTC-4, Carlos wrote:
> How would you implement map and other higher order functions
> (procedures taking one or more procedures)?
> 
> Especially the part when the procedure is to be run, and you must clear
> the stacks from your working elements.


This might be of some interest:
http://codereview.stackexchange.com/questions/12249/concatenative-postscript-library

I do not know if it does anything to clear stacks, but it definitely defines /map and is along the same lines as your attempt.

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

#2087

[Ross Presser <rpresser@gmail.com>, 2014-10-30 20:30]
> On Thursday, October 30, 2014 12:27:49 PM UTC-4, Carlos wrote:
> > How would you implement map and other higher order functions
> > (procedures taking one or more procedures)?
> > 
> > Especially the part when the procedure is to be run, and you must
> > clear the stacks from your working elements.
> 
> 
> This might be of some interest:
> http://codereview.stackexchange.com/questions/12249/concatenative-postscript-library
> 
> I do not know if it does anything to clear stacks, but it definitely
> defines /map and is along the same lines as your attempt.

It's quite elegant how he defines it, unfortunately it uses the stack to
accumulate the result, so the passed proc can't use it.
-- 

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

#2085

On Thursday, October 30, 2014 11:27:49 AM UTC-5, Carlos wrote:
> How would you implement map and other higher order functions
> (procedures taking one or more procedures)?
> 
> Especially the part when the procedure is to be run, and you must clear
> the stacks from your working elements.
> 
> I've resorted to use a stack of dictionaries anchored on userdict
> (implemented with a linked list) to keep local variables. It works but
> I don't really like it.
> 
> What are other possibilities?
> 

I've run into similar issues trying to write procedures that work 
like "control structures", like loops. The trick I've found is to 
use the `token` operator to dynamically build a new procedure body
based on a string template. Eg. This procedure

  { 1 add }

becomes

  ({ 1 add }) token pop exch pop   % { 1 add }

. Now what's cool about this is you can bind names in the procedure
at the time it is created, by using immediately-loaded names (PLRM
calls them immediately-evaluated, but I've decided that's a stupid name).

  /x 1 def
  ({ //x add }) token pop exch pop

And the name only needs to be on the dictstack while the `token` 
operator is executing, and then it can go away.

  1 dict begin
  /x 1 def
  ({ //x add }) token pop exch pop
  end       % { 1 add }

I used this trick to make a loop body that calls a user proc.
But it leaves the dictstack clean while the user proc is 
executing, and then reclaims the dictionary. Like this,

  1 dict begin
  /DICT currentdict def
  /x 1 def
  ({ //x add //DICT begin /x 2 def end }) token pop exch pop
  end

Um. that's a stupid example, since we've already bound //x,
redefining isn't going to do anything. But I hope the basic
idea is clear. If you bind all the names in a procedure,
that procedure can execute without needing access to those
definitions.

For a fuller (working) example, see my answer here:
http://stackoverflow.com/a/20581765/733077
although it was probably overkill for that question. :)

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

#2088

[luser- -droog <mijoryx@yahoo.com>, 2014-10-30 22:56]
> On Thursday, October 30, 2014 11:27:49 AM UTC-5, Carlos wrote:
> > How would you implement map and other higher order functions
> > (procedures taking one or more procedures)?
> > 
> > Especially the part when the procedure is to be run, and you must
> > clear the stacks from your working elements.
> > [...]
> 
> I've run into similar issues trying to write procedures that work 
> like "control structures", like loops. The trick I've found is to 
> use the `token` operator to dynamically build a new procedure body
> based on a string template.
> [...]
> I used this trick to make a loop body that calls a user proc.
> But it leaves the dictstack clean while the user proc is 
> executing, and then reclaims the dictionary. Like this,
> 
>   1 dict begin
>   /DICT currentdict def
>   /x 1 def
>   ({ //x add //DICT begin /x 2 def end }) token pop exch pop
>   end
> [...]

This is great! It makes everything so much simpler. That's exactly what
I was looking for. Thanks.

Carlos.

PS: the new implementation:

% <array/string> <proc> map <new array/string>
/map {
    4 dict begin
        /proc exch def
        /arr exch def
        /res arr length
             arr type /stringtype eq { string } { array } ifelse
        def
        /i 1 array def
        ({
            0 1 //arr length 1 sub { % for
                dup //i 0  3 -1 roll  put
                //arr exch get
                //proc exec
                //res //i 0 get  3 -1 roll  put
            } for
            //res
        }) token pop exch pop bind
    end
    exec
} bind def

-- 

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

#2094

On Saturday, November 1, 2014 6:15:40 PM UTC-5, Carlos wrote:
> [luser- -droog <mijoryx@yahoo.com>, 2014-10-30 22:56]
> PS: the new implementation:
> 
> % <array/string> <proc> map <new array/string>
> /map {
>     4 dict begin
>         /proc exch def
>         /arr exch def
>         /res arr length
>              arr type /stringtype eq { string } { array } ifelse
>         def
>         /i 1 array def
>         ({
>             0 1 //arr length 1 sub { % for
>                 dup //i 0  3 -1 roll  put
>                 //arr exch get
>                 //proc exec
>                 //res //i 0 get  3 -1 roll  put
>             } for
>             //res
>         }) token pop exch pop bind
>     end
>     exec
> } bind def
> 

There is a possible problem here. Since `bind` applies to all subarrays,
and the user-proc has been embedded directly into this array.

instead of

>                 //proc exec

it might be better to do

                  //mydict /proc get exec

so the procedure is not directly embedded.

Applying `bind` would break code that tries to use operator names as
variables, like

    {
        /length 5 def
        length dup mul % length^2
        ...
    }

The executable name `length` in the second line would be replaced by the 
postscript operator if `bind` were applied.

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

#2095

[luser- -droog <mijoryx@yahoo.com>, 2014-11-15 00:43]
[...]
> There is a possible problem here. Since `bind` applies to all
> subarrays, and the user-proc has been embedded directly into this
> array.
> 
> instead of
> 
> >                 //proc exec
> 
> it might be better to do
> 
>                   //mydict /proc get exec
> 
> so the procedure is not directly embedded.
> 
> Applying `bind` would break code that tries to use operator names as
> variables, like
> 
>     {
>         /length 5 def
>         length dup mul % length^2
>         ...
>     }
> 
> The executable name `length` in the second line would be replaced by
> the postscript operator if `bind` were applied.

I didn't think of that. The problem is worse, because the string is
tokenized at the time /map is executed, and by that moment the user
could have already redefined some operators (presumably he wouldn't do
that at library loading time).

    /length 5 def [ 1 2 3 ] { length add } map

So, basically, inside /map, the code surrounding "<userproc> exec"
should be bound before any operator is redefined, but the "<userproc>"
should be left as-is.

One solution can be to write the code as usual (not in a string), using
placeholders for the objects. That way, it would be bound at definition
time. When /map is called, the placeholders are replaced with the
objects. Basically, doing the "({ //x }) token" thing by hand, just so
everything that isn't a //name can be bound at definition time.

Here is a new version of map that uses that approach, plus two helper
procedures:

% <array/string> <proc> map <new array/string>
/map {
    4 dict begin
        /,proc exch def
        /,arr exch def
        /,res ,arr length
             ,arr type /stringtype eq { string } { array } ifelse
        def
        /,i 1 array def
        {
            0 1 /,arr length 1 sub { % for
                dup /,i 0  3 -1 roll  put
                /,arr exch get
                /,proc exec
                /,res /,i 0 get  3 -1 roll  put
            } for
            /,res
        } deepcopy dup currentdict replaceall
    end exec
} bind def

% copies array recursively
% <array> deepcopy <new array>
/deepcopy {
    dup xcheck exch
    dup length array copy
    dup length 1 sub 0 exch 1 exch { % for       % a i
        2 copy 2 copy get dup type /arraytype eq % a i a i e ?
        { % ifelse
            deepcopy put
        }
        {
            pop pop pop
        } ifelse
        pop
    } for
    exch { cvx } if
} bind def

% recursively replaces elements in <array> found in <dict>
% <array> <dict> replaceall -
/replaceall {
    1 index length 1 sub  0 1  3 -1 roll { % for 0 1 length-1
        3 copy  3 -1 roll  exch    % a d i d a i
        get                        % a d i d e
        2 copy known               % a d i d e ?
        % ifelse
        {                          % a d i d e
            get                    % a d i v
            3 index  3 1 roll      % a d a i v
            put
        } % else
        {                          % a d i d e
            dup type /arraytype eq % a d i d e ?
            { exch replaceall }
            { pop pop } ifelse
            pop
        } ifelse                   % a d
    } for
    pop pop
} bind def

Carlos.
-- 

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

#2102

On Saturday, November 15, 2014 6:38:00 PM UTC-6, Carlos wrote:
[very cool stuff]

I've summarized and explained your results at:
http://codereview.stackexchange.com/a/69933/5912

Bravo!

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

#2194

On Saturday, November 15, 2014 at 6:38:00 PM UTC-6, Carlos wrote:
> [luser- -droog <mijoryx@yahoo.com>, 2014-11-15 00:43]
> [...]
> > There is a possible problem here. Since `bind` applies to all
> > subarrays, and the user-proc has been embedded directly into this
> > array.
> > 
> > instead of
> > 
> > >                 //proc exec
> > 
> > it might be better to do
> > 
> >                   //mydict /proc get exec
> > 
> > so the procedure is not directly embedded.
> > 
> > Applying `bind` would break code that tries to use operator names as
> > variables, like
> > 
> >     {
> >         /length 5 def
> >         length dup mul % length^2
> >         ...
> >     }
> > 
> > The executable name `length` in the second line would be replaced by
> > the postscript operator if `bind` were applied.
> 
> I didn't think of that. The problem is worse, because the string is
> tokenized at the time /map is executed, and by that moment the user
> could have already redefined some operators (presumably he wouldn't do
> that at library loading time).
> 
>     /length 5 def [ 1 2 3 ] { length add } map
> 
> So, basically, inside /map, the code surrounding "<userproc> exec"
> should be bound before any operator is redefined, but the "<userproc>"
> should be left as-is.
> 
> One solution can be to write the code as usual (not in a string), using
> placeholders for the objects. That way, it would be bound at definition
> time. When /map is called, the placeholders are replaced with the
> objects. Basically, doing the "({ //x }) token" thing by hand, just so
> everything that isn't a //name can be bound at definition time.
> 
> Here is a new version of map that uses that approach, plus two helper
> procedures:
> 
> % <array/string> <proc> map <new array/string>
> /map {
>     4 dict begin
>         /,proc exch def
>         /,arr exch def
>         /,res ,arr length
>              ,arr type /stringtype eq { string } { array } ifelse
>         def
>         /,i 1 array def
>         {
>             0 1 /,arr length 1 sub { % for
>                 dup /,i 0  3 -1 roll  put
>                 /,arr exch get
>                 /,proc exec
>                 /,res /,i 0 get  3 -1 roll  put
>             } for
>             /,res
>         } deepcopy dup currentdict replaceall
>     end exec
> } bind def
> 
> % copies array recursively
> % <array> deepcopy <new array>
> /deepcopy {
>     dup xcheck exch
>     dup length array copy
>     dup length 1 sub 0 exch 1 exch { % for       % a i
>         2 copy 2 copy get dup type /arraytype eq % a i a i e ?
>         { % ifelse
>             deepcopy put
>         }
>         {
>             pop pop pop
>         } ifelse
>         pop
>     } for
>     exch { cvx } if
> } bind def
> 
> % recursively replaces elements in <array> found in <dict>
> % <array> <dict> replaceall -
> /replaceall {
>     1 index length 1 sub  0 1  3 -1 roll { % for 0 1 length-1
>         3 copy  3 -1 roll  exch    % a d i d a i
>         get                        % a d i d e
>         2 copy known               % a d i d e ?
>         % ifelse
>         {                          % a d i d e
>             get                    % a d i v
>             3 index  3 1 roll      % a d a i v
>             put
>         } % else
>         {                          % a d i d e
>             dup type /arraytype eq % a d i d e ?
>             { exch replaceall }
>             { pop pop } ifelse
>             pop
>         } ifelse                   % a d
>     } for
>     pop pop
> } bind def
> 
> Carlos.
> --

I stumbled across an old one of mine. The file is
dated Dec 24 2012. This version is not safe to use
if any of its operators are not available by their
standard names at *execution time*, ie. this code
exhibits the problem that Carlos's code solves.
But it's shorter. :)

It also modifies the argument in-place. So if you
want a copy, make a copy. Delayed-binding, and such.

%!
%/exch{pstack exch}bind def 

%string proc  map  --  
%array proc  map  --  
/map{
    4 dict dup begin
    {/dic/proc/src}{exch def}forall

    0 1 src length 1 sub 
    (   
     {   
        //dic/i 2 index put 
        //src exch get 
            //proc exec
        //src exch //dic/i get exch put 
     }   
    )token pop exch pop 
    bind end for 
}def

[1 1 1]dup{1 sub}map ==
(---)== flush
(this_is_a_lowercase_string___ish)dup
{16#20 sub}map
==

[toc] | [prev] | [standalone]

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

csiph-web