花了两个月的时间瞄完了SICP,完成了一到三章的大部分习题,第四章照着书上实现了一个元循环解释器,以及一个查询系统,第五章也照着书上模拟了一下机器语言,最后一节编译没有细看,现在做一下总结。
整本书依次介绍了过程抽象、数据抽象、环境模型、解释器、编译器
一、过程抽象
1.正则序先将参数展开然后规约,应用序先对参数求值,然后将值代入,特别要注意的著名的Y combinator只适用于正则序,而通常的lisp解释器都是基于应用序的。
2.迭代型递归只使用常量的内存空间,类似于命令式语言中的循环结构,而普通的递归需要调用栈。
3.高阶函数----过程作为参数,常见的过程map,apply,filter等都用到了高阶函数,lambda表达式返回一个函数。高阶函数是函数式编程最大的特点,C/C++虽然可以调用函数指针模拟map,apply等函数,但并没有lisp这样直观,函数是一等公民。
二、数据抽象
1.闭包性质,以cons为例子,构成序对的元素本身仍然可以是一个序对。按照书上的话说,某个操作满足闭包性质,意味着,通过该操作组合起数据对象的结构本身还可以通过同样的操作继续进行组合。2013.12.05:今天明白当时对闭包的解释存在错误,那么到底什么是fp中的closure到底是什么呢?通俗的讲,闭包性质就是子函数可以访问父函数的局部变量的性质。结合下面的队列实现,闭包性质可以模拟面向对象的代码风格,有另一种解释js闭包的说法是:一个闭包就是当一个函数返回时,一个没有释放资源的栈区
2.lisp的动态数据类型似乎使数据抽象的实现更加灵活。
三、环境模型
1.以消息传递为基础的面向对象系统,通过环境模型(let操作实质为lambda的语法糖)保存局部变量,模拟事物状态的变化过程。下面是一个用消息传递机制实现的队列
(define (make-queue) (let ((front-ptr '()) (rear-ptr '())) (define (empty-queue?) (null? front-ptr)) (define (insert-queue! elem) (let ((new-pair (cons elem '()))) (if (empty-queue?) (begin (set! front-ptr new-pair) (set! rear-ptr new-pair) front-ptr) (begin (set-cdr! rear-ptr new-pair) (set! rear-ptr new-pair) front-ptr)))) (define (delete-queue!) (if (empty-queue?) "error,queue is empty" (begin (set! front-ptr (cdr front-ptr)) front-ptr))) (define (dispatch m) (cond ((eq? m 'print-queue) front-ptr) ((eq? m 'insert-queue!) insert-queue!) ((eq? m 'delete-queue!) (delete-queue!)) ((eq? m 'empty-queue?) (empty-queue?)) (else "no that operation"))) dispatch))
(define (print-queue q) (q 'print-queue)) (define (insert-queue! q elem) ((q 'insert-queue!) elem)) (define (delete-queue! q) (q 'delete-queue!)) (define (empty-queue? q) (q 'empty-queue?)) (define q1 (make-queue))
队列的具体操作以及实现都被封装在了q1的内部,很像C++/JAVA中的类,通过调用(print-queue q1)可以改变q1的状态。
但是这就造成了执行了相同的函数时,返回值不同的问题,也就是“副作用”,通常在纯函数式语言中,不管何时调用一个函数,返回值都是相同,这和数学上的函数是相同,但是在环境模型中由于存在局部状态,通过外部的操作可以改变它。引用赋值的一大代价是对于程序的并发执行所产生的一系列问题,也可以追溯到现代操作系统的进程管理中的资源互斥和共享,其实质也是由于副作用造成的,这也是纯函数式编程中不可能存在的问题。
四、解释器
1.由于SICP上的解释器实现的细节过于繁琐,为了避免扎进细节当中无法自拔,以下引用王垠博客中的一个简版的解释器模型做一个总体的把握,这个模型给出了解释器的一个整体框架
;;; 以下三个定义 env0, ent-env, lookup 是对环境(environment)的基本操作: ;; 空环境 (define env0 '()) ;; 扩展。对环境 env 进行扩展,把 x 映射到 v,得到一个新的环境 (define ext-env (lambda (x v env) (cons `(,x . ,v) env))) ;; 查找。在环境中 env 中查找 x 的值 (define lookup (lambda (x env) (let ([p (assq x env)]) (cond [(not p) x] [else (cdr p)])))) ;; 闭包的数据结构定义,包含一个函数定义 f 和它定义时所在的环境 (struct Closure (f env)) ;; 解释器的递归定义(接受两个参数,表达式 exp 和环境 env) ;; 共 5 种情况(变量,函数,调用,数字,算术表达式) (define interp1 (lambda (exp env) (match exp ; 模式匹配 exp 的以下情况(分支) [(? symbol? x) (lookup x env)] ; 变量 [(? number? x) x] ; 数字 [`(lambda (,x) ,e) ; 函数 (Closure exp env)] [`(,e1 ,e2) ; 调用 (let ([v1 (interp1 e1 env)] [v2 (interp1 e2 env)]) (match v1 [(Closure `(lambda (,x) ,e) env1) (interp1 e (ext-env x v2 env1))]))] [`(,op ,e1 ,e2) ; 算术表达式 (let ([v1 (interp1 e1 env)] [v2 (interp1 e2 env)]) (match op ['+ (+ v1 v2)] ['- (- v1 v2)] ['* (* v1 v2)] ['/ (/ v1 v2)]))]))) ;; 解释器的“用户界面”函数。它把 interp1 包装起来,掩盖第二个参数,初始值为 env0 (define interp (lambda (exp) (interp1 exp env0)))
该模型通过模式匹配(match),对一个scheme表达式进行递归求值,最后返回该表达式的值,其中只定义了基本的操作+,-,*,\,以及对于单参数的lambda表达式的解释,通常当遇到一个lambda表达式时,需要进行环境的扩充,即在原环境的下一层中创造一个新的环境,环境中是变量和具体值的绑定。
scheme中的基本语法define,let,if,cond等都可以通过lambda和interp1以及一些基本条件语句的组合来表达,具体细节可以参考SICP上的实现。
通过上面可以看到解释的基本过程: 给出一个表达式exp->对表达式进行模式匹配->判断子表达式类型->递归求子表达式的值(可能会创建新环境,添加binding)->调用当前过程->返回该表达式的值
五、编译器
1.总结一下垃圾回收机制,将一个内存块分成两块,一个叫做工作存储区,一个叫做自由存储区,当工作存储区中已经没有资源之后,即free指针已在工作存储区的末尾,我们便进行垃圾回收时,可以从每个寄存器出发进行追踪,追踪到的所有位置都是工作存储区中有用的数据,未追踪到的都是废料,此时只需将所有有用数据依次移动到自由存储区(其中不存在有用的数据)。全部移动完毕后在自由存储区中设置一个新的free指针,然后将工作存储去和自由存储区交换,就完成了一次垃圾回收。