我想写一个递归记忆Scheme解释器。在求值过程中的任何时刻，解释器都应该能够检测到它何时接收到之前见过的一对表达式和环境作为参数。
简单记忆eval and apply效率低下。每次调用时都需要在哈希表中查找参数eval/apply，这需要遍历哈希表匹配上的整个（可能很大）参数。
例如，假设解释器评估程序
(car (list A))
其中 A 计算为一个大对象。当口译员评估申请时(list A)，它首先评估list and A单独。在适用之前list to A，它在哈希表中查找以前是否见过这个应用程序，遍历整个A计算哈希值的对象。稍后，当记忆解释器应用时car对于包含 A 的列表，它计算该列表的哈希值，这再次涉及遍历整个 A 对象。
相反，我想构建一个解释器逐渐建立大约唯一的哈希值，尽可能避免重新计算并保证不太可能发生冲突。
例如，可以使用其值的 MD5 递归地扩展解释器操作的每个对象，或者，如果它是复合对象，则使用其组件散列的 MD5。环境可以存储其每个变量/值条目的散列，并且环境的散列可以被计算为各个散列的函数。然后，如果环境中的条目发生变化，则无需重新遍历整个环境来计算环境的新哈希。相反，仅需要重新计算已更改的变量/值对的哈希，并且需要更新条目哈希集的全局哈希。
是否存在关于逐步构建近似唯一散列的相关工作，特别是在递归记忆和/或程序评估的背景下？
请注意，如果表达式是不可变的（不允许自修改代码），那么您可以对它们使用 EQ 相等。如果环境是不可变的，你可以同样对待它们。 EQ 相等速度很快，因为您只需将机器指针中的位作为哈希值。
问题是赋值会改变环境，导致表达式值发生变化。如果允许的话，该如何处理。
一种方法是记下在其词法范围内包含破坏性代码的环境，并以某种方式对它们进行注释，以便评估器可以识别此类“受污染的环境”，而不会对它们进行缓存。
顺便说一句，您显然需要具有弱语义的哈希表，以便任何成为垃圾的对象都不会堆积在内存中。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
