代码之家 › 专栏 › 技术社区 › Don Hatch

为什么在递归Postscript过程中使用保存/还原?

postscript

1

Don Hatch · 技术社区 · 8 年前

在格伦·C·里德(Glenn C.Reid)的《后记思考》(Thinking In Postscript,1990)一书中,有两个版本给出了一个递归函数的结构。

函数接受一个整数参数:如果参数是奇数, 它返回论点;如果参数为偶数,则函数递归调用自身并返回结果加1,因此结果总是奇数。

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 操纵也被省略了),对吗? 省略它会在某种程度上让程序变得更糟吗?

给出的解释是:

在本例中,字典分配的内存是收回 拯救 和 恢复 ,将每个保存对象放入递归字典,直到需要它。如果递归调用该函数,则可能会生成多个保存对象,但最终会生成每个保存对象在递归调用返回时恢复。

我不明白。不是吗 begin / end 足以回收任何需要回收的内存吗?我对什么不太了解 拯救 / 恢复 是的,但它们听起来像是相当重的操作,这使得它们在这里的出现显得更加奇怪。

安德烈·赫克 "Learning PostScript by Doing" (2005) 使用 拯救 /对它的例子进行类似的还原,其解释基本上是相同的。

2 回复 | 直到 8 年前

1

luser droog 8 年前

我认为你有理由感到困惑。我认为在第一个节目中 save 和 restore 从语义学的角度来看,完全没有必要。唯一有益的效果(对于级别1的口译员)是,它确保用于创建字典的内存可供重用。Postscript Level 2于1992年发布,因此在本书出版两年后。他可能有实验性的口译员负责垃圾收集。但对于使用一级口译员的听众来说,他必须瞄准一级口译员 拯救 和 恢复 是吗只有回收内存的方法。

格伦·里德可能打算举三个例子,但不知何故,其中两个被挤在了一起。看看函数具有 拯救 / 恢复 但是没有创建字典。

/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

这仍然有效!可以说是“使用存储堆栈”[*]。唯一的问题是局部变量具有全局可见性[**]。

谢谢你的提问!读了这个问题后,我顿悟到这是可能的。

[*]具体执行 拯救 和 恢复 不一定需要使用硬件堆栈,但它们的行为在PLRM中描述为使VM遵循“类似堆栈的规则”。

[**]但奇怪的是,这似乎不是 真实的 问题,因为变量的生命周期有限。即使名字 save_obj 和 arg 在其他地方使用的,调用 恢复 将使它们恢复原状。如果函数对字符串中的字节进行了任何修改,则不会出现这种情况,因为字符串值不受 拯救 和 恢复 .

2

1

KenS 8 年前

实际上,“开始”使字典操作数成为字典堆栈上的当前字典。最后要做的就是从堆栈中删除字典。

因此,“end”不会检查(例如)字典堆栈中是否还有任何字典包含您刚刚调用end的字典。它也不会检查操作数堆栈,以查看字典是否从那里引用。等等等等。

这意味着“end”不能决定字典不再被引用,因此它不能丢弃正在使用的内存。

所以这两种操作都不会恢复任何内存。PostScript使用垃圾收集内存模型,因此无法判断何时恢复内存。但是,“保存”会按“原样”保存当前内存,“还原”会将内存恢复到该点。因此,无论在保存和恢复之间发生什么,恢复后的内存都将与保存时完全相同。这是唯一能真正确定的方法。

语言中没有定义垃圾收集器和保存/恢复的精确操作,只要它在执行操作符时的行为符合描述就足够了。

我在PostScript中看到了以多种不同方式实现的内存处理,存储和恢复的具体操作有很大不同。然而,它们通常不是很“重”,因为本质上你只是在内存中做了一个保存标记,然后当你进行恢复时,把这一点之后的所有东西都扔掉。

另一方面,vmreclain通常调用标记/扫描操作来检查VM中分配的所有对象,看看它们是否仍然被引用,如果没有,则丢弃它们。

因此,您可以(通常)用VMRecall代替保存/恢复。效果大致相同,但需要更长的时间才能执行。