Structure and Interpretation of Computer Programs 读书笔记 Chapter 1 构造过程抽象 1.1 程序设计的基本元素

Structure and Interpretation of Computer Programs 读书笔记 Chapter 1 构造过程抽象 1.1 程序设计的基本元素

2020, Jan 17    

第1章 构造抽象过程

  • 这一张主要学习的是有关计算过程的知识。

    定义:计算过程是存在于计算机的里的一类抽象事物,主要操作一些被称之为”数据”的抽象事物。(就像Java中的各种类中的方法)

  • 我们指挥这种过程的程序就像是巫师的巫术一样,使用一些诡秘而深奥的程序设计语言,通过符号表达式的形式精心编排而成,他们描述了我们希望相应的计算过程去完成的工作。

  • 但是幸运的是,我们学习程序的危险性远远小于巫术。但是我们也必须像麻瓜一样,必须去学习、理解、预期我们所使用的咒语(程序)所带来的效果。程序里即使有一个小错误(bug or glitch),也可能带来无法预料的后果。 真实的程序设计则需要极度细心,需要经验和智慧。
  • 设计良好的计算系统就像设计良好的汽车或者核反应堆一样,具有某种模块化的设计,其中的各个部分都可以独立地构造、替换和排除错误。

  • 书中所使用的Lisp方言Scheme,并不是一门主流语言,但是有一个非常重要的特征:计算过程的Lisp描述(过程)本身可以作为Lisp的数据来表示和操作。而不是现在很多威力强大的程序设计技术,都依赖于填平在 “被动的”数据和”主动的”过程之间的传统划分。

1.1 程序设计的基本元素

一个强有力的语言,不仅是一种指挥计算机执行任务的方式,它应该成为一种框架,是我们能够在其中组织自己有关计算过程的思想。 每一种强有力的语言都提供了三种机制:

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

用白话来解释,数据就是我们希望去操作的东西,而过程就是有关操作这些数据的规则描述。这样,任何强有力的程序设计语言都必须能够表达表述基本的数据和基本过程,还需要提供对过程和数据进行组合和抽象的方法。

1.1.1 表达式

  • 开始程序设计,最简单的方式就是打开计算机的终端,用键盘输入一个表达式,解释器的响应就是将它对这一个表达式的求值结果显示出来。
  • 运算对象+运算符 ==>组合式 (组合式本身也可以作为运算对象参与其他组合式的运算(套娃递归))
  • 即使对于非常复杂的表达式 解释器也是按照同样的基本循环运作: 读入->求值->打印

1.1.2 命名和环境

  • 程序设计中一个必不可少的方面,就是它需要提供一种通过名字去使用计算对象的方式。我们将名字标识符成为变量,它的值也就是它所对应的那个对象。
  • 实际上,构造一个复杂的程序,也就是为了去一步步地创建出越来越复杂的计算性对象。(一个Lisp程序通常是由一大批相对简单的过程组成的)
  • 我们可以将值和符号相关联,而后又能提取出这些纸,这意味着解释器必须维护这某种存储能力,以便保持有关 名字-值 对偶的轨迹。这种存储被称之为环境 (更加准确的说是全局环境,以后会看到,在一个计算过程中完全可能涉及到若干不同的环境(全局域和局部域,全局变量和局部变量))

1.1.3 组合式的求值

一个组合式的求值狐妖就是做两件事

  1. 求值该组合式的各个子表达式
  2. 将作为最左子表达式的(运算符)的值那个过程应用于相应的实际参数,所谓的实际参数就是其他子表达式(运算对象)的值。
  • 一般而言,我们将递归看做一种处理层次性结构的(像树这样的对象)极强有力的技术。
  • “值向上穿行”形式的求值形式是一类更一般的计算过程的例子,这种计算过程被称为树形积累。
  • (define x 3)这种定义的情况,这算是一种特殊形式,作用是将符号x关联一个3的值,这并不是一个组合式。每一种特殊形式都有自己的求值规则。

1.1.4 复合过程

三个元素:

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

这是一种威力更强大的抽象技术

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

上述代码就是是用复合过程的方式,定义了一个乘方,使用的时候只需要

(square x)

和组合式的嵌套类似,复合过程也可以使用在其他的复合过程的定义当中

(
    define (sum_of_squares x y) (+ (square x) (square y))
)

例如上面的代码,就是一个平方和的复合过程实现,我们同样也能够将其实用到更加复杂的复合过程中去(无限套娃)。但是由于复合过程的构造太深,如果我们只是看到sum_of_squares这一层,就会感到疑惑?这个square究竟是像 “+”,”-“,”*”,”/” 一样直接做在解释器中呢?还是被定义成了一个复合过程呢?

(
    define (f a)
        (sum_of_squares (+ a 1) (* a 2))
)

1.1.5 过程应用的代换模型

在本章的例子当中,就比如上方的 平方和 例子 (f 5) 结果是136,我们是怎么去理解这个过程的呢?

  1. (f 5) 我们先取出f的体
  2. (sum_of_squares (+ a 1) (* a 2)) 然后将实际参数替换这个表达式中的形参
  3. (sum_of_squares (+ 5 1) (* 5 2)) 这样就转化为了两个简单表达式的运算
  4. (sum_of_squares 6 10) 然后取出sum_of_square的体,同样进行计算
  5. (+ 36 100) 得到结果

上面的这种模型,就是我们所说的代换模型。但是有两点需要注意:

  • 代换的作用只是方便我们理解,而不是解释器的实际工作方式的具体描述。
  • 在模拟复杂的科学研究现象的时候,我们也都是从最简单的模型开始的。

正则序和应用序

  • 正则序:完全展开再进行规约(处理到了最后一步,再进行求值)
  • 应用序:先求值参数而后应用(一边带入,一边处理)(可能会重复求值,浪费效率

条件表达式和谓词

  • 条件表达式:根据不同的情况进行不同的处理(if-else、switch、cond等等)
  • 谓词:返回 真 或者 假 的表达式。