Why use save/restore in recursive Postscript procedures?

In Glenn C. Reid's book Thinking in Postscript (1990), two versions
of a recursive function are shown.

The function takes one integer argument: if the argument is odd,
it returns the argument; if the argument is even, the function
calls itself recursively and returns the result plus one, so the result is always an odd number.

Example 6.5: Recursion Using the Dictionary Stack

/recurse_proc % int recurse_proc int
%def
save
2 dict begin
/save_obj exch def
/arg exch def
arg 2 div truncate
2 mul cvi
arg eq %ifelse
% even number
arg 1 add recurse_proc
%else
arg
ifelse
save_obj % leave on stack
end
restore % to save_obj on stack
bind def
2 recurse_proc


In Example 6.6 is the same procedure as the one in Example 6.5, rewritten to use the operand stack instead of the dictionary stack.

Example 6.6: Recursion Using the Operand Stack

/recurse_proc % int recurse_proc int
%def
dup 2 div truncate
2 mul cvi
1 index eq %ifelse
% even number
1 add recurse_proc
if
bind def
2 recurse_proc


My question is: what is the point of the save/restore
in Example 6.5? The program works fine without it (if the save_obj manipulation is omitted too), right?
Would omitting it make the program worse in some way?

save

restore

save_obj

The explanation given is:

In this example, the memory allocated by the dictionary is
reclaimed by save and restore, putting each save object into the recursion
dictionary until it is needed. If the function is called recursively, more
than one save object may be generated, but each will ultimately be
restored as the recursive calls return.

save

restore

I don't understand that. Isn't the begin/end sufficient to reclaim any memory that needs reclaiming? I don't have a very deep understanding of what save/restore do, but they sound like fairly heavyweight operations, which makes their appearance here seem all the more odd.

begin

end

save

restore

André Heck's "Learning PostScript by Doing" (2005) uses save/restore similarly for its examples, and its explanation is essentially the same.

save

2 Answers
2

begin, in effect, makes the dictionary operand the current dictionary on the dictionary stack. All end does is remove the dictionary from the stack.

So 'end' doesn't check to see if (for example) any of the dictionaries still on the dictionary stack includes the dictionary that you just called end for. Nor does it check the operand stack to see if the dictionary is referenced from there. Etc, etc.

That means that 'end' can't decide that the dictionary is no longer referenced, so it can't discard the memory it is using.

So neither of those operations recovers any memory. PostScript uses a Garbage Collected memory model, so you can't tell when memory will be recovered. However, save saves the current memory 'as is' and restore restores the memory back to that point. So no matter what occurs between save and restore, the memory will be exactly the same after the restore as it was at the point of the save. That's the only way to be really certain.

The precise action of the garbage collector and save/restore isn't defined in the language, its sufficient that it behaves as described when you execute the operators.

I've seen memory handling implemented in a number of different ways in PostScript, and the exact action of save and restore varies considerably. However they are not usually very 'heavywieght', because essentially you are just making a mark in memory for the save, and throwing everything after that point away when you do a restore.

vmreclaim on the other hand, usually invokes a mark/sweep operation to check all objects allocated in VM to see if they are still referenced and discarding them if not.

So instead of a save/restore you could (usually) replace the restore with a vmreclaim. The effect would be broadly the same, but it would take a lot longer to execute.

I think you are rightly confused. I think that in the first program the save and restore are entirely unnecessary from a semantics point of view. The only beneficial effect (on Level 1 interpreters) is that it ensures that the memory used for the create dictionary is made available for re-use. Postscript Level 2 was released in 1992, so 2 years after this book. There may have been experimental interpreters available to him that had Garbage Collection. But for his audience who were using an installed base of Level 1 interpreters he had to target Level 1, and save and restore are the only way to reclaim memory.

save

restore

save

restore

It's possible that Glenn Reid intended to make three examples but somehow two of them got squashed together. Take a look at the function with save/restore but without creating a dictionary.

save

restore

/recurse_proc % int recurse_proc int
%def
save
/save_obj exch def
/arg exch def
arg 2 div truncate
2 mul cvi
arg eq %ifelse
% even number
arg 1 add recurse_proc
%else
arg
ifelse
save_obj % leave on stack
restore % to save_obj on stack
bind def
2 recurse_proc


This still works! It might be said to "use the Save Stack"[*]. The only problem is that the local variables have global visibility[**].

Thanks for a great question! I had the epiphany that this was possible after reading the question.

[*] The exact implementation of save and restore do not necessarily need to employ a hardware stack, but their action is described in the PLRM as enabling VM to follow a "stack-like discipline".

save

restore

[**] But, bizarrely, this doesn't seem to be a real problem since the variables have a limited lifetime. Even if the names save_obj and arg were used elsewhere, the call to restore would revert them to their original states. This would not be the case if the function made any modification of the bytes in a string, since string values are not affected by save and restore.

save_obj

arg

restore

save

restore

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy