作业 4

第 4 课配套作业：SICP 区间算术与列表练习，以及 my-substitute 系列过程练习

模板

在终端输入下面的命令，把模板文件复制到当前目录（注意末尾的句点）：

cp ~cs61as/autograder/templates/hw4.rkt .

或者可以从这里下载模板。

自动评分器

如果你在实验机上，grader 命令会运行自动评分器。如果你在自己的个人电脑上，应该下载 grader.rkt 和作业 4 测试。

热身

试着预测下列表达式会返回什么，然后用 Racket 解释器核对答案：

(define x (cons 4 5))
(car x)
(cdr x)
(define y (cons 'hello 'goodbye))
(define z (cons x y))
(car (cdr z))
(cdr (cdr z))
(cdr (car z))
(car (cons 8 3))
(car z)
(car 3)

练习 1

前几道练习涉及 SICP 2.1.4。区间算术的细节见正文。

SICP 2.7

Alyssa 的程序不完整，因为她没有实现区间抽象。下面是区间构造函数的定义：

(define (make-interval a b) (cons a b))

定义选择函数 upper-bound 和 lower-bound 来补全实现。

SICP 2.8

用与 Alyssa 类似的推理，说明两个区间的差可以如何计算。定义相应的减法过程 sub-interval。

SICP 2.10

Ben Bitdiddle 是位专家系统程序员，他从 Alyssa 肩上看过去，评论说：用跨零区间做除数意味着什么并不清楚。修改 Alyssa 的代码，检查这种情况，并在出现时报错。

重要

注意： 跨零指一个端点 $\leq 0$ 而另一个端点 $\geq 0$ ！

SICP 2.12

定义构造函数 make-center-percent，它接受一个中心值和一个百分比容差，产生所需的区间。你还必须定义选择函数 percent，产生给定区间的百分比容差。center 选择函数与上面给出的相同。

SICP 2.17

定义过程 last-pair，它返回只含给定（非空）列表最后一个元素的列表：

-> (last-pair (list 23 72 149 34))
(34)

SICP 2.20

过程 +、* 和 list 接受任意数量的实参。定义这类过程的一种方法是用点尾记法（dotted-tail notation）配合 define。在过程定义中，形参表最后一个形参名前面有一个点，表示调用过程时，前面的形参（如果有）照常取前几个实参的值，而最后一个形参的值是剩余实参组成的列表。例如，给定定义

(define (f x y . z) <body>)

过程 f 可以用两个或更多实参调用。如果我们求值

(f 1 2 3 4 5 6)

那么在 f 的函数体中，x 是 1，y 是 2，z 是列表 '(3 4 5 6)。给定定义

(define (g . w) <body>)

过程 g 可以用零个或更多实参调用。如果我们求值

(g 1 2 3 4 5 6)

那么在 g 的函数体中，w 是列表 '(1 2 3 4 5 6)。

用这种记法写过程 same-parity，它接受一个或多个整数，返回所有与第一个实参奇偶性相同的实参组成的列表。例如，

-> (same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

-> (same-parity 2 3 4 5 6 7)
(2 4 6)

SICP 2.22

Louis Reasoner 想改写练习 2.21 的第一个 square-list 过程，让它产生迭代过程：

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) 
              (cons (square (car things))
                    answer))))
  (iter items nil))

不幸的是，这样定义 square-list 得到的答案列表顺序与期望的相反。为什么？

Louis 随后交换 cons 的实参顺序来修这个 bug：

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))

这样也不行。解释为什么。

练习 2

写过程 my-substitute，它接受三个实参：一个列表、一个旧词和一个新词。它应返回该列表的副本，但旧词的每次出现都换成新词，包括子列表中的出现。例如：

-> (my-substitute '((lead guitar) (bass guitar) (rhythm guitar) drums)
                  'guitar
                  'axe)
((lead axe) (bass axe) (rhythm axe) drums)

你可能会觉得过程 list? 有用：

-> (list? (list 1 2 3))
#t
-> (list? 'apple)
#f
-> (list? 4)
#f

练习 3

现在写 my-substitute2，它接受一个列表、一个旧词列表和一个新词列表；后两个列表应等长。它应返回第一个实参的副本，但第二个实参中出现的每个词，换成第三个实参中对应的词：

-> (my-substitute2 '((4 calling birds) (3 french hens) (2 turtle doves))
                   '(1 2 3 4)
                   '(one two three four))
((four calling birds) (three french hens) (two turtle doves))

专家挑战

想做就做这些，作为额外挑战。它们不计分。

练习 4

写过程 cxr-function，它接受一个以 c 开头、以 r 结尾、中间有一串 a 和/或 d 字母的词，如 cdddadaadar。它应返回相应的函数。

练习 5

SICP 练习 2.6。除加法外，再发明非负整数的乘法和乘方。如果你真有热情，试试能不能发明减法。（记住，游戏规则是你只有 λ 作为起点。）阅读 ~cs61as/lib/church-hint 获取一些建议。

练习 6

SICP 练习 2.18；这需要花点心思，你应确保做对，但别为它卡上一整个小时。注意：你的解法应翻转列表，而不是句子！也就是说，你应该用 cons、car、cdr，而不是 first、sentence 等。

提交作业！

提交说明见这份指南。它涵盖基本终端命令和作业提交。

提交遇到任何麻烦，尽管问 TA！