Chap.4 数字游戏

仅考虑非负整数集。基本元件add1接受一个参数，结果为这个参数的后继数，即这个数字+1，基本元件sub1接受一个参数，结果为这个数字的前驱数，即这个数字-1。基本元件zero?接受1个参数，表示这个数字是否为0.

使用这三个基本元件，首先来实现两个数字的加法运算。两数字m与n相加，可以描述为数字m进行n次add1操作，而进行n次add1操作可以用(zero? n)与(sub1 n)组合进行。由于+号已经是基本运算，我们使用原子o+表示我们自定义的这个加法，尝试编写此函数：

(define o+
  (lambda (m n)
    (cond
      ((zero? n) m)
      (else (o+ (add1 m) (sub1 n))))))

这就已经违反了Scheme十诫之第一诫：问题之首必用null?，不过对于数字，zero?就类似于列表的null?，类似地add1是类似于cons那样构建列表，sub1像cdr那样进行一般性递归。

两数字m与n相减，即对m执行n次sub1。尝试编写'-函数（虽然仅考虑非负整数集，不过当前o-函数对负整数也有效）：

(define o-
  (lambda (m n)
    (cond
      ((zero? n) m)
      (else (o- (sub1 m) (sub1 n))))))

看来针对数字类型，要将Scheme十诫之第一诫进行一点更新：

Scheme十诫之第一诫(ver 1.1)：对一个原子列表lat递归调用时，要先询问(null? lat)，对于一个数字n进行递归调用时，要先询问(zero? n)

接下来实现乘法。两个数字m与n相乘，就是累加n次的m。对于数字而言，递归时则是由o+连接的典型元素与一般性递归，对于乘法，典型元素就是m，一般性递归则是(o* m (sub1 n))，即：

(define o*
  (lambda (m n)
    (cond
    ((zero? n) 0)
    (else (o+ m (o* m (sub1 n)))))))

Scheme十诫之第四诫(ver 1.1)：在递归时总是至少改变一个参数。该参数必须向着不断接近结束条件而改变。改变的参数必须在结束条件中得以测试：用cdr时则用null?测试结束，用sub1时则用zero?测试结束

(o* 12 3)的值为36，其计算过程为：

  (o* 12 3)
= (o+ 12 (o* 12 2))
= (o+ 12 (o+ 12 (o* 12 1)))
= (o+ 12 (o+ 12 (o+ 12 (o* 12 0))))
= (o+ 12 (o+ 12 (o+ 12 0)))
= (o+ 12 (o+ 12 12))
= (o+ 12 24)
= 36

Scheme十诫之第五诫：用+构建一个值时，总是用0作为结束代码行的值；用*构建一个值时，总是用1作为结束行代码的值；用cons构建一个列表时，总是用(quote ())作为结束行代码的值。

记全部由数字（本节仅指非负整数）构成的列表为tup，即元组Tuple。编写一个tup+，接受将两个长度相同的tup作为参数，结果为同样长度的元组，每个元素是相应位置原tup的元素之和。例如tup1是(3 6 9 11 4)，tup2是(8 5 2 0 7)，则(tup+ tup1 tup2)结果为(11 11 11 11 11)。

由于限制tup1和tup2的长度需要一致，当二者都为空时，返回一个空列表，否则将两个tup的首元素相加，作为典型元素，两个tup的分别cdr作为一般性递归，使用cons构建成一个最终的列表。

(define tup+
  (lambda (tup1 tup2)
    (cond
      ((and (null? tup1) (null? tup2)) (quote()))
      (else (cons
             (o+ (car tup1) (car tup2))
             (tup+ (cdr tup1) (cdr tup2)))))))

改进一下，如果tup1和tup2的长度可以不一致，长度不足则认为是以0填充，例如tup1为(3 4),tup2为(4 6 8 1),新的(tup+ tup1 tup2)将得到(7 10 8 1)。

这时，两个表可能不同时为空，当tup1为空的时候，应返回tup2，当tup2为空的时候，应返回tup1，都不空的时候则进行典型元素和一般性递归的构建。tup1与tup2同时为空时，可以按tup1为空返回tup2，此时tup2是空表，所以逻辑上是正确的。

(define tup+
  (lambda (tup1 tup2)
    (cond
      ((null? tup1) tup2)
      ((null? tup2) tup1)
      (else (cons
             (o+ (car tup1) (car tup2))
             (tup+ (cdr tup1) (cdr tup2)))))))

再编写lt和gt的表达式，分别表示“less than”和“greater than”用于数字的比较。要比较两数字m,n的大小，仅用基本元件设计递归来比较二者的大小。可以对m和n执行多次sub1，直到某个数字满足zero?，当m先满足zero?，此时n仍大于0（仅考虑非负整数），说明m比n小，反之亦然。

(define lt
  (lambda (m n)
    (cond
      ((zero? m) #t)
      ((zero? n) #f)
      (else (lt (sub1 m) (sub1 n))))))

测试一下，(lt 2 4)的求值过程：

  (lt 2 4)
= (lt 1 3)
= (lt 0 2)
= #t

是正确的。如果用两个相等的数字进行测试(lt 2 2)：

  (lt 2 2)
= (lt 1 1)
= (lt 0 0)
= #t

仍然得到真的结果，但实际应当为假。原因在于两个zero?判断会对结果产生影响，如果换过来的话：

(define lt
  (lambda (m n)
    (cond
      ((zero? n) #f)
      ((zero? m) #t)
      (else (lt (sub1 m) (sub1 n))))))

这个问题就解决了，两个数字相等时，返回值为假。类似地，编写gt函数：

(define gt
  (lambda (m n)
    (cond
      ((zero? m) #f)
      ((zero? n) #t)
      (else (gt (sub1 m) (sub1 n))))))

有了lt和gt，就可以编写对于数字类型的判等函数eq?，当然eq?作为基本元件，有些Scheme语言标准中允许对数字类型进行判等，为示区别，针对非负整数来自定义的判等函数称为oeq?

(define oeq?
  (lambda (m n)
    (cond
      ((> m n) #f)
      ((< m n) #f)
      (else #t))))

四则运算还有一个求商运算，scheme中可以使用quotient。我们自定义的求商函数命名为div，要求m除以n的商，即m当中含有多少个n，就是若m仍大于n，则将典型元素为1，且一般性递归推导为m-n与n求商，最终m小于n时，商为0结束递归。

(define div
  (lambda (m n)
    (cond
      ((< m n) 0)
      (else (add1 (div (o- m n) n))))))

例如(div 15 4)的运算过程为：

  (div 15 4)
= (add1 (div 11 4))
= (add1 (add1 (div 7 4)))
= (add1 (add1 (add1 (div 3 4))))
= (add1 (add1 (add1 0)))
= (add1 (add1 1))
= (add1 2)
= 3