在Clojure中,不能在库级别有效地实现单元格吗？

Question

Clojure有自己的系列,不需要传统的lispy cons细胞.但我发现这个概念很有意思,它被用在一些教材中(例如,SICP).我一直想知道这个cons原语是否需要是原始的.我们不能在库中实现它(以及在其上运行的传统功能)吗？我搜索过,但是我发现没有写过这样的库.

Answer 1

Cons单元格是Lisp中用于s表达式的重要构建块.例如,参见McCarthy关于Lisp的各种出版物和1958年以后的符号表达式(例如符号表达式的递归函数).Lisp中的每个列表都由cons单元组成.

使用cons单元作为库来实现链表(和树,...)绝对是可能的.但是对于Lisp来说,它们是如此重要,以至于它需要早期并且实现非常有效.

在Lisp系统中,通常存在许多缺点单元和分配新缺陷单元的高速率(称为consing).因此,Lisp的实现者可能希望优化其Lisp实现:

• 小尺寸的cons细胞 - >不超过两个机器字,一个字用于汽车,一个字用于cdr
• 快速分配新的利弊细胞
• 有效的垃圾收集细胞(找到不再使用的cons细胞非常快)
• 直接在cons单元中存储原始数据(数字,字符......) - >没有指针开销
• 优化Lisp数据的局部性,例如cons单元结构(列表,关联列表,树,......),例如通过使用生成/复制垃圾收集器和/或内存区域来构建cons单元

因此,Lisp系统使用各种技巧来实现这一目标.例如,指针可以编码,如果它们指向cons单元格 - 因此cons单元本身不需要类型标记.Fixnums具有非常少的标记位并且适合cons细胞的CAR或CDR.在MIT Lisp机器上,系统还具有省略cons单元的CDR部分的功能,当它是线性列表的一部分时.

为了实现所有这些优化目标,通常需要在汇编程序和/或C中手动调整Lisp运行时的实现.Lisp处理器或Lisp VM通常将提供CAR,CDR,CONS,CONSP,......作为机器指令.

但是在这样的Lisp实现之外,它显然可以将cons单元实现为库 - 具有更差的空间和时间效率.

边注

Maclisp有超过两个名为Hunks的插槽