Зачем использовать сохранение / восстановление в рекурсивных процедурах Postscript?

Question

В книге Гленна К. Рейда «Мышление в постскриптуме» (1990), две версии рекурсивной функции.

Функция принимает один целочисленный аргумент: если аргумент нечетный, возвращает аргумент; если аргумент четный, функция вызывает себя рекурсивно и возвращает результат плюс один, так что результатом всегда будет нечетное число.

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

В Примере 6.6 та же процедура, что и в Примере 6.5, переписана для использования стека операндов вместо стека словаря.

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

Мой вопрос: в чем смысл save / restore в Примере 6.5? Программа отлично работает без нее (если и манипуляции save_obj тоже опущены), верно? Не упустит ли это какую-нибудь программу хуже?

Объяснение дано:

В этом примере память, выделенная словарем, восстанавливается save и restore, помещая каждый объект сохранения в рекурсию словарь пока не нужен. Если функция вызывается рекурсивно, более чем один объект сохранения, но каждый в конечном итоге будет восстанавливается при возврате рекурсивных вызовов.

Я не понимаю этого. Разве begin / end не достаточно для восстановления памяти, требующей восстановления? Я не очень хорошо понимаю, что делают save / restore, но они звучат как довольно тяжелые операции, что делает их появление здесь еще более странным.

Андре Хека * "Изучение PostScript с помощью Doing" (2005) использует save / restore аналогично для своих примеров, и его объяснение по существу такое же.

Answer 1

Я думаю, что вы совершенно запутались. Я думаю, что в первой программе save и restore совершенно не нужны с точки зрения семантики. Единственный полезный эффект (для интерпретаторов уровня 1) заключается в том, что он обеспечивает доступность памяти, используемой для создания словаря, для повторного использования. Постскриптум Level 2 был выпущен в 1992 году, так что спустя 2 года после этой книги. Возможно, ему были доступны экспериментальные переводчики, у которых была сборка мусора. Но для своей аудитории, которая использовала установленную базу интерпретаторов уровня 1, он должен был нацелиться на уровень 1, и save и restore - это только способ восстановить память.

Возможно, что Гленн Рид намеревался сделать три примера, но каким-то образом два из них были сведены вместе. Взгляните на функцию с 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

Это все еще работает! Можно сказать «использовать стек сохранения» [*]. Единственная проблема заключается в том, что локальные переменные имеют глобальную видимость [**].

Спасибо за отличный вопрос! У меня было прозрение, что это стало возможным после прочтения вопроса.

[*] Точная реализация save и restore не обязательно должна использовать аппаратный стек, но их действие описывается в PLRM как предоставление возможности виртуальной машине следовать «подобной стеку дисциплине».

[**] Но, как ни странно, это не похоже на реальную проблему, поскольку переменные имеют ограниченное время жизни. Даже если имена save_obj и arg были использованы в другом месте, вызов restore вернул бы их в их первоначальное состояние. Этого не произошло бы, если бы функция выполняла какие-либо изменения байтов в строке, поскольку на строковые значения не влияют save и restore.

Answer 2

begin, по сути, делает словарь операндом текущим словарем в стеке словарей. Все, что нужно сделать, это удалить словарь из стека.

Таким образом, 'end' не проверяет, содержит ли (например) какой-либо словарь, все еще находящийся в стеке словарей, словарь, для которого вы только что назвали end. Он также не проверяет стек операндов, чтобы определить, есть ли ссылка на словарь оттуда. И т. Д.

Это означает, что 'end' не может решить, что на словарь больше не ссылаются, поэтому он не может сбросить используемую память.

Так что ни одна из этих операций не восстанавливает память. PostScript использует модель памяти с мусором, поэтому вы не можете определить, когда будет восстановлена ​​память. Однако сохранение сохраняет текущую память «как есть», а восстановление восстанавливает память до этой точки. Поэтому независимо от того, что происходит между сохранением и восстановлением, после восстановления память будет точно такой же, какой она была в момент сохранения. Это единственный способ быть уверенным в себе.

Точное действие сборщика мусора и сохранения / восстановления не определено в языке, достаточно того, что оно ведет себя так, как описано при выполнении операторов.

Я видел обработку памяти, реализованную различными способами в PostScript, и точное действие сохранения и восстановления значительно различается. Однако они обычно не очень «тяжелые», потому что, по сути, вы просто делаете отметку в памяти для сохранения и выбрасываете все после этой точки, когда вы делаете восстановление.

vmreclaim, с другой стороны, обычно вызывает операцию mark / sweep, чтобы проверить все объекты, выделенные в VM, чтобы увидеть, есть ли на них ссылки, и отбросить их, если нет.

Таким образом, вместо сохранения / восстановления вы можете (обычно) заменить восстановление на vmreclaim. Эффект будет примерно таким же, но для его выполнения потребуется намного больше времени.