1.1 程序设计的基本元素
1.1.1 表达式
数
数是一种最基本的表达式
> 486
486
过程
过程（内置运算符或函数）是另一种基本表达式，例如：
+-*/
组合式
- 过程和数可以组合成组合式
- 组合式中的第一个元素（最左边）总是过程：
(+ 137 349)
嵌套表达式
如果组合式的元素也是组合式，他就是嵌套表达式
(+ (* 3 5) (- 10 6))
代码格式
书写代码的时候要注意换行和缩排
(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))
1.1.2 命名和环境
命名
命名将一个名字和一个对象关联起来，命名是一种最基本的抽象
;将名字 size 和数字 2 关联起来
> (define size 2)
> size
2
> (* 5 size)
10
环境
名字保存在环境中，不同环境中的名字互不干扰
1.1.3 组合式求值
求值过程
对组合式求值是一个递归过程
- 先求值各个子表达式
- 将求出的值作为参数应用到过程
- 如果子表达式也是组合式，重复这一流程
如下表达式
(* (+ 2 (* 4 6))
(+ 3 5 7))
可用下图中的树表示，递归特别适合处理像树这样的层次性结构
表达式也可以用树表示
环境和求值的关系
内置运算符也是一种名字，和普通名字没太大区别，只不过他们是存在于全局环境中，并且已经关联到对应的指令序列上而已
环境为求值提供了上下文，没有环境，求值就没有意义
特殊形式 define
define 是一种特殊的形式，和一般的求值规则有所不同
1.1.4 复合过程
定义复合过程
所谓的复合过程就是创建自定义的新过程
> (define (square x) (* x x))
上面的 define 创建了一个过程对象，并将这个对象和名字 square 相关联
使用复合过程
我们可以像使用内置过程一样使用复合过程：
> (square 21)
441
> (square (+ 2 5))
49
> (square (square 3))
81
用复合过程定义复合过程
对解释器来说，复合过程和内置过程完全一样，因此可以用复合过程继续定义新的复合过程
> (define (sum-of-squares x y)
(+ (square x) (square y)))
> (sum-of-squares 3 4)
25
继续复合
> (define (f a)
(sum-of-squares (+ a 1) (* a 2)))
> (f 5)
136
1.1.5 过程求值的代换模型
过程求值有两种代换模型：
- 应用序
- 正则序
下面让我们分析一下组合式 (f 5) 求值的代换过程
应用序代换
- 总是先求值参数
- 全部参数求值为基本表达式（即数值）后，开始求值过程名
- 如果参数是一个组合式，则对其求值过程同样遵循应用序代换
应用序代换过程
正则序代换
- 总是现求值过程名
- 过程名求值为基本过程（即内置运算符）后，开始求值参数。
- 如果参数是一个组合式，则对其求值过程同样遵循正则序代换
正则序代换过程
1.1.6 条件表达式和谓词
到目前为止，我们能够自定义的复合过程表达能力还非常有限，我们需要条件表达式
条件表达式
(cond (p1 e1)
(p2 e2)
......
(pn en)
(else e))
条件表达式也是一种特殊形式，因为他不会对全部参数求值。只要检测到了为真的条件，他就会返回条件对应的表达式，之后的参数不会再检测
谓词
谓词就是返回真或者假的过程，常见的谓词有：
><=
if 语句
if 语句只有一个判断条件，为真返回表达式 1，为假返回表达式 2
逻辑运算
-
(and e1 e2 ...... en)，检测到一个为假，则返回假；否则返回最后一个表达式的值 -
(or e1 e2 ...... en)返回第一个检测到的为真的表达式的值，如果全部为假则返回假 (not e)
注意：
and和or是特殊形式，因为他们没有对所有的参数进行求值
练习 1.1
按顺序求值下面的表达式
> 10
10
> (+ 5 3 4)
12
> (- 9 1)
8
> (/ 6 2)
3
> (+ (* 2 4) (- 4 6))
6
> (define a 3)
> (define b (+ a 1))
> (+ a b (* a b))
19
> (= a b)
#f
> (if (and (> b a) (< b (* a b)))
b
a)
4
> (cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
16
> (+ 2 (if (> b a) b a))
6
> (* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
16
练习 1.2
将下面的数学公式转化成前缀表达式
> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7)))
-37/150
练习 1.3
定义一个过程，他有三个参数，返回其中较大的两个数的平方和
;;;求两个数的平方和
(define (sum-of-squares x y)
(+ (* x x) (* y y)))
;;;计算三个数中两个较大的数的平方和
(define (bigger-sum-of-squares x y z)
(cond ((and (< x y) (< x z)) (sum-of-squares y z))
((and (< y x) (< y z)) (sum-of-squares x z))
(else (sum-of-squares x y))))
> (bigger-sum-of-squares 6 3 4)
52
> (bigger-sum-of-squares 1 2 3)
13
> (bigger-sum-of-squares 3 7 5)
74
sumOfSquares x y = x*x + y*y
biggerSumOfSquares x y z
| (x > y) && (y > z) = sumOfSquares x y
| (x > y) && (z > y) = sumOfSquares x z
| otherwise = sumOfSquares y z
练习 1.4
描述下面这个自定义过程的求值步骤
;;;过程定义
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
下面是求值步骤：
;;;调用
(a-plus-abs-b 10 99)
109
;;;参数已经是基本表达式了，求值过程名得到
((if (> 99 0) + -) 10 99)
109
;;;参数已经是基本表达式了,求值过程表达式得到
(+ 10 99)
109
练习 1.5
下面的过程可以判断出你的解释器是正则序还是应用序，解释其中的原理
;;;定义 1
(define (p) (p))
;;;定义 2
(define (test x y)
(if (= x 0)
0
y))
解释如下：
;;;求值表达式 (test 0 (p))
;;;对于应用序 -----------------------------
> ;;;首先求值参数，得到
(test 0 (p))
;;;接下来会不断的求值 (p)，导致死循环
;;;对于正则序 -----------------------------
> ;;;首先求值过程名，得到
(if (= 0 0)
0
(p))
0
;;;if 语句：因为条件满足，所以只求值第一个表达式，返回 0；表达式 (p) 不会被求值
1.1.7 实例：采用牛顿法求平方根
到目前为止，我们学习的内容已经可以完成一些简单的工作，比如下面求平方根的程序：
- 核心算法是不断迭代改进猜测值，直到足够好
- 将算法中一些小的计算分离出来，作为辅助函数
- 没有其他语言中的循环语句，但是仍然完成了迭代
#lang racket
;;;开方
(define (sqrt x)
(sqrt-iter 1.0 x))
;;;开方算法：
;;;1. 如果猜测值足够好，则返回猜测值；
;;;2. 否则改进猜测值，然后迭代该过程
;;;参数：猜测值和开方数
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
;;;判断足够好的算法
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
;;;改进猜测值的算法
(define (improve guess x)
(average guess (/ x guess)))
;;;下面是辅助函数-------------------------
;;;求平均数
(define (average x y)
(/ (+ x y) 2))
;;;求平方
(define (square x)
(* x x))
习题 1.6
下面是一个模仿 if 的自定义过程，但是他会导致死循环，为什么？
;; 6-new-if.scm
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
解答：
因为内置的 if 是一种特殊形式，特殊形式有自己的求值规则，if 的求值规则如下：
- 只有条件为假，
if才会求值第二个表达式，导致递归调用 - 如果条件为真，
if会求值第一个表达式，整个过程可以退出
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess ;;;条件为真时会从这里退出
(sqrt-iter (improve guess x) x)))
而自定义的 new-if 是一个函数，因此
- 按照函数求值规则，无论条件是真是假，他都会先对所有参数求值。而第二个表达式在这里仅仅是函数的一个参数
- 求值第二个表达式会导致递归调用，又会再次求值
new-if，导致死循环
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x))) ;;;无论条件是真是假，都会求值这个表达式，导致死循环
习题 1.7
之前求平方根的算法，对于非常大或者非常小的数可能会出错：
- 出错的原因是什么？
- 怎么改进？
解答：
首先看看 good-enough? 过程
;;;判断足够好的算法
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
这个算法认为，猜测数的平方与被开方数之间的差值小于 0.001 就是足够好，但是可能有下面两种情况：
- 对于非常小的被开方数，比如
0.0001，其本身已经小于判定差值，导致任意猜测数都是足够好 - 对于非常大的被开方数，比如
100000000000000000000000000000000000000，由于精度问题，永远不可能满足足够好的条件，导致死循环
改进算法
猜测数的改变量与旧的猜测数的比值小于一定范围，则认为是足够好
;;; 新的足够好算法
(define (good-enough? old-guess new-guess)
(> 0.01
(/ (abs (- new-guess old-guess))
old-guess)))
;;;由于足够好算法的参数发生了变化，因此主过程也要进行相应的改变
(define (sqrt-iter old-guess x)
(let ((new-guess (improve old-guess x)))
(if (good-enough? old-guess new-guess)
new-guess
(sqrt-iter new-guess x))))
练习 1.8
设计一个求立方根的过程，下面这个公式可以改进的猜测值
解答：
题目中给出的公式是改进猜测数的公式，有了这个公式，我们可以模仿求平方根的算法进行设计
;;;题目给出的公式就是改进猜测数的公式
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess))
3))
;;;给用户使用的接口
(define (cube-root x)
(cube-root-iter 1.0 x))
;;;主过程
(define (cube-root-iter guess x)
(if (good-enough? guess x)
guess
(cube-root-iter (improve guess x)
x)))
;;;检测足够好的过程
(define (good-enough? guess x)
(< (abs (- (cube guess) x))
0.001))
1.1.8 过程作为抽象黑箱
对于一个计算问题，我们一般都可以将他分解为若干个子问题，例如之前的求平方根算法：
但是，定义过程的目的不仅仅是为了分解，而是为了抽象，过程也是一种抽象。
为什么过程是抽象的？
黑箱
过程的使用者不会考虑过程内部的细节和使用的名字，这是一种抽象，也是一种隔离机制。
例如下面两个求平方根的过程，虽然内部使用了不同的算法，但是对使用者来说是没有区别的
(define (square x) (* x x))
(define (square x) (exp (double (log x))))
局部名
过程内部定义的名字（包括形参）都是局部的，其作用域只在过程体中，不会对外部造成影响。如果改变过程内部某个名字，过程的功能不会有任何改变。
下面的两个过程，参数名不同，但是对解释器来说，他俩是相同的：
(define (square x) (* x x))
(define (square y) (* y y))
约束变量和自由变量
过程内部的名字会被过程约束，因此这些名字也叫做约束变量。
而被过程使用，但是不被过程约束的名字就称作自由变量。例如：+ - * 这些全局名字
在过程内部使用自由变量，就说明过程对外部产生了依赖。因此，应该尽量少使用不标准的外部名字
内部定义和块结构
除了变量可以被约束在过程内部，辅助过程也可以被约束在主过程内部，这样的程序内聚性更好
下面改写求平方根的程序，将辅助过程定义在主过程内部
(define (sqrt x)
;;;是否足够好
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
;;;改进猜测值
(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 会被所有辅助函数使用
其实可以不用传来传去，直接使用即可。改进代码如下：
(define (sqrt x)
;;;是否足够好
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
;;;改进猜测值
(define (improve guess)
(average guess (/ x guess)))
;;;核心算法
(define (sqrt-iter guess)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
;;;迭代开始
(sqrt-iter 1.0))
注意：参数
x在这里成为了词法作用域（即主过程作用域）下的自由变量，辅助过程都会对x产生依赖，因此不要改变x（外部依赖）的值
