程序解释期间的增量式哈希计算(Efficient incremental hash computat

我想写一个递归memoizing Scheme解释 。在评价过程中的任何点，解释器应该能够在接收到对表达和环境的，它先前已经看到作为参数来检测。

平原记忆化eval和apply是低效的 。这将需要对每个呼叫查找在哈希表中的参数eval / apply ，这需要走在哈希表匹配整个（可能很大）参数。

例如，假设解释评估程序

(car (list A))

其中A计算为一个大对象。当解释评估程序(list A)它首先对list和A独立。之前，它适用list来A ，它会查找其哈希表是否已经见过这个应用程序，走在整个A对象来计算哈希值。后来，当memoizing解释适用car到包含列表，它计算了该名单中又涉及到走在整个的目的哈希值。

相反，我想建立一个逐步建立起约独特的哈希值 ，避免了重新计算在可能的情况，并提供了一个保证，碰撞是不可能的解释。

例如，人们可以递归地延伸的每个对象，所述解释器的操作上，其值的MD5，或，如果它是一个复合对象，以其部件散列的MD5。的环境中可能存储的哈希它的每个变量/值的条目，并且环境的散列可能被计算为个体散列的函数。然后，如果在环境的变化中的条目，这是没有必要rewalk整个环境计算环境的新的哈希值。相反，只需要改变的变量/值对的哈希值重新计算，需要更新组项目散列全球哈希值。

是否存在对递归记忆化和/或项目评估的背景下逐步建立约独特的哈希值，尤其是相关的工作？

请注意，如果表达式是不可变的（不能自修改代码），那么你可以对它们使用情商平等。如果环境是不可变的，你可以同样对待他们。 EQ平等是快，因为你只是走位从机器的指针是一个哈希值。

然后，问题是它发生变异的环境中作业，导致表达式的值来改变。如果他们被允许，你如何处理这个。

一种方法是要记包含在他们的词汇范围破坏性代码的环境，并以某种方式加以注释，以便评估可以识别这样的“污染环境”，并为他们不会做缓存。

顺便说一句，你显然希望用这种弱语义哈希表，使得成为垃圾的任何对象不会在内存中堆积起来。