文章目录
  1. 1. 本章主旨—构造过程抽象
  2. 2. 程序设计的基本要素
  3. 3. 过程与它们所产生的问题
    1. 3.1. 找零钱
    2. 3.2. 求素数
  4. 4. 用高阶函数过抽象
  5. 5. 总结

最近两个月除了工作之外,业余时间一直在研习sicp这本经典书。关于这本书的讨论有很多,像老赵写过SICP的书托,我觉得与其讨论这本书有没有读的价值,不如花上些,随手翻翻,如果感兴趣,就读下去;否则直接忽略即可。计算机理论发展到了现在,有太多太多经典需要我们去读了,恐怕我们这一辈子都无法读完,为什么不找你感兴趣的来读呢?

我这次建了个Github库来记录课后每一道习题与平时的所感所悟,希望对后面阅读sicp的同胞们有所帮助。

废话不多说了,趁着上周刚看完第一章,现在进行一下总结。

本章主旨—构造过程抽象

我们在进行程序设计时,接触到的无非就是两类东西:数据操作数据的过程。本章只处理简单的数值数据,将注意力集中在过程的构造。本书采用lisp方言scheme进行教学,之所以选择lisp,是因为:

计算过程的lisp描述(称为过程)本身又可以作为lisp的数据来表示和操作。

现在许多威力强大的程序设计技术,都依赖于填平在“被动的”数据和“主动的”过程之间的传统划分。鉴于lisp可以将过程作为数据进行处理的灵活性,使它成为探索这些技术最方便的现存语言之一。

程序设计的基本要素

一个强有力的编程语言,应该提供下面三种机制,编程者利用它们来组织自己有关计算过程的思想:

  1. 基本表达式形式
  2. 组合机制
  3. 抽象机制

scheme使用前缀表示法,这和我们平常的编程语言不一样,需要适应。

本小节依此讲解了下面知识:

  • 基本的表达式,环境和变量
  • 组合式的求值
  • 过程的定义
  • 复合过程求值的替换模型(应用序与正则序)
  • 条件表达式和谓词
  • 过程抽象

概念本身比较简单,我们需要明确下面几个点:

  1. 表达式求值过程就是表达式语义的实现
  2. 代换模型给出了过程定义和过程应用的一种语义

    很多 Scheme 过程的行为可以用这个模型描述
    后面会看到,更复杂的过程需要用扩充的语义模型(像一些语法糖衣)

  3. 代换模型只是为了帮助直观理解过程应用的行为

    它并没有反映解释器的实际工作过程
    实际解释器的情况后面讨论,基于环境实现

  4. 本课程要研究解释器工作过程的一组模型

    代换模型最简单,容易理解,但不足以解释所有的实际程序
    其局限性是不能解释带有可变数据的程序
    后面将介绍更精细的模型

无论是 C 还是 Scheme,都没规定运算对象的求值顺序。这意味着 假定它们采用某种特殊顺序都是不正确且不可靠的。所以我们不要写只有按特定求值顺序才能得到所需结果的表达式!

1
2
3
//C 语言里依赖于求值顺序的表达式,这里的输出依赖于编译器的实现,与语言本身无关
m = n++ + ++n;
printf("%d, %d", n, n++);

本小节以牛顿法求平方根展示了如何通过简单的过程构造复杂的过程。关于牛顿法的代码及优化方案我git笔记中找到。

过程与它们所产生的问题

本小节主要讲解了下面几个概念:

  • 过程的内部定义与块结构(上面的牛顿法我已经使用)
  • 分析过程(静态、动态)产生的计算过程(动态,行为)
  • 计算过程的类型

    线性递归
    线性迭代
    树形递归

  • 计算的代价

本小节主要是熟悉过程,知道常见过程的分类,以及能够明确各种过程所占用的资源。

这里有意思的是习题1.19,通过矩阵相乘的方式来算斐波那契数,大家可以去了解下。

找零钱

关于这个题目我在git库上的笔记已经有了比较详细的介绍,这里不再赘述。

求素数

这里求素数有两种解法,分别是:

  1. 寻找因子,代码参考习题1.22
  2. 费马检查,代码参考习题1.24

这里比较有意思的是习题1.28,这道题介绍了一种费马检测的不会被欺骗的变形,称为Miller-Rabin检查。
到现在我还不知道为什么MR检查不会被欺骗,感觉应该是和费马定量等价的,无非就是等式两边同时除以了a而已。后面想明白后,我会再即时更新。

除了上面两个外,本章还用了下面两个例子:

1
2
3
4
(definee (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

用高阶函数过抽象

这一小节可算是第一章的重点,在这小节里,过程既可以作为参数传给过程,又可以作为过程的返回值,通过不断抽象,得到一系列高阶过程,前面的牛顿法,不定点都可以轻松用高阶过程来实现。

这里主要是做相应的习题来巩固自己的理解,如果你是第一次接触高阶函数,我相信你一定会大喊:“还能这么玩呀”!

总结

经过2个月的时间陆陆续续把这第一章看完,现在过了2周再来写这篇总结,效果还是蛮好的,很多东西一下就能够回想起来,不过也发现之前的漏洞,一些点当时没深究,放下了也就没有然后了。这次总结发现了些,这个周末一定补充上。

如果你也在读sicp,希望你能坚持下去,让我们一起享受编程的奥妙。

PS:在写这篇总结时,在简书上我找到这么一篇文章仍距遥远,知易行难,不知该作者的功力有多深厚才能有这么深的见解。
世界这么大, 让我们抓紧从SICP开始行动起来吧。


KeepWritingCodes 微信公众号

本博客使用 disqus 评论系统,但不幸被墙,不会翻墙的小伙伴可以通过上面的公众号与我交流。希望我们的交流能给你我带来些许启发。

PS: 微信公众号,头条,掘金等平台均有我文章的分享,但我的文章会随着我理解的加深不定期更新,建议大家最好去我的博客 liujiacai.net 阅读最新版。

文章目录
  1. 1. 本章主旨—构造过程抽象
  2. 2. 程序设计的基本要素
  3. 3. 过程与它们所产生的问题
    1. 3.1. 找零钱
    2. 3.2. 求素数
  4. 4. 用高阶函数过抽象
  5. 5. 总结