SICP Chapter1 读书笔记

Chapter 1:Building Abstraction with Procedures 构造过程抽象

  • 计算过程是存在于计算机里的一类抽象事物,它在演化过程中会去操作一些被称为数据的抽象事物。我们通过创建被称为程序的规则模式来指导这类过程的进行。程序由程序设计语言编排而成。
  • 我们将要使用Lisp表达过程性的思想,它是今天还在广泛使用的历史第二悠久的语言,本书将使用Lisp的一个方言,Scheme。我们之所以选择Lisp,是因为它有许多独特的特征,其中最重要的是:计算过程的Lisp描述本身又可以作为Lisp的数据来表示和操作。

1.1 The Elements of Programming 程序设计的基本元素

语言的三种机制(要素):

  • 基本表达形式
  • 组合的方法
  • 抽象的方法
1.1.1 Expression 表达式
(+ 137 349)
(- 1000 344)
(* 5 99)
(/ 10 5)
  • 上面这样的表达式叫做组合式,构成方式为通过一个括号括起一些表达式,构成一个表,用于表示一个过程应用,表中最左边的元素称为运算符,其余均为运算对象。为了得到表达式的值,我们只需要将由运算符刻画的过程应用于有关的实际参数上。

将运算符放在运算对象左边,这种形式被称为前缀表示。前缀表示的优点:

  1. 适用于可能带任意个实参的过程。
  2. 可以直接扩充,允许组合式的嵌套。
1.1.2 Naming and the Environment 命名和环境
  • 程序设计需要提供一种通过名字标识符去使用计算对象的方式,就是我们说的变量,他的值就是它所对应的那个对象。
  • 在Lisp的Scheme方言里,通过define来给事物命名。
  • 我们可以将值与符号相关联,之后又能提取出这些值,这说明解释器需要维护某种存储能力,这种存储就是环境。
1.1.3 Evaluating Combinations 组合式求值

要对组合式进行求值,需要:

  1. 求值该组合式的各个子表达式
  2. 将作为最左表达式(运算符)的值的那个过程应用于相应的实际参数
  • 为了实现对一个组合式的求值,我们们必须先对组合式里的每个元素求值(本质上也是同样的求值过程),所以从本质上说这个过程是递归的。
  • define不属于组合式,是一种特殊情况,每种特殊情况都有其独特的计算规则。
1.1.4 Compound Procedure 复合过程

Lisp中的一些元素:

  • 数和运算是基本的数据和过程。
  • 组合式的嵌套让我们可以把多个操作组织到一起。
  • 定义是一种受限的抽象手段,它为名字关联相应的值。

过程定义,是一种更强大的抽象技术,它使我们可以为复合操作提供名字,而后就可以将这样的操作作为一个单元使用。

定义“平方”这一过程:

(define (square x) (* x x))

这就是一个复合过程,它的名字为square。
过程定义的一般形式如下:

(define (<name> <formal parameters>) <body>)

可以用square作为基本构件去定义其他的过程:

(define (sum-of-squares x y) (+ (square x) (square y)))

现在我们还可以用sum-of-squares作为构件,去进一步构造其他过程:

(define (f a) (sum-of-squares (+ a 1) (* a 2)))
1.1.5 The Substitution Model for Procedure Application 过程应用的代换模型
  • 据1.1.3中的描述:解释器首先对运算符和各个对象求值,而后将得到的过程应用于得到的实际参数, 我们称之为应用序求值
  • 但是还有另外一种求值的方法:先不求出运算对象的值,直到实际需要它们时再去求。这样做的话,有些表达式会进行多次求值,这种“完全展开而后归约”的求值模型被称为正则序求值
  • Lisp采用应用序求值,这样能避免对表达式的重复求值,从而提高效率。
1.1.6 Conditional Expressions and Predicates 条件表达式和谓词

条件表达式的一般形式:

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

表达式会按顺序求值谓词,直到得到真,此时就返回相应字句中表达式的值。如果无法找到为真的谓词, cond的值就没有定义。不过如果我们写了else,则在找不到表达式为真的字句时,就返回序列表达式<e>的值。

还有一种特殊形式if,用于只有两种情况的分情况分析。
(if <predicate>
    <consequent>
    <alternative>)

解释器首先计算<predicate>,如果它是真的,解释器然后计算<consequent>然后返回它的值,否则,计算并返回<alternative>。

  • 还有一些逻辑复合运算符,利用它们可以构造出复合谓词,最常用的三个复合运算符:and, or, not
  • cond,if,and,or,not都属于”special from”
1.1.7 Example: Square Roots by Newton’s Method 实例:牛顿法求平方根
  • 在数学中,大家通常关心的是说明性的描述(是什么),但在计算机科学中,大家关心的是行动性的描述(怎么做)。
1.1.8 Procedures are Black-Box Abstractions 过程作为黑盒抽象
  • 局部名
  • 内部定义
  • 块结构

1.2 Procedures and the Processes They Generate 过程与它们所产生的计算

  • 拥有能看清所考虑的动作的后果的能力,我们才能够学会如何去构造可靠的程序,使其表现出预期需要的行为。
  • 一个过程也就是一种模式,它描述了一个计算过程的局部演化方式,描述这一计算过程中的每个步骤是如何基于前面的步骤建立起来的。
  • 这一节将考察由一些简单过程所产生的计算过程的“形状”,还将考察这些计算过程消耗各种计算资源(如时间和空间)的速率。
1.2.1 Linear Recursion and Iteration 线性的递归和迭代
  • 迭代计算过程就是那种状态可以用固定数目的状态变量描述的计算过程,同时又存在一套固定的规则来描述计算过程从一个状态到下一个步骤转换时这些变量的计算方式。还可能有一个结束检测,它描述了这一计算应该终止的条件。
  • 迭代在计算过程的任何一点都有变量提供了关于计算状态的一个完整描述,而递归过程里还有一些“隐藏”信息由解释器维持着,指明“这一计算过程走到了哪一步”。
  • 尾递归:在常量空间中执行迭代计算,即使这个计算的描述是递归的。
1.2.2 Tree Recursion 树形递归
  • 树形递归示例:菲波那契数列
  • 这是一个造成巨大浪费的算法,因为做了很多重复计算..
  • 但当我们考虑的是在层次结构性的数据上操作,而不是对数操作时,树形递归计算过程就是强大的工具。如1.1.3里面的求值表达式用的就是树形递归计算。
1.2.3 Orders of Growth 增长的阶
  • 一般而言,总存在着某个有关问题特性的数值,使我们可以相对于它去分析给定的计算过程。
  • 增长的阶提供了对计算过程行为的一种很粗略的描述。
1.2.4 Exponentiation 求幂
  • 定义一个不变量,要求他在状态转移时候保持不变,这是迭代算法设计时的一个非常有用地方法。
  • 例子:求幂运算,快速幂算法。
1.2.5 Greatest Common Divisors 最大公约数
  • 求最大公约数:欧几里德算法。
  • 定理:如果欧几里德算法需要用k步计算出一对整数的GCD,那么这对数中较小的那个数必然大于或等于第k个斐波那契数。
1.2.6 Example: Testing for Primality 实例:素数检测
  • 素数检测:Miller-Rabin 素数测试。

1.3 Formulating Abstractions with Higher-Order Procedures 使用高阶过程(函数)做抽象

  • 前面已经引入了过程作为抽象,使得能够描述对于数的复合操作,但又不依赖与特定的数。例子就是求立方。
  • 但求立方并没有表达立方这一概念。
  • 这样我们只能在语言提供的基本操作上去建立过程,而不能基于高级的操作去建立过程。
  • 所以我们需要更强大的抽象:以过程作为参数或返回值。用于表示一般的方法,与特定功能无关。
1.3.1 Procedures as Arguments 过程作为参数

一个表达求和概念本身的过程:(不仅仅是计算特定和)

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))
1.3.2 Constructing Procedures Using lambda 使用lambda构造过程

lambda用于以与define相同的方式建立过程,不同之处在于没有为该过程指定名称:

(lambda (<formal parameters>)
  <body>)

let表达式:

(let ((<var1> <exp1>)
      (<var2> <exp2>)
      ...
      (<varn> <expn>))
  <body>)

let表达式可被下面lambda表达形式所替代:

((lambda (<var1> ... <varn>)
    <body>)
  <exp1>
  ...
  <expn>)

这样,解释器就不需要为局部变量增加任何新机制,let表达式只是lambda表达式的语法糖而已。

  • let使得我们能够在尽可能接近其使用的地方建立局部变量约束,变量的值是在let之外计算的。
1.3.3 Procedures as General Methods 过程作为一般方法

一些例子介绍上文介绍的”更强力的抽象”,用于表达计算的一般性过程,与其中所涉及的特定函数无关。

  • 区间折半寻找方程的根
  • 找出函数的不动点
1.3.4 Procedures as Returned Values 过程作为返回值

上面例子说明,将过程作为参数传递,能够大大增强我们语言的表达能力。

下面我们创建返回值本身也是过程的过程,表达能力还能进一步增强。

  • 牛顿法

一般来说,程序设计语言总会对计算元素的可能使用方式加以限制,限制最少的元素成为“第一级元素”,他们的“特权”有:

  1. 可以用变量命名;
  2. 可以提供过程作为参数;
  3. 可以把过程作为结果返回;
  4. 可以包含在数据结构中;

这本书使用的Lisp语言给了过程完整的“第一级状态”,所以拥有“惊人”的描述能力。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注