Lisp:list vs S-expression

Question

我现在正在学习Lisp.我遇到了两个术语"列表"和"S表达式".我只是无法区分它们.它们只是Lisp中的同义词吗？

Answer 1

首先,并非所有S表达式都代表列表; 诸如foobar表示裸原子的表达式也被认为是S表达式.正如"cons"语法一样,(car . cons)当"cons"部分本身不是另一个列表(或nil)时使用.更熟悉的列表表达式,例如(a b c d),只是嵌套cons单元链的语法糖; 那个例子扩展为(a . (b . (c . (d . nil)))).

其次,术语"S表达式"是指语法 - (items like this (possibly nested)).这样的S-expression为表示在一个列表中的Lisp的源代码,但它不是技术上的列表本身.这种区别与十进制数字序列及其数值之间的区别,或引号内的字符序列与结果字符串之间的区别相同.

这可能是一种过于技术性的区别; 程序员通常会将值的文字表示称为值本身.但是使用Lisp和列表,事情变得有点棘手,因为Lisp程序中的所有内容在技​​术上都是一个列表.

例如,考虑以下表达式:

(+ 1 2)

上面是简单的S-表达其表示的平面列表,由原子+,1和2.

但是,在Lisp程序中,这样的列表将被解释为对+函数的调用,其中1和2作为参数.(请注意,这是如此解释的列表,而不是S表达式 ;评估者是已经由读者预先解析的列表,而不是源代码文本.)

因此,虽然上面的S表达式代表一个列表,但它很少在Lisp程序的上下文中被称为 "列表".除非讨论宏,或者读者的内部工作,或者由于某些其他代码生成或解析上下文而进行了一次metasyntactic讨论,否则典型的Lisp程序员会将上述内容视为数值表达式.

在另一方面,任何可能的以下S-表达式将被称为"列表",因为他们评估作为Lisp代码将产生由上述文字S-表达作为运行时的值表示的列表中:

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

当然,代码和数据的等价性是Lisp的一个很酷的东西,所以区别是流动的.但我的观点是,尽管以上所有都是S表达式和列表,但只有一些在随意的Lisp中被称为"列表".

Answer 2

S表达式是数据的表示法.

历史上,s表达式(符号表达式的简称)被描述为:

• 像FOO和的符号BAR
• 利用s表达式作为其第一和第二元素来构建细胞:( 表达-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表达式编写的.

这里描述:麦卡锡,符号表达式的递归函数

在像Common Lisp这样的Lisp编程语言中,s-expressions有更多的语法,可以编码更多的数据类型:

• 符号: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表达式.

Answer 3

您应该首先了解主要的Lisp功能 - 程序可以作为数据进行操作.不像其他语言(如C或Java),其中通过使用特殊的语法(写程序{,},class,define,等),在Lisp语言编写代码(嵌套)名单(顺便说一句,这允许表达抽象语法树直接).再一次:你编写的程序看起来就像语言的数据结构.

当你把它称为数据时,你称之为"列表",但是当你谈论程序代码时,你最好使用术语"s-expression".因此,从技术上讲它们是相似的,但在不同的环境中使用.这些术语混合的唯一真正的地方是元编程(通常使用宏).

还要注意,s表达式也可能由唯一的原子组成(如数字,字符串等).