初识LISP：构造过程抽象

以前写的一篇读书笔记，入门lisp以及练习markdown用的，粘过来。
安科网有部分格式不支持，原文链接：https://www.zybuluo.com/qikangkang/note/853428

LISP是一门历史悠久的函数式编程语言。20世纪50年代后期，John McCarthy基于他的论文《符号表达式的递归函数及其机械计算》，设计了这一数学记述形式，为递归方程的使用做推理。后来MIT为其开发了语言解释器。
LISP语言最重要的特征是：计算过程的Lisp描述本身又可以作为Lisp的数据来表示和操作。
本书使用Lisp方言Scheme来举例。
Mac安装解释器：brew install mit-scheme

1.基本元素

(+ 2 3 4)
表达式用括号括起来，最左元素称为 运算符，其余元素称为运算对象。运算符也可以是一个过程（函数）
定义变量，函数：
(define pi 3.14159)
(define circumference (* 2 pi ))

2.过程及计算

下面具一个例子来明白如下概念：
递归过程（着重指语法层面，该过程定义中，引用了过程本身）
递归计算过程、迭代计算过程（指计算过程的进展方式）
尾递归（过程语法定义是递归的，执行迭代型的计算过程）

计算斐波那契数列：0，1，1，2，3，5，8，13，21，...
规则为：
$$
f(n) =
\begin{cases}
0, & \text{$n = 0$} \
1, & \text{$n = 1$} \
f(n-1)+f(n-2), & \text{$n > 1$}
\end{cases}
$$

用Lisp来实现：

(define (fib n)
 (cond ((= n 0) 0)
       ((= n 1) 1)
       (else (+ (fib (- n 1))
                (fib (- n 2))))))

这个过程是一个典型的树型递归，但是从算法层面看很糟糕，会做许多重复计算。实际上，计算最终要落脚到(fib 0)和(fib 1)，而计算(fib n)最终所需的计算(fib 0)和(fib 1)的次数正好是Fib(n+1)，由于斐波那契数列是成指数增长的，因此该过程所用的计算步骤会随输入增长而指数增长。
我们可以想办法规划出一种迭代的计算过程，基本想法就是 用一对整数a,b分别初始化为Fib(1)和Fib(0)，而后反复同时使用下面规则：

a=a+b b=a,注意是同时。相当于 c＝a，a＝a+b，b＝c；
在n次应用上述变换规则之后，a和b分别等于Fib(n+1)和fib(n)。
实现如下：

(define (fib n)
    (fib-iter 1 0 n))

(define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))

这种方式是一种线性迭代计算过程，跟第一种过程在计算步骤上差异巨大，后一方法相对于n为线性的，前一方法增长像Fib(n)一样快。

总结一下：
在上面的两种方法中，线性迭代计算过程更加高效，但并非说树形递归计算过程没有用，当我们考虑的是在层次结构性的数据上操作，而不是对数操作时，树型递归计算过程是一种自然的，威力强大的工具。而且更加容易理解设计，比如斐波那契数列相当于直接把定义翻译成lisp语言。

3.用高阶函数做抽象

高阶过程：一个过程，以过程作为参数，或者以过程作为返回值。
3.1 过程作为参数
考虑下面三个过程：
1、计算从a到b的各整数之和

(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))

2、计算从a到b的整数立方之和

(define (cube x) 
        (* x x x))
        
(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1 ) b))))

3、计算下面的序列之和
$$\frac{1}{13}+\frac{1}{57}+\frac{1}{9*11}+...$$

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2)))
         (pi-sum (+ a 4) b))))

可以看出，这三个过程共享着一种基础模式，我们可以把它抽象出来

(define (<name> a b)
  (if (> a b)
      0
      (+ (<term> a)
         (<name> (<next a>) b))))

就如同数学中的“求和记法”一样：$$\sum_{n=a}^b=f(a)+...+f(b)$$
它能够使我们处理求和概念本身，而不是某个具体的求和。
要在Lisp中实现这些，上面的写法是不行的，我们需要把

(define (sum a b term next)
  (if (> a b)
      0
      (+ (term a)
         (sum (next a) b term next))))

然后用这个高阶函数分别去计算上面的三个过程

(define (term n) n)
(define (next n) (+ n 1))
(define (sum-integers a b)
  (sum a b term next))

(define (term n) (* n n n))
(define (next n) (+ n 1))
(define (cubes a b)
  (sum a b term next))

(define (term n) (/ 1.0 (* n (+ n 2))))
(define (next n) (+ n 4))
(define (pi-sum a b)
  (sum a b term next))

3.2 用lambda构造过程
为了能够更简单的定义上述过程，我们引入一种lambda特殊形式，可以代替define 子过程。
比如pi-sum过程：

(define (pi-sum a b)
  (sum a b 
       (lambda (x) (/ 1.0 (* x (+ x 2))))
       (lambda (x) (+ x 4))))

用let创建局部变量
假定要计算函数：
$$f(x,y)=x(1+xy)^2+y(1-y)+(1+xy)(1-y)$$
可能希望将它描述为：
$$
a=1+xy\
b=1-y\
f(x,y)=xa^2+yb+ab
$$
let实现如下：

(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

找出函数的不动点
如果x满足方程$f(x)=x$，称x为函数f的不动点。对于某些函数，通过从某个初始猜测值出发，反复的应用f
$f(x),f(f(x)),f(f(f(x)))...$，直到值的变化不大时，就可以找到它的一个不动点。我们设计一个过程fixed-point，它以一个函数和一个初始猜测为参数，产生该函数的一个不动点的近似值。

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
        next
        (try next))))
  (try first-guess))

我们尝试用这种方法去计算平方根$\sqrt x$：
$$y=\sqrt x,即y^2=x,即y=x/y$$

(define (sqrt x)
  (fixed-point (lamada (y) (/ x y))
               1.0))

遗憾的是，这一不动点搜寻并不收敛，对初始猜测值$y_1$，下一个猜测值将是$y_2=x/y_1$,再下一个猜测值$y_3=x/y_2=y_1$，结果进入了一个无限循环，不断重复两个猜测$y_1,y_2$。控制这类震荡的一种方法是不让猜测变化太剧烈，因为实际答案总在$y$和$x/y$之间，因此我们取y的下一个值为$y$和$x/y$的平均值

(define (sqrt x)
  (fixed-point (lamada (y) (average y (/ x y)))
               1.0))

3.3过程作为返回值
上面的例子说明，将过程作为参数传递，能显著增强程序设计语言的表达能力。通过创建另一种返回值本身也是过程的过程，我们还能得到进一步的表达能力。
在上文求平方根的过程中，我们利用x和$f(x)$的平均值作为下一个猜测，使逼近收敛。这种思想叫做平均阻尼，是一种很有用的一般性技术。我们可以描述平均阻尼思想如下：

(define (average-damp f)
  (lamada (x) (average x (f x))))

这里的average-damp是一个过程，它的参数f也是一个过程，返回值是另一个过程，通过lamada定义产生。
利用average-damp，我们重做平方根过程：

(define (sqrt x)
  (fixed-point (average-damp (lamada (y) (/ x y)))
            1.0))

通过抽象、重组基本的计算过程，使得复杂过程更加清晰且容易理解、复用。比如求立方根：

(define (cube-root x)
  (fixed-point (average-damp (lamada (y) (/ x (square y)))
               1.0))

牛顿法
微积分都讲过导数的概念。
$Dg(x)$是g对x的导数，一般而言，如果dx是一个很小的数，那么
g的导数在任一数值x的值有下面函数给出：
$$Dg(x)=\frac{g(x+dx)-g(x)}{dx}$$
那么我们可以实现如下（取dx为0.00001）：

(define dx 0.00001)
(define (deriv g)
  (lamada (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

牛顿法有一种特殊情况。如果$g(x)$是一个可微函数，那么方程$g(x)=0$的一个解就是函数$f(x)$的一个不动点，其中：
$$f(x)=x-\frac{g(x)}{Dg(x)}$$
有了导数过程之后，牛顿法就可以描述为一个求不动点的过程了：

(define (newtown-transform g)
  (lamada (x) 
    (- (x) (/ (g x) ((deriv g) x)))))
(define (newtown-method g guess)
  (fixed-point (newtown-transform g) guess))

求平方根(通过牛顿法去找$y^2-x$的零点)：

(define (sqrt x)
  (newtown-method (lamada (y) (- (square y) x))
                  1.0))

复合过程是一种至关重要的抽象机制，作为编程者，我们应该设法识别程序里的基本抽象，进一步去构造更加强大的抽象。高阶过程的重要性，就在于是我们能显式地用程序设计语言的要素去描述这些抽象，是我们能像操作其他计算元素一样去操作它们。
一般而言，程序设计语言总会对计算元素的可能使用方式加上某些限制。带有最少限制的元素被称为具有第一级的状态。Lisp给了过程完全的第一级状态。这给有效实现提出了巨大的挑战，但由此获得的语言描述能力却是惊人的。