《计算机程序构造与解释》读书笔记(1)

末蓝、 2023-03-01 13:41 1阅读 0赞

#  #

### 文章目录 ###

*  
 *   *  1. 概念是为什么？
     *  2. 构造过程的抽象
     *   *  2.1 程序设计的基本要素
         *   *  2.1.1 表达式
             *  2.1.2 命名和环境
             *  2.1.3 组合式的求值
             *  2.1.4 复合过程
             *  2.1.5 过程应用的代换模型
             *  2.1.6 条件表达式和谓词
     *  3. 过程与它们产生的计算
     *   *  3.1 线性的递归与迭代
         *  3.2 树形递归
         *  3.3 成本的计算
     *  4.用高阶函数做抽象
     *   *  4.1 过程作为参数
         *  4.2 用 lambda
         *  4.3 过程作为一般性方法
         *  4.4 过程作为返回值
     *  5. 写在最后

最近有点「间歇性踌躇满志，持续性混吃等死」，难道是因为工作太久？

随便什么原因，还得靠强大（微弱）的意志努力调整下状态，所以以一份炸鸡块作为奖励开始写本应该早就写完的读书笔记。

## 1. 概念是为什么？ ##

「面向对象」和「面向过程」是在编程的路上最初的接触的到两个概念。靠着肌肉记忆，还能够说出面向对象的特性是封装、继承和多态。但是你有没有思考过这些概念是如何被提出的？

> 「万物皆有因果，万象皆随因缘。」

面向对象和面向过程是编程的时候的两种切入角度，以前觉得，既然面向对象时后面提出的，那大抵是因为「面向对象」是更好的吧。其实则不然，这种编程思维的使用必须结合实际场景，比如采用的语言、抽象的事物等来进行判断。你想要用 C 语言来写面向对象可以，但是对于使用者来说，这必然是耗时、费力且不省心的。

> 「甲之蜜糖，乙之砒霜」

其实程序设计的时候，从上层看需要处理的要素无非两类：

*  过程
 *  数据

数据是一种我们希望去操作的东西，而过程就是操作这些数据的规则的描述。**面向对象 和 面向过程这两种编程的思路，应该就是取自程序的组成部分**

基于应试教育的影响，我们养成了看到概念就背，考试只字不差的填就好的思维。但是在真实的世界中，概念绝非单纯是要你记忆的，概念就是在人们之间建立起一个统一的空间，尽可能的确保我们看到的和所理解的都是在一个层面上。就好像是 C++ 中，同一个命名空间中看到的变量的命名和值是一致的一样。

## 2. 构造过程的抽象 ##

### 2.1 程序设计的基本要素 ###

做一份炸鸡块需要鸡块、油、各种调料和厨师，那程序设计的基本要素是什么呢？木有想到包括什么的话，那可以看看下图猜猜他们都是什么？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70]

#### 2.1.1 表达式 ####

表达式的概率很好理解，比如：

*  1235 ：这是个数字组成的表达式
 *  \+ / \*：这是一个过程组成的表达式
 *  （+ 137 349）：这是个复合表达式，称之为组合式子

> 注：（+ 137 349）这个一个前缀表达式，思考为什么存在前缀表达式这种设计？
> 
> 很简单，因为它适用于带有任意个实参的过程。

#### 2.1.2 命名和环境 ####

(define size 2)

这是一个表达式，此处 size 变量于数值 2 的别名，这称之为命名，而以后的运算过程中可以通过 size 这个名字去引用其值，保存名称和数值的这种存储关系的称之为环境。

#### 2.1.3 组合式的求值 ####

对下列表达式求值

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

分解一下上述表达式，需要将求值规则应用于 4 个不同的表达式。求值过程中子表达式不断递归向上求值的过程，称之为树形积累。如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70 1]

#### 2.1.4 复合过程 ####

总结一下前面的内容：

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

而过程的定义是指为复合操作提供名字，而后就可以将这样的操作作为一个单元使用。比如：

（define (square x) (* x x))

上述的定义为：square 这个定义为平方表达式，其操作是 x\*x，过程定义的一般形式是：

（define ( <name> <formal parameters>) <body>)

#### 2.1.5 过程应用的代换模型 ####

代换模式的两种方式：

*  先对运算符和各个运算对象求值，而后将得到的过程应用于得到的实际参数。
 *  先不求运算对象的值，直到实际需要它们时再去求值。（惰性求值）

> 注：
> 
> 1.  惰性求值的好处是，对于相同的子表达式不用求值多次
> 2.  今天晚上跟同事讨论 severless 的优化点的时候，一位同事提出的 js object 跟 go struct 的转换可以延后到 js 在使用的时候在求值，也是这个思路

#### 2.1.6 条件表达式和谓词 ####

至此，我们能够定义过程，但是没有办法根据不同的条件，选择不同的处理过程。所以大多数高级语言都会提供 if 或 swatch 的条件判断语法。此处于 Lisp 语言为例：

对于下面的表达和 lisp 的翻译

x 如果 x > 0
    |x| =  0 如果 x = 0
           -x 如果 x < 0
    (define (abs x))
      (cond ((> x 0) x)
            ((= x 0) 0)
            ((< x 0) -x)
      )

故 Lisp 的一般性形式如下:

(cond (<p1> <e1>)
          (<p2> <e2>)
          …………
          (<pn> <en>)
          )

此处的 P 就是一个谓词。

## 3. 过程与它们产生的计算 ##

背会象棋的口诀之后，下一个步骤就是学习一些经典的棋局该如何走。同理在写代码时脑海中有了抽象的概念之后，下一个步骤是学习几种常见的抽象方式。

### 3.1 线性的递归与迭代 ###

考虑分别用递归和迭代的方式实现阶乘的表达式

n! = n*(n-1)*(n-2)……3*2*1

递归：

(define (factorial n)
       (if (= n 1)
           1
           (* n (factorial (- n 1)))))

迭代：

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

总结：过程的重新可以从迭代和递归的两种角度考虑。

### 3.2 树形递归 ###

以斐波那契数列的计算考虑树形递归，其定义规则为：

0                   如果 n = 0
    Fib = 1                   如果 n = 1
          Fib(n-1)+Fib(n-2)   否则

抽象代码实现：

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

注：该过程所需要的计算步骤随着输入增长而指数性地增长，但是其空间需求只是随着输入而线性增长。

### 3.3 成本的计算 ###

熟悉各种兵法，但是却不知道该如何选择，其实就是什么都不会吧（ps 突然想起了纸上谈兵的赵括。

不同的计算过程在消耗计算资源的速率上有着巨大的差别，而评估这种差异的方式就是使用增长的阶，即 O(n)。

该章节以求幂为例子，分别解析了递归、迭代和优化迭代的三种解法中消耗的时间和空间。见书 P29

总结：大概从来就没有最优的解法一说吧，所有的解法都是要因地制宜。

## 4.用高阶函数做抽象 ##

在作用上，过程也就是一类抽象，它们描述了一些对数的复合操作，但是由不依赖于特定的数。例如，在定义：

(define (cube x) (* x x x))

这并不是某个特定数值的立方，而是对于任意的数得到其立方的方法。

### 4.1 过程作为参数 ###

顾名思义，函数的参数除了一般意义上的数值之外，还可以是某个过程的定义。这个概念并没有什么特殊的，但是引入这个概念的是通过提取了三个 sum\_xxx 函数，构造出一个通用的以 sum 过程为参数的框架。「**这个思维，是需要在日常的编程工作中逐步有意识的做且反复积累的。**」

### 4.2 用 lambda ###

一般而言，lambda 用与 define 同样的方式创建过程，除了不为有关过程提供名字之外。

（lambda (<formal-parameters) body)

例如：

（define (plus4 x) (+ x 4)) <=> (define plus4 (lambda (x) (+ x 4)))

思考：为什么会引入 lambda 表达式这一个概念呢？

答：以我现在的理解程度来解释的话，应该是免除繁杂的子过程（即子函数定义），直接通过 lambda 表达式来表示子过程。嗯，终于知道为什么 js 里这么多的 (x => \{……\}) 是做了啥

### 4.3 过程作为一般性方法 ###

额，这不就是 4.1 提到的抽象框架的思考方式……，害的我特意反复读了两遍复杂的数学定义——通过区间折半寻找方程的根，找出函数的不动点（ps 差点被描述劝退。

### 4.4 过程作为返回值 ###

一家人就要整整齐齐不是，过程除了作为函数的入参也能作为函数的出参。（ps 在某些编程语言是可以的哈

思考：这种函数返回值的方式是不是取自流水线呢，每次只加工一部分，然后剩余的丢给更精细化的产线去处理。

## 5. 写在最后 ##

原谅我 3，4 小结木有太多的例子，其实也不能怪我，全部都是数学函数，抄来放在这里也没啥用，提取一下中心思想就好。（ps 主要是写太久了，腰痛……

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70]: /images/20230208/52102c46d7de460ea861496a07a65bff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70 1]: /images/20230208/a965439f56de432db7012ac26d39d756.png