编程导论——第1章：起步

计算机只能做两件事，执行计算并记录计算的结果，但是它把这两件事完成得非常漂亮。常见的台式机和笔记本电脑每秒钟可以执行近10亿次计算，快得难以置信。想象一下，让一个球从1米高自由落体掉到地板上，就在这段时间内，你的计算机可能已经执行了10亿条指令。从内存角度来说，一台普通的计算机可能有几百GB（gigabyte，1 gigabyte是10亿字节）。几百GB到底有多大呢？如果一字节（byte，1字节等于8比特，用来表示一个字符）重一盎司（实际上当然没有这么重），那么100 GB总重量会超过300万吨，几乎和美国一年的煤炭产量相同。 在漫长的人类历史上，计算的速度受限于人脑的计算速度以及书写结果的速度。这也就是说人们只能计算最小的问题。即使现代计算机的速度已经如此之快，仍然有很多问题无法计算（例如，气候变化），但是越来越多的问题是可以通过计算来解决的。我们希望当你学完本书时，可以使用计算思维来解决工作、学习或者日常生活中遇到的大部分问题。 那么，到底什么是计算思维呢？ 所有的知识都可以归结为两类：陈述性知识和指令性知识。陈述性知识是由事实陈述组成的。例如，“当y*y=x时，x的平方根是数字y”，这是一个事实的陈述。可惜，我们无法得知如何计算平方根。 指令性知识表达的是“怎么做”，或者说演绎信息的方法。亚历山大里亚的希罗（Heron of Alexandria）是第一个记录如何计算一个数的平方根的人。 他的方法可以总结成这样。 随机选择一个数g。如果g*g和x足够接近，停止并宣布g是答案；否则选择一个新的数，取g和x/g的平均值，也就是(g+x/g)/2。使用新选择的数来代替g并重复这个过程，直到g*g和x足够接近。 思考下面这个例子，计算25的平方根： (1) 随意选择一个数作为g，比如3； (2) 3*3=9，通过判断可知这个数不够接近25； (3) 将g替换为(3+25/3)/2=5.67 ； (4) 5.67*5.67=32.15，仍然不够接近25； (5) 将g替换为(5.67+25/5.67)/2=5.04； (6) 5.04*5.04=25.4和25足够接近，所以我们停止计算并宣布5.04是25平方根的合适近似值。 注意，这个方法描述的是一系列简单的步骤，结合一个控制流程来决定步骤的执行顺序。这样的描述称为算法 。这个算法就是猜测和验证算法的一个例子。它基于这样一个事实：我们很容易验证一个猜测是否足够好。 更严谨的说法是，一个算法就是一个有穷指令序列，描述了在给定输入上的一个计算过程，这个计算过程经过一系列事先定义好的状态，最终产生一个输出。 算法有点像菜谱： ① 加热蛋奶混合液； ② 搅拌； ③ 将勺子放入蛋奶混合液中； ④ 拿出勺子并用手指在勺子背面抹一下； ⑤ 如果勺子背面出现明显的痕迹，停止加热，并冷却蛋奶混合液； ⑥ 否则重复整个过程。 这个算法包含一些测试，用来判断过程是否完成，还包含一些和执行顺序相关的指令，有时会基于一个测试来跳转到其他指令。 那么如何把菜谱的思想应用到机械过程中呢？一种方法是设计一个专门计算平方根的机器。听起来可能很奇怪，但是最早的计算机器就是固定程序计算机，也就是说，它们的设计目的就是做非常具体的事情，而且大多数情况下用来解决具体的数学问题，例如计算炮弹的弹道。最早的计算机之一（1941年由阿塔纳索夫和贝里制造）被设计用来解线性方程组，除此之外什么都不能做。二战期间，阿兰•图灵设计的名为炸弹（bombe）的机器，仅仅用来破解德国的Enigma编码。一些非常简单的计算机仍然使用这种方法。例如，四功能计算器就是一个固定程序计算机，只能做基本的数学运算，不能用来处理文本或者玩电子游戏。要改变这类机器的程序，只能更换电路。 第一台真正的现代计算机是Manchester Mark 1。和它的前辈不同，Manchester Mark 1 是程序存储计算机。这样的计算机存储（并操作）一个指令序列，且有一个元素集合，这些元素会执行序列中的指令。通过创建指令集结构并将计算分解为一个指令序列（也就是一个程序），我们可以制造高度可扩展的机器。程序存储计算机可以轻易地改变程序，因为它可以在程序的控制下用处理数据的方式来处理这些指令。实际上，计算机的核心变成了一个可以运行任意合法指令集的程序（叫作解释器），它可以计算任何能用基本指令集描述的东西。 需要操作的程序和数据都存储在内存中。一般来说，会有一个程序计数器指向内存中的特定位置，这个位置上的指令会被当作计算的开始。大多数情况下，解释器仅仅是继续执行序列中的下一条指令。但在有些情况下，它会执行一个测试，根据测试结果的不同，可能会跳转到序列中的其他位置，这叫作控制流。控制流非常重要，有了它，我们就可以编写完成复杂任务的程序。 再回到菜谱这个比喻上来，如果给一个优秀厨师一组固定的原料，他可以通过不同的组合方式创造出无限种美食。同理，给一个优秀程序员一组固定的初始元素，他可以创造出无限种有用的程序。这就是编程如此让人吃惊的原因。 要创造菜谱，或者说指令序列，我们需要一门编程语言来描述它们，从而向计算机发号施令。 1936年，英国数学家阿兰•图灵提出了一种理论计算设备，叫作通用图灵机。这个机器有一条无限长的纸带作为内存，纸带上可以记录0、1以及一些非常简单原始的指令，用来移动、读取和输出内容到纸带。邱奇图灵论题宣称，如果一个函数是可计算的，那么图灵机一定可以通过编程来计算它。 邱奇图灵论题中的“如果”非常重要。并不是所有问题都有可计算的解。例如，图灵提出，不可能写这样一个程序：给定一个任意的程序P，当且仅当P永不停止时输出true。这就是著名的停机问题。 邱奇图灵论题直接导致了图灵完备性这个概念的提出。当一门编程语言可以用于模拟一个通用图灵机时，我们才说它是图灵完备的。因此，任何可以用一门编程语言（比如Python）编写的程序都可以用另一门编程语言（比如Java）来编写。当然，有的东西使用特定的语言更容易编写，但是所有语言的计算能力都是等价的。 幸好，程序员并不需要使用图灵的原始指令来编写程序，现代编程语言提供了一个更大并且更实用的原始指令集。然而，编程的基本思想仍然是组装一个操作的序列。 无论使用什么原始指令集，无论用何种方法来使用它们，编程的优势和劣势都是一样的：计算机只能做你让它做的事。优势在于，你可以随意创造有趣和有用的东西。劣势在于，当它没有按照你的想法来运行时，你只能从自身找原因。 世界上有成百上千种编程语言，并没有哪个是最好的（不过或许你可以找出一些最坏的）。对于不同类型的应用程序来说，不同的语言可能有好有坏。比如MATLAB非常适合操作向量和矩阵，C语言非常适合用来开发控制数据网络的程序，PHP非常适合用来开发网站，Python则是一个多面手，可以胜任很多种工作。 每种编程语言都有基本结构、语法、静态语义和语义。可以用一门自然语言类比，拿英语来说，基本结构是单词，语法描述了哪些单词串可以构成结构正确的句子，静态语义定义了哪些句子是有意义的，语义定义了这些句子的含义。Python的基本结构包括字面量（例如，数字3.2和字符串'abc'）以及中缀运算符（例如+和/）。 一门语言的语法定义了哪些字符和符号串的结构是有效的。例如，英语中词串“Cat dog boy”从语法角度来说不是一个有效的句子，因为英语的语法并不承认名词+名词+名词这种句子结构。在Python中，原语序列3.2+3.2从语法角度来说是有效的，但序列3.2 3.2就不是。 静态语义定义了哪些语法有效的字符串是有意义的。在英语中，字符串“I are big”的结构是代词+系词+形容词，这是语法有效的序列。但它并不是有效的英语，因为代词“I”是单数，但是系动词“are”是复数。这就是典型的静态语义错误。在Python中，序列3.2/'abc'是语法有效的（字面量+操作符+字面量），但因为数字并不能被字符串除，所以产生了一个静态语义错误。 一门语言的语义就是给每个语法有效且没有静态语义错误的符号串关联一个含义。在自然语言中，句子可能有二义性。例如，句子“I cannot praise this student too highly”可能是称赞也可能是谴责。编程语言的设计保证了每个合法的程序都只有一个明确的含义。 尽管语法错误是最常见的一种错误（尤其是在学习新编程语言时），它却是最不具危险性的一种。每种严肃的编程语言都会做完整的语法错误检测，绝对不允许用户执行有语法错误的程序。此外，大多数情况下语言系统都会提供足够清晰的错误提示，指出错误发生的位置，让用户很明确地知道如何修复错误。 静态语义错误就有一点复杂。一些编程语言，比如Java，在允许程序执行之前会做非常多的静态语义检查。其他语言，比如C和Python，（唉！）相比之下只做很少的静态语义检查。Python在运行程序时确实会做很多静态语义检查，但并不会捕获所有静态语义错误。如果这些错误没有被检测到，程序的行为通常就会无法预料。后面我们会看到一些这样的例子。 通常大家并不会说一个程序有语义错误。如果一个程序没有语法错误也没有静态语义错误，它就必然有含义；也就是说，它有语义。当然，这并不代表它所具有的语义就是编写者所希望的。当程序的含义和编写者所希望的含义不同时，事情就糟糕了。 如果程序有错误并且无法预测它的行为，那会发生什么？  它可能会崩溃，也就是说，停止运行并伴有明显的迹象。在设计良好的计算系统中，一个程序的崩溃不会破坏整个系统。当然，一些非常流行的计算机系统并没有这么好的设计。几乎每个使用个人电脑的人都运行过一个想方设法逼你重启计算机的程序 。  它可能继续运行、运行、运行，永远不会停止。如果你不确定程序需要运行的时间，这种无法停止的情况将很难被发现。  它可能会运行完毕并生成一个可能对也可能错的答案。 这些情况都很不好，相比之下，最后一种最糟糕。如果一个程序看起来好像做了正确的事但是实际上出错了，往往会发生很多不好的事。钱财可能丢失，患者可能会接受致命剂量的放射性治疗，飞机可能会坠毁，等等。 所以，在编写程序时，要尽量让程序在出现异常时可以明显地表现出来。我们之后会讨论如何做到这一点。 动手练习：计算机有时很烦人，如果你不明确地告诉它想让它做什么，它很有可能做错事。试着为在两地之间开车写一个算法。假设你是为某人而写，然后想象一下，如果这个人完全按照算法描述来开车，会发生什么？比如说，他可能会被开多少张罚单？