14

I'm trying to emulate Lisp-like list in JavaScript (just an exercise with no practical reason), but I'm struggling to figure out how to best represent an empty list.

Is an empty list just a nil value or is it under the hood stored in a cons cell?

I can:

(car '())
NIL
(cdr '())
NIL

but an empty list for sure can not be (cons nil nil), because it would be indistinguishable from a list storing a single nil. It would need to store some other special value.

On the other hand, if an empty list is not built from a cons cell, it seems impossible to have a consistent high-level interface for appending a single value to an existing list. A function like:

(defun append-value (list value) ...

Would modify its argument, but only if it is not an empty list, which seems ugly.

4

4 回答 4

15

信不信由你，这实际上是一个宗教问题。

人们敢于将某些方言称为某种 Lisp，其中空列表是某种组合或聚合对象，而不仅仅是像nil.

例如，在“MatzLisp”（更广为人知的 Ruby）中，列表实际上是数组。

在 NewLisp 中，列表是容器：列表类型的对象，其中包含项目的链表，因此空列表是空容器。[参考]。

在不是这种壮观的集群摸索的 Lisp 语言中，空列表是原子，非空列表是二进制单元格，其中一个字段保存第一项，另一个字段保存列表的其余部分。列表可以共享后缀。给定一个(1 2 3)我们可以cons用来创建的列表，(a 1 2 3)并且(b c 1 2 3)两者都共享(1 2 3).

（在 ANSI Common Lisp 中，空列表原子()与 symbol 是相同的对象nil，它对自身求值并且也用作布尔 false。在 Scheme 中，()不是符号，并且与 Boolean false#f对象不同。但是 Scheme 列出仍然由对组成，并由一个原子终止。）

评估的能力(car nil)不会自动从列表的 cons-and-nil 表示中得出，如果我们查看古老的 Lisp 文档，例如 1960 年初的 Lisp 1.5 手册，我们会发现这是不存在的。最初，car严格来说是访问 cons 单元格字段的一种方式，并且严格要求有一个 cons 单元格参数。

(car nil)像允许Just Work（这样黑客可以从他们的程序中删除许多无用的代码行）这样的好主意并不是一夜之间出现的。允许的想法(car nil)可能是从 InterLisp 中出现的。不管怎样，Evolution Of Lisp论文声称 MacLisp（Common Lisp 的重要前身之一，与 20 年后出现的 Apple Macintosh 无关）模仿了 InterLisp（另一个重要的前身之一）的这一特性。

像这样的小细节决定了愉快的编程和对监视器发誓之间的区别：例如，参见A Short Ballad Dedicated to the Growth of Programs，灵感来自于一个 Lisp 程序员与一种无法访问空列表的无礼方言的斗争car，并且不要用作布尔值 false。

于 2013-05-18T05:20:27.480 回答
15

空列表只是nil符号（根据定义，符号不是 conses）。如果给定car，cdr则定义为返回。nilnil

至于列表变异函数，它们返回一个您应该重新分配给变量的值。例如，查看nreverse函数的规范：它可能会修改给定的列表，也可能不会，并且您应该使用返回值，而不是依赖它来就地修改。

甚至nconc，典型的破坏性附加函数也是这样工作的：它的返回值是你应该使用的附加列表。它被指定在原地修改给定的列表（除了最后一个），但如果你把它nil作为第一个参数，它不能很好地修改它，所以你仍然必须使用返回值。

于 2013-05-17T10:15:53.520 回答
4

NIL在 Common Lisp 中有点奇怪，因为

  • 它是一个符号（意味着symbolp返回T）
  • 是一个列表
  • 不是一个缺点单元格（consp返回NIL）
  • 无论如何你都可以接受CAR它CDR

请注意，这背后的原因可能也是历史原因，您不应认为这是唯一合理的解决方案。其他 Lisp 方言做出了不同的选择。

于 2013-05-18T05:58:15.170 回答
2

用你的 Lisp 解释器试试：

(eq nil '())
=> t

nil在对/ 空列表进行操作时，一些操作是特殊情况下执行非正交（甚至是好奇:-) 的事情。你正在调查的行为就是car其中之一。cdr

作为空列表的nil身份是您了解 Lisp 的第一件事。我试图想出一个很好的谷歌点击，但我会选择一个，因为有很多：http ://www.cs.sfu.ca/CourseCentral/310/pwfong/Lisp/1/tutorial1.html

于 2013-05-17T10:07:03.553 回答