讀書筆記：編程原本（其一、基礎(chǔ)概念）

注：本文知識以及例子來源主要是人民郵電出版社出版的編程原本，作者是Alexander Stepanov赵讯，適量夾雜一些廢話和本人的書寫習(xí)慣

這本書是將寫程序中的一些思想抽象出來盈咳，用數(shù)學(xué)語言闡述，再利用C++強(qiáng)大的抽象能力進(jìn)行實(shí)現(xiàn)边翼。因此鱼响，書里面使用了不少數(shù)學(xué)語言。我們在一開始先列舉一些數(shù)學(xué)符號或記法的含義讯私，以便后續(xù)遇到疑問時(shí)查詢热押。

符號	含義	舉例
$\land$	邏輯與，即多個(gè)判斷條件成立時(shí)斤寇，表達(dá)式方成立	$\varepsilon_0 \land \varepsilon_1 \land \varepsilon_2$
$\lor$	邏輯或桶癣，即某個(gè)判斷條件成立時(shí)，表達(dá)式即成立	$\varepsilon_0 \lor \varepsilon_1 \lor \varepsilon_2$
$\lnot$	邏輯非娘锁，即該判斷條件不成立時(shí)牙寞，表達(dá)式成立	$\lnot \varepsilon_0$
$\Rightarrow$	蘊(yùn)涵，即前表達(dá)式成立時(shí)莫秆，后表達(dá)式自然成立	$(\forall x, y \in \mathbb{R}) xy = 0 \Rightarrow x = 0 \lor y = 0$
$\in$	屬于符號间雀，指元素所在集合	$i \in \mathbb{Z^+}$
$\forall$	全稱量詞，指某個(gè)集合內(nèi)任何元素镊屎，使得后續(xù)判斷條件成立	$\forall x \in \mathbb{R}, x^2 \ge 0$
$\exists$	存在量詞惹挟，指某個(gè)集合中，存在至少一個(gè)元素缝驳，使得后續(xù)判斷條件成立	$\exists x \in \mathbb{R}, x^2 = 0$
$\colon$	類型限定符连锯，說明變量的類型	$prime : \mathbb{N}$
$\equiv$	恒等符號，指兩個(gè)對象始終相等	$f(x) \equiv 0$
$\times$	笛卡爾積用狱，生成分別來自于兩個(gè)集合的元素的有序?qū)?/td>	$\mathbb{R}^2 \equiv \mathbb{R} \times \mathbb{R}$
$\rightarrow$	函數(shù)符號运怖，箭頭從函數(shù)定義域指向函數(shù)值域	$f : \mathbb{C} \rightarrow \mathbb{R}$
$:=$	定義符號，用一系列表達(dá)式說明某個(gè)變量的性質(zhì)	$even := even \in \mathbb{Z}$ $\land \exists k \in \mathbb{Z}, even = 2k$
$\triangleq$	定義等號夏伊，用一系列表達(dá)式定義某個(gè)概念	$Even(n) \triangleq Integer(n)$ $\land \exists k \in \mathbb{Z}, n = 2k$
T(n)	類型摇展，描述一個(gè)變量所在集合的函數(shù)，返回一個(gè)真值溺忧。這里的P和n只是例子咏连，我們會(huì)用斜體字來表示類型	Type(T : Variable) $\triangleq$ Func(T) $\land$ Codomain(T) $= bool$
P(n)	屬性盯孙，描述一個(gè)集合性質(zhì)的函數(shù)，返回一個(gè)真值祟滴。這里的P和n只是例子镀梭，我們會(huì)用粗體字來表示屬性	Prop(P : Collection) $\triangleq$ Func(P) $\land$ Codomain(P) $= bool$

上面部分符號的使用范圍存在重合，且不一定是數(shù)學(xué)中常用或通用的記法踱启，具體使用時(shí)以表達(dá)清晰為準(zhǔn)。類型和屬性本質(zhì)都是返回真值的函數(shù)（即謂詞）研底，其差別在于定義時(shí)前者的參數(shù)是符合該類型的任何變量埠偿，后者的參數(shù)是擁有改屬性的一個(gè)集合。在這里干講感覺也不清晰榜晦，還是回到書中去看實(shí)在的例子吧冠蒋。

基礎(chǔ)概念

除了上述的符號之外，我們還需要知道一些概念來方便之后深入這本書乾胶。鑒于原書中有些概念過于抽象且后續(xù)沒有多少引用抖剿，我在這里只選取了一些概念：

值：在計(jì)算機(jī)中，所有數(shù)據(jù)（data）都是由0和1的序列組成的识窿，它們對應(yīng)著現(xiàn)實(shí)中存在意義的內(nèi)容（比如數(shù)字斩郎，文本，圖片等等）喻频；我們將計(jì)算機(jī)中某個(gè)存儲(chǔ)的二進(jìn)制序列稱為一個(gè)表示（Representation）缩宜，如0100，而將其在現(xiàn)實(shí)中對應(yīng)的內(nèi)容稱為一個(gè)解釋（Interperetation）甥温，如上文的0100可以對應(yīng)整數(shù)4锻煌。我們將這樣的一項(xiàng)數(shù)據(jù)和它的解釋稱為一個(gè)值（value）。值類型（value type）則是指從一個(gè)表示集合到一個(gè)解釋集合的對應(yīng)關(guān)系姻蚓。舉例來講宋梧，C++中的 int 是一種值類型，它從32位二進(jìn)制序列映射到整數(shù)狰挡。下面列舉一些值類型的屬性：
- 真部分的（properly partial）：指該類型的值只能表示其所在集合中的一個(gè)真子集捂龄，反之則稱其是全的（total）。比如C++中 int 是真部分的圆兵，但 bool 就是全的跺讯。
- 唯一表示的（uniquely represented）：指值類型的映射關(guān)系是單射。比如bool 類型的一些實(shí)現(xiàn)中殉农，將所有非0的數(shù)都視為TRUE刀脏，此時(shí)對于TRUE就有多個(gè)表示方式，即不是唯一表示的超凳。
- 有歧義的（ambiguous）：指某個(gè)表示存在多個(gè)解釋的值愈污，反之則稱其是無歧義的（unambiguous）耀态。比如用兩個(gè)十進(jìn)制數(shù)表示某一年的類型是有歧義的。千年蟲問題的來源就和這個(gè)也有關(guān)暂雹。

如果一項(xiàng)數(shù)據(jù)在某種值類型的映射下能對應(yīng)一個(gè)解釋首装，則稱其對于該值類型是良形式的（well-formed）。反例比如杭跪，IEEE 754浮點(diǎn)標(biāo)準(zhǔn) 中仙逻，NaN在機(jī)器中的序列不存在實(shí)數(shù)中的任何解釋，故NaN在 float 類型中非良形式涧尿。

此外系奉，兩個(gè)值相等（equality）指的是兩個(gè)值的解釋完全相等；表示相等（representational equality）指的是數(shù)據(jù)的二進(jìn)制序列完全相等姑廉。比如缺亮，4位補(bǔ)碼中的1100映射到整數(shù)-4，但無符號碼中表示相等的1100映射到整數(shù)12桥言，它們的值不相等萌踱。

引理：一個(gè)值類型有唯一表示時(shí)，相等蘊(yùn)涵表示相等号阿。
引理：一個(gè)值類型無歧義時(shí)并鸵，表示相等蘊(yùn)涵相等。

對象：一個(gè)對象（object）是一個(gè)相對具體事物的表示倦西。其狀態(tài)（state）是某個(gè)值類型的一個(gè)值能真，狀態(tài)可以不斷改變。某一時(shí)間點(diǎn)對象的狀態(tài)表示成值稱為一個(gè)快照（snapshot）扰柠。對象擁有一系列資源（resource）用于保存其狀態(tài)粉铐，這些資源可以是連續(xù)存儲(chǔ)的，也可以位于不同的存儲(chǔ)空間中卤档。對象類型（object type）是指一種在存儲(chǔ)空間中保存和修改值的模式蝙泼。對于每個(gè)對象類型存在對應(yīng)的值類型來描述對象的狀態(tài)。以相對簡單的方式理解值和對象的區(qū)別劝枣，即值是不變的常量汤踏，而對象是存儲(chǔ)一個(gè)或多個(gè)值的容器，其中的值可以隨情況變?yōu)槠渌闹堤蛱凇Ｅe個(gè)例子溪胶，int 是值類型，也可以當(dāng)作對象類型：10可以是int類型的值稳诚，而x可以是int類型的對象哗脖。之前講到的值類型的特點(diǎn)也可以拓展到對象和對象類型上：
- 一個(gè)對象是良形式的當(dāng)且僅當(dāng)其狀態(tài)是良形式的。
- 一個(gè)對象類型是真部分的當(dāng)且僅當(dāng)其值類型是真部分的。否則其是全的才避。
- 一個(gè)對象類型是唯一表示的當(dāng)且僅當(dāng)其值類型是唯一表示的橱夭。
過程：一個(gè)過程（procedure）是一個(gè)指令序列，它可能修改某些對象的狀態(tài)桑逝，也可能構(gòu)造或析構(gòu)一些對象棘劣。這些和過程交互的對象可以分為以下幾類：
1）輸入/輸出（input/output）：指通過參數(shù)或返回值直接或間接傳遞的對象。
2）局部狀態(tài)（local state）：指在該過程的一次調(diào)用中被創(chuàng)建楞遏、修改并銷毀的對象茬暇。
3）全局狀態(tài)（global state）：指可以被多個(gè)過程多次調(diào)用中訪問的對象。
4）所有狀態(tài)（own state）：指僅由該過程或隸屬過程訪問但在多次過程調(diào)用中共享的狀態(tài)寡喝。
熟悉C++的同學(xué)可以通過下面的例子簡單理解這四種類型的對象：

int i = 0;                          // i是全局狀態(tài)
int procedure(int& a, int b) {      // 這里的函數(shù)procedure就是一個(gè)過程而钞，a，b是輸入
    static int count = 0;           // count是所有狀態(tài)拘荡，static表示該變量在多次調(diào)用中共享
    ++count;
    while (a + i < b) {
        std::cout << b;
        ++a;                        // a既是輸入也是輸出，因?yàn)閍可能被修改
    }
    int tmp = a;                    // tmp是局部狀態(tài)
    std::cout << tmp;
    return (count == 10) ? -1 : count;  // count在這里也是輸出
}

這個(gè)例子本身缺少意義撬陵，但是列舉了各種在過程中使用對象的例子珊皿。

規(guī)范類型和規(guī)范過程
規(guī)范類型需要定義和其關(guān)聯(lián)的一系列過程用來操作該類型的對象。這些過程可以通過組合構(gòu)建出該類型上的其它過程巨税。這些特定的基本過程如下：

名稱	記號	C++
默認(rèn)構(gòu)造操作	/	T a;
拷貝構(gòu)造操作	/	T a = b;
析構(gòu)操作	/	T.~T();
相等判斷	$a = b$	a == b
	$a \neq b$	a != b
賦值	$a \leftarrow b$	a = b

值得注意的是蟋定，默認(rèn)構(gòu)造操作之后，對象的值是不能確定的草添，對于其的任何除賦值和析構(gòu)操作之外的過程都是無定義的（這大概就是C++毒瘤的開始）驶兜。構(gòu)造操作和析構(gòu)操作并不拘泥于表格中的C++形式，它們可以在任何需要構(gòu)建或析構(gòu)對象時(shí)被調(diào)用远寸。

規(guī)范過程則是指抄淑，過程的行為在相同輸入的情況下保持一致性。這里的相同輸入是指每個(gè)輸入都能分別通過相等判斷驰后。舉個(gè)例子肆资，print(2)和print(1 + 1)的行為是一致的，因?yàn)?和1+1是相等的值灶芝。但是下面這種情況中郑原，函數(shù)numerator就不是規(guī)范的：

#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類型是規(guī)范的夜涕，但是numerator并不是犯犁，對于Rational(1/2)和Rational(2/4)這兩個(gè)相等的對象，它會(huì)給出不同的結(jié)果女器。

以上是對原書第一章的整理和總結(jié)酸役，其實(shí)有不少內(nèi)容并沒有展示出來，我會(huì)考慮在后續(xù)篇目中有需要的時(shí)候再作總結(jié)，或者加到當(dāng)前篇目簇捍。

讀書筆記：編程原本（其一崔列、基礎(chǔ)概念）

讀書筆記：編程原本（其一梢褐、基礎(chǔ)概念）

基礎(chǔ)概念