[Back]

Chapter 3

3.1 赋值和局部状态

DEF.42 状态变量 我们使用几个状态变量来刻画一个对象所经历的历史,以此能确定它在此刻的行为。同时,这些状态变量之间的互相作用也刻画了对象之间的交互关系。由此,我们就需要给对象分配局部状态变量,使得他们能够随着时间的推移表现对象的状态。

DEF.43 赋值 Scheme中的赋值语法形式为: (set!<name> <value>) 对任何改变值的操作,scheme约定都以!结尾。 我们可以将变量封装在过程中,表示了只有该过程可以访问,这样就构建了一种被称为局部变量的结构。

事实上,引进赋值的概念带来了一个问题:这使得我们能够理解Scheme求值过程的代换模型在这里失效了。 与所有状态必须显式操作和传递额外参数相比,赋值和将状态隐藏在局部变量中,可以以一种更模块化的方式构造系统。

引入赋值带来的最本质的变化,就是我们的语言中的符号并不仅仅作为语法层面上值的名字,而是表示指向了一个存储值的位置,而这个指在寄存器中又是可以改变的。

DEF.44 引用透明性 如果一门语言具有“同一的东西可以在表达式中互相替换”的性质,而不会改变相关表达式的值,我们就称这门语言具有引用透明性。

有关同一性的指代,如果我们给一个对象取以别名,并观察它和它的别名的变化方式,我们就能确定它们是同一的了,但是这样在程序设计中将会引入副作用错误,这使得有些人主张程序语言中不应该有别名(Lampson et al. 1981)

命令式的程序设计会强迫人们去思考赋值的顺序和关联性,这大大增加了复杂度和容易出错的几率。

 

3.2 求值的环境模型

DEF.45 环境 环境是框架的序列,他确定了值与约束之间的关系。一个框架则是约束的对偶表格,每一个约束会将一个符号关联于一个值上。同时我们还有以下几条规则:

  • 框架永远指向一个外围环境,除非这个框架是全局的
  • 在一个框架中,一个变量只能有一个约束。
  • 一个变量在这个环境中的值是第一个出现该变量的框架中约束值
  • 一个变量可以是无约束的
  • DEF.46 遮蔽 如果一个变量在环境多个框架内都有约束,我们会说,前序的框架约束遮蔽了之后的约束。

    以上便是环境模型最基本的定义

    基本上,环境模型和代换模型在求值的表述方面没有什么差异,但是,环境模型却能够解决所谓的将复合过程应用于参数究竟是一个怎么样的过程。 如果我们把过程看作一个Lambda表达式和指针构成的序对,那么就可以将过程的环境定义为产生过程的环境,因此define的作用也就是将约束加入环境。 应用过程的原理其实是,创建一个更靠前的新环境,并将形式变量约束为实际参数。

     

    3.3 用变动的数据做模拟

    DEF.47 变动数据和改变函数 操作来修改数据对象成员的函数被称为改变函数,具有可变动的成员的数据对象被称为变动数据

    我们可以看出,对数据对象的变动是在指向性上的变动,即将原本指向某个数据的指针改变位置,这样会产生一些不必要的冗余数据,在没有自行管理内存或者具有垃圾收集机制编译器支持的情况下,应该谨慎使用这些操作。

    当一个数据对象被同时用在了多个结构中时,就说这些结构共享了这个数据。由于Lisp中的符号是默认共享的,因此我们无法改变符号指针的指向,这也是Lisp的eq?基本过程能够奏效的原因。 我们也因此可以用eq?来检查数据的相等性 由此带来的问题是,如果数据对象本身也是具有标识,或者说,是存储在计算机内存中的信息,同一性的问题虽然可以被暂时解决,但也会在某种程度上失效。

    赋值是我们所需的所有来改变变动数据的手段,将赋值引入语言后,我们甚至拥有了改变环境的能力

    我们尝试着用变动数据对象来构造一个FIFO的队列

    有了变动赋值的能力,我们同样也能创建出一个键值对映射的多维表格,这个表格可以为我们第二节所学习的通用型操作系统做出贡献

    以事件驱动的模拟程序来模拟数字电路,同样也可以使我们更加深刻地理解整个系统的行为 数字电路中功能块的延迟问题,使我们设计电路的时候所能够遇到的主要问题。

    使用一种基于表结构的扩展数据结构,待处理表,就可以很方便的模拟数字电路的时延问题

    DEF.48 约束系统 在一般的计算机语言中,我们往往描述一些动作为取得一定量的输入,执行指令并生产出一定量的输出,这个系统显然无法创造出通用的求解例如方程这样的约束系统的程序。 一个约束系统是指将变量通过一定的运算组合而成的等式或是不等式,求解约束系统的工作要面对的问题是约束的传播,如何正确描述约束在两个变量之间的不同关系。 我们同样也可以使用约束网络来组合各种约束关系,在这个网络中,约束被通过连接器连接起来。连接器保存值,用于参与约束的计算。 非定向的计算是约束系统的重要特征。

     

    3.4 并发:时间是一个本质问题

    所有潜藏在赋值,命令和同一性问题之后的中间问题……其实是一个关于时间的问题。 我们引入了赋值,由此使得我们能更好的模拟现实世界,也使得时间作为一个不可忽视的重要变量被考虑了进来。

    由此带来的一个问题,现实中对象的活动可能不是顺序执行的,相反,是“同时”发生的(至少在我们看起来是如此),这时用一系列并发执行的进程(Process)来处理事务就是一个十分自然的想法。 然而实际上,真实处理器采用的流水线策略使得命令总是顺序执行的,这时候,在程序设计领域深入的模拟并发就成了一个关键所在。

    解决并发问题的核心所在实际上是出现了进程间无法通信的情况。 第一个可能的解决方案非常简单,完全拒绝了并发的操作。 另一个方式是,使得并发的结果和某种顺序的执行结果保持一致。 并发函数具有内在的不确定性,它往往只是一系列可能值的集合。 我们设想一个热量的流动的模拟,这个特殊的并发中,无论采用何种顺序执行都会得到正确的结果,这也是并发的最理想情况。

    显然以上的处理方式都不够通用化,在处理更多的并发进程时,代价是无法忍受的。

    DEF.49 串行化组 串行化所做的事情就是,将一系列进程分为几个集合,使得,集合之间能够并发的执行,而集合之内却不允许。

    我们先介绍一个叫做parallel-execute的过程,这个过程接受多个无参函数做参数,然后并行的运行它们。 然后我们构建串行化组,使得在其中的过程都不能并发的执行。

    我们不得不采用破坏模块化的代价来解决多重资源共享的并发问题,通过取消让对象自动管理串行化,我们显式地调用每个进程的串行组来锁死这些共享的资源。

    DEF.50 互斥元与信号量 互斥元是一种基于信号量机制的简化处理,它能够解决并发进程共享资源的互斥问题。 一个互斥元描述如下: 它可以被获取和释放,一旦它被获取,那么任何对于它的下一次获取都要在释放之后进行。 互斥元能够正常工作的核心所在是它一定得是一个原子级的操作。 在采用了时间片模型的处理器中,我们就得禁止设置值与检查值之间中断。 而在多处理器的机器中,我们就需要用专门指令和仲裁器来完成这项工作。 遗憾的是,我们无法制造出一个百分之百公平的仲裁器,除非允许它运行无限的时间。

    DEF.51 死锁 当两个串行化的进程互相阻塞,导致无法继续运行的情况被称为死锁。 有些死锁无法避免,一个一般性的避免死锁的方法是,创造一个枚举获取共享资源的方式。 当有些死锁无法避免时,就需要一种称为死锁恢复的方法

    并发系统的设计一个更加深刻的问题是,我们无法准确的定义共享状态的含义。 由于流水线和缓存的存在,串行化实际上在实际中非常低效,一个用于取代它的方法是屏障同步,即使得进程随意地并发执行,但设置一些同步点,任何进程不能在所有进程到达同步点前穿过它。 本质上,任何并发系统的时间问题都其实是进程间的通信问题,一旦确立的全局的通信次序,在任意时刻单个进程的正确性就能够得到保证,而在这个时间点地资源地同一性问题,实际上就变得无关紧要了。 我们在并发和状态系统中遇到的困难,可能是现实世界最基本复杂性的一种反映(信息的传播速度与时间)

    注:考虑到内容的特殊性,本节所有代码均尚未经过测试。

     

    3.5 流

    让我们重新从头开始考虑对世界的模拟。 我们的模拟基于一个将变量看作离散化的随时间变化的量的集合,但是,当我们仅仅需要考察变量的时间史时,单一的量就变得不重要了,我们仅仅需要确知那个与时间相关联的函数而已。

    我们之前已经采用了累积器和过滤器以及映射等优美的概念来处理序列,但是这种优雅带来的代价便是极其地低效。 流就是这样一个非常巧妙的想法,它通过部分构造出流结构供访问,大大提升了效率,这种由需要驱动的思想非常的深刻。这样我们完成的工作,松弛了计算中事件实际发生的顺序和过程的表面结构的关系。

    我们可以简单地将delay过程描述为返回一个无参函数,过程体则是原来的那个表达式。当然在这边也可以使用一种记忆化的方式去优化流。实际上,实现流的方式多种多样,在Algol中,由于按名调用特性的存在,表也自动成了流,而记忆化的过程其实也可以被称为按需调用。

    意料之中的是,我们可以用流来定义出所谓的无穷的对象,因为我们生产的永远只是一个允诺,而不是现实的值。

    一种被称为序列加速器的技术,可以帮助序列快速收敛。

    我们原本的设计就是将流表示为信号的数字形式,那么反过来,我们也能用流方便地建模数字信号系统。

    我们能够隐式定义数字电路中循环的能力,其实都来自于delay这个函数,它能够在构造出本身之前就完成对后一项的求值,但是,有时我们不止需要隐式去定义delay,还需要显式地去定义。 我们这时候需要保证一个对象,也就是被积函数作为延时参数来传递给过程。

    上述例子让我们看到了显式调用delay和force的好处,但是我们也必须为普通的integral和delay的建立一个通用的高阶过程。 在这样的情况下,ML语言的类型推导就能在高阶过程中维持一定的数据类型区别,这也是数据类型多态的一种体现。 一个完全延时求值的例子就是采用惰性求值的Haskell,但是这也带来了在模拟变动数据上的一些困难,如何将这两者结合起来,依然是很有价值的问题。

    为了更好地体现流的优势,我们可以用它来实现随机数和蒙特卡洛过程,在这里,既不需要赋值也不需要局部状态。

    流真正带给我们的,其实是一种将时间显式表示出来的方式,实际上,这使得我们甚至能够用良好定义的数学函数——其输入完全决定了输出来模拟变动的数据。 这当然是因为角度的不同,就如观察粒子的状态,如果我们在粒子的世界线上观察,其实它也没有发生变动。

    因此我们思考问题有了两种角度,当我们要模拟现实世界的一样事物时,或者是将其作为变量,对象引入计算机,这种思考方式是简单直观的,或者是,我们试着找出一个过程来更好的处理这个事物,使之继续能在不变性中得出变化。 我们也就可以看到FP语言在并发系统中的强大威力了。 实际上,流中也有一些时间的麻烦,设想我们归并并发流的顺序,就会发现这是不确定的,这种不确定说明了归并有时候并不时一个函数,而是一种关系,这是来自并发本质的不确定性。 所谓的对象观点和函数式观点的优劣性争端,也突出了我们在本质认识论的争端:这个世界是连续的无状态函数,还是单一的具有关系集合的对象集?我们期待有着一个大统一的理论出现。