最近一段时间在读 SICP，它使用 Scheme 这门语言讲解程序设计。学习 Scheme 是一段有趣的体验。尽管打开招聘网站，找不到这门语言的职位，似乎学完之后并不能找份工作。但作为程序员，我们直接打交道的是编程语言，思维过程也与编程语言语言相关。因此编程语言绝不仅仅是一个工具，多了解些编程范式总是有所裨益的。Scheme 是一门优美简洁的语言，它包含极少的语言元素，却有十分强大的表现力。

编程环境

vscode 也有一些插件支持 Scheme 的语言高亮，但不支持自动缩进。推荐使用 DrRacket 作为 Scheme 的编程环境。DrRacket 可以很方便地安装包，这样我们可以很快地建立相应的学习环境，如 SICP。它的语言选项中自带 HTDP 的教学包，如果选择以 HTDP 为教材，那么它是编程环境的首选。它的编辑器支持语法检查与自动缩进，这样编写 Scheme 时，就可以不必陷入括号的汪洋大海中了。

基本元素

表达式

Scheme 中，表达式可以是一个数，如 100，也可以包含过程（函数），如 (+ 100 100)。可以在命令行中直接键入表达式，查看结果：

> 100
100
> (+ 100 100)
200
>

其他语言中，两个数相加一般表示为 100 + 100 这种易于理解的中缀形式。除了中缀形式，加法运算还可以表示成前缀形式+ 100 100，以及后缀形式（逆波兰表达式）100 100 +。Scheme 采用前缀形式，将运算符放在最左边，随后才是操作数，并且由括号扩起来。Scheme 语法基于 s 表达式，前缀形式便是 s 表达式的一种。前缀形式看起来不够自然，这与用户习惯相关，也就是说习惯后就自然了。实际上使用这种表示方法有很多优点：

  1. 方便处理多个实参。多个数相加可以表示为 (+ 1 2 3 4)，而非 1 + 2 + 3 + 4 这样需要写多个运算符。
  2. 嵌套结构不会有求值顺序上的歧义。1 + 2 * 3 的结果是 7 而不是 6，是因为我们知道先 * 再 +，即 * 的优先级高于 +。而前缀形式 (+ 1 (* 2 3)) 很自然地要求先完成子表达式 (* 2 3) 后，才会进行 (+ 1 6)， 不会额外引入运算符优先级的问题。
  3. 表达形式的一致性。例如定义过程：
(define (add x y)
    (+ x y))

(add 1 2) 是过程 add 的一个示例，形式与运算符的 (+ 1 2) 一致。这将运算符与过程统一了——运算符也是过程。而在别的语言中，两者的使用完全不是一个形式。

当然这种前缀形式也有不便之处，那就是括号太多造成视觉污染。括号的问题可以借助 IDE 来进行辅助检查，有的环境也支持中括号[]的形式与小括号区分。

Scheme 中表达式可以嵌套，这意味着它的定义和计算具有递归的性质。递归是指描述一个概念时用到了自身，这个概念可以是一个数据结构，也可以是一个计算过程。

表达式可以定义为：

  • 数是一个表达式，如 100
  • 将过程作用于表达式后也是一个表达式

注意第二条白表明表达式的定义是递归的。根据以上定义，可以推导出：

  1. 100 是一个表达式， 200 也是一个表达式
  2. (+ 100 200) 是一个表达式，(+ 100 300) 是一个表达式
  3. 将 + 作用域上面两个表达式，(+ (+ 100 200) (+ 100 300)) 也是一个表达式

表达式求解可描述为：

  • 对过程的参数进行表达式求解
  • 将过程作用于参数，获得表达式的值

当过程的参数也是个表达式时，则需要对这个表达式进行求解，因此表达式的求解过程用到了自身的定义，也是递归的。

表达式是程序的基本组成单元，其定义和求解都具有递归的特点。使用递归去描述一个事物实际上可以降低复杂度，因为用到了自身的定义，而减少额外事物的引入。现代程序语言都支持递归，而在 Scheme 中使用递归是一件十分自然的事情。

过程

上文提到了递归，这里以一个示例去进一步了解这一概念。

计算 n 以内的正整数和。下面是递归与尾递归的两种形式：

; 1 递归方式：
(define (sum n)
  (if (= n 0) 0
      (+ n (sum (- n 1)))))

; 2 尾递归方式：
(define (sum n)
  (define (sum-iter n count)
    (if (= n 0) count
        (sum-iter (- n 1) (+ count n))))
  (sum-iter n 0))

递归需要保存过程调用的历史数据，而尾递归等价于迭代，通过参数传递信息，不需要记录历史信息。空间复杂度上，递归形式的是O(n)，而尾递归是O(1)。时间复杂度上两者都是O(1)。尽管两者的时间复杂度一样，但因为递归形式的过程有调用树的扩展与收缩，会显著慢于尾递归。更严重的是，当 n 太大时，递归形式的过程会耗尽内存，直接不可用。当处理的问题具有通项公式时，递归的过程仅仅相当于对问题重新描述一遍，而尾递归则需要斟酌一下才能写出来。

Scheme 中的过程还反映了黑盒的概念。在终端键入：

> +
#<procedure:+>
> sum
#<procedure:sum>

+ 和 sum 都是过程，但我们无法区分他们是基本过程还是复合过程，是内置过程还是自定义过程。这一特性允许我们对 Scheme 语言进行扩展，我们自己添加的过程就像 Scheme 内置的一样。在使用上，这些过程都遵循相同的格式：过程紧挨着左括号，作为列表的第一项。

Scheme 的使用列表作为基本数据结构。(+ 100 200) 就是一个包含三个元素的列表。定义的过程 sum 也是由列表构成。在 Scheme 中，过程即是数据。过程可以作为过程的参数，也可以作为参数的返回值。

学习资料

这不是一篇教程，不准备再继续介绍 Scheme 的语法和语言特性，进一步的学习可以参考：

  1. sicp 经典教材, 采用 Scheme 语言描述编程中的抽象。B 站上有这本书的配套视频课程，由作者亲自讲述。两个作者长得有点相像，其中一个是左撇子。
  2. The Little Schemer 这本书也很受推崇。中文版已经绝版，英文版有免费 PDF 版，可以自行搜索。采用对话式教学，跟 Scheme 语法一样特别。
  3. 公开课-编程范式 是一门讲述编程范式的课程。内容包含 c/并发编程/scheme/python，有一定难度，但看完后绝对有多收获。