Lisp: 列表 vs S-表达式

Question

我是Lisp的新手。我遇到了两个术语“列表”和“S表达式”。我只是无法区分它们。它们在Lisp中只是同义词吗？

我是Lisp的新手。我遇到了两个术语"列表"和"S表达式"。我不知道如何区分它们。它们在Lisp中是同义词吗？

- Dagang

---

更多信息请参阅C2关于sexprs的维基。 - Asherah

Answer 1

首先，不是所有的S表达式都表示列表；例如表达式foobar表示一个原子，也被认为是一个S表达式。当“cons”部分本身不是另一个列表（或nil）时，“cons cell”语法(car . cons)也是一种S表达式。更常见的列表表达式，例如(a b c d)，只是一系列嵌套的cons单元的语法糖；该示例展开为(a . (b . (c . (d . nil))))。

其次，“S表达式”一词指的是语法 - (像这样的项（可能嵌套）)。这样的S表达式是Lisp源代码中列表的表示形式，但它本质上并不是一个列表。这种区别类似于十进制数字序列和它们的数值之间的区别，或者在引号内的字符序列和生成的字符串之间的区别。

这可能是一个过于技术化的区别；程序员经常像它们本身的价值一样引用值的文字表示。但是对于Lisp和列表，情况会变得有点棘手，因为Lisp程序中的每一件事情本质上都是一个列表。

例如，请考虑以下表达式：

(+ 1 2)

以上是一个简单的S表达式，表示一个扁平列表，由原子+、1和2组成。

但是，在Lisp程序中，这样的列表将被解释为调用+函数并以1和2作为参数。（请注意，被解释的是列表而不是S表达式；求值器接收到预先由阅读器解析的列表，而不是源代码文本。）

因此，虽然上述S表达式表示一个列表，但在Lisp程序的上下文中很少被称为“列表”。除非讨论宏或者阅读器的内部工作，或者因为其他生成代码或解析上下文而进行元语言讨论，否则典型的Lisp程序员通常会将上面的内容视为数字表达式。

另一方面，下列任何一个S表达式可能会被称为“列表”，因为将它们作为Lisp代码进行求值将产生由上面文字表示的列表作为运行时值：

'(+ 1 2)
(quote (+ 1 2))
(list '+ 1 2)

当然，代码和数据等价是 Lisp 的一大优点，因此区分是流动的。但我的观点是，虽然上述所有内容都是 S 表达式和列表，但只有一些在 Lisp 中的非正式说法中被称为“列表”。

- Mark Reed

---

列表是一个包含NIL哨兵的cons单元链。这就是全部。reader将文本转换为S表达式——在LISP中，一切都是S表达式——它可以是原子或者cons单元（向量是原子等等）。该读取器不尝试验证eval的参数。 - Will Ness

S表达式不会被读取器输出。"S表达式"是指带有括号等符号的文本表示形式。当读取器完成它的工作时，它已经不再是一个S表达式，而是一个实际的内存列表 - 就是你提到的那个"带有nil哨兵的cons单元链"。 - Mark Reed

Answer 2

S-表达式是一种数据的符号表示法。

历史上，s-表达式（符号表达式的缩写）被描述为：

• 符号，例如FOO和BAR
• cons cell，其中s表达式作为第一个和第二个元素：( expression-1 . expression-2 )
• 列表终止符NIL
• 一种写列表的约定：( A . ( B . NIL ) ) 简单地写成列表(A B)

还要注意的是，历史上程序文本的书写方式有所不同。下面是函数ASSOC的示例。

assoc[x;y] =
   eq[caar[y];x] -> cadar[y];
   T -> assoc[x;cdr[y]]

历史上，也存在将这些m表达式（简称元表达式）映射到s表达式的方法。今天，大多数Lisp程序代码都是使用s表达式编写的。

这在这里描述：麦卡锡，《符号表达式的递归函数》 在像Common Lisp这样的Lisp编程语言中，s表达式具有更多的语法，并且可以编码更多的数据类型：

- 符号：symbol123，| 这是一个带空格的符号 | - 数字：123，1.0，1/3，... - 字符串："This is a string" - 字符：#\a，#\space - 向量：#(a b c) - Conses和lists：（a.b），（a b c） - 注释：;这是一个注释，#| 这是一个注释 |#

等等。

列表

列表是一种数据结构。它由cons单元和列表结束标记组成。在Lisp中，列表具有作为s表达式列表的表示法。您可以使用其他符号表示法来表示列表，但在Lisp中，人们已经确定了使用s表达式语法来编写它们。

附注：程序和形式

在像Common Lisp这样的编程语言中，编程语言的表达式不是文本，而是数据！这与许多其他编程语言不同。 Common Lisp编程语言中的表达式称为Lisp forms。

例如，函数调用是Lisp数据，其中调用是具有函数符号作为其第一个元素的列表，而下一个元素是其参数。

我们可以将其写为（sin 3.0）。但它确实是数据。我们也可以构造数据。

评估Lisp形式的函数称为EVAL，并且它采用Lisp数据，而不是程序文本或程序文本的字符串。因此，您可以使用返回Lisp数据的Lisp函数构建程序：（EVAL（LIST 'SIN 3.0））评估为0.14112。

由于Lisp表单具有数据表示，因此通常使用Lisp的外部数据表示来编写它们 - 这是什么？ - s表达式！

它是s表达式。 Lisp表单作为Lisp数据以s表达式的形式外部编写。

- Rainer Joswig

---

S表达式先出现了。它们从来不是程序员看到的，而是一种中间表示形式。但是，要想出顶层表示形式M表达式花费了一段时间，而且团队并不太满意。到那个时候，每个人都已经决定喜欢原样的S表达式。因此，即使从历史上看，始终都是S表达式为主；至多，M表达式只是一个脚注。 - Mark Reed

@Mark Reed：麦卡锡1960年的论文描述了符号表达式和元表达式。 - Rainer Joswig

没错，@rainerjoswig。我想我记错了。感谢您的纠正。 - Mark Reed

你说“带有表达式的cons单元格...”，难道不应该是“带有s表达式的cons单元格...”吗？ - day

当你写下 "expression-1 . expression-2" 时，你是否实际上是想表达 ".. s-expression-1 . s-expression-2"？ - Elliptical view

Answer 3

你首先需要了解 Lisp 的主要特点 - 程序可以作为数据进行操作。与其他语言（如 C 或 Java）不同，在 Lisp 中，您编写代码时使用的是（嵌套的）列表，而不是特殊语法（例如 {，}，class，define等）。顺便说一下：这使得可以直接表示 抽象语法树。再次强调：您编写的程序看起来就像语言的数据结构一样。

当您将其视为数据时，称其为“列表”，但当您谈论程序代码时，最好使用术语“s表达式”。因此，从技术上讲，它们是相似的，但在不同的上下文中使用。这些术语混合在一起的唯一真正场所是元编程（通常使用宏）。

还要注意，s表达式也可以由唯一的原子（如数字、字符串等）组成。

- ffriend

---

s表达式在历史上并不是程序代码，而是一种数据表示法。列表是一种数据结构。请参阅麦卡锡关于Lisp的原始论文。 - Rainer Joswig

@ffriend：当然，mapcar适用于列表。不，eval不能处理s表达式。它可以处理表示为数据的Lisp形式。 - Rainer Joswig

@RainerJoswig：数据_本身不能_by definition_表达_任何东西，它们是某个值的值，应该以某种方式进行表示。在内存中，有关Lisp形式的数据可以表示为嵌套的Lisp列表、其他类型的列表（不在这个Lisp本身中使用）、Java类实例的集合、Haskell中的代数数据类型层次结构或其他任何东西。在_source code(从问题中可以看出OP对Lisp语法感到困惑)中，Lisp形式被表示为文本，格式化为（具有）_s表达式_的符号。 - ffriend

@RainerJoswig：这仅适用于Common Lisp，但如果您关心，请将我的注释中的每个“source code”更改为“source file”，那么您应该就可以理解了。 - ffriend

除了术语纠结之外，这里的要点是 Lisp 中的 eval 函数不操作字符串，这与大多数现代动态语言中同名函数不同。相反，它期望其参数已经是内存中代码的表达方式，即（一棵分层嵌套的）列表树。读取器将 S 表达式转换为要求求值的列表。因此，S 表达式是列表的文本表示形式。实际上，它们被序列化，就像 JSON 或 XML 可以表示对象树一样。 - Mark Reed

Answer 4

一个S表达式的简单定义是：

(define S-expression?
    (λ (object)
        (or (atom? object) (list? object))))

;; Where atom? is:

(define atom?
  (λ (object) 
    (and (not (pair? object)) (not (null? object)))))

;; And list? is:

(define list? (λ (object)
  (let loop ((l1 object) (l2 object))
    (if (pair? l1)
        (let ((l1 (cdr l1)))
          (cond ((eq? l1 l2) #f)
                ((pair? l1) (loop (cdr l1) (cdr l2)))
                (else (null? l1))))
        (null? l1)))))

- dkinzer

Answer 5

两者的书写方式相似：（blah blah blah），可以嵌套。唯一的区别是列表以撇号为前缀。

在评估时：

• S表达式返回一些结果（可以是原子、列表、nil或其他任何东西）
• 列表返回列表

如果需要，我们可以将列表转换为S表达式，反之亦然。

• （eval'（blah blah blah））=>列表被视为S表达式，并返回结果。
• （quote（blah blah blah））=> sexp被转换为列表，并返回列表而不进行评估

IAS：

• 如果将列表视为数据，则称为列表；如果将其视为代码，则称为S表达式。

- Prabu

---

如果将列表视为数据，则称其为列表；如果将其视为代码，则称其为s-exp。在我的经验中，如果将列表视为数据，则称其为列表；否则，通常称其为函数调用。术语“s表达式”是专门用于以元文本方式讨论语法的。 - Mark Reed

"IME" = 依我个人经验 - Elliptical view