《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。

实现:

1
2
3
(define looking
(lambda (a lat)
(keep-looking a (pick 1 lat) lat)))
1
2
3
4
5
6
(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,不停递归调用。

1
2
3
(define eternity
(lambda (x)
(eternity x)))

(shift pair)

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

实现:

1
2
3
4
5
(define shift
(lambda (pair)
(build (first (first pair))
(build (second (first pair))
(second pair)))))

(align pora)

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

1
2
3
4
5
6
7
8
(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 中的原子个数。

实现:

1
2
3
4
5
6
7
(define length*
(lambda (pora)
(cond
((atom? pora) 1)
(else
(plus (length* (first pora))
(length* (second pora)))))))

(shuffle pora)

类似于 align,用 revpair 替代 shift

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

定义:参考阿克曼函数

实现:

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

停机问题

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

1
2
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

    1
    2
    3
    4
    (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》第九章的论述方法用自己的理解再写一遍。

– EOF –