SICP笔记(五)

闭包

In general,an operation for combining data objects satisfies the closure property if results of combining things with that operation can themselves be combined using the same operation.

根据书中脚注,SICP中的闭包只是涉及组合方面的相关特性,并不涉及自由变量。使用闭包特性可以快速地构建复杂性,在本节的实例中我们可以看到其强大的威力。


序列

使用cons,可以轻松地构造序对,有序的序列也可以用cons构造。
(cons <a1> (cons <a2> (cons ... (cons <an> nil) ... )))连续使用cons构造序列,nil意为空表,表示序对的链结束,但是此写法太过冗长,scheme便提供了基本操作(list <a1> <a2> ... <an>),两者是等价的,是语法糖关系。
基本操作list可以构建出序列,序列是一种基本数据结构,我们常常需要对其处理。python中的list,python就提供了很丰富的基本方法,使用python处理list时就很得心应手。基于序列在scheme中的表示,使用递归和迭代的方法,我们构造了一些基本操作,append,reverse等。
想到闭包性质,我们很容易联想序列的元素本身也是序列的情况,第一感觉处理时应该是困难了不少,仔细想想递归的属性,递归当仁不让成为首选,轻松get!
处理层次性结构时,千万不要尝试进入数据的表示层,应当在抽象屏障之上处理数据结构。

Map

map是一种重要的结构,在更高的层次上对表操作进行了抽象。Map为我们建起了一层抽象屏障,将实现表变换的过程与如何提取表中元素以及组合结果的细节隔离开,常与lambda函数配合使用。

八皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
;;; 八皇后问题
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))

(define empty-board '())

(define (adjoin-position new-row k rest-of-queens)
(cons new-row rest-of-queens))

(define (safe? k positions)
(define (iter new-row rest-of-queens i)
(if (null? rest-of-queens)
#t
(let ((current-row (car rest-of-queens)))
(if (or (= new-row current-row)
(= new-row (+ current-row
i))
(= new-row (- current-row
i)))
#f
(iter new-row (cdr rest-of-queens) (+ i 1))))))
(iter (car positions) (cdr positions) 1))

假设已经放好k-1个皇后,在此基础上,在第k列的每一行上摆上皇后,然后过滤合适的解。解法中的flatmap函数使用了嵌套映射,在正确放好k-1个皇后的基础上产生第k列的每一行放上皇后的集合扩展,filter函数通过safe?过滤合适的解。

约定接口

还记得刚开始的时候,老师介绍说,本课程的三大方面,黑盒抽象,约定接口与元语言抽象。
约定接口利于模块化设计,可以单独地设计好模块,解决问题时只需从模块库中挑取合适的模块,组合起来,这种策略就非常灵活了,并且可以重复利用模块,大量减轻工作量。此处,序列是载体,将各种模块化的操作囊括进来,组合我们需要的目标程序。书中,先枚举区间内的数,接着映射,然后对所有结果过滤,累积合适的解。

图形语言

本节的实例是一种图形语言的实现,在这种语言中,基本元素叫painter,不同以往的是,它是由过程表示,给painter传入一个frame参数,painter便在frame画出其表示的图像。因为painter是由过程表示的,于是lisp的组合方法完全适用于此语言,也就是说,这门图形语言嵌套在lisp中。在picture的组合中,因为picture具有闭包性质,我们便可以快速地通过一些基本操作构建复杂的操作。
在这门语言的实现中,我们抽象了好几个层次,在每一层上做出修改,最后的结果也会做出相应的改变。此实例,告诉我们数据和过程之间并没有区别,用过程表示数据,使编程变得简单且优雅!


习题解答:传送门