SICP读书总结-第一章

发表于 更新于 分类于

前言

SICP这本书可以说是一本被吹捧了很多年的书,看这本书的起源虽说记不太清了,但是肯定和一个词有关—“内功”,之前也是先看了一遍Sussman教授给企业培训的视频课程,可以说在第一次看的时候,作为一个没有接触过函数式编程的程序员来说,只能说是惊为天人,就像是自己的编程观被颠覆了一次一样:原来程序还可以这么写,也被其中的很多观念所深深的打动和折服,对程序开发的层次的抽象和积累以及对Stream—流的印象也是非常的深刻,还有就是eval,apply这两只手互相描绘自己的神奇情形(这里又和GEB产生了一些联系,看到GEB上这幅插图的时候才知道这是爱舍尔的画),可以说每一幕都能深刻的吸引着我,在此期间也同时发现了很多的优质的博客,刘未鹏 | Mind Hacks和王垠的博客也使我受益匪浅,从康托尔、哥德尔、图灵——永恒的金色对角线这篇文章开始,也使得我似乎开始对数学又有了更多的兴趣,直接导致的是我开始看了《巴赫，爱舍尔，哥德尔》(简称GEB)这本也被称为是神书的书,在兴趣集中的一瞬间,思绪就会向四处蔓延出去,就像在揭开了数学这本魅人的书的一角的时候,其中的精彩就会涌地冲向你的面前,你会发现某些简洁的定理散发出了不可思议的美丽,并且是那么坚实地站在数学的大海中并且为所有的船员提供了方向,然后就会发现,在你知识所及的任何一个角落里,其实它早就暗藏其中,当你用一种震惊的目光注视着你的新的发现的时候,它只是镇定的在那里发出它自己的魅力,就像在其他任何一个角落一样.
在看完了讲课的视频之后,感觉还是有点不够滋味,便开始捧起了SICP这本书来看,而且这一次是坚定了决心的捧起了英文版,但是在过程中又先刷了一遍MIT的CS6.00的课程,原本每天都要啃掉一点的计划也是在事情的堆积中拖延了好久,也是在推完了视频之后才有了富裕的时间来好好看,由于之前已经看过一次视频的缘故,英文倒也没有对阅读造成很大的阻碍,也是在推完了第一章之后,把总结写在博客上,算是长期维持这个博客的又一个动力罢.

第一章总结

这一章的英文标题是:Building Abstractions with Procedures,翻译版是叫:构造过程抽象,但是个人感觉翻译过来总是少了那么点味道.
这一章的主要内容是先介绍了函数式编程的一种语言:Lisp,然后介绍了一些基本的语法和元素,在语言的运用上主要是讲了对很多数学问题的求解,包括阶乘,Fibnacci,求根等等,然后讲了如何构造高阶过程.
个人觉得第一章的精髓就在Produces上,在C/Java开发的时候,我们总是清晰的划分出数据和过程这两个概念,包括OO也是对数据和对数据的操作的抽象的封装,但是在这本书的开始,作者就想要模糊我们关于数据和过程的边界,因为在FP(函数式编程)中,数据和过程其实就是一种东西,在视频课程中,教授的说法就是:

让我们从虚无中来构造数据

也就是:建立抽象的数据不需要任何的数据,可以只用过程来完成.当然这么说还是十分抽象,在第二章中会得到很好的解释和演绎.

程序设计的基本要素:

根据教授的说法就是,当我们去考量一门程序设计语言的时候,应该从下面3个角度去考虑:

  1. 这门语言的基本元素是什么
  2. 将这些基本元素组合起来的手段是什么
  3. 可以操作和命名由元素组合起来的单元的手段是什么

接着主要是讲了一下的内容:

  • 表达式
  • 变量和变量环境
  • 组合式的求值
  • 复合过程及其求值(代换模型):normal order & applicative order
  • 条件表达式和谓词
  • 黑盒抽象

个人比较注意的内容是讲到了程序的形状(shape),书本上的例子是关于阶乘的计算的几种方法的比较,也顺便讲了关于复杂度和指数级复杂度的一些知识.课程的举例是加法的实现的2种方法的比较,第一种是: 

1
2
3
4
(define (+ x y)    
    (if (= x 0)    
    y    
    (+ (-1 + x) (+1 y))))

第二种是: 

1
2
3
4
(define (+ x y)    
    if (= x 0)    
    y    
    (+1 (+ (-1+ x) y))))

在进行手动的代换模型计算之后可以发现,第一种计算是线性的,每一次代换和求值之后只是括号中的数字发生变化,一个+1一个-1,但是第二种方式会使得过程无限变大,在草稿纸上看到就是先拓展再收缩,第一种可以解释为线性迭代,第二种则是递归求解(非常直观的能够看到不同的算法对于复杂度的影响).而其差别还不仅仅只体现在复杂度上,第一个算法可以实现断点和续算,只需要记录很少的信息,但是第二种算法如果深度过深,要中断之后继续运算的话,只能从头再来.从这里也能看出一个好的算法能够体现在很多的方面.
课本中的另一个例子就是关于牛顿法求平方根以及优化,主要是熟悉Lisp语言和一些算法的优化.
最后一个小点就是关于黑盒抽象就是说我们不必关心一个抽象过程里面发生了什么,只要在实现之后调用即可.

过程以及(我觉得是怎么写好过程)

主要讲的是:

  • 线性递归和迭代
  • 树型递归
  • 算法复杂度
  • 指数幂
  • GCD(最大公因数)
  • 素性测试

主要是讲了一些基本的算法的概念,包括上面讲的”shapes”,和Fibnacci计算中的重复和优化(这个基本在入门课程里都会讲到,只是代码实现不一样),然后讲了快速幂和GCD的求法以及综合的优化问题.
矩阵求Fibnacci在以前的算法训练中也已经接触过,倒是没有很新奇的地方,只是递推类的问题都可以矩阵优化,还有快速幂(哈哈),掌握之后还是挺有趣的.
素性测试比较感兴趣的是关于费马小定理的知识以及在素数测试中的应用,然后发现这也是一个大坑,就不往里面踩了,相关的知识还有中国剩余定理.

高阶过程来组织抽象

在看了关于FP的一些知识之后发现其实就是科里化(Currying),就是把过程(函数)来当成参数,但是在第一次看到这种方式的时候,只有惊叹:代码还能这么写!
一个很有意思的例子就是关于求和了: 

1
2
3
4
5
(define (sum term a next b)    
    (if (> a b)    
    0    
    (+ (term a)        
        (sum term(next a) next b))))

虽然是一个很简单的都不能叫做算法了,但是可以发现在经过高度的抽象之后,sum这么一个简单的过程也可以变得很牛逼(反正第一次我看到的时候是折服了),因为你在C/Java里从来没有想过这么来求和.而且还非常的好解释:
(定义 (求和 求和项产生过程 起始值a 下一项产生过程 上界b))
这时不得不赞叹一下FP的美妙的地方了(你以为那只是一个”+”号?对不起,它也是可以替换成过程的).
另一个非常吸引我的点就是:fixed point了,原因如下:

  • 求根的函数y=sqrt(x)等价于y经过函数f的作用,收敛于改进函数的值,ex:(y+y/2)/2(书中提到的一个improve方法),也就是函数y在f的作用下,最终f(sqrt(x)) ==> sqrt(x),也就是找到函数f(improve)的不动点.sqrt可以改写如下:
    1
    2
    (define (sqrt x)    
        (fixed-point f 1))

视频中还提到了如果improve函数是x/y的话在某些情况下会不收敛,画出函数图像就类似于电路中的震荡信号,而震荡信号可以在平均阻尼作用下收敛,于是x/y在函数平均阻尼的作用下,也可以用来寻找sqrt的不动点,这里,就变成了寻找平均阻尼函数的不动点,而平均阻尼函数平均的是x/y,而更厉害的是,平均阻尼函数仍然可以用求平均值的函数来计算: 

1
2
3
4
;;ave-dmp就是平均阻尼函数,接受一个函数f,产生一个函数x就是平均阻尼之后的函数
(define (ave-dmp)    
    lamdba(f)        
        (lamdba(x) (average(f x) x))))
  • 而牛顿法求函数的零点,也对应于一个函数y,使得fixed-point(y)=0,但是但是,求根函数又等于什么呢?前面说到找到f(sqrt(x))=sqrt(x)也就等价于F=f(sqrt(x))-sqrt(x)=0,也就是说,求根==>找到F的零点==>F的零点又等于找到f的不动点,看到这里的时候,我只能感觉到:真的神奇.
  • 而不动点理论最吸引我的,还是在产生Y组合子的时候,当然这又可以变成长篇大论了,而这也是我在看FP的时候,从数学角度非常吸引我的地方,当然后面的课程里它不止一次的出现,其实它变成了这门课程结束之后最最最吸引我的一点,也不止一次为这个简单而又艰深的理论所赞叹,折服.

结束

第一章就总结到这里,但是FP所具有魅力,深邃的地方才刚开始,但是已经足够使我兴奋,也给了我更多学习下去的动力.而时常的总结也确实使我获益很多,在回顾知识的过程中,也会有一些新的见解和发现,并且之前看课程的时候是手写的笔记其实更像是草稿,这也算是一次重新整理的过程吧.

吾常终日而思矣，不如须臾之所学也。