计算机科学导论（草稿）

Feb 28, 2024

这一草稿最初是为已经学过一门编程语言的人准备的，打算之后替换为为完全零基础的人看的版本。在写完它之后，我觉得自己需要解释一下为什么要把一篇导论写得如此难读，「为什么不能直接教给我如何去写程序？」。

现在很多人，学什么东西就像去食堂打饭一样，讲求一个狼吞虎咽，给什么吃什么，我猜想他们吃的东西，一定挺香。尽管如此，我不打算把东西喂到别人嘴里，以我毕业以来对计算机技术的疏远，想必也不能胜任这样的工作。

相对的，这篇导论是一幅地图，但它不是把每个知识点都标记清楚的那种地图，而是汇集了各种小道消息的航海图：它所试图传达的并非是某种确定的、成体系知识，而是某种切身的体验——它不吝啬于包含一些判断、一些猜想、一些假说、一些模糊的和尚未探索到的边界——它们是我曾经着迷于这门学科的证明。希望你能看到，在这副地图上看来，这一门学科中的某些东西看起来是有些迷人的，甚至是能激励读者自行去探索的。

计算机语言简介

就像人类语言一样，计算机的语言是可塑性相当强的，C、C++、Python、Lisp……但是它们的描述能力却往往大同小异，就像一门语言往往能翻译成另一门语言一样。而比起人类语言，对于计算机语言的描述能力我们可以很容易给出一个严格的范围，这个范围就是「图灵完备性」的范围。

要理解这一点首先要问，作为语言，计算机语言描述的是什么？计算机语言所描述的是一个处理数据的过程。因此计算机语言的描述能力就是它的计算能力（这里的计算能力是指是否能进行某种计算，或可计算性，而不指计算的速度）。

作为这类语言及其所依附的系统的外部的人，我们可以这样简单地设想这个可计算性——我们看到程序的运行前后，这个语言所运行的系统的状态发生了改变，因此可以将这一整个过程区分为：起始状态、计算过程、终止状态。我们对于给定的语言，从所有可能的起始状态到所有可能的终止状态之间的映射，其可能的模式是有限的（不是数量上的有限），这一点约束了其可计算性的范围。

计算机能够做什么、不能做什么，教学中常常不被当作一个重要的预设向学生交代好，而是直接探讨计算效率的问题。于是常常会产生这样的疑问：「为什么我不能这样写？」「因为这样做会导致死循环。」可是，死循环毋宁只是一个结果。

如何理解计算：序列或表达式

我们接下来讨论计算的过程，计算活动（程序）及它的描述（代码）。我们可以通过两种方式来理解代码：序列和表达式。对应着计算活动就是序列的执行和表达式的求值。

一段程序的运行往往是可以用一长串序列来理解，就像一条长长的纸带那样。但是，程序的执行不一定是一条直线，就像我们阅读一样，有些标记会提示我们去回顾之前的片段，从而让我们的阅读在文中跳来跳去。在计算机中这种跳转和反复之所以可能，是因为在系统管理着其中每一个可以跳转到的位置，像书籍那样存在一张索引表中。常见的循环和控制流（while、if等），都是通过查表并跳转来完成的。在古埃及的石板上、中国古代的书卷里和在几何原本里我们所看到的种种算法，大多就是以序列的形式来表示的。它们的特点是，在算法之外有一个明确的状态（石子、小木棍的排列等），每一步都令这个状态发生变化。在程序设计里，这类状态的变化通常被冠以「变量的值的变化」这样的名称，而令状态的操作序列的单元则被称为是「语句」。

以辗转相除法为例：

1. 开始, 设a和b为给定的值;
2. 设d为a除b的商, r为a除b的余数;
3. 若d等于0, 跳转到标号5;
4. 设a为b, 设b为r;
5. 结束, a就是要求的值.

C语言的编程范式就是这种形式的，在随后的发展中，根据Dijkstra的建议取消了标号而代之以各种语句块（一般是由{}所包裹的部分），形成了现在我们最常看到的语言编写方式，这一风格被称为是结构化编程：

开始, 设a和b为给定的值;
设d为a除b的商, r为a除b的余数;
直到 { d等于0 } 则 { 结束 } 否则 { 设a为b, 设b为r, 继续 }
a就是要求的值.

但是，我们满也可以不这样去理解程序的运行，而是把整个程序的运行看成是一个整体，看成是一个表达式。这样，计算的过程就不是按照语句的顺序一条条的过掉，而是将给定的值直接代入表达式中以进行求值。同样以读一本书为例子，这就像是你已经熟悉了一本书而要提炼出这本书的精髓，你会首先从概念的整体出发，而不是像写摘要那样复述这本书的论证过程。因为表达式是一次性地被交付给系统的，所以其中的各种操作没有执行顺序的优先性，而只有逻辑上的优先性。比起算法序列，这样的运算方式不需要额外维护一个状态，更符合代数的思维。

在这种表示法中，我们首先不谈论算法执行的步骤而谈论求值的步骤，每一步都是对表达式的某一个具有优先级的局部（同样是表达式）求一次值，并用这个值代换掉这个局部，从而得到了一个更为短的表达式，就像代数中不断计算括号内的部分来得到结果那样。以这样的方式，编程可以就变得像按计算器一样简单，只需要确定符号的定义而不需要关心变量的变化。唯一的问题是：计算机只能处理处理某种特殊形式的表达式，即递归式（一个可以引用自己的表达式），我们需要找到它的形式。

依然以辗转相除法为例：

$$ GCD(a,b) = \begin{cases} a &, b = 0 \\ GCD(b,a \ \mathbf{rem} \ b) &, b \neq 0 \end{cases} $$

可以看到，这种形式给出了辗转相除法的精髓：它以较小的规模上关联于自身，从而令问题变为一个更小的问题，最终收敛到一个最简单的情况。这个表达式没有一点多余的地方，因此学习算法时，如果可能就一定要分析算法的递归版本。

除此之外，也很容易分析它的时间复杂度和空间复杂度。

另外，它也可以很容易地转化为代码：

函数 GCD(a, b)
	如果 b 是...
		0, 则函数的值是 a
		b, 则函数的值是 GCD(b, a除b的余数)

在表达式表示中，每一个表达式的计算都带有上下文或者环境。例如在GCD函数中，对于确定的a和b，我们能获得一个有限长度的GCD表达式，其中每一个子表达式都拥有不同的上下文。内侧GCD函数的b值不同于外侧GCD的b值，因为它们所处的上下文不同，因为内侧的b值是被展开、被代入后的b值，它相当于外侧的a除b的余数。这个上下文，和序列表示中系统状态的变化是严格对应的。

我们说，这两种描述方式在描述能力上是同一的。它们所专有的概念也是相兼容的。因此一般程序设计语言都可以采用这两种范式的任意一种。例如在C语言中我们也有函数、表达式。

计算机系统

现在，我们知道了如何表述一次计算，我们也能够去设想要完成一次计算所需要的基本活动。但是我们究竟有什么东西被计算了？什么是可计算的东西？

计算机的语言是灵魂，它的组成结构则是它的身体。我也找了两个（相互对抗的）角度来理解计算机的身体：数位（digits）和符号（symbol）。

首先是数位计算，它使用位元的组合模式来定义什么是数据。对于每一种计算机架构，往往有不同的数位定义，它们往往与计算机所使用的底层物理结构密切相关——对此，有相当长的历史可以诉说。

古巴比伦时代采用了一套相当原始的数字表示法，参杂着十进制和六十进制、形象化（麦子的形象）和抽象化（条、扎、捆）。在计数法的演变中能找到很多历史的转折，例如，托勒密时代还常常在用的十二进制和六十进制的数字表示法，既有历史原因，也是出于天文计算的需求。

帕斯卡发明滚轮加法器采用的阿拉伯数字，使用这种单一进制的表示法作为机械内部的数据表示方法，简化了机械设计的复杂度，令机械的小型化成为可能。而且，即使要计算像不同欧洲国家的不同货币转换，只需要对输入额外加一层转换模组即可，不需要修改内部的数字表示方式。这一思想到了今天，就是我们使用二进制的位元来表示数据的最早萌芽。（因此可以说，二进制数据本身没有意义，它只是方便计算机处理的东西，只是中间产物，只有交付给人才有意义）

我们如今的手机、电脑这类现代计算机都遵循着冯诺依曼架构，同之前的计算相比，它的最大特点在于它是可编程的，这就是说，计算的描述（代码）本身也以数据的形式交付给计算机。例如在帕斯卡的加法器中我们给出的是「1」「2」然后我们得到「3」，在冯诺依曼机中我们则需要额外给出一个「+」。其之所以可能，在于机器内部实现了一系列指令集，人的输入被当作一条指令，而数据和操作都只是指令之中的一个部分而已。可以说，在现代计算机中，代码同数据的关系是颇为暧昧不清的，在不同的平台上才会重视这种区分。（C语言这样的低级语言是常常和平台特定的指令集打交道的语言，因此在不同的机器上往往会得到不同的结果，而一些高级语言力图脱离特定机器的限制、做到在不同的机器上得到相同的结果）（之所以很多时候区分整型和浮点数，就是因为它们在机器上对应的操作集不同）

如果理解了计算机的组成，那么其他一些不那么明显的常识就变得清晰可见了。比如说，究竟为什么我们需要各种各样的排序算法？答案是，内存的最常见实现方式是使用一个随机访问存储器（RAM），它就像一个书架，你可以从任何地方拿书存书，但是它不会自动为你把书排好序。因此要让一小块内存里的数据排序好，要么我们亲自为其进行一次整理（算法），要么为其配备一套官僚系统（数据结构）来维持书架始终有序。在学校里让人们做的种种题目中，输入往往以一个序列的形式给出的，随后学生常常将它转化成所谓的「数组」，仅是在这不自觉的一步之中，就已经有着一种转换了，即把转瞬即逝的输入流保存在可以不按顺序来获取的记忆中。

然后是符号演算，根据一套基本的推导规则来操作一系列符号。比起前面说的数位计算，这更多是一种思想上的东西，这里只是姑且采用符号的说法。这时，我们不再考虑数字，而是关注符号。我们将机器理解为解释者，而把代码理解为待解释的文本，这两者不是相互外在的东西。例如，把翻译RNA的细胞体当作是机器，把阅读代码的我们当作是机器。去思考它，就是去成为它。

在Minecraft中可以实现一台现代计算机，但是对于运行着Minecraft的这台电脑而言，它只是在进行一系列的运算罢了。没有人会以「能通过人脑编译为机器代码」作为理解一段代码的标准，而只会把这一点当作是理解这台机器的标准。但是，我们脑海中仍然在进行着某种演算，或构思。我们不仅关心代码中那些关乎于机器的部分，还有我们的意图。机器完全可以是概念中的机器，比如Java虚拟机之中存在「垃圾回收」这一机制，然而这一机制不存在物理上的对应物。像代码中各个符号所对应的「引用」「参数」「作用域」「所有权」……这些概念都是为了方便编写程序的人组织自己的思想、描述自己的问题而出现的。这样，我们学习一门语言就不是在学习一台机器或者一台工具，而是在学习一种方法或一套体系。（虽然它们间实际上大同小异）（对此而言，C语言可以说是一门对新手而言相当不友好的编程语言了，因为用它完成一件事的方法有很多，但是支撑着它的概念却常常是较为基础的，有相当多的东西需要试错才能掌握）

所以问题在于「怎么算？」思路是什么？你如何描述自己的问题？你如何将实际的问题转化为概念的语言，因为在这门语言体系中捆绑着现成的解决方案？我们要记得我们在思维这类问题的时候，往往不是打开电脑输入「给我算」。我们一贯是习惯于用纸、笔和脑子来进行计算的，而现在只是把其中的一些步骤分派给了计算机去做而已。前置的、概念上的梳理工作仍然是必需的，仅当我们进行过了大量的运思、以至于形成了某种直观的连接后，我们才会直接上手写代码。

例如，大多数语言都允许我们定义结构化的数据，例如C语言中的「结构体」：

struct C {
	int a;
	int b;
}

这段代码究竟会在机器上执行什么吗？不一定，但它一定会在机器上产生某种效果，造成某种约束，以令对C结构体中的c成员的访问是不可能的。这类约束或限定的工作就是思想上的工作，它保证了语义上的一致性。当它被翻译为机器代码，就不再有C了，只剩下单纯的约束效果还存在着。这个约束是被运思的东西之中最基本的东西之一，它的例子有「条件」「类型」「边界」……某种程度上讲，编程就是适当地施加约束的技艺，在讲述数据结构和算法的时候，可以更清楚地看到这一点。

可以海德格尔关于工具的「应手-在手」对子来说明这两个角度：当我们上手直接做事时，我们不会劳心去观察工具的外观；而当我们遇到了障碍、工具显得不那么趁手时，我们停下来观察手中的工具。对工具的掌握即是掌握了的工具：理解了计算机的底层构成，能让我们更自如地运思而不逾越限度；而有着一套成熟的解决问题的体系化的知识，回过头去倒推具体的实现也更加容易。

数据结构及算法

我们使用数据结构，最终是因为它能以更小的代价获得同样的成效，这个代价可以用时间和空间方面去衡量。对于大多数冠以「实现某某数据结构/算法」的问题而言，因为我们所使用的机器是一种特殊的机器（一种冯诺依曼机的实现），所以数据结构所追求的效率都是在此基础之上计算的代价最小化。在大多数情况下，我们所编程的是单个逻辑处理器所进行的操作，我们要操作的数据往往在内存之中。如果不考虑这一点，我们完全可以通过引入特殊硬件来计算同样的问题。例如通过显卡来处理一些数据，这时我们所依据的是完全不同的架构，给出的算法也颇有不同。所以完整问题实际上是「在某某架构之上解决某个问题，以求最大化地利用硬件资源」。

一切数据结构/算法都是针对具体的情况的（给定硬件和问题，方案择优）。从这个根本的角度上说，对于数据结构和算法的区分是不存在的，仅仅是在处理时间和空间上的代价时所采用的策略上的区别。有时候主要是为了减少时间成本，比如数据库本身会花费一些空间来存储日志文件，以便遇到问题时能够更快地恢复。有时候主要是为了减少空间成本，比如在内存有限的情况下处理大规模数据。总之这部分工作说到底就是节省各种现实资源的成本。「编程」一词在原始意义上，就是针对各种类型的资源进行安排。

所以课堂中教的各种数据结构和算法，其实都是非常特殊的工具，在实际工作之中很少会需要自己去实现它们，因为针对固定的架构和多数问题，各种语言的标准库里往往都会有足够好的现成解决方案。因此应该在同两个方面的联系之中学习这门学科：理解这些工具所诞生的渊源，知道书中每个算法的限制；把握这些解决方案中共通的思想，知道如何选择算法。

对于课堂教学中所给出的问题，我们可以这样来分析我们架构：

当老师说「排序问题」时，他往往说的是「不引入自定义的数据结构来进行排序」，也就是说「排序一个数组」，那么理想的方案当然就是「归并排序」「快速排序」这类时间代价为$n\log{n}$的算法了。但是排序问题本身并不一定限定在这个特定的数据结构上，对于不同结构的数据，不同算法的代价是不同的，选择的方案也就有所不同。例如对于链表，它不具有可随机访问的性质，因此普通的查询操作也需要更多的时间代价（因为需要遍历链表元素），所以我们会选用访问次数较少的排序算法，这时课本中给出的算法能用得上的就很有限了（一般也很少使用链表来存储需要排序的数据）。再比如对于红黑树、二叉树这种数据结构，它本身就是某种有序的结构，「排序」在这个意义之下就是按照它提供的规范去插入和查询其中的元素而已。

模糊地说，数据结构的特点就是它的限制是在空间上的，算法的特点就是它的限制是在时间上的。如何理解这一点？

对于前者而言，我们对一片空间范围内的操作进行限制，以保证这片空间上的结构上（相对空间位置上）的一致性；对后者而言，我们对一段时间范围内操作进行限制，以保证这段时间从开始到结束的趋势上（几个关键特征上）的一致性。所以程序设计的关键就在于构建出约束，并遵守这个约束。

要设计一个数据结构或算法，就要记住：在每次操作前后、每个周期的开始和结束，有什么东西是不变的。有些不变的东西是不会变的，例如结构定义、应用在什么之上。而有些不变的东西需要你自觉加以限制，比如对操作或步骤的实现。

要对一个既有的数据结构或算法进行分析，可以沿着类似的思路，去寻找其中的种种约束，并且思考为什么作者要施加这种约束。一般来说，这类分析都需要参照着算法的实际运行或者图示来进行分析，只是看描述或者代码是比较困难的。以Dijkstra最短路径算法为例进行分析。

这一小片精神，这一小块血肉，随你处置，愿你善待它