读书笔记：编程原本（其一、基础概念）

注：本文知识以及例子来源主要是人民邮电出版社出版的编程原本，作者是Alexander Stepanov，适量夹杂一些废话和本人的书写习惯

这本书是将写程序中的一些思想抽象出来，用数学语言阐述，再利用C++强大的抽象能力进行实现。因此，书里面使用了不少数学语言。我们在一开始先列举一些数学符号或记法的含义，以便后续遇到疑问时查询。

符号	含义	举例
$\land$	逻辑与，即多个判断条件成立时，表达式方成立	$\varepsilon_0 \land \varepsilon_1 \land \varepsilon_2$
$\lor$	逻辑或，即某个判断条件成立时，表达式即成立	$\varepsilon_0 \lor \varepsilon_1 \lor \varepsilon_2$
$\lnot$	逻辑非，即该判断条件不成立时，表达式成立	$\lnot \varepsilon_0$
$\Rightarrow$	蕴涵，即前表达式成立时，后表达式自然成立	$(\forall x, y \in \mathbb{R}) xy = 0 \Rightarrow x = 0 \lor y = 0$
$\in$	属于符号，指元素所在集合	$i \in \mathbb{Z^+}$
$\forall$	全称量词，指某个集合内任何元素，使得后续判断条件成立	$\forall x \in \mathbb{R}, x^2 \ge 0$
$\exists$	存在量词，指某个集合中，存在至少一个元素，使得后续判断条件成立	$\exists x \in \mathbb{R}, x^2 = 0$
$\colon$	类型限定符，说明变量的类型	$prime : \mathbb{N}$
$\equiv$	恒等符号，指两个对象始终相等	$f(x) \equiv 0$
$\times$	笛卡尔积，生成分别来自于两个集合的元素的有序对集合	$\mathbb{R}^2 \equiv \mathbb{R} \times \mathbb{R}$
$\rightarrow$	函数符号，箭头从函数定义域指向函数值域	$f : \mathbb{C} \rightarrow \mathbb{R}$
$:=$	定义符号，用一系列表达式说明某个变量的性质	$even := even \in \mathbb{Z}$ $\land \exists k \in \mathbb{Z}, even = 2k$
$\triangleq$	定义等号，用一系列表达式定义某个概念	$Even(n) \triangleq Integer(n)$ $\land \exists k \in \mathbb{Z}, n = 2k$
T(n)	类型，描述一个变量所在集合的函数，返回一个真值。这里的P和n只是例子，我们会用斜体字来表示类型	Type(T : Variable) $\triangleq$ Func(T) $\land$ Codomain(T) $= bool$
P(n)	属性，描述一个集合性质的函数，返回一个真值。这里的P和n只是例子，我们会用粗体字来表示属性	Prop(P : Collection) $\triangleq$ Func(P) $\land$ Codomain(P) $= bool$

上面部分符号的使用范围存在重合，且不一定是数学中常用或通用的记法，具体使用时以表达清晰为准。类型和属性本质都是返回真值的函数（即谓词），其差别在于定义时前者的参数是符合该类型的任何变量，后者的参数是拥有改属性的一个集合。在这里干讲感觉也不清晰，还是回到书中去看实在的例子吧。

基础概念

除了上述的符号之外，我们还需要知道一些概念来方便之后深入这本书。鉴于原书中有些概念过于抽象且后续没有多少引用，我在这里只选取了一些概念：

值：在计算机中，所有数据（data）都是由0和1的序列组成的，它们对应着现实中存在意义的内容（比如数字，文本，图片等等）；我们将计算机中某个存储的二进制序列称为一个表示（Representation），如0100，而将其在现实中对应的内容称为一个解释（Interperetation），如上文的0100可以对应整数4。我们将这样的一项数据和它的解释称为一个值（value）。值类型（value type）则是指从一个表示集合到一个解释集合的对应关系。举例来讲，C++中的 int 是一种值类型，它从32位二进制序列映射到整数。下面列举一些值类型的属性：
- 真部分的（properly partial）：指该类型的值只能表示其所在集合中的一个真子集，反之则称其是全的（total）。比如C++中 int 是真部分的，但 bool 就是全的。
- 唯一表示的（uniquely represented）：指值类型的映射关系是单射。比如bool 类型的一些实现中，将所有非0的数都视为TRUE，此时对于TRUE就有多个表示方式，即不是唯一表示的。
- 有歧义的（ambiguous）：指某个表示存在多个解释的值，反之则称其是无歧义的（unambiguous）。比如用两个十进制数表示某一年的类型是有歧义的。千年虫问题的来源就和这个也有关。

如果一项数据在某种值类型的映射下能对应一个解释，则称其对于该值类型是良形式的（well-formed）。反例比如，IEEE 754浮点标准中，NaN在机器中的序列不存在实数中的任何解释，故NaN在 float 类型中非良形式。

此外，两个值相等（equality）指的是两个值的解释完全相等；表示相等（representational equality）指的是数据的二进制序列完全相等。比如，4位补码中的1100映射到整数-4，但无符号码中表示相等的1100映射到整数12，它们的值不相等。

引理：一个值类型有唯一表示时，相等蕴涵表示相等。
引理：一个值类型无歧义时，表示相等蕴涵相等。

对象：一个对象（object）是一个相对具体事物的表示。其状态（state）是某个值类型的一个值，状态可以不断改变。某一时间点对象的状态表示成值称为一个快照（snapshot）。对象拥有一系列资源（resource）用于保存其状态，这些资源可以是连续存储的，也可以位于不同的存储空间中。对象类型（object type）是指一种在存储空间中保存和修改值的模式。对于每个对象类型存在对应的值类型来描述对象的状态。以相对简单的方式理解值和对象的区别，即值是不变的常量，而对象是存储一个或多个值的容器，其中的值可以随情况变为其它的值。举个例子，int 是值类型，也可以当作对象类型：10可以是int类型的值，而x可以是int类型的对象。之前讲到的值类型的特点也可以拓展到对象和对象类型上：
- 一个对象是良形式的当且仅当其状态是良形式的。
- 一个对象类型是真部分的当且仅当其值类型是真部分的。否则其是全的。
- 一个对象类型是唯一表示的当且仅当其值类型是唯一表示的。
过程：一个过程（procedure）是一个指令序列，它可能修改某些对象的状态，也可能构造或析构一些对象。这些和过程交互的对象可以分为以下几类：
1）输入/输出（input/output）：指通过参数或返回值直接或间接传递的对象。
2）局部状态（local state）：指在该过程的一次调用中被创建、修改并销毁的对象。
3）全局状态（global state）：指可以被多个过程多次调用中访问的对象。
4）所有状态（own state）：指仅由该过程或隶属过程访问但在多次过程调用中共享的状态。
熟悉C++的同学可以通过下面的例子简单理解这四种类型的对象：

int i = 0;                          // i是全局状态
int procedure(int& a, int b) {      // 这里的函数procedure就是一个过程，a，b是输入
    static int count = 0;           // count是所有状态，static表示该变量在多次调用中共享
    ++count;
    while (a + i < b) {
        std::cout << b;
        ++a;                        // a既是输入也是输出，因为a可能被修改
    }
    int tmp = a;                    // tmp是局部状态
    std::cout << tmp;
    return (count == 10) ? -1 : count;  // count在这里也是输出
}

这个例子本身缺少意义，但是列举了各种在过程中使用对象的例子。

规范类型和规范过程
规范类型需要定义和其关联的一系列过程用来操作该类型的对象。这些过程可以通过组合构建出该类型上的其它过程。这些特定的基本过程如下：

名称	记号	C++
默认构造操作	/	T a;
拷贝构造操作	/	T a = b;
析构操作	/	T.~T();
相等判断	$a = b$	a == b
	$a \neq b$	a != b
赋值	$a \leftarrow b$	a = b

值得注意的是，默认构造操作之后，对象的值是不能确定的，对于其的任何除赋值和析构操作之外的过程都是无定义的（这大概就是C++毒瘤的开始）。构造操作和析构操作并不拘泥于表格中的C++形式，它们可以在任何需要构建或析构对象时被调用。

规范过程则是指，过程的行为在相同输入的情况下保持一致性。这里的相同输入是指每个输入都能分别通过相等判断。举个例子，print(2)和print(1 + 1)的行为是一致的，因为2和1+1是相等的值。但是下面这种情况中，函数numerator就不是规范的：

#include <cassert>
struct Rational {
    int numerator;
    int denominator;

    Rational() : Rational(0, 1) { }
    Rational(int p, int q) : numerator(p), denominator(q) { 
        assert(q != 0);
    }
    bool operator=(Rational const& other) {
        if (numerator == 0 && other.numerator == 0) {
            return true;
        }
        else {
            return numerator * other.denominator == denominator * other.numerator;
        }
    }
};

int numerator(Rational const& r) {
    return r.numerator;
}

上例中，Rational类型是规范的，但是numerator并不是，对于Rational(1/2)和Rational(2/4)这两个相等的对象，它会给出不同的结果。

以上是对原书第一章的整理和总结，其实有不少内容并没有展示出来，我会考虑在后续篇目中有需要的时候再作总结，或者加到当前篇目。