北京大学，计算机程序构造和解释（SICP）课件，裘宗燕老师主讲

共17个文件

pdf：17个

5星 · 超过95%的资源需积分: 44 171 浏览量 2010-05-10 09:26:35 上传评论 4 收藏 3.66MB RAR 举报

《计算机程序构造和解释》（SICP，Structure and Interpretation of Computer Programs）是一本具有深远影响力的计算机科学教材，由Harold Abelson和Gerald Jay Sussman编写，MIT Press出版。这门课程由北京大学数学学院的裘宗燕教授主讲，他是该书中文版的译者，因此在讲解时能够深入浅出地传达原书的精神和精华。 SICP不仅是一本关于编程的书籍，更是一本探讨计算概念和方法的教科书。它以Lisp语言作为教学工具，因为Lisp的简洁性和表达力强，非常适合用来展示程序的构造和解释过程。通过学习SICP，学生将能够理解如何设计、分析和实现复杂的程序系统，培养出强大的抽象思维能力。课程内容涵盖了以下几个关键知识点： 1. **基本编程概念**：包括变量、数据结构（如列表、树）、控制结构（条件语句、循环）、函数定义与应用等。 2. **过程和数据抽象**：讨论如何使用函数来封装复杂操作，以及如何通过数据结构表示复杂数据，从而实现模块化和代码重用。 3. **递归**：深入探讨递归原理，它是函数式编程中的核心概念，用于解决各种问题，如遍历数据结构、求解数学问题等。 4. **元编程**：学习如何编写可以操作和扩展自身的程序，理解和实现编译器和解释器的基本原理。 5. **动态类型和动态绑定**：Lisp使用动态类型系统，允许在运行时改变变量的类型，动态绑定则让函数参数的绑定可以在执行时确定。 6. **组合器和解释器**：构建简单的解释器，理解程序的执行过程，学习如何将高级语言转化为机器可理解的形式。 7. **符号处理**：利用Lisp的符号处理能力，实现符号计算和自动推理。 8. **硬件模拟**：通过软件模拟硬件行为，理解计算机系统的底层工作原理。 9. **并发和分布式计算**：探讨多线程和分布式计算模型，为现代并行计算打下基础。 10. **软件工程**：讨论软件开发的组织和管理，以及调试和测试策略。裘宗燕老师的讲解将理论与实践相结合，不仅涵盖SICP原著的精髓，还可能结合实际案例，帮助学生更好地理解这些概念。通过北京大学的这门课程，学生不仅能掌握编程技能，还能培养出深厚的计算思维，对未来的计算机科学研究或职业发展大有裨益。压缩包中的“SICP 北大课件”文件可能包含课件、讲义、习题解答等资料，是学习SICP的宝贵资源。

资源推荐

资源详情

资源评论

收起资源包目录

SICP 北大课件.rar （17个子文件）

SICP 北大课件

sicp00.pdf 164KB

sicp05-3.pdf 241KB

sicp02-3.pdf 163KB

sicp04-2.pdf 151KB

sicp05-1.pdf 270KB

sicp05-2.pdf 184KB

sicp02-1.pdf 245KB

summary.pdf 110KB

sicp03-4.pdf 238KB

sicp04-1.pdf 209KB

sicp01-1.pdf 173KB

sicp03-3.pdf 206KB

sicp03-1.pdf 149KB

sicp03-2.pdf 384KB

sicp01-2.pdf 269KB

sicp04-3.pdf 246KB

sicp02-2.pdf 800KB

程序设计技术和方法

裘宗燕，2009-2010 -1-

2. 构造数据抽象(2)

本节讨论

 数据抽象和操作的实例：一个图形语言

 符号数据（与数值数据对应）

 符号表达式的处理（计算，符号计算）

 抽象数据的多重表示

 数据导向的程序设计

 消息传递

程序设计技术和方法

裘宗燕，2009-2010 -2-

一个图形语言

 以一个构造图形的简单语言为例，展示数据抽象和闭包的作用和威力

 其中高阶过程扮演了关键性的角色

 主要功能：构造具有重复性元素的图形，元素按规则变形变大小

 两个这种图形的例子：

像 Escher 画的图（当然，远没那些画复杂，也没那么深刻）

程序设计技术和方法

裘宗燕，2009-2010 -3-

图形语言：基本想法

 基本元素：painter。一个 painter 画出一种特定图像

 可根据要求对所画图像进行操作（改变大小和变形）

 画出的图像依赖于具体框架。如：

组合图像的方式：（假设定义了各种组合操作，具体实现见后）

 beside 使用两个 painter，让它们分别在左右半区域画图

 below 使用两个 painter，让它们分别在上下半区域画图

 flip-vert 使用一个 painter，画出上下反转后的图

 flip-hozil 使用一个 painter，画出左右反转后的图

wave 画的图 rogers 画的图

程序设计技术和方法

裘宗燕，2009-2010 -4-

图形语言：组合

 一个或几个 painter 组合起来还是 painter

(define wave2 (beside wave (flip-vert wave)))

(define wave4 (below wave2 wave2))

 应该考虑 painter 的重要组合模式，并将其实现为Scheme过程

 例如，抽象出 wave4 里的模式：

(define (flipped-pairs painter)

(let ((painter2 (beside painter (flip-vert painter))))

(below painter2 painter2)))

(define wave4 (flipped-pairs wave))

 可能从一个过程

抽取出多个不同

的模式

 如对 wave4，可

考虑将反转方式

抽取出来作为过

程参数

 可有其他考虑

定义好的操作可用

于任何painter

程序设计技术和方法

裘宗燕，2009-2010 -5-

图形语言：组合

 向右分割和分支：

(define (right-split painter n)

(if (= n 0)

painter

(let ((smaller (right-split painter (- n 1))))

(beside painter (below smaller smaller)))))

(right-split wave 4) (right-split rogers 4)

程序设计技术和方法

裘宗燕，2009-2010 -6-

图形语言：组合

 向右上角分割和分支：

(define (corner-split painter n)

(if (= n 0) painter

(let ((up (up-split painter (- n 1)))

(right (right-split painter (- n 1))))

(let ((top-left (beside up up))

(bottom-right (below right right))

(corner (corner-split painter (- n 1))))

(beside (below painter top-left)

(below bottom-right corner))))))

(corner-split wave 4)

(corner-split rogers 4)

还可以定义更复杂的图形

组合过程

程序设计技术和方法

裘宗燕，2009-2010 -7-

图形语言：组合

 把四个 corner-split 按适当方式组合，定义下面 square-limit，就可以

生成本节开始的两个图形：

(define (square-limit painter n)

(let ((quarter (corner-split painter n)))

(let ((half (beside (flip-horiz quarter) quarter)))

(below (flip-vert half) half))))

(square-limit rogers 4)

程序设计技术和方法

裘宗燕，2009-2010 -8-

图形语言：高阶操作

 前面对 painter 的组合模式进行抽象，定义了几个过程。同样可以对

painter 的组合操作进行抽象，定义高阶过程，它们以对 painter 的操

作作为参数，产生对 painter 的新操作

 例：flipped-pairs 和 square-limit 都是将原区域分为4块，而后按不同

变换方式摆放四个部分的图像。把这 4 个变换抽象为过程参数：

(define (square-of-four tl tr bl br)

(lambda (painter)

(let ((top (beside (tl painter) (tr painter)))

(bottom (beside (bl painter) (br painter))))

(below bottom top))))

 重新定义 flipped-pairs：

(define (flipped-pairs painter)

(let ((combine4 (square-of-four identity flip-vert

identity flip-vert)))

(combine4 painter)))

程序设计技术和方法

裘宗燕，2009-2010 -9-

图形语言：框架

 假设已有框架的构造函数 make-frame，选择函数 original-frame,

edge1-frame 和 edge2-frame

需要一个映射由给定 frame 生成一个过程，它由向量参数生成所需向量：

(define (frame-coord-map frame)

(lambda (v)

(add-vect

(origin-frame frame)

(add-vect (scale-vect (xcor-vect v)

(edge1-frame frame))

(scale-vect (ycor-vect v)

(edge2-frame frame))))))

现在考虑 painter 本身及其技术基础

 图像的显示框架可以用3个向量表示：

 基准向量描述框架基准点的位置

 两个角向量分别描述两个相邻角的相对位置

平面向量 v 有两个分量

生成的过程用 frame 变换给定向

量（移基点/两方向比例变换）

程序设计技术和方法

裘宗燕，2009-2010 -10-

图形语言：painter

 每个 painter 都是一个过程，它以一个框架为参数，通过适当的位移和

放大缩小，将它要画的图形嵌入由参数给定的框架里

 基本 painter 的实现依赖于具体图形系统和被画图像的种类。例如，假

定有画直线的基本过程 draw-line，用线段表的方式表示折线图形中的

折线，就可以用下面过程画出各种折线图：

(define (segments->painter segment-list)

(lambda (frame)

(for-each

(lambda (segment)

(draw-line

((frame-coord-map frame) (start-segment segment))

((frame-coord-map frame) (end-segment segment))))

segment-list)))

实现适当的线段表表示（也是一种数据抽象），给出 wave 图形的线

段表，就可以用 segments->painter 定义出 wave

程序设计技术和方法

裘宗燕，2009-2010 -11-

图形语言：painter，变换和组合

 用过程表示 painter，在图形语言里建立了一种很好的抽象屏障

容易创建基本 painter，容易通过组合构造复杂的 painter

任何以框架为参数，基于它画图的过程都可作为 painter

 对 painter 的操作都是创建新 painter，如 flip-vert 和 beside，其中用

到作为参数的 painter，还涉及框架变换

 对 painter 的操作都基于 transform-painter 定义。它以一个 painter

和变换框架的信息为参数，基于变换后的框架调用原 painter。框架变

换信息用三个向量描述，分别表示新基准点和两个边向量的终点

(define (transform-painter painter origin corner1 corner2)

(lambda (frame)

(let ((m (frame-coord-map frame)))

(let ((new-origin (m origin)))

(painter

(make-frame new-origin

(sub-vect (m corner1) new-origin)

(sub-vect (m corner2) new-origin)))))))

程序设计技术和方法

裘宗燕，2009-2010 -12-

图形语言：变换和组合

 各种 painter 变换都可以基于过程 transform-painter 定义

 如纵向反转 flip-vert ：

(define (flip-vert painter)

(transform-painter painter

(make-vect 0.0 1.0) ;neworigin

(make-vect 1.0 1.0) ; new end of edge1

(make-vect 0.0 0.0))) ; new end of edge2

 将框架收缩到原区域的右上四分之一区域：

(define (shrink-to-upper-right painter)

(transform-painter painter (make-vect 0.5 0.5)

(make-vect 1.0 0.5) (make-vect 0.5 1.0)))

 将图形逆时针旋转 90 度：

(define (rotate90 painter)

(transform-painter painter (make-vect 1.0 0.0)

(make-vect 1.0 1.0) (make-vect 0.0 0.0)))

程序设计技术和方法

裘宗燕，2009-2010 -13-

图形语言：变换和组合

 将图像向中心收缩：

(define (squash-inwards painter)

(transform-painter painter (make-vect 0.0 0.0)

(make-vect 0.65 0.35) (make-vect 0.35 0.65)))

 beside 以两个 painter 为参数：

(define (beside painter1 painter2)

(let ((split-point (make-vect 0.5 0.0)))

(let ((paint-left

(transform-painter painter1 (make-vect 0.0 0.0)

split-point (make-vect 0.0 1.0)))

(paint-right

(transform-painter painter2 split-point

(make-vect 1.0 0.0) (make-vect 0.5 1.0))))

(lambda (frame)

(paint-left frame)

(paint-right frame)))))

程序设计技术和方法

裘宗燕，2009-2010 -14-

强健设计和语言分层

 总结：图形语言里的 painter 和基本数据抽象都用过程表示。这样能

 以统一方式处理各种本质上完全不同的基本画图功能

 组合方式有闭包性质，已有 painter 的组合仍然是 painter

 所有过程抽象手段都可以用于组合各种 painter

 复杂系统应该通过分层设计完成

 描述这些层次需要一系列语言

 通过组合一个层次中的各种基本元素，得到另一更高层次的元素

 每层提供基本元素、组合手段和抽象手段，支持更高层次的构造

 在图形语言实例中：

 基本语言提供基本图形功能，如为 segmant->painter 提供画线段功能，

为 rogers 提供画图和着色功能

 一组基本 painter 提供基本图形，beside 和 below 等操作 painter

 在此之上实现图形操作的组合，以 beside 和 below 等作为操作对象

程序设计技术和方法

裘宗燕，2009-2010 -15-

符号数据和符号处理

 早期计算机只用于处理数值数据，主要应用是科学和工程计算

 随着计算机应用发展，人们看到越来越多的非数值计算问题。Lisp语言

原本就是要支持非数值计算，数值计算是后加的。下面讨论 Scheme

的这方面情况，许多问题在非数值应用中有普遍意义

 首先介绍如何把处理任意符号的功能引进 Scheme。符号计算中处理的

是下面形式的表达式（符号表达式）：

(a b c d)

(234517)

((Norah 12) (Molly 9) (Anna 7) (Lauren 6) (Charlotte 4))

符号表达式形式上就像是 Scheme 程序：

(* (+ 23 45) (+ x 9))

(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))

 为描述和处理任意符号表达式，需要有一种方法来说任意的符号（以及

符号表达式）本身，而不是说符号的值

程序设计技术和方法

裘宗燕，2009-2010 -16-

符号数据：引号

 自然语言中也需要区分词语本身和词语的意义，如

我们现在把“我们”写五遍

他把写了“桌子”的纸条贴在桌子边上

 Scheme 用类似形式描述符号对象，在被引表达式

前加单引号，就表示这个表达式自身

(define a 1)

(define b 2)

(list a b)

(1 2)

(list 'a 'b)

(a b)

(list 'a b)

(a 2)

 引号不仅可以用于单个的符号，也可以用于“组合对象”

(car '(a b c))

(cdr '(a b c))

(b c)

 为实现符号操作，有基本谓词 eq?，它判断是否同一个符号。例

(define (memq item x)

(cond ((null? x) false)

((eq? item (car x)) x)

(else (memq item (cdr x)))))

评论收藏

内容反馈

Cap_zhou

2013-12-06

资源时扫描版的，不是很清楚啊
zenghao0708

2012-09-14

配合书一起看，很不错的
Simon_click

2014-05-14

挺好的，看看裘老师的理解后的SICP。可以知道这本书的重点。lisp太难读了
luopuya

2013-02-01

资源挺好的，但是直接在课程主页就可以下了http://www.math.pku.edu.cn/teachers/qiuzy/progtech/下
lovedhuier

2013-11-14

资源不错，不过跟书上的差不太多