The Little Schemer 知识点整理（六）：如影随形

2018 年 12 月 29 日

准备知识

算术表达式

它要么是一个原子（包括数字），要么是用 +×↑ 连接起来的两个算术表达式。
算术表达式的表示方式
- 中缀：(3 + 4)
- 后缀：(3 4 +)
- 前缀：(+ 3 4)
- 前缀：(+ (× 3 6) (↑ 8 2))
表示法

数字也是某种表示法，比如阿拉伯表示法 4。我们也可以用 (() () () ()) 来表示。

Scheme 十诫之第七诫

对具有相同性质的 subparts 进行递归调用：

列表的子列表
算术表达式的子表达式

Scheme 十诫之第八诫

~~八戒，为师。。。~~

使用辅助函数来抽象表达方式。

自定义函数

(numbered? aexp)

定义：用于判断一个算术表达式的表示方式中，是否除了 +×↑ 之外，只包含数字。

实现：

(define numbered?
  (lambda (aexp)
    (cond
      ((atom? aexp) (number? aexp))
      (else
        (and (numbered? (car aexp))
             (numbered? (car (cdr (cdr aexp)))))))))

(value nexp)

定义：返回可计数算术表达式（中缀）的一般性值。

实现：

(define value
  (lambda (nexp)
    (cond
      ((atom? nexp) nexp)
      ((eq? (car (car nexp)) (quote +))
        (plus (value (car nexp))
              (value (car (cdr (cdr nexp))))))
      ((eq? (car (car nexp)) (quote ×))
        (× (value (car nexp))
           (value (car (cdr (cdr nexp))))))
      (else
        (↑ (value (car nexp))
           (value (car (cdr (cdr nexp)))))))))

如果是前缀表达式的话：

(define value
  (lambda (nexp)
    (cond
      ((atom? nexp) nexp)
      ((eq? (car nexp) (quote +))
        (plus (value (car (cdr nexp)))
              (value (car (cdr (cdr nexp))))))
      ((eq? (car nexp) (quote ×))
        (× (value (car (cdr nexp)))
           (value (car (cdr (cdr nexp))))))
      (else
        (↑ (value (car (cdr nexp)))
           (value (car (cdr (cdr nexp)))))))))

(1st-sub-exp aexp)

定义：一个算术表达式（前缀）的表示方式中的第一个子表达式。

实现：（可省略 cond 和 else，因为只有一个问题）

(define 1st-sub-exp
  (lambda (aexp)
    (car (cdr aexp))))

(2nd-sub-exp aexp)

定义：一个算术表达式（前缀）的表示方式中的第二个子表达式。

实现：

(define 2nd-sub-exp
  (lambda (aexp)
    (car (cdr (cdr aexp)))))

抽象 value 函数

我们把 (car nexp) 替换成 (operator nexp)：

(define operator
  (lambda (aexp)
    (car aexp)))

那么 value 函数可以重写为：

(define value
  (lambda (nexp)
    (cond
      ((atom? nexp) nexp)
      ((eq? (operator nexp) (quote +))
        (plus (value (1st-sub-exp nexp))
              (value (2nd-sub-exp nexp))))
      ((eq? (operator nexp) (quote ×))
        (× (value (1st-sub-exp nexp))
           (value (2nd-sub-exp nexp))))
      (else
        (↑ (value (1st-sub-exp nexp))
           (value (2nd-sub-exp nexp)))))))

调整 1st-sub-exp 和 operator 就可以表示中缀算术表达式：

(define 1st-sub-exp
  (lambda (aexp)
    (car aexp)))

(define operator
  (lambda (aexp)
    (car (cdr aexp))))

这里，1st-sub-exp，2nd-sub-exp 和 operator 都是辅助函数。

回顾 lat? 函数

(define lat?
  (lambda (l)
    (cond
      ((null? l) #t)
      ((atom? (car l)) (lat? (cdr l)))
      (else #f))))

如果 0 表示为 ()，1 是 (())，2 是 (() ())，以此类推。

当 l 是 (1 2 3)，lat? l 显然是 #t。但是如果把数字用上述表示法表示，那 lat? l 的值显然是 #f，与实际不符。所以使用辅助函数来抽象的时候需要注意这类问题。

EOF