计算机程序的构造和解释

时光荏苒,程序生涯已度两年余。但构造程序的能力却不尽人意,遂迫切需要获取到构造程序的思维知识,以解目前堆积木式的开发方式的困境。看到书本中间有这么一句话"我们现在的情况就像是在学下象棋的过程中的一个阶段,此时已经知道了移动棋子的各种规则,但却还不知道典型的开局、战术和策略。",这句话非常切近目前的状态。

构造过程抽象

关于抽象的几点表象(John Locke - 有关人类理解的随笔.1690):

  • 将若干简单认知组合为一个复合认知,由此产生各种复杂的认知。
  • 将两个认知放在一起对照。不管它们如何简单或复杂,并不将它们合而为一。由此得到有关它们相互关系的认知。
  • 将有关知识跟那些在实际中和它们同在的所有其他人知隔离开。

计算过程、数据抽象和程序

"计算过程"是存在于计算机中的一类抽象事物,这些过程会去操作一些被称为"数据"的抽象事物。人们创建出一些称为"程序"的规则模式,以指导这类过程的进行。程序用一些程序设计语言,通过"符号表达式"的形式精心编排而成,它描述了希望相应的计算过程去完成的工作。

设计良好的计算系统应具有某种模块化设计,其中各部分都可以独立的构造、替换、排除错误。

关于Lisp的介绍

Lisp的名字来自表处理(LISt Processing),于20世纪50年代后期由John McCarthy基于他的论文“Recursive Functions of Symbolic Expressions and Their Computation by Machine”(符号表达式的递归函数及其机械计算 1960)发明。

强有力的程序设计语言,不仅是一种指挥计算机执行任务的方式,还应该成为一种框架,使我们能够在其中组织自己有关计算过程的思想。在描述一个语言时,需要将注意力特别放在语言所提供的,能够将简单认知组合起来形成更复杂认知的方法方面。每一种强有力的语言都为此提供了三种机制:

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

程序设计中需要处理的两类要素

  • 过程 - 有关操作数据的规则的描述
  • 数据 - 我们希望去操作的"东西"

复合表达式 、组合式具体定义是什么?

求值环境 - 存储、维护、保持值与符号的关联

基本过程 - 编程语言提供的一些内置的操作过程(Lisp中的特殊形式 + - define)EXP:(+ 2 3) (define x 2)

复合过程 - 将基本过程组合起来的自定义过程 EXP: (define (square x) (* x x))

过程求值的两种模型:

  • 应用序解释器首先对运算符和各个运算对象求值,而后将得到的过程应用于得到的实际参数。这种"先求值参数而后应用"的求值模型称为"应用序求值"
  • 正则序解释器先不求出运算对象的值,直到需要它们的值时再做。首先用运算对象表达式去替换形式参数,直至得到一个只包含基本运算符的表达式,然后再去执行求值。这种"完全展开而后归约"的求值模型称为"正则序求值"

练习1.1

MIT/GNU Scheme running under OS X
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2014 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Wednesday January 4, 2017 at 8:46:32 AM
  Release 9.2 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118 || Edwin 3.116

1 ]=> 10

;Value: 10

1 ]=> (+ 5 3 4)

;Value: 12

1 ]=> (- 9 1)

;Value: 8

1 ]=> (/ 6 2)

;Value: 3

1 ]=> (+ (* 2 4) (- 4 6))

;Value: 6

1 ]=> (define a 3)

;Value: a

1 ]=> (define b (+ a 1))

;Value: b

1 ]=> (+ a b (* a b))

;Value: 19

1 ]=> (= a b)

;Value: #f

1 ]=> (if (and (> b a) (< b (* a b))) b a)

;Value: 4

1 ]=> (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25))

;Value: 16

1 ]=> (+ 2 (if (> b a) b a))

;Value: 6

1 ]=> (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1))

;Value: 16

练习1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))

练习1.3 - 定义一个过程,它以三个数位参数,返回其中较大两个数之和

;;; 求三个数字中较大的两个之和
(define (sum-tow-large-num number-1 number-2 number-3)
  (- (+ number-1 number-2 number-3) (fetch-small number-1 number-2 number-3)))

;;; 求三个数字中较小的数字
;;; 最小值的决策树
;;;                                                       (x < y)
;;;                       (x < z)                                                 (y < z)
;;; (x < y x < z) (x < y z < x)         (y < x y < z) (y < x z < y)
(define (fetch-small number-1 number-2 number-3)
  (cond
    ((and (< number-1 number-2) (< number-1 number-3)) number-1)
    ((and (< number-1 number-2) (< number-3 number-1)) number-3)
    ((and (< number-2 number-1) (< number-2 number-3)) number-2)
    ((and (< number-2 number-1) (< number-3 number-2)) number-3)))

练习1.4 - 考察允许运算符为复合表达式的组合式的求值模型,根据这一模型的认知描述下面过程的行为

(define (a-plush-abs-b a b)
  ((if (> b 0) + -) a b))

首先允许运算法为符合表达式的组合式。根据Lisp求值原则首先求值(if (> b 0) + -)表达式,将a、b值作用于其结果 + 或 - 符号。得(+/- a b)。

MIT/GNU Scheme running under OS X
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2014 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Wednesday January 4, 2017 at 8:46:32 AM
  Release 9.2 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118 || Edwin 3.116

1 ]=> (define a 10)

;Value: a

1 ]=> (define b 20)

;Value: b

1 ]=> (define sybol (if (> b 0) + -))

;Value: sybol

1 ]=> (sybol a b)

;Value: 30

1 ]=>

练习1.5 - Ben Bitdiddle 发明了一种检测方法,能够确定解释器究竟使用哪种序求值,是采用应用序,还是采用正则序。他定义了两个过程:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

而后他求值下面的表达式:

(test 0 (p))

如果某个解释器采用的是应用序求值,Ben会看到什么样的情况?如果解释器采用的是正则序求值,他又会看到什么情况?请对你的回答作出解释。(无论采用正则序或者应用序,假定特殊形式if的求值规则总是一样的。其中谓词部分先行求值,根据其结果确定随后求值的子表达式部分)。

应用序求值:求值结果是程序陷入无限自身调用。在应用序求值(test 0 (p)) 时,从左向右求值依次时test、0、(p)。test已在全局环境中绑定,数字0求值结果为其自身,因为过程p返回的是其自身,(p)求值时陷入无限循环(调用自身)。

正则序求值:求值结果是0。在正则序求值时(test 0 (p))时,根据其求值规则'解释器先不求值运算对象',将过程test展开(if (= x 0) 0 y) 并求值返回0,if形式又是test的最后、唯一一个形式,所以test过程的求值结果为0

牛顿法求平方根

(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 (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

;;; BUG‘s Code
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
    (else else-clause)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x) x)))

练习1.6

程序运行结果

1 ]=> (define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
    (else else-clause)))

;Value: new-if

1 ]=> (define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x) x)))

;Value: sqrt-iter

1 ]=> (sqrt 2)

;Aborting!: maximum recursion depth exceeded

解释 - 根据应用序求值规则判断'new-if'在调用时,其形式参数总是被求值,同时sqrt-iter并非尾递归调用。也就是说'(sqrt-iter (improve guess x) x)'表达式总被调用求值,从而导致"超过最大递归深度"(maximum recursion depth exceeded)问题。而if特殊形式在条件表达式求值为false时,其else部分不被求值。

练习1.7

(define (sqrt x)
        (sqrt-iter 1.0 x))

(define (sqrt-iter guess x)
  (if (new-good-enough guess (improve guess x))
      (improve guess x)
      (sqrt-iter (improve guess x) x)))

(define (improve guess x)
  (adv guess (/ x guess)))

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

(define (good-enough guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (new-good-enough old-guess new-guess)
  (> 0.01 (/ (abs (- new-guess old-guess)) old-guess)))

练习1.8

(define (sqrt x)
  (sqrt-iter-3 1.0 x))

(define (sqrt-iter-3 guess x)
  (if (new-good-enough guess (imp guess x))
      (imp guess x)
      (sqrt-iter-3 (imp guess x) x)))

(define (new-good-enough old-guess new-guess)
  (> 0.01 (/ (abs (- new-guess old-guess)) old-guess)))

(define (imp guess x)
  (adv (/ x (square guess)) (* 2 guess)))

(define (adv x y)
  (/ (+ x y) 3))

过程抽象

  • 每个过程应完成一件可以清楚标明的工作,使其可以被用作定义其他过程的模块
  • 每个过程应该能隐藏起清楚标明的工作细节,使过程的使用者将其作为一个黑箱使用
  • 每个过程的意义应该不依赖于其作者为形式参数所选用的名字

线性的递归和迭代

  • 递归计算过程
  • 迭代计算过程
  • 线性递归过程
  • 线性迭代过程

递归计算过程和递归过程

当过程是递归的时候,论述的是语法形式上的事实,说明这个过程的定义中(直接或间接的)引用了该过程本身。在说某一计算过程具有某种模式时(如线性递归)是指这一计算过程的进展方式。应明确区分两者的含义。递归过程产生出迭代计算的例子:

;;; 递归过程产生的迭代计算
(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product) (+ counter 1) (max-count))))

练习1.9

;;; First
(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

;;; Second
(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

(+ 4 5)

;;; First
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
(9)

;;; Second
(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8)) (+ 0 9)
(9)

两个过程都是递归过程。其中First是递归计算过程、Second是迭代计算过程。

练习1.10

(define (A x y)
  (cond
    ((= y 0) 0)
    ((= x 0) (* 2 y))
    ((= y 1) 2)
    (else (A (- x 1) (A x (- y 1))))))

;; 求值 (A 1 10) =>>
(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
(1024)

;; 求值 (A 2 4)  =>>
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
(A 0 (A 1 15))
(A 0 (A 0 (A 1 14)))
(A 0 (A 0 (A 0 (A 1 13))))
(A 0 (A 0 (A 0 (A 0 (A 1 12)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))
(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))
(A 0 (A 0 (A 0 (A 0 4096))))
(A 0 (A 0 (A 0 8192)))
(A 0 (A 0 16384))
(A 0 32768)
(65536)
;; 求值 (A 3 3)  =>>
(define (nothing)
  (display "I'm tired!"))
(define (f n) (A 0 n)) ; 2n
(define (g n) (A 1 n)) ; 2^n
(define (h n) (A 2 n)) ; 2^2^2... n ...^2
(define (k n) (* 5 n n)) ; 5n^2

斐波那契数列

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) (fib (- n 2))))))

(define (fib n)
  (fib-iter 0 1 n))
(define (fib-iter a b count)
  (if (= count 0) a (fib-iter b (+ a b) (- count 1))))

(fib 5)
(+ (fib 4) (fib 3))
(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))
(+ (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0)) (fib 1)))
(+ (+ (+ (+ (fib 1) (fib 0)) 1) (+ 1 0)) (+ (+ 1 0) 1))
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 0) 1))
(5)

练习1.11

;; Recursion
(define (f n)
  (if (< n 3) n (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

;; iteration
;; f(3)=f(2)+2f(1)+3f(0)
;; f(4)=f(3)+2f(2)+3f(1)
;; f(5)=f(4)+2f(3)+3f(2)

(define (f n)
  (f-iter 0 1 2 n))

(define (f-iter a b c n)
  (if (< n 3)
      a
      ()))

Date: 2018-08-06 Mon 18:50

Author: xueshumeng

Email: xue.shumeng@yahoo.com

Created: 2023-08-28 Mon 14:16