Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

22 Oct 2020

The Little Schemer读书笔记(七)

第9章 … and Again, and Again, and Again, …

开场先介绍一个looking函数:

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

looking函数的使用举例,对于(looking 'caviar '(6 2 4 caviar 5 7 3)),第一个位置是6,以6作为下标找到的节点值是7;以7为下标找到的节点值为3;以3为下标找到的节点值为caviar,和目标匹配,然后返回#t。

如果是(looking 'caviar '(6 2 grits caviar 5 7 3))的话,找到的是grits,和目标不匹配,返回#f。但是如果是(looking 'caviar '(7 2 4 7 5 6 3))的话,那么就进入无限循环了。

下面给出keep-looking的定义:

 (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的所写。

前面定义的looking叫做partial function,本章之前遇到的都是total function。partial function不会对每个输入都产生一个值。下面再举一个partial function的例子:

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

eternity会不断重复调用自己,永远不会结束。

在这个例子之前,书中例子中函数的递归都是基于对list的遍历,而list一般是有限长度的,所以递归是有底线的。上面的eternity例子所表明的意思是,递归可以是没有底线的。

下一个碰到的是shift:

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

书中对shift的描述:

The function shift takes a pair whose first component is a pair and build a pair by shifting the second part of the first component into the second component.

接下来是align函数:

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

可以猜测,上面的pora是pair or atom的缩写。align的主要功能是在一个嵌套的pair上反复执行shift操作。但是,shift并不会减少pair中atom的个数。align函数是total function。

接下来的是length*,用来统计align的参数pora中的atom的个数:

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

接下来是weight函数,和length相比,给pair的左成员更多权重,多达两倍:

 (define weight*
    (lambda (pora)
      (cond
        ((atom? pora) 1)
        (else
          (+ (* (weight* (frist pora)) 2)
             (weight* (second pora)))))))

接下来是shuffle:

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

如果输入是((a b) (c d)),那么shuffle的执行将不会终止。所以shuffle是partial function。

接下来的函数是C:

(define C
    (lambda (n)
      (cond
        ((one? n) 1)
        (else
          (cond
            ((even? n) (C (/ n 2)))
            (else (C (add1 (* 3 n)))))))))

C函数在输入为0的时候无法产生值。对于C函数,书中提到了一个人物Lothar Collatz (1910-1990)。

接下来的函数是A:

(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函数,书中提到的人物是Wilhelm Ackermann。A函数和shuft以及looking一样,对于某些输入参数,递归无法在有限时间内收敛。比如:(A 4 3)

然后书中引用了一首诗:

But answer came there none – And this was scarcely odd, because They’d eaten every one.

The Walrus and The Carpenter - Lewis Carroll

接下来,书中举了一个will-stop?的例子,来看看是否能定义出一个函数,能够用来判断另一个函数是否能够返回值。

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

然后又列举了一个last-try来扩展will-stop?,使其能应用在eternity上,使其能应用在eternity上:

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

给出的结论是无法定义出这样一个will-stop?,书中给出的解释是:

We took a really close look at the two possible cases. If we can define will-stop?, then (will-stop? last-try) must yield either #t or #f. But it cannot – due to the very definition of what will-stop? is supposed to do. This must mean that will stop? cannot be defined.

last-try是一个反例,它是对will-stop?的一个悖论(只有(will-stop? last-try) 在false的情况下,last-try才会stop),表明有些递归函数,是无法用(define …)来命名的。

有很多函数是无法define的,也就是说不能有名字。对此,书中附带列举了两个人名: Alan M. Turing (1912-1954) 以及 Kurt Gödel (1906-1978) 。

那怎么办呢?很简单,没有名字,就不通过名字来使用函数,而是直接使用函数本身。就像一个人原本叫张三,但是后来名字被剥夺了,所以不能通过张三找到这个人,但是还是可以跟这个人打交道的。

下面是length函数的定义:

(define length
    (lambda (l)
      (cond
        ((null? l) 0)
        (else (add1 (length (cdr l)))))))

我们完全可以把其名字length去掉。先来看下面这个例子:

(lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (eternity (cdr l))))))

上面定义了一个lambda函数,但是因为没有名字,在定义之后再无法使用,因为无法通过名字来找到它。所以,要在定义的时候就使用这个函数,比如:

(lambda (l)
    (cond
      ((null? l) 0)
      (else
        (add1
          ((lambda (l)
             (cond
               ((null? l) 0)
               (else (add1 eternity (cdr l)))))
           (cdr l))))))

上面的嵌套代码有重复的部分,细心的人或许能够发现重复的部分有下面的模式:

((lambda (length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 (length (cdr l)))))))
   eternity)

你可能会觉得上面函数又有了名字,叫length。可是这个名字是局部的临时的,跟用(define …)定义的名字在作用域上有所不同。

把重复的部分提取出来,用局部的mk-length加以表示,我们有:

((lambda (mk-length)
     (mk-length
       (mk-length eternity)))
   (lambda (length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 (length (cdr l))))))))

上面的lambda定义对'()返回0

只要嵌套mk-length,即可实现对模式的重复:

((lambda (mk-length)
   (mk-length
     (mk-length
       (mk-length eternity)))
   (lambda (length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 (length (cdr l))))))))

如果高兴,我们可以把length也命名为mk-length,毕竟length也只是局部的名字:

((lambda (mk-length)
     (mk-length
       (mk-length eternity)))
   (lambda (mk-length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 (mk-length (cdr l))))))))

All names are equal, but some names are more equal than others. – George Orwell ( 1903- 1950)

进一步,eternity挪到里面

((lambda (mk-length)
      (mk-length mk-length))
   (lambda (mk-length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 ((mk-length eternity) (cdr l))))))))

上面的lambda函数在'(apple)的时候返回1,但是如果list元素超过一个,就没有结果了。

更进一步,将eternity替换成mk-length:

((lambda (mk-length)
      (mk-length mk-length))
   (lambda (mk-length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 ((mk-length mk-length) (cdr l))))))))

这样一改造,那么上面的lambda函数能够接受节点数为N的list了。这是一个把自己传给自己,让自己重复自己的游戏。

可以更加进一步,把(mk-length mk-length)提取出来,称为length

 ((lambda (mk-length)
     (mk-length mk-length))
   (lambda (mk-length)
     ((lambda (length)
        (lambda (l)
          (cond
            ((null? l) 0)
            (else (add1 (length (cdr l)))))))
      (mk-length mk-length))))

遗憾的是,上面的例子递归无法收敛。因为(mk-length mk-length)是一个函数调用,而我们需要的是返回一个length函数,所以需要让其返回一个lambda:

 ((lambda (mk-length)
     (mk-length mk-length))
   (lambda (mk-length)
     ((lambda (length)
        (lambda (l)
          (cond
            ((null? l) 0)
            (else (add1 (length (cdr l)))))))
      (lambda (x)
        ((mk-length mk-length) x)))))

这样的话,中间的那个(lambda (length) ...其实和mk-length没有太大关系了,可以提取出一个单独的函数:

 ((lambda (le)
     ((lambda (mk-length)
        (mk-length mk-length))
      (lambda (mk-length)
        (le (lambda (x)
              ((mk-length mk-length) x))))))
   (lambda (length)
     (lambda (l)
       (cond
         ((null? l) 0)
         (else (add1 (length (cdr l))))))))

也就是下面的部分其实是独立的:

(lambda (le)
     ((lambda (mk-length)
        (mk-length mk-length))
      (lambda (mk-length)
        (le (lambda (x)
              ((mk-length mk-length) x))))))

上面的这个函数叫做Y combinator,其常见形式是:

(define Y
    (lambda (le)
      ((lambda (f) (f f))
       (lambda (f)
         (le (lambda (x) ((f f) x)))))))

但是(Y Y)会返回什么结果呢?谁知道!

(本章完)

comments powered by Disqus