什么是 S 表达式

2024-05-18

所有 Lisp 开发人员似乎都知道什么是 S 表达式。但有人能为非 Lisp 开发者解释一下这一点吗?

已经有一个维基百科条目(https://en.wikipedia.org/wiki/S-expression https://en.wikipedia.org/wiki/S-expression)。但如果您不想深入了解细节,那么这并没有多大帮助。

什么是 S 表达式?我可以用 S-Expression 表达什么? Lisp 通常使用 S 表达式的目的是什么? S 表达式只与 Lisp 开发人员相关吗?


S 表达式是 Lisp 中的基本存储单元。根据最初的定义,S 表达式是以下两种情况之一。

  • 一个原子,或
  • 一个缺点细胞

原子是基本情况。在经典 Lisp(约翰·麦卡锡提出的原始语言)中,原子只是一个独特的单位,我们通常用名称来指定它。从概念上讲,您可以将其视为一个字符串,尽管这不是任何现代 Lisp 内部存储它的方式。所以foobar是一个原子,所以也是potato。它们只是字符串atomic,从某种意义上说,它们不再递归地包含任何更多的 S 表达式。

请注意,现代 Lisp 方言扩展了“原子”的定义以包括数字等内容,因此在 Common Lisp 中,1.0将是代表数字的有效原子。

cons 单元是 Lisp 中组成的基本单位。 cons 单元是指向另外两个 S 表达式的结构。我们将这些 S 表达式中的第一个称为car第二个是cdr。这些名称很古老,最初是指 cons 单元在旧计算机上的存储方式,但如今 Lisp 程序员仍在使用它们。你会听到一些人提到car作为“第一个”或“头”,你会听到有些人提到cdr作为“尾巴”或“休息”。 (尽量不要将 cdr 称为“第二个”术语,因为这是不明确的,并且可能被解释为其他内容,我们稍后会讨论)

Now, we write括号中的 cons 单元格之间有一个点。因此,汽车和 cdr 都是原子的 cons 单元看起来像

(foo . bar)

这是一个细胞,其汽车是原子foo其 cdr 是原子bar。我们还可以嵌套 con 单元格。

((foo . bar) . (baz . potato))

然后我们最终得到一种类似二叉树的结构,其中每个分支都有一个左分支和一个右分支(用我们的术语来说是一辆汽车和一个 cdr),每个叶子都是一个原子。

那么我们能用这个做什么呢?嗯,一方面,我们可以存储链接列表。有多种方法可以做到这一点,但 Lisp 社区的流行惯例是使用 car 来存储当前值,并使用 cdr 来存储指向列表其余部分的 cons 单元。然后,当我们到达列表的末尾时(我们可能存储一个null指针(如果我们在 C 或 Java 中执行此操作),我们会挑选一个特定的原子,称为NIL。没什么特别的NIL上述定义中的原子;我们只是挑选了一个,因为我们需要一个作为约定。

所以代表列表[a, b, c, d],我们将其存储为

(a . (b . (c . (d . NIL))))

最外面的 cons 单元的汽车是列表的第一个元素,或者a。 cdr 存储列表的其余部分。 cdr的车是第二个元素,b, 等等。 (这就是为什么我说不要将 cdr 称为“第二”元素,因为“第二”通常用来表示“cdr 的汽车”)

事实上,我们经常这样做,以至于 Lisp 中还有另一种符号约定。如果 cdr 是另一个 cons 单元,那么我们只需删除.和括号并理解其含义。所以,一般来说,对于任何 S 表达式,我们说以下两个是等价的a, b, and c.

(a . (b . c)) === (a b . c)

再说一次,我没有改变定义。仍然只有两个有效的 S 表达式:原子和 cons 单元。我刚刚发明了一种更紧凑的方式来编写它们。

同样,由于我们将使用NIL有很多要结束的清单,我们只是将其删除。如果我们有一个NIL作为 cons 单元的 cdr,那么按照惯例,我们删除.NIL。因此以下对于任何 S 表达式都是等价的a.

(a . NIL) === (a)

再说一次,我只是发明新的、紧凑的方式来编写东西,而不是改变定义。

最后,为了符号方便,我们有时可能会写成原子NIL作为一对空括号,因为它应该看起来像空列表。

NIL === ()

现在,看看我们之前的清单

(a . (b . (c . (d . NIL))))

我们可以使用这些规则来简化它

(a . (b . (c . (d . NIL))))
(a b . (c . (d . NIL)))
(a b c . (d . NIL))
(a b c d . NIL)
(a b c d)

现在这看起来非常像 Lisp 语法。这就是 S 表达式的美妙之处。你的 Lisp 代码writing只是一堆S表达式。例如,考虑以下 Lisp 代码

(mapcar (lambda (x) (+ x 1)) my-list)

这是普通的 Lisp 代码,是您在任何日常程序中都会看到的类型。在 Common Lisp 中,它为每个元素加一my-list。但美妙之处在于它只是一个大S表情。如果我们删除所有语法糖,我们会得到

(mapcar . ((lambda . ((x . NIL) . ((+ . (x . (1 . NIL))) . NIL))) . (my-list . NIL)))

不漂亮,至少在美学上是这样,但现在更容易看出这实际上只是一堆终止于原子的细胞。整个 Lisp 语法树就是这样:一个充满代码的二叉树。你可以这样操纵它。您可以编写将这棵树作为数据结构的宏,并用它做任何他们想做的事情。 Lisp 程序的抽象语法树并不是该语言内部的某种不透明结构;它是一种语言内部的抽象语法树。它只是一棵树:一种极其简单的数据结构,无论如何,您已经在日常编程中使用了它。在 Lisp 程序中用于存储数据的列表和其他结构也用于存储代码。

现代 Lisp 方言通过新的约定以及在某些情况下的新数据类型扩展了这一点。例如,Common Lisp 添加了一个数组类型,因此#(1 2 3 4 5) is an array的五个元素。它不是一个链表(因为实际上,链表对于随机访问来说很慢),它完全是另一回事。同样,Lisp 方言在基础上添加了新的约定NIL我们已经讨论过了。在大多数 Lisp 方言中,撇号或单引号用于表示对quote特殊形式。那是,

'x === (quote x) (quote . (x . NIL))

对于任何 S 表达式x。不同的方言为原始的 McCarthy 定义添加了不同的功能,但核心概念是:我们需要能够舒适地存储代码的绝对最小定义是什么and我们的 Lisp 程序的数据。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

什么是 S 表达式 的相关文章

  • Common Lisp 中的属性列表是否引用某些全局状态?

    下面的代码有z作为局部变量 但它的行为就像全局变量一样 defun foo m let z stuff nil push m getf z stuff print z foo 1 foo 2 foo 3 我希望输出是 STUFF 1 STU
  • 了解 LISP 中的绑定变量和自由变量

    我正在阅读SICP 又出现了绑定变量和自由变量的话题 然而 我对此感到困惑 术语 绑定变量 仅适用于形式参数变量吗 此外 文本还指出过程定义 绑定 其形式参数 这让我感到困惑 因为有些人说我们将值 绑定 到变量 显然 当我们谈论不同类型的变
  • 如何理解clojure的lazy-seq

    我正在尝试理解 Clojurelazy seq运算符 以及惰性求值的一般概念 我知道这个概念背后的基本思想 表达式的求值被延迟 直到需要该值为止 一般来说 这可以通过两种方式实现 在编译时使用宏或特殊形式 在运行时使用 lambda 函数
  • 防止 LISP 中的终端输出

    我想运行一个函数 但不让它在终端中输出结果 例如 set A B 正常返回B在控制台中如下所示 gt gt gt set A B B gt gt gt A B 我不希望它返回任何东西 我仍然希望该函数能够完成它应该做的事情 只是默默地 gt
  • 为什么在绘制 API 中,origin 通常位于左上角,而逻辑上本机 GL 位于左下角?

    我注意到很多绘图 API 的 0 0 原点位于左上角 因此 y 实际上随着增加而下降 我想知道这是为什么 不工作在我个人认为更符合逻辑的左下角 常规 x y 网格的原点 也恰好是硬件渲染 API 中坐标的本机表示 有什么特别的优势吗 或者它
  • CLISP - 反转简单列表

    我必须反转简单 单维 列表的元素 我知道有一个内置的反向函数 但我不能用它来做这个 这是我的尝试 defun LISTREVERSE LISTR cond lt length LISTR 2 LISTR listr is 1 atom or
  • Common Lisp 中的(随机)不那么随机?

    好的 最后一个问题 我将用 Common Lisp 完成我的猜数游戏 D 每当游戏开始 或者在第一个游戏之后开始新游戏 时 都会调用以下函数 Play the game defun play If it s their first time
  • 在 Lisp 解释过程中,“读者”的任务是什么?

    我想知道 读者 在解释 编译 Lisp 程序期间的目的 或者更准确地说 是 读者 的任务 从我刚刚完成的问题前研究来看 在我看来 读者 特别是本例中的 Clojure 可以被视为 语法预处理器 它的主要职责是读取器宏和原始形式的扩展 所以
  • 为什么在基于 Lisp 的语言中习惯上将许多右括号放在一行上?

    通常代码如下所示 one thing another thing arg1 f arg5 r another thing arg1 f arg5 r 为什么不喜欢这样 one thing another thing arg1 f arg5
  • 在 Java Runtime.getRuntime().exec(...) 中使用引号和双引号

    我正在尝试在 Mac OSX 中从 Java 启动 Lisp 映像 使用控制台中的图像 我输入以下内容 lisp image eval package method some argument 一切都运行良好 在Java中 我在使用传递引号
  • 在我的 Linux 机器上安装 lisp

    我使用 Vim 作为我的编辑器 Practical common Lisp 建议安装 Lispbox 我不知道如何使用 emacs 不知道如何用那个 T T 运行 lisp 代码 之后我找到了一个名为 limp vim 的 vim lisp
  • 为什么 LISP 中符号名称中的连字符是约定俗成的?

    这个推荐的理由是什么 为什么不与使用下划线的其他编程语言保持一致 我认为 LISP 使用连字符有两个原因 历史 和 因为你可以 History LISP 是一种古老的语言 在早期输入下划线可能会很困难 例如 我用于 LISP 的第一个终端是
  • 解决斐波那契数列的 Lisp 方法

    我想尝试学习 Lisp 但很快就放弃了 我想我会再试一次 我正在看 求 400 万以下所有偶数斐波那契数的总和 我写了下面的代码 它可以工作 但是很丑陋 其中最主要的是它太慢了 因为它一直在进行简单的递归 当我用 Python 编写这个程序
  • 从when语句内的函数返回

    我想做的就是使用 when 语句返回一个值 我想要以下功能 if x return y 我正在尝试使用 when x y 但是when语句并没有以退出函数并返回y的方式进行计算 它只是愉快地继续下一行 有没有办法做到这一点而不需要制作一个看
  • 如何说服 Lisp SBCL 进行内联 Fixnum 算术?

    我在其他 SO 答案中找到了一些技术 但显然我无法说服 SBCL 进行内联修复数算术 declaim optimize speed 2 safety 1 declaim ftype function fixnum fixnum double
  • 递归分割列表函数 LISP

    split list 函数接受一个列表并返回一个由两个列表组成的列表 其中两个列表由输入的交替元素组成 我写了以下内容 defun split list L cond endp L list NIL NIL t let X split li
  • 我为什么要学习 Lisp? [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi
  • Lisp:使用语法糖访问递归哈希

    我正在尝试构建一个函数 或宏 来简化哈希表深处数据的获取和设置 也就是说 哈希中的哈希 哈希中的哈希等 我不认为我可以用宏来做到这一点 而且我不知道如何用 eval 来做到这一点 我希望能够执行以下操作 gethashdeep HEROES
  • 如何在 Lisp 中生成一系列佩尔数而不是特定的数

    如何使用 cons 或其他方式打印列表佩尔数 https en wikipedia org wiki Pell number直到第N个数 defun pellse k if or zerop k k 1 k 2 pellse k 1 pel
  • Common Lisp 中的原子和 Clojure 中的原子有什么区别?

    下列page http clojure org atoms讨论原子在 Clojure 中的工作原理 它并没有详细说明 Clojure 和其他 lisp 方言中原子之间的差异 Common Lisp 中的原子和 Clojure 中的原子之间的

随机推荐