SICP读书笔记--第3章《模块化、对象和状态》

一、说明

  • 在第1章中我们知道了如何进行过程抽象,如何利用高阶过程达到更高一级的抽象。

  • 在第2章中我们学会了数据抽象,知道了它的一般方法,利用它对系统各层次之间建立抽象屏障,利用闭包性质设计层次性结构数据,并学会了序列操作的一般性约定方法,深刻领会了数据导向的程序设计方法,并学会利用了消息传递进行程序分派。

这两章的内容都可以利用代换模型进行解释,可是在自然界中的对象都不可避免地要考虑由时间带来的状态问题,本章就是通过引入对象、状态和赋值概念后完成对现实世界的模拟。

  • 本章内容分布:
    • 3.1赋值和局部状态
    • 3.2求值的环境模型
    • 3.3用变动数据做模拟
    • 3.4并发:时间是一个本质问题
    • 3.5流
  • 我的解题代码

二、总结

  • 本章中我们将看到一个强有力的、用于构造模拟真实物理系统的程序的设计策略:基于被模拟系统的结构去设计程序的结构

    • 构造与物理系统中每一个对象相对应的计算对象
    • 对系统里的每种活动,在计算系统里定义对应的符号操作
  • 两种组织策略:

    • 将注意力集中在对象上,考虑它们的行为可能随时间的变化而不断变化。
    • 将注意力集中在流过系统的信息流上,看作信号处理系统,考虑对流的一系列动作如过滤映射组合等。
  • 新的计算模型:环境模型

1.赋值和局部状态

  • 对象状态的描述:引入它的一些局部状态变量,维持有关这一对象的历史。
  • 对象间的交互:建立起一个对象的状态变量与其他对象状态变量之间的联系。

1.1赋值操作

  • 使用了特殊形式set!,语法:

    (set! <name> <new-value>),这里<name>将是一个符号,<new-value>是任何表达式。

    set!将修改<name>,使它的值变成求值<new-value>的结果。

  • 使用了特殊形式begin,语法:

    (begin <exp1> <exp2> ... <expk>),导致表达式<exp1><expk>按顺序求值,<expk>的值作为整个begin形式的值返回。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    (define (make-withdraw balance)
    (lambda (amount)
    (if (>= balance amount)
    (begin (set! balance (- balance amount))
    balance)
    "Insufficient funds")))
    (define W1 (make-withdraw 100))
    (define W2 (make-withdraw 100))
    (W1 20)
    ;==> 80
    (W1 30)
    ;==> 70

    1.2赋值带来的利益

  • 一种维护模块化设计的强大技术:

    将系统看作一集带有局部状态的对象,从一个复杂计算过程中一部分的角度看,其他部分都像是在随时间不断变化,它们隐藏起自己的随时间变化的内部状态

    1.3赋值带来的代价

  • 破坏了前两章一直存在的一个特性:引用透明性,使确定能否通过等价地表达式代换去简化表达式变成了复杂的问题。

  • 强迫人们去考虑赋值的顺序问题,保证每个语句所用的是被修改变量的正确版本。

2.求值的环境模型

  • 一个环境就是框架的一个序列,每个框架是包含着一些约束的一个表格,这些约束将一些变量关联与对应的值。
  • 每个框架包含着一个指针,指向这个框架的外围环境
  • 一个变量相对于某个特定环境的,就是在这个环境中,包含着该变量的第一个框架里这个变量的约束值。

2.1求值规则

过程应用的环境模型的两条规则:

  • 将一个过程对象应用于一集实际参数,将构造出一个新框架,其中将过程的形式参数约束到调用时的实际参数,而后在新的环境的上下文中求值过程体。

  • 对于一个给定环境求值一个lambda表达式,将创建起一个过程对象,它是一个序对,由该lambda表达式的正文和一个指向环境的指针组成,这个指针指向创建这个过程对象的环境。

2.2内部定义

  • 以局部过程定义作为程序模块化的技术里的两个关键性质:
    • 局部过程的名字不会与包容它们的过程之外的名字相互干扰。
    • 局部过程只需将包含着它们的过程的形参作为自由变量,就可以访问该过程的实际参数。

3.用变动数据做模拟

3.1变动的表

  • 通过两个操作set-car!set-cdr!去分别改变一个序对的carcdr指针的指向来实现变动的表。

3.2队列

  • 队列是一个先进先出的数据结构,这里主要是引入首尾指针的思想来加速对队列末端的访问。

3.3二维表格

  • 二维表格里的每个值由两个关键码的索引,我们将这个表格构造为一个一维表格,其中的每个关键码又标识了一个子表格。

3.4数字电路的模拟器

  • 这是被称为事件驱动的模拟程序的一个代表,在这类系统里一些事件引发另一些在随后时间发生的事件,它们又会引发随后的事件,并如此继续下去。

3.5约束的传播

  • 通过构造约束网络组合各种约束,约束通过连接器连接起来。当某个连接器被给定了一个值时,它就会去唤醒所有与之关联的约束,通知它们自己有了新值,并如此继续下去。

4.并发:时间是一个本质的问题

4.1并发系统中时间的性质

  • 复杂性原因:多个进程有可能共享同一个状态变量

  • 并发程序正确性的两种限制方式:

    • 一种严格的限制方式:修改任意共享状态变量的两个操作都不允许同时发生。

    • 另一种不那么严格的方式:保证并发系统产生出的结果与各个进程按照某种方式顺序运行产生出的结果完全一样

4.2控制并发的机制

  • 串行化组:创建一些不同的过程集合,并且保证在每个时刻,在任何一个串行化集合里至多只有一个过程的一个执行。

从本质上看,在并发控制中,任何时间概念都必然与通信有内在的密切联系。有意思的是,时间与通信之间的这种联系也出现在相对论里,在那里的光速(可能用于同步事件的最快信号)是与时间和空间有关的基本常量。在处理时间和状态时,我们在计算模型领域所遭遇的复杂性,事实上,可能就是物理世界中最基本的复杂性的一种反映。

5.流

  • 是另一条对状态进行模拟的途径,它的核心是一种数学函数的思想:

    我们将一个量$x$的随时间变化的行为,描述为一个时间的函数$x(t)$。如果我们关注的是每个时刻下的$x$,那么可以看作是一个变化着的量。如果我们关注值的整个时间史,那么就不需要强调其中的变化—函数$x(t)$没有改变。

5.1流的实现

  • 基本想法:做出一种安排,只是部分地构造出流的结构,并送给使用流地程序,如果还需要访问尚未构造出的部分,则会自动继续构造下去。

  • 特殊形式delay:求值(delay <exp>)返回一个延时对象,可以看作是对在未来的某个时间求值<exp>的许诺。

  • 过程force:以一个延时对象为参数,执行相应的求值工作。

5.2流计算模式的使用

  • 我们可以将整个的时间序列作为有关的目标,而不是去关注状态变量在各个时刻的值。这将使我们更方便地组合与比较来自不同时刻的状态的组合。

将迭代操作表示为流操作

1
2
3
4
5
6
; 求解一个数的平方
(define (sqrt-stream x)
(define guesses
(cons-stream 1.0
(stream-map (lambda (guess) (sqrt-improve guess x))
guesses)))

序对的无穷流

  • 这里主要是生产序对$(i,j)$,并且$i<=j$

    1
    2
    3
    4
    5
    6
    7
    (define (pairs s t)
    (cons-stream
    (list (stream-car s) (stream-car t))
    (interleave
    (stream-map (lambda (x) (list (stream-car s) x))
    (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))

将流作为信号

  • 用流的元素表示为一个信号在顺序的一系列时间间隔上的值。

5.3函数式程序的模块化和对象的模块化

  • 本章一开始就提出了其目标,那就是构造一些计算模型,使其结构能够符合我们对于试图去模拟的真实世界的看法,有下面的两种方式:

    • 将这一世界模拟为一集相互分离的、受时间约束的、具有状态的相互交流的对象。
    • 将它模拟为单一的、无时间也无状态的统一体。

我的解题代码

------------- 本文结束 感谢您的阅读 -------------

本文标题:SICP读书笔记--第3章《模块化、对象和状态》

文章作者:Perry

发布时间:2019年03月23日 - 06:00

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/983e3830.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%