笔记仓库

正常人的正常笔记集

SICP从DrRacket钻了出来

标题致敬沙丁鱼从地里钻了出来(イワシがつちからはえてくるんだ)

在条件允许的情况下,一般建议阅读Structure and Interpretation of Computer Programs 和实验时用GNU/MIT Scheme比较合适,不过我之前习惯写了Racket语言懒得转过去,所以还是用DrRacket环境了。我在这里碎碎念一些遇到的问题和解决的方法,其中也不少借助了前人的资料和其他友人的指导,希望能帮助后来人避开一些坑。

参考资料

所以具体怎么安装DrRacket和SICP collection就不必多说了,早一些的资料可能会提到PLaneT包的neil/SICP

1
#lang planet neil/sicp

但这个包已经停止维护了,而且作者也加入了新的SICP支持包的开发团队。所以我也还是推荐按照上述方法按照后使用

1
#lang sicp

接下来会给出一些我在直接使用书中代码实验时遇到的困难,并且将根据我自己的学习进度保持更新


Picture Language

2.2.4 Example: A Picture Language 整个小节的环境差不多都是自定义的,所以其实也无所谓什么语言标准差异了。使用前先声明

1
2
#lang sicp
(#%require sicp-pict)

几个primitive painter过程对象如rogerswave都没有在这个包里实现,不过也无所谓,反正那几个图案你在图样图sample也见过了,主要是测试接下来你写的那些图片处理(旋转,放缩,组合)函数是否正确,那么用这个包的其他painter也可以。

可以通过指定一个0-255的灰度值用(number->painter color)构造一个色块作为painter,或者指定一个图片文件路径用(load-painter filename)构造一个painter。当然我自己为了方便起见直接用built-in的两个painter

1
2
(paint einstein)
(paint diagonal-shading)

调用这两个paint过程会在REPL中打印这两个painter,前者是爱因斯坦的画像,后者是一个沿着对角线方向渐变的灰色色块。einsteindiagonal-shading都是已经被定义完成的painter,都可以用来作为这小节各个函数定义的测试输入。

这个环境中的(transform-painter origin corner1 corner2)的返回结果为(painter? -> painter?)的函数,而原书的transform-painter原型则是(transform-painter painter origin corner1 corner2),需要包括被变形的painter在内的四个参数,直接返回变形结果,而非我们的package中定义的返回一个变形函数。需要稍微注意一下,以免编写时出现传参错误。

Case Sensitive

Racekt语言区分符号和其他identifier的大小写1,而MIT Scheme并不区分。但SICP包并没有在这一点沿用模仿Scheme的特性

1
2
#lang sicp
(eq? 'A 'a) ;#f

Exercise 2.70所使用的Huffman树alphabet全为大写,需要编码的message部分却是含有部分小写。会导致无法找到目标字符在树中的位置。可以使用#ci前缀令所有字符都case-fold到小写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define tree (generate-huffman-tree #ci'((WAH 1)
(BOOM 1)
(A 2)
(GET 2)
(JOB 2)
(SHA 3)
(YIP 9)
(NA 16))))

(define message #ci'(Get a job
Sha na na na na na na na na
Get a job
Sha na na na na na na na na
Wah yip yip yip yip yip yip yip yip yip
Sha boom))

Get/Put

2.4.3 Data-Directed Programming and Additivity已经开始使用putget两个过程了,实际上MIT Scheme也没有内置它们的实现,但书中假设我们已经实现了,Chapter 2都在直接使用它们。实质上,put是对一个二维表进行增操作,get是对同一个二维表进行查操作,这些在Chapter 3,具体来说是3.3.3 Representing Tables部分给出了两个函数的定义。为了提前使用可以照抄Chapter 3二维表部分的所有定义内容,也可以通过Racket的内置hash table实现:

1
2
3
4
5
6
7
8
9
10
#lang sicp
(#%require (only racket/base make-hash hash-ref hash-set!))

(define *op-table* (make-hash))

(define (put op type proc)
(hash-set! *op-table* (list op type) proc))

(define (get op type)
(hash-ref *op-table* (list op type) #f)

Cyclic List

Exercise 3.16 开始出现带有回路的list结构,比如这里一个“长度为无穷大”的list

1
2
3
4
5
#lang sicp
(define n3 (list 'c))
(define n2 (cons 'b n3))
(define w (cons 'a n2))
(set-cdr! n3 w)

在DrRacket的REPL下调用display可以看到这个pair结构是这样表示的

1
2
(display w)
;#0=(a b c . #0#)

借助于Scheme Editor绘制当前环境的box-pointer以及frame图

当然我不推荐你在Scheme环境下试图直接返回w或者调用(display w)打印这个循环的pair结构,Scheme是个老实人,遇到这些list/pair时不会检查它是否含有回路结构,从而陷入一个找不到出口的递归(死循环),这点在原书上也有相关警告:

Be careful not to make the interpreter try to print a structure that contains cycles.

然而这种情况在DrRacket没什么可担心的。Racket在表示循环结构时会引入#n=这样的符号,用来递归定义被表示的对象2#n可以看作某个反身代词,n的取值为从0开始的整数,用于代表需要被表示的某个单元结构。在上面的表达式#0=(a b c . #0#)中,#0用于指代w,#0=后面的表达式表示#0实际上是什么,是(a b c . #0#)这样一个pair,用我们熟悉的写法可以写为(cons 'a (cons 'b (cons 'c #0))),从w开始用3个cdr可以把这个pair剥茧抽丝到#0##0的引用),也就是w本身。

当然,#n的写法也可以用来表达非循环对象3,比如(list 100 100 100)可以表示为(#1=100 #1# #1#)

所以在DrRacket调试带有回路的list时,就算debug工具的中间量也可以直接显示这种表示,就没必要像原书指导的那样如履薄冰了,放心大胆的去尝试探索吧。

Internal Definitions

3.5.4 Streams and Delayed Evaluation 解微分方程的过程中,出现了一个block definition结构的互递归变量定义,当然毫无疑问第一次出现的是哪个Scheme解释器都不可能接受的写法,但是第二次在integral中使用延迟求值参数,如下

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (solve f y0 dt)
(define y (integral (delay dy) y0 dt))
(define dy (stream-map f y))
y)


(define (integral delayed-integrand initial-value dt)
(define int
(cons-stream
initial-value
(let ((integrand (force delayed-integrand)))
(add-streams (scale-stream integrand dt) int))))
int)

在GNU/MIT Scheme是支持的,但DrRacket的解释器并不支持这样的写法,会提示这样的错误

1
2
y: undefined;
cannot use before initialization

毕竟它对internal definitions的实现就是这个样子的,我也很无奈,一时也想不到什么合适的解决方案,试过letrec和双delay都无效。这个坑先放着吧。

另外,这个小节围绕的微分方程$$dy/dt=f(y)$$在编程实现中,无论是电路图上还是代码中的中间变量dy,按照我的个人理解,实际上对应的都是公式中的$dy/dt$,这一点十分让人困惑。我想等我有空了还是发邮件问问作者吧(这也要等有空,不是一顺手的事吗,懒癌发作没救了


  1. 1.https://docs.racket-lang.org/guide/symbols.html
  2. 2.https://docs.racket-lang.org/reference/pairs.html 4.9.8 Immutable Cyclic Data 部分,顺便小声说一句这种表示法的争议比较大,以前还可以用于直接定义循环对象(define x ’#0=(1 . #0#)),现在直接废止这种定义法了,只能用于打印显示,详见http://blog.racket-lang.org/2007/11/getting-rid-of-set-car-and-set-cdr.html
  3. 3.https://docs.racket-lang.org/reference/reader.html