Concatenative PostScript library

As a part of picking up concatenative programming, I decided to implement the common concatenative operations in PostScript. Here is my attempt at implementing some of the words in other concatenative languages in PostScript. Would any one who is familiar with PostScript and functional/concatenative programming comment on my code?

```
%!PS
% conventions: parameter names with let begins with .

% basic definition, makes the definitions less verbose.
/. {bind def} bind def
/' {load} bind def
/reverse {{} exch {exch [3 1 roll aload pop]} forall}.
/let {dup length dict begin reverse {exch def} forall}.
/let* {reverse {exch def} forall}.

% some predicates.
/eq? {eq}.
/list? {dup type /arraytype eq?}.
/leaf? {list? not}.
/empty? {dup length 0 eq?}.
/zero? {dup 0 eq?}.

% stacky functions
/rup {3 1 roll}.
/rdown {3 -1 roll}.
/# {exch dup rdown .makeoperator bind def} bind def

/getname {dup 0 get exch}.
/getbody {dup length 1 sub 1 exch getinterval}.

% convenience arithmetic
/+ {add}.
/- {sub}.
/* {mul}.
/\ {div}.

% lispy functions
/first {0 get}.
/car {first}.
/!first {dup first}.
/rest {dup length 1 sub 1 exch getinterval}.
/cdr {rest}.
/!rest {dup rest}.
/head {dup length 1 sub 0 exch getinterval}.
/!head {dup head}.
/tail {dup length 1 sub get}.
/!tail {dup tail}.
/cons {[rup aload pop]}.
/tadd {[rup aload length 1 add -1 roll] }.
/uncons {getname getbody}.
/concat {exch [ rup aload pop counttomark -1 roll aload pop ] }.
% make a unit list.
/unit {1 array astore cvx}.
/succ {1 add}.
/pred {1 sub}.
/range {[rup exch aload pop rup exch rdown {} for]}.

% higher order thingies.
/map { [ rup forall ] }.
% [1 2 3 4] {1 add} map
/fold {rup exch rdown forall}.
%/reverse {{} {exch cons} fold}.
% {} [1 2 3 4 5] {exch cons} forall

% [1 2 3 4] 0 {+} fold
% name - filter is taken so we are left with..
/find {
4 dict begin
/aif {0 /get /if}.
/atox { [ exch cvx {cvx} forall ] cvx}.
[ rup [ /dup rdown /exec /not [{pop}] aif ] atox forall ]
end}.

/transpose {

There is an improvement that can be made to the map function. Your version:

/. {bind def} bind def

%...

/rup {3 1 roll}.

%...

/map { [ rup forall ] }.
% [1 2 3 4] {1 add} map

The problem here is building the new array on the stack. While normally this is a perfectly sound technique in postscript, it places severe restrictions on how the procedure must behave. Using debug.ps to produce a trace (caveat: I had to remove all the bind calls because the debugger has a bug with binding, apparently) illustrates how the execution proceeds through the example [1 2 3 4] {1 add} map. (I know you know how it executes, this is for the audience. ;)

[  %|- -mark- 
1  %|- -mark- 1 
2  %|- -mark- 1 2 
3  %|- -mark- 1 2 3 
4  %|- -mark- 1 2 3 4 
]  %|- [1 2 3 4] 
{1 add}  %|- [1 2 3 4] {1 add} 
map  %|- [1 2 3 4] {1 add} 
[  %|- [1 2 3 4] {1 add} -mark- 
rup  %|- [1 2 3 4] {1 add} -mark- 
3  %|- [1 2 3 4] {1 add} -mark- 3 
1  %|- [1 2 3 4] {1 add} -mark- 3 1 
roll  %|- -mark- [1 2 3 4] {1 add} 
forall  %|- -mark- 1 
1  %|- -mark- 1 1 
add  %|- -mark- 2 
[2 3 4]  %|- -mark- 2 [2 3 4] 
{1 add}  %|- -mark- 2 [2 3 4] {1 add} 
forall  %|- -mark- 2 2 
1  %|- -mark- 2 2 1 
add  %|- -mark- 2 3 
[3 4]  %|- -mark- 2 3 [3 4] 
{1 add}  %|- -mark- 2 3 [3 4] {1 add} 
forall  %|- -mark- 2 3 3 
1  %|- -mark- 2 3 3 1 
add  %|- -mark- 2 3 4 
[4]  %|- -mark- 2 3 4 [4] 
{1 add}  %|- -mark- 2 3 4 [4] {1 add} 
forall  %|- -mark- 2 3 4 4 
1  %|- -mark- 2 3 4 4 1 
add  %|- -mark- 2 3 4 5 
[]  %|- -mark- 2 3 4 5 [] 
{1 add}  %|- -mark- 2 3 4 5 [] {1 add} 
forall  %|- -mark- 2 3 4 5

So whenever the procedure (the loop body) executes, the rest of the array is on the stack.

1  %|- -mark- 1 1 
add  %|- -mark- 2 
% ...
1  %|- -mark- 2 2 1 
add  %|- -mark- 2 3 
% ...
1  %|- -mark- 2 3 3 1 
add  %|- -mark- 2 3 4 
% ...
1  %|- -mark- 2 3 4 4 1 
add  %|- -mark- 2 3 4 5

So you can't do something like this to add a constant to each element. Because the array-building gets in the way.

5 [1 2 3 4] {1 index add} map

A good attempt at removing this difficulty came from Carlos in a comp.lang.postscript thread. Instead of using a forall loop directly, he uses a for loop running through the indices of the array and calls the user proc by name, managing the extraction and re-insertion of the the values in the array in the loop body.

The problem there is that we've simply passed-off the interference to a different stack. The operand stack is now clear and usable, but the dictionary stack now has our bookkeeping dictionary on top (or worse: everything is global in userdict). So we're very prone to name-collision and unintended scoping issues when trying to use the function in an application.

A couple of little-known features of the postscript language combine to offer a solution: dynamic code-generation. So we want a map that roughly does this:

/map { % arr proc  map  arr'
    10 dict begin           % arr proc
    /proc exch def          % arr
    /arr exch def           % 
    0 1 arr length 1 sub {  % i
        /i exch def         % 
        arr i get           % arr_i
        proc                % proc(arr_i)
        arr exch i exch put % 
    } for                   % 
    arr                     % arr'
    end                     % arr'
} def

But without having this local dictionary on the stack while proc is executing.

What we can do to accomplish this is to generate a loop-body with these names hard-bound to their values. Postscript provides its scanner as the token operator which can produce a complete procedure-body from a string template.

({1 1 add =} remainder) token  %  ( remainder) {1 1 add =} true
pop                            %  ( remainder) {1 1 add =}
exch                           %  {1 1 add =} ( remainder)
pop                            %  {1 1 add =}

And the scanner will also substitute names prefixed with a double-slash // when they are encountered. So we can do this, too:

/val 5 def
({//val =}) token pop exch pop %  {5 =}

Now the name doesn't need to be defined for the procedure to execute.

/val 5 def
({//val =}) token pop exch pop %  {5 =}
currentdict /val undef
exec  % prints: 5

So finally we get something like this:

```
/map { % arr proc map arr'
10 dict begin % arr proc
/mydict currentdict def % arr proc
/proc exch def % arr
/arr exch def %
0 1 arr length 1 sub % 0 1 n-1
({
{ % i
//mydict exch /i exch put %
//arr % arr
//mydict /i get % arr i
get % arr_i
//mydict /proc get % arr_i proc
exec % proc(arr_i)
//arr exch % arr proc(arr_i)
//mydict /i get exch % arr i proc(arr_i)
put %
} for %
//arr % arr'
}) token po

StackExchange Code Review Q#12249, answer score: 9