The Little Schemer 知识点整理（九）：……周而复始……

自定义函数

(looking a lat)

定义：在一个 lat 中查找有没有 a，但按照如下规律：

假设 a 是 caviar，lat 是 (6 2 4 caviar 5 7 3)，那么列表的第 1 个元素是 6，第 6 个元素是 7，第 7 个元素是 3，第 3 个元素是 4，第 4 个元素是 caviar，它不是数字了，与 a 相同，那么函数结果就是 #t。

实现：

(define looking
  (lambda (a lat)
    (keep-looking a (pick 1 lat) lat)))

(define keep-looking
  (lambda (a sorn lat)
    (cond
      ((number? sorn)
        (keep-looking a (pick sorn lat) lat))
      (else (eq? sorn a)))))

sorn 代表 symbol or number。

对比之前所学的递归，可以发现这里的 keep-looking 并没有对 lat 的某部分进行递归调用。我们把这样的递归称之为“非一般性”递归。那么这样的递归还有什么特点呢？

继续假设 a 还是 caviar，但 lat 变成 (7 2 4 7 5 6 3)，可以看到查询进程永远不会停下来。我们把 looking 这样的函数称为部分函数（Patial Function），以前所接触的那些函数都叫全函数（Total Function）。

(eternity x)

这里定义了一个最简单的部分函数 eternity，它并未完成任何目标，只是传入参数 x，不停递归调用。

(define eternity
  (lambda (x)
    (eternity x)))

(shift pair)

定义：参数 pair 的第一个元素也是 pair，将这个 pair 的第二个元素移进参数 pair 的第二个元素中，以此构建一个新的 pair。

实现：

(define shift
  (lambda (pair)
    (build (first (first pair))
           (build (second (first pair))
                  (second pair)))))

(align pora)

align 和 keep-looking 一样，在第二个条件中，(shift pora) 改变了 align 的参数，它不一定是 pora 的一部分，无法保证能够接近最终目标。其实这是违反了第七诫。

(define align
  (lambda (pora)
    (cond
      ((atom? pora) pora)
      ((a-pair? (first pora))
        (align (shift pora)))
      (else (build (first pora)
                   (align (second pora)))))))

(length* pora)

定义：计算 pora 中的原子个数。

实现：

(define length*
  (lambda (pora)
    (cond
      ((atom? pora) 1)
      (else
        (plus (length* (first pora))
              (length* (second pora)))))))

(shuffle pora)

类似于 align，用 revpair 替代 shift。

(define shuffle
  (lambda (pora)
    (cond
      ((atom? pora) pora)
      ((a-pair? (first pora))
        (shuffle (revpair pora)))
      (else (build (first pora)
                   (shuffle (second pora)))))))

假设 pora 是 ((a b) (c d))，那么 (shuffle pora) 递归不会停止，所以它是一个部分函数。

(A n m)

定义：参考阿克曼函数。

实现：

(define A
  (lambda (n m)
    (cond
      ((zero? n) (add1 m))
      ((zero? m) (A (sub1 n) 1))
      (else (A (sub1 n)
               (A n (sub1 m)))))))

这是一个全函数，但是不是所有值都能轻易计算出来，比如 (A 4 3)。

停机问题

经历了这么多全函数和部分函数的讨论，我们设计一个函数，用来判断某些函数：针对每个参数，是否返回一个值。形式如下：

(define will-stop?
  (lambda (f)
    ...))

它总是返回 #t 或者 #f，所以是一个全函数。接下来代入几个函数，逐个分析他们是不是会 stop？函数的参数都用空列表来代替，这样最简单。

1. length

   (length (quote ())) 是 0，这时 will-stop? length 为 #t。

2. eternity

   (eternity (quote ())) 不会返回值，根本停不下来，这时 will-stop? length 显然是 #f。

3. last-try

   定义 last-try：

   (define last-try
     (lambda (x)
       (and (will-stop? last-try)
           (eternity x))))

   (last-try (quote ())) 的值也就是 (and (will-stop? last-try) (eternity (quote ()))) 的值。考虑以下两种情况：

   • (will-stop? last-try) 是 #f，表示 last-try 停不下来，则：

     1. (and (will-stop? last-try) (eternity (quote ()))) = #f；
     2. (last-try (quote ())) = #f，表示 last-try 能够停下来。嗯？矛盾。

   • (will-stop? last-try) 是 #t，表示 last-try 能够停下来，则：

     1. (and (will-stop? last-try) (eternity (quote ())))，后面的 eternity 停不下来，整体也停不下来啊；
     2. 于是 (last-try (quote ())) 也停不下来。嗯？？？也矛盾了。

所以对于 will-stop?，如果我们能够定义它，那么它必然会生成 #t 或 #f；但是上面的例子告诉我们有时这是做不到的。要定义清楚 will-stop? 就必须意味着它无法被定义。说人话就是我们写不出 will-stop? 这样的函数。详见停机问题。

Y 组合子

本章的余下内容在构造 Y 组合子，即大名鼎鼎的 Y Combinator。我看了好几遍，查了一堆资料，才懂了个大概，感觉值得单独写一篇文章来详细叙述，把「The Little Schemer」第九章的论述方法用自己的理解再写一遍。