【SICP】过程抽象:递归,迭代和高阶函数

少女dtysky

世界Skill

时刻2015.09.10

银河疾走。
疾走,疾走的终点是死亡,盛宴却永不会落幕。

这个系列是在学习魔法导论SICP时某些精要部分的归纳和总结,本节是第一章的总结,第一章在复习了一些常见算法的同时,讲述了在极其简单的基本scheme环境下如何适当的对程序的过程进行抽象,道出了抽象的一般形式,并给出了如何写出高可读性的代码——这些代码是符合人类的逻辑思维过程的。
第一章所有的习题如下,使用DrRacket环境:
SICP-Chapter1


1 Scheme

Scheme是一种Lisp方言,Lisp,即表处理语言,他的基本编程思想是函数式和递归的,所以对数学的亲和性很高,但对于人类而言就没有这么容易理解了,和其他C系的编程语言不同,在写Lisp的时候往往需要首先进行人肉优化,这会带来两个结果:

  1. 增加思考成本,降低短期效率
  2. 让代码结构变得更为清晰,增加可读性,降低维护成本

当然,现在Lisp嫡系的编程语言境遇都不怎么好,所以虽然其有通用语言之名,但却没有实际生产之实,而本书用到的Scheme更是只用于教学领域,那么这本书讲的东西就毫无实践意义了么?并非如此,SICP并不是一本讲语言的书,他讲的是对程序设计进行抽象的思想,而使用Scheme只是恰好有许多优秀、无所不包的特性,同时还能方便使用者造轮子,而造轮子,则是学习的最高效手段之一。

1.1 本节用到的Scheme语法

基本运算:

(+ 1 2) ;3
(- 1 2) ;-1
(* 1 2) ;2
(/ 1 2) ;1/2
(/ 1 2.0) ;0.5
(< 1 2) ;#t
(> 1 2) ;#f

逻辑运算:

(and (1 < 2) (1 > 2)) ;#f
(or (1 < 2) (1 > 2)) ;#t
(not (1 < 2)) ;#t

过程定义:

(define (inc x)
    (+ x 1))
(inc 2) ;3

分支语句:

(define (if-test x)
    (if (< x 5)
    1
    2))
(if-test 4) ;1
(if-test 6) ;2

(define (cond-test x)
    (cond   ((< x 5) 1)
            ((< x 10) 2)
            (else 3)))
(cond-test 4) ;1
(cond-test 9) ;2
(cond-test 100) ;3

匿名函数:

((lambda (x) (+ x 1)) 1) ;2
(let ((x (+ 1 1))) x) ; 2

2 递归和迭代

递归和迭代是两种基本的过程,他们都只需要一个过程的递推公式,通常而言,求得递推公式往往比求得通项公式要来的容易,所以这其实也是一种可以简化思考的方式。

2.1 线性递归和迭代

考虑一个函数,其定义为:

n! = 1 x 2 x 3 x ... x n

显然,这就是阶乘函数的定义,其递推公式是十分简单和浅显的,而通项公式则不是那么简单,下面我们可以分别用递归和迭代来实现它:

递归:

(define (factor n)
    (if n 0)
    1
    n * (factor (- n 1)))

这个递归实现的实际运算过程如下:

(factor 5)
(x 5 (factor 4)
(x 5 (4 x (factor 3)))
......
(x 5 (x 4 (x 3 (x 2 (factor 1))))
(x 5 (x 4 (x 3 (x 2 1))))
......
120

可见,递归过程中,原先的表达式会先被展开,直到无法再继续展开之时再回归计算。同时注意到递归总是发生在条件分支的末尾,这种递归而形式叫做“尾递归”,也是最常用的一种递归。

迭代:

用递归过程计算阶乘实际上是按照以下公式进行的:

n! = n x (n - 1) x (n - 2) x ... x 2 x 1

这有一个展开后回归的过程,所以必须使用一个特殊的存储结构(堆栈)去存储整个展开的轨迹,以用于之后的回归计算,虽然这种形式十分直观和便于理解,但往往也会造成大量资源的消耗,于是有了以下的迭代形式:

(define (factor n)
    (define (iter count result max-count)
        (if (= count max-count)
            result
            (iter
                (+ count 1)
                (* result count)
                max-count)))
    (iter 1 1 n))

迭代的实际运算过程如下:

(factor 5)
(iter 1 1 5)
(iter 2 1 x 2 5)
(iter 3 2 x 3 5)
(iter 4 6 x 4 5)
(iter 5 24 x 5 5)
120

可见,在迭代形式下,计算是实时的,没有展开的概念,也无需回归计算,计算过程中只需要维护count, result和max-count三个变量即可,需求的资源大大减少,然而这个的代价是代码的形式不够直观(阶乘这种小东西还好,一旦复杂起来...)

2.2 树形递归和迭代

树形递归实际上就是多个分支的线性递归,也可以说线性递归是单分支的树形递归,考虑以下函数:

$$Finb(n) = \begin{cases}0 && n = 0 \\1 && n = 1\\ Finb(n-1) + Finb(n-2) && others\ \end{cases}$$

这个函数即Fibonacci数列,它有许多有趣的性质和广泛的应用然而在这里只用它来讨论树形递归,它的递归形式如下:

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

你可以自行按照上面的展开过程进行展开,可以看到,由于最末的分支中有两个分支,这两个分支将会分别展开,并且每一次的进一步展开也是如此,所以最后将会形成一个树状的结构。

迭代形式:

与线性迭代不同,线性迭代中下一个状态只和当前状态有关,而fib函数下一个状态还和前一个状态有关,所以需要额外增加一个变量来保存前一个状态的值,其实现如下:

(define (fib n)
    (define (iter count result last) 
        (if (= n 0) 
            result
            (iter 
                (- count 1)
                (+ result last)
                result)))
    (iter n 1 0))

2.3 比较

由以上分析可见,递归过程一般比较直观,便于编写,但空间复杂度和时间复杂度均比迭代过程高,相反,迭代过程比较考验设计能力,但其复杂度相对迭代过程占有优势。


3 高阶函数

高阶函数是一类特殊的函数,得益于Lisp语系函数式一等公民的这个特性,让其得以实现,在Scheme中,函数也是一种数据类型,可以作为函数的参数或者函数的返回值,这也给我们提供了一种思维的方式——我们可以定义一些函数,它们以函数参数,返回一些函数,就像是某些用于生成“生产设备”的工厂一样,生产出用于加工其他部件的机器。

注:Scheme中也将“函数”称为“过程”。

比如,我们都知道“加法”是一种抽象,加法的对象不仅可以是数,还可以是各种函数(数也是一种特殊的函数,即f(x) = x),所以我们就可以对加法进行抽象:

(define (plus a b)
    (lambda (x)
        (+ (a x) (b x))))
(define (square x) (* x x))
(define (cube x) (* x x x))
((plus square cube) 2) ;12

函数plus接受两个过程a和b,返回一个另一个过程,这个过程用匿名函数产生,它首先分别将变量x应用于过程a和b,随后将这两个过程的返回值进行相加运算。

在初步了解之后,我们可以做一些有趣的实验:

比如,我们知道“萌”是一个状态,也是一种行为,它可以表达为以下的含义——如果某某属性对于我而言是可以划分到“萌”的状态中的,那么我就是“moe”它的。这样一来,我们就可以定义为一个名为“moe”的过程,它接受一些属性,返回一个布尔值,如果返回值为真,则说明我是萌这个属性的,否则不萌:

(define (moe xxx)
    (if (yyy)
        true
        false))

在这里xxx和yyy均没有被定义,由于萌属性错综复杂,为了简化演示,我们将这个属性限定为“年龄”,如下:

(define (moe age)
    (< age 9))

现在这个moe过程的含义是:如果对象的年龄小于9岁,那么我就是萌她的,否则不是。但这种做法局限性是很强的,如果我不仅仅想用9岁作为一个阈值,而是想自己去定义我萌的年龄段,该怎么办?在其他语言中,一般想到的做法或许是加一个参数作为标示,来确定自己究竟萌哪一个年龄段,然后在函数中加上若干的分支去判断以给出答案,比如以下的python版本:

def moe(type, age):
    if type == 'loli':
        return age > 8 and age < 12
    elif type == 'girl':
        return age < 16
    ......

但在Scheme中,我们可以使用高阶函数来完成同样的需求,我们可以定义一个参数为函数的函数moe:

(define (moe tpye)
    (lambda (x)
        (type x)))

接下来定义每个属性的年龄段:

(define (loli age)
    (and (> age 8) (< age 12)))
(define (girl age)
    (and (> age 11) (< age 16)))

然后便可以使用moe函数来判定某个年龄是否符合你所萌的属性了:

((moe loli) 9) ;#t
((moe girl) 10) ;#f

是不是有点人工智能的意思?这也就是Lisp语系的魅力所在——随时随地,无时不刻,只要你想,就可以建立你自己的DSL。

如果不是自己的创作,少女是会标识出来的,所以要告诉别人是少女写的哦。