SICP-1.1程序设计的基本元素

每一种强有力的语言都为此提供三种机制:

  • 基本的表达形式,用于表示语言所关心的最简单的个体。
  • 组合的方式,通过它们可以从较简单的东西出发构造出复合的元素。
  • 抽象的方法,通过它们可以为复合对象命名,并将它们当作单元去操作。
    在程序设计中,我们需要处理两类要素:过程和数据。而这两者并不是严格分离的,数据是一种我们希望去操作的东西,而过程是有关操作这些数据的规则的描述。这样,任何强有力的程序设计语言都必须能表述基本的数据和基本的过程,还需要提供对过程和数据进行组合和抽象的过程。

1.1.1 表达式

Scheme中的基本表达式就是数:456、3、8…,解释器则会输出你键入的数的值:456、3、8…。

组合式:用表示过程的表达形式,将表示数的表达式组合起来,形成复合表达式。构成方式就是用一对括号括起一些表达式,形成一个表,表里最左边的元素是运算符,其它元素为运算对象。比如:

1
2
3
(+ 137 349)
(* 3 5 8)
(- 4 9 8 76)

这种将运算符放在所有运算对象左边的形式称为前缀表示。这种形式的一大好处就是适用于带有任意个实参的过程,表里右边的运算对象可以是任意个。
前缀表示的另一个有点就是可以直接扩充,允许出现组合式嵌套的情况,而且嵌套深度没有限制:

1
(/ (* (+ 4 6) (- 97 32)) (+ 98 78))

1.1.2 命名和环境

变量:名字标识符,它的值就是它所对应的那个对象。
Scheme中通过define命名变量:

1
2
3
4
5
6
7
8
9
10
11
(define time 30)
age
30
(* age 2)
60
(define distance 100)
distance
100
(define speed (/ distance time))
speed
10/3

任何一个复杂的程序都是由一个个简单的过程组成的,通过创建一个程序所需要的名字-对象关联,就可以一步步创建越来越复杂的计算性对象或过程,进而构造一个复杂的程序。

而解释器为了保持名字 – 对象关联,需要维护某种存储能力,这就被称为环境,更准确的说叫做全局环境,而在一个计算过程中,完全可能涉及不同的环境。

1.1.3 组合式的求值

解释器是按照下面的过程求值一个组合式的:

  1. 求值该组合式的各个子表达式。
  2. 将作为最左子表达式(运算符)的值的那个过程应用于相应的实际参数,也就是其它子表达式(运算对象)的值

而一个深度嵌套的组合式的求值过程,就是在各个子表达式中不断的重复上面的两个过程。这种在自己的计算步骤中,包含了调用这个计算规则本身的需要,这一求值过程就是递归

1
2
(* (+ 2 (* 4 6))
(+ 3 5 7))

可以用树形来表示上面这一组合式的求值过程,这种“值向上穿行”形式的求值过程被称为树形积累

IMG_2396

1.1.4 复合过程

过程定义:可以给某一复合操作过程提供名字,而后可以通过这个名字将这一复合操作作为一个单元使用了。比如定义一个“平方”操作过程:

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

过程定义的一般形式是:

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

name是关联的过程名字,formal parameters是形式参数,可以有多个,body是具体的操作过程。
也可以将定义好的过程作为基本构件去定义其它过程:

1
2
(define (sum-of-square x y) 
(+ (square x) (square y)))

1.1.5 过程应用的代换模型

对于复合过程,过程应用的计算过程是:将复合过程应用于实际参数,就是在将过程体重的每个形参用相应的实参取代之后,对这一过程体求值。

这种计算过程称为过程应用的代换模型

解释器首先对运算符和各个运算对象求值,而后将得到的过程运用于得到的实际参数,这种先求值参数而后应用的方式称为应用序求值

先不求出运算对象的值,而是用运算对象表达式去代换形式参数,直到得到一个只包含基本运算符的表达式,然后再去求值。这种“完全展开而后归约”的求值模型称为正则序求值

Scheme解释器里用的是应用序求值,部分原因在于能避免对于表达式的重复求值,但某些时候,正则序求值也会非常有用,后面的章节会讲到。

1.1.6 条件表达式和谓词

条件表达式的一般性形式为:

1
2
3
4
5
6
(cond (<p1> <e1>)
(<p2> <e2>)
(<p3> <e3>)
.
.
(<pn> <en>))

其中

是谓词,是一个表达式,它的值会被解释为真或假(Scheme中#t为真,#f为假)。
上述形式中,会按顺序求值谓词p,直到求出的值为真,然后计算序列表达式e的值,并返回该值。如果没有找到值为真的p,cond的值则没有定义。

另外可以通过else返回一个绝对值:

1
2
3
(cond (<p1> <e1>)
(<p2> <e2>)
(else x))

另外也可以使用if

1
2
(if <predicate> <consequent> <alternative>)
;if 可以省略else

Scheme采用的特殊形式的if,在求值时,解释器会先求值predicate,如果为真,再去求值consequent,否则就是求值alternative。而不是采用应用序求值方式,先对所有参数求值,再进行计算。这一点需要特别注意。

基本的谓词有><=,逻辑运算符有:

  1. 逻辑与:(and \…\)
  2. 逻辑或:(or \…\)
  3. 逻辑非:(not \)

具体的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (abs x)
(cond ((> x 0) (- x))
((= x 0) 0)
((< x 0) x)))

(define (abs x)
(cond ((> x 0) (- x))
(else x))

;两个abs等价的

(define (compare x)
(if (< x 0)
(- x)
x))

1.1.8 过程作为黑箱抽象

1.1.7中的求平方根的问题,我们分为了若干个子问题,每一个子问题的解决过程都进行了定义,并将这些子过程的定义用作定义其它过程的模块。这样在使用一个过程定义时,这个定义内部的计算细节就被隐藏,也无需关注,我们只需要知道它能做的事即可。比如square,我们只需要知道它能计算一个数的平方,而不需要知道它是如何计算的。这就是一个过程的抽象,在这一抽象层次上,任何能计算出平方的过程都可以用。

在这些过程抽象中,我们使用到了一些参数,比如xguess,这些都是形式参数,这些形式参数只在这一抽象的过程中有效,它们被称为约束变量,整个过程体就是这些形参的作用域。

如果一个变量不是被约束,我们就称它为自由的。比如squareimprove guessabs这些就是自由的,在任何过程体中都是有效的。

之前我们已经定义了improve guess, good-enough?等过程抽象,但其实我们目前定义的这些只是用来辅助计算sqrt的,但因为它们都是自由的,如果其它的计算过程也需要这样的辅助,但计算过程不一样,就得定义不一样的名字。这样就很容易在定义过程时造成命名混乱,而且这些过程都是辅助特定的计算过程的,现在这样独立定义出来,也会影响代码的可读性。因此我们可以把这些定义放入sqrt过程内部,变成一个约束变量、内部定义。

1
2
3
4
5
6
7
8
9
10
(define (sqrt x)
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.0001))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 x))

又因为x在整个sqrt过程体中都是有效的,没有必要再在内部传递,可以直接用作实际参数,因此这个过程定义又可以简化为:

1
2
3
4
5
6
7
8
9
10
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.0001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
坚持原创技术分享,您的支持将鼓励我继续创作!