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.

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.