第 6 课作业

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

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

你也可以在这里下载模板。

自动评分器

要在你自己的计算机上运行自动评分器，请下载测试文件这里，然后按照之前几课的说明操作。

练习 0

从文件 ~cs61as/lib/racket1.rkt 中加载 racket-1 解释器。

要启动解释器，请输入 (racket-1)。通过求值一些表达式来熟悉它。记住：你有全部用于算术和列表操作的 Racket 原语；你有 lambda 但没有高阶函数；你没有 define。要停止 racket-1 解释器并返回 Racket，只需求值一个非法表达式，比如 ()。

0a. 详细追踪 racket-1 如何处理下面这样的简单过程调用：

((lambda (x) (+ x 3)) 5)

0b. 试着发明高阶过程；由于你没有 define，只能用 Y 组合子技巧，像这样：

Racket-1:
((lambda (f n)  ; 这个 lambda 在定义 MAP
    ((lambda (map) (map map f n))
    (lambda (map f n)
        (if (null? n)
            '()
            (cons (f (car n)) (map map f (cdr n))) )) )) ; 定义 MAP 的 lambda 到此结束
first              ; MAP 的实参 f
'(the rain in spain)) ; MAP 的实参 n

(t r i s)

0c. 由于所有 Racket 原语在 racket-1 中自动可用，你可能以为可以用 Racket 的原生 map 函数。试试这两个例子：

Racket-1:
(map first '(the rain in spain))
Racket-1:
(map (lambda (x) (first x)) '(the rain in spain))

解释结果。

0d. 修改解释器，添加 and 特殊形式。测试你的成果。确保一旦计算出假值，你的 and 就返回 #f，不再求值任何后续实参。

练习 1

完成下面这些习题：

Abelson & Sussman，习题 2.74、2.75、2.76、2.77、2.79、2.80、2.81、2.83

练习 2

为 racket-1 写一个 map 原语（叫它 map-1，免得你和 Racket 搞混哪个是哪个），要求对一切被映射的过程都能正确工作。

练习 3

修改 racket-1 解释器，添加 let 特殊形式。

练习 4

SICP 习题 2.62

这会很有帮助：SICP 2.3.3

练习 5

文件 ~cs61as/lib/bst.scm 包含 SICP 2.3.3 中的二叉搜索树过程。用 adonset 构造出第 156 页所示的那些树。

选做：练习 6

处理类型问题的另一种方法是类型推断。例如，如果一个过程包含表达式 (+ n k)，我们就可以推断 n 和 k 具有数值。类似地，表达式 (f a b) 表明 f 的值是一个过程。请写一个名为 inferred-types 的过程，给定一个 Scheme 过程的定义作为实参，返回关于该过程各参数的信息列表。信息列表应为每个参数包含一个元素；每个元素应是一个两元素列表，第一个元素是参数名，第二个元素是表示推断出的参数类型的词。可能的类型如下：

类型	推断规则
?	类型无法推断
procedure	参数出现在一个未加引号的表达式的第一个词，或作为 map 或 every 的第一个实参
number	参数作为 +、-、max 或 min 的实参出现
list	参数作为 append 的实参出现，或作为 map 或 member 的第二个实参出现
sentence-or-word	参数作为 first、butfirst、sentence 或 member? 的实参出现，或作为 every 的第二个实参出现
x	推断出了冲突的类型

做这道题时，你可以假设被考察过程的体中不包含 if 或 cond，尽管它可能包含任意嵌套的以及加了引号的表达式。（一个更有雄心的推断过程，会考察更全面的过程集合，还能推断出”非空列表”这类条件。）下面是你的推断过程应该返回什么的例子。

(inferred-types
    '(define (foo a b c d e f)
        (f (append (a b) c '(b c))
           (+ 5 d)
           (sentence (first e) f)) ) )

它应该返回：

((a procedure) (b ?) (c list) (d number)
 (e sentence-or-word) (f x))

如果你真的很有雄心，还可以维护一个推断参数类型的数据库，在正在考察的过程调用了另一个你见过的过程时用上它！

提交作业！

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

提交时如有任何困难，尽管问助教！