《SICP》中的练习题(Guile实现)。
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
ex1
ex2
ex3
LICENSE
README.md

README.md

SICP

《Structure and Interpretation of Computer Programs》练习题

使用guile来做练习,运行平台为windows + cygwin 在linux环境下,须修改guile的运行路径

2013-03-06

目前《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》。

2013-02-18

《SICP》第二章的学习,断断续续持续了有大半个月了,今天我要结束第二章的学习,计划进入第三章。下面趁自己还没完全忘光,小结下第二章学习:

这章主要讲了如何将数据组合起来,形成复合数据。通过序对和列表这种基本数据结构来保存数据,使用一系列的过程来构造复杂的复合数据。在构造复合数据的过程中,要经过良好的设计,将底层实现的细节有效的屏蔽起来。使得在操作复合数据时,不必关系每种复合数据内部的细节。

为了解释复合数据的过程中如何进行良好的抽象屏障,本章给出了一个极端的例子。完全通过过程来实现基本的数据类型,如整数,并给出了基本运算过程+1等。通过这个例子来说明,数据内部的实现过程可以是多种多样甚至是不可思议的,只要满足运算法则,则可以不管它内部的实现细节。

后面讲了使用不同的构造方法来构造复合数据,有可能会出现不同的运算结果,在这里一定要当心。接着便到了list这种基本数据结构上场了,通过序对来实现list,介绍了对列表和树的映射操作。使用序列作为约定的界面,可以将很多过程看做是信号流图。过程可以看做对序列做map、filter、accumulate的组合来得到结果,也就是模块化的操作。初始的数据从一段流入,经过几个模块的过滤、映射以及累积,流出的便是需要的数据。从序列的操作中提取几个共有的模式,讲这几个模式编写成通用的模块,就可以处理很多常见的问题,大大节省了编程的时间,提高了解决问题的效率。设计一个图形语言,这一节我没有学习。大概讲的还是怎么设计复合数据以及操作它们的过程,来实现我们想要的功能。

2.3节的符号数据,我也是过了一遍,并没有对其中的例子进行练习。通过将符号作为参数,在过程中比较符号参数来实现对应的操作,给予了编程极大的灵活性。这节这后的内容我没有认真练习,因为实在是太多太复杂了。我准备在见识到lisp更美妙的特性后,在来好好的补习下第二章后面的内容。

小结一下,《SICP》第二章给出了lisp之所以叫lisp的最重要的两样特性,一个是列表作为约定的数据结构来制造复合数据,另一个是符号操作,因为lisp一开始设计时就是为了方便的进行符号操作。在第三章的学习时,我将继续把第二章中一些重要的我没理解的lisp概念和技巧弄弄清楚,回头再来好好做下第二章后面的练习题。

2013-01-23

今天结束了第一章的学习,lisp开始初步展现出魔法。 将过程(也就是函数)作为第一级元素,给了lisp强大的表达力。 过程可以用变量命名,可以给过程做参数,可以作为过程的返回值。 我看到,lisp代码几乎是数学公式的精确定义。 第一章主要是讲的过程的抽象,如何将算法精准的编程。 我大开了眼界,这是在其他编程语言中没法体会到的神奇。 第二章将主要讲数据的抽象,希望继续好好学习,好好掌握。