1.1 程序设计的基本元素¶
编程语言的三种机制：基本表达形式、组合方法、抽象方法。
在程序设计中要处理两类要素：过程和数据，实际上两者并不严格区分，用于构造过程的规则同样适用于操作各种数据。
1.1.1 表达式¶
前缀表达式-将运算符放在所有运算对象的左边, 完全适用于带有任意个实参的过程, 可以直接扩充, 允许出现组合式嵌套的情况。
读入-求值-打印循环
(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))
1.1.2 命名环境¶
使用 define 进行变量命名。
为存储值与变量名的关联, 解析器必须维护某种存储能力, 此即为环境。
(define pi 3.14159)
(define radius 10)
(define circumference (* 2 pi radius))
1.1.3 组合式的求值¶
组合式的求值是一个递归的过程:
求值该组合式的各个子表达式。
将作为最左边表达式(运算符)的值的那个过程应用于相应的实际参数, 而这些参数即为其它子表达式(运算符)的值。
define 作为一个求值规则的特殊形式, 并不是将实际参数作用于 define, 而是为第一个参数(变量)关联第二个参数(值)。
1.1.4 复合过程¶
(define (square x) (* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
1.1.5 过程应用的代换模型¶
正则序求值-完全展开而后规约。
应用序求值-先求值参数而后应用。
应用序和正则序的不同，Lisp采用应用序以避免对表达式的重复求值
1.1.6 条件表达式和谓词¶
;; (cond (<p1> <e1>)
;; (<p2> <e2>)
;; ...
;; (<pn> <en>))
(define (abs x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x))))
(define (abs x)
(cond ((< x 0) (- x)
(else x))))
;; (if <predicate> <consequent> <alternative>)
(define (abs x)
(if (< x 0)
(- x)
x))
练习 1.1¶
> 10
10
> (+ 5 3 4)
12
> (- 9 1)
8
> (/ 6 2)
3
> (+ (* 2 4) (- 4 6))
6
> (define a 3)
a
> (define b (+ a 1))
b
> (+ 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 a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
所以应该是: 返回其中较大两个数的平方和
;; 定义求最小值的函数, 采用 if 方式实现
(define (min-num a b c)
(if (< a b)
(if (< a c) a c)
(if (< b c) b c)))
;; 利用前面的函数和 cond 表达式实现
(define (sum-max a b c)
(cond ((= (min-sum a b c) a) (sum-of-squares b c))
((= (min-sum a b c) b) (sum-of-squares a c))
(else (sum-of-squares a b))))
练习 1.4¶
给出的函数实现的功能是: 接受两个参数, 返回第一个参数与第二个参数绝对值的和
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
练习 1.5¶
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
对于应用序, “先对参数求值然后应用”, 则对 p 的调用将会陷入死循环;
对于正则序, “完全展开而后进行规约”, 则对 test 展开时对 if 语句判断为真后直接返回 0, 从而避免了对 p 的调用。
1.1.7 实例: 采用牛顿法求平方根¶
(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 (- (squre guess) x)) 0.0001))
(define (squre x)
(* x x))
(define (sqrt x)
(sqrt-iter 1.0 x))
练习 1.6¶
对于自定义的 new-if, 根据 Lisp 的应用序求值原则, 不论 predicate 真假, 两个参数 then-clause 、 else-clause 都会被求值, 这样将会导致陷入对 sqrt-iter 的递归调用, 进而因递归调用的栈深度超过阀值而导致程序崩溃。
练习 1.7¶
在被求值的数很小或很大时，因为变化程度很小会导致程序进入死循环
修改后的程序如下:
(define (sqrt-iter old_guess new_guess x)
(if (good-enough? old_guess new_guess)
new_guess
(sqrt-iter new_guess (improve new_guess x) x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? old_guess new_guess)
(< (/ (abs (- old_guess new_guess))
old_guess)
0.0001))
(define (squre x)
(* x x))
(define (sqrt x)
(sqrt-iter 1.0 (improve 1.0 x) x))
练习 1.7¶
仿照实例中的实现以及上一题目中的改进之处
(define (square x) (* x x))
(define (cube x) (* x x x))
(define (good-enough old_guess new_guess)
(< (/ (abs (- old_guess new_guess))
old_guess)
0.0001))
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (cube-root-iter old_guess new_guess x)
(if (good-enough old_guess new_guess)
new_guess
(cube-root-iter new_guess (improve new_guess x) x)))
(define (cube-root x)
(cube-root-iter 1.0 (improve 1.0 x) x))
1.1.8 过程作为黑箱抽象¶
一个问题可以分解成若干个子问题, 而这些子问题因为可以清楚标明自身的工作, 因此可以构成定义其它过程的模块。
一个过程的定义应该能隐藏具体实现的细节, 使得调用者不必自己去实现这些过程, 而是作为一个黑箱接受它。
过程的形式参数作为约束变量, 作用域为定义过程的过程体。
使用内部定义和块结构使子过程局部化, 避免与过程外的环境发生冲突。
(define (average x y)
(/ (+ x y) 2))
(define (sqrt x)
(define (good-enough? guess x)
(< (abs (- (squre 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))