《The Little Schemer》知识点整理(六):如影随形

准备知识

  1. 算术表达式

    它要么是一个原子(包括数字),要么是用 +×↑ 连接起来的两个算术表达式。

  2. 算术表达式的表示方式

    • 中缀:(3 + 4)
    • 后缀:(3 4 +)
    • 前缀:(+ 3 4)
    • 前缀:(+ (× 3 6) (↑ 8 2))
  3. 表示法

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

Scheme 十诫之第七诫

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

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

Scheme 十诫之第八诫

八戒,为师。。。

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

自定义函数

(numbered? aexp)

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

实现:

1
2
3
4
5
6
7
(define numbered?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
(else
(and (numbered? (car aexp))
(numbered? (car (cdr (cdr aexp)))))))))

(value nexp)

定义:返回可计数算术表达式(中缀)的一般性值。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
(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)))))))))

如果是前缀表达式的话:

1
2
3
4
5
6
7
8
9
10
11
12
13
(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)

定义:一个算术表达式(前缀)的表示方式中的第一个子表达式。

实现:(可省略 condelse,因为只有一个问题)

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

(2nd-sub-exp aexp)

定义:一个算术表达式(前缀)的表示方式中的第二个子表达式。

实现:

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

抽象 value 函数

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

1
2
3
(define operator
(lambda (aexp)
(car aexp)))

那么 value 函数可以重写为:

1
2
3
4
5
6
7
8
9
10
11
12
13
(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 就可以表示中缀算术表达式:

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

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

回顾 lat? 函数

1
2
3
4
5
6
(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 –