SICP学习笔记-前言与程序设计的基本元素

前言

这本书所要讨论的问题都要涉及到三类需要关注的对象：人的大脑、计算机程序的集合以及计算机的本身。每一个计算机程序都是现实中或者精神中某个过程的模型。

心智活动，除了尽力产生各种简单的认识之外，主要表现在如下三个方面：

  • 将若干简单的认识组合为一个复杂的认识，由此产生各种复杂的认识。
  • 将两个认识放在一起对照，不管他们是如何简单或者复杂，在这样作时并不是将他们合而为一。而是由此得到他们之间相互关系的认识。
  • 将有关认识与那些在实际中和他们同在的所有其他认识隔离开，这就是抽象，所有具有普遍性的认识都是这样得到的。

这本书主要讲解的有关计算过程的知识，这些过程回去操作一些被称为数据的抽象事物。

程序设计的基本元素

  • 基本表达形式 ：用于表达语言所关心的最简单的个体；
  • 组合的方法 ：通过他们可以从较简单的东西出发构造出复合元素；
  • 抽象的方法 ：通过他们可以为复合对象命名，并将他们当作单元去操作。

在程序设计中，需要处理两类要素：过程和数据。从形式上面说，数据是一类我们希望去操作的东西，而过程就是有关操作这些过程的描述。

表达式

在电脑终端前面用键盘输入一个表达式，解释器的相应就是他对这一求值结果的显示。

组合式：用一个括号扩起来的一些表达式，行成的一个表，用于表示一个运算过程，例如(* 4 5)表示 4*5。其中表中最左变的元素如例子中的*号表示运算符。其他元素都被称为运算对象。要得到这种组合式的值，采用的方式就是将运算符所刻画的运算过程应用于有关的实际参数（运算对象的值）。

命名和环境

变量：通过名字去命名变量的方式，将名字标识符称为变量。在scheme中通过下面方法定义(define size 2)。

环境：解释器维护某种存储的能力，及将值与符号相关联然后又能通过这个符号提取这个值。

组合式的求值

解释器本身是按照下面过程工作：要求值一个组合式。

  1. 求值该组合式各子表达式的值。
  2. 将运算符的值应用与相应的实际参数（其他子表达式的值）。

反复应用第一个步骤可以将我们带到求值过程中的某一点，在这里遇到的不是表达式而是基本表达式，例如数、运算符、或者基本表达式。处理这些基本情况安下面方式处理。

  • 数的值就是他们表示的数值；
  • 内部运算符的值就是能完成对应操作的计算机指令序列；
  • 其他名字的值就是在环境中关联这一名字的对象；

复合过程

lisp的基本元素，他们也必然会出现在任意一种强有力的设计语言中，这些东西包括：

  • 数和算数运算是基本的数据和过程；
  • 组合式和嵌套提供了一种组织起多个操作的方法；
  • 定义是一种受限的抽象手段，他为名字关联相应的值。

过程定义 ：通过它可以为复合操作提供名字，并将这样的操作作为一个单元使用。过程定义的一般形式如下：

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

这里可以将理解成为函数名，理解成为函数入参，理解为函数体。

过程应用的代换模型

对于复合过程，过程应用的计算过程如下

将复合过程应用与实际参数，就是在将过程体中的每个形参用相应的实参取代之后，对这一过程的求值。

代换模型需要强调两点：

  • 代换的作用是帮助我们领会过程调用中的情况，而不是对解释器实际的工作方式的具体描述。通常的解释器都不采用直接操作过程的正文，用值去代换形式参数的方式去完成对具体过程的求值，在实际中他们一般采用提供形式参数的局部环境的方式，产生“代换”的效果。
  • 后面将给出解释器如何工作的一系列模型，一个比一个更加精细。这里描述的代换模型只是这些模型中的第一个。

应用序和正则序

  • 正则序求值 ：先完全展开而后归约
  • 应用序求值 ：先求参数值而后应用（lisp采用的求值方式）

条件表达式和谓词

如求x的绝对值可以用下面代码表示：

1
2
3
4
(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

这里第一个表达式称为谓词，表示这是一个表达式，它的值将被解释为真或者假。表达式的工作可以解释为先求值第一个谓词，如果它的值是false，那么就求解下一个谓词，直到发现一个为true的谓词。此时解释器就返回相应句子中的表达式的值。

求x的绝对值的另两种写法

1
2
3
(define (abs x)
  (cond ((> x 0) x)
        (else (- x))))
1
2
3
4
(define (abs x)
  (if (< x 0)
      (- x)
      x))

除了上面的这些还有一些复合运算符and or not对应与C语言中的&& || !。

example：采用牛顿法求平方根

数学函数和计算机过程中又一个重要的差异，那就是，这一过程必须有效可行。函数与过程之间的矛盾，不过是在描述一件事情的特征，与描述如何去做这个事情之间的普遍性差异的一个具体反映。换一种说法，人们有时也将它说成是说明性的知识与行动性知识之间的差异。在数学里，人们常常关心的是说明性的描述（是什么），而在计算机科学里，人们则通常关心行动性的描述（怎么做）。

牛顿法求平方根，对x的平方根有一个猜测y，可以通过循环求出y和x/y的平均值来求2的平方根。求解代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(define (sqrt x)
  (sqrt_iter 1.0 x))

(define (sqrt_iter guess x)
  (if (good_enough? guess x)
      guess
      (sqrt_iter (improve guess x)
                  x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good_enough? guess x)
  (< (abs (- (* guess guess) x)) 0.001))

(sqrt 2)

过程作为黑箱抽象

前面的的求平方根的过程描述了，从原问题到子问题的一个分解过程。

约束变量：形式参数的名字是什么完全没有关系。一个过程的定义约束了它所有的形式参数。如果在一个完整的过程定义里将某个约束变量统一换名，这一过程定义将不会有任何改变，这个过程体叫做这个变量的 作用域。

  • 局部名：过程中的形式参数是相应过程体里的局部名字。
  • 内部定义和块结构：嵌套的定义过程，理解为类中的方法。示例如下：
1
2
3
4
5
6
7
8
9
10
11
(define (sqrt x)
  (define (good_enough? guess)
    (< (abs (- (* guess guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt_iter guess)
    (if (good_enough? guess))
        guess
        (sqrt_iter (improve guess)))
  (sqrt_iter 1.0)
)

这里将x作为内部定义中的自由变量，这样在外围的sqrt被调用时，x由实际参数得到自己的值。这种方法被称为 词法作用域 。