megrxu

SICP 读后

Apr 18, 2020  「PL」  

暑假读了一下 SICP。

函数式和抽象

最前面的一小沓许多都是常规函数式编程中老生常谈的部分。但是跟着作者的脚步,能够很明显地发现他们把「抽象」放在了一个非常高的角度。从小的,一般的情况开始玩弄,最后推广;后来发现推广的一般式是一个更一般式的特殊形式,从而使得最初的几例亦可以用这种推广进行实现。

另外,一些例子还「强迫」读者不再使用过程式的思维,考虑任何的「寄存器」了。将值在程序调用时进行传递(例如大量的把递归改为迭代的练习题),从而使得纯函数能够做大量以前以为需要改变临时变量的值才能做到的事情,并且也没有引入可见的时间或空间冗余。这些是书中所谓的「过程抽象」。

除了程序本身,下层对上层的抽象屏障还使得「接口」这种东西变得异常清晰。只要一些声明,就可以开发不同层次的程序,而无需考虑底层的设计细节。就我理解来看,这是抽象在设计模式方面的一个简单应用,但是在 SICP 中显得非常自然。进一步,有了接口,以及对于大量不同对象的类似操作,则必然就需要有通用性系统进行「分发」:根据对象的类型和操作名,分发给他对应的函数。到后期开始实现「类型塔」和类型之间的转化,也显得不是那么难了(如果让我直接去想怎么实现,我感觉我很快就会把问题变得非常复杂)。

再谈副作用 – 以及模拟世界的另一种方式

和纯函数打了一段时间交道,接下来就得看看环境模型了。这个模型下,变量的值并不是每时每刻都一样的,因为存在了有副作用的函数。副作用使得函数(或者说对象)本身带有了状态,从而可以做到很多以前做不到的事情。例如银行的账单。直观来看,似乎几乎不可能通过纯的函数进行实现,毕竟账户的值是一个变动的值,无法使用一个函数来进行记录。函数的副作用引来了好处,也当然引来了痛点:我们必须小心地维护这些状态,以便他们按照我们意图的方式工作;函数执行的先后顺序,也可能需要特别考虑。

更惊人的是,实际上通过「流」,一种延迟(按需)计算的,可以用纯函数实现的数据结构,可以实现无状态的银行账户,从而在另一个角度来模拟这个物理世界。这样定义出来的函数本身是无状态的,但是用户的交互赋予了它状态,使得不同时刻它具有了不同的值。更巧妙的结合是,虽然可以使用纯函数来实现这样的「流」,但是如果同时在内部辅以「状态」,例如求值一次之后就将其标记为「已求值的」,则又将会减少一大堆的计算冗余(将来不需要再计算了)。

更进一步:新的语言

其实有了之前的数据抽象,以及对于环境模型的认识,已经可以使用 lisp 构建一个 lisp 的求值器了。但是,这当然是不够的,我们需要更多的可能性,而不是实现已经有的:

  • 对「流」的实现表现了一种「按需计算」的可能性,而这个可能性可以更深层次地嵌入到求值器中去,这便是惰性求值。
  • 开发一个不确定的过程,它可以根据一些约束,来逐渐减小自己的搜索空间。从而使得破解谜题成为可能。即 amb 求值器。
  • 根据逻辑查询语句,搜索模式匹配下的语句,并返回这些满足要求的条目。