# README（讲师版）

> **CS:APP Data Lab**
>
> 给讲师的指导
>
> May 31, 2011：现在包含了“击败教授”比赛
>
> Copyright (c) 2002-2018, R. Bryant and D. O'Hallaron
>
> 汉化：Hansimov

此目录包含运行 CS:APP Data Lab 所需的文件，它有助于培养学生对位表示、补码运算和 IEEE 浮点的理解。

为了好玩，我们还提供了一个新的基于 HTTP 的用户级“击败教授”竞赛，取代了旧的基于电子邮件的版本。新的比赛是完全独立的，不需要 root 密码。唯一的要求是在 Linux 机器上有一个具有 IP 地址的用户帐户。

系统需求：使用 bison 和 flex 构建 dlc。

## 1. 概述

在该实验中，学生处理一个名为 bits.c 的 C 文件，它由一系列编程“谜题” 组成。每个谜题都是一个需要完善的函数体，从而实现一个特定的数学函数，比如“绝对值”。在解决非浮点谜题时，学生仅能使用直线 C 代码和一组受限的 C 语言算术和逻辑运算符。对于浮点谜题，他们可以使用条件句和任意运算符。

学生使用以下三种工具检查作业。讲师使用相同的工具来评分。

1. **dlc：**&#x4E00;个“数据实验编译器”，用 bits.c 检查每个函数是否符合编码准则，检查学生是否使用少于最大数量的运算符，是否只使用直线代码，是否只使用合法运算符。其源代码和一个 Linux 二进制文件都包含在实验中。
2. **btest：**&#x4E00;个测试工具，用于检查 bits.c 中函数的正确性。这个工具已经得到了显著的改进，现在可以检查整数和浮点表示的大范围（wide swaths）边缘用例（edge cases），比如 0、最小有符号数（Tmin）、非规格化的数和规格化的数的边界（denorm-norm boundary） 和无限大（inf）。
3. **driver.pl：**&#x4E00;个自动评分驱动程序，它使用 dlc 和 btest 来检查 bits.c 中每个测试函数的正确性，以及是否符合编码准则。

实验的默认版本包括 15 个谜题，位于 **./src/selections.c** 中，从目录 **./src/puzzles/** 中定义的 73 个标准谜题中选择。你可以从标准的谜题中选择一组不同的拼图来定制每个学期的实验。

你也可以自己定义新的谜题，并将它们添加到标准集合中。请参阅 **./src/README** 以获取如何向标准集合添加新谜题的说明。

注：如果你定义了新的谜题，请发送给我（Dave O'Hallaron， droh@cs.cmu.edu）这样我就可以将它们添加到 data lab 发行版的标准谜题集中。

## 2. 文件

所有的 CS:APP 实验都有着相同的简单的顶层目录结构：

| 文件名              | 说明                                                 |
| ---------------- | -------------------------------------------------- |
| Makefile         | 构建整个实验。                                            |
| README           | 本文件。                                               |
| src/             | 包含实验的所有源代码。                                        |
| datalab-handout/ | 发给学生的材料目录。由 Makefile 从 ./src 中的文件生成。不要修改此目录中的任何内容。 |
| grade/           | 自动评分脚本，讲师可以用它来给学生提交的文件打分。                          |
| writeup/         | LaTeX 实验报告样例。                                      |
| contest/         | 可选的“击败教授”比赛所需的所有文件。                                |

## 3. 构建实验

**第 0 步。**&#x5982;果你打算开启“击败教授”比赛（第 5 节），那么编辑 ./contest/Contest.pm 文件，以便驱动程序知道将结果发送到何处。参考 ./contest/README 获取简单的说明。如果您决定**不**提供比赛，那么在这一步中什么都不做。

**第 1 步。**&#x7F16;辑文件 **./src/selections.c** 选择要包含的谜题。默认的 **./src/selections.c** 来自 CMU 的 Data Lab 此前的一个实例。文件 **./src/selections-all.c** 包含可供选择的谜题的完整列表。

**第 2 步。**&#x4FEE;改 **./writeup** 中 的 LaTeX 实验报告，定制成你的课程所需。

**第 3 步。**&#x5728;当前目录中键入以下内容：

```bash
unix> make clean
unix> make
```

Makefile 生成 btest 源文件，构建 dlc 二进制文件（如果需要），格式化实验报告，然后将 btest、dlc 二进制文件和驱动程序复制到讲义目录。之后，它将构建讲义目录的 tar 文件（位于 **./datalab-handout.tar**），然后你可以将其发给学生。

关于二进制可移植性的注意事项：dlc 作为二进制文件放在 **datalab-handout** 目录中。由于动态库的不同版本，Linux 二进制文件并非总能跨发行版移植。需要注意的是，应在与学生所用机器兼容的一台机器上编译 dlc。

注意：运行 “make” 也会自动生成谜题的解答，可以在 **./src/bits.c** 和 **./src/bits.c-solution** 中找到。

## 4. 给实验评分

有个方便的自动评分脚本可以自动为学生提交的作业评分。说明可参见 **./grade/README**。

## 5. “击败教授”比赛

为了好玩，我们还提供了一个可选的“打败教授”比赛，学生和讲师竞争。目标是用最少的运算符来解决每个数据实验室难题。在每一个谜题中，能匹配或击败讲师的操作符数目的学生是赢家。有关如何设置竞赛的简单说明，参见 **./contest/README** 。

注：比赛是完全可选的。你提供与否对你如何建立和分发该实验没有影响。

注：如果你决定提供比赛，那么你应该在构建实验**之前**配置比赛，以便驱动程序知道发送每个学生比赛结果的服务器和端口（使用 **./src/Driverhdrs.pm** 文件中定义的常量，它们从 **./contest/Contest.pm** 配置文件自动生成）。

如果你**已经**构建完实验并将其分发给学生了，你还是可以提供比赛：

1）参照 **contest/Makefile** 中所述配置比赛。

2）照常重新构建实验：

```bash
linux> cd datalab
linux> make
```

3）将新的 **./src/Driverhdrs.pm** 文件分发给学生。

## 6. 实验性的 BDD 检查器

为了好玩，我们包含了一个基于二进制决策图（binary decision diagram，BDD）的实验性的正确性检查器（R. E. Bryant，IEEE Transactions on Computers，August, 1986），它使用了科罗拉多大学的 CUDD BDD 包。BDD 检查器对 bits.c 中的测试函数进行穷举测试，对照参考解答，形式化验证每个测试函数对&#x4E8E;_&#x6240;&#x6709;_&#x53EF;能的输入值的正确性。对于和参考解答不同的函数，BDD 检查器生成一个反例，该反例以一组函数参数的形式出现，这些参数会让测试解答与参考解答不同。

源代码包含在 **./src/bddcheck** 中。编译方法：

```bash
unix> cd src/bddcheck
unix> make clean
unix> make
```

使用 BDD 检查 **./src/bits.c** 的正确性：

```bash
unix> cd src
unix> ./bddcheck/check.pl    # 包含错误信息和反例
unix> ./bddcheck/check.pl -g # 紧凑的表格输出，不含错误消息
```

注意，**check.pl** 必须在 **./bddcheck** 的父目录运行。

我们在 CMU 使用这个 BDD 检查器而非 btest 已经有好几年了，代码看起来是稳定的。主要缺点在于从 **bits.c** 中提取函数的 Perl 代码，它通常能工作，但是有些事情——比如对其他函数的调用，或者不以一个大括号结尾的函数——会使它混乱。所以我们不愿意让它成为分发的 CS:APP 实验的默认检查器。但是，如果您对某个特定解答的正确性有任何疑问，那么这是一个权威的决定方法。

任何有关 BDD 检查器的意见，请发送给 **randy.bryant@cs.cmu.edu**。





