《Structure and Interpretation of Computer Programs》练习题
使用guile来做练习,运行平台为windows + cygwin 在linux环境下,须修改guile的运行路径
目前《SICP》第三章的学习正在如火如荼的进行中,有点小感悟,总结如下:
第三章第一小节,主要介绍了使用对象化的方法来编程。之前两章中,我们将符号看做是一个名字,指代值或者过程的一个名字。通过第一章介绍的代换模型,总可以把一个过程代换成一系列基本的运算符号。这种也就是所谓的函数式编程,给定固定的输入,获得固定的输出,不会有改变。第三章中引进了赋值操作set!,这个运算符可以改变某个符号的值。这样代换模型就没法很好的解释程序行为了。这里我们不能把符号只看做一个名字,而必须看做是一个对象,拥有自己的值并存放在某处。通过赋值运算符,可以改变符号的值。在不同的情况下,求值同样的过程,可能有不同的解。其实说白了,就是scheme在这里引进了局部变量。
第三章第二小节,引进了为了理解对象化的环境模型。解释了每一个过程本身有符号约束,所在的上层环境中也有符号约束。学到这里,scheme解开了自己内部神秘的面纱。在一个过程所处的上层环境中变量值的改变,会影响这个过程的行为。不知道为什么在这里,《SICP》进行了详尽的环境模型演示,其实这种环境模型就相当于C语言中的变量作用域而已。如果学习了C语言,再来看这一节的解释,就很明了了。整个scheme解释器环境就相当于一个正在运行的main函数,每个变量名都有一个值。如果这个变量是个全局变量,修改变量的值,必然会影响使用它的子函数运算结果。
第三章第三小节,又介绍了一种修改变结构的操作符set-car!与set-cdr!。在我看来,这就是对指针的操作。将scheme中的列表看做是C语言中实现的链表结构,修改scheme的列表中的值,就是对链表指针的操作。后面介绍了设计队列操作的方法,与C语言的队列实现如出一辙。比C语言好的地方是,scheme把指针操作封装起来了,大大保证了安全性。并且自带了垃圾回收,不用手工去释放没用的对象所占的内存。列表也是实现好了,不用自己去用结构体实现。看到这里,我豁然开朗,明白了scheme列表实现的具体细节。我用scheme写了个汉诺塔游戏,其实就是实现好堆栈,写出堆栈操作的过程,与C语言写是没什么两样的。
学到这里,我视乎看到了scheme语言运行的内部过程。与C语言比较起来,scheme的语法更加灵活,数据结构也更加灵活,但说到底,内部细节也是可以想象成一个巨大运行的C程序。这种联系和想象,可以帮助我更好的学习《SICP》。
《SICP》第二章的学习,断断续续持续了有大半个月了,今天我要结束第二章的学习,计划进入第三章。下面趁自己还没完全忘光,小结下第二章学习:
这章主要讲了如何将数据组合起来,形成复合数据。通过序对和列表这种基本数据结构来保存数据,使用一系列的过程来构造复杂的复合数据。在构造复合数据的过程中,要经过良好的设计,将底层实现的细节有效的屏蔽起来。使得在操作复合数据时,不必关系每种复合数据内部的细节。
为了解释复合数据的过程中如何进行良好的抽象屏障,本章给出了一个极端的例子。完全通过过程来实现基本的数据类型,如整数,并给出了基本运算过程+1等。通过这个例子来说明,数据内部的实现过程可以是多种多样甚至是不可思议的,只要满足运算法则,则可以不管它内部的实现细节。
后面讲了使用不同的构造方法来构造复合数据,有可能会出现不同的运算结果,在这里一定要当心。接着便到了list这种基本数据结构上场了,通过序对来实现list,介绍了对列表和树的映射操作。使用序列作为约定的界面,可以将很多过程看做是信号流图。过程可以看做对序列做map、filter、accumulate的组合来得到结果,也就是模块化的操作。初始的数据从一段流入,经过几个模块的过滤、映射以及累积,流出的便是需要的数据。从序列的操作中提取几个共有的模式,讲这几个模式编写成通用的模块,就可以处理很多常见的问题,大大节省了编程的时间,提高了解决问题的效率。设计一个图形语言,这一节我没有学习。大概讲的还是怎么设计复合数据以及操作它们的过程,来实现我们想要的功能。
2.3节的符号数据,我也是过了一遍,并没有对其中的例子进行练习。通过将符号作为参数,在过程中比较符号参数来实现对应的操作,给予了编程极大的灵活性。这节这后的内容我没有认真练习,因为实在是太多太复杂了。我准备在见识到lisp更美妙的特性后,在来好好的补习下第二章后面的内容。
小结一下,《SICP》第二章给出了lisp之所以叫lisp的最重要的两样特性,一个是列表作为约定的数据结构来制造复合数据,另一个是符号操作,因为lisp一开始设计时就是为了方便的进行符号操作。在第三章的学习时,我将继续把第二章中一些重要的我没理解的lisp概念和技巧弄弄清楚,回头再来好好做下第二章后面的练习题。
今天结束了第一章的学习,lisp开始初步展现出魔法。 将过程(也就是函数)作为第一级元素,给了lisp强大的表达力。 过程可以用变量命名,可以给过程做参数,可以作为过程的返回值。 我看到,lisp代码几乎是数学公式的精确定义。 第一章主要是讲的过程的抽象,如何将算法精准的编程。 我大开了眼界,这是在其他编程语言中没法体会到的神奇。 第二章将主要讲数据的抽象,希望继续好好学习,好好掌握。