33

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

4

5 回答 5

33

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

其次，术语“S-表达式”指的是语法- (items like this (possibly nested))。这样的 S 表达式是列表在 Lisp 源代码中的表示，但从技术上讲，它本身并不是列表。这种区别与十进制数字序列与其数值之间的区别，或者引号内的字符序列与结果字符串之间的区别相同。

这可能是一个过于技术性的区别。程序员经常引用值的文字表示，就好像它们就是值本身一样。但是对于 Lisp 和列表，事情变得有点棘手，因为Lisp 程序中的所有内容在技术上都是一个列表。

例如，考虑这个表达式：

(+ 1 2)

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

然而，在 Lisp 程序中，这样的列表将被解释为+以 1 和 2 作为参数的函数调用。（请注意，如此解释的是list，而不是S-expression；评估者是已由读者预先解析的列表，而不是源代码文本。）

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

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

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

当然，代码和数据的等价性是 Lisp 最酷的事情之一，所以区别是流动的。但我的观点是，虽然以上所有都是 S 表达式和列表，但在随意的 Lisp 语言中，只有一些会被称为“列表”。

于 2012-05-27T02:09:09.047 回答
16

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

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

  • 像FOO和这样的符号BAR
  • 以 s 表达式作为其第一个和第二个元素的cons 单元格：( 表达式-1 . 表达式-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 表达式编写的。

此处对此进行了描述：McCarthy, Recursive Functions of Symbolic Expressions

如今，在像 Common Lisp 这样的 Lisp 编程语言中，s 表达式有更多的语法并且可以编码更多的数据类型：

  • 符号：symbol123,|This is a symbol with spaces|
  • 数字：123, 1.0, 1/3, ...
  • 字符串："This is a string"
  • 人物：#\a,#\space
  • 矢量图：#(a b c)
  • 缺点和列表：( a . b ),(a b c)
  • 评论： ; this is a comment,#| this is a comment |#

和更多。

列表

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

旁注：程序和表格

在像 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 表达式在外部写入。

于 2012-05-27T04:55:14.573 回答
7

您应该首先了解 Lisp 的主要功能 - 程序可以作为数据进行操作。与其他语言（如 C 或 Java）不同，您使用特殊语法（{、、、、}等）编写程序class，define在 Lisp 中，您将代码编写为（嵌套）列表（顺便说一句，这允许直接表达抽象语法树）。再说一遍：你编写的程序看起来就像语言的数据结构。

当你把它说成数据时，你称之为“列表”，但当你谈到程序代码时，你最好使用术语“s-expression”。因此，从技术上讲，它们是相似的，但在不同的上下文中使用。混合这些术语的唯一真正地方是元编程（通常与宏一起使用）。

另请注意，s 表达式也可能包含唯一的原子（如数字、字符串等）。

于 2012-05-27T02:19:35.497 回答
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)))))
于 2014-03-15T21:34:14.087 回答
0

两者的写法类似：（blah blah blah），可能是嵌套的。有一个区别 - 列表以撇号为前缀。

关于评价：

  • S 表达式返回一些结果（可能是原子或列表或 nil 或其他）
  • 列表返回列表

如果需要，我们可以将列表转换为 s-exp，反之亦然。

  • (eval '(blah blah blah)) => list 被视为 s-exp 并返回结果。
  • (quote (blah blah blah)) => sexp 被转换为列表并且列表返回而不评估

国际会计准则：

  • 如果将 List 视为数据，则称为 List，如果将其视为代码，则称为 s-exp。
于 2012-05-29T16:05:11.010 回答