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

共17个文件

pdf：17个

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

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

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源推荐

资源详情

资源评论

收起资源包目录

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)))))

评论收藏

内容反馈

Simon_click

2014-05-14

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

2013-12-06

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

2013-11-14

资源不错，不过跟书上的差不太多
月来香满衣

2013-05-29

配合书一起看的
JanitaK

2013-05-24

这个资源非常不错，不但能够作为专业方面的知识，也可以给一些非计算机专业的朋友普及。最好配合书一起看

前往

页

xiahongtao

粉丝: 4
资源: 3

会员权益专享

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

蓝光主板详细故障代码分析

优博讯i6200S:I6300A刷机方法.zip

由于资源大于15M,所以无法一次上传.分上,下两个部分.

Linux下core文件的使用方法详解

2012-2017真题分析与解答

reading-sicp:《计算机程序的构造和解释》(SICP) 解题集

计算机程序的构造与解释

SICP 计算机程序的构造与解释

casa-do-estudante

专题资料（2021-2022年）dfsservice海工港口工程的长效防腐设计草案20100712要点.doc

账号密码查看器

彩灯控制系统（控制8个不同颜色的彩灯依次由暗变亮）

有源滤波器设计及计算方法

SICP 计算机程序设计与解释 中文版

sicp-study-group:一个研究计算机程序结构和解释（SICP）的研究小组

SICP 习题答案

sicp-solutions:“计算机程序的结构和解释”（SICP）中的练习解决方案

表面波演示软件SWCT

蝴蝶小程序

viewy:在Rails中管理Postgres视图依赖关系的工具

xvideo-js：CLI应用程序选择视频，将其添加到收藏夹，查看视频标签，然后在浏览器上打开视频。 :waving_hand::crossed_fingers::vulcan_salute:

高等数学 第7版 上册 同济大学

SICP 计算机程序设计与解释 Structure and Interpretation of Computer Program 英文版

SICP 使用的scheme解释器

计算机程序设计与解释(英文版word文档）（Structure and interpretation of Computer Programming)

sicp-in-python（中文版+英文版）PD

SICP-racket:计算机程序的结构和解释中代码示例的框架实现

会员权益专享

最新资源

SICP 计算机程序设计与解释中文版

高等数学第7版上册同济大学