草绘利弊细胞

为了更好地理解 conses 和列表的语义,经常使用这种结构的图形表示。cons 单元通常用两个接触的盒子表示,它们包含指向 carcdr 值的两个箭头,或者直接指向值。例如,结果:

(cons 1 2)   
;; -> (1 . 2)

可以用以下图纸之一表示:

请注意,这些表示纯粹是概念性的,并不表示值包含在单元格中或从单元格指向的事实 :通常这取决于实现,值的类型,优化级别等在本例的其余部分中,我们将使用第一种绘图,这是一种更常用的绘图。

所以,例如:

(cons 1 (cons 2 (cons 3 4)))   ; improper `dotted` list
;; -> (1 2 3 . 4)

表示为:

而:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))  ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)

表示为:

这是一个树状结构:

(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4)         ; note the printing as an improper list

最后一个示例显示了这种表示法如何帮助我们理解语言的重要语义方面。首先,我们编写一个类似于前一个的表达式:

(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)

可以通常的方式表示为:

然后,我们编写一个不同的表达式,这显然与前一个表达式相同,这似乎通过结果的打印表示来确认:

(let ((cell-a (cons 1 2)))
  (cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)

但是,如果我们绘制该图中,我们可以看到的是,表达的语义是不同的,因为相同的细胞是值两者car 部和外 conscdr 部分(这是,cell-a 被的共享 ):

并且可以通过以下测试验证两个结果的语义在语言级别上实际上不同的事实:

(let ((c1 (cons (cons 1 2) (cons 1 2)))
      (c2 (let ((cell-a (cons 1 2)))
            (cons cell-a cell-a))))
  (list (eq (car c1) (cdr c1))
        (eq (car c2) (cdr c2)))
;; -> (NIL T)

第一个 eq 是*假的,因为 c1carcdr 在结构上相等( equal 确实如此 ),但不是相同(即相同的共享结构),而在第二次测试中结果是真的,*因为 c2carcdr相同的,即它们是相同的结构