3

我想写一个递归记忆的 Scheme 解释器。在评估期间的任何时候，解释器都应该能够检测到它何时接收到它以前见过的一对表达式和环境作为参数。

简单的记忆eval和apply是低效的。eval它需要在每次调用/时查找哈希表中的参数apply，这将需要遍历哈希表匹配的整个（可能很大）参数。

例如，假设解释器评估程序

(car (list A))

其中 A 计算为一个大对象。当解释器评估应用程序(list A)时，它首先单独评估list和A。在应用于 之前list，A它会在其哈希表中查找它之前是否见过此应用程序，遍历整个A对象以计算哈希。稍后，当记忆解释器应用于car包含 A 的列表时，它会为该列表计算一个哈希，这再次涉及遍历整个 A 对象。

相反，我想构建一个解释器，逐步建立近似唯一的 hashes，尽可能避免重新计算，并保证不会发生冲突。

例如，可以使用其值的 MD5 递归扩展解释器操作的每个对象，或者，如果它是复合对象，则使用其组件散列的 MD5。环境可能会为其每个变量/值条目存储散列，并且环境的散列可以作为单个散列的函数来计算。然后，如果环境中的条目发生变化，则无需重新遍历整个环境来计算环境的新哈希。相反，只需要重新计算已更改的变量/值对的散列，并且需要更新条目散列集的全局散列。

是否存在增量构建近似唯一哈希的相关工作，特别是在递归记忆和/或程序评估的背景下？

4

1 回答 1

2

请注意，如果表达式是不可变的（不允许自修改代码），那么您可以对它们使用 EQ 相等。如果环境是不可变的，您可以同样对待它们。EQ 相等很快，因为您只是将机器指针中的位作为哈希。

那么问题是分配改变环境，导致表达式值改变。如果他们被允许，如何处理。

一种方法是记下在其词法范围内包含破坏性代码的环境，并以某种方式对其进行注释，以便评估者可以识别此类“污染环境”而不为它们进行缓存。

顺便说一句，您显然需要具有弱语义的哈希表，这样任何成为垃圾的对象都不会堆积在内存中。

于 2012-04-25T01:17:05.440 回答