Memoizing in PostScript

Question

The pusherr and poperr procedures maintain an internal stack as a lisp-like linked-list. It's a little slower than an earlier stackwise version according to naive testing. It allocates lots of 2- and 3- element arrays for its data. But the code using them becomes very readable IMO with this approach.

The memo-func function generates a procedure body specified by the template but with the DICT replaced by the dict argument.

The resulting procedure simply pushes the local dict, then pushes an error handler for the /undefined error, then just does load, and pops the handler and the dict. If load does not find the needed value, it will signal an /undefined error which will be caught be our handler.

The error handler calls the procedure named /default and saves the input and output as a new definition in the local dict.

Improvements?

%! 
<< 
/errorstack null % [ {errordict/errname{handler}} null ] 
/pusherr { 
 errordict 3 1 roll 3 copy pop 2 copy get % ed /n {new} ed /n {old} 
 3 array astore cvx errorstack 2 array astore /errorstack exch store 
 put 
} 
/poperr { 
 errorstack dup null ne { 
 aload pop /errorstack exch store 
 exec put 
 } if 
} 
/memo-func { 
 { 
 DICT begin 
 /undefined { pop dup default dup 3 1 roll def } pusherr 
 load 
 poperr 
 end 
 } 
 dup length array copy 
 dup 3 2 roll 0 exch put cvx 
} 
>> begin 
/fib << 
 0 1 
 1 1 
 /default { dup 2 sub fib exch 1 sub fib add } 
>> 100 dict copy memo-func def 
0 1 100 { fib = } for

The 100 dict copy allows you to also set the initial size of the dictionary to determine how many entries you can add before it needs to rehash.

This code was previously posted in comp.lang.postscript at the end of a thread which includes the stackwise version mentioned above.

• luser droog: One issue I can see is it's not clear how to extend it to multiple arguments without a pattern-matching setup which would need to be implemented because PostScript doesn't have it.

Answer 1

Bug

poperr leaves a null on the stack if errorstack is null. Better:

/poperr { 
 errorstack null ne { 
 errorstack aload pop /errorstack exch store 
 exec put 
 } if 
}

This leaves the stack clean and makes extra calls to poperr harmless. If desireable, some action could be put in the else case but since this code is mucking about with error handlers, it is unclear whether signalling an error is correct here.