sp 构造过程抽象

解释器本身是按照下面的过程工作的

要求值一个组合式,做下面的事情:

  • 求值该组合表达式的各个子表达式
  • 将作为最左子表达式(运算符)的值的那个过程应用于相应的实际参数,所谓实际参数也就是其他子表达式(运算对象)的值
1
(* (+ 2 (* 4 6 ))
2
	(+ 3 5 7 ))

为了实现对一个组合式的求值过程,我们必须先对组合式里的每个元素执行同样的求值过程,因此,在性质上,这一求值过程是递归的,就是说,它在自己的工作步骤中,包含着调用这个规则本身的需求

1585359759171

一般而言,我们应该把递归看做一种处理层次性结构(像树这样的对象)极强有力的技术,“值向上穿行”形式的求值形式是一类更一般的计算过程的例子,这种计算过程成为树形积累

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

环境所扮演的角色就是用户确定表达式中各个符号的意义

复合过程

任何强有力的程序设计语言都有如下特点

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

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

1
(defun square (x) (* x x ))

过程定义的一般形式是:

1
(defub <name> (<formal parameters>) (<body>))
1
Break 5 [6]> (square 12)
2
144
3
Break 5 [6]> (square (+ 2 5))
4
49
5
6
Break 8 [9]> (+ (square (+ 2 5)) 3)
7
52

平方和:

1
(defun sum-of-squares(x y)
2
	(+ (squrare x) (square y)))
1
Break 9 [10]> (defun sum-of-squares(x y)
2
(+ (square x) (square y)))
3
SUM-OF-SQUARES
4
Break 9 [10]> (sum-of-squares 3 4 )
5
25
过程应用的代换模型
1
(dufun f (a) (sum-of-squares (+ a 1) (* a 2)))
2
3
Break 10 [11]> (defun f (a) (sum-of-squares (+ a 1) (* a 2)))
4
F
5
6
(sum-of-squares (+ a 1) (* a 2))
7
(sum-of-squares (+ 5 1) (* 5 2))
8
(+ (square 6) (square 10))
9
(+ 36 100)
10
136
11
12
Break 10 [11]> (f 5)
13
136

上面描述的过程成为代换模型,注意:

  • 代换模型的作用只是为了帮助我们领会过程调用中的情况,而不是对解释器实际工作方式的具体描述,通常的解释器都不采用直接操作过程的正文,用值代换形式参数的方式取完成对过程调用的求值。在实际中, 他们一般采用提供形式参数的局部环境的方式,产生代换效果
应用序和正则序
  • 在上面的例子中,解释器首先对运算符和各个运算对象求值,而后将得到的过程应用于得到的实际参数
  • 另一种求值模型是先不求出运算对象的值,直到实际需要他们的值时再去做,采用这种求值方式,我们就应该受限运算对象表达式去代换形式参数,直到得到一个只包含一个基本运算符的表达式,然后再去执行求值
1
(sum-of-squares (+ 5 1) (* 5 2))
2
( + (square (+ 5 1)) (square (* 5 2)) )
3
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
4
归约
5
(+  (* 6 6) (* 10 10 ))
6
(+ 36 100)
7
136

这种“完全展开而后约”的求值模型成为正则序求值,与之对应的是现在解释器里实际使用的”先求值参数而后应用“的方式,称之为应用序求值

Lisp采用应用序求值,部分原因在于这样做能够避免对于表达式的重复求值,从而可以提高一些效率

条件表达和谓词

求一个数的绝对值

|x| = { x 如果x>0 ; 0 如果x=0;-x 如果x<0}

这种结构称为分情况分析

cond

1
(defun abs-a (x)
2
  (cond ((> x 0) x)
3
  		((= x 0) 0)
4
  		((< x 0) (-x)))
5
)
6
7
(defun abs-b (x) 
8
    (cond ((< x 0) (-x))
9
    		(else x )))
10
11
(defun abs-c (x)
12
    (if (< x 0)
13
        (-x)
14
        x))

if, 是条件表达式的一种受限形式,适用于分情况分析中只有两个情况的需要,if表达式的一般形式是

1
(if <predicate> <consequent> < alternative>)

逻辑复合运算符

1
(and <e1> <e2> <e3>)
1
(or <e1> <e2> <e3>)
1
(not <e>)

练习举例:

1
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5 ))))) (* 3 (- 6 2) (- 2 7)))
1
(defun (p) (p))
2
(defun test (x y)
3
    (if (= x 0 )
4
        0
5
        y))

在数学里,人们通常关心的是说明性的描述(是什么), 而在计算机科学里,人们则通常关心行动性的描述(怎么做)

牛顿法求平方根
1
(defun average(x y) 
2
	(/ (x + y ) 2)
3
)
4
5
(defun improve (guess x)
6
	(average(guess (/ x guess)))
7
)
8
9
(defun good-enough? (guess x) 
10
	(< (abs (- (square guess) x)) 0.001)
11
)
12
13
(defun sqrt-iter (guess x)
14
	(if goog-enough? ( guess x)
15
		guess
16
		(sqrt-iter (improve( guess x))
17
					x)
18
		)
19
	)
20
)
21
22
(defun sqrt (x) 
23
	(sqrt-iter 1.0 x)
24
)