“hash cons”是什么意思?

把每个人的答案放在一起:

ACL2(一种应用公共Lisp的计算逻辑)是一个由编程语言、一阶逻辑中的可扩展理论和机械定理证明器组成的软件系统。

—— Wiki ACL2

在计算机编程中,cons(发音为/203;_k_nz/或/203;_k_ns/)是Lisp编程语言大多数方言中的基本功能。cons构造(因此得名)内存对象,其中包含两个值或指向值的指针。这些对象被称为(cons)单元、conses或(cons)对。在Lisp术语中,“to cons x to y”表示用(cons x y)构造一个新对象。结果对有一个左半部分,称为汽车(第一个元素),右半部分(第二个元素),称为CDR。

—— Wiki Cons

从逻辑上讲,hons只是cons的另一个名称,即下面是一个acl2定理:

(等于(hons x y)(cons x y))

荣誉通常比缺点运行得慢,因为在创建一个荣誉时,试图看看一个荣誉是否已经存在于同一辆车和CDR中。这涉及到搜索和哈希表的使用。

—— http://www.cs.utexas.edu/~moore/acl2/current/HONS.html

考虑到你的问题:

对某些类进行哈希运算,并将其实例与引用相等进行比较

看来 hash cons 对Lisp构造函数进行哈希处理以通过相等比较确定对象是否已存在的过程。

来自奥德斯基、斯彭和维纳(2007年) scala编程 ,Artima出版社,第243页:

通过缓存在弱集合中创建的所有实例,可以散列类的cons实例。然后,每当需要类的新实例时,首先检查缓存。如果缓存中已有一个元素与要创建的元素相同,则可以重用现有实例。由于这种安排,任何两个等于equals()的实例也等于引用相等。

http://en.wikipedia.org/wiki/Hash_cons 现在重定向。

它是 con s 允许哈希 eq (参考)比较而不是深入的比较。这对内存更有效(因为相同的对象存储为引用),当然,如果比较是一种常见操作,则速度更快。

http://www.cs.utexas.edu/~moore/acl2/current/HONS.html 描述Lisp的实现。