CS 61A Scheme 规范

最后更新：2022年春季

关于本规范

本课程使用的 Scheme 版本并不完全符合该语言的任何官方规范，尽管它可能最接近R5RS，并带有 一些来自其他版本（既有旧版本也有新版本）的功能和术语。我们 偏离官方规范有几个原因，包括易于实现（对于教职员参考实现和学生 完成 Scheme 项目而言）和易于教学。

本文档和链接的内置过程参考非常长， 试图形式化 61A 中使用的 Scheme 变体。课程讲义、实验和 讨论可能是学习该语言的更好资源。 然而，概述和术语部分可能 在你希望阅读该语言的更正式描述时有用。

你不应该觉得有必要阅读特殊形式和内置过程的完整参考， 但特定部分在从事 Scheme 作业和项目时可能有助于参考（相关部分通常会在作业本身中链接）。

一个已完成且正确的 Scheme 项目实现，包括所有 额外学分问题，应该与教职员解释器的功能匹配， 不包括错误追踪。

本文档主要关注基于 Python 的解释器。网页 解释器应该大致匹配其行为，但由于不同的宿主 语言和 Web 平台的约束，可能存在一些不一致之处，你可以提交问题。此外，网页解释器包含 几个额外功能，例如图表制作器和 JS 互操作性，这些功能在此处没有 文档说明。

概述和术语

表达式和环境

Scheme 通过在环境中求值表达式来工作。每个表达式 求值得到一个值。某些表达式是自求值的，这意味着 它们既是一个表达式也是一个值，并且它求值得到自身。

帧是从符号（名称）到值的映射，以及可选的 父帧。当前环境指的是当前帧，以及一直到全局帧的父帧链（它没有父帧）。当 在环境中查找符号时，Scheme 首先检查当前帧并 返回相应的价值（如果存在）。如果不存在，它会在每个后续父帧中重复此 过程，直到找到符号，或者 没有更多父帧可检查。

原子表达式

有几种原子或原始表达式。数字、布尔值、 字符串和空列表（nil）都是原子且自求值的。 符号是原子的，但不是自求值的（它们求值得到先前 在环境中绑定到它的 值）。

调用表达式

不是原子的 Scheme 表达式称为组合，并且 由一个或多个子表达式组成，用括号括起来。大多数形式 被求值为调用表达式，它有三个求值步骤：

1. 求值第一个子表达式（运算符），它必须求值得到一个 过程（见下文）。
2. 按顺序求值剩余的子表达式（操作数）。
3. 将步骤1中的过程应用于步骤2中的已求值操作数（参数）。

这些步骤反映了 Python 和其他语言中的步骤。

特殊形式

然而，并非所有组合都是调用表达式。有些是特殊形式。 解释器维护一组特定符号（有时称为 关键字），当它们是 第一个子表达式时，表示组合是一个特殊形式。每个特殊形式都有自己的过程来决定要求值哪些操作数以及 如何求值（如下所述）。解释器总是首先检查组合的 第一个子表达式。如果它匹配其中一个关键字，则使用相应的 特殊形式。否则，组合被求值为 调用表达式。

符号编程

Scheme 的核心数据类型是列表，如下文所述，由序对构建。 Scheme 代码实际上是由这些列表构建的。这意味着代码 (+ 1 2) 被构造为 + 符号、数字 1 和数字 2 的列表，然后被求值为调用表达式。

由于列表通常被求值为组合，我们需要一种特殊形式来 获取实际的、未求值的列表。quote 是一种特殊形式，它接受单个 操作数表达式并返回它，未求值。因此，(quote (+ 1 2)) 返回符号 +、数字 1 和数字 2 的实际列表， 而不是求值表达式以得到数字 3。这也适用于 符号。a 在当前环境中被查找以获取相应的 值，而 (quote a) 求值得到字面值符号 a。

因为 quote 在 Scheme 中非常常用，该语言有一种简写方式： 只需在你想保持未求值的表达式前面加上单引号。'(+ 1 2) 和 'a 分别等价于 (quote (+ 1 2)) 和 (quote a)。

杂项

与 R5RS 一样，61A Scheme 完全不区分大小写（字符串除外）。本 规范将在符号中使用小写字符，但相应的 大写字符可以互换使用。

值的类型

数字

数字建立在 Python 的数字类型之上，因此可以支持 任意大整数和双精度浮点数的组合。

网页解释器尽可能复制这一点，但可能偏离 基于 Python 的版本，因为不同的宿主语言以及需要 在浏览器中运行时要绕过 JavaScript 的怪异行为。

解释器的宿主语言中任何有效的实数字面量都应该被 正确读取。当浮点数字涉及任何计算或任何真除法时，你不应该指望一致的结果。

布尔值

有两个布尔值：#t 和 #f。Scheme 布尔值可以输入为 它们的规范形式 #t 或 #f，或者作为单词 true 或 false。

任何表达式都可以在布尔上下文中被求值，但 #f 是唯一为 假的值。所有其他值在布尔上下文中都被视为真。

2018年春季之前的一些解释器在输出布尔值时会显示单词 true 和 false， 但自此之后更新的任何解释器都不应该出现这种情况。

符号

符号在 Scheme 中用作标识符。有效符号由以下特殊字符的某种 组合和字母数字字符组成：

!$%&*/:<=>?@^_~+-.

所有符号应在内部存储为小写字母。符号必须不 构成有效的整数或浮点数。

字符串

与其他实现不同，61A Scheme 没有单个 字符的概念。字符串被视为具有自身权利的原子数据类型。字符串 可以作为双引号内的字符序列输入到解释器中， 某些字符（如换行符和双引号）需要转义。 作为一般规则，如果一段文本作为 JSON 键是有效的，它在 61A Scheme 中应该 作为字符串工作。与大多数其他 Scheme 实现相比， 61A Scheme 中的字符串是不可变的。

字符串行为的这些差异是由于宿主语言中字符串的状态造成的： Python 和 Dart 都有不可变的字符串，没有单个字符的概念。

由于基于 Python 的解释器对字符串用处不大，它缺乏对字符串操作的适当 支持。网页解释器需要字符串来实现 JS 互操作（除其他事项外），它支持 string-append 内置过程，它 接受任意数量的值或任何类型，并将它们组合成 一个字符串。额外的字符串操作可以通过 JS 互操作完成。

序对和列表

序对是由两个字段组成的内置数据结构，一个 car 和一个 cdr（有时也称为第一个和第二个，或第一个和其余部分）。第一个 值可以包含任何 Scheme 数据类型。然而，第二个值必须包含 nil、序对或流承诺。

nil 是 Scheme 中表示空列表的特殊值。它可以通过在解释器中输入 nil 或 () 来 输入。

列表被定义为 nil 或其 cdr 是另一个列表的序对。 序对显示为它们所表示序列中元素的括号括起来的、空格分隔的序列。 例如，(cons (cons 1 nil) (cons 2 nil)) 显示为 ((1) 2)。这意味着 cons 是不对称的。

在流的情况下，上述规则有一个例外。流 表示为流的 car，后跟一个点，后跟构成其 cdr 的 承诺。例如

scm> (cons-stream 1 nil)
(1 . #[promise (not forced)])

列表字面量可以通过 quote 特殊形式构造，因此 (cons 1 (cons 'a nil)) 和 '(1 a) 是等价的。

过程

过程表示 Scheme 程序中的某个子程序。过程在 Scheme 中是 一等公民，这意味着它们可以绑定到名称并在各处传递， 就像任何其他 Scheme 值一样。过程在大多数其他语言中等价于 函数，这两个术语有时可以互换使用。

过程可以在一定数量的参数上被调用，执行一定数量的 动作，然后返回某个 Scheme 值。

过程调用可以使用语法 ( ...) 来执行， 其中 是某个求值得到过程的表达式，每个 （可以有任意数量，包括 0）求值得到 过程的一个参数。术语"过程调用"与术语"调用表达式"可以互换使用。

有几种类型的过程。内置过程（或简称内置）是 解释器内置的，并在启动时已绑定到名称 （尽管你仍然可以重新绑定这些名称）。Python 版解释器中所有 内置过程的列表可在 Scheme 内置过程文档中找到。

Lambda 过程使用 lambda 或 define 特殊形式定义（见 下文），并创建一个新帧，其父帧是定义 lambda 时所在的帧， 在调用时。lambda 主体中的表达式随后在此新环境中被求值。 Mu 过程类似，但新帧的父帧是 调用 mu 时的帧，而不是创建它时的帧。

61A Scheme 也有宏过程，必须使用 define-macro 特殊形式定义。宏的工作方式类似于 lambda，不同的是它们 将调用表达式中的操作数表达式传递到宏中，而不是 已求值的参数，然后它们在调用环境中 求值宏返回的表达式。求值 宏调用表达式的修改过程是：

1. 求值运算符。如果它不是宏过程，请遵循正常的调用 表达式步骤。
2. 将步骤1中的宏过程应用于未求值的操作数。
3. 宏返回后，在调用环境中求值该值。

宏有效地让用户定义新的特殊形式。宏过程接受 未求值的操作数表达式，并且通常应该返回一段 Scheme 代码，该代码等价于宏。

承诺和流

承诺表示在环境中延迟求值表达式。 它们可以通过将表达式传递到 delay 特殊形式来构造。 承诺的求值可以通过将其传递到 force 内置过程中来强制。承诺的表达式将只被求值一次。 第一次调用 force 将存储结果，后续对相同承诺调用 force 时将立即返回该结果。

承诺必须包含序对或 nil，因为它被用作流的 cdr。如果 在强制时发现它包含其他内容，force 将报错。如果 force 由于任何原因报错，承诺保持未强制状态。

例如

scm> (define p (delay (begin (print "hi") (/ 1 0))))
p
scm> p
#[promise (unforced)]
scm> (force p)
hi
Error
scm> p
#[promise (unforced)]
scm> (force p)
hi
Error

或者，对于一个类型错误的示例：

scm> (define p (delay (begin (print "hi") 2)))
p
scm> p
#[promise (unforced)]
scm> (force p)
hi
Error
scm> p
#[promise (unforced)]
scm> (force p)
hi
Error

承诺用于定义流，流之于列表就像承诺之于 常规值。流被定义为序对，其中 cdr 是 求值得到另一个流或 nil 的承诺。cons-stream 特殊形式和 cdr-stream 内置过程使 流的构造和操作更容易。(cons-stream a b) 等价于 (cons a (delay b))， 而 (cdr-stream x) 等价于 (force (cdr x))。

给那些熟悉 JavaScript 等语言中承诺的人的注意事项：尽管 Scheme 承诺和 JS 风格的承诺源自 相同的一般概念，JS 承诺最好被描述为 异步计算的值的占位符。基于 Python 的 61A Scheme 解释器没有异步的概念，因此其承诺只表示 延迟求值。

未定义

最后，还有一个 undefined 值，某些内置 过程可以返回它。此值的行为类似于 Python 中的 None。如果输入到 REPL 的表达式求值得到 undefined，它不会被打印，就像 Python 一样。

特殊形式

在所有下面的语法定义中， 指的是可以变化的可选元素 x， 而 [x] 指的是可选元素 x。省略号 表示一个可以有多个前面的元素。

所有版本的 61A Scheme 中都包含以下特殊形式。

define

(define  )

求值 并将该值绑定到当前环境中的 。 必须是有效的 Scheme 符号。

(define ( [param] ...)  ...)

使用 param 作为参数、body 表达式作为主体构造一个新的 lambda 过程，并将其绑定到当前环境中的 name。 name 必须是有效的 Scheme 符号。每个 param 必须是唯一的有效 Scheme 符号。此快捷方式等价于：

(define  (lambda ([param] ...)  ...))

但是，某些解释器可能会给使用此快捷方式创建的 lambda 一个 name 的内在名称，用于可视化或调试目的。

在这两种情况下，返回值都是符号 。

示例：

scm> (define x 2)
x
scm> (define (f x) x)
f

if

(if   [alternative])

求值 predicate。如果为真，则求值并返回 consequent。 否则，如果存在 alternative，则求值并返回它（如果在这种情况下没有 alternative，则返回值为未定义）。

示例： 此代码返回非空列表的长度，空列表返回 0：

(define nums '(1 2 3))
(if (null? nums) 0 (length nums))

cond

(cond  ...)

clause 对应于以下形式的表达式：

( [expression] ...)

或者，clause 可以写成：

(else [expression] ...)

从第一个 clause 开始。求值 test。如果为真，则按顺序求值 expression，返回最后一个。如果没有，则返回 test 求值得到的结果。如果 test 为假，则继续到下一个 clause。 如果没有更多 clause，则返回值为未定义。 形式为 (else [expression] ...) 的子句等价于 (#t [expression] ...)。

示例： 此代码对负数返回 -1，对正数返回 1，对零返回 0。

(define n -3)
(cond
    ((< n 0) -1)
    ((> n 0) 1)
    (else 0)
)

and

(and [test] ...)

按顺序求值 test，返回第一个假值。如果没有 test 为假，则返回最后一个 test。如果未提供参数，则返回 #t。

示例： 当 x 同时大于 10 且小于 20 时，此 and 形式求值得到真。

(define x 15)
(and (> x 10) (< x 20))

or

(or [test] ...)

按顺序求值 test，返回第一个真值。如果没有 test 为真且没有更多 test，则返回 #f。

示例： 当 x 小于 -10 或大于 10 时，此 or 形式求值得到真。

(define x -15)
(or (< x -10) (> x 10))

let

(let ([binding] ...)  ...)

binding 对应于以下形式的表达式：

( )

首先，在当前帧中求值时每个 binding 的 expression。 接下来，创建一个扩展当前环境的新帧，并将每个 name 绑定到其中相应的已求值 expression。

最后，按顺序求值 body 表达式，返回已求值的 最后一个。

示例： 此 let 形式有两个绑定和三个主体表达式：

(let (
      (x 5)
      (y 10)
     )
  (print x)
  (print y)
  (+ x y)
)

begin

(begin  ...)

在当前环境中按顺序求值每个 expression，返回 已求值的最后一个。

示例： 这是 begin 在过程内的 if 形式中使用。返回值是三个表达式中的最后一个。

(define (sortedpair a b)
    (if (> a b)
        (begin
            (print a)
            (print b)
            (cons a (cons b nil))
        )
        (begin
            (print b)
            (print a)
            (cons b (cons a nil))
        )
    )
)

(define spair (sortedpair 10 20))
(car spair)

lambda

(lambda ([param] ...)  ...)

创建一个以 param 作为参数、以 body 表达式 作为主体的新 lambda。当以此形式创建的过程被调用时，调用帧 将扩展此 lambda 定义时所在的环境。

示例： 此代码立即使用两个参数调用 lambda 过程：

((lambda(x y) (+ (* x x) (* y y))) 3 4)

quote

(quote )

或者，

'

返回字面值 expression，而不求值它。

quasiquote

(quasiquote )

或者，

`

返回字面值 expression，而不求值它，除非 expression 的子表达式 是以下形式：

(unquote )

在这种情况下，expr2 被求值并替换上述形式在 否则未求值的 expression 中。

unquote

(unquote )

或者，

,

mu

(mu ([param] ...)  ...)

创建一个以 param 作为参数、以 body 表达式作为主体的新 mu 过程。当此形式创建的过程被调用时， 调用帧将扩展调用 mu 时所在的环境。

define-macro

(define-macro ( [param] ...)  ...)

使用 param 作为参数、以 body 表达式作为主体构造一个新的宏过程，并将其绑定到当前环境中的 name。 name 必须是有效的 Scheme 符号。每个 param 必须是唯一的有效 Scheme 符号。

宏过程应该是词法作用域的，就像 lambda 过程一样。

expect

此特殊形式包含在教职员解释器和网页解释器中，用于运行文档测试，但不是官方 Scheme 规范的一部分。

(expect  
)

在当前环境中求值 expr 并将其与（未求值的） output 进行比较，打印出结果。如果在求值 expr 时发生异常， 它会被捕获并打印回溯信息。

unquote-splicing

此特殊形式包含在教职员解释器和网页解释器中，但不在课程范围内，也不包含在项目中。

(unquote-splicing )

或者，

,@

类似于 unquote，不同的是 expr2 必须求值得到一个列表，然后 将该列表拼接到包含它的 expression 结构中。

delay

此特殊形式包含在教职员解释器和网页解释器中，但不在课程范围内，也不包含在项目中。

(delay )

返回一个在当前环境中延迟求值 expression 的承诺。

cons-stream

此特殊形式包含在教职员解释器和网页解释器中，但不在课程范围内，也不包含在项目中。

(cons-stream  )

(cons (delay )) 的简写。

set!

此特殊形式包含在教职员解释器和网页解释器中，但不在课程范围内，也不包含在项目中。

(set!  )

求值 expression 并将结果绑定到从当前环境中可以 找到的第一个帧中的 name。如果 name 在当前 环境中未绑定，则会导致错误。

返回值为未定义。

补充阅读

• Scheme 内置过程 - 涵盖基于 Python 的解释器的内置过程。
• R5RS 规范 - 61A Scheme 最 closely resembles 的完整 Scheme 规范。