map and higher order functions

[Carlos]

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

--

[ken]

In article <20141030172...@samara.DOMA>, an...@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

[Carlos]

[ken <k...@spamcop.net>, 2014-10-30 16:57]

> In article <20141030172...@samara.DOMA>,
> an...@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.

> [...]

--

[Ross Presser]

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.

[luser- -droog]

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

[ken]

In article <20141030195...@samara.DOMA>, an...@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

[Carlos]

[Ross Presser <rpre...@gmail.com>, 2014-10-30 20:30]

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

[Carlos]

[luser- -droog <mij...@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

--

[luser- -droog]

On Saturday, November 1, 2014 6:15:40 PM UTC-5, Carlos wrote:
> [luser- -droog <mij...@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.

[Carlos]

[luser- -droog <mij...@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.
--

[luser- -droog]

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!

[luser- -droog]

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