软件设计实践大作业

Lv.1 数据类型

在开始写代码之前，首先要梳理整个项目的框架。我们要实现的是一个 Mini-Lisp 的 REPL 程序——什么叫 REPL 呢？就是 Read-Eval-Print-Loop，中国话叫做“读取-求值-打印”循环。具体到这个项目而言，就是：

  1. 读取一行文本；
  2. 对这行文本“求值”；
  3. 打印求值的结果；
  4. 转到 1。

很明显，重点在于“求值”。什么是求值？粗糙地看就是将一个字符串，转换到一个 Mini-Lisp 的“值”。显然，“值”就是数据。Mini-Lisp 有七种数据类型：

  • 数类型；
  • 布尔类型；
  • 字符串类型；
  • 符号类型；
  • 空表类型；
  • 对子类型；
  • 过程类型。

你在这一节需要对数据类型这个事情有一点印象，因为我们稍后需要编写相关的代码。如果把“求值”细分成若干步骤的话，就可以分成：

  • 词法分析器：将 字符串 转换到 词法标记 序列；
  • 语法分析器：将这些 词法标记 组成一个有意义的 表达式；
  • 求值过程：对表达式进行求值，得到一个单独的数据。

具体到例子而言，

  • 词法分析器：将 "(+ 1 2)" 转换到 ( + 1 2 ) 这么五个词法标记；
  • 语法分析器：将上述五个词法标记重新组合为符号 +、数值 1 和数值 2 构成的列表；
  • 求值过程：对刚刚得到的列表 '(+ 1 2) 进行求值，从而得到数类型的值 3。

词法分析器我们已经提供好了，所以理论上如果一步步实现的话，下一步应该实现“语法分析器”。但这是 Lv.2 才要做的——因为不管是语法分析器还是求值过程，都涉及到了不同的数据类型。刚刚 (+ 1 2) 的例子中，这五个语法标记会组合为一个对子类型的值 (+ 1 2)，又稍后将这个对子类型的值，转换为数类型的值 3。

如果我们尝试编写一个实现语法分析器的函数，它的签名（声明）应该类似于：

std::shared_ptr<Value> parse(std::deque<TokenPtr> tokens);

语法分析器接受词法标记序列，也就是 std::deque<TokenPtr>，这很理所当然，没什么好说的。但是它返回的类型却值得思考。我这里用了 std::shared_ptr<Value>，其中 Value 是一个代表值的抽象类。

如果你对 Token 及其子类的工作原理已经有了认识的话，应该不难想到，这里仍然是用指针来实现多态。Value 作为抽象的基类，它可以被任何数据类型的值所实现，比如 BooleanValue StringValue NumericValue 等等。但具体到用什么指针，是裸指针 Value*，还是 std::unique_ptr 还是 std::shared_ptr，就需要一些思考了。这里我暂且不解释使用 std::shared_ptr 的原因，当你写到后面的时候或许就能理解这个选择。目前，就暂且相信我一次，用 std::shared_ptr<Value>。

任务 1.1 定义数据类型

那么，你要编写的第一块代码，就是 Value 抽象类和它的子类。这一部分你不用考虑过程类型，所以你要实现如下子类：

  • BooleanValue 存放一个布尔类型的值；
  • NumericValue 存放一个数类型的值。显然，无脑用 double 来存放就行；
  • StringValue 存放一个字符串类型的值；
  • NilValue 存放一个空表。显然，它不需要任何数据成员；
  • SymbolValue 存放一个符号类型的值。它需要存放这个符号的名字，或者说“变量名”；
  • PairValue 存放一个对子类型的值。它需要有两个数据成员，左半部分的值和右半部分的值——以 std::shared_ptr 的形式。

新建一个头文件 value.h，以及配套的源文件 value.cpp。在 value.h 中声明以上类，并给出相应的构造函数。回顾一下抽象类的写法，这并不困难。我们可以假设 Mini-Lisp 中所有的值都是只读的，所以你可以放心地将所有成员声明为私有的，甚至是只读的。value.cpp 用来存放构造函数的定义；你如果习惯把构造函数内联声明在类定义里，也可以暂且留空。

当你编写头文件时，需要添加“包含保护”。也就是这样的代码：

#ifndef VALUE_H
#define VALUE_H

// 你的代码

#endif

这个手段可以有效地防止你的头文件被多次 #include。你也可以用 #pragma once，但这是不标准的。

编写完成后，在 main.cpp 中包含这个头文件，检查编译是否通过。

任务 1.2 编写外部表示

Mini-Lisp 中，每一种数据类型都有其外部表示。外部表示这个词太抽象了，其实就是转换到字符串的结果。比如说数值 42 转换到字符串的结果就是 "42"，而由符号 a 和符号 b 构成的对子，转换到字符串就写作 (a . b)。

接下来的编码任务是这样的：为每一种数据类型的值，提供 toString 成员函数以提供其外部表示法。你需要用到虚函数，来实现基类型 Value 到各个最终覆盖实现的动态派发。我建议将这些函数的定义放在源文件 value.cpp 中。

对于大部分的数据类型，提供 toString 实在是太平凡了。

  • 数值的外部表示就是 std::to_string 后的结果——但如果是整数的话，就不要显示小数点的好。
  • 布尔值的外部表示就是 #t #f。
  • 符号的外部表示就是符号所指代的变量名（这是最简单的情形）。
  • 字符串的外部表示就是用双引号括一下。std::quoted 可能会派上用场。
  • 空表的外部表示就是 ()。

但是对子类型稍微复杂一些——对子类型的外部表示类似于“列表表示”，比如对子 (a . (b . (c . d))) 的外部表示应当写作 (a b c . d)。而对子 (a . (b . (c . (d . ())))) 的外部表示则是 (a b c d)。动脑的时间到了，通过一些“递归”，可以比较轻松地实现这种外部表示。

列表表示简单来说就是尽可能将对子写成列表的形式 (a b c ... )。如果一个对子的右半部分不是对子或空表（也就是不再是列表）的时候，用一个 . 分隔，然后将右半部分写出。这也就是 (a b c . d) 中 . d 的含义。

TIP

列表是一种特殊的数据类型，它是对子类型和空表类型的组合，一个列表具有如下结构：

  • 空表；或
  • 对子，其中左半部分是任意数据，右半部分是列表

而不是列表的对子被称为带点列表，例如上述分析中，(a . (b . (c . (d . ())))) 是一个列表，而 (a . (b . (c . d))) 是一个带点列表，也就不是列表。厘清这一概念将有利于你完成后续任务。

你可能还需要判断一个 Value 的具体类型是什么。这个时候，最方便的办法就是用 RTTI 机制——运行时类型信息。你可以用 typeid 运算符或者 dynamic_cast：

ValuePtr myValue = /* ... */;
// 首先用 typeid 判断动态类型，随后用 static_cast 转换到该类型
if (typeid(*myValue) == typeid(PairValue)) {
  auto& pair = static_cast<const PairValue&>(*myValue);
  // pair 是绑定到 const PairValue 的引用
}

ValuePtr myValue = /* ... */;
// 尝试用 dynamic_cast 转换到该类型。转换出错时，条件不成立
if (auto pair = dynamic_cast<const PairValue*>(myValue.get())) {
  // pair 是指向 const PairValue 的裸指针
}

此外，如果为 Value 重载 operator<< 的话，可以写得更舒服一点。

测试

我们尽量在每一部分结尾都提供一些测试的方法，来检测你是否正确完成了本部分的程序。不过这一关没有什么成型的代码，所以就在 main 函数中试试下面的代码吧（原本的代码可以留着，之后还会用）：

#include <iostream>
#include "./value.h"

using ValuePtr = std::shared_ptr<Value>; // 把这个添加到 value.h，可以减少许多重复的代码。
int main() {
    ValuePtr a = std::make_shared<NumericValue>(42);
    ValuePtr b = std::make_shared<BooleanValue>(false);
    ValuePtr c = std::make_shared<SymbolValue>("eq?");
    ValuePtr d = std::make_shared<StringValue>("Hello\"");
    ValuePtr e = std::make_shared<NilValue>();
    ValuePtr f = std::make_shared<PairValue>(
        c,
        std::make_shared<PairValue>(
            a,
            std::make_shared<PairValue>(d, e)
        )
    );
    std::cout << a->toString() << '\n'
              << b->toString() << '\n'
              << c->toString() << '\n'
              << d->toString() << '\n'
              << e->toString() << '\n'
              << f->toString() << std::endl;
}

如果某些类的构造函数和你想得不太一样，你也可以略微修改上面的代码。总之，期望的输出是：

42
#f
eq?
"Hello\""
()
(eq? 42 "Hello\"")

阶段性检查

在教学网 大作业 / Lv.1 检查 处，提交上述测试的运行截图（截到部分代码和运行窗口即可）。在 2024 年 5 月 5 日 23:59:59 前提交的，可能获得分数加成。

Last Updated:
Contributors: Guyutongxue