符号数据

百科说， Scheme 是现代编程语言的皇后。她美丽而深邃。

引号

如果将 scheme 表达式的求值过程看作符号替换，那么对引号的求值就是消去引号。

例如：

> 'apple
apple

> '18
18

不同于变量解引用

'apple和apple是不同的，如果直接对 apple 求值，解释器会试图用 apple 绑定的符号替换它，在找不到定义时就会报错：

apple
× apple: undefined;
cannot reference an identifier before its definition

不同于字符串

'apple和"apple"是不同的，但是差异比较微妙。“apple” 是字符串，和数字一样是常量。对常量求值的结果是常量本身，对引号求值则会消去引号：

引号可以嵌套，字符串不能：

> 'r
r

> ''r
'r

> '''r
''r

' 引起的内容必须是演算中可能出现的结果，即合法的表达式，而字符串的内容是任意的。为什么有这个限制？不严谨地说，引号的内容是 scheme 中的字面量，既是字面量，当然不能是随意的字符串。对符号的操作产生的也是符号，而不能是无意义的的字符串。

阻止求值

可以将引号理解为，阻止解释器对所引的表达式求值。请看，

> (list 1 2 3)
(1 2 3)

> '(list 1 2 3)
(list 1 2 3)

> (cons 1 (list 2 3 4))
(1 2 3 4)

> (cons 1 '(2 3 4))
(1 2 3 4)

> (cons 1 '(list 2 3 4))
(1 list 2 3 4)

> (cdr (cons 1 '(list 2 3 4)))
(list 2 3 4)

最大的疑问可能是，在阻止解释器对 list 求值之后，list 变成了什么？

从实现的角度说，list 作为函数指针被保存在列表里了，本该发生的函数调用没有触发，被引号阻止了。

从概念的角度说，list 就是 list ，一个平凡的符号¹。Scheme 中不存在一个对象能不能放进列表里的疑问，因为列表就是其符号本身，它不包含我们赋予它的含义，如“容器”。它在求值过程中像是容器，是因为它和“容器”在含义世界中的运算是同构的。

实例：符号求导

修改表达式，大概是一种比函数装饰器更强大的手法。请看这段程序：

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp))))
        ((exponentiation? exp)
         (let ((u (base exp))
               (n (exponent exp)))
           (make-product
            (make-product n (make-exponentiation u (- n 1)))
            (deriv u var))))
        (else
         (error "unknown expression type -- DERIV" exp))))

cond中的每个分支对应一种表达式类型，分别是：

• 数字
• 变量
• 和
• 积
• 常数幂
• 未知类型

每种表达式的求导方法，本质上通过对exp的分解与重组实现。下面列出它们的谓词、分解方法、构造函数：

和

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list '+ a1 a2))))

(define (addend s) (cadr s))

(define (augend s)
  (if (null? (cdddr s))
      (caddr s)
      (cons '+ (cddr s))))

积

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))

(define (multiplier p) (cadr p))

(define (multiplicand p)
  (if (null? (cdddr p))
      (caddr p)
      (cons '* (cddr p))))

幂

(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))

(define (make-exponentiation base exponent)
  (cond ((=number? exponent 0) 1)
        ((=number? exponent 1) base)
        ((and (number? base) (number? exponent)) (exp base exponent))
        (else (list '** base exponent))))

(define (base e) (cadr e))

(define (exponent e) (caddr e))

杂项

(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (even? x)
  (= (remainder x 2) 0))

(define (square x)
  (* x x))

(define (equal? x y)
  (cond ((and (symbol? x) (symbol? y)) (eq? x y))
        ((and (number? x) (number? y)) (= x y))
        ((and (null? x) (null? y)) true)
        ((and (list? x) (list? y)) (and (equal? (car x) (car y))
                                        (equal? (cdr x) (cdr y))))
        (else false)))

(define (exp b e)
  (cond ((= e 0) 1)
        ((even? e) (exp (square b) (/ e 2)))
        (else (* b (exp b (- e 1))))))

用例

> (deriv '(+ (** x 2) (* -3 x) 2) 'x)
(+ (* 2 x) -3)

冯诺依曼结构，图灵机，lambda 演算

我认为，理解符号数据的关键，是对形式系统和 lambda 演算有基础的认识。

形式系统

有两个世界，一个形式的世界，一个含义的世界。

在形式的世界中，只有形式公理（一组初始字符串）、形式证明（一组操作字符串的规则）、形式定理（由规则导出的字符串）。

所谓含义的世界，就是一个人的所有思想，在那里，“猫”不只是一个符号，还是毛茸茸的触感和灵活的身姿。

计算

计算的本质是 lambda 演算过程，lambda 演算是一种形式系统，等价于图灵机，是图灵完备的。

Scheme 解释器是利用冯诺依曼结构的电子计算机进行 lambda 演算的程序，它不区分数据和程序，只利用规则对表达式进行求值（形式系统中字符串的剪切替换）。

对引号的求值规则是规则的一种……

此中有真意，欲辨已忘言。

---

---

1. 参见认知科学家写给小白的Lambda演算。另外，推荐《数学女孩3 哥德尔不完备定理》。 ↩︎