计算机程序的构造和解释

March 20, 2018

计算机程序的构造和解释
———

序
---------

关注程序的创建、执行和研究。使用Lisp方言书写
本书中讨论的各种问题主要涉及到：人的大脑，计算机程序的集合，以及计算机本身。每一个计算机程序都是现实中的或者精神中的某个过程的一个模型。通过人的头脑孵化出来，这种过程出现在人们的经验或者思维中。很少能够通过程序将这种过程模拟到永远令人满意的程度。因为这个原因，程序也在不断的演化。当我们对模型的认识更深入、更扩大，更广泛时，我们就会修改程序。直到达到一中亚稳定状态。而在这时，程序中有会出现一个需要我们为之奋斗的模型。计算机程序设计领域之所以令人兴奋的源泉，就在于他所引起的连绵不绝的发现。

组织技术
一致性和正确性在程序变得更大更复杂的时候，非常值得怀疑了。很少能够看到有关大型程序正确性的完全形式化的论述。
组织技术: 是理解程序设计这种具有设计、创造性的事业中的本质。
因为大的程序是从小的东西成长起来的。所以，开发一个标准化的程序结构的武器库，并保证其中每种结构的正确性。再通过组织技术，将这些结构组合成更大的结构。这些都是至关重要的。发现并掌握这种强有力的组织技术，将提升我们构造大型重要程序的能力,反过来，因为构造大型程序的费力，导致我们去发明新的方法，来减轻构造大型程序的沉重负担。

在任何非常大的程序设计工作中，一个非常有用的组织原则就是通过发明新语言，去控制和隔离作业模块之间的信息流动。
算法
执行了某个精确函数的程序我们称为算法。特别需要关注的两个参数是：执行的事件、对数据存储的需要。程序员应该追求好的算法

前言

计算机语言不仅仅是让计算机执行操作的一种形式，更重要的是，他是一种表述有关方法学的思想的形式化媒介。
所以，程序是写给人读的，然后才是去执行
最基本的材料不是特定程序的语法，不是某种巧妙的算法。而是一些能够用于控制大型软件系统的智力复杂性的技术。（创建抽象去控制复杂性，通过建立约定的界面，以便能够用一种混合与匹配的方式组合在一起，建立一些新的语言去描述各种设计，每种语言强调设计中的一个特定方面并降低其他方面的重要性，以控制复杂度）
计算机科学并不是一种科学，而且其重要性也与计算机本身并无太大关系。计算机革命是有关我们如何去思考的方式，以及我们如何去表达自己思考的一个革命。这其中最基本的东西是，过程性认知论的现象，就是如何从一种命令式的观点去研究知识的结构，这是一种与经典数学领域总所采用的更具有说明性的观点完全不同。数学为精准处理 “是什么的” 提供了一种框架，而计算则为精准处理“怎样做” 的概念提供了一种框架。

过程构造抽象

心智活动主要表现如下三个方面
1. 将若干简单的认识组合为一个复杂的认识，由此产生出复杂的认识
2. 将两个认识放在一起做对照，不管他们如何简单或者复杂。这样做并不将他们合二为一，由此得到的有关他们相互关系的认知。
3. 将有关认识与那些实际中和他们同在懂得所有其他的认识隔离开，这就是抽象。所有具有普遍性的认识都是这样得到的
计算过程的Lisp描述，本身又可以作为Lisp的数据来表示和操作。现在的语言都在填平『被动的数据』和『主动的过程』之间的传统划分，（划分是什么？）能够将过程表示为数据的能力，Lisp的这种能力使Lisp成为编写那些必须将其他程序当做数据去操作的程序的最佳语言，比如：计算机语言的解释器和编译器。 macro
程序设计的基本元素
- 语言提供的将简单的认识组合起来成为更复杂认识三种机制：
  1. 基本表达形式: 组成语言的最小单位，个体
  2. 组合的方法：通过他们可以将简单的组合成为复杂的
  3. 抽象的方法：通过他们将复杂对象命名，并将他们作为单元去使用
    程序中需要处理过程和数据两种元素，数据是一种我们需要去处理的东西，过程就是我们操作数据的规则的描述。任何语言都需要能够表述基本的数据和基本的的过程，还需要提供对过程和数据进行抽象组合的方法。
- 具体语言的实现：
  1. 表达式
    (操作符参数1 参数2)
    解释器总是按照从终端读入一个表达式，对这个表达式求值，而后打印出得到的结果，称为读入—求值—打印的循环， REPL
  2. 命名
    (define radius 10)
    创建名字–对象的关联。鼓励人们采用递增的方式去开发和调试程序。其中需要注意的是，其中隐含着环境的概念，其中保持着名字—值的关联
    环境在确定表达式中各个符号的意义是十分重要的，如果没有相关环境的任何信息，那么说表达式(+ x 1) 是没有任何意义的。因为需要环境提供x的意义。环境是具有普遍性的概念。他为求值过程提供了一种上下文。对我们理解程序的执行起着重要的作用。
  3. 组合式的求值
    1. 求值该组合式的各个子表达式
    2. 将作为最左表达式的值的那个过程应用与相应的实际参数。所谓实际参数就是各个子表达式的求值结果
      为了实现对一个组合式的求值过程，我们必须先对组合式里的每个元素执行同样的求值过程。因此，在性质上，这一求值过程是递归的。
    3. 反复的执行第一步骤，最终会到达求值中的一个点，在这里遇到的不是组合式而是基本表达式。例如内部运算符或者其他名字
      - 数的值就是他们所表示的数值
      - 内部运算符的值就是能完成相应操作的机器指令序列， fun
      - 其他名字的值就是在环境中关联与这一名字的那个对象，变量
        可以将第二种情况看做最后一种情况的特殊情况，像 +， - 等，相应的指令序列就是与之关联的值
  4. 特殊形式
    (define x 3) 并不是一个组合式，一般性的求值规则的这种例外称为特殊形式。各种不同类型的表达式（有着不同的求值规则）组成了程序设计语言的语法形式。
```
 (* (+ 2 (* 4 5))
    (+ 3 5 7 ))
```
    条件表达式，谓词并不是普通的过程（表达式不一定都需要求值）
    (if ) (cond ( ) ( ) ... ( ))
  5. 代换模型
    - 组合式的求值递归过程
    - 正则序求值：完全展开而后归约
    - 应用序求值：先求值参数而后应用
过程
- 形式参数，约束变量、自由变量: 在过程体中扮演者一种非常特殊的角色，形式参数的具体名字是什么，完全没有关系，这样的名字称为。一个过程的定义约束了他所有的形式参数，如果一个变量不是被约束的，我们就称他为自由的。一个名字的定义被约束于的那一个表达式称为这个名字的作用域，所以在过程的定义中，被声明的为形式参数的那些约束变量，就以这个过程的体作为他们的作用域。
- 块结构:
```
(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 (sqrt x)
  (sqrt-iter 1.0 x))

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



(define (sqrt x)
  (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)))
  (sqrt-iter 1.0 x))

(define (sqrt x)
  (define (sqrt-iter guess)
    (if (good-enough? guess)
      guess
      (sqrt-iter (improve guess))))
  (define (good-enough? guess)
    (< (abs (- (square guess))) 0.001 ))
  (define (improve guess)
    (average guess (/ x guess)))
  (sqrt-iter 1.0 x))
```
  这种嵌套的定义称为块结构，是最简单的名字包装问题的一种正确方式。这其中还有一种简化的方法，因为所有的辅助过程定义放到内部，x在sqrt内部是受约束的。过程good-enough， improve都定义在sqrt利民啊，也就是说显示的将x传递来传递去没有必要了，我们让x作为内部定义中的自有变量。sqrt被调用时，x就确定了。这种方式称为词法作用域。
- 过程与他们所产生的计算
  1. 线性的迭代和递归
```
 (define (factorial n)
   (if (= n 1)
     1
     (* n (factorial (- n 1)))))

 (define (factorial n)
   (fact-iter 1 1 n))
 (define (fact-iter product conter max-count)
   (if (> counter max-count)
     product
     (fact-iter (* counter product)
       (+ counter 1)
       max-count)))
```
    第一个为递归计算过程，代换模型展开的形状是一个先逐步展开而后收缩的形状。收缩阶段为这些运算的实际执行。这种类似性的计算过程由一个推迟执行的运算链条刻画
    第二个为线性递归计算过程，解释器只需要维护函数调用的参数，就可完成函数调用。
  2. 过程的计算过程和形式:
    - 过程形式：过程的书写形式
    - 计算过程：过程的计算过程
    - 迭代计算过程：在计算过程中的任何一点，程序的变量都提供了一个有关计算状态的完整描述。在任何时刻计算停下来，都可以提供参数来重新计算，
    - 递归过程：论述的是一个语法形式上的。说明这个过程的定义中，调用了自己。
    - 递归计算过程：函数的计算过程的进展方式。而不是过程上的语法形式上的书写，他们隐含着一些信息，有解释器维持，来指明所推迟的运算形成的链条中的位置。这一计算处在何处，这个链条越长，所需要保存的信息也就越多。
    - 为什么需要区分计算过程和形式过程？大部分语言的实践设计中，对任何递归过程的解释，所消耗的存储量总与过程调用的数目成正比，即便他所描述的计算过程是迭代的。作为这是一事实的后果就是—特殊的循环结构： for, while等。scheme 能够将形式上的递归而计算过程为递归形式，依然能够在常数空间上运行，这种实现为：尾递归。
  fact-iter 递归过程讲产生迭代的计算过程，因为展开的计算过程上确实是迭代的，其中的状态由三个变量保持。解释器没有额外的隐含的状态保存。
scheme相关
- 命名
  （define <body>）
- 条件表达式和谓词
  (cond ( ) ( ) ... ( )) (if ) (and ..... ) (or ..... ) (not ) and or 不是普通的过程, 其中的参数不一定都会求值，not 是过程
- 高阶函数: 函数作为参数, 函数作为返回值
```
   (define (sum term a next b)
     (if (> a b)
         0
         (+ (term a)
         (sum term (next a) next b)))))
```
```
     * lambda  (lambda <parameters> <body>)  (lambda (x) (* x x x))
```

构造数据抽象（复合数据）

语言所包含的将数据对象组合起来的，形成复合数据的方式。提高设计的模块性，是我们得以在比语言提供的基本数据对象更高的概念层次上。处理与数据有关的各种问题。
复合数据能够将处理数据对象的表示部分，与处理数据对象的使用部分相互隔离开来，这种技术具有一般性，形成了一种成为数据抽象的强有力的设计方法学。数据抽象技术能够是程序更容易设计，维护和修改。
形成复合数据的关键在于，程序设计语言提供的某种黏合剂，他们可以用于把一些数据对象组合起来，形成更复杂的数据对象，1）过程 2）闭包，用于组合数据对象的黏合剂同样适用于复合数据对象 3）符号表达式
数据导向型程序设计
数据抽象的基本思想：设法构造出一些使用复合数据的对象的程序，使他们就像是在“抽象数据”上操作一样，我们的程序使用复合数据的方式应该是这样的：除了完成当前工作的必要东西之外，他们不对数据做任何的假设。同时，一种具体的数据表示的定义，也应该跟程序中使用数据的方式无关。这要求在我们的系统里面需要一组过程：选择函数、构造函数。
按愿望思维方式，（从上倒下）是一种强有力的设计方法，其中不会设计到细节，只是思考整体的数据使用方法。（复合数据结构的操作界面）
序对: cons, car, cdr 从序对构造起来的数据对象成为表结构的数据
数据抽象的基本思想就是：为每一类数据对象标识出一组操作。是的对这类数据对象的所有操作都可以基于他们表述，而且在操作这些数据对象时也只使用他们。
形象化的表示了有理数系统的结构，其中的水平线表示抽象屏障，他们呢隔离了系统中的不同的层次，在每一层上，这些屏障都把使用数据抽象的程序与实现数据抽象的程序隔离开来，使得有理数的程序有理数实现提供的函数完成对有理数的操作，而这些函数又是基于构造函数和选择函数make-rat, numer denom 实现的。而make-rat等函数又是基于序对实现的。有关序对实现的细节与有理数的其余部分都完全没有u关系。每一层次中的过程构成了所定义的抽象屏障的界面，联系起来系统中的不同层次.
数据意味着什么：我们总可以将数据定义为一组适当的选择函数和构造函数，其中这些过程必须满足某些必要条件。（试着将这些条件放到程序中，面向对象，编译类型语言的语法检查，是不是都在某种程度上实现这些检测）
序对的概念，我们只需要定义，z = (cons x y)，那么 car(z) == x (cdr z) == y, 意味着，任何满足这三个条件的函数都可以作为实现。
```
    (define (cons x y)
       (define (dispatch m)
           (cond ((= m 0) x)
                 ((= m 1) y)
                 (else (error "error argument ")))))
     (define (car z) (z 0))
     (define (cdr z) (z 1))
```
序对 (cons a b) cons的闭包性质是非常重要的，某种组合数据对象的操作满足闭包性质，就是说，通过他组合起来的对象得到的结果本身还可以通过同样的操作再次进行组合。闭包性质是一种组合功能的关键所在。
序列的表示： (cons 1 (cons 2 (cons 3 nil))) (list 1 2 3)
map

        (define (scale-list items factor)
    (if (null? items)
'()
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))

(scale-list (list 1 2 3 4 5) 10)

(define (map proc items)
  (if (null? items)
      '()
      (cons (proc (car items))
            (map proc (cdr items)))))


(define (scale-list items factor)
  (map (lambda (x) (* x 10))
       items))

map 不仅仅是一种模式，更重要的建立起了一种高级抽象。在scale-list 原来的设计中，更多的注意力放在了，循环递归的结构中，而通过map定义的scale-list 则忽略了这种细节层面的情况，强调是表到表的缩放，这两种形式上的差异并不在于计算机会执行不同的计算过程，而在于我们对这同一种过程的不同思考方式。